ZigBee中Cluster-Tree路由算法改進研究

鄒國霞，李 燕

（桂林航天工業高等?？茖W校，桂林 541004）

0 引言

無線傳感器網絡是由大量無處不在的，具有通信與計算能力的微小傳感器節點密集布設在監控區域而組成的自組織網絡，在工業控制、工業無線定位、家庭網絡、汽車自動化、樓宇自動化、消費電子、醫療設備等多個領域具有廣闊的應用前景和較高的應用價值。ZigBee是IEEE 802.15.4標準基礎上的無限個域網的短距離無線通信技術，它擁有低成本、低功耗、低復雜度、網絡容量大、可靠性高等方面的優勢[1~3]。

在ZigBee網絡中，Cluster-tree路由算法為目的地址提供了簡單但可靠的路由[4~6]。該算法采用了網絡地址分配機制，節點根據目的節點的網絡地址來計算下一跳節點。雖然該算法具有簡單并且不需要存儲路由表等優點，但也存在一些缺點,比如即使目的節點就在發送節點附近，數據包也必須沿Cluster-tree拓撲傳送到目的節點，而不能直接發送到目的節點。為此，靠近根部的節點可能會因為業務量過大而過早耗盡電池能量。針對這些情況，本文對Cluster-tree路由算法進行了改進，引入路由表，使局部路由最優化,從而減少了網絡的總體能量消耗，延長了網絡的壽命。

1 ZigBee Cluster-tree路由算法

IEEE 802.15.4定義了2種物理設備，全功能設備（Full Function Device,FFD）和精簡功能設備（Reduced Function Device,RFD）[7,8]。FFD可以擔任網絡協調器、路由器和終端設備，能與RFD和其他FFD進行通訊。RFD只能作為終端設備，只需要較少的資源和存儲空間，成本比FFD低很多。在ZigBee網絡中，定義了三種邏輯設備類型：ZigBee協調器（簡稱ZC）、ZigBee路由器、ZigBee終端設備。

1.1 ZigBee地址分配機制

加入ZigBee網絡的節點通過IEEE 802.15.4 MAC層提供的關聯過程組成一顆邏輯Clustertree，當網絡中的節點允許一個新節點通過它加入網絡時，它們之間就形成了父子關系，每個進入網絡的節點都會得到父節點為其分配的一個在該網絡中唯一的網絡地址。規定每個父節點最多可以連接Cm個子節點, 這些子節點中最多可以有Rm個路由節點，網絡的最大深度為Lm。Cskip(d)是網絡深度為d的父節點為其子節點分配的地址之間的偏移量。Cskip(d)的計算表達式為(1)式

設置ZC的網絡地址為0 ，其網絡深度Depth0 =0。假設父節點k的深度為d，地址為Ap。如果新加入的節點是RFD ，并且該節點是其父節點的第n個RFD節點，則父節點為該節點分配網絡地址:

如果新加入的節點是FFD，并且該節點是其父節點的第k個FFD節點。則父節點為該節點分配網絡地址:

ZigBee網絡路由基于上面的分布式網絡地址分配機制構建，支持Cluster-Tree路由算法、AODVjr路由算法及兩者混合模式的路由算法。

1.2 Cluster-tree路由算法

在該算法中，節點根據目的節點的網絡地址來計算分組的下一跳，假設地址為A，深度為d的ZigBee路由節點收到目的節點地址為D的數據幀，路由節點首先通過(4)式

判斷該目的節點是否是它的后代節點。

如果目的節點是其后裔節點,則下一跳節點地址為(5)式。

否則，如果目的節點不是其后裔節點，則下一跳節點為該節點的父節點。

2 問題的提出

ZigBeeCluster-tree路由算法按Cluster-tree型結構分層遍歷，算法簡單且查找目的節點的速度快，但是這種路由選擇不可能是最佳路由，而且ZC節點需要轉發大量的數據，必須儲備充足的能量，但是就目前的技術，電池的使用時間是有限制的，為此容易造成網絡分割，縮短網絡壽命。

假設有如圖1所示的網絡，如果采用原始的Cluster-Tree路由算法，rfd[12]發送數據給rfd[14]，需要4跳才能到達；rfd[12]發送數據給rfd[17]，需要5跳才能到達。且都需要ZC進行轉發，消耗了大量的ZC能量。如果考慮在無線信號覆蓋范圍內，信號可以直接從源地發送到目的地，則rfd[12]發送數據給rfd[14]，需要2跳就能到達；rfd[12]發送數據給rfd[17]，需要2跳就能到達。

針對以上的問題，需要將鄰居表應用到Cluster-Tree路由算法中，減少Cluster-Tree路由算法的路由跳數和節約整體能量。

圖1 ZigBee網絡拓撲結構圖

3 改進算法設計

3.1 鄰居表定義

如果兩節點在一跳范圍內可以直接通信,我們就說這兩個節點是鄰居。當一個ZigBee節點想要加入網絡時，它會以廣播的形式將請求連接的信息傳給其一跳通信范圍內的其他節點；收到請求連接信息的其它存在于已知網絡中的節點會給要求加入網絡的節點傳回一個信息；最后要求加入網絡的節點根據收到的信息選擇一個合適的父節點，再回傳一個加入信息并正式加入該網絡。

