基于鄰居表的能量均衡ZigBee樹路由改進算法

白樂強，王玉濤，孫晶晶

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

0 引 言

根據在網絡中功能的不同，可以將ZigBee［1］節點分為全功能設備和精簡功能設備兩種類型［2］。協調器與路由器為FFD 設備，終端節點為RFD 設備。根據網絡結構的不同，ZigBee一般分為樹路由和AODVjr（Ad－hoc on－demand distance vector junior）兩種路由算法。樹路由是ZigBee協議中定義的最基本的路由方式，該算法只依靠相關節點的父、子節點進行路徑選擇，相對簡單、無需維護路由表，節省網絡的存儲資源［3］，但該算法往往產生較大路徑成本。Cluster－Tree［4］與AODVjr相結合的改進算法［5］能選出路由跳數較少的路徑，有效減少網絡總體能量消耗，但該算法只將路由跳數作為節點路由代價的評判標準，沒有考慮節點剩余能量。基于能量感知與能量均衡的路由算法［6］根據節點的剩余能量，選擇路徑損耗小、能量消耗低的節點作為下一跳轉發節點，有效降低了網絡總體能耗，但該算法沒有考慮所選路徑的跳數問題。

針對源節點到目的節點的路由跳數多以及節點能量負載不均衡問題，提出一種基于鄰居表的能量均衡ZigBee網絡樹路由改進算法 （EBZTR）。

1 ZigBee網絡樹路由算法

1.1 ZigBee網絡地址分配機制

ZigBee網絡采用分布式地址分配機制，為每個網絡設備分配唯一的網絡地址。其中Cm為最大子節點數，Rm為子節點中最大路由節點數，Lm為網絡最大深度［1］，Cskip（d）表示網絡深度為d 的路由節點所能分配的地址偏移量，如式 （1）所示

若父節點地址為Aparent，那么分給它的第n個路由子節點地址An應滿足式 （2）

分給它的第m 個終端節點地址Am滿足式 （3）

1.2 ZigBee網絡樹路由尋址方式

樹路由算法完全依賴樹型結構轉發數據。若一個網絡地址為An、網絡深度為d 的FFD 節點向目的地址為D 的節點發送數據包，樹路由算法先判斷目的節點是否為該節點的后代節點。若目的節點D 是節點An的后代節點，將數據包轉發到相應節點上［7］。

判斷目的節點D 為節點An后代節點的充要條件是

An＜D ＜An＋Cskip（d－1） （4）

在滿足式 （4）的前提下，節點An會根據式 （5）計算下一跳節點地址N

若目的節點D 不滿足式 （4），則將數據包轉發給節點An的父節點。

在ZigBee樹路由算法中，根據地址分配機制可得到源節點和目的節點最大深度的公共父輩節點，用LCA（S，D）表示。S、D 分別代表源節點、目的節點，用level（u）表示節點u的深度，用R（u）表示節點u 到目的節點的樹路由跳數。那么源節點到目的節點的樹路由跳數［8］如式 （6）所示

2 鄰居表

設網絡中每個設備類型為FFD 的節點都會存儲一個相應的鄰居表，當前節點A 共有P個鄰居節點，Ap表示節點A 的第p 個鄰居節點地址且1≤p≤P，則節點A 的鄰居表信息結構如圖1所示。

圖1 鄰居表信息結構

（1）NodeTypeAp：NodeTypeAp為節點Ap的節點設備類型，NodeTypeAp＝0 表示節點設備類型為RFD，Node－TypeAp＝1表示節點設備類型為FFD。

（2）NpowerAp：NpowerAp為節點Ap剩余能量。

（3）CountAp：CountAp為節點Ap作為路由節點的次數。

（4）RoutingCostAp：RoutingCostAp為節點Ap路由 代價，路由代價越大表示節點轉發數據包的損耗越大。

若節點Ap的節點類型為RFD 時，由于RFD 節點不具有路由功能，則此時RoutingCostAp的值為無限大；否則RoutingCostAp（q）計 算 如 式 （7）［9］所 示，其 中 節 點Ap（q）為NodeTypeAp＝1對應的節點，節點A 共有Q 個此類鄰居節點且Q≤P、1≤q≤Q，RoutingCostAp（q）為 節 點Ap（q）路由代價

式中：CountAp（q）——節 點Ap（q）作 為 路 由 節 點 次 數；SunsAp（q）——節點Ap（q）具有的子孫節點個數；DepthAp（q）——節點Ap（q）網絡深度；NpowerAp（q）——節點Ap（q）剩余能量。

3 EBZTR算法設計

算法綜合考慮節點剩余能量，在節點類型為FFD 的當前節點的鄰居節點中，選取剩余能量充足且到目的節點樹路由跳數最少的鄰居節點作為下一跳轉發節點，避免利用剩余能量偏低的節點轉發數據包。該算法通過設定節點能量閾值，將網絡中的節點分為剩余能量充足區的節點集合和剩余能量偏低區的節點集合。其中算法中的能量閥值用Cwarning表示，Cwarning的計算如式 （8）所示

