能量高效的ZigBee路由算法

鄧宇，徐思燕

（西華大學計算機與軟件工程學院，成都　610039）

能量高效的ZigBee路由算法

鄧宇，徐思燕

（西華大學計算機與軟件工程學院，成都610039）

傳統ZigBee網絡路由協議中沒有保護剩余能量低的節點，在路由發現中進行廣播RREQ等問題。考慮傳播路徑上的能量消耗，RREQ的發送方向，節點之間的鄰居關系，提出一種基于能量的高效路由算法，算法仿真結果表明，改進后的算法有效地減少RREQ的發送數量，增加節點的存活率，延長網絡的生存時間。

ZigBee網絡；RREQ；路由算法；能量；仿真

0　引言

ZigBee是一種低成本、低速率的短距離雙向無線通信新技術，該技術物理層和MAC層主要是基于IEEE802.15.4標準，網絡層通過ZigBee聯盟制定。在醫療、軍事、監控、智能家居、工業控制、環境監測等領域得到了廣泛的應用［1］。由于ZigBee網絡節點能量限制，所以網絡拓撲結構和網絡的路由策略的選擇，對于整個ZigBee網絡的有效性起著至關重要的作用。

在ZigeBee網絡中，主要采用Cluster-Tree和AODVjr算法相互結合的策略來完成轉發操作。Cluster-Tree算法是靜態算法，通過節點之間的拓撲關系來進行轉發過程，不需要存儲路由表，但是數據在轉發選擇中并非是最優的路徑，而是嚴格按照拓撲關系進行轉發，缺少相應的靈活性和伸縮性。AODVjr算法是在傳統的AODV算法中改進來的，可以通過廣播請求來進行路由查找和路由維護。但由于兩個算法固有局限，使得原有的算法在路由發現、均衡網絡負載、能量消耗等方面存在不足。

本文以節省能量和減少網絡廣播為主要目標，對路由算法進行分析，改進原有的AODVjr路由發現過程，使得在路由過程中能節省能量、減少RREQ廣播、延長網絡生存時間。

1　ZigBee網絡層路由通信原理

1.1Cluster-Tree及地址分配

ZigBee網絡把節點分為了協調器、路由節點、終端節點三種類型。網絡地址是16位的，最多可以分配65536個節點，假設每個父節點最大可接納的子節點數為Cm，可接納的最大的路由節點數為Rm，以及網絡的最大深度為Lm［2］，經過分布式的地址分配策略，可以根據公式（1）計算出深度為d的父節點為其子節點（路由節點和終端節點）預留的地址偏移量Cskip，根據子節點的類型，采用的分配方式也有一定的區別［1］。

如果子節點是第n個新加入的路由節點，父節點為其分配的路由地址通過公式（2）計算。

父節的地址為Ap，如果子節點是第n個新加入的終端節點，父節點為其分配的路由地址通過公式（3）計算。

在該路由算法中，源節點到目的節點下一跳的方向通過目的節點網絡地址計算出來。源節點先需要判斷和目的節點的關系，判斷后再進行下一跳的路徑的選擇，若目標節點是源節點的子節點，直接轉發給目的節點。否則將源節點的數據轉發給父節點，通過父節點來進行轉發的接力。

1.2AODVjr及其路由選擇

AODVjr路由分為路由發現和路由維護兩個過程。

RREQ：主要是在發起路由的功能，通過廣播該分組，詢問收到該分組的節點是否知道到達目的節點的路由。

RREP：該分組只能由目標節點進行回復，RREP分組的傳送路徑為路由建立過程中的反向路由，產生從源節點到目標節點的可靠路由。

2　改進的路由算法

AODVjr是一種改進的AODV算法，AODVjr路由的基本原理就是通過廣播RREQ來實現按需的路由發現的功能，最早到達目標節點的RREQ回復做出響應，可以避免造成路由環路，選出路徑。但是傳統的AODVjr在路由發現時候是廣播RREQ，并未根據網絡的拓撲結構選擇合適的方向，可能造成網絡在某種程度上擁塞和網絡帶寬等資源的浪費［3］。

由于AODVjr算法存在不同程度的缺陷，為了獲取更好的網絡生存時間和網絡數據傳輸效率，充分利用節點的能量劃分，本文提出一種基于能量的高效路由算法，分別通過鄰居表和路由發現兩方面進行改進。

2.1鄰居表

每一個節點加入ZigBee網絡都維護自己鄰居點的信息，記錄著本節點與其他節點已存在的路由信息。鄰居表是由每一個ZigBee節點自動維護的，所以如果能在發起路由請求之前通過鄰居表尋址目的節點，將會避免路由發現等流程，能降低網絡能量的消耗和避免網絡的擁塞［4-5］。

