ZigBee中Cluster-Tree路由算法改進(jìn)研究

鄒國(guó)霞，李 燕

（桂林航天工業(yè)高等專科學(xué)校，桂林 541004）

0 引言

無線傳感器網(wǎng)絡(luò)是由大量無處不在的，具有通信與計(jì)算能力的微小傳感器節(jié)點(diǎn)密集布設(shè)在監(jiān)控區(qū)域而組成的自組織網(wǎng)絡(luò)，在工業(yè)控制、工業(yè)無線定位、家庭網(wǎng)絡(luò)、汽車自動(dòng)化、樓宇自動(dòng)化、消費(fèi)電子、醫(yī)療設(shè)備等多個(gè)領(lǐng)域具有廣闊的應(yīng)用前景和較高的應(yīng)用價(jià)值。ZigBee是IEEE 802.15.4標(biāo)準(zhǔn)基礎(chǔ)上的無限個(gè)域網(wǎng)的短距離無線通信技術(shù)，它擁有低成本、低功耗、低復(fù)雜度、網(wǎng)絡(luò)容量大、可靠性高等方面的優(yōu)勢(shì)[1~3]。

在ZigBee網(wǎng)絡(luò)中，Cluster-tree路由算法為目的地址提供了簡(jiǎn)單但可靠的路由[4~6]。該算法采用了網(wǎng)絡(luò)地址分配機(jī)制，節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)的網(wǎng)絡(luò)地址來計(jì)算下一跳節(jié)點(diǎn)。雖然該算法具有簡(jiǎn)單并且不需要存儲(chǔ)路由表等優(yōu)點(diǎn)，但也存在一些缺點(diǎn),比如即使目的節(jié)點(diǎn)就在發(fā)送節(jié)點(diǎn)附近，數(shù)據(jù)包也必須沿Cluster-tree拓?fù)鋫魉偷侥康墓?jié)點(diǎn)，而不能直接發(fā)送到目的節(jié)點(diǎn)。為此，靠近根部的節(jié)點(diǎn)可能會(huì)因?yàn)闃I(yè)務(wù)量過大而過早耗盡電池能量。針對(duì)這些情況，本文對(duì)Cluster-tree路由算法進(jìn)行了改進(jìn)，引入路由表，使局部路由最優(yōu)化,從而減少了網(wǎng)絡(luò)的總體能量消耗，延長(zhǎng)了網(wǎng)絡(luò)的壽命。

1 ZigBee Cluster-tree路由算法

IEEE 802.15.4定義了2種物理設(shè)備，全功能設(shè)備（Full Function Device,FFD）和精簡(jiǎn)功能設(shè)備（Reduced Function Device,RFD）[7,8]。FFD可以擔(dān)任網(wǎng)絡(luò)協(xié)調(diào)器、路由器和終端設(shè)備，能與RFD和其他FFD進(jìn)行通訊。RFD只能作為終端設(shè)備，只需要較少的資源和存儲(chǔ)空間，成本比FFD低很多。在ZigBee網(wǎng)絡(luò)中，定義了三種邏輯設(shè)備類型：ZigBee協(xié)調(diào)器（簡(jiǎn)稱ZC）、ZigBee路由器、ZigBee終端設(shè)備。

1.1 ZigBee地址分配機(jī)制

加入ZigBee網(wǎng)絡(luò)的節(jié)點(diǎn)通過IEEE 802.15.4 MAC層提供的關(guān)聯(lián)過程組成一顆邏輯Clustertree，當(dāng)網(wǎng)絡(luò)中的節(jié)點(diǎn)允許一個(gè)新節(jié)點(diǎn)通過它加入網(wǎng)絡(luò)時(shí)，它們之間就形成了父子關(guān)系，每個(gè)進(jìn)入網(wǎng)絡(luò)的節(jié)點(diǎn)都會(huì)得到父節(jié)點(diǎn)為其分配的一個(gè)在該網(wǎng)絡(luò)中唯一的網(wǎng)絡(luò)地址。規(guī)定每個(gè)父節(jié)點(diǎn)最多可以連接Cm個(gè)子節(jié)點(diǎn), 這些子節(jié)點(diǎn)中最多可以有Rm個(gè)路由節(jié)點(diǎn)，網(wǎng)絡(luò)的最大深度為L(zhǎng)m。Cskip(d)是網(wǎng)絡(luò)深度為d的父節(jié)點(diǎn)為其子節(jié)點(diǎn)分配的地址之間的偏移量。Cskip(d)的計(jì)算表達(dá)式為(1)式

設(shè)置ZC的網(wǎng)絡(luò)地址為0 ，其網(wǎng)絡(luò)深度Depth0 =0。假設(shè)父節(jié)點(diǎn)k的深度為d，地址為Ap。如果新加入的節(jié)點(diǎn)是RFD ，并且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的第n個(gè)RFD節(jié)點(diǎn)，則父節(jié)點(diǎn)為該節(jié)點(diǎn)分配網(wǎng)絡(luò)地址:

