改進的ZigBee網絡路由算法

徐沛成，胡國榮

（中國科學院微電子研究所，北京100029）

0 引 言

ZigBee通信技術的MAC層和PHY層基于IEEE802.15.4標準協議，ZigBee聯盟在此基礎上定義了ZigBee的NWK層和APL層，使其構成一套完整的標準協議。ZigBee技術在傳感器網絡中的應用已日益受到重視，低成本、低功耗、低數據傳輸速率、低復雜度等優點滿足了小型、低成本的固定、便攜或移動設備無線聯網的要求［1］。ZigBee協議的 NWK層［2］負責建立和管理網絡，其核心問題是路由算法，路由算法直接關系到網絡中節點轉發的跳數、網絡的時間延遲以及網絡能量的消耗［3］。

1 ZigBee網絡概述

1.1 網絡結構

ZigBee網絡層主要支持3種網絡拓撲結構：星形（star），網狀 （mesh）以及屬性 （cluster－tree）結構［4］。根據IEEE802.15.4標準協議可以將設備分成2種類型：FFD和RFD，其中FFD是指全功能節點設備，能夠組織建立網絡，也有能力管理其它節點的加入與離開網絡，而RFD是指精簡功能節點設備，不能組建網絡，只能選擇已有的網絡加入，也沒有管理其它節點的功能。ZigBee網絡中的協調器 （coordinator）和路由器 （router，可分 為 RN＋、RN－）必須都是FFD，RN＋具有路由功能，RN－沒有路由功能，而終端節點設備 （end device，ED）則可以是RFD也可以是 FFD［5］。

1.2 地址分配機制

ZigBee網絡地址分配采用分布式地址分配機制［6］，即為每個潛在的父節點提供有限的地址塊，再由父節點把地址分配給子節點。ZigBee網絡中的協調器決定網絡中允許的最大設備數，參數Rm決定父節點設備的子節點中的路由器的數目，其余設備為終端節點，不具有路由能力。每個設備都有相關深度，用Lm表示，指示其與協調器傳輸數據幀所需要的最少跳數。每個父節點可以擁有的最大子節點數目用Cm表示。Zigbee網絡中的協調器的Lm為0，地址為0X0000，其子節點的Lm為1，協調器決定網絡的最大深度。對于深度為d，地址為Af的父節點為它的有路由器能力的子節點分配的網絡地址塊如式 （1）。若設備的Cskip（d）為0，則表示該設備沒有路由能力接受子節點，只能作為終端節點，若大于0，則表示該設備可以接受子節點設備，并根據其路由能力給子節點分配地址。父節點為它的第一個有路由能力的子節點比自己大1，為每個有路由能力的子節點設備分配的地址用Cskip（d）分離，如式 （2）所示，為終端節點設備分配地址如式 （3）所示

2 ZigBee網絡的路由算法

2.1 Cluster－tree樹型路由算法［7－8］

Cluster－tree算法采用樹型分層路由，地址為Ar、深度為d的路由節點收到目的地址為D的幀，若目的地址為自己則直接接收，否則用式 （4）判斷目的地址是否是其子節點，若是子節點，則轉發給合適的子節點，若不是，則轉發給自己的父節點

Cluster－tree算法簡單，幀總是沿著樹型路徑轉發，由于沒有路由功能，不需要存儲路由表，節省了存儲空間，節點造價低。但是該算法屬于靜態路由，不適合移動場合，并且由于幀的轉發總是沿著樹型路徑，導致越靠近協調器的節點的轉發任務越重，消耗也越大，而且容易造成路徑擁堵。

2.2 AODVjr路由算法

AODVjr協議［9－11］是 AODV協議的簡化，AODVjr協議考慮到了無線節點的有限移動性，并且最大限度的降低了節點能耗。在AODVjr協議中取消了AODV協議的HELLO消息、路由錯誤信息、問詢序列號等措施，但保留了按需路由的特性。由于AODVjr協議的能耗遠遠小于AODV協議，所以在無線傳感網絡中越來越多地使用AODVjr協議。

3 路由算法問題分析

