劉瓊

(1.湖南大學軟件學院,湖南長沙 410082;2.湖南人文科技學院教務處,湖南婁底 417001)

無線傳感器網(wǎng)絡分簇路由協(xié)議研究綜述

劉瓊1,2

(1.湖南大學軟件學院,湖南長沙 410082;2.湖南人文科技學院教務處,湖南婁底 417001)

首先分析了無線傳感器網(wǎng)絡區(qū)別于傳統(tǒng)無線網(wǎng)絡的個性化特點,然后從簇頭選舉、簇的形成和數(shù)據(jù)傳輸?shù)确矫娓爬藷o線傳感器網(wǎng)絡分簇路由協(xié)議的研究現(xiàn)狀,最后對無線傳感器網(wǎng)絡路由協(xié)議進行了總結(jié)。

無線傳感器網(wǎng)絡;節(jié)能;路由協(xié)議

作為新一代傳感器網(wǎng)絡,無線傳感器網(wǎng)絡 (W ireless SensorNetwork,WSN)的研究始于 1990年代末期。從 2000年起,國內(nèi)外的無線傳感器網(wǎng)絡研究日趨活躍,取得了很多

研究成果。由于無線傳感器網(wǎng)絡可以使人們在任何時間、地點和任何環(huán)境下獲取大量可靠的信息,所以這已經(jīng)引起了世界上許多國家在軍事領域、工業(yè)領域和學術(shù)領域的極大關注。美國《商業(yè)周刊》認為無線傳感器是全球未來四大新技術(shù)之一,是 21世紀世界最具有影響力的 21項技術(shù)之一。

本文從簇頭選舉、簇的形成、數(shù)據(jù)傳輸?shù)确矫娓爬四壳把芯空咴跓o線傳感器網(wǎng)絡分簇路由協(xié)議節(jié)能方面的相關研究,為進一步研究無線傳感器網(wǎng)絡路由協(xié)議提供參考。

1 無線傳感器網(wǎng)絡特點

無線傳感器網(wǎng)絡是指一組傳感器節(jié)點被部署在監(jiān)測區(qū)域中,這些傳感器節(jié)點以無線通信方式形成一個自組織網(wǎng)絡系統(tǒng),它們協(xié)作的感知、采集并處理網(wǎng)絡覆蓋區(qū)域中感知對象的信息,并發(fā)送給基站[1]。與傳統(tǒng)無線網(wǎng)絡相比它具有如下特點:

1.1 自組織網(wǎng)絡

網(wǎng)絡的部署無需依賴任何預設的網(wǎng)絡設施,節(jié)點通過分層協(xié)議和分布式算法協(xié)調(diào)各自的行為,節(jié)點活躍狀態(tài)下可以快速、自動地組成一個獨立的網(wǎng)絡。

1.2 動態(tài)網(wǎng)絡

傳感器網(wǎng)絡的拓撲結(jié)構(gòu)由于各種因素而改變,如節(jié)點的電能耗盡或自然災害等原因影響失效,各種條件的變化可能造成無線通信鏈路帶寬發(fā)生變化,甚至通信不穩(wěn)定,這些問題要求傳感器網(wǎng)絡系統(tǒng)要能夠適應這種變化,具有動態(tài)系統(tǒng)可重構(gòu)性。

1.3 通信能力受限

傳感器節(jié)點的通信帶寬是有限的,通常僅有幾百 kbps。傳感器節(jié)點的通信范圍與無線電發(fā)送設備的發(fā)送信號強度、接收設備的接收能力及自然環(huán)境 (如山地,樹林)等干擾因素有關。

1.4 以數(shù)據(jù)為中心的網(wǎng)絡

互聯(lián)網(wǎng)中將網(wǎng)絡設備用唯一的 IP地址進行標識,是一個以地址為中心的網(wǎng)絡。無線傳感器網(wǎng)絡節(jié)點是否編號取決于網(wǎng)絡通信協(xié)議的設計,用戶使用無線傳感器網(wǎng)絡查詢事件時,直接將所關心的事件通告給網(wǎng)絡,網(wǎng)絡在獲得指定事件的信息后匯報給用戶。

1.5 電源能量有限

傳感器節(jié)點通常通過自身攜帶的電池供電,能量是非常有限的,由于傳感器節(jié)點的數(shù)量規(guī)模龐大,而且工作的環(huán)境非常復雜甚至有危險的,通過人工更換電池的方式補給能量是不太現(xiàn)實的。

1.6 多跳路由

傳感器節(jié)點覆蓋在一定的區(qū)域外,因此節(jié)點之間采用多跳的通信方式來減少遠距離傳輸能量消耗。