如果新加入的節(jié)點(diǎn)是FFD，并且該節(jié)點(diǎn)是其父節(jié)點(diǎn)的第k個(gè)FFD節(jié)點(diǎn)。則父節(jié)點(diǎn)為該節(jié)點(diǎn)分配網(wǎng)絡(luò)地址:

ZigBee網(wǎng)絡(luò)路由基于上面的分布式網(wǎng)絡(luò)地址分配機(jī)制構(gòu)建，支持Cluster-Tree路由算法、AODVjr路由算法及兩者混合模式的路由算法。

1.2 Cluster-tree路由算法

在該算法中，節(jié)點(diǎn)根據(jù)目的節(jié)點(diǎn)的網(wǎng)絡(luò)地址來計(jì)算分組的下一跳，假設(shè)地址為A，深度為d的ZigBee路由節(jié)點(diǎn)收到目的節(jié)點(diǎn)地址為D的數(shù)據(jù)幀，路由節(jié)點(diǎn)首先通過(4)式

判斷該目的節(jié)點(diǎn)是否是它的后代節(jié)點(diǎn)。

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

否則，如果目的節(jié)點(diǎn)不是其后裔節(jié)點(diǎn)，則下一跳節(jié)點(diǎn)為該節(jié)點(diǎn)的父節(jié)點(diǎn)。

2 問題的提出

ZigBeeCluster-tree路由算法按Cluster-tree型結(jié)構(gòu)分層遍歷，算法簡(jiǎn)單且查找目的節(jié)點(diǎn)的速度快，但是這種路由選擇不可能是最佳路由，而且ZC節(jié)點(diǎn)需要轉(zhuǎn)發(fā)大量的數(shù)據(jù)，必須儲(chǔ)備充足的能量，但是就目前的技術(shù)，電池的使用時(shí)間是有限制的，為此容易造成網(wǎng)絡(luò)分割，縮短網(wǎng)絡(luò)壽命。

假設(shè)有如圖1所示的網(wǎng)絡(luò)，如果采用原始的Cluster-Tree路由算法，rfd[12]發(fā)送數(shù)據(jù)給rfd[14]，需要4跳才能到達(dá)；rfd[12]發(fā)送數(shù)據(jù)給rfd[17]，需要5跳才能到達(dá)。且都需要ZC進(jìn)行轉(zhuǎn)發(fā)，消耗了大量的ZC能量。如果考慮在無線信號(hào)覆蓋范圍內(nèi)，信號(hào)可以直接從源地發(fā)送到目的地，則rfd[12]發(fā)送數(shù)據(jù)給rfd[14]，需要2跳就能到達(dá)；rfd[12]發(fā)送數(shù)據(jù)給rfd[17]，需要2跳就能到達(dá)。

針對(duì)以上的問題，需要將鄰居表應(yīng)用到Cluster-Tree路由算法中，減少Cluster-Tree路由算法的路由跳數(shù)和節(jié)約整體能量。

圖1 ZigBee網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖

3 改進(jìn)算法設(shè)計(jì)

3.1 鄰居表定義

如果兩節(jié)點(diǎn)在一跳范圍內(nèi)可以直接通信,我們就說這兩個(gè)節(jié)點(diǎn)是鄰居。當(dāng)一個(gè)ZigBee節(jié)點(diǎn)想要加入網(wǎng)絡(luò)時(shí)，它會(huì)以廣播的形式將請(qǐng)求連接的信息傳給其一跳通信范圍內(nèi)的其他節(jié)點(diǎn)；收到請(qǐng)求連接信息的其它存在于已知網(wǎng)絡(luò)中的節(jié)點(diǎn)會(huì)給要求加入網(wǎng)絡(luò)的節(jié)點(diǎn)傳回一個(gè)信息；最后要求加入網(wǎng)絡(luò)的節(jié)點(diǎn)根據(jù)收到的信息選擇一個(gè)合適的父節(jié)點(diǎn)，再回傳一個(gè)加入信息并正式加入該網(wǎng)絡(luò)。

在節(jié)點(diǎn)加入ZigBee網(wǎng)絡(luò)時(shí)，相互傳送信息的過程中可以得知一跳范圍內(nèi)節(jié)點(diǎn)的一些基本信息，并將這些信息存放在鄰居表里。設(shè)計(jì)的鄰居表結(jié)點(diǎn)NbNode如圖2所示。

圖2 鄰居表結(jié)點(diǎn)結(jié)構(gòu)體

NbNode有三個(gè)域:

AddNb：鄰居節(jié)點(diǎn)地址。

Type：鄰居節(jié)點(diǎn)設(shè)備類型, 如果為FFD設(shè)備，既可以作為路由器也可以作為終端設(shè)備；如果為RFD設(shè)備，不具有路由功能，只進(jìn)行數(shù)據(jù)的收發(fā)。

Depth：鄰居節(jié)點(diǎn)的深度。

3.2 改進(jìn)算法描述

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

1）搜索目的子節(jié)點(diǎn)

圖3 改進(jìn)Cluster-Tree路由算法流程圖