如圖1所示的樹型網絡可以分為3個區域，分別標記為區域1，區域2，區域3。根據Cluster－tree算法，幀的傳輸總是沿著樹型路徑，因此若區域3中的E節點想要發送幀給區域1中的 D節點，其發送路徑為 E－F－G－H－A－C－D，需要6跳來完成，但是從圖中可以看出，E節點與D節點距離很近，E節點完全可以直接把幀發送給D節點，即ED，只需1跳。所以這種按樹型路徑轉發的路由算法雖然簡單，但是不僅增加了轉發次數也造成了時間上的延遲以及能量消耗的浪費［12］。

圖1 區域間相鄰節點路由分析

AODVjr路由算法比AODV更簡單有效，但是其發送的RREQ容易引起廣播風暴，從而增加網絡能量消耗。如圖1所示，若區域3中的節點G想要發送數據給區域2中的節點B，它們之間有3跳的距離，但是在使用AODVjr路由算法尋找路徑時，RREQ在大于3跳時仍會被轉發，造成能量的不必要消耗，并且RREQ沒有方向選擇，容易形成廣播風暴。

4 ZigBee路由算法的改進

4.1 Cluster－tree算法的改進

改進算法為Cluster－tree算法加入鄰居表，鄰居表是節點周圍一跳范圍內的節點列表，是節點加入網絡的時候在通過發送廣播幀得到的回復消息的基礎上建立的，能夠一跳把消息發送到周圍目的節點。在鄰居表中可以為每個節點建立一個記錄條目，記錄包括節點在網絡中的地址，節點的設備類型等信息，當周圍節點信息發生變化時對鄰居表進行更新。

改進后的Cluster－tree路由算法：

（1）子節點查找。當節點收到一個數據幀時，先檢查目的地址D是否是自己，若是，則直接接收，若不是，則利用式 （4）判斷該目的地址是否是自己的子節點，若是，則轉發給相應的子節點，若不是，轉向 （2）。

（2）鄰居節點查找。若目的地址D存在于鄰居表中，則直接發送給相應的鄰居節點，若不在，則使用式 （5）選擇鄰居節點Ak中到達D最近的節點Ac為

其中Ak，k＝0，1…m為鄰居表中鄰居節點的地址。若Ac節點為RFD則轉向 （3），若為FFD則使用式 （4）進行判斷D是否是Ac子節點，即

若目的地址D是Ac的子節點，將數據幀轉發給Ac，若目的地址D不是Ac的子節點，轉向 （3）。

（3）父節點查找。若目的地址D不是Ac的子節點，計算出Ac的父節點Ar，判斷是否是D，若不是，則根據式（4）判斷是否是Ar的子節點。若是其子節點則將數據幀轉發給Ac，否則將數據發給自己的父節點。

具體流程圖如圖2所示。

圖2 改進的Cluster－tree算法流程

4.2 ADOVjr路由算法的改進

為了對RREQ的發送方向進行選擇，可以在RREQ的分組中增加標志位flag，若flag為0則表示子節點可以轉發而父節點不必轉發，若flag為1則表示父節點可以轉發而子節點不必轉發，從而對RREQ的發送方向進行選擇，具體過程如下：

（1）當網絡中的一個節點收到RREQ時，先判斷自己是否是其目的地址，若是，則直接回復，若不是，則轉向（2）。

（2）Ls為源節點的深度，若當前跳數大于Lm＋Ls時，應丟棄該RREQ，否則轉向 （3）。

（3）判斷flag的值進行方向選擇，若flag＝0，則轉向（4），若flag＝1，則轉向 （6）。

（4）判斷當前節點是否是前一跳的父節點，若是，則丟棄該RREQ，若不是，則轉向 （5）。

（5）判斷目的節點是否是當前節點的子節點，若是，繼續轉發，若不是，修改flag位為1，轉向 （8）。

（6）判斷當前節點是否是前一跳的子節點，若是，丟棄該RREQ，若不是，則轉向 （7）。

（7）判斷目的節點是否是當前節點的子節點，若不是，繼續轉發，若是，修改flag位為0，轉向 （8）。

（8）轉發RREQ，當到達目的節點時，目的節點需回復RREP。

中間節點處理RREQ的過程如圖3所示。

圖3 中間節點處理RREQ的過程

4.3 兩種路由算法的結合與改進

ZigBee網絡中的節點可以分為：Coordinator、RN＋、RN－、RFD［13］，其中前三者都是全功能節點，Coordinator、RN＋能夠建立和管理網絡，具有路由功能，使用AODVjr路由算法，RN－節點沒有路由功能，使用Cluster－tree路由算法沿樹型路徑轉發數據，RFD只能作為終端節點。

