基于ZigBee網(wǎng)絡(luò)的AODV路由改進(jìn)算法

常赟杰+張位勇+李桂香

摘要：針對AODV協(xié)議算法會產(chǎn)生冗余RREQ報文，導(dǎo)致網(wǎng)絡(luò)擁塞的缺點(diǎn)，提出一種能量有效的改進(jìn)算法EE-AODV。EE-AODV在路由發(fā)現(xiàn)過程中，通過設(shè)定定時器選擇跳數(shù)少、剩余能量高、鏈路質(zhì)量好的節(jié)點(diǎn)進(jìn)行數(shù)據(jù)包的轉(zhuǎn)發(fā)。實(shí)驗(yàn)證明，EE-AODV減少了ZigBee網(wǎng)絡(luò)中RREQ報文的數(shù)量、降低了數(shù)據(jù)包的時延，降低了網(wǎng)絡(luò)整體能耗，提高了網(wǎng)絡(luò)生存周期。

關(guān)鍵詞：ZigBee；AODV路由；能量有效；剩余能量；鏈路質(zhì)量

中圖分類號：TP393 文獻(xiàn)標(biāo)識碼：A 文章編號：1009-3044（2017）06-0022-02

Abstract：The AODV protocol has disadvantage of large numbers of redundant data which will lead to network congestion.An energy efficient improved AODV routing （EE-AODV） was proposed. EE-AODV choose the nods which have lower number of hops， higher level of the， remaining energy， and higher of the link quality to broadcast the packet during the route-discovery process. Experiment shows that the EE-AODV prolongs the ZigBee networks lifetime for reducing the number of RREQs the energy consumption， and decreasing the network delay.

Key words：Zigbee； AODV routing； energy efficient； remaining energy； link quality

1 概述

ZigBee作為物聯(lián)網(wǎng)的關(guān)鍵技術(shù)之一，以其功耗低、數(shù)據(jù)傳輸可靠、組網(wǎng)靈活、數(shù)據(jù)傳輸安全性好和低成本的優(yōu)勢廣泛地應(yīng)用于智能家居、智能交通、工業(yè)自動化以及醫(yī)療等各個領(lǐng)域[1]。在網(wǎng)絡(luò)層，ZigBee采用樹路由和AODV兩種路由協(xié)議。AODV協(xié)議適用于Mesh網(wǎng)絡(luò)，具有較低的數(shù)據(jù)傳輸時延，但是該協(xié)議在路由發(fā)現(xiàn)過程中，會產(chǎn)生大量冗余的RREQ報文。如果網(wǎng)絡(luò)規(guī)模過大，就會產(chǎn)生廣播風(fēng)暴，造成網(wǎng)絡(luò)擁塞，浪費(fèi)了網(wǎng)絡(luò)資源。現(xiàn)有研究結(jié)果 [2-6]表明，傳統(tǒng)的AODV改進(jìn)算法都沒有將轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇和限制廣播報文進(jìn)行有機(jī)結(jié)合。另外一些過于復(fù)雜的算法，增加節(jié)點(diǎn)到計算和存儲開銷，反而加大了網(wǎng)絡(luò)的整體能耗。本文提出一種能量有效的AODV改進(jìn)算法，稱為EE-AODV（Energy Efficient-AODV），選擇最優(yōu)節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)數(shù)據(jù)包，限制RREQ報文數(shù)量，減少了網(wǎng)絡(luò)能耗，提高了ZigBee網(wǎng)絡(luò)的命周期。

2 AODV算法存在的問題

AODV（Ad hoc On-demand Distance Vector）是一種按需路由協(xié)議，每個節(jié)點(diǎn)只有在有需要的時候才開啟路由發(fā)現(xiàn)過程。當(dāng)源節(jié)點(diǎn)要發(fā)送數(shù)據(jù)給目的節(jié)點(diǎn)時，若路由表中沒有相應(yīng)的路由，首先廣播RREQ報文來開啟路由發(fā)現(xiàn)過程，節(jié)點(diǎn)收到RREQ報文以后，如果自身不是目的節(jié)點(diǎn)則繼續(xù)廣播該報文。最終目的階段接收到RREQ分鐘以后，停止廣播，回復(fù)一個RREP報文。當(dāng)源節(jié)點(diǎn)收到目的節(jié)點(diǎn)RREP報文后，路由建立完畢，開始發(fā)送數(shù)據(jù)幀。AODV在路由發(fā)現(xiàn)過程中產(chǎn)生大量的廣播報文，隨著網(wǎng)絡(luò)規(guī)模的增加，這些RREQ報文數(shù)量急劇增加，在網(wǎng)絡(luò)中造成洪泛，會導(dǎo)致數(shù)據(jù)包傳送時延增大，數(shù)據(jù)包丟失，嚴(yán)重的情況下會出現(xiàn)網(wǎng)絡(luò)擁塞，導(dǎo)致網(wǎng)絡(luò)中斷。此外，部分RREQ報文的傳輸范圍超過網(wǎng)絡(luò)的最大跳數(shù)，傳輸次數(shù)達(dá)到最大時會被節(jié)點(diǎn)丟棄，造成網(wǎng)絡(luò)能力的浪費(fèi)。

