摘要：ZigBee技術是為無線傳感器網(wǎng)絡技術設計的一項新興的低成本、低功耗的短距離無線通信技術。在分析ZigBee路由機制的基礎上，針對控制分組的傳輸范圍和轉發(fā)方向提出降低路由開銷的改進方案，并與原算法進行仿真分析。

關鍵詞：ZigBee；路由算法；路由開銷

中圖分類號：TP393文獻標識碼：A 文章編號：1009-3044(2008)06-10000-00

Research on ZigBee Routing Algorithm with Reduced Routing Overhead

GUO Zhuang－h(huán)ui， HU Ke， WANG Lei

(Institute of Electronic Communication Engineering， Tongji University， Shanghai 200092，China)

Abstract: ZigBee technology is a low-cost， low power consumption， short-distance wireless communication technology， which is newly designed for wireless sensor networks. Based on the analysis of routing process， the author proposes improved routing strategies focus on restricting the transmission range and direction of control packets to reduce the routing overhead， and make simulation and analysis with original routing algorithm.

Key words: ZigBee; routing algorithm; routing overhead

1 引言

ZigBee技術是一種新興的針對于無線傳感器網(wǎng)絡的短距離無線通信技術。它依據(jù)IEEE802.15.4標準，在數(shù)千個微小的傳感器之間相互協(xié)調，以接力的方式通過無線電波將數(shù)據(jù)從一個傳感器傳到另一個傳感器，由于這些傳感器只需要很少的能量，所以具有非常高的通信效率。與藍牙和Wi-Fi相比，ZigBee具有數(shù)據(jù)傳輸速率低、功耗低、成本低，復雜度低、時延短、網(wǎng)絡容量大、工作頻段靈活等特點，其技術特性決定它將是無線傳感器網(wǎng)絡最具潛力的選擇，具有廣闊的應用前景[1]。

為了達到低成本、低功耗、可靠性高等設計目標，ZigBee網(wǎng)絡中采用了Cluster-Tree + AODVjr路由算法，結合了Cluster-Tree算法和AODVjr算法各自的優(yōu)點。Cluster-Tree（簇-樹）是一種由協(xié)調器展開生成的樹型網(wǎng)絡拓撲結構，適合于節(jié)點靜止或者移動較少的場合，屬于靜態(tài)路由，不需要存儲路由表。AODVjr (AODV Junior)[2]是對按需距離矢量路由(Ad-hoc On-Demand Distance Vector Routing， AODV)[3，4]算法的改進，充分考慮了降低成本、節(jié)能、使用的方便性等因素，簡化了AODV的一些特點，但是仍然保持AODV的原始功能。

路由開銷是衡量路由算法性能的一個非常重要的指標，它是傳遞數(shù)據(jù)分組時使用的控制分組總和，較大的路由開銷將會給網(wǎng)絡的運行帶來負面影響。由于控制分組相對于數(shù)據(jù)分組是一種資源的浪費，因此在保證網(wǎng)絡的分組遞交率和平均時延性能不受影響的前提下，盡量減少無用的控制分組，降低路由算法的路由開銷，對于網(wǎng)絡的優(yōu)化和減負具有重要的意義。

2 ZigBee路由算法分析

在ZigBee網(wǎng)絡中，節(jié)點使用Cluster-Tree算法按照父子關系選擇路徑，即當一個節(jié)點接收到數(shù)據(jù)分組后如果發(fā)現(xiàn)該數(shù)據(jù)分組不是給自己的，則只能轉發(fā)給它的父節(jié)點或者子節(jié)點，不存在路由發(fā)現(xiàn)過程，然而由Cluster-Tree建立的路由不一定是最優(yōu)的路徑，會造成分組傳輸時延增加，而且容易造成網(wǎng)絡中通信流量分配不均衡。為了提高路由效率，ZigBee中允許具有路由功能的節(jié)點使用AODVjr算法去發(fā)現(xiàn)路由，即具有路由功能的節(jié)點可以不按照父子關系而直接發(fā)送信息到其通信范圍內的其它具有路由功能的節(jié)點，尋找通往目的節(jié)點的最優(yōu)路徑；而不具有路由功能的節(jié)點仍然使用Cluster-Tree路由發(fā)送數(shù)據(jù)分組和控制分組。由于AODVjr的使用，降低了分組傳輸時延，提高了分組遞交率。

