基于最小跳數(shù)的無線傳感器網(wǎng)絡(luò)能量自適應(yīng)路由算法

摘要：針對基于最小代價的路由算法冗余信息過多和能耗不均衡問題，提出了一種新的路由算法——MHEP算法。新算法通過在網(wǎng)絡(luò)中建立最小跳數(shù)場和路徑節(jié)點最小能量場，使得信息包可以沿著能耗最優(yōu)的路徑向網(wǎng)關(guān)節(jié)點發(fā)送。通過仿真實驗與基于最小代價的路由算法的比較，結(jié)果表明該路由算法在能量節(jié)省和能耗均衡方面具有明顯的優(yōu)勢。

關(guān)鍵詞:無線傳感器網(wǎng)絡(luò)； 路由算法； 最小代價； 最小跳數(shù)； OMNET++仿真

中圖分類號：TP393文獻標志碼：A

文章編號：1001-3695(2007)11-0236-03

無線傳感器網(wǎng)絡(luò)綜合了傳感器技術(shù)、嵌入式計算技術(shù)、分布式信息處理技術(shù)和通信技術(shù)，能夠協(xié)作地實時監(jiān)測、感知和采集網(wǎng)絡(luò)分布區(qū)域內(nèi)的各種環(huán)境或監(jiān)測對象的信息，并對這些信息進行處理，傳送給需要這些信息的用戶[1，2]。無線傳感器網(wǎng)絡(luò)是一種能量有限的網(wǎng)絡(luò)，且能量通常無法得到補充。因此，在無線傳感器網(wǎng)絡(luò)中，有效利用有限的能量資源是任何路由算法首要考慮的因素。無線傳感器網(wǎng)絡(luò)設(shè)計的一個主要目標是最大化網(wǎng)絡(luò)生命期[3]。如果網(wǎng)絡(luò)中某些節(jié)點能量消耗過快，這對網(wǎng)絡(luò)的生存期有很大的影響。所以，每個節(jié)點能耗均衡也是路由算法的重要考慮因素。

本文提出了一種基于最小跳數(shù)的能量自適應(yīng)路由算法（minimum hops energy－adapted protocol，MHEP）。該路由算法的關(guān)鍵思想是利用到sink節(jié)點的最小跳數(shù)（minimum hops count，MHC）和路徑節(jié)點最小剩余能量（minimum path－node energy，MPE ）作為路由選擇度量來完成信息包的轉(zhuǎn)發(fā)。仿真實驗顯示該算法具有良好的性能。

1當(dāng)前研究現(xiàn)狀

無線傳感器網(wǎng)絡(luò)的路由算法是一個非常活躍的研究領(lǐng)域，基于最優(yōu)路徑的路由是其中比較重要的研究方向。目前國內(nèi)外提出了多種基于最優(yōu)路徑的路由算法。這些路由算法中比較有代表性的是基于最小代價的路由算法[4]。該算法中每個節(jié)點只需要維持自己到接收器的最小代價，信息包就可以沿著最小代價路徑向網(wǎng)關(guān)發(fā)送。這個路由算法的缺點是會在網(wǎng)絡(luò)中引起很多的冗余信息，且沒有考慮網(wǎng)絡(luò)的能量消耗。針對該路由算法的不足和缺點，筆者提出了一種基于最小跳數(shù)并充分考慮能耗均衡的最優(yōu)路徑路由算法。

2新算法設(shè)計

算法假定網(wǎng)絡(luò)中節(jié)點分布固定且相對均勻，信息包消耗的總能量可以用經(jīng)過的跳數(shù)來衡量。在初始化階段，首先由sink節(jié)點向網(wǎng)絡(luò)中洪泛最小跳數(shù)場消息，每個接收到該消息的節(jié)點建立或更新自己的最小跳數(shù)場，并保存一個最小跳的next－h(huán)op可用節(jié)點集；之后由sink節(jié)點發(fā)起沿最小跳數(shù)場的方向洪泛路徑節(jié)點最小剩余能量場消息，在網(wǎng)絡(luò)中建立起路徑節(jié)點最小剩余能量場。這樣沿最小跳數(shù)場遞減的方向，每個節(jié)點均建立了到sink節(jié)點的多條路徑，信息包選擇路徑節(jié)點最小剩余能量最大的路徑進行轉(zhuǎn)發(fā)。基于最小跳數(shù)的路由可以保證任何節(jié)點的信息沿著最優(yōu)路徑向網(wǎng)關(guān)節(jié)點發(fā)送，使得整個信息傳輸過程消耗的總能量最小，路徑節(jié)點最小剩余能量的引入可以使得網(wǎng)絡(luò)中節(jié)點的能耗相對均衡，從而最大化網(wǎng)絡(luò)的生存期。另外，針對傳感器節(jié)點能量的變化，算法引入了一種基于通信量的MPE場更新策略。

