基于節點轉移的ZigBee網絡路由改進算法

李躍 黃希玲 賈海瑞

摘 要：ZigBee網絡的一個主要的目標就是降低網絡的耗能，以延長網絡的使用時間。但ZigBee協議中的網絡結構和路由算法并沒有完整的討論能量消耗問題。該文提出一種改進的分布式路由算法，該算法盡可能通過電源供電路由節點轉發數據，最終減少電池供電路由節點的能量消耗來延長網絡的生存時間。仿真結果表明，該算法只需少量的通訊開銷就可以明顯地減少電池供電路由節點的耗能。

關鍵詞：ZigBee協議 能耗有效 路由 算法

中圖分類號：TP393 文獻標識碼：A 文章編號：1674-098X（2015）02（b）-0013-03

Improved Algorithm of ZigBee Network Based on Node-Transporting

Li Yue1 Huang xiling1 Jia Hairui2

（1.City College of Southwest University of Science and Technology，Mianyang，621010，China；2.Sichuan airport consciousness Technology Co. Ltd.Chengdu，610000，China）

Abstract：One of the primary goals of ZigBee is low power consumption and therefore long-living networks.Current network formation and routing protocols described in the ZigBee specification do not completely discuss power consumption issues.Distributed routing algorithm to reduce power consumption of battery-powered devices by routing the communication through mains-powered devices is proposed.The proposed algorithm works in tree topologies supported by ZigBee and requires only minor modifications to the current specification. The simulation results showed that the algorithm is able to reduce the power consumption of battery-powered devices significantly with minimal communication overhead.

Key Words：ZigBee Standard； Energy Efficient； Routing；Algorithm

ZigBee技術是一種低成本、低功耗、低速率的基于IEEE 802.15.4無線標準有關組網、安全和應用軟件方面的短距離雙向無線通信技術，該技術主要針對低速率無線傳感器網絡和控制網絡而設計，能夠滿足小型化，低成本設備（如智能家居，工業控制和傳感器網絡等）的無線網絡要求，廣泛地應用于工業、建筑等無線通信應用場合[1]。

ZigBee協議中的網絡結構和路由算法并沒有完整的討論節點能量消耗問題[2]。文獻[3]討論了通過引入鄰居表，在選擇路由的時候考慮節點的剩余能量，盡量避開剩余能量較低的節點。文獻[4]分析了ZigBee傳感器網絡協議棧不同層的能量效率。文獻[5]提出了根據數據包的到達率，采用動態的信標間隔來增加節點的休眠時間以節約能量。文獻[6]提出了一種使用跨層費用計算函數構造樹路由的算法，該函數綜合考慮了剩余能量，信道質量和路由跳數。同樣在文獻[7]中提出在ZigBee網絡的路由發現階段，采用構造的函數來選擇能量滿足的路徑，延遲受限制的路徑。

但現有的文獻資料對在ZigBee無線網絡中電源供電設備和電池供電設備共存的情況沒有深入的研究，而有關大量ZigBee無線傳感器網絡的應用設計中，不同電源類型的設備可以共存，例如，智能家居、樓宇自動化以及工業控制等[1]，在這些應用中部分節點能夠使用外接持續電源。網絡中電池供電的節點設備和電源供電的節點設備可以共存，電源供電的節點設備能夠降低維修的費用，而電池供電的節點設備使用在不容易布線或布線代價較高的位置。該文深入研究了ZigBee網絡的組網技術及其路由算法，結合電源供電設備和電池供電設備的特點，構建了相應的算法模型，提出了一種基于ZigBee樹型網絡的電源感知路由算法（Power-Aware Routing Algorithm， PARA）。PARA算法基于簇樹型網絡拓撲，用來減少ZigBee網絡中電池供電節點的能量消耗，延長網絡運行時間。

1 算法模型構建與分析

