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

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

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

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

1 AODVjr路由思想

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

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

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

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

⑷ AODVjr由目的節(jié)點(diǎn)定期向源節(jié)點(diǎn)發(fā)送KEEP ALIVE連接信息來(lái)維持路由。當(dāng)源節(jié)點(diǎn)在一段時(shí)間內(nèi)沒(méi)有收到目的節(jié)點(diǎn)發(fā)來(lái)的KEEP ALIVE信號(hào)時(shí)，它認(rèn)為此條路徑失效，必要時(shí)重新進(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]查找自身路由表，如果沒(méi)有發(fā)現(xiàn)到一條到ffd[0]的有效路徑，于是就發(fā)起路由發(fā)現(xiàn)過(guò)程，構(gòu)建并洪泛RREQ包。ffd[0]選擇最先到達(dá)的RREQ包的傳送路徑ffd[5]-ffd[2]-zc-ffd[0]，并返回RREP信息，ffd[5]收到ffd[0]發(fā)來(lái)的RREP信號(hào)，建立路由路徑，ffd[5]就會(huì)按這條路徑來(lái)發(fā)送緩存的數(shù)據(jù)。同時(shí)ffd[0]定期發(fā)送KEEP_ALIVE包，以維護(hù)路由信息。

2 AODVjr路由存在的問(wèn)題

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

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

在AODVjr中里，路由請(qǐng)求命令幀用來(lái)發(fā)起一個(gè)路由發(fā)現(xiàn)過(guò)程，路由應(yīng)答命令用來(lái)返回路由信息，它們的載荷部分的第二個(gè)字節(jié)命令選項(xiàng)中，低7位保留，為此在改進(jìn)的AODVjr中，可以充分利用這些保留位，改進(jìn)后的命令選項(xiàng)如表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算法，在相同的時(shí)間里，對(duì)RFD節(jié)點(diǎn)發(fā)送的數(shù)據(jù)包數(shù)量、消息經(jīng)過(guò)的跳數(shù)以及FFD節(jié)點(diǎn)能量變化進(jìn)行統(tǒng)計(jì)，得到的結(jié)果如圖3、圖4、圖5所示。

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

圖4上表示在AODVjr算法下，各個(gè)RFD節(jié)點(diǎn)上消息跳數(shù)，圖4下表示在改進(jìn)的AODVjr算法下，各個(gè)RFD節(jié)點(diǎn)上消息跳數(shù)。從圖4中可以看出，改進(jìn)的AODVjr算法在相同的時(shí)間里，RFD上統(tǒng)計(jì)的跳數(shù)的次數(shù)比原始AODVjr多很多，這一點(diǎn)與圖3的仿真結(jié)果是一致的。另外，從圖4可以看出，下圖的跳數(shù)比較穩(wěn)定，變化的幅度沒(méi)有上圖大，而且上圖的節(jié)點(diǎn)上消息的跳數(shù)大都在10跳以上，下圖最多只有6.0跳。這說(shuō)明改進(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)通信時(shí)，都必須過(guò)這兩個(gè)FFD節(jié)點(diǎn)，由于改進(jìn)的AODVjr加入了方向控制，為此，這兩個(gè)節(jié)點(diǎn)的能量耗費(fèi)比沒(mé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ù)時(shí)需要用到，而從圖3可以看出改進(jìn)AODVjr中RFD收發(fā)數(shù)據(jù)量都比原始AODVjr中RFD收發(fā)數(shù)據(jù)量多，由于原始AODVjr沒(méi)有進(jìn)行數(shù)據(jù)包傳輸方向控制，在查找路由時(shí)使用了廣播，為此，在原始AODVjr中FFD[3]能量耗費(fèi)比改進(jìn)AODVjr中FFD[3]能量耗費(fèi)快。

5 結(jié)束語(yǔ)

針對(duì)AODVjr算法思想以及網(wǎng)絡(luò)命令幀的格式，本文提出了一種改進(jìn)的AODVjr算法，充分利用AODVjr算法中的命令選項(xiàng)的保留字，進(jìn)行路由的傳輸?shù)姆较蚩刂?，避免廣播風(fēng)暴，降低了跳數(shù)，節(jié)約了能量。經(jīng)過(guò)omnet++4.1仿真，證實(shí)改進(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] 杜煥軍，張維勇，劉國(guó)田.ZigBee網(wǎng)絡(luò)的路由協(xié)議研究[J].合肥工業(yè)大學(xué)學(xué)報(bào)（自然科學(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ì)算機(jī)工程，2009.3：167-169