白樂強(qiáng),王玉濤,孫晶晶
(沈陽建筑大學(xué) 信息與控制工程學(xué)院,遼寧 沈陽110168)
根據(jù)在網(wǎng)絡(luò)中功能的不同,可以將ZigBee[1]節(jié)點分為全功能設(shè)備和精簡功能設(shè)備兩種類型[2]。協(xié)調(diào)器與路由器為FFD 設(shè)備,終端節(jié)點為RFD 設(shè)備。根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的不同,ZigBee一般分為樹路由和AODVjr(Ad-h(huán)oc on-demand distance vector junior)兩種路由算法。樹路由是ZigBee協(xié)議中定義的最基本的路由方式,該算法只依靠相關(guān)節(jié)點的父、子節(jié)點進(jìn)行路徑選擇,相對簡單、無需維護(hù)路由表,節(jié)省網(wǎng)絡(luò)的存儲資源[3],但該算法往往產(chǎn)生較大路徑成本。Cluster-Tree[4]與AODVjr相結(jié)合的改進(jìn)算法[5]能選出路由跳數(shù)較少的路徑,有效減少網(wǎng)絡(luò)總體能量消耗,但該算法只將路由跳數(shù)作為節(jié)點路由代價的評判標(biāo)準(zhǔn),沒有考慮節(jié)點剩余能量?;谀芰扛兄c能量均衡的路由算法[6]根據(jù)節(jié)點的剩余能量,選擇路徑損耗小、能量消耗低的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點,有效降低了網(wǎng)絡(luò)總體能耗,但該算法沒有考慮所選路徑的跳數(shù)問題。
針對源節(jié)點到目的節(jié)點的路由跳數(shù)多以及節(jié)點能量負(fù)載不均衡問題,提出一種基于鄰居表的能量均衡ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法 (EBZTR)。
ZigBee網(wǎng)絡(luò)采用分布式地址分配機(jī)制,為每個網(wǎng)絡(luò)設(shè)備分配唯一的網(wǎng)絡(luò)地址。其中Cm為最大子節(jié)點數(shù),Rm為子節(jié)點中最大路由節(jié)點數(shù),Lm為網(wǎng)絡(luò)最大深度[1],Cskip(d)表示網(wǎng)絡(luò)深度為d 的路由節(jié)點所能分配的地址偏移量,如式 (1)所示
若父節(jié)點地址為Aparent,那么分給它的第n個路由子節(jié)點地址An應(yīng)滿足式 (2)
分給它的第m 個終端節(jié)點地址Am滿足式 (3)
樹路由算法完全依賴樹型結(jié)構(gòu)轉(zhuǎn)發(fā)數(shù)據(jù)。若一個網(wǎng)絡(luò)地址為An、網(wǎng)絡(luò)深度為d 的FFD 節(jié)點向目的地址為D 的節(jié)點發(fā)送數(shù)據(jù)包,樹路由算法先判斷目的節(jié)點是否為該節(jié)點的后代節(jié)點。若目的節(jié)點D 是節(jié)點An的后代節(jié)點,將數(shù)據(jù)包轉(zhuǎn)發(fā)到相應(yīng)節(jié)點上[7]。
判斷目的節(jié)點D 為節(jié)點An后代節(jié)點的充要條件是
An<D <An+Cskip(d-1) (4)
在滿足式 (4)的前提下,節(jié)點An會根據(jù)式 (5)計算下一跳節(jié)點地址N
若目的節(jié)點D 不滿足式 (4),則將數(shù)據(jù)包轉(zhuǎn)發(fā)給節(jié)點An的父節(jié)點。
在ZigBee樹路由算法中,根據(jù)地址分配機(jī)制可得到源節(jié)點和目的節(jié)點最大深度的公共父輩節(jié)點,用LCA(S,D)表示。S、D 分別代表源節(jié)點、目的節(jié)點,用level(u)表示節(jié)點u的深度,用R(u)表示節(jié)點u 到目的節(jié)點的樹路由跳數(shù)。那么源節(jié)點到目的節(jié)點的樹路由跳數(shù)[8]如式 (6)所示
設(shè)網(wǎng)絡(luò)中每個設(shè)備類型為FFD 的節(jié)點都會存儲一個相應(yīng)的鄰居表,當(dāng)前節(jié)點A 共有P個鄰居節(jié)點,Ap表示節(jié)點A 的第p 個鄰居節(jié)點地址且1≤p≤P,則節(jié)點A 的鄰居表信息結(jié)構(gòu)如圖1所示。
圖1 鄰居表信息結(jié)構(gòu)
(1)NodeTypeAp:NodeTypeAp為節(jié)點Ap的節(jié)點設(shè)備類型,NodeTypeAp=0 表示節(jié)點設(shè)備類型為RFD,Node-TypeAp=1表示節(jié)點設(shè)備類型為FFD。
(2)NpowerAp:NpowerAp為節(jié)點Ap剩余能量。
(3)CountAp:CountAp為節(jié)點Ap作為路由節(jié)點的次數(shù)。
(4)RoutingCostAp:RoutingCostAp為節(jié)點Ap路由 代價,路由代價越大表示節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包的損耗越大。
若節(jié)點Ap的節(jié)點類型為RFD 時,由于RFD 節(jié)點不具有路由功能,則此時RoutingCostAp的值為無限大;否則RoutingCostAp(q)計 算 如 式 (7)[9]所 示,其 中 節(jié) 點Ap(q)為NodeTypeAp=1對應(yīng)的節(jié)點,節(jié)點A 共有Q 個此類鄰居節(jié)點且Q≤P、1≤q≤Q,RoutingCostAp(q)為 節(jié) 點Ap(q)路由代價
式中:CountAp(q)——節(jié) 點Ap(q)作 為 路 由 節(jié) 點 次 數(shù);SunsAp(q)——節(jié)點Ap(q)具有的子孫節(jié)點個數(shù);DepthAp(q)——節(jié)點Ap(q)網(wǎng)絡(luò)深度;NpowerAp(q)——節(jié)點Ap(q)剩余能量。
算法綜合考慮節(jié)點剩余能量,在節(jié)點類型為FFD 的當(dāng)前節(jié)點的鄰居節(jié)點中,選取剩余能量充足且到目的節(jié)點樹路由跳數(shù)最少的鄰居節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點,避免利用剩余能量偏低的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包。該算法通過設(shè)定節(jié)點能量閾值,將網(wǎng)絡(luò)中的節(jié)點分為剩余能量充足區(qū)的節(jié)點集合和剩余能量偏低區(qū)的節(jié)點集合。其中算法中的能量閥值用Cwarning表示,Cwarning的計算如式 (8)所示
式 (8)中 的Ap(q(k))為 當(dāng) 前 節(jié) 點A 的 第k 個 滿 足TRC(Ap(q),D)≤TRC(A,D)-1對應(yīng)的鄰居節(jié)點地址,其中節(jié)點A 共有K 個此類鄰居節(jié)點,TRC(A,D)為節(jié)點A 到達(dá)目的節(jié)點D 的樹路由跳數(shù),TRC(Ap(q),D)為節(jié)點Ap(q)到達(dá)目的節(jié)點D 的樹路由跳數(shù);NpowerAp(q(k))為節(jié)點Ap(q(k))剩余能量;RoutingCostAp(q(k))為節(jié)點Ap(q(k))路由代價。
處于剩余能量充足區(qū)的節(jié)點集合:該節(jié)點集合中所有節(jié)點的剩余能量值均大于Cwarning,參與下一跳轉(zhuǎn)發(fā)節(jié)點的選擇過程。
處于剩余能量偏低區(qū)的節(jié)點集合:該節(jié)點集合中所有節(jié)點的剩余能量值均小于Cwarning,不參與下一跳轉(zhuǎn)發(fā)節(jié)點的選擇過程。
EBZTR 算法中相關(guān)參數(shù)的定義,見表1。
EBZTR 算法在選取下一跳轉(zhuǎn)發(fā)節(jié)點過程中,當(dāng)存在多個剩余能量充足且到達(dá)目的節(jié)點樹路由跳數(shù)最少的鄰居節(jié)點時,選取節(jié)點轉(zhuǎn)發(fā)優(yōu)先級最大的鄰居節(jié)點作為下一跳轉(zhuǎn)發(fā) 節(jié) 點,其 中 用ForwardingLevelAp(q(k(t(w))))表 示 節(jié) 點Ap(q(k(t(w))))的轉(zhuǎn)發(fā) 優(yōu) 先 級。ForwardingLevelAp(q(k(t(w))))的 計算如式 (9)所示
表1 EBZTR 算法相關(guān)參數(shù)定義
RoutingCostAp(q(k(t(w))))表 示 節(jié) 點Ap(q(k(t(w))))的 路 由 代價。根 據(jù) 式 (9)可 知:TRC(Ap(q(k(t(w)))),D)值 越 小 則ForwardingLevelAp(q(k(t(w))))值 越 大;RoutingCostAp(q(k(t(w))))的值越大則ForwardingLevelAp(q(k(t(w))))值越小。
通過計算集合F中所有節(jié)點到達(dá)目的節(jié)點的樹路由跳數(shù)及TRC(A,D),構(gòu)成滿足TRC(Ap(q),D)≤TRC (A,D)-1對應(yīng)的鄰居節(jié)點集合G,根據(jù)樹形拓?fù)浣Y(jié)構(gòu)的特點,所選的路由路徑一定存在。節(jié)點A 確認(rèn)節(jié)點集合G 中所有鄰居節(jié)點的剩余能量值,根據(jù)節(jié)點集合G 中所有鄰居節(jié)點的剩余能量值計算Cwarning值的大小,判斷集合G 中節(jié)點的能量狀態(tài)。構(gòu)成滿足剩余能量充足區(qū)的節(jié)點集合H,在節(jié)點集合H 中,構(gòu)成到達(dá)目的節(jié)點樹路由跳數(shù)最少的節(jié)點集合L,利用式 (9)計算節(jié)點集合L 中所有節(jié)點的轉(zhuǎn)發(fā)優(yōu)先級,選取轉(zhuǎn)發(fā)優(yōu)先級最大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點,其中節(jié)點A 轉(zhuǎn)發(fā)一次數(shù)據(jù)包,其CountA值加1。
EBZTR 算法具體步驟如下:
步驟1 判斷節(jié)點A 是否為目的節(jié)點。
若是則算法結(jié)束;否則轉(zhuǎn)向步驟2。
步驟2 判斷節(jié)點A 設(shè)備類型是否為RFD。
若是則發(fā)送數(shù)據(jù)包給父節(jié)點Aparent,算法結(jié)束;否則轉(zhuǎn)向步驟3。
步驟3 判斷節(jié)點A 的一跳鄰居節(jié)點是否存在目的節(jié)點。
若存在則發(fā)送數(shù)據(jù)包給該鄰居節(jié)點,算法結(jié)束;否則轉(zhuǎn)向步驟4。
步驟4 在節(jié)點集合E 中,構(gòu)成NodeTypeAp=1對應(yīng)的節(jié)點集合F。
步驟5 利用式 (6)分別計算節(jié)點集合F中鄰居節(jié)點的TRC(Ap(q),D)及TRC(A,D),構(gòu)成TRC(Ap(q),D)≤TRC(A,D)-1對應(yīng)的鄰居節(jié)點集合G。
步驟6 在節(jié)點集合G 中,計算Cwarning值,根據(jù)Cwarning值構(gòu)成滿足剩余能量充足的節(jié)點集合H。
步驟7 在 節(jié) 點 集 合H 中,構(gòu) 成min TRC(Ap(q(k(t))),D)對應(yīng)的節(jié)點集合L。
步驟8 在節(jié)點集合L 中,利用式 (9)計算節(jié)點Ap(q(k(t(w))))的ForwardingLevelAp(q(k(t(w)))),發(fā) 送 數(shù) 據(jù) 包 給ForwardingLevelAp(q(k(t(w))))最大的節(jié)點,算法結(jié)束。
重復(fù)上述步驟,直至數(shù)據(jù)包到達(dá)目的節(jié)點為止。
為證明EBZTR 算法的可行性,對EBZTR 算法的時間復(fù)雜度與利用該算法選取的路徑進(jìn)行分析。
性質(zhì)1 EBZTR 算法的時間復(fù)雜度為O(P),其中P為當(dāng)前節(jié)點的鄰居節(jié)點個數(shù)。
證明:算法開始,第一步與第二步,每一步均計算1次。第三步判斷P個鄰居節(jié)點是否為目的節(jié)點,計算P次。第四步判斷P個鄰居節(jié)點是否為FFD 節(jié)點,計算P次。第五步計算集合F中每個節(jié)點到目的節(jié)點樹路由跳數(shù),每個節(jié)點最多計算Lm次,有Q 個節(jié)點,共計算Lm×Q 次。第六步判斷集合G 中K 個節(jié)點的能量狀態(tài),計算K 次。第七步找出集合H 中T 個節(jié)點到達(dá)目的節(jié)點樹路由跳數(shù)最少的節(jié)點,計算T 次。第八步計算集合L中W 個節(jié)點的轉(zhuǎn)發(fā)優(yōu)先級,計算W 次。其中P≥Q≥K≥T≥W,所以EBZTR算法的計算次數(shù)為1+1+P+P+Lm×Q+K+T+W< (7+Lm)×P,即EBZTR算法的時間復(fù)雜度為O (P)。
性質(zhì)2 EBZTR 算法選取的路徑是初級通路。
證明:為了證明EBZTR 算法具有該性質(zhì),只需證明數(shù)據(jù)包在傳遞過程中到目的節(jié)點的樹路由跳數(shù)不斷減少。把當(dāng)前節(jié)點與前一跳節(jié)點的關(guān)系分成父子關(guān)系與非父子關(guān)系兩種。設(shè)ti表示第i 個轉(zhuǎn)發(fā)節(jié)點與前一跳節(jié)點具有父子關(guān)系,稱為樹節(jié)點,ni表示第i 個轉(zhuǎn)發(fā)節(jié)點與前一跳節(jié)點具有非父子關(guān)系,稱為非樹節(jié)點。
按照樹路由算法,路徑可表示為 (S,t1,t2,ti,…tj,D),路由跳數(shù)為j+1,j≥i≥0。隨著數(shù)據(jù)傳遞,路由跳數(shù)逐跳減少,如式 (10)所示
利用EBZTR 算法會出現(xiàn)4種情況:
(1)樹節(jié)點到樹節(jié)點
根據(jù)式 (10),R(ti)<R(ti-1)。
(2)樹節(jié)點到非樹節(jié)點
根據(jù)EBZTR 算法的描述,R(ni)<R(ti),R(ti)<R(ti-1),所以R(ni)<R(ti-1)。
(3)非樹節(jié)點到樹節(jié)點
若ti+1是ni的父節(jié)點,level(ti+1)=level(ni)-1;
若ti+1是ni的子節(jié)點,level(ti+1)=level(ni)+1 且level(LCA(ti+1,D))=level(LCA(ni,D))+1。
所以R(ti+1)=level(ti+1)+level(D)-2×level(LCA(ti+1,D))<R(ni)。
(4)非樹節(jié)點到非樹節(jié)點
根據(jù)以上3種情況,R(ni+1)<R(ti+1)<R(ni)。
所以,EBZTR 算法找到的路徑中任何一個轉(zhuǎn)發(fā)節(jié)點到目的節(jié)點的樹路由跳數(shù)都小于上一跳節(jié)點到目的節(jié)點的樹路由跳數(shù),數(shù)據(jù)包傳遞過程中到目的節(jié)點的樹路由跳數(shù)不斷減少。所以EBZTR 算法選取的路徑?jīng)]有重復(fù)節(jié)點,是一條初級通路。
為驗證EBZTR 算法的性能,采用MATLAB平臺針對網(wǎng)絡(luò)整體能耗、死亡節(jié)點個數(shù)以及數(shù)據(jù)包發(fā)送成功率三方面進(jìn)行實驗仿真,并與樹路由算法、文獻(xiàn) [5]中的算法和文獻(xiàn) [6]中的改進(jìn)算法進(jìn)行對比。實驗仿真參數(shù):Cm=6、Rm=6、Lm=4,利用式 (1)、式 (2)和式 (3)搭建一個網(wǎng)絡(luò)范圍為200m×200 m、節(jié)點個數(shù)為100、最大傳輸距離為40m 的ZigBee網(wǎng)絡(luò),節(jié)點的初始能量設(shè)置為1000J,判定節(jié)點死亡能量為50J,數(shù)據(jù)包長度為80bytes、數(shù)據(jù)流類型為CBR、發(fā)送數(shù)據(jù)包的速率為50包/s以及仿真時間設(shè)為300s,其中ZigBee網(wǎng)絡(luò)節(jié)點的初始能量和判定節(jié)點是否死亡的能量是根據(jù)現(xiàn)有大多數(shù)ZigBee路由算法的取值選取的。實驗中每種場景的仿真數(shù)據(jù)均是獨(dú)立運(yùn)行100次后求取的平均值。
如圖2所示,隨著時間的不斷推移,網(wǎng)絡(luò)總體能量消耗逐漸增多,EBZTR 算法總體能量消耗少于樹路由算法、文獻(xiàn) [5]中的算法以及文獻(xiàn) [6]中的改進(jìn)算法。網(wǎng)絡(luò)中節(jié)點能量消耗=節(jié)點初始能量-節(jié)點剩余能量[10]。由于EBZTR 算法在路徑選擇過程中綜合考慮剩余能量與路徑成本,盡量選擇具有能量充足、路徑成本低的路徑進(jìn)行傳輸數(shù)據(jù),從而節(jié)省了網(wǎng)絡(luò)的整體能耗。
圖2 網(wǎng)絡(luò)總體能量消耗
如圖3所示,EBZTR 算法出現(xiàn)死亡節(jié)點的個數(shù)少于樹路由算法、文獻(xiàn) [5]以及文獻(xiàn) [6]中的改進(jìn)算法。初始階段,網(wǎng)絡(luò)中沒有出現(xiàn)節(jié)點死亡的現(xiàn)象,隨著時間的不斷推移,死亡節(jié)點個數(shù)不斷增多。由于EBZTR 算法避免利用剩余能量偏低的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包,能有效均衡網(wǎng)絡(luò)的負(fù)載,從而延長網(wǎng)絡(luò)的整體壽命。
圖3 網(wǎng)絡(luò)死亡節(jié)點個數(shù)
如圖4所示,隨著時間的不斷推移,EBZTR 算法中的數(shù)據(jù)包從源節(jié)點成功到達(dá)目的節(jié)點的比例高于樹路由算法、文獻(xiàn) [5]中的算法以及文獻(xiàn) [6]中的改進(jìn)算法。網(wǎng)絡(luò)中死亡節(jié)點數(shù)目的大小直接影響數(shù)據(jù)包發(fā)送成功率的高低,網(wǎng)絡(luò)中死亡節(jié)點數(shù)目越多,丟失數(shù)據(jù)包的現(xiàn)象就越多。EBZTR 算法借助一跳鄰居表,綜合考慮節(jié)點剩余能量與路由代價,有效減少網(wǎng)絡(luò)死亡節(jié)點個數(shù),進(jìn)而達(dá)到數(shù)據(jù)包發(fā)送成功率提高的目的。
圖4 數(shù)據(jù)包發(fā)送成功率
針對現(xiàn)有能量均衡ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法的不足,提出一種基于鄰居表的能量均衡ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法。該算法借助一跳鄰居表,選取能量充足且到達(dá)目的節(jié)點樹路由跳數(shù)最少的節(jié)點集合,當(dāng)存在多個鄰居節(jié)點能量充足且到達(dá)目的節(jié)點樹路由跳數(shù)相同時,選取轉(zhuǎn)發(fā)優(yōu)先級最大的節(jié)點作為下一跳轉(zhuǎn)發(fā)節(jié)點。理論分析結(jié)果表明,該算法具有較低的時間復(fù)雜度,可以找到一條初級通路。仿真結(jié)果表明,該算法有效減少網(wǎng)絡(luò)整體能量消耗,避開剩余能量偏低的節(jié)點轉(zhuǎn)發(fā)數(shù)據(jù)包,推遲死亡節(jié)點出現(xiàn)的時間,延長ZigBee網(wǎng)絡(luò)使用壽命。
[1]ZigBee Alliance.ZigBee specification [S].2008.
[2]WANG Xiaowei,ZHAO Xinhui.Design of low energy consumption routing protocol based on AODV in ZigBee network[J].Computer Measurement&Control,2013,21 (2):461-463 (in Chinese).[王小偉,趙新輝.基于AODV 協(xié)議的Zig-Bee網(wǎng)絡(luò)低能耗按需多路由設(shè)計 [J].計算機(jī)測量與控制,2013,21 (2):461-463.]
[3]LIU Dan,QIAN Zhihong,LIU Ying.Tree routing improvement algorithm in ZigBee network [J].Journal of Jilin University(Engineering and Technology Edition),2010,40 (5):1392-1396 (in Chinese).[劉丹,錢志鴻,劉影.ZigBee網(wǎng)絡(luò)樹路由改進(jìn)算法 [J].吉林大學(xué)學(xué)報 (工學(xué)版),2010,40(5):1392-1396.]
[4]Huang Yu-Kai,Pang Ai-Chun.Distributed throughput optimization for ZigBee cluster-tree networks[J].IEEE Transactions on Parallel and Distributed Systems,2012,23 (3):513-520.
[5]XU Peicheng,HU Guorong.Improved ZigBee network routing algorithm [J].Computer Engineering and Design,2013,34(9):3019-3023 (in Chinese).[徐沛成,胡國榮.改進(jìn)的Zig-Bee網(wǎng)絡(luò)路由算法 [J].計算機(jī)工程與設(shè)計,2013,34 (9):3019-3023.]
[6]HE Xuewen,WANG Qiang,ZHANG Zhenli.Research of ZigBee network tree routing algorithm based on energy awareness and energy balance [J].Industry and Mine Automation,2013,39 (10):44-47 (in Chinese). [何學(xué)文,王強(qiáng),張振利.基于能量感知與能量均衡的ZigBee網(wǎng)絡(luò)樹路由算法研究[J].工礦自動化,2013,39 (10):44-47.]
[7]GUO Xiangyong,LIU Hongli.Design of building energy consumption monitoring system based on ZigBee technology [J].Computer Measurement &Control,2011,19 (3):551-553 (in Chinese).[郭湘勇,劉宏立.基于ZigBee技術(shù)的建筑能耗監(jiān)測系統(tǒng)設(shè)計[J].計算機(jī)測量與控制,2011,19 (3):551-553.]
[8]Taehong Kim,Seong Hoon Kim,Jinyoung Yang,et al.Neighbor table based shortcut tree routing in ZigBee wireless networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,25 (3):706-716.
[9]LI Yudong,HUANG Hongguang,XIANG Xixi.Improved Zig-Bee routing algorithm based on energy balance[J].Computer Engineering and Design,2011,32 (2):397-400(in Chinese).[李予東,黃宏光,向西西.基于能量均衡的ZigBee路由算法優(yōu)化[J].計算機(jī)工程與設(shè)計,2011,32 (2):397-400.]
[10]Mostafa KA Al-Harbawi,Mohd Fadlee A Rasid,Nor Kamariah Noordin.Utilizing neighbours-table to improve tree routing [J].Wireless Personal Communications,2012,65:469-488.