傳統(tǒng)的無線網(wǎng)絡首要目標是提供高可靠性和更高的帶寬;而無線傳感器網(wǎng)絡存在能量受限的問題,因此無線傳感器網(wǎng)絡路由設計大多把能耗最小化作為首要目標。針對以上特點,許多研究人員提出了很多高效節(jié)能的路由協(xié)議。

2 無線傳感器網(wǎng)絡路由協(xié)議研究綜述

LEACH[2]是最早提出的分簇路由協(xié)議,它的基本思想是:以循環(huán)的方式隨機選擇簇頭節(jié)點,將整個網(wǎng)絡的能量負載平均到每個傳感器節(jié)點,從而達到降低網(wǎng)絡能量耗費、延長網(wǎng)絡生命周期的目的。從LEACH執(zhí)行過程我們看出,每輪循環(huán)大致包括了三個階段:簇頭的產(chǎn)生、簇的形成和簇的路由。

簇頭的產(chǎn)生是簇形成的基礎,簇的路由依賴于簇的結(jié)構(gòu)。它們是分簇路由協(xié)議設計的關鍵技術(shù),三者密切相關,但也相對獨立。所有的無線傳感器分簇路由協(xié)議都是圍繞著如何選擇簇頭、如何成簇、如何進行數(shù)據(jù)傳輸來考慮設計的[3]。

2.1 簇頭節(jié)點的優(yōu)化

LEACH采用分布式協(xié)議,算法簡單,基本解決了負載平衡的問題,但是簇頭分布不均,為此 Heinzelman作了改進 (LEACH-C)[4],它采用集中式協(xié)議,在成簇階段各節(jié)點將自身信息和剩余能量匯報給基站 (BS,Base Station),由BS根據(jù)各節(jié)點剩余能量占網(wǎng)絡總能量的比例等指標進行優(yōu)化運算,選出合適的簇首。文獻[5]中引入了剩余能量,使能量消耗比例較低的節(jié)點優(yōu)先當選簇頭,并且進一步改進了閾值大小,該算法綜合考慮了節(jié)點能量和閾值大小對簇頭選擇的影響,使能量更加均衡。

在 LEACH中簇頭的產(chǎn)生具有極大的隨機性,容易出現(xiàn)部分節(jié)點剩余能量相對較小但仍被選為簇頭,此時節(jié)點的能量會很快耗盡,成為“盲節(jié)點”的情況,張怡等人[6]提出了依據(jù)節(jié)點剩余能量的隨機數(shù)生成策略,該策略進一步降低了剩余能量較小的節(jié)點成為簇頭的可能性,進一步均衡網(wǎng)絡能量負載。在 CPRE協(xié)議[7]中,選擇剩余能量大于或等于平均能量且產(chǎn)生的隨機數(shù)小于閾值的節(jié)點為簇頭,并選取離基站較近且具有較高能量的簇頭作為中繼節(jié)點,通過簇間轉(zhuǎn)發(fā)的方式將數(shù)據(jù)發(fā)送到基站。

張磊等人提出了 EDBCM協(xié)議[8],該協(xié)議選擇能量較高且距基站距離的平方較近的節(jié)點為最佳簇頭,進一步降低數(shù)據(jù)轉(zhuǎn)發(fā)的能量損耗。文獻[9]中提出了基于低能量的雙簇頭路由分簇協(xié)議,該協(xié)議使能量最小的 K個節(jié)點盡可能地接近簇頭,同時,在發(fā)送數(shù)據(jù)時在簇內(nèi)選擇能量較大且距離基站較近的節(jié)點作為 Data簇頭,通過雙簇頭的建立,進一步均衡簇內(nèi)和簇間的通信消耗。

2.2 簇的形成

簇頭產(chǎn)生之后,廣播當選的消息給周圍的節(jié)點,周圍的節(jié)點根據(jù)收到的廣播信號強度來決定加入哪一個簇,這是大數(shù)協(xié)議常用的成簇方式。在成簇過程中,不少人綜合能量等因素來考慮簇的規(guī)模和負載均衡問題,提出了不同的成簇方法。

在 PEGASIS協(xié)議[10]中,通過貪婪協(xié)議把節(jié)點組織成一條鏈,數(shù)據(jù)只在相鄰節(jié)點間進行發(fā)送接收,每個節(jié)點在數(shù)據(jù)融合[11]后以最小的功率發(fā)送數(shù)據(jù),并且每輪中只選擇一個簇頭與基站通信。該協(xié)議沒有簇的重構(gòu)開銷,降低了能耗,但是節(jié)點之間由于數(shù)據(jù)的轉(zhuǎn)發(fā)有較大延時。EECS協(xié)議[12],綜合考慮了成員節(jié)點的能量與簇頭到基站的距離能量消耗,從而保證了簇頭的負載均衡。