路由節點在發起路由發現過程前，先執行對鄰居表的掃描，實現通過鄰居表搜索目的節點的功能。

2.2路由發現策略

如果目標節點不在鄰居表的范圍內，那么就需要開啟路由發現過程。通過廣播到目的節點的RREQ分組來實現最短路徑的查找，在路由發現過程中，有一些節點的頻繁使用一段時間后，節點的能量耗盡，造成網絡一定程度分割，節點就需要通過路由維護來重新查找路由的路徑，這樣會加重網絡的延遲和網絡負擔加重［4-5］。為了避免網絡節點過度使用和降低網絡的能量消耗，在路由發現時，解決如下兩個問題：（1）盡量避免使用能量低于閾值線的節點；（2）控制RREQ傳播方向。這樣既能保護剩余能量較小的節點，也能降低網絡的能量消耗。

設節點的能量為E，初始能量為Eo，當E＞=30%Eo的時候節點才參與RREQ的轉發。否則當低于閾值時候，收到RREQ直接拋棄。

由Cluster-Tree的傳播特性可知，若已知目的節點為當前節點的父節點，將分組向當前節點的子節點傳播是消耗節點能量，只會增加網絡的擁塞和浪費網絡的能量、帶寬。因此在節點轉發分組前，如果能事先進行判斷目的節點的方向，則可以減少網絡中的冗余的RREQ發送，避免網絡資源的浪費。

當前節點在對收到的RREQ進行轉發前，先通過下面的偽代碼判斷RREQ往下的傳播方向：

節點I收到其他節點發送給它的一個RREQ路由請求分組后，對RREQ的處理執行如下偽碼：

路由具體流程如下圖：

圖1　

圖2　節點存活率

3　仿真驗證

為了評估改進后的算法性能，本文利用NS-2，對改進前后的路由算法進行仿真。在仿真環境中，網絡大小設置為120m×120m，節點數為100，數據包的類型為CBR，初始能量為100J，數據流大小為50Byte，Cm=4、Rm=4、Lm=5，總仿真時間為400s。

圖1對算法改變前后的節點存活率進行了比較分析，可以看出改進后的算法在節點存活率上優于傳統的算法。

圖3對算法改變前后的RREQ發送數量進行分析，可以看出改進后的算法在發送RREQ包上有明顯的減小，降低了網絡風暴，延緩了網絡的分割。

4　結語

本文為了減少RREQ的發送數量、增加節點存活率、提高ZigBee網絡效率，提出一種基于能量的高效路由算法，該算法可以根據鄰居表選擇路徑，計算請求路徑上的節點剩余能量作為閾值線，考慮路徑上的能量因素，改進原有RREQ傳播方向，仿真結果證明，改進后的算法有效地減少了RREQ的發送數量，提高了節點的存活率，延長網絡的生存時間。

圖3　RREQ發送對比圖

［1］劉兆孟，吳錫生.能量高效的ZigBee路由算法.計算機仿真，2013-09-15

［2］王琛，柴喬林，王芳.基于樹形結構的ZigBee能量均衡協議研究.計算機工程與設計，2009-08-16

［3］劉兆孟.ZigBee無線傳感網絡路由協議的研究與設計.江南大學碩士論文，2013-06-01

［4］班艷麗.基于能量有效的ZigBee網絡路由算法研究［D］.山東大學碩士論文，2009－6：68－71．

［5］張擎，劉淑美，柴喬林．能量高效的ZigBee網絡改進路由策略［J］．計算機工程，2010，36（7）：108-111.作者簡介：

鄧宇（1991-），男，四川瀘州人，碩士研究生，研究方向為嵌入式系統及其應用

徐思燕（1986-），女，四川宜賓人，碩士研究生，研究方向為嵌入式系統及其應用

Energy Efficient Routing Algorithm for ZigBee

DENG Yu，XU Si-yan
（College of Computer and Software Engineering，Xihua University，Chengdu 610039）

Traditional ZigBee network routing protocols do not protect the low residual energy of nodes，broadcasting in the routing discovery RREQ，etc.Considers the energy consumption of the propagation path，the sending direction of RREQ，relationship between neighbor nodes，puts forward a kind of efficient routing algorithm based on energy，the algorithm simulation results show that the improved algorithm effectively can reduce the number of sending RREQ，increase the survival rate of the node，prolong the survival time of the network.

ZigBee Network；RREQ；Routing Algorithm.Energy；Simulation

1007-1423（2016）26-0023-004DOI：10.3969/j.issn.1007-1423.2016.26.005

2016-06-28

2016-09-05