無線傳感器網(wǎng)絡(luò)中AODVjr路由算法改進(jìn)*

摘 要： 目前無線傳感器網(wǎng)絡(luò)主要采用ZigBee協(xié)議，而ZigBee協(xié)議中AODVjr路由算法查找路由時容易引起廣播風(fēng)暴。根據(jù)AODVjr算法中路由請求命令幀結(jié)構(gòu)和路由應(yīng)答命令幀結(jié)構(gòu)的特點(diǎn)，研究出一種改進(jìn)的AODVjr路由算法。改進(jìn)算法中通過命令幀結(jié)構(gòu)中的命令選項保留字，取保留字第0位控制命令幀傳輸?shù)姆较蛐?，該位?表示向該節(jié)點(diǎn)的子節(jié)點(diǎn)方向傳輸，該位為0表示目的地不在該節(jié)點(diǎn)的子節(jié)點(diǎn)范圍內(nèi)。利用OMNET++4.1進(jìn)行的仿真實驗結(jié)果表明，改進(jìn)的AODVjr路由算法能有效減少通信量，降低跳數(shù)，節(jié)約網(wǎng)絡(luò)的整體能量，同時提高了網(wǎng)絡(luò)的傳輸效率。

關(guān)鍵詞： ZigBee； AODVjr； 廣播風(fēng)暴； OMNET

中圖分類號：TP393 文獻(xiàn)標(biāo)志碼：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 引言

無線傳感器網(wǎng)絡(luò)是由大量無處不在的，具有通信與計算能力的微小傳感器節(jié)點(diǎn)密集布設(shè)在監(jiān)控區(qū)域而組成的自組織網(wǎng)絡(luò)，應(yīng)用前景非常廣闊。目前無線傳感器網(wǎng)絡(luò)主要采用基于IEEE 802.15.4協(xié)議標(biāo)準(zhǔn)的ZigBee協(xié)議，ZigBee是一種無限個域網(wǎng)的短距離無線通信技術(shù)，它具有成本低、功耗低、復(fù)雜度低、網(wǎng)絡(luò)容量大、可靠性高等方面的優(yōu)勢[1-3]。

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

1 AODVjr路由思想

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

⑴ AODVjr規(guī)定只能是目標(biāo)節(jié)點(diǎn)對最先到達(dá)的RREQ信號做出響應(yīng)，保證路由無環(huán)路，AODVjr中沒有使用目的節(jié)點(diǎn)序列號。

⑵ AODVjr規(guī)定RERR（Route Error）僅轉(zhuǎn)發(fā)給傳輸失敗的數(shù)據(jù)包的源節(jié)點(diǎn)。

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

⑷ AODVjr由目的節(jié)點(diǎn)定期向源節(jié)點(diǎn)發(fā)送KEEP ALIVE連接信息來維持路由。當(dāng)源節(jié)點(diǎn)在一段時間內(nèi)沒有收到目的節(jié)點(diǎn)發(fā)來的KEEP ALIVE信號時，它認(rèn)為此條路徑失效，必要時重新進(jìn)行路由發(fā)現(xiàn)。

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

2 AODVjr路由存在的問題

AODVjr算法具有靈活的路徑查找功能，其按需產(chǎn)生路由路徑的方式提高了協(xié)議效率，能快速適應(yīng)動態(tài)鏈路環(huán)境，并可支持多播功能。但ZigBee網(wǎng)絡(luò)中的AODVjr路由算法容易引起RREQ廣播風(fēng)暴并耗費(fèi)資源。另外，AODVjr屬于后應(yīng)式的按需Ad hoe網(wǎng)絡(luò)，不會周期性地更新自己的路由信息，只有在需要通信時，才發(fā)起路由查找過程。在ZigBee網(wǎng)狀網(wǎng)絡(luò)里，節(jié)點(diǎn)會移動或者休眠，因此對路由查找使用比較頻繁。為了達(dá)到節(jié)能且降低通信復(fù)雜度的目的，本文對AODVjr算法進(jìn)行了改進(jìn)，針對廣播風(fēng)暴，采用網(wǎng)絡(luò)命令傳輸?shù)姆较蛑笇?dǎo)性，減少信息傳輸?shù)拇螖?shù)。

3 改進(jìn)算法設(shè)計

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

命令傳輸方向位為1表示向該節(jié)點(diǎn)的子節(jié)點(diǎn)方向傳輸，該位為0表示目的地不在該節(jié)點(diǎn)的子節(jié)點(diǎn)范圍內(nèi)，應(yīng)該向該節(jié)點(diǎn)的父節(jié)點(diǎn)傳輸。命令傳輸方向主要是控制命令傳輸?shù)拇笾路较?，避免發(fā)生廣播風(fēng)暴，其算法流程圖如圖2所示。

4 算法分析和仿真結(jié)果分析

根據(jù)ZigBee中網(wǎng)狀路由AODVjr算法和改進(jìn)的AODVjr算法思想，采用OMNET++4.1分別進(jìn)行了模擬，其網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖如圖1所示。在同一種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)下，所有的運(yùn)行環(huán)境和參數(shù)都相同，利用原始AODVjr和改進(jìn)的AODVjr算法，在相同的時間里，對RFD節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)量、消息經(jīng)過的跳數(shù)以及FFD節(jié)點(diǎn)能量變化進(jìn)行統(tǒng)計，得到的結(jié)果如圖3、圖4、圖5所示。

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

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

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

5 結(jié)束語

針對AODVjr算法思想以及網(wǎng)絡(luò)命令幀的格式，本文提出了一種改進(jìn)的AODVjr算法，充分利用AODVjr算法中的命令選項的保留字，進(jìn)行路由的傳輸?shù)姆较蚩刂?，避免廣播風(fēng)暴，降低了跳數(shù)，節(jié)約了能量。經(jīng)過omnet++4.1仿真，證實改進(jìn)之后的AODVjr算法提高了ZigBee網(wǎng)絡(luò)的通信效率。

參考文獻(xiàn)：

[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網(wǎng)絡(luò)的路由協(xié)議研究[J].合肥工業(yè)大學(xué)學(xué)報（自然科學(xué)版），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] 劉瑞霞，李春杰，郭強(qiáng)等.基于ZigBee網(wǎng)狀網(wǎng)絡(luò)的分簇路由協(xié)議[J].計算機(jī)工程，2009.3：167-169