2.1 網(wǎng)絡地址的分配機制[5]

假定每個父節(jié)點最多可以連接Cm個子節(jié)點，這些子節(jié)點中最多可以有Rm個路由節(jié)點，網(wǎng)絡的最大深度為Lm，用Cskip(d)表示網(wǎng)絡深度為d的父節(jié)點為其子節(jié)點分配的地址間的偏移量，它的值可按如下公式計算：

對于地址為A深度為d的ZigBee路由器，如果地址為D的目的節(jié)點滿足下面的不等式，那么D是它的一個子節(jié)點：

若目的節(jié)點 是當前節(jié)點 的后代，那么從 到 的下一跳節(jié)點地址 可以表示為：

2.2 路由建立過程

路由的建立過程分為以下兩大步驟：

第一步，廣播RREQ分組，建立反向路由：

節(jié)點創(chuàng)建并向周圍節(jié)點廣播一個RREQ分組，如果收到RREQ的節(jié)點是一個RN-節(jié)點，它就按照Cluster-Tree路由轉發(fā)此分組；如果收到RREQ的節(jié)點是一個RN+節(jié)點，則在路由表中建立一個指向RREQ源節(jié)點的反向路由，并繼續(xù)廣播此RREQ分組。

第二步，回復RREP分組，建立正向路由：

經(jīng)過一系列廣播后，一旦RREQ到達目的節(jié)點（RN+）或者目的節(jié)點（RN-和RFD）的父節(jié)點，此節(jié)點就向RREQ的源節(jié)點回復一個RREP分組，RREP將沿著已建立的反向路由向源節(jié)點傳輸，每個收到RREP的節(jié)點建立到目的節(jié)點的正向路由并更新相應的路由信息。

圖1給出了一個路由建立的例子。

3 降低路由開銷的改進算法研究

由于Cluster-Tree算法的使用，ZigBee路由相比AODVjr具有較少的路由開銷，但是我們分析ZigBee的路由機制，發(fā)現(xiàn)在尋找路徑的過程中仍然會產生很多多余的控制分組，這些控制分組雖然也參與路由發(fā)現(xiàn)，但對于最終找到一條最優(yōu)路徑并沒有什么幫助。如果我們能夠在路由發(fā)現(xiàn)過程中適當?shù)叵拗七@些控制分組的產生或轉發(fā)，將能夠顯著地降低網(wǎng)絡的路由開銷。能否準確地找到這部分控制分組是非常關鍵的，因為如果抑制了一些可能找到最優(yōu)路徑的控制分組的產生或轉發(fā)，將會降低路由協(xié)議的性能（如分組遞交率、平均端到端時延等）。

針對第3節(jié)對ZigBee路由算法的分析，我們從兩個角度分析降低路由開銷的策略：

（1）限制RREQ分組的傳輸范圍

ZigBee路由中，RN+節(jié)點在選擇路徑時會向周圍節(jié)點廣播路由請求分組RREQ，網(wǎng)絡中的其它節(jié)點幫助轉發(fā)RREQ以便找到一條通往目的節(jié)點的最優(yōu)路徑。這樣隨著網(wǎng)絡業(yè)務量的增加，節(jié)點需要處理的控制分組也會大量增加。路徑的長度直接影響著網(wǎng)絡的各項性能，ZigBee在Cluster-Tree算法中加人AODVjr的一個主要原因就是為了尋找相比Cluster-Tree更優(yōu)的路徑，如果找到的路徑比按照Cluster-Tree算法選擇的路徑長，便沒有了實際的意義，而且較長的路徑往往會對網(wǎng)絡的平均端到端時延和壽命等產生負面影響。因此，如果我們能夠事先確定RREQ分組的傳輸范圍，使之不超過節(jié)點按照Cluster-Tree算法找到的路徑長度，那么就能夠丟棄一些超出傳輸范圍的控制分組，達到降低路由開銷的目的。

