鄒國霞，李 燕

（桂林航天工業(yè)高等?？茖W(xué)校，桂林 541004）

0 引言

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

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

1 ZigBee Cluster-tree路由算法

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

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

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

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

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

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

1.2 Cluster-tree路由算法

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

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

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

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

2 問題的提出

ZigBeeCluster-tree路由算法按Cluster-tree型結(jié)構(gòu)分層遍歷，算法簡單且查找目的節(jié)點的速度快，但是這種路由選擇不可能是最佳路由，而且ZC節(jié)點需要轉(zhuǎn)發(fā)大量的數(shù)據(jù)，必須儲備充足的能量，但是就目前的技術(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能量。如果考慮在無線信號覆蓋范圍內(nèi)，信號可以直接從源地發(fā)送到目的地，則rfd[12]發(fā)送數(shù)據(jù)給rfd[14]，需要2跳就能到達(dá)；rfd[12]發(fā)送數(shù)據(jù)給rfd[17]，需要2跳就能到達(dá)。

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

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

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

3.1 鄰居表定義

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

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

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

NbNode有三個域:

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

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

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

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

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

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

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

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

2）搜索鄰居表

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

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

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

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

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

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

具體流程如圖3所示。

4 算法的仿真和分析

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

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

4.1 節(jié)點能耗比較

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

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

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

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

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

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

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

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

5 結(jié)論

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

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

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

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