鄧宇，徐思燕

（西華大學(xué)計算機(jī)與軟件工程學(xué)院，成都　610039）

能量高效的ZigBee路由算法

鄧宇，徐思燕

（西華大學(xué)計算機(jī)與軟件工程學(xué)院，成都610039）

傳統(tǒng)ZigBee網(wǎng)絡(luò)路由協(xié)議中沒有保護(hù)剩余能量低的節(jié)點，在路由發(fā)現(xiàn)中進(jìn)行廣播RREQ等問題。考慮傳播路徑上的能量消耗，RREQ的發(fā)送方向，節(jié)點之間的鄰居關(guān)系，提出一種基于能量的高效路由算法，算法仿真結(jié)果表明，改進(jìn)后的算法有效地減少RREQ的發(fā)送數(shù)量，增加節(jié)點的存活率，延長網(wǎng)絡(luò)的生存時間。

ZigBee網(wǎng)絡(luò)；RREQ；路由算法；能量；仿真

0　引言

ZigBee是一種低成本、低速率的短距離雙向無線通信新技術(shù)，該技術(shù)物理層和MAC層主要是基于IEEE802.15.4標(biāo)準(zhǔn)，網(wǎng)絡(luò)層通過ZigBee聯(lián)盟制定。在醫(yī)療、軍事、監(jiān)控、智能家居、工業(yè)控制、環(huán)境監(jiān)測等領(lǐng)域得到了廣泛的應(yīng)用［1］。由于ZigBee網(wǎng)絡(luò)節(jié)點能量限制，所以網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和網(wǎng)絡(luò)的路由策略的選擇，對于整個ZigBee網(wǎng)絡(luò)的有效性起著至關(guān)重要的作用。

在ZigeBee網(wǎng)絡(luò)中，主要采用Cluster-Tree和AODVjr算法相互結(jié)合的策略來完成轉(zhuǎn)發(fā)操作。Cluster-Tree算法是靜態(tài)算法，通過節(jié)點之間的拓?fù)潢P(guān)系來進(jìn)行轉(zhuǎn)發(fā)過程，不需要存儲路由表，但是數(shù)據(jù)在轉(zhuǎn)發(fā)選擇中并非是最優(yōu)的路徑，而是嚴(yán)格按照拓?fù)潢P(guān)系進(jìn)行轉(zhuǎn)發(fā)，缺少相應(yīng)的靈活性和伸縮性。AODVjr算法是在傳統(tǒng)的AODV算法中改進(jìn)來的，可以通過廣播請求來進(jìn)行路由查找和路由維護(hù)。但由于兩個算法固有局限，使得原有的算法在路由發(fā)現(xiàn)、均衡網(wǎng)絡(luò)負(fù)載、能量消耗等方面存在不足。

本文以節(jié)省能量和減少網(wǎng)絡(luò)廣播為主要目標(biāo)，對路由算法進(jìn)行分析，改進(jìn)原有的AODVjr路由發(fā)現(xiàn)過程，使得在路由過程中能節(jié)省能量、減少RREQ廣播、延長網(wǎng)絡(luò)生存時間。

1　ZigBee網(wǎng)絡(luò)層路由通信原理

1.1Cluster-Tree及地址分配

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

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

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

在該路由算法中，源節(jié)點到目的節(jié)點下一跳的方向通過目的節(jié)點網(wǎng)絡(luò)地址計算出來。源節(jié)點先需要判斷和目的節(jié)點的關(guān)系，判斷后再進(jìn)行下一跳的路徑的選擇，若目標(biāo)節(jié)點是源節(jié)點的子節(jié)點，直接轉(zhuǎn)發(fā)給目的節(jié)點。否則將源節(jié)點的數(shù)據(jù)轉(zhuǎn)發(fā)給父節(jié)點，通過父節(jié)點來進(jìn)行轉(zhuǎn)發(fā)的接力。

1.2AODVjr及其路由選擇

AODVjr路由分為路由發(fā)現(xiàn)和路由維護(hù)兩個過程。

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

RREP：該分組只能由目標(biāo)節(jié)點進(jìn)行回復(fù)，RREP分組的傳送路徑為路由建立過程中的反向路由，產(chǎn)生從源節(jié)點到目標(biāo)節(jié)點的可靠路由。

2　改進(jìn)的路由算法

AODVjr是一種改進(jìn)的AODV算法，AODVjr路由的基本原理就是通過廣播RREQ來實現(xiàn)按需的路由發(fā)現(xiàn)的功能，最早到達(dá)目標(biāo)節(jié)點的RREQ回復(fù)做出響應(yīng)，可以避免造成路由環(huán)路，選出路徑。但是傳統(tǒng)的AODVjr在路由發(fā)現(xiàn)時候是廣播RREQ，并未根據(jù)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)選擇合適的方向，可能造成網(wǎng)絡(luò)在某種程度上擁塞和網(wǎng)絡(luò)帶寬等資源的浪費［3］。

由于AODVjr算法存在不同程度的缺陷，為了獲取更好的網(wǎng)絡(luò)生存時間和網(wǎng)絡(luò)數(shù)據(jù)傳輸效率，充分利用節(jié)點的能量劃分，本文提出一種基于能量的高效路由算法，分別通過鄰居表和路由發(fā)現(xiàn)兩方面進(jìn)行改進(jìn)。

2.1鄰居表

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

路由節(jié)點在發(fā)起路由發(fā)現(xiàn)過程前，先執(zhí)行對鄰居表的掃描，實現(xiàn)通過鄰居表搜索目的節(jié)點的功能。

2.2路由發(fā)現(xiàn)策略

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

設(shè)節(jié)點的能量為E，初始能量為Eo，當(dāng)E＞=30%Eo的時候節(jié)點才參與RREQ的轉(zhuǎn)發(fā)。否則當(dāng)?shù)陀陂撝禃r候，收到RREQ直接拋棄。

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

當(dāng)前節(jié)點在對收到的RREQ進(jìn)行轉(zhuǎn)發(fā)前，先通過下面的偽代碼判斷RREQ往下的傳播方向：

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

路由具體流程如下圖：

圖1　

圖2　節(jié)點存活率

3　仿真驗證

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

圖1對算法改變前后的節(jié)點存活率進(jìn)行了比較分析，可以看出改進(jìn)后的算法在節(jié)點存活率上優(yōu)于傳統(tǒng)的算法。

圖3對算法改變前后的RREQ發(fā)送數(shù)量進(jìn)行分析，可以看出改進(jìn)后的算法在發(fā)送RREQ包上有明顯的減小，降低了網(wǎng)絡(luò)風(fēng)暴，延緩了網(wǎng)絡(luò)的分割。

4　結(jié)語

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

圖3　RREQ發(fā)送對比圖

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

［2］王琛，柴喬林，王芳.基于樹形結(jié)構(gòu)的ZigBee能量均衡協(xié)議研究.計算機(jī)工程與設(shè)計，2009-08-16

［3］劉兆孟.ZigBee無線傳感網(wǎng)絡(luò)路由協(xié)議的研究與設(shè)計.江南大學(xué)碩士論文，2013-06-01

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

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

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

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

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