2．1初始化工作

MHEP路由算法的初始工作階段分成以下兩步：

a)Sink節(jié)點發(fā)起建立MHC場；傳感節(jié)點獲得到sink節(jié)點的最小跳數(shù)信息，并保存next－h(huán)op可用節(jié)點集。

算法采用經(jīng)典的洪泛算法（flooding）來建立MHC場和next－h(huán)op可用節(jié)點集。開始階段，置sink節(jié)點的MHC為0，置其他所有節(jié)點的MHC為無窮大，然后sink節(jié)點向其所有鄰居節(jié)點發(fā)送MHC消息，并置消息的當(dāng)前MHC為0；這些鄰居節(jié)點收到MHC消息后，將自己的MHC置為0+1=1，并生成一個當(dāng)前MHC為1、sender為節(jié)點本身的新消息向其鄰居節(jié)點廣播。

3算法分析和仿真實驗結(jié)果

3．1算法分析

減少網(wǎng)絡(luò)中的冗余信息包是節(jié)省傳感器網(wǎng)絡(luò)能量的一種很有效的方式。在基于最小代價的路由算法中，傳感器節(jié)點需要向所有的鄰居節(jié)點廣播信息包，并由滿足代價要求的節(jié)點向sink節(jié)點轉(zhuǎn)發(fā)。這個過程中將不可避免地產(chǎn)生大量的冗余信息包。MHEP路由算法通過從next－h(huán)op可用節(jié)點集中選擇一個鄰居節(jié)點進行信息包轉(zhuǎn)發(fā)，成功克服了廣播導(dǎo)致的信息包冗余。基于最小代價的信息包轉(zhuǎn)發(fā)過程如圖3（a）所示。本路由算法的信息包轉(zhuǎn)發(fā)情況如圖3（b）所示。可以看出，圖3（a）中節(jié)點1到2、1到4、1到5、1到6和5到7傳送的信息包均是冗余信息包；而圖3（b）沒有冗余信息包的存在。

圖2節(jié)點握手過程圖3路由算法冗余比較

某些關(guān)鍵節(jié)點的失效對網(wǎng)絡(luò)的生存期有很大的影響，節(jié)點能量的均衡消耗也是無線傳感器網(wǎng)絡(luò)路由算法設(shè)計必須考慮的問題。該路由算法采用綜合衡量路徑節(jié)點最小剩余能量的策略，有效地避免了低能量節(jié)點參與數(shù)據(jù)包的轉(zhuǎn)發(fā)，從而很明顯地提高了無線傳感器網(wǎng)絡(luò)的生存期。

3．2算法仿真實驗

算法通過仿真實驗[5]和基于最小代價的路由算法進行了比較。為了準確地反映兩種算法的性能對比，這里限定基于最小代價的路由算法中代價為傳感節(jié)點到sink節(jié)點的跳數(shù)。仿真結(jié)果證明了MHEP算法的有效性。

仿真工具采用OMNET++3.2 p1，網(wǎng)絡(luò)覆蓋面積600×600 m2，網(wǎng)絡(luò)節(jié)點數(shù)目設(shè)置為60個，設(shè)置節(jié)點的傳輸距離為50 m。采用的傳輸信道數(shù)據(jù)傳輸率為250 kbps，出錯率為0，信道延遲為0.3 s，數(shù)據(jù)包長度為128 bit。實驗中，從第4 s開始，每隔4 s，網(wǎng)絡(luò)中均有10個隨機節(jié)點構(gòu)造信息包向sink節(jié)點發(fā)送。網(wǎng)絡(luò)中設(shè)定，所有節(jié)點的初始能量為9 000個能量單位，接收一個消息消耗1個能量單位，發(fā)送一個消息消耗2個能量單位，接收一個信息包消耗2個能量單位，發(fā)送一個信息包消耗4個能量單位。實驗仿真結(jié)果如圖4、5所示。