當RN－節點收到數據幀時使用改進的Cluster－tree路由算法進行轉發，減少數據幀在網絡中的轉發跳數以及網絡時間延遲。當Coordinator和RN＋節點收到數據幀時，因為具有路由能力，所以優先查找路由表條目是否包含目的節點地址，若有，則直接發送，若不包括，則不立即使用AODVjr路由算法而是先使用改進的Cluster－tree算法，若成功，則轉發數據幀，若失敗則啟用改進的AODVjr路由算法。這樣可以充分利用樹型網絡結構特點，減少時間上的延遲以及路由發現過程中能量消耗。

5 仿真與結果分析

為了模擬真實環境，采用NS2仿真軟件，通過修改代碼與仿真參數觀察仿真結果。實驗采用獨立多次仿真，然后取其平均值，以減小誤差。實驗的網絡結構為協調器位于中心位置，網絡中的其它節點隨機分布在協調器周圍。其它參數如下：網絡結構大?。?50m×150m，有效數據源：CBR，數據幀傳輸距離：10m，實驗中的數據幀大小為80Byte，另外Lm，Rm，Cm分別為6，4，5。

在圖4中對原Cluster－Tree算法和改進的Cluster－Tree算法在網絡中運行所需要的平均跳數進行了對比，從圖中可以看出，隨著選取的節點數目不斷增加，兩種算法所需要的跳數都在增加，但是改進的Cluster－Tree算法所需要的跳數要少于原Cluster－Tree算法，并且隨著節點數的增加，跳數減少的更加明顯。在圖5中對原Cluster－Tree算法和改進的Cluster－Tree算法在網絡中的平均時間延遲進行了對比，從圖中可以看出，隨著選取的節點數不斷增加，兩種算法的時間延遲都在增加，但是改進后的Cluster－Tree算法的延遲要小于原Cluster－Tree算法，并且這種趨勢也隨著節點數的增加變的增加明顯。綜合平均跳數與平均時間延遲來看，在這兩種對比中改進的Cluster－Tree算法都優于原Cluster－Tree算法，其所需要的跳數更少，時間延遲更小，從而能量消耗也會減少，提高了網絡的整體性能。

在圖6中對AODVjr路由算法，AODVjr＋Cluster＋Tree算法和改進的AODVjr＋改進的Cluster＋Tree算法在網絡中的平均跳數進行了對比，從圖中可以看出AODVjr路由算法所需要的平均跳數最多，因為其在路由表沒有相關條目時需要進行路由發現從而建立發送路徑，而采用AODVjr＋Cluster－Tree算法的平均跳數要小于AODVjr算法，因為鄰居表的存在，使得其可以很快的做出轉發，而不必進行路由發現，改進的AODVjr算法＋改進的Cluster＋Tree算法因為能夠有效的利用鄰居表和選擇RREQ的轉發方向，所以平均跳數最少。在圖7中對AODVjr路由算法，AODVjr＋Cluster＋Tree算法和改進的AODVjr＋改進的Cluster＋Tree算法在網絡中的平均時間延遲進行了對比，時間延遲和轉發跳數有一定的關系，AODVjr算法所需要的時間最多，AODVjr＋Cluster－Tree算法次之，而改進的AODVjr算法＋改進的Cluster＋Tree算法所需時間最少。綜合平均跳數與平均時間延遲來看，改進的AODVjr算法＋改進的Cluster＋Tree算法最優，也即該算法在網絡中的路由效率最高。

6 結束語

本文對ZigBee網絡的兩種現有算法Cluster＋Tree算法和AODVjr算法都進行了改進優化，并對這兩種算法進行了綜合利用，提出了改進算法。在原Cluster＋Tree算法中加入鄰居表，建立一跳范圍內的鏈路信息，在原AODVjr算法中加入標志位flag控制RREQ的轉發方向。對兩種路由算法綜合利用后的改進路由策略為RN－節點直接使用改進后的Cluster＋Tree算法，而RN＋節點則先使用改進后的Cluster＋Tree算法，若失敗在啟用改進后的AODVjr算法。通過仿真實驗結果可以看出，這種改進的算法在轉發跳數和網絡時間延遲等方面都要優于原來的算法，能夠有效提高ZigBee網絡的總體性能。