由ZigBee網絡的樹路由算法可知，路由完全依賴父節點和子節點的關系。這樣在ZigBee網絡中就存在以下幾個問題：（1）即使目的節點在轉發節點的一跳通信范圍內，數據包也必須沿樹拓撲傳送到目的節點，而無法直接發送到目的節點[3]。（2）某些實用的網絡拓撲中，持續電源設備與電池供電設備共存，如果采用現有的樹路由算法，所有的路由都是單一的，這樣網絡中某些電池供電節點會過早耗盡電池的能量，縮短網絡的使用時間。

分析圖1構建的ZigBee簇樹混合電源節點網絡模型，圖中C是網絡的協調器節點，標號R1～R13的節點是FFD節點，RFD節點略去，電源供電的路由節點用實線表示，電池供電的路由節點用虛線表示。當路由節點R6與路由節點R3、R5通信時，其路由分別是R6 -R2-C-R3，R6 -R2-C-R1-R4-R5。以上路由中，需要電池供電結點R1、R2和R4轉發數據，使得電池供電節點消耗能量增加，網絡容易因個別電池供電節點能量的耗盡而中斷。

2 電源感知路由算法

2.1 算法思想

電源感知路由算法思想是盡可能的通過持續電源節點轉發數據，減少電池供電節點的數據轉發量。樹型網絡拓撲中，兩節點間只有一條路由通路，樹型網絡形成后，就沒有可選擇的路由來減少電池供電設備的數據轉發量[2]。一個可行的方案是依據流量的動態分布改變樹型網絡的拓撲結構，通過持續電源節點轉發數據，減少電池供電節點的數據轉發量，降低網絡中電池供電路由節點的總負載。

例如將圖1中節點R6與節點R2的連接斷開，而將節點R6連接到節點R7，將節點R5與R4斷開并與結點R6建立連接。網絡拓撲結構改變后，節點R6與節點R3和節點R5的路由均不通過電池供電的路由節點，這樣就減少了電池供電節點的數據轉發量。

當網絡中有新節點加入或原有節點離開時，協調器會檢測到網絡結構的改變，此時啟動路由改進算法重構網絡，使得路由算法能夠動態適應網絡的變化。恰當地更改網絡拓撲結構可整體降低電池供電節點的數據轉發量。此外，不同路徑上流量的變化也會引起網絡拓撲結構的改變。

2.2 算法初始條件計算

ZigBee樹型拓撲中，要實現上述算法，路由節點需要獲取以下信息：（1）節點轉發的數據流量；（2）已知網絡中數據轉發時的路由；（3）路由中包含的電池供電節點；（4）路由節點可連接的其他路由節點信息。由ZigBee樹型網絡結構的特征可知，一個路由節點只需要極少的流量就可獲得這些信息[3] [4]。當數據經過某路由節點轉發時，該路由節點能夠檢測到數據的源節點和目的結點，以及該結點轉發數據的比重。獲取節點設備的電源類型需要額外的信息，算法中通過搜集每個節點的信息，協調器記錄電池供電節點的信息，其它節點訪問協調器獲取所需信息。數據轉發的路由在樹型網絡中可由具有路由能力的節點直接計算獲得。通過（1）式計算網絡中電池供電路由節點的總負載[5]，其中TotalLoad是電池節點的總負載，P是路由中電池供電節點的數目，n為網絡中的總路由數，T是該條路由轉發數據量的比重。

（1）

為獲取可連接的鄰居節點的信息，該文中引入了鄰居表[8]，如果某路由節點在另一路由節點的直接通信范圍內，則兩節點互為鄰居節點，網絡中只針對FFD節點儲存鄰居節點信息，每個FFD節點通過鄰居列表記錄下該節點與其他節點的鄰接關系。鄰居表中記錄如圖2所示，在鄰居表中ADDR是鄰居節點地址，DType是鄰居節點電源類型。

2.3 重構網絡拓撲結構算法流程

