ZigBee路由算法的改進

徐潔 黃虎

【摘要】網(wǎng)絡(luò)層的路由協(xié)議是ZigBee協(xié)議規(guī)范的研究重點之一，因為網(wǎng)絡(luò)節(jié)點中節(jié)點的能量資源、計算能力和帶寬都非常有限，路由算法優(yōu)化與否對整個網(wǎng)絡(luò)的性能有著至關(guān)重要的作用。從控制RREQ分組以及能量均衡的角度出發(fā)，對AODVjr算法提出了改進。通過仿真實驗，將改進的算法與原AODVjr算法進行性能參數(shù)的比較分析，實驗結(jié)果驗證了改進后的算法的有效性。

【關(guān)鍵詞】ZigBee路由算法AODVjr無線傳感器網(wǎng)絡(luò)

一、引言

近年來，作為在低速率的無線傳感器網(wǎng)絡(luò)和控制網(wǎng)絡(luò)中最受矚目的技術(shù)之一，ZigBee以其低成本、低功耗、低速率、高可靠性等特性，廣泛應(yīng)用于工業(yè)、醫(yī)療、軍事、智能家居等需要低功耗、低成本，對數(shù)據(jù)傳輸速率和服務(wù)質(zhì)量要求不高的無線通信應(yīng)用場合[1]。

ZigBee網(wǎng)絡(luò)層（NWK）介于MAC層和應(yīng)用層之間，是由ZigBee聯(lián)盟制定的。ZigBee網(wǎng)絡(luò)層的主要功能就是確保ZigBee的MAC層能正常工作，并且提供適合的服務(wù)接口給應(yīng)用層。網(wǎng)絡(luò)層提供了兩個必要的功能服務(wù)實體用于向應(yīng)用層提供接口：數(shù)據(jù)服務(wù)實體和管理服務(wù)實體[1-2]。

NWK主要功能有：（1）加入和離開網(wǎng)絡(luò)；（2）幀的安全機制管理；（3）根據(jù)路由發(fā)送幀到目的地址；（4）發(fā)現(xiàn)和維護路由；（5）發(fā)現(xiàn)單跳鄰居節(jié)點和維護鄰居節(jié)點信息。

二、ZigBee網(wǎng)絡(luò)層技術(shù)簡介

2.1網(wǎng)絡(luò)拓撲結(jié)構(gòu)及地址分配

ZigBee網(wǎng)絡(luò)中存在三種網(wǎng)絡(luò)節(jié)點，分別為中心協(xié)調(diào)器、路由節(jié)點和終端節(jié)點。協(xié)調(diào)器是整個ZigBee網(wǎng)絡(luò)的中心，是協(xié)調(diào)點，負責(zé)整個網(wǎng)絡(luò)的組織、維護和管理工作，必須由FFD（全功能設(shè)備）構(gòu)成；路由節(jié)點負責(zé)數(shù)據(jù)的傳輸和轉(zhuǎn)發(fā)功能，必須由FFD構(gòu)成，但路由節(jié)點必須由協(xié)調(diào)器控制；終端節(jié)點負責(zé)自身數(shù)據(jù)的發(fā)送并接收其他節(jié)點傳過來的數(shù)據(jù)，可以由FFD或RFD（精簡功能設(shè)備）構(gòu)成。

ZigBee網(wǎng)絡(luò)有星型、網(wǎng)狀型和樹型三種拓撲組織形式。由于樹型網(wǎng)絡(luò)結(jié)合了星型結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)的優(yōu)點，且具有較好的擴展性，所以ZigBee網(wǎng)絡(luò)一般采用簇樹拓撲結(jié)構(gòu)組織節(jié)點。中心協(xié)調(diào)器啟動后就創(chuàng)建一個網(wǎng)絡(luò)，設(shè)置自身網(wǎng)絡(luò)地址為0，路由節(jié)點和終端節(jié)點選擇相應(yīng)的有路由功能的父節(jié)點加入網(wǎng)絡(luò)，形成父子關(guān)系。成功加入網(wǎng)絡(luò)后，該節(jié)點獲得父節(jié)點分配的一個唯一的網(wǎng)絡(luò)地址。

規(guī)定每個父節(jié)點最多可以連接Cm個子節(jié)點，這些子節(jié)點中最多可以有Rm個路由節(jié)點，網(wǎng)絡(luò)的最大深度為Lm，Cskip（d）是網(wǎng)絡(luò)深度為d的父節(jié)點為其子節(jié)點分配的地址之間的偏移量，它的值按公式（1）計算，分配給第k個子路由節(jié)點的地址Ak滿足式（2），分配給第n個子路由器節(jié)點的地址Ak滿足式（3）。其中，Afather代表父節(jié)點的地址。

2.2Cluster-tree路由算法

Cluster-tree算法根據(jù)樹結(jié)構(gòu)轉(zhuǎn)發(fā)分組，如果終端節(jié)點要發(fā)送數(shù)據(jù)包到網(wǎng)絡(luò)中的其他節(jié)點，則直接將該數(shù)據(jù)包轉(zhuǎn)發(fā)給其父節(jié)點，由父節(jié)點進行轉(zhuǎn)發(fā)。