當(dāng)一個(gè)節(jié)點(diǎn)接收到一個(gè)數(shù)據(jù)幀時(shí)，首先根據(jù)式(4)檢查目的地址D是否是它的一個(gè)后代節(jié)點(diǎn),如果 D 是后代節(jié)點(diǎn),沿著Cluster-tree型結(jié)構(gòu)將該數(shù)據(jù)幀轉(zhuǎn)發(fā)到相應(yīng)的子節(jié)點(diǎn),如果D不是后代節(jié)點(diǎn),轉(zhuǎn)向步驟(2) 。

2）搜索鄰居表

如果D與鄰居表表項(xiàng)中的AddNb相等，則直接發(fā)送給鄰居節(jié)點(diǎn)；如果D與鄰居表表項(xiàng)中的AddNb不相等，則看Type類型，只有當(dāng)Type=“FFD”時(shí)，再利用式(4)檢查目的地址D是否是該鄰居節(jié)點(diǎn)的一個(gè)后代節(jié)點(diǎn),如果D是其后代節(jié)點(diǎn),將該數(shù)據(jù)幀轉(zhuǎn)發(fā)到該鄰居節(jié)點(diǎn),如果D不是其后代節(jié)點(diǎn),轉(zhuǎn)向步驟(3) 。

3）搜索下一條子節(jié)點(diǎn)

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

4）搜索祖先節(jié)點(diǎn)

不滿足(1)-(3)條件時(shí)，將數(shù)據(jù)幀發(fā)送給當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)。

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

具體流程如圖3所示。

4 算法的仿真和分析

仿真工具采用OMNET++4.1。網(wǎng)絡(luò)覆蓋面積為500*500m，網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目為30，網(wǎng)絡(luò)延遲為0，誤碼率為0，參照?qǐng)D1網(wǎng)絡(luò)拓?fù)?，設(shè)置Cm=6，Rm=4，Lm=4。為了簡(jiǎn)化，ZC初始能量為30000J,，其他節(jié)點(diǎn)能量初始為20000J。仿真時(shí)間為60S。

通過仿真實(shí)驗(yàn)，對(duì)改進(jìn)算法和傳統(tǒng)Cluster-tree路由算法進(jìn)行比較，重點(diǎn)比較了節(jié)點(diǎn)能耗和平均跳數(shù)。

4.1 節(jié)點(diǎn)能耗比較

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

圖4 Cluster-Tree路由算法改進(jìn)前后節(jié)點(diǎn)能耗變化趨勢(shì)對(duì)比圖

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

4.2 節(jié)點(diǎn)跳數(shù)比較

圖5 Cluster-Tree路由算法改進(jìn)前后節(jié)點(diǎn)跳數(shù)變化趨勢(shì)對(duì)比圖

圖5中線段的端點(diǎn)處表示此時(shí)RFD發(fā)送的信息已經(jīng)到達(dá)目的地，橫坐標(biāo)表示時(shí)間，單位為S，縱坐標(biāo)為跳數(shù)。從圖中可以看出，圖5(b)6跳個(gè)數(shù)約為15，圖5(a)6跳個(gè)數(shù)約為20；圖5(b)2跳個(gè)數(shù)約為16，圖5(a)2跳個(gè)數(shù)約為15；圖5(b)3跳個(gè)數(shù)為28，圖5(a)3跳個(gè)數(shù)為11；圖5(b)4跳個(gè)數(shù)約為18，圖5(a)4跳個(gè)數(shù)約為29；圖5(b)5跳個(gè)數(shù)約為36，圖5(a)5跳個(gè)數(shù)約為39。

從整體上看，改進(jìn)的Cluster-Tree路由算法節(jié)點(diǎn)跳數(shù)要小于原Cluster-Tree路由算法。

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

5 結(jié)論

針對(duì)Cluster-Tree路由算法存在的一跳節(jié)點(diǎn)可能需要多跳到達(dá)問題，將鄰居表引入進(jìn)Cluster-Tree路由算法中，經(jīng)仿真實(shí)驗(yàn)證明，改進(jìn)的Cluster-Tree路由算法可以根據(jù)鄰居表有效的優(yōu)化路由，同時(shí)降低網(wǎng)絡(luò)整體能量消耗，特別是ZC的能量消耗，最終提高網(wǎng)絡(luò)的效率，延長(zhǎng)網(wǎng)絡(luò)的存活時(shí)間。

[1] 賀玲玲.Z igBee傳感網(wǎng)絡(luò)Cluster-T ree改進(jìn)路由算法研究[J].傳感技術(shù)學(xué)報(bào),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] 班艷麗,柴喬林,王芳.改進(jìn)的ZigBee 網(wǎng)絡(luò)路由算法[J].計(jì)算機(jī)工程與應(yīng)用, 2009,45(5):95-97,116.

[7] 朱向慶,王建明.Z igBee協(xié)議網(wǎng)絡(luò)層的研究與實(shí)現(xiàn)[J].電子技術(shù)應(yīng)用,2006,32(1):137-140.

[8] 孫利民,李建中,陳渝,等.無線傳感器網(wǎng)絡(luò)[M].北京:清華大學(xué)出版社, 2005.