當網絡中有新的節點加入或有節點離開時，網絡重構會發生，用（1）式計算所有可重構的新拓撲網絡中的電池供電節點總負載，若總負載最小的網絡結構，也即最好的網絡拓撲結構，其總負載小于當前網絡的總負載時，算法更改網絡拓撲，否則維持原有網絡拓撲。一個路由節點依據電池供電節點的總負載量來決定其父節點，需要改變網絡拓撲時，該路由節點就斷開與原父節點的連接，并與新的父節點建立連接，新父節點的路徑深度要求不大于原父節點的路徑深度，避免該節點的子節點無法獲得足夠的網絡地址，網絡重構選擇新父節點的具體算法如下。

（1）初始化網絡中的電池供電設備總負載為load。

（2）依次取得網絡中具有路由能力的節點Cn。

（3）依次取得節點Cn的鄰居節點An，若無鄰居節點時轉向第（2）步。

（4）如果節點An的深度小于節點Cn的網絡深度，算法繼續，否則轉到第（3）步。

（5）使用（1）式計算當節點Cn連接到父節點An時網絡中電池供電節點的總負載newload，如果新找到網絡拓撲中電池供電節點的總負載小于已發現的網絡拓撲負載時，將load值更改為newload，并且記錄節點An和節點Cn。

（6）轉到第（2），繼續查找使得網絡中電池供電節點的總負載最小的節點對An和Cn，直到分析完網絡中所有具有路由能力的節點。

（7）將節點Cn連接到節點An，父節點An給節點Cn分配新地址Rn，選擇父節點的過程結束。

由ZigBee樹型網絡的地址分配機制可知，當路由節點的父節點改變后，該節點的地址及其所有子節點的地址都需要重新分配。重構網絡時，改變父節點的重構子樹的根節點將原有地址和新分配的地址發送給各后代節點，每個后代節點利用該信息計算其父節點、子節點或自身的地址。重構子樹的節點更改地址后，按ZigBee網絡中獨立節點方式加入網絡拓撲中。通過以下算法可修改網絡結構改變后重構子樹中節點的地址，具體流程如下。

（1）初始化函數參數，R是子樹根節點原地址，R是子樹根節點新地址，D是后代節點原地址，函數返回結果是后代節點新地址Dn

（2）若節點D是子樹根節點R的后代節點

（3）將D賦值為R，A賦值為R。

（4）遞歸查找地址A，使其指向節點D

（5）遞歸計算節點D在新網絡拓撲中地址

更改設備地址算法的偽代碼如下：

UpdateAddress（R，R，D）

{if（ R< D&& D< （R+ C（depth-1）））

{D=R；A=R；

While（A！= D）

{skip=C（depth）；skip=C（depth）；

index=

A=A+1+index*skip

D=D+1+index*skip }}}

return Dn

網絡中節點的地址改變后，網絡中其余的節點應該獲取改變地址節點的信息，以便能夠正確的發送數據包。同時修改協調器中存儲的節點信息，使修改后的節點地址與電源類型一致，以便能夠正確的計算網絡中電池供電節點的總負載。當某個網絡拓撲中數據流量穩定時，網絡重構會生成一個新的穩定的網絡拓撲，新的網絡拓撲中會盡可能避免使用電池供電節點轉發數據，當發現網絡中電池供電節點的總負載減少時，即有更好的網絡拓撲時，網絡繼續進行重構。因為路由節點會不斷地檢測轉發的數據包，并且做相應的記錄，因此該算法也能處理網絡流量動態改變的情況，當網絡中總流量或部分路由中的流量發生變化時，新的網絡拓撲重構會進行以適應新的網絡流量狀態。

3 仿真結果分析

算法仿真分別在使用了PSAR算法和未使用PSAR算法兩種情況下進行。仿真中所有變量保持不變，改變以下變量來測量算法的運行效果。這些變量是電池供電節點的數據轉發總量，網絡規模和電池供電節點占網絡總節點數的比例。表示算法效率的變量是網絡中電池供電節點總負載的耗能減少百分率（Reduction），定義見（2）式。