AODV算法在選擇轉(zhuǎn)發(fā)路由中總是選擇最少跳數(shù)的路由。但是如果最短路徑中的某些節(jié)點(diǎn)如果能量偏低，頻繁使用該路徑會導(dǎo)致節(jié)點(diǎn)能量提前耗盡能量，使得路由失效。節(jié)點(diǎn)重新發(fā)起路由發(fā)現(xiàn)過程又會導(dǎo)致網(wǎng)絡(luò)中大量RREQ報文泛濫，加大了網(wǎng)絡(luò)能耗。同樣的，如果最短路徑中某些節(jié)點(diǎn)之間的通信鏈路質(zhì)量差，會導(dǎo)致數(shù)據(jù)包丟失的概率增大，節(jié)點(diǎn)將不得不耗費(fèi)大量精力進(jìn)行數(shù)據(jù)包的重傳，導(dǎo)致節(jié)點(diǎn)提前耗盡能量。

3 AODV改進(jìn)算法

EE-AODV在路由發(fā)現(xiàn)過程中，設(shè)定一個定時器來選擇最優(yōu)節(jié)點(diǎn)發(fā)送的RREQ報文，以減少路由發(fā)現(xiàn)過程中RREQ報文的數(shù)量，降低數(shù)據(jù)包洪泛的發(fā)生。定時器的設(shè)置以后，節(jié)點(diǎn)接收到第一個數(shù)據(jù)包以后，等待一段時間接受更多的RREQ包，從中選擇最優(yōu)的RREQ包，以選擇最佳的轉(zhuǎn)發(fā)節(jié)點(diǎn)。定時器時間和節(jié)點(diǎn)接收到的RREQ包的數(shù)量成正比，定時器按照下面公式設(shè)置：

首先，在路由發(fā)現(xiàn)過程中的RREQ報文中增加節(jié)點(diǎn)的剩余能量和RSSI的值，原AODV包中，跳數(shù)已包含在里邊。節(jié)點(diǎn)第一次接收RREQ，開啟定時器。在定時結(jié)束之前，若節(jié)點(diǎn)接收到RREQ，根據(jù)其報文中的跳數(shù)、剩余能量和RSSI值，采用上面公式計算權(quán)值，若比存儲的值高，則更新存貯的權(quán)值。在定時器到期之后，節(jié)點(diǎn)轉(zhuǎn)發(fā)廣播最高權(quán)值的RREQ包。目的節(jié)點(diǎn)回復(fù)的也是具有最高轉(zhuǎn)發(fā)權(quán)值的RREP。EE-AODV算法偽代碼如表1所示：

4 EE-AODV算法分析