馬玉剛等人提出了基于固定聚類的節(jié)能算法[13],所有節(jié)點分為固定的聚類,聚類內(nèi)節(jié)點自動輪換擔任簇頭,通過減少聚類區(qū)域內(nèi)節(jié)點之間的信息傳輸,從而減少不必要的能量消耗,更高效地傳送有用數(shù)據(jù),均衡了網(wǎng)絡負載。

以上分簇路由協(xié)議大都是基于均勻分簇的,傳感器節(jié)點間往往采用多跳方式進行通信,一些節(jié)點既要發(fā)送數(shù)據(jù)也要轉(zhuǎn)發(fā)數(shù)據(jù)。同時,數(shù)據(jù)流遵循多對一的模式,離基站較近的節(jié)點需要承擔更多的數(shù)據(jù)轉(zhuǎn)發(fā)任務。因此這些節(jié)點容易過早耗盡自身的能量,導致在基站周圍出現(xiàn)“能量空洞”(energy hole)現(xiàn)象?！澳芰靠斩础爆F(xiàn)象的出現(xiàn)使整個網(wǎng)絡采集的數(shù)據(jù)不能進一步傳送給基站節(jié)點,此時網(wǎng)絡的生存周期提前結(jié)束,但是網(wǎng)絡中仍有大量較高能量的節(jié)點未被充分利用,基于此,李成法等人提出了 EEUC非均勻分簇協(xié)議[14],該協(xié)議分簇時使靠近基站的簇的規(guī)模小于遠離基站的簇,使靠近基站的簇頭有更多的能量為簇間數(shù)據(jù)轉(zhuǎn)發(fā)使用,較好地避免了“能量空洞”的問題。

2.3 簇的數(shù)據(jù)傳輸

無線傳感器網(wǎng)絡中,節(jié)點能量受限,節(jié)點的有效通信半徑也比較小。雖然可以通過調(diào)整發(fā)射功率來增大通信半徑,但由于隨著距離的逐漸變大,信號的空間損耗也迅速增大,因此,在分簇路由協(xié)議中一般采用多跳的傳輸方式來傳輸數(shù)據(jù)以達到節(jié)省能量的目的[15]。

但是,采用多跳傳輸方式并不是節(jié)點之間傳送數(shù)據(jù)采用多跳或是跳數(shù)越多越節(jié)能[16]。一些研究表明[17],節(jié)點距離基站較近時,應避免多跳路由機制,減少路由開銷,當節(jié)點傳輸距離較大時,在限制轉(zhuǎn)發(fā)距離和跳數(shù)的前提下,多跳傳輸策略能夠減少網(wǎng)絡的能量消耗。

目前無線傳感器網(wǎng)絡分簇路由協(xié)議都是綜合考慮了以上一個或多個方面來延長網(wǎng)絡的生命周期。在文獻[18]中,以剩余能量為參數(shù)限制簇頭多跳算法中間節(jié)點的選擇,由Pr im算法生成包括基站在內(nèi)的所有簇頭節(jié)點的最小生成樹,在簇頭剩余能量滿足條件時,使得簇間以最短距離進行多跳通信。在 EEHCA協(xié)議[19]中,由基站根據(jù)節(jié)點剩余能量和簇頭之間的距離選舉簇頭,節(jié)點用單跳和多跳模式交替與簇頭進行通信,從而使簇頭的分布更均勻,節(jié)點的負載更均衡。

3 結(jié)論

通過學者對當前無線傳感器網(wǎng)絡分簇路由協(xié)議的分析研究,可以看出一個好的無線傳感器網(wǎng)絡分簇路由協(xié)議應具備如下特點:

3.1 節(jié)能

采用數(shù)據(jù)融合技術(shù),減少節(jié)點數(shù)據(jù)轉(zhuǎn)發(fā)時不必要的控制信息,合理選擇多跳進行遠距離通信。

3.2 負載平衡

采用不均勻的分簇方式,避免靠近基站的節(jié)點過早的死亡,綜合考慮節(jié)點的剩余能量、與基站的距離以及最優(yōu)數(shù)據(jù)轉(zhuǎn)發(fā)路徑等因素,盡可能解決負載平衡的問題。

[1]任豐原,黃海寧,林闖.無線傳感器網(wǎng)絡[J].軟件學報,2003,14(7):1282-1291.