（2）

改進算法通過仿真實驗和傳統樹路由算法進行了比較，主要比較優化前后兩種網絡拓撲中電池供電節點轉發數據的總負載。仿真結果證明了使用改進算法重構的網絡中能使電池供電節點的總負載平均減少50%以上，證明了改進算法的有效性。

仿真工具采用Omnet++，網絡覆蓋面積為400×400，網絡中路由節點數分別為40和100個，網絡中的節點都是具有路由能力的FFD節點，網絡協調器參數初始化Cm =5，Rm=5，Lm=5，網絡中電池供電節點比例的值依次是10，30，…，90%。仿真實驗結果如圖3和圖4所示。

圖3記錄了仿真網絡中分別為40和100時，網絡中電池供電節點的總負載隨電池供電節點占網絡節點比例的變化。分析可知，當采用改進后的PARA算法，可使電池供電節點的總負載較原網絡拓撲平均減少近50%，同時網絡中隨著電池供電節點比例以及節點密度的增大，PARA算法對網絡拓撲重構后電池供電節點總負載的影響也相應減小。說明該算法更適用于電源供電節點占一定比例的網絡。

實驗結果同時分析了PARA算法的網絡路由代價，即控制信息數據量占實際數據量的比重。算法費用主要來自記錄或詢問設備的電源類型，請求潛在父節點的連接，重構子樹節點的地址更改，網絡重構后通知其它節點重構子樹節點的新地址。由圖4 可知，控制信息的數據量比率低于0.6%，算法對網絡流量的影響小，算法的穩定性較好。網絡規模在40和100時，控制報文的比率相差不大，說明網絡規模對該比率并無顯著的影響，這是因為當網絡規模增大時，控制信息的數據量與網絡的總數據量在同比增加。

4 結語

該文在深入研究了ZigBee網絡的組網技術及其路由算法的基礎上，結合電源供電設備和電池供電設備的特點，提出了一種基于ZigBee樹型網絡的電源感知路由算法（PARA），并分析了改進算法的性能。由仿真評估可知PARA算法比樹路由算法（DAAM）有效的減少了網絡中電池供電節點的數據轉發量，算法只需少量的通訊開銷就可以明顯地減少電池供電路由節點的耗能，延長了網絡的生存時間。但該算法僅適應于持續電源節點占一定比例的網絡，且網絡中需含有完全由持續電源節點組成的路徑，該算法研究為特定應用環境中網絡節點的布置提供了理論基礎。

參考文獻

[1] IEEE Std.802.15.4，Wireless Medium Access Control（MAC） and Physical Layer（PHY）Specification for Low-Rate Wireless Personal Area network， October 1，2003.

[2] ZigBee Standards Organization.（2006）.ZigBee specification.

[3] Shah，p.，Shaikh，T.，Ghan，l，Shilaskar，S.Power mana- gement using ZigBee wireless sencor network.Emerging trends in engineering and technology，2008.First International Conference on2008：242-245.

[4] Egan，D.The emergence of ZigBee in building automation and industrial control[J].Computering and Control Engineering Journal，2005，16（2），14-19.

[5] Chen，M.Yang，L.T.Kwon，T. Zhou，L.&Jo，M.Itinerary planning for energy efficient agent communications in wireless sensor networks[J].Vehicular Technology，IEEE Transactions on，2011，60（7）：3290-3299.

[6] I.Hwang，J.Baek.Wireless Access Monitoring and Control System based on Digital Door Lock，IEEE Trans[J].Consumer Electron，2007，53（4）.

[7] 薛艷亮，胡建萍，王江柱.基于分布式編址機制的ZigBee組網技術研究[J].杭州電子科技大學學報，2008，28（2）：33-36.

[8] 戚劍超，魏臻.ZigBee樹型路由算法的改進[J].合肥工業大學學報，2010，33（4）：529-532.