式 （8）中 的Ap（q（k））為 當 前 節 點A 的 第k 個 滿 足TRC（Ap（q），D）≤TRC（A，D）－1對應的鄰居節點地址，其中節點A 共有K 個此類鄰居節點，TRC（A，D）為節點A 到達目的節點D 的樹路由跳數，TRC（Ap（q），D）為節點Ap（q）到達目的節點D 的樹路由跳數；NpowerAp（q（k））為節點Ap（q（k））剩余能量；RoutingCostAp（q（k））為節點Ap（q（k））路由代價。

處于剩余能量充足區的節點集合：該節點集合中所有節點的剩余能量值均大于Cwarning，參與下一跳轉發節點的選擇過程。

處于剩余能量偏低區的節點集合：該節點集合中所有節點的剩余能量值均小于Cwarning，不參與下一跳轉發節點的選擇過程。

EBZTR 算法中相關參數的定義，見表1。

EBZTR 算法在選取下一跳轉發節點過程中，當存在多個剩余能量充足且到達目的節點樹路由跳數最少的鄰居節點時，選取節點轉發優先級最大的鄰居節點作為下一跳轉發 節 點，其 中 用ForwardingLevelAp（q（k（t（w））））表 示 節 點Ap（q（k（t（w））））的轉發 優 先 級。ForwardingLevelAp（q（k（t（w））））的 計算如式 （9）所示

表1 EBZTR 算法相關參數定義

RoutingCostAp（q（k（t（w））））表 示 節 點Ap（q（k（t（w））））的 路 由 代價。根 據 式 （9）可 知：TRC（Ap（q（k（t（w）））），D）值 越 小 則ForwardingLevelAp（q（k（t（w））））值 越 大；RoutingCostAp（q（k（t（w））））的值越大則ForwardingLevelAp（q（k（t（w））））值越小。

通過計算集合F中所有節點到達目的節點的樹路由跳數及TRC（A，D），構成滿足TRC（Ap（q），D）≤TRC （A，D）－1對應的鄰居節點集合G，根據樹形拓撲結構的特點，所選的路由路徑一定存在。節點A 確認節點集合G 中所有鄰居節點的剩余能量值，根據節點集合G 中所有鄰居節點的剩余能量值計算Cwarning值的大小，判斷集合G 中節點的能量狀態。構成滿足剩余能量充足區的節點集合H，在節點集合H 中，構成到達目的節點樹路由跳數最少的節點集合L，利用式 （9）計算節點集合L 中所有節點的轉發優先級，選取轉發優先級最大的節點作為下一跳轉發節點，其中節點A 轉發一次數據包，其CountA值加1。

EBZTR 算法具體步驟如下：

步驟1 判斷節點A 是否為目的節點。

若是則算法結束；否則轉向步驟2。

步驟2 判斷節點A 設備類型是否為RFD。

若是則發送數據包給父節點Aparent，算法結束；否則轉向步驟3。

步驟3 判斷節點A 的一跳鄰居節點是否存在目的節點。

若存在則發送數據包給該鄰居節點，算法結束；否則轉向步驟4。

步驟4 在節點集合E 中，構成NodeTypeAp＝1對應的節點集合F。

步驟5 利用式 （6）分別計算節點集合F中鄰居節點的TRC（Ap（q），D）及TRC（A，D），構成TRC（Ap（q），D）≤TRC（A，D）－1對應的鄰居節點集合G。

步驟6 在節點集合G 中，計算Cwarning值，根據Cwarning值構成滿足剩余能量充足的節點集合H。

步驟7 在 節 點 集 合H 中，構 成min TRC（Ap（q（k（t））），D）對應的節點集合L。

步驟8 在節點集合L 中，利用式 （9）計算節點Ap（q（k（t（w））））的ForwardingLevelAp（q（k（t（w）））），發 送 數 據 包 給ForwardingLevelAp（q（k（t（w））））最大的節點，算法結束。

重復上述步驟，直至數據包到達目的節點為止。

4 EBZTR算法理論分析

為證明EBZTR 算法的可行性，對EBZTR 算法的時間復雜度與利用該算法選取的路徑進行分析。

性質1 EBZTR 算法的時間復雜度為O（P），其中P為當前節點的鄰居節點個數。

證明：算法開始，第一步與第二步，每一步均計算1次。第三步判斷P個鄰居節點是否為目的節點，計算P次。第四步判斷P個鄰居節點是否為FFD 節點，計算P次。第五步計算集合F中每個節點到目的節點樹路由跳數，每個節點最多計算Lm次，有Q 個節點，共計算Lm×Q 次。第六步判斷集合G 中K 個節點的能量狀態，計算K 次。第七步找出集合H 中T 個節點到達目的節點樹路由跳數最少的節點，計算T 次。第八步計算集合L中W 個節點的轉發優先級，計算W 次。其中P≥Q≥K≥T≥W，所以EBZTR算法的計算次數為1＋1＋P＋P＋Lm×Q＋K＋T＋W＜ （7＋Lm）×P，即EBZTR算法的時間復雜度為O （P）。

性質2 EBZTR 算法選取的路徑是初級通路。