（2）限制RREQ分組的轉發(fā)方向

由第3節(jié)路由建立過程中RREQ分組的廣播機制可知，RN+節(jié)點收到RREQ分組后如果發(fā)現(xiàn)自己不是路由的目的節(jié)點，便向周圍所有的鄰節(jié)點轉發(fā)此RREQ，事實上這樣做存在著很大一部分浪費，而且隨著轉發(fā)跳數(shù)的增加，此種無益的開銷增加得更大。究其原因主要有兩點：其一，并不是所有的鄰節(jié)點都有可能幫助其找到到達目的節(jié)點的最優(yōu)路徑，有些鄰節(jié)點幾乎不可能找到通往目的節(jié)點的路徑，而有些鄰節(jié)點只會使路由選擇走很大彎路；其二，在大多數(shù)路由算法的路由發(fā)現(xiàn)過程中，數(shù)據(jù)可以傳輸?shù)姆秶ǔＯ拗圃诰W(wǎng)絡直徑的范圍之內，超過傳輸范圍的RREQ會被節(jié)點丟棄，因此存在一些鄰節(jié)點由于距離目的節(jié)點太遠而不可能將RREQ分組轉發(fā)過去。從上述分析可知，如果我們在每個節(jié)點轉發(fā)RREQ分組前，加入一個路由方向判斷機制，如果此節(jié)點是對路由發(fā)現(xiàn)無益的節(jié)點，令它丟棄分組不再轉發(fā)，那么可以節(jié)省很大一部分路由開銷。隨著網(wǎng)絡深度的增加，這種節(jié)省會更加明顯。

4 改進算法的實施方案

4.1 限制RREQ分組的傳輸范圍

根據(jù)上一節(jié)的分析，我們可以在源節(jié)點廣播RREQ分組前根據(jù)目的節(jié)點的地址來設置分組傳輸?shù)淖畲蠓秶?，當傳輸?shù)穆窂匠^此范圍時，節(jié)點自動丟棄收到的這個分組。

從樹型結構可以很容易地看出，如果僅使用Cluster-Tree算法選擇路由，可能存在的最長路徑應是網(wǎng)絡最大深度的2倍，即2Lm，可以規(guī)定RREQ的最大傳輸范圍為2Lm，這樣當RREQ的傳輸范圍到達2Lm時，節(jié)點便自動丟棄收到的RREQ。

為了進一步合理地縮小傳輸范圍，盡量降低路由開銷，我們利用ZigBee網(wǎng)絡的Cluster-Tree參數(shù)Cm、Rm、Lm和目的節(jié)點的網(wǎng)絡地址D0來確定RREQ的最大傳輸范圍l。發(fā)起RREQ的源節(jié)點地址為 深度為d，均為已知量，目的節(jié)點的深度為d0，為未知量。下面詳細闡述求解 的過程。

首先判斷目的節(jié)點與源節(jié)點的位置關系。如果目的節(jié)點是源節(jié)點的后代或源節(jié)點是目的節(jié)點的后代，那么RREQ到達目的節(jié)點后所發(fā)現(xiàn)的路徑長度應不大于目的節(jié)點與源節(jié)點的深度之差，即l=│d0-d│；如果目的節(jié)點和源節(jié)點均不是對方的后代，那么所發(fā)現(xiàn)的路徑長度應不大于目的節(jié)點與源節(jié)點相對于最高深度公共父節(jié)點的深度之和，設最高深度公共父節(jié)點的深度為dc，則l=d+d0-2dc。作為特例，當它們的公共父節(jié)點只有協(xié)調器節(jié)點時，dc=0，此時l=d+d0。

事實上，目的節(jié)點是源節(jié)點的后代或者源節(jié)點是目的節(jié)點的后代也是一種特殊情況，此時dc=d或dc=d0，我們可以統(tǒng)一用=d+d0-2dc來求。然而由于源節(jié)點發(fā)送分組時只知道目的節(jié)點的地址D0不知道其深度d0，也不知道它與目的節(jié)點的最大深度父節(jié)點的深度dc，我們無法直接得到l。

