Zigbee網絡基礎路由分析與改進

摘要:Zigbee是一種基于IEEE 802.15.4協議標準的新興的短距離無線通信技術。該文詳細介紹了兩種適用于ZigBee網絡的近距離基礎路由協議，分析這兩種路由算法并提出相應改進方案或策略。最后提出了一種基于AODVjr的簇樹網絡路由策略，平衡考慮了報文的端到端延遲和網絡生存時間，提高了ZigBee網絡的性能。

關鍵詞:路由算法;Cluster-Tree;AODVjr;分簇

中圖分類號:TP393文獻標識碼:A文章編號:1009-3044(2009)33-9242-04

Analysis and Improvement for Basic Zigbee Wireless Networks Route

ZOU Xiao-wu，XU Du，JIANG Yong-ping，ZHOU Yan-can

(School of Information，Guangdong University of Technology，Guangzhou 510009，China)

Abstract: Zigbee is an emerging shortrange wireless network technology， based on IEEE 802.15.4 protocols. In this paper， two short-distance route protocols for Zigbee networks are introduced and analysed in details， the corresponding improved blue print and strategy are proposed.At last， suggest an improved Cluster-Tree routing algorithm based on AODVjr， which equipoise the latency of transport and life span of networks， and raised the efficiency of ZigBee networks.

Key words: routing algorithm; cluster-tree; AODVjr

ZigBee是一種新興的近距離、低復雜度、低功耗、低數據速率、低成本的無線網絡技術，建立在IEEE 802.15.4標準的基礎上，在數千個微小的傳感器之間相互協調實現通信。但是在ZigBee傳感器網絡中，由于網絡內節點資源有限，數據包的傳送通常需要通過多跳通信方式到達目的端。因此，數據包的傳送延遲和節點的剩余能量成為了路由設計的重點，如何根據不同的應用需求設計高效率的路由選擇算法是實際應用中網絡層設計的一個主要任務。

1 ZigBee網絡的拓撲結構

IEEE802.15.4/ZigBee網絡層支持如圖1所示的三種拓撲結構:星型、簇樹型和網狀型拓撲結構。在星型網絡中，整個網絡由一個稱為zigBee協調器的設備來控制。zigBee協調器負責發起和維護網絡正常工作，保持同網絡的終端設備來通信。在網狀型和簇樹型拓撲結構中，zigBee協調器負責啟動網絡以及選擇關鍵的網絡參數，也可以使用zigBee路由其來擴展網絡結構。在簇樹型網絡中，路由其采用分級路由策略來傳送控制信息和數據。樹型網絡可以采用基于信標的方式進行通信。網狀型(Mesh)網絡中，設備之間使用完全對等的通信方式。Mesh網一般是由若干個FFD連接在一起組成骨干網，每個節點都可以與它的無線通信范圍內的其它節點通信，但它們中也有一個會被推薦為ZigBee協調點。

2 兩種常見的ZigBee網絡路由算法

2.1 Cluster-Tree算法簡介

Cluster-Tree(簇樹)算法[2]中，節點根據分組目的節點的網絡地址計算分組的下一跳.對于地址為A深度為d的ZigBee路由節點，如果下述表達式(1)成立，則具有地址為D的目的設備為子設備，其中Cskip由網絡地址分配機制確定。

A

如果確定分組的目的節點是接收節點的一個后代，節點就將分組發送給它的一個子節點，此時如果滿足:

D>A+Rm﹡Cskip (d)(2)

則說明目的節點是它的一個終端子節點，這時下一跳節點地址N為:

N=D (3)

否則，N=A+1+{[D-(A-1)]/ Cskip (d)}﹡Cskip (d)(4)

如果目的節點不是接收節點的一個后代，則將分組發送給它的父節點。

2.2AODVjr算法簡介

