徐沛成，胡國榮

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

0 引 言

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

1 ZigBee網(wǎng)絡概述

1.1 網(wǎng)絡結構

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

1.2 地址分配機制

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

2 ZigBee網(wǎng)絡的路由算法

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

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

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

2.2 AODVjr路由算法

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

3 路由算法問題分析

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

圖1 區(qū)域間相鄰節(jié)點路由分析

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

4 ZigBee路由算法的改進

4.1 Cluster－tree算法的改進

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

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

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

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

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

若目的地址D是Ac的子節(jié)點，將數(shù)據(jù)幀轉發(fā)給Ac，若目的地址D不是Ac的子節(jié)點，轉向 （3）。

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

具體流程圖如圖2所示。

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

4.2 ADOVjr路由算法的改進

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

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

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

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

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

（5）判斷目的節(jié)點是否是當前節(jié)點的子節(jié)點，若是，繼續(xù)轉發(fā)，若不是，修改flag位為1，轉向 （8）。

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

（7）判斷目的節(jié)點是否是當前節(jié)點的子節(jié)點，若不是，繼續(xù)轉發(fā)，若是，修改flag位為0，轉向 （8）。

（8）轉發(fā)RREQ，當?shù)竭_目的節(jié)點時，目的節(jié)點需回復RREP。

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

圖3 中間節(jié)點處理RREQ的過程

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

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

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

5 仿真與結果分析

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

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

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

6 結束語

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

［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的加權質心定位算法的仿真與實現(xiàn) ［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技術網(wǎng)絡層的路由算法分析 ［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］.電腦開發(fā)與應用，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能量均衡協(xié)議研究 ［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］.合肥工業(yè)大學學報 （自然科學版），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網(wǎng)絡改進路由策略 ［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網(wǎng)絡基礎路由分析與改進 ［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網(wǎng)絡路由算法 ［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網(wǎng)絡中Cluster—Tree路由算法優(yōu)化 ［J］.數(shù)字技術與應用，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路由算法優(yōu)化 ［J］.計算機工程與設計，2011，32（2）：397－400.］