圖4反映了分別應(yīng)用兩種路由算法在網(wǎng)絡(luò)中引起的能量消耗情況。圖中①代表基于最小代價的路由算法；②代表MHEP路由算法。圖中前4 s是初始化階段，兩種路由算法的能量消耗相差不大；從第4 s開始，網(wǎng)絡(luò)中開始隨機產(chǎn)生信息包，基于最小代價的路由算法產(chǎn)生大量的冗余信息包，能量消耗呈現(xiàn)明顯的上升趨勢，而MHEP路由算法不產(chǎn)生冗余信息包，能量消耗是一種平緩上升的趨勢。這與上面的分析是一致的。可以看出，在能量的節(jié)省方面，MHEP路由算法具有明顯的優(yōu)勢。

圖5反映了在網(wǎng)絡(luò)運行過程中關(guān)鍵節(jié)點的能量過耗情況，仿真假定若某個節(jié)點的現(xiàn)有能量低于初始能量的30%，則該節(jié)點處于低能量狀態(tài)。圖中①表示基于最小代價的路由算法低能量節(jié)點統(tǒng)計狀況；②表示MHEP路由算法低能量節(jié)點統(tǒng)計狀況。基于最小代價的路由算法在第50 s之前就開始出現(xiàn)低能量節(jié)點，而MHEP路由算法在第80 s左右才開始出現(xiàn)低能量節(jié)點；在前200 s內(nèi)，基于最小代價的路由算法產(chǎn)生的低能量節(jié)點數(shù)目為20個，為網(wǎng)絡(luò)所有節(jié)點數(shù)目的1/3，而MHEP路由算法產(chǎn)生的低能量節(jié)點為7個，僅為網(wǎng)絡(luò)節(jié)點數(shù)目的1/9左右。由此看出，在能量均衡消耗方面，MHEP路由算法也具有明顯的優(yōu)勢。

4結(jié)束語

針對基于最小代價的路由算法的缺點和不足，本文提出了一種基于最小跳數(shù)且考慮能耗均衡的路由算法MHEP。該算法通過在網(wǎng)絡(luò)中建立最小跳數(shù)場和路徑節(jié)點最小能量場，使得傳感器節(jié)點的信息包沿著總能量消耗最小且能量最均衡的方向向網(wǎng)關(guān)節(jié)點傳送。該算法通過一種基于通信量的更新策略進行路徑最小能量場的維護，運行維護簡單，且適用于中大規(guī)模的無線傳感器網(wǎng)絡(luò)。仿真實驗表明，該路由算法在能量總消耗和能耗均衡方面表現(xiàn)出了很好的性能。

參考文獻:

[1]TILAK S， ABU－GHAZALEH N B， HEINZELMAN W. A taxonomy of wireless micro－sensor network models[J].Mobile Computing and Communications Review， 2002，1(2):1-8.

[2]AKYILDIZ I F， SU Wei－lian， SANKARASUBRAMANIAM Y， et al. A survey on sensor networks[J].IEEE Communications Magazine， 2002，40(8):102－114.

[3]鄭勇，楊志義，李志剛，等.基于無線傳感器網(wǎng)絡(luò)的網(wǎng)內(nèi)數(shù)據(jù)融合[J].計算機應(yīng)用研究， 2006，23(4):243-245.

[4]YE Fan，CHEN A，LIU Song－wu，et al. A scalable solution to minimum cost forwarding in large sensor networks[C]//Proc of the 10th International Conference on Computer Communications and Networks.Piscataway:IEEE，2001:304-309.

[5]VARGAR A. OMNET++ discrete event simulation system version 3．2 user manual[K/OL].[2006].http://www.omnetpp.org/doc/manual/usman.html.

[6]SOHRABI K，GAO J，AILAWADHI V， et al. Protocols for self－orga￣nization of a wireless sensor network [J]. IEEE Personal Communications， 2000，7(5):16-27.

[7]彭剛，曹元大，鐘偉軍，等.無線傳感器網(wǎng)絡(luò)基于數(shù)據(jù)匯聚的路由[J].計算機工程與應(yīng)用，2005，41(12):12－14.

[8]HILL J L.System architecture for wireless sensor networks[D]. Berkeley: University of California， 2003:15-30.

“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文”