［1］GAO Lipeng，ZHU Meidong，YANG Dan.Simulation and implement of weighted centroid localization algorithm based on ZigBee ［J］.Chinese Journal of Sensors and Actuators，2010，23 （1）149－150 （in Chinese）. ［郜麗鵬，朱梅冬，楊丹，基于ZigBee的加權質心定位算法的仿真與實現 ［J］.傳感技術學報，2010，23 （1）149－150.］

［2］LIU Lijun，TONG Lili，ZigBee network layer routing algorithm analysis ［J］.Compu－ter and Information Technology，2008 （1）：70－72 （in Chinese）.［劉麗鈞，童麗麗.ZigBee技術網絡層的路由算法分析 ［J］.計算機與信息技術，2008（1）：70－72.］

［3］GUO Ruixing，WANG Qingsheng，Research and Improvement on the Routing Algorithm in ZigBee Networks ［J］.Computer Development ＆ Applications，2011，24 （5）32－33 （in Chinese）. ［郭瑞星，王慶生.ZigBee路由算法的研究與改進［J］.電腦開發與應用，2011，24 （5）32－33.］

［4］WANG Chen，CHAI Qiaolin，WANG Fang.Energy balanced protocol research based on tree structure ZigBee ［J］.Computer Engineering and Design，2009，30 （15）：3534－3586 （in Chinese）.［王琛，柴喬林，王芳.基于樹形結構的ZigBee能量均衡協議研究 ［J］.計算機工程與設計，2009，30（15）：3534－3586.］

［5］XIE Chuan.Research of AODVjr algorithm based on ZigBee［J］.Computer Engineering，2011，37 （10）87－88 （in Chinese）.［謝川.基于ZigBee的AODVjr算法研究 ［J］.計算機工程，2011，37 （10）87－88.］

［6］ZigBee.Alliance.ZigBee.specification.2008 ［DB／OL］.［2013－01－10］.http：／／www.zigbee.org.

［7］QI Jianchao，WEI Zhen.Animproved tree－based routing algorithm for ZigBee ［J］.Journal of Hefei University of Technology，2010，33 （4）：530－531 （in Chinese）. ［戚劍超，魏臻.ZigBee樹型路由算法的改進 ［J］.合肥工業大學學報 （自然科學版），2010，33 （4）：530－531.］

［8］Dilum Bandara H M N，AnuraP Jayas－umana.An enhanced top－down cluster and cluster tree formation algorithm for wireless sensor networks ［C］／／International Conference on InduS－trial and Information Systems，2007：565－570.

［9］ZHAGN Qing，LIU Shumei，CHAI Qiaolin.Energy efficient improved routing strategy for ZigBee network ［J］.Computer Engineering，2010，36 （7）：108－109 （in Chinese）. ［張擎，劉淑美，柴喬林.能量高效的ZigBee網絡改進路由策略 ［J］.計算機工程，2010，36 （7）：108－109.］

［10］ZOU Xiaowu，XU Du，JIANG Yongping，et al.Analysis and improvement for basic Zigbee wireless networks route［J］.Computer Knowledge and Technology，2009，5 （33）：9242－9243 （in Chinese）.［鄒小武，徐杜，蔣永平，等.Zigbee網絡基礎路由分析與改進 ［J］.電腦知識與技術，2009，5 （33）：9242－9243.］

［11］WANG Fang，CHAI Qiaolin，BAN Yanli.Improved routing algorithm for ZigBee mesh networks ［J］.Computer Applications，2008，28 （11）：112－113 （in Chinese）. ［王芳，柴喬林，班艷麗.一種改進的ZigBee mesh網絡路由算法 ［J］.計算機應用，2008，28 （11）：2788－2789.］

［12］PENG Sheqiang，WANG Wei.Cluster－tree routing algorithm optimization ZigBee network ［J］.Digital Technology and Application，2012 （4）：112－113 （in Chinese）. ［彭設強，王為.ZigBee網絡中Cluster—Tree路由算法優化 ［J］.數字技術與應用，2012 （4）：112－113.］

［13］LI Yudong，HUANG Hongguang，XIANG Xixi.Improved ZigBee routing algorithm based on energy balance ［J］.Computer Engineering and Design，2011，32 （2）：397－400 （in Chinese）.［李予東，黃宏光，向西西.基于能量均衡的Zig－Bee路由算法優化 ［J］.計算機工程與設計，2011，32（2）：397－400.］