如果一個路由器節(jié)點要轉(zhuǎn)發(fā)數(shù)據(jù)包到網(wǎng)絡(luò)地址為D的目的節(jié)點，已知該路由器節(jié)點的網(wǎng)絡(luò)地址和深度分別為A和d。

首先，該路由器節(jié)點會依據(jù)下述表達式判斷目的節(jié)點是否是其后裔節(jié)點：

RREQ分組。

此外，由于網(wǎng)絡(luò)中某些節(jié)點傳輸數(shù)據(jù)量過大，特別是距離中心協(xié)調(diào)器越近的節(jié)點，從而提前耗盡自身能量，容易造成網(wǎng)絡(luò)分割，影響了整個網(wǎng)絡(luò)的通信，縮短了網(wǎng)絡(luò)的壽命。

針對以上問題，本文從控制RREQ分組以及能量均衡的角度出發(fā)，提出一種改進的算法，有效的限制AODVjr路由發(fā)現(xiàn)過程中的RREQ的廣播，延遲網(wǎng)絡(luò)分割出現(xiàn)的時間，從而提高網(wǎng)絡(luò)的性能。

3.2改進的路由算法M_ZBR

3.2.1冗余RREQ分組的控制

改進的路由算法M_ZBR在路由發(fā)現(xiàn)階段，利用Cluster-tree結(jié)構(gòu)及算法的特點，根據(jù)公式（4）判斷出目的節(jié)點與當(dāng)前節(jié)點的關(guān)系，從而判斷出RREQ分組轉(zhuǎn)發(fā)最佳的大致方向。因此，M_ZBR算法在RREQ分組中增加一個標(biāo)志位flag。當(dāng)目的節(jié)點為當(dāng)前節(jié)點的后裔節(jié)點時，flag=0，即表示當(dāng)前節(jié)點的父節(jié)點不宜轉(zhuǎn)發(fā)該RREQ分組；當(dāng)目的節(jié)點不是當(dāng)前節(jié)點的后裔節(jié)點時，flag=1，即表示當(dāng)前節(jié)點的后裔節(jié)點不宜轉(zhuǎn)發(fā)該RREQ分組。

另外，從樹結(jié)構(gòu)可以看出，若在使用Cluster-tree路由算法時，可能存在的最長路徑應(yīng)是網(wǎng)絡(luò)最大深度的2倍。由此，M_ZBR算法通過設(shè)定最大傳輸跳數(shù)也可以減少部分冗余的RREQ分組，本算法中，當(dāng)跳數(shù)hops>2Lm時，節(jié)點便丟棄該RREQ分組。

3.2.2節(jié)點能量的控制

M_ZBR算法根據(jù)ZigBee路由算法的特點，對ZigBee網(wǎng)絡(luò)中的路由節(jié)點采用了能量控制機制，這對延長網(wǎng)絡(luò)壽命，延遲死亡節(jié)點以及網(wǎng)絡(luò)分割出現(xiàn)的時間都是十分必要的。因此，M_ZBR算法定義了節(jié)點最小路由能量Emin，當(dāng)節(jié)點的能量低于Emin時，路由節(jié)點將不再發(fā)起路由發(fā)現(xiàn)，即不再采用AODVjr路由算法。

在ZigBee網(wǎng)絡(luò)中，越靠近中心協(xié)調(diào)器的節(jié)點參與數(shù)據(jù)傳輸就越頻繁，對整個網(wǎng)絡(luò)的通信來說也就越重要，所以Emin的能量控制應(yīng)與節(jié)點深度成反比，深度越小節(jié)點應(yīng)具有相對較大的最小路由能量，因此，將Emin定義為：

其中，Elimit為節(jié)點正常工作需要的最小能量值，為控制系數(shù)，可以根據(jù)需要人為的控制Emin的大小，d為節(jié)點的深度。

此外，M_ZBR算法依據(jù)節(jié)點最小路由能量的定義，設(shè)置一個節(jié)點能量警戒值Ewarning：

其中，k為大于1的控制系數(shù)。

依據(jù)以上節(jié)點能量閾值的設(shè)置，M_ZBR算法在RREQ分組中增加了能量標(biāo)志位energy_flag，用于統(tǒng)計RREQ分組傳輸過程中統(tǒng)計處于能量警戒區(qū)內(nèi)的節(jié)點個數(shù)。

3.2.3算法流程

