基于最小跳數的無線傳感器網絡能量自適應路由算法

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

關鍵詞:無線傳感器網絡； 路由算法； 最小代價； 最小跳數； OMNET++仿真

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

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

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

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

1當前研究現狀

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

2新算法設計

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

2．1初始化工作

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

a)Sink節點發起建立MHC場；傳感節點獲得到sink節點的最小跳數信息，并保存next－hop可用節點集。

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

3算法分析和仿真實驗結果

3．1算法分析

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

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

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

3．2算法仿真實驗

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

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

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

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

4結束語

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

參考文獻:

[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]鄭勇，楊志義，李志剛，等.基于無線傳感器網絡的網內數據融合[J].計算機應用研究， 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]彭剛，曹元大，鐘偉軍，等.無線傳感器網絡基于數據匯聚的路由[J].計算機工程與應用，2005，41(12):12－14.

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

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