基于鄰居表的能量均衡ZigBee樹路由改進(jìn)算法

白樂強(qiáng)，王玉濤，孫晶晶

（沈陽建筑大學(xué) 信息與控制工程學(xué)院，遼寧 沈陽110168）

0 引 言

根據(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）。

1 ZigBee網(wǎng)絡(luò)樹路由算法

1.1 ZigBee網(wǎng)絡(luò)地址分配機(jī)制

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）

1.2 ZigBee網(wǎng)絡(luò)樹路由尋址方式

樹路由算法完全依賴樹型結(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）所示

2 鄰居表

設(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）剩余能量。

3 EBZTR算法設(shè)計

算法綜合考慮節(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é)點為止。

4 EBZTR算法理論分析

為證明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é)點，是一條初級通路。

5 仿真結(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ā)送成功率

6 結(jié)束語

針對現(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.