（1）當(dāng)RFD節(jié)點要給網(wǎng)絡(luò)中其他節(jié)點發(fā)送數(shù)據(jù)時，直接采用Cluster-tree算法，即將數(shù)據(jù)轉(zhuǎn)發(fā)給其父節(jié)點，由其父節(jié)點轉(zhuǎn)發(fā)。（2）當(dāng)FFD節(jié)點要發(fā)送數(shù)據(jù)到網(wǎng)絡(luò)中其他節(jié)點時，首先查找路由表中有無到目的節(jié)點的路由表項，若有則按路由表轉(zhuǎn)發(fā)數(shù)據(jù)包，若無則啟動路由發(fā)現(xiàn)過程。（3）在路由發(fā)現(xiàn)階段，任意節(jié)點收到RREQ分組時，首先檢測本節(jié)點是不是該RREQ分組的目的節(jié)點，如果不是，則轉(zhuǎn)（4）；若是，則轉(zhuǎn)（9）。（4）判斷節(jié)點自身的剩余能量，如果剩余能量小于節(jié)點最小路由能量Emin則直接丟棄RREQ分組，否則轉(zhuǎn)（5）。（5）查看RREQ分組中的跳數(shù)值，若hops>2Lm，則丟棄RREQ分組，否則轉(zhuǎn)（6）。（6）查看RREQ分組中的標(biāo)志位flag，若flag=0，轉(zhuǎn)（7），若flag=1，則轉(zhuǎn)（8）。（7）flag=0表明本節(jié)點不宜轉(zhuǎn)發(fā)子節(jié)點發(fā)送的分組，需判斷本節(jié)點是否為前一跳的父節(jié)點，若是，則丟棄RREQ分組；若不是，則判斷目的節(jié)點是否為當(dāng)前節(jié)點的后裔節(jié)點，如果是，flag的值繼續(xù)為0，直接轉(zhuǎn)發(fā)分組，若目的節(jié)點是當(dāng)前節(jié)點的后裔節(jié)點，則設(shè)置flag=1。（8）flag=1表明本節(jié)點不宜轉(zhuǎn)發(fā)父節(jié)點發(fā)送的分組，需判斷本節(jié)點是否為前一跳的子節(jié)點，若是，則丟棄該分組；若不是，則需判斷目的節(jié)點是否為當(dāng)前節(jié)點后裔節(jié)點，如果是，則設(shè)置flag=0，若目的節(jié)點不是當(dāng)前節(jié)點的后裔節(jié)點，flag的值繼續(xù)為1，直接轉(zhuǎn)發(fā)分組。（9）當(dāng)目的節(jié)點收到RREQ分組時，判斷自身剩余能量，若小于Emin，直接回復(fù)RREP；否則將收到的分組放入緩存區(qū)，在緩存時間t內(nèi)，比較各RREQ分組的能量標(biāo)志位energy_flag，選擇energy_flag最小的RREQ分組且回復(fù)RREP。

四、仿真結(jié)果分析

為了驗證改進算法的實際效果，通過仿真實驗對比原來的AODVjr算法，分別比較了死亡節(jié)點個數(shù)以及總能量損耗，仿真結(jié)果證明了算法的可行性和有效性。

圖3是原AODVjr算法與改進算法死亡節(jié)點數(shù)的比較，曲線（1）是原AODVjr算法隨數(shù)據(jù)流量增加而變化的死亡節(jié)點數(shù)，曲線（2）是改進后的算法的死亡節(jié)點數(shù)。當(dāng)數(shù)據(jù)流量較小時，節(jié)點能耗就較少，節(jié)點死亡數(shù)相對就比較少。當(dāng)數(shù)據(jù)流量增加時，死亡節(jié)點數(shù)也會增加，改進的算法通過能量標(biāo)志位的判斷，選取能量標(biāo)志位最小的RREQ分組并回復(fù)，明顯比原算法的死亡節(jié)點數(shù)增加的緩慢。

圖4比較了改進算法與原算法的網(wǎng)絡(luò)總能量耗損。曲線（1）是原AODVjr算法隨數(shù)據(jù)流量增加而變化的網(wǎng)絡(luò)總能量耗損，曲線（2）是改進后的算法的網(wǎng)絡(luò)總能量耗損。顯然，改進的AODVjr算法通過控制了RREQ分組減少了網(wǎng)絡(luò)的耗能。

五、結(jié)論

本文主要針對ZigBee的路由協(xié)議進行分析，基于能量均衡對ZigBee現(xiàn)有的路由算法AODVjr提出了改進，通過限制路由發(fā)現(xiàn)過程中的RREQ的廣播，很好的延遲網(wǎng)絡(luò)分割出現(xiàn)的時間，從而提高網(wǎng)絡(luò)的性能。仿真實驗將原算法和改進的算法進行了比較，改進的路由算法有效地減少了總耗能與死亡節(jié)點數(shù)。

參考文獻

[1] ZigBee Alliance. ZigBee Document 053474r13 [S]. December 1， 2006.

[2]朱向慶，王建明. ZigBee協(xié)議網(wǎng)絡(luò)層的研究與實現(xiàn).電子技術(shù)應(yīng)用. 2006.1：129

[3] Hakeres I D， KleinBerodt. AODVjr，AODV simplified[J]. Mobile Computing and Communication Review， 2002， 6（3）：100-101.[4]班艷麗，柴喬林，王芳.改進的ZigBee網(wǎng)絡(luò)路由算法.計算機工程與應(yīng)用，2009，45（5）：95-97

[4]謝川.基于ZigBee的AODVjr算法研究.計算機工程，2011，37（10）：87-89

[6]張擎，劉淑美，柴喬林.能量高效的ZigBee網(wǎng)絡(luò)改進路由策略.計算機工程，2010，36（7）：108-110