ZigBee路由算法的改進

徐潔 黃虎

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

【關鍵詞】ZigBee路由算法AODVjr無線傳感器網絡

一、引言

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

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

NWK主要功能有：（1）加入和離開網絡；（2）幀的安全機制管理；（3）根據路由發送幀到目的地址；（4）發現和維護路由；（5）發現單跳鄰居節點和維護鄰居節點信息。

二、ZigBee網絡層技術簡介

2.1網絡拓撲結構及地址分配

ZigBee網絡中存在三種網絡節點，分別為中心協調器、路由節點和終端節點。協調器是整個ZigBee網絡的中心，是協調點，負責整個網絡的組織、維護和管理工作，必須由FFD（全功能設備）構成；路由節點負責數據的傳輸和轉發功能，必須由FFD構成，但路由節點必須由協調器控制；終端節點負責自身數據的發送并接收其他節點傳過來的數據，可以由FFD或RFD（精簡功能設備）構成。

ZigBee網絡有星型、網狀型和樹型三種拓撲組織形式。由于樹型網絡結合了星型結構和網狀結構的優點，且具有較好的擴展性，所以ZigBee網絡一般采用簇樹拓撲結構組織節點。中心協調器啟動后就創建一個網絡，設置自身網絡地址為0，路由節點和終端節點選擇相應的有路由功能的父節點加入網絡，形成父子關系。成功加入網絡后，該節點獲得父節點分配的一個唯一的網絡地址。

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

2.2Cluster-tree路由算法

Cluster-tree算法根據樹結構轉發分組，如果終端節點要發送數據包到網絡中的其他節點，則直接將該數據包轉發給其父節點，由父節點進行轉發。

如果一個路由器節點要轉發數據包到網絡地址為D的目的節點，已知該路由器節點的網絡地址和深度分別為A和d。

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

RREQ分組。

此外，由于網絡中某些節點傳輸數據量過大，特別是距離中心協調器越近的節點，從而提前耗盡自身能量，容易造成網絡分割，影響了整個網絡的通信，縮短了網絡的壽命。

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

3.2改進的路由算法M_ZBR

3.2.1冗余RREQ分組的控制

改進的路由算法M_ZBR在路由發現階段，利用Cluster-tree結構及算法的特點，根據公式（4）判斷出目的節點與當前節點的關系，從而判斷出RREQ分組轉發最佳的大致方向。因此，M_ZBR算法在RREQ分組中增加一個標志位flag。當目的節點為當前節點的后裔節點時，flag=0，即表示當前節點的父節點不宜轉發該RREQ分組；當目的節點不是當前節點的后裔節點時，flag=1，即表示當前節點的后裔節點不宜轉發該RREQ分組。

另外，從樹結構可以看出，若在使用Cluster-tree路由算法時，可能存在的最長路徑應是網絡最大深度的2倍。由此，M_ZBR算法通過設定最大傳輸跳數也可以減少部分冗余的RREQ分組，本算法中，當跳數hops>2Lm時，節點便丟棄該RREQ分組。

3.2.2節點能量的控制

M_ZBR算法根據ZigBee路由算法的特點，對ZigBee網絡中的路由節點采用了能量控制機制，這對延長網絡壽命，延遲死亡節點以及網絡分割出現的時間都是十分必要的。因此，M_ZBR算法定義了節點最小路由能量Emin，當節點的能量低于Emin時，路由節點將不再發起路由發現，即不再采用AODVjr路由算法。

在ZigBee網絡中，越靠近中心協調器的節點參與數據傳輸就越頻繁，對整個網絡的通信來說也就越重要，所以Emin的能量控制應與節點深度成反比，深度越小節點應具有相對較大的最小路由能量，因此，將Emin定義為：

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

此外，M_ZBR算法依據節點最小路由能量的定義，設置一個節點能量警戒值Ewarning：

其中，k為大于1的控制系數。

依據以上節點能量閾值的設置，M_ZBR算法在RREQ分組中增加了能量標志位energy_flag，用于統計RREQ分組傳輸過程中統計處于能量警戒區內的節點個數。

3.2.3算法流程

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

四、仿真結果分析

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

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

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

五、結論

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

參考文獻

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

[2]朱向慶，王建明. ZigBee協議網絡層的研究與實現.電子技術應用. 2006.1：129

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

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

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