無線傳感器網絡中AODVjr路由算法改進*

摘 要： 目前無線傳感器網絡主要采用ZigBee協議，而ZigBee協議中AODVjr路由算法查找路由時容易引起廣播風暴。根據AODVjr算法中路由請求命令幀結構和路由應答命令幀結構的特點，研究出一種改進的AODVjr路由算法。改進算法中通過命令幀結構中的命令選項保留字，取保留字第0位控制命令幀傳輸的方向性，該位為1表示向該節點的子節點方向傳輸，該位為0表示目的地不在該節點的子節點范圍內。利用OMNET++4.1進行的仿真實驗結果表明，改進的AODVjr路由算法能有效減少通信量，降低跳數，節約網絡的整體能量，同時提高了網絡的傳輸效率。

關鍵詞： ZigBee； AODVjr； 廣播風暴； OMNET

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2013）01-09-03

Improvement of AODVjr routing algorithm in wireless sensor network

Zou Guoxia， Tang Jianqing

（Guilin University of Aerospace Technology， Guilin， Guangxi 541004， China）

Abstract： At present， ZigBee protocol is mainly applied in wireless sensor network. However， it is easier to arouse a broadcast storm when using the AODVjr routing algorithm. According to the characteristics of AODVjr algorithm， that is， route-requesting command frame structure and the route-replying command frame structure， an improved AODVjr routing algorithm is designed. The improved algorithm reserves word by commanding options in the command frame structure， and controlling the direction of command frame transmission by using the reserved word 0. If the bit is 1， the frame should be forward to the child node of the current node. Otherwise， the destination node is not a child node of the current node. The simulation result by using OMNET++4.1shows that the improved AODVjr routing algorithm can effectively reduce traffic， and save the overall energy of the network， while improving the efficiency of network transmission.

Key words： ZigBee； AODVjr； broadcast storm； OMNET

0 引言

無線傳感器網絡是由大量無處不在的，具有通信與計算能力的微小傳感器節點密集布設在監控區域而組成的自組織網絡，應用前景非常廣闊。目前無線傳感器網絡主要采用基于IEEE 802.15.4協議標準的ZigBee協議，ZigBee是一種無限個域網的短距離無線通信技術，它具有成本低、功耗低、復雜度低、網絡容量大、可靠性高等方面的優勢[1-3]。

ZigBee協議網絡層采用Cluster-Tree和AODVjr路由算法。AODVjr算法是AODV（Ad hoe On Demand Distance Vector， Ad hoc按需距離矢量路由協議）算法的簡化，它跟AODV一樣，與目標節點通信時，采取先找路由，再發送數據或命令的辦法。本文充分利用AODVjr算法中的命令選項的保留字，取保留字第0位控制路由的方向性，該位為1表示向該節點的子節點方向傳輸，該位為0表示目的地不在該節點的子節點范圍內。經過omnet++4.1仿真，證實了改進后的AODVjr算法提高了ZigBee網絡的通信效率。

1 AODVjr路由思想

AODVjr是在AODV的基礎上發展而來的，是AODV算法的簡化，其思想[4-6]如下。

⑴ AODVjr規定只能是目標節點對最先到達的RREQ信號做出響應，保證路由無環路，AODVjr中沒有使用目的節點序列號。

⑵ AODVjr規定RERR（Route Error）僅轉發給傳輸失敗的數據包的源節點。

⑶ 在數據傳輸中如果發生鏈路中斷，AODVjr采用本地修復，在路由修復的過程中，僅允許目的節點回復RREP。如果本地修復失敗，則發送RERR到數據包的源節點，通知它由于鏈路中斷而引起目的節點不可達。RERR的格式也被簡化至僅包含一個不可達的目的節點。

⑷ AODVjr由目的節點定期向源節點發送KEEP ALIVE連接信息來維持路由。當源節點在一段時間內沒有收到目的節點發來的KEEP ALIVE信號時，它認為此條路徑失效，必要時重新進行路由發現。

如圖1所示，當rfd[0]設備要發送數據給ffd[0]，rfd[0]先把數據發送給具有路由功能的父節點ffd[5]，ffd[5]查找自身路由表，如果沒有發現到一條到ffd[0]的有效路徑，于是就發起路由發現過程，構建并洪泛RREQ包。ffd[0]選擇最先到達的RREQ包的傳送路徑ffd[5]-ffd[2]-zc-ffd[0]，并返回RREP信息，ffd[5]收到ffd[0]發來的RREP信號，建立路由路徑，ffd[5]就會按這條路徑來發送緩存的數據。同時ffd[0]定期發送KEEP_ALIVE包，以維護路由信息。

2 AODVjr路由存在的問題