[2]HE INZELMAN W R,CHANDRAKASAN A,BALAKR ISHNAN H.Energy-efficient communication protocol for wireless microsensor networks[C]//Proceedings of the 33rd hawaii International Conference on System Sciences.Washington,DC:IEEE Computer Society,2000:8020-8030.

[3]沈波,張世永,鐘亦平.無線傳感器網(wǎng)絡分簇路由協(xié)議[J].軟件學報,2006,17(7):1588-1600.

[4]HE INZELMAN W R,CHANDRAKASAN A,BALAKR ISHNAN H.An application-specific protocol architecture forwirelessmicro-sensor networks[J].IEEE Transactions on W ireless Communications,2002,1(4):660-670.

[5]HANDYM J,HAASEM,T IMMERMANN D.Low energy adaptive clustering hierarchywith deterministic cluster-head selection[C]//In:Proc.of the 4th IEEE Conf.on Mobile and W ireless Communicatin Networks.Stockholm:IEEE communications Society,2002:368-372.

[6]張怡,李云,劉占軍,等.無線傳感器網(wǎng)絡中基于能量的簇頭選擇改進算法[J].重慶郵電大學學報,2007,19(5):613-616.

[7]龔本燦,李臘元,蔣廷耀,等.一種基于剩余能量的無線傳感器網(wǎng)絡分簇協(xié)議[J].計算機工程與應用,2008,44(8).

[8]張磊,陳曙.一個新的基于能量和距離的傳感器網(wǎng)絡協(xié)議[J].計算機應用,2008,28(5):1117-1119.

[9]李輝,李臘元,李方云.一種基于低能量的雙簇首 WSN路由算法[J].武漢理工大學學報:交通科學與工程版,2009,33(3):450-453.

[10]L INDSEY S,RAGHAVENDRA C S.PEGASIS:Powerful-efficient gathering in sensor infor mation systems[EB/OL].GregRichardson.Proceedings of IEEE Aerospace Conference of the IEEE Computer SocietyMT.2002:9-16.

[11]王娟,王汝傳,孫力娟.數(shù)據(jù)融合在傳感器網(wǎng)絡協(xié)議中的節(jié)能性分析[J].計算機技術(shù)與發(fā)展,2006,16(11):4-6.

[12]YeM,LiC F,Chen GH,et al.EECS:An energy efficient clustering scheme in wireless sensor networks[C]//In:Proc.of the IEEE Int’1 Performance Computing and Communications Conf.New York:IEEE Press,2005:535-540..

[13]馬玉剛,周群彪.基于 LEACH的無線傳感器網(wǎng)絡節(jié)能算法[J].計算機應用,2009,29(6):1514-1516.

[14]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網(wǎng)絡路由協(xié)議[J].計算機學報,2007,30(1):27-36.

[15]ZHANG Wenya,L IANG Zize.Apower efficient routing protocol for wireless sensor network[C]//Proceedings of the 2007 IEEE International Conference on Networking,sensing and Control(ICNSCp07).Washington,DC:IEEE Computer Society,2007:20-25.

[16]ZHU Jin,PAPAVASS IL I OU S.On the energy-efficientorganization and the lifetime of multihop sensor networks[J].IEEE CommunicationsLetters,2003,7(11):537-539.

[17]尚鳳軍,雷陽.無線傳感器網(wǎng)絡能量有效成簇算法研究[J].小型微型計算機系統(tǒng),2009,30(5):839-842.

[18]王國芳,李臘元,李春林,等.無線傳感器網(wǎng)絡中基于能量約束的簇頭多跳算法[J].傳感技術(shù)學報,2009,22(7):997-1001.

[19]劉述鋼,劉宏立,詹杰,等.無線傳感網(wǎng)絡中能耗均衡的混合通信算法研究[J].通信學報,2009,30(1):12-17.

(責任編校:光明)

Research Summary on Cluster Routing Protocols in W ireless Sensor Network

LIU Q iong1,2

(1.College of Software,Hunan University,Changsha,410082,China;
2.Hunan Institute of Humanities,Science and Technology,Loudi,417001,China)

First compared with traditionalwireless network,the characteristics ofwireless sensor network are analyzed.Then cluster head election,cluster fornation and data transmission etc.are discussedwithin the framework of cluster routingprotocols in wireless sensor ne twork.Finally the development ofwireless sensor network router is summed up.

wireless sensor network;saving energy;routing protocol

TP393

A

1673-0712(2010)02-0024-03

2010-02-15.

劉瓊(1977-),男,湖南雙峰人,湖南人文科技學院助教,湖南大學軟件學院在讀碩士,研究方向:無線傳感器網(wǎng)絡路由協(xié)議。