AODVjr是一種簡化版本的AODV(Ad hoc按需距離矢量路由協議)，主要是考慮到ZigBee無線傳感器網絡的電池能量有限性、應用方便性等因素，而簡化了AODV的一些特點。在MESH結構的ZigBee網絡中一般使用AODVjr算法來進行路由發現和數據傳輸。AODVjr舍棄了AODV中的目標序列號和跳數，只能是目標節點來對最先到達的RREQ信號做出響應，而不是像AODV中已知到目的節點路徑的中間節點也可以做出響應。這種策略也被稱作點到點策略。同時AODVjr取消了HELLO信息的發送，由Destination定期向Source發送KEEP_ALIVE連接信息來維持路由。當Source在一段時間內沒有收到Destination發來的KEEP_ALIVE信號時，它認為此條路徑失效，必要時重新進行路由發現。此外，AODV中的RERR信號以及前驅列表在AODVjr算法中也無需考慮。這使得ZigBee的路由發現簡單且實用、且更加節能高效。圖2是使用AODVjr算法時尋找路由的方式，可看到RREQ廣播和RREP回復的過程。R5是中心協調器，當終端設備D6要發送數據給R2，D6先把數據發送給具有路由功能的父節點R7，R7查找自身路由表，沒有發現到一條到R2的有效路徑，于是發起一個路由發現過程，構建并同時洪泛RREQ包。R2選擇最先到達的RREQ包的傳送路徑R7—R6—R2，并返回RREP信息，R7收到R2發來的RREP信號，路由路徑建立，R7就會按這條路徑來發送緩存的數據。在此期間，R2定期發送KEEP—ALIVE包，用以維護路由信息。

3 算法分析及改進

基于ZigBee協議堆棧的應用通常采用默認路由策略，NWK層一般默認采用AODVjr算法，而Cluster-Tree(簇樹)路由算法一般在對時延要求較高的場合才會給予考慮。從參考文獻[3]的模擬中可以看出，在大多數情況下采用AODVjr算法的延遲明顯長于簇樹路由算法，因為AODVjr的路由發現過程產生了額外的延遲。盡管簇樹路由算法在縮短時延方面有很好的效果，但它是一個靜態的算法而AODVjr中能耗均勻的分布于網絡，而能耗在WSN中是一個非常關鍵的問題，所以將AODVjr作為默認路由是合理的。然而，為了網絡能更加實用、高效，針對能耗和時延對原有算法作一些改進是必須做的。

3.1 一種改進的Cluster-Tree算法

為使簇樹路由算法在縮短時延方面有更好的效果，應該考慮鄰居節點[4]和選擇下一跳節點是到目的節點的最短路徑的節點。這是基于Greedy算法的想法，因此沒有必要去證實最后采用了一條最短的路徑。改進的算法主要包括以下三步:

1) 如果目的節點在它的鄰居列表中，直接傳輸到對應的節點。

2) 如果目的節點是它的子節點，選擇自身的子節點作為下一跳。

3) 如果不屬于以上兩種情況之一，那么選擇除其子節點外鄰居列表中到達目的節點最少跳數的節點作為下一跳。算法如下:

Algorithm 1: 計算最少跳數節點

Input: source node S，destination node D

Output: minHopNode-the minimum hop node address

Begin:

maxComDepth-record the max common ancestor depth，set 0 at first

minHopNode-record the node of maxComDepth，set S’s parent at first

foreach node N in S’s neighbor table

if N is the children node of S continue

for i=1 to Lm

if N and D do not have the common ancestor node at depth i

then i = i-1 break;

end for

if i > maxComDepth then

maxComDepth = i;minHopNode = N

end foreach

End

3.2 改進AODVjr算法的基本策略

對AODVjr算法進行改進時，一般從能量角度考慮，根據節點的剩余能量狀態分為充足、不充足及即將耗盡3種等級。路由發現過程中，中間節點在收到路由RREQ報文后，根據節點自身能量等級決定下一步動作。算法如下:①收到RREQ報文后，判斷自身能量狀態:能量在第1等級時，直接轉②;能量在第2等級時，等待一段時間后轉②;能量在第3等級時，轉③。②判斷自身是否為目的節點，若不是，轉發RREQ報文;若是，回復RREP報文。③不對RREQ進行響應。

