無線傳感器網絡分簇路由協議研究綜述

劉瓊

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

無線傳感器網絡分簇路由協議研究綜述

劉瓊1,2

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

首先分析了無線傳感器網絡區別于傳統無線網絡的個性化特點,然后從簇頭選舉、簇的形成和數據傳輸等方面概括了無線傳感器網絡分簇路由協議的研究現狀,最后對無線傳感器網絡路由協議進行了總結。

無線傳感器網絡;節能;路由協議

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

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

本文從簇頭選舉、簇的形成、數據傳輸等方面概括了目前研究者在無線傳感器網絡分簇路由協議節能方面的相關研究,為進一步研究無線傳感器網絡路由協議提供參考。

1 無線傳感器網絡特點

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

1.1 自組織網絡

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

1.2 動態網絡

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

1.3 通信能力受限

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

1.4 以數據為中心的網絡

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

1.5 電源能量有限

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

1.6 多跳路由

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

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

2 無線傳感器網絡路由協議研究綜述

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

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

2.1 簇頭節點的優化

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

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

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

2.2 簇的形成

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

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

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

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

2.3 簇的數據傳輸

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

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

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

3 結論

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

3.1 節能

采用數據融合技術,減少節點數據轉發時不必要的控制信息,合理選擇多跳進行遠距離通信。

3.2 負載平衡

采用不均勻的分簇方式,避免靠近基站的節點過早的死亡,綜合考慮節點的剩余能量、與基站的距離以及最優數據轉發路徑等因素,盡可能解決負載平衡的問題。

[1]任豐原,黃海寧,林闖.無線傳感器網絡[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]沈波,張世永,鐘亦平.無線傳感器網絡分簇路由協議[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]張怡,李云,劉占軍,等.無線傳感器網絡中基于能量的簇頭選擇改進算法[J].重慶郵電大學學報,2007,19(5):613-616.

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

[8]張磊,陳曙.一個新的基于能量和距離的傳感器網絡協議[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]王娟,王汝傳,孫力娟.數據融合在傳感器網絡協議中的節能性分析[J].計算機技術與發展,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的無線傳感器網絡節能算法[J].計算機應用,2009,29(6):1514-1516.

[14]李成法,陳貴海,葉懋,等.一種基于非均勻分簇的無線傳感器網絡路由協議[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]尚鳳軍,雷陽.無線傳感器網絡能量有效成簇算法研究[J].小型微型計算機系統,2009,30(5):839-842.

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

[19]劉述鋼,劉宏立,詹杰,等.無線傳感網絡中能耗均衡的混合通信算法研究[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-),男,湖南雙峰人,湖南人文科技學院助教,湖南大學軟件學院在讀碩士,研究方向:無線傳感器網絡路由協議。