易知0≤dc≤d，我們可以沿樹型結構從協(xié)調器節(jié)點向地址為 的源節(jié)點發(fā)送分組，循環(huán)利用本文2.1節(jié)式3求出下一跳地址N，此時dc將從0開始依次增加至d-1，在每一個中間節(jié)點處利用式2判斷目的節(jié)點是否是當前節(jié)點的后代：當它是深度為dc的節(jié)點的后代而不是深度為dc+1的節(jié)點的后代時，則dc即為源節(jié)點和目的節(jié)點的最大深度父節(jié)點的深度。

求dc的算法流程如圖2。

在求得dc之后，我們從協(xié)調器節(jié)點開始沿著樹型結構，利用循環(huán)過程直至求得的下一跳地址 等于目的節(jié)點地址D0，統(tǒng)計出的循環(huán)次數(shù)便是從協(xié)調器節(jié)點到目的節(jié)點的跳數(shù)，即深度d0，進而求得RREQ的最大傳輸范圍l=d+d0-2dc。其計算流程如下圖3。

計算出l后，源節(jié)點在廣播RREQ分組前可以將RREQ的傳輸范圍設為l，當傳輸路徑到達l時自動丟棄RREQ，這樣就進一步縮小了RREQ的傳輸范圍，減少了不必要控制分組的轉發(fā)，達到降低路由開銷的效果。

4.2 限制RREQ分組的轉發(fā)方向

從前面的介紹可以得知，ZigBee網(wǎng)絡中所有節(jié)點在收到分組后都可以利用本文2.1中的式2判斷分組想要到達的目的節(jié)點是否是自己的一個后代。如果節(jié)點確定了RREQ分組的目的節(jié)點是自己的一個后代，那么此時如果仍然讓其父節(jié)點為其轉發(fā)RREQ，此RREQ找到通往目的節(jié)點的最優(yōu)路徑的可能性是非常小的，甚至有可能無法到達目的節(jié)點；反之，如果節(jié)點確定了RREQ分組的目的節(jié)點不是自己的一個后代，卻仍然將RREQ發(fā)送給它所有的子節(jié)點，這些子節(jié)點再轉發(fā)RREQ已沒有太大的意義。我們可以使用式2判斷RREQ目的節(jié)點的大致方向，從而限制其向與目的節(jié)點相反的方向傳輸，達到節(jié)省路由開銷的目的。

具體做法如下：

在路由請求分組RREQ中增加一個標志位flag，用來記錄RREQ的目的節(jié)點與本節(jié)點的關系：flag=1，目的節(jié)點是本節(jié)點的后代；flag=0，目的節(jié)點不是本節(jié)點的后代。設目的節(jié)點為D，在路由發(fā)現(xiàn)過程中存在兩個中間節(jié)點A和B，A向B轉發(fā)分組。我們的算法是：

（1）A在轉發(fā)RREQ分組前，執(zhí)行下列偽碼：

if (D是A的一個后代)

flag = 1;

else

flag = 0;

（2）B收到A轉發(fā)的RREQ分組后，執(zhí)行下列偽碼：

if (flag = = 1)

{

if (B是A的父節(jié)點)

丟棄RREQ；

else

處理RREQ；

}

else

{

if(B是A的一個子節(jié)點)

丟棄RREQ；

else

處理RREQ；

}

綜合上述兩種改進策略，我們將其應用在ZigBee原始路由算法中，基于降低路由開銷的改進算法流程如下圖4所示：

5 仿真結果及性能分析

本文采用NS2軟件對改進算法和原算法的性能進行仿真，仿真采用下圖5所示的網(wǎng)絡拓撲。

仿真參數(shù)見表1。

表1 降低路由開銷改進算法的仿真參數(shù)