當出現源節點在一段時間后仍沒發現有效路由，則重新進行路由嘗試，此時路由節點不再進行能量區分以保證路由正常建立。通過上述改進，每個節點根據自身的狀況有選擇地轉發RREQ報文，能阻止在能量不足的節點上建立路由，有效地減少了RREQ報文的廣播風暴，可以在總體上提高網絡性能。

4 一種基于AODVjr的簇樹網絡路由策略

通過對上述改進后的算法和改進的策略分析可知:改進的Cluster-Tree結構的優點在于可以增加網絡的覆蓋范圍，在縮短時延和數據聚合方面有較為明顯的優勢[5]。但其缺點也很明顯，這種非自適應算法決定了不可能最大限度延長網絡的生存時間。而AODVjr算法具有靈活的路由查找功能，其按需路由提高了協議效率，具有快速適應動態鏈路環境、較低的處理和內存開銷以及支持多播的特點且具有自主學習和發現拓撲的能力，但是因需要維護路由表而有初始延遲且容易產生RREQ廣播風暴而耗費能量。為此，提出了融合了上述兩種改進算法優點的一種基于AODVjr的簇樹網絡路由策略，即優化AODVjr+Cluster。

4.1 簇的建立過程

協議在設計的之初將整個ZigBee網絡分成多個簇[6]，簇的建立過程可分為四個階段:簇首節點的選擇、簇首節點的廣播、簇的建立和調度機制的生成。每個簇又由多個節點組成，這些節點按功能又分成3種類型的節點:簇首，簇成員和網關節點。簇首作為簇的中心，負責路由過程建立后向簇內成員廣播和簇結構的建立，收集簇成員的數據并在融合處理后發送給網關節點。簇的劃分是依據下面的規則的基礎建立的:

1) 中心節點是一個簇首;

2) 簇首必須是有路由能力的節點，且網絡深度為偶數的節點;

3) 深度為奇數的節點則屬于它的父節點的簇;

4) 終端節點的簇屬于它的父節點的簇。

簇首建立過程如圖3所示。

簇的建立過程是根據節點分布的密集度來劃分。簇首的短地址作為該簇的標簽。簇的劃分是按隔一個深度做一次劃分，因為中心節點的深度為0且是一個簇首，所以在深度為偶數的路由節點里面選擇一個簇首，簇首的短地址就是這個簇的所有成員的標識。除以中心節點為簇首形成一個簇外，其它的簇首則是根據節點的分布情況來選擇的，基于AODVjr的分簇路由根據判斷信號強度來確定網絡中節點的密集程度。在簇形成的開始階段，判斷網絡深度，網絡深度為偶數的節點向外廣播RREQ，收到RREQ的節點向源節點發送一個確認信息，則發送RREQ的源節點把收到的確認信息按照所規定的最小信號強度來取舍，若大于這個值，則這個節點加入鄰居表里，最后根據比較鄰居表里周圍節點的數目選定節點數最多的節點作為簇首，這個節點的短地址作為這個簇的標簽，節點一旦被選定為簇首節點，則向它的周圍節點發送簇首廣播報文，收到廣播報文的節點在自己不是簇首的情況下發送簇加入報文，簇首發送加入響應后，即加入到該簇。簇成員節點維護一個簇首節點列表，簇首節點維護一個網絡的所有簇成員列表。

4.2 路由過程的建立與維護

AODVjr+Cluster的路由請求過程類似于Z_AODV的方式。源節點有數據要發送給目標節點時，首先在自己的路由表中查尋到目標節點的路徑，若路由存在且有效，則直接發送數據;反之，若路由不存在或路由存在但已標明為無效時，源節點則開啟一個泛洪路由發現過程。新路由建立伊始，源節點創建一個路由請求包RREQ，并向其周圍節點廣播。如果鄰居節點收到RREQ，則根據計算簇標簽的方法計算出目的節點的簇標簽，并在它的鄰居表中增加這個簇標簽的一個路由接入點，路由查找表中也增加一個目的節點的網絡地址的路由接入點;在中間節點收到RREQ時，則與它的路由搜索表中的比較路由成本，如果這個路由成本比較低的話，則更新路由搜索表。之后繼續廣播，直至到達目的節點為止。

