鄒國霞,李 燕
(桂林航天工業(yè)高等??茖W(xué)校,桂林 541004)
無線傳感器網(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ò)的壽命。
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è)備。
加入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路由算法及兩者混合模式的路由算法。
在該算法中,節(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é)點。
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)圖
如果兩節(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步,具體方法如下:
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所示。
仿真工具采用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中紅色表示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路由算法。
圖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é)約了整體能量。
針對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.