如圖1所示的ZigBee Mesh網(wǎng)絡(luò)中，節(jié)點(diǎn)上方的數(shù)字為其轉(zhuǎn)發(fā)權(quán)值。若節(jié)點(diǎn)S發(fā)送數(shù)據(jù)給節(jié)點(diǎn)D，開啟路由發(fā)現(xiàn)過程，如果采用AODV 算法，在路由發(fā)現(xiàn)過程中廣播的RREQ廣播順序如表1左邊所示。當(dāng)節(jié)點(diǎn)G最先轉(zhuǎn)發(fā)廣播的RREQ包給目的節(jié)點(diǎn)D。這D就會回復(fù)RREP包給節(jié)點(diǎn)G，按照最短路徑原則，此時，選擇的轉(zhuǎn)發(fā)路線為S，C，G，D。若采用文本提出的EE-AODE算法，每個節(jié)點(diǎn)在接收到RREQ以后，啟動定時器，等待更多的RREQ包到來，然后根據(jù)公式（2）計算轉(zhuǎn)發(fā)權(quán)值，從中選擇最優(yōu)的一個節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)。例如步驟4，節(jié)點(diǎn)E之前接收到A，B轉(zhuǎn)發(fā)的RREQ包，但是節(jié)點(diǎn)B的權(quán)值為0.86，比節(jié)點(diǎn)A的權(quán)值高。因此，E將丟棄節(jié)點(diǎn)A廣播的RREQ包，因此，只向B，F(xiàn)，H三個節(jié)點(diǎn)廣播RREQ包。最后目的節(jié)點(diǎn)收到G，F(xiàn)，H三個節(jié)點(diǎn)廣播的RREQ包以后，只回復(fù)權(quán)值最高的節(jié)點(diǎn)F。此時，路由轉(zhuǎn)發(fā)線路為S，B，F(xiàn)，D也是4跳。雖然跳數(shù)不變，但是此路線中節(jié)點(diǎn)的剩余能量和線路狀況都優(yōu)于前者，發(fā)送數(shù)據(jù)過程中丟包率更小，能耗更低。此外，在圖1所示的9個節(jié)點(diǎn)的RREQ廣播過程中，AODV算法廣播的數(shù)據(jù)包有31個，EE-AODV廣播的書數(shù)據(jù)包26個，廣播包數(shù)減少了17%。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，RREQ廣播包就減少的越多，因此，本算法非常適合大規(guī)模的ZigBee Mesh網(wǎng)絡(luò)。

5 算法仿真結(jié)果

將EE-AODV算法和AODV路由算法在NS 2.35環(huán)境下分別進(jìn)行仿真比較。在仿真場景中，在 網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)分別為50、100、150、200、250、300的情況下，各自運(yùn)行50次仿真，將結(jié)果平均值。仿真參數(shù)設(shè)置公式（2）的權(quán)值為α=0.5、β=0.3、γ=0.2。仿真結(jié)果如圖2，圖3。

網(wǎng)絡(luò)能耗對比如圖3所示，本文提出的算法基于跳數(shù)、節(jié)點(diǎn)的剩余能量和鏈路質(zhì)量三者均衡考慮，在轉(zhuǎn)發(fā)節(jié)點(diǎn)選擇過程中，剩余能量、鏈路質(zhì)量好的節(jié)點(diǎn)。隨著節(jié)點(diǎn)數(shù)的增多，EE-AODV算法的能量明顯優(yōu)于AODV算法，因此網(wǎng)絡(luò)存活的時間更長。

網(wǎng)絡(luò)時延的對比如圖2所示。由于EE-AODV算法減少了網(wǎng)絡(luò)中RREQ數(shù)據(jù)包的數(shù)量，抑制了廣播風(fēng)暴的產(chǎn)生，這減少了網(wǎng)絡(luò)中數(shù)據(jù)包的碰撞機(jī)會，使得數(shù)據(jù)包的端對端時延更小。

6 結(jié)論

本文提出的能量有效的AODV算法簡單易用，不需要很多額外的計算和存儲開銷，算法能夠降低網(wǎng)絡(luò)的整體能耗，減小數(shù)據(jù)包的到達(dá)時延，可以提高網(wǎng)絡(luò)的生存周期。本算法在工業(yè)、醫(yī)療以及監(jiān)控領(lǐng)域的大規(guī)模的ZigBee Mesh網(wǎng)絡(luò)中都具有廣泛的應(yīng)用價值。

參考文獻(xiàn)：

[1] Bandyopadhyay D， Sen J. Internet of Things： Applications and Challenges in Technology and Standardization[J]. Wireless Personal Communications， 2011， 58（1）：49-69.

[2] 徐沛成， 胡國榮. 改進(jìn)的ZigBee網(wǎng)絡(luò)路由算法[J]. 計算機(jī)工程與設(shè)計， 2013， 34（9）：3019-3023.

[3] 徐艷， 王茜， 武劍. ZigBee路由協(xié)議優(yōu)化仿真研究[J]. 計算機(jī)仿真， 2013， 30（6）：292-295.

[4] 狄萬昕， 江明. 基于權(quán)重和均衡能量的ZigBee改進(jìn)路由算法[J]. 安徽工程大學(xué)學(xué)報， 2016， 31（2）：78-81.

[5] Kasraoui M， Cabani A， Mouzna J. ZBR-M： A New Zigbee Routing Protocol[J]. International Journal of Computer Science & Applications， 2013， 10（2）： 15-32.

[6] 謝忠明， 何華冰， 李云飛， 等. 一種基于鏈路狀態(tài)感知的 Zigbee 多徑路由算法[J]. 微電子學(xué)與計算機(jī)， 2015（9）： 65-69.