目標節點收到路由請求后，不再廣播路由請求，先建立反向路徑，并生成一個RREP，RREP中含有最新的各類信息，沿反向路徑送至源節點。源節點和中間節點在收到RREP后建立到目標節點的路由，更新系列號等相關信息，源節點建立路由并開始傳送數據。這個路由過程一旦建立完畢，源節點向它的簇首發送一個攜帶有路由信息的路由確認包RNOT(Rote Notify)，簇首在收到這個確認包后再廣播一個路由更新包RUPT(Route Update)，簇成員收到這個信息后，則共享節點新建立的路由信息。

數據傳送階段，簇成員通常只與其簇首通信，數據的轉發由簇首負責。基于AODVjr的分簇算法既保證了原有覆蓋范圍內的數據通信，又在很大程度上節省了能量和縮短了時延。分簇思想具有很明顯優點，簇頭可以負擔數據融合的任務，減少了數據通信量;其拓撲結構有利于分布式算法的應用，適合大規模部署的網絡。由于大部分簇內節點在相當長的時間內關閉通信模塊，不參加數據轉發過程，因此可以延長整個網絡的生存時間。

4.3 仿真與結果分析

用NS-2仿真軟件[7]進行模擬實驗將改進的AODVjr+Cluster算法和改進的AOOVjr進行比較，重點是對比兩者在數據傳送過程中報文的發送成功率及分組端到端的平均延時。仿真結果證明了前者的高效性。在相同的仿真環境下分別運行AODVjr和優化的AODVjr+Cluster的仿真程序并比較仿真結果，圖4是報文發送成功率比較圖，從圖中可以看出優化的AODVjr+Cluster協議的數據報文發送成功率要明顯高于原來的AODVjr協議。

圖5是網絡中兩種協議在相同的節點數量下數據包端到端的平均延時。從圖5可以看出，隨著源節點數目的增多時延變長。在相同源節點數目的情況下，延時的總體趨勢是隨著節點數變多而變大，這是由于隨著源節點數目的增加會使網絡過于擁塞，包成功接收的時間變長，因此會加長時延。而在源節點數目相同的情況下，優化的AODVjr+Cluster算法的時延還是相對較小的。

5 結束語

針對ZigBee網絡的基本路由算法，本文在詳細分析了其特征基礎之上提出了改進的Cluster-Tree算法和改進AODVjr的基本策略，最后提出了一種基于AODVjr的簇樹網絡路由策略。改進的簇樹算法在原Cluster-Tree算法基礎上引進了鄰居列表，在數據傳輸過程中，綜合考慮了路由跳數;改進AODVjr算法的基本策略，從能量角度考慮，有效延長網絡的生存時間;基于AODVjr的簇樹網絡路由綜合了上述兩種改進方案的優點，能有效的兼顧端到端延遲和節點剩余能量，較好的改善了網絡效率。總之，通過對ZigBee網絡路由分析，可以進一步改進其網絡性能，從而保證ZigBee網絡技術獨特的生存空間。

參考文獻:

[1] 蔣挺，趙成林.紫蜂技術及其應用[M].北京:北京郵電大學出版社，2006:9-12.

[2] 耿萌.Zigbee路由協議研究與分析[D].河南:信息工程大學，2006.

[3] B. NEFZI and Y. Q. Song. Performance analysis and improvement of zigbee routing protocol[C].In 7th IFAC International Conference on Fieldbuses Networks in Industrial Embedded Systems， pages 351–369， France， 2007.

[4] 班艷麗，柴喬林，王琛.基于能量均衡的ZigBee網絡樹路由算法[J].計算機應用，2008，28(11):2791-2794.

[5] 劉湘雯，侯惠峰，張霞等.基于群樹結構的IPv6無線傳感器網絡的組網及路由協議[J].計算機科學，2007，34(5):28-31.

[6] HOU Ting-chao，Tsai T J.An Access—based Clustering Protocol for Multihop Wireless Ad Hoc Networks[J].IEEE Joumal on Selected Areas in Communications，2001，19(7):1201-1210.

[7] 鮑鳳卿.基于Ns2的ZigBee網絡節點接入的研究[J].信息技術，2008，11(5):95-98.