證明：為了證明EBZTR 算法具有該性質，只需證明數據包在傳遞過程中到目的節點的樹路由跳數不斷減少。把當前節點與前一跳節點的關系分成父子關系與非父子關系兩種。設ti表示第i 個轉發節點與前一跳節點具有父子關系，稱為樹節點，ni表示第i 個轉發節點與前一跳節點具有非父子關系，稱為非樹節點。

按照樹路由算法，路徑可表示為 （S，t1，t2，ti，…tj，D），路由跳數為j＋1，j≥i≥0。隨著數據傳遞，路由跳數逐跳減少，如式 （10）所示

利用EBZTR 算法會出現4種情況：

（1）樹節點到樹節點

根據式 （10），R（ti）＜R（ti－1）。

（2）樹節點到非樹節點

根據EBZTR 算法的描述，R（ni）＜R（ti），R（ti）＜R（ti－1），所以R（ni）＜R（ti－1）。

（3）非樹節點到樹節點

若ti＋1是ni的父節點，level（ti＋1）＝level（ni）－1；

若ti＋1是ni的子節點，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）非樹節點到非樹節點

根據以上3種情況，R（ni＋1）＜R（ti＋1）＜R（ni）。

所以，EBZTR 算法找到的路徑中任何一個轉發節點到目的節點的樹路由跳數都小于上一跳節點到目的節點的樹路由跳數，數據包傳遞過程中到目的節點的樹路由跳數不斷減少。所以EBZTR 算法選取的路徑沒有重復節點，是一條初級通路。

5 仿真結果與分析

為驗證EBZTR 算法的性能，采用MATLAB平臺針對網絡整體能耗、死亡節點個數以及數據包發送成功率三方面進行實驗仿真，并與樹路由算法、文獻 ［5］中的算法和文獻 ［6］中的改進算法進行對比。實驗仿真參數：Cm＝6、Rm＝6、Lm＝4，利用式 （1）、式 （2）和式 （3）搭建一個網絡范圍為200m×200 m、節點個數為100、最大傳輸距離為40m 的ZigBee網絡，節點的初始能量設置為1000J，判定節點死亡能量為50J，數據包長度為80bytes、數據流類型為CBR、發送數據包的速率為50包／s以及仿真時間設為300s，其中ZigBee網絡節點的初始能量和判定節點是否死亡的能量是根據現有大多數ZigBee路由算法的取值選取的。實驗中每種場景的仿真數據均是獨立運行100次后求取的平均值。

如圖2所示，隨著時間的不斷推移，網絡總體能量消耗逐漸增多，EBZTR 算法總體能量消耗少于樹路由算法、文獻 ［5］中的算法以及文獻 ［6］中的改進算法。網絡中節點能量消耗＝節點初始能量－節點剩余能量［10］。由于EBZTR 算法在路徑選擇過程中綜合考慮剩余能量與路徑成本，盡量選擇具有能量充足、路徑成本低的路徑進行傳輸數據，從而節省了網絡的整體能耗。

圖2 網絡總體能量消耗

如圖3所示，EBZTR 算法出現死亡節點的個數少于樹路由算法、文獻 ［5］以及文獻 ［6］中的改進算法。初始階段，網絡中沒有出現節點死亡的現象，隨著時間的不斷推移，死亡節點個數不斷增多。由于EBZTR 算法避免利用剩余能量偏低的節點轉發數據包，能有效均衡網絡的負載，從而延長網絡的整體壽命。

圖3 網絡死亡節點個數

如圖4所示，隨著時間的不斷推移，EBZTR 算法中的數據包從源節點成功到達目的節點的比例高于樹路由算法、文獻 ［5］中的算法以及文獻 ［6］中的改進算法。網絡中死亡節點數目的大小直接影響數據包發送成功率的高低，網絡中死亡節點數目越多，丟失數據包的現象就越多。EBZTR 算法借助一跳鄰居表，綜合考慮節點剩余能量與路由代價，有效減少網絡死亡節點個數，進而達到數據包發送成功率提高的目的。

圖4 數據包發送成功率

6 結束語

針對現有能量均衡ZigBee網絡樹路由改進算法的不足，提出一種基于鄰居表的能量均衡ZigBee網絡樹路由改進算法。該算法借助一跳鄰居表，選取能量充足且到達目的節點樹路由跳數最少的節點集合，當存在多個鄰居節點能量充足且到達目的節點樹路由跳數相同時，選取轉發優先級最大的節點作為下一跳轉發節點。理論分析結果表明，該算法具有較低的時間復雜度，可以找到一條初級通路。仿真結果表明，該算法有效減少網絡整體能量消耗，避開剩余能量偏低的節點轉發數據包，推遲死亡節點出現的時間，延長ZigBee網絡使用壽命。

［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 協議的Zig－Bee網絡低能耗按需多路由設計 ［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網絡樹路由改進算法 ［J］.吉林大學學報 （工學版），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）.［徐沛成，胡國榮.改進的Zig－Bee網絡路由算法 ［J］.計算機工程與設計，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）. ［何學文，王強，張振利.基于能量感知與能量均衡的ZigBee網絡樹路由算法研究［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技術的建筑能耗監測系統設計［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路由算法優化［J］.計算機工程與設計，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.