AODVjr算法具有靈活的路徑查找功能，其按需產生路由路徑的方式提高了協議效率，能快速適應動態鏈路環境，并可支持多播功能。但ZigBee網絡中的AODVjr路由算法容易引起RREQ廣播風暴并耗費資源。另外，AODVjr屬于后應式的按需Ad hoe網絡，不會周期性地更新自己的路由信息，只有在需要通信時，才發起路由查找過程。在ZigBee網狀網絡里，節點會移動或者休眠，因此對路由查找使用比較頻繁。為了達到節能且降低通信復雜度的目的，本文對AODVjr算法進行了改進，針對廣播風暴，采用網絡命令傳輸的方向指導性，減少信息傳輸的次數。

3 改進算法設計

在AODVjr中里，路由請求命令幀用來發起一個路由發現過程，路由應答命令用來返回路由信息，它們的載荷部分的第二個字節命令選項中，低7位保留，為此在改進的AODVjr中，可以充分利用這些保留位，改進后的命令選項如表1所示。

命令傳輸方向位為1表示向該節點的子節點方向傳輸，該位為0表示目的地不在該節點的子節點范圍內，應該向該節點的父節點傳輸。命令傳輸方向主要是控制命令傳輸的大致方向，避免發生廣播風暴，其算法流程圖如圖2所示。

4 算法分析和仿真結果分析

根據ZigBee中網狀路由AODVjr算法和改進的AODVjr算法思想，采用OMNET++4.1分別進行了模擬，其網絡拓撲結構圖如圖1所示。在同一種網絡拓撲結構下，所有的運行環境和參數都相同，利用原始AODVjr和改進的AODVjr算法，在相同的時間里，對RFD節點發送的數據包數量、消息經過的跳數以及FFD節點能量變化進行統計，得到的結果如圖3、圖4、圖5所示。

圖3上表示在AODVjr算法下，各個RFD節點收到的數據包的數量，圖3下表示在改進的AODVjr算法下，各個RFD節點收到的數據包的數量。從圖3中可以看出，改進的AODVjr算法在相同的時間里，傳送的數據包的量比原始AODVjr算法要大得多，這說明改進后的AODVjr算法提高了通信效率。

圖4上表示在AODVjr算法下，各個RFD節點上消息跳數，圖4下表示在改進的AODVjr算法下，各個RFD節點上消息跳數。從圖4中可以看出，改進的AODVjr算法在相同的時間里，RFD上統計的跳數的次數比原始AODVjr多很多，這一點與圖3的仿真結果是一致的。另外，從圖4可以看出，下圖的跳數比較穩定，變化的幅度沒有上圖大，而且上圖的節點上消息的跳數大都在10跳以上，下圖最多只有6.0跳。這說明改進后的AODVjr算法減少了跳數。

圖5上是原始AODVjr中FFD節點和中心協調器能量變化圖，圖5下是改進AODVjr中FFD節點和中心協調器能量變化圖。起初中心協調器能量為30000，FFD節點為20000，黃色和綠色曲線分別表示FFD[1]和FFD[6]，從圖1可以看出，RFD[3]與其他節點通信時，都必須過這兩個FFD節點，由于改進的AODVjr加入了方向控制，為此，這兩個節點的能量耗費比沒有改進的AODVjr要快很多。藍色曲線表示FFD[3]節點能量變化，從圖1可以看出FFD[3]節點只有RFD[1]節點發生數據和接收數據時需要用到，而從圖3可以看出改進AODVjr中RFD收發數據量都比原始AODVjr中RFD收發數據量多，由于原始AODVjr沒有進行數據包傳輸方向控制，在查找路由時使用了廣播，為此，在原始AODVjr中FFD[3]能量耗費比改進AODVjr中FFD[3]能量耗費快。

5 結束語

針對AODVjr算法思想以及網絡命令幀的格式，本文提出了一種改進的AODVjr算法，充分利用AODVjr算法中的命令選項的保留字，進行路由的傳輸的方向控制，避免廣播風暴，降低了跳數，節約了能量。經過omnet++4.1仿真，證實改進之后的AODVjr算法提高了ZigBee網絡的通信效率。

參考文獻：

[1] ChakeresID， Klein-Berndt. AODVjr， AODV Simplified[J]. Mobile Computing and Communication Review，2002.6（3）：100-101

[2] Baront P， Pillai P， Chook V W C. Wireless sensor networks： Asurvey on the state of the art and the 802.15.4 and ZigBee stand-stards[J].Computer Communications，2007.30（7）：1655-1695

[3] Akaka K， Youngish M. A Survey on Routing Protocols for Wireless Sensor Networks[J].Ad Hoc Networks，2005.3（3）：325-349

[4] 杜煥軍，張維勇，劉國田.ZigBee網絡的路由協議研究[J].合肥工業大學學報（自然科學版），2008.10：85-89

[5] Seong Hoon Kim， Poh Kit Chong， Woncheol Cho.Location-Free

Semi-Directional Flooding for On-Demand Routing in Low-Rate Wireless Mesh Networks[J].ICCCN’2011，2011：1-7

[6] 劉瑞霞，李春杰，郭強等.基于ZigBee網狀網絡的分簇路由協議[J].計算機工程，2009.3：167-169