從仿真結果可以看出，ZBR改進算法的路由開銷始終遠遠小于原始ZBR算法的路由開銷。這是因為：一，ZBR改進算法在源節(jié)點廣播RREQ分組前利用樹型結構和Cluster-Tree算法限制了RREQ的最大傳輸范圍，丟棄了一部分超出范圍的不必要的控制分組；二，在每個中間節(jié)點轉發(fā)之前，都進行當前節(jié)點與目的節(jié)點關系的判斷，以便指示下一跳節(jié)點該如何處理。路由開銷得到了很好的改善，那么改進后網(wǎng)絡的分組遞交率、平均跳數(shù)和平均端到端時延性能會不會由于改進算法的引用導致明顯的下降呢？圖7分別給出了仿真的結果。

從圖7(a)中可以看出，隨著CBR數(shù)據(jù)流個數(shù)的增加，ZBR改進算法與ZBR算法的分組遞交率相差不大，仍然維持在99.6%左右，說明改進方案并沒有影響數(shù)據(jù)包的發(fā)送效率。從圖7(b)(c)可以看出，隨著CBR數(shù)據(jù)流個數(shù)的增加，ZBR改進算法的平均跳數(shù)、平均端到端時延始終與原始ZBR算法保持一致，ZBR改進算法的平均跳數(shù)和平均端到端時延并沒有明顯高于ZBR，這說明改進算法對RREQ分組范圍和方向的限制策略是合理的，丟棄的分組基本為沒有意義的冗余分組，改進算法的使用并沒有使節(jié)點選擇更長的路徑，沒有增加發(fā)送分組的時延。

綜合以上分析可以得出下述結論：

降低路由開銷的ZigBee路由改進算法通過限定RREQ分組的最大傳輸范圍和約束RREQ分組在每個中間節(jié)點的轉發(fā)方向，使節(jié)點在路由發(fā)現(xiàn)時丟棄了一部分無益的控制分組，從而在保證網(wǎng)絡分組遞交率、平均跳數(shù)和平均端到端時延性能的同時，達到了降低路由開銷的目的。

6 結語

本文在分析ZigBee路由算法和路由機制的基礎上，針對降低網(wǎng)絡的路由開銷這一目標探討了改進方案，并在NS-2仿真平臺中進行了驗證和對比分析。

改進方案從兩個角度考慮：通過設置路由請求分組RREQ的最大傳輸范圍，丟棄超出此范圍的無益控制分組，通過限定每一個中間節(jié)點轉發(fā)分組的方向，丟棄對路由發(fā)現(xiàn)無益的反方向控制分組。經(jīng)過上述方案對算法的改進，明顯減少了路由開銷，同時從仿真結果可以看出，分組遞交率、平均跳數(shù)、平均端到端時延等性能沒有受到較大影響。這是由于本方案丟棄的分組均為對節(jié)點發(fā)現(xiàn)最優(yōu)路徑無關緊要的節(jié)點，準確地找出這些節(jié)點是方案可靠性的

關鍵。

7 致謝

本文研究得到了國家自然科學基金重點項目（70531020）資助，在此謹表謝意。

參考文獻：

[1]酈亮. IEEE802.15.4 標準及其應用.電子設計應用，2003.

[2]Ian D.Chakeres， Luke Klein-Berndt. AODVjr， AODV simplified. Mobile Computing and Communications Review， 2002， 6(3):100-101

[3]Charles E. Perkins， Ad hoc On Demand Distance Vector Routing，Mobile Computing Systems and Applications， 1999.

[4]Masayuki Tauchi， Ad-Hoc Routing Protocol Avoiding Route Breaks Based on AODV， System Sciences， 2005.

[5]蔣挺，趙成林.紫蜂技術及其應用.北京：北京郵電大學出版社，2006.

收稿日期：2008-01-12

基金項目：國家自然科學基金重點項目（70531020）

作者簡介：郭壯輝，同濟大學電子與信息工程學院碩士研究生，研究方向為智能自動化；胡柯，同濟大學電子與信息工程學院碩士研究生，研究方向為智能自動化；汪鐳，江蘇無錫人，同濟大學控制科學與工程系教授，博士生導師，從事智能自動化系統(tǒng)研究。

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”