在節點加入ZigBee網絡時，相互傳送信息的過程中可以得知一跳范圍內節點的一些基本信息，并將這些信息存放在鄰居表里。設計的鄰居表結點NbNode如圖2所示。

圖2 鄰居表結點結構體

NbNode有三個域:

AddNb：鄰居節點地址。

Type：鄰居節點設備類型, 如果為FFD設備，既可以作為路由器也可以作為終端設備；如果為RFD設備，不具有路由功能，只進行數據的收發。

Depth：鄰居節點的深度。

3.2 改進算法描述

算法分3步，具體方法如下：

1）搜索目的子節點

圖3 改進Cluster-Tree路由算法流程圖

當一個節點接收到一個數據幀時，首先根據式(4)檢查目的地址D是否是它的一個后代節點,如果 D 是后代節點,沿著Cluster-tree型結構將該數據幀轉發到相應的子節點,如果D不是后代節點,轉向步驟(2) 。

2）搜索鄰居表

如果D與鄰居表表項中的AddNb相等，則直接發送給鄰居節點；如果D與鄰居表表項中的AddNb不相等，則看Type類型，只有當Type=“FFD”時，再利用式(4)檢查目的地址D是否是該鄰居節點的一個后代節點,如果D是其后代節點,將該數據幀轉發到該鄰居節點,如果D不是其后代節點,轉向步驟(3) 。

3）搜索下一條子節點

如果A < D < A + Cskip(d-1)，則下一跳地址為

4）搜索祖先節點

不滿足(1)-(3)條件時，將數據幀發送給當前節點的父節點。

5）重復(1)-(4)步驟

具體流程如圖3所示。

4 算法的仿真和分析

仿真工具采用OMNET++4.1。網絡覆蓋面積為500*500m，網絡節點數目為30，網絡延遲為0，誤碼率為0，參照圖1網絡拓撲，設置Cm=6，Rm=4，Lm=4。為了簡化，ZC初始能量為30000J,，其他節點能量初始為20000J。仿真時間為60S。

通過仿真實驗，對改進算法和傳統Cluster-tree路由算法進行比較，重點比較了節點能耗和平均跳數。

4.1 節點能耗比較

圖4中紅色表示ZC節點，其他的為FFD節點，橫坐標為時間，單位為秒，縱坐標為能量，單位為J。從圖中可以看出，改進Cluster-Tree路由算法中，ZC節點變化比較緩慢，仿真時間結束時剩余能量比Cluster-Tree路由算法多很多。其他的FFD節點，只有藍色和綠色代表的FFD節點能耗比原Cluster-Tree路由算法快，其它的FFD節點能耗都有所減少。

圖4 Cluster-Tree路由算法改進前后節點能耗變化趨勢對比圖

從整體上看，改進的Cluster-Tree路由算法整體能耗要小于原Cluster-Tree路由算法。

4.2 節點跳數比較

圖5 Cluster-Tree路由算法改進前后節點跳數變化趨勢對比圖

圖5中線段的端點處表示此時RFD發送的信息已經到達目的地，橫坐標表示時間，單位為S，縱坐標為跳數。從圖中可以看出，圖5(b)6跳個數約為15，圖5(a)6跳個數約為20；圖5(b)2跳個數約為16，圖5(a)2跳個數約為15；圖5(b)3跳個數為28，圖5(a)3跳個數為11；圖5(b)4跳個數約為18，圖5(a)4跳個數約為29；圖5(b)5跳個數約為36，圖5(a)5跳個數約為39。

從整體上看，改進的Cluster-Tree路由算法節點跳數要小于原Cluster-Tree路由算法。

綜合(1)(2)比較分析證實：改進的Cluster-Tree路由算法在減少路由跳數得同時節約了整體能量。

5 結論

針對Cluster-Tree路由算法存在的一跳節點可能需要多跳到達問題，將鄰居表引入進Cluster-Tree路由算法中，經仿真實驗證明，改進的Cluster-Tree路由算法可以根據鄰居表有效的優化路由，同時降低網絡整體能量消耗，特別是ZC的能量消耗，最終提高網絡的效率，延長網絡的存活時間。

[1] 賀玲玲.Z igBee傳感網絡Cluster-T ree改進路由算法研究[J].傳感技術學報,2010,23(9):1303-1307.

[2] ZigBee Alliance.ZigBee specification 2008[ DB/OL].[2008.01.27]. http://www.zigbee.org .

[3] Suzuki,N.;Mitani,T.;Shinohara,N..Study and Development of a microwave power receiving system for ZigBee device[J].Asia-P acific Microwave ConferenceProceedings,APMC2010:45-48.

[4] Khan,S.A.;Khan,F.A..Performance analysis of a ZigBee beacon enabled cluster-tree network[J].Third International Conference on Electrical Engineering,ICEE 2009:1-6.

[5] Dilum Bandara,H.;Jayasumana,A.P..An enhanced top-down cluster and cluster-tree formation algorithm for Wireless Sensor Networks[J].International Conference on Industrial and Information Systems,ICIIS 2007:565-570.

[6] 班艷麗,柴喬林,王芳.改進的ZigBee 網絡路由算法[J].計算機工程與應用, 2009,45(5):95-97,116.

[7] 朱向慶,王建明.Z igBee協議網絡層的研究與實現[J].電子技術應用,2006,32(1):137-140.

[8] 孫利民,李建中,陳渝,等.無線傳感器網絡[M].北京:清華大學出版社, 2005.