汪 紅，曾繁迪，田莎莎

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢430074)

基于ZigBee網(wǎng)絡(luò)的自適應(yīng)剪枝能耗均衡路由算法

汪 紅，曾繁迪，田莎莎

(中南民族大學(xué) 計算機科學(xué)學(xué)院，武漢430074)

在ZigBee網(wǎng)絡(luò)中建立兩個節(jié)點的通信時，為了既保證路徑中總的能量耗費最低，又令路徑中不包括剩余能量較少的節(jié)點，盡量延長網(wǎng)絡(luò)的壽命，提出了基于ZigBee網(wǎng)絡(luò)的自適應(yīng)剪枝能耗均衡(AP-ECB)路由算法.該算法包括兩個改進的策略：自適應(yīng)剪枝策略和能耗均衡策略.自適應(yīng)剪枝策略采用有效的剪枝策略令更多的節(jié)點進入休眠狀態(tài)，節(jié)約了能耗；能耗均衡策略規(guī)避了將剩余能量較少的節(jié)點選入路徑，保證了ZigBee網(wǎng)絡(luò)的可用性.對AODVjr和AP-ECB路由算法進行了仿真驗證，結(jié)果表明：AP-ECB路由算法選擇的路徑能耗更少，同時遇到的死亡節(jié)點更少.

路由算法；自適應(yīng)剪枝；能耗均衡；死亡節(jié)點

1 ZigBee無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)與能耗分析

ZigBee是基于IEEE802.15.4標(biāo)準(zhǔn)的低功耗局域網(wǎng)協(xié)議[9].作為傳統(tǒng)的無線傳感器網(wǎng)絡(luò)中的一種，ZigBee實現(xiàn)了低功耗、低數(shù)據(jù)吞吐量的無線連接.在ZigBee網(wǎng)絡(luò)中存在3種邏輯設(shè)備類型：協(xié)調(diào)器(Coordinator)、路由器(Router)和終端設(shè)備(EndDevice)[10].一個ZigBee網(wǎng)絡(luò)由一個協(xié)調(diào)器以及多個路由器和多個終端設(shè)備組成，如圖1所示.協(xié)調(diào)器負責(zé)整個網(wǎng)絡(luò)的配置和管理，路由器和終端負責(zé)采集和轉(zhuǎn)發(fā)數(shù)據(jù).這3種邏輯設(shè)備構(gòu)成了ZigBee無線傳感器網(wǎng)絡(luò)的眾多節(jié)點.

圖1 ZigBee網(wǎng)絡(luò)示意圖Fig.1 Schematic diagram of ZigBee network

每一個ZigBee無線傳感器網(wǎng)絡(luò)節(jié)點可分為兩大部分，即微程序控制器(MCU)模塊和射頻(RF)模塊.與RF模塊相比，MCU模塊和傳感器本身僅消耗小部分能量.因此，降低ZigBee無線傳感器網(wǎng)絡(luò)的功耗，主要是降低RF模塊的功耗.RF模塊可分為發(fā)送狀態(tài)、接受狀態(tài)、空閑狀態(tài)和休眠狀態(tài).實驗表明：RF模塊在休眠狀態(tài)下的功耗是其它3種狀態(tài)下的1/20，因此降低RF模塊的功耗，關(guān)鍵是在不影響網(wǎng)絡(luò)正常運行的前提下，將無數(shù)據(jù)傳送任務(wù)的RF模塊置為休眠狀態(tài)[11].

2 AODVjr路由算法及其分析

2.1 AODVjr路由算法原理

AODVjr算法有3種路由控制分組，分別為：路由請求(RREQ)、路由應(yīng)答(RREP)、路由錯誤(RERR)，其工作過程如下.

(1)源節(jié)點以洪泛方式廣播一個RREQ路由控制分組；

(2)收到RREQ的節(jié)點判斷自己以前是否已經(jīng)收到RREQ分組，若是一個新的RREQ分組，則在其路由表中建立一個反向路由；若不是新的分組則將其丟棄；

(3)RREQ傳遞到目的節(jié)點之后，目的節(jié)點需要向源節(jié)點回復(fù)一個RREP控制分組，此分組會按照步驟(2)中建立的反向路由，從目的節(jié)點傳送至源節(jié)點；

首先是市場定位。成功的市場定位十分重要，在旅游行業(yè)發(fā)展中起到了十分重要的效能。管理人員按照大數(shù)據(jù)市場數(shù)據(jù)分析和內(nèi)容調(diào)研，可對市場構(gòu)成內(nèi)容和市場發(fā)展特征內(nèi)容以及消費群體需求內(nèi)容等進行高效判斷與了解。通過科學(xué)信息信息數(shù)據(jù)收集操作和管理操作以及分析操作基礎(chǔ)上，創(chuàng)建優(yōu)質(zhì)處理模式，綜合保障品牌市場個性化定位，在此前提下提升行業(yè)間接受度和民眾認可度。實踐環(huán)節(jié)內(nèi)，務(wù)必實現(xiàn)資源控制，更深度地對潛在數(shù)據(jù)資源予以有效挖掘與高效利用。

(4)源節(jié)點收到RREP控制分組后，將反向路由反向，建立正向路由，從源節(jié)點向目的節(jié)點傳送數(shù)據(jù).

2.2 AODVjr路由算法分析

如圖1所示，為了建立任意兩個節(jié)點的通信，圖中大部分節(jié)點都參與了通信路徑的建立，無法進入休眠狀態(tài)，造成了能量的損耗.另外，由于整個ZigBee網(wǎng)絡(luò)中的節(jié)點眾多，有些節(jié)點可能已經(jīng)能量耗盡，處于死亡狀態(tài)，若找到的通信路徑正好包含死亡節(jié)點，將導(dǎo)致數(shù)據(jù)通信失敗.基于AODVjr路由算法的上述兩個缺點，本文提出了自適應(yīng)剪枝能耗均衡路由算法.

3 自適應(yīng)剪枝能耗均衡路由算法

自適應(yīng)剪枝能耗均衡路由算法包括兩個改進策略：自適應(yīng)剪枝策略和能耗均衡策略，這兩個策略一起保證了所選擇的路徑消耗能量較少且包含的死亡節(jié)點較少.

3.1 自適應(yīng)剪枝策略

AODVjr算法在執(zhí)行過程中，大部分節(jié)點都參與了通信路徑的建立，造成了能量的大量損耗.造成這個結(jié)果有如下幾個原因：首先，ZigBee網(wǎng)絡(luò)中節(jié)點之間的聯(lián)系都是雙向的；其次，ZigBee網(wǎng)絡(luò)中低層的節(jié)點可以對高層節(jié)點反向傳送數(shù)據(jù)；最后，源節(jié)點與目的節(jié)點之間通信路徑的建立是向各個方向發(fā)散的，沒有方向性.基于上述原因，本文提出了自適應(yīng)剪枝策略，該策略可描述如下.

(1)將ZigBee網(wǎng)絡(luò)中同層節(jié)點之間的網(wǎng)絡(luò)鏈路暫時去掉，以圖1為例，去掉同層節(jié)點之間的網(wǎng)絡(luò)鏈路后如圖2所示.

(2)設(shè)源節(jié)點的網(wǎng)絡(luò)深度為ls，目的節(jié)點的網(wǎng)絡(luò)深度為lo，若l=ls-lo>0，則令源節(jié)點向上面l層處尋找父節(jié)點；否則，就令目的節(jié)點向上面l層處尋找父節(jié)點.若源節(jié)點(目的節(jié)點)上面l層處的父節(jié)點即為目的節(jié)點(源節(jié)點)，則保存此路徑上的各個節(jié)點，并為這些節(jié)點添加(1)中去掉的網(wǎng)絡(luò)鏈路，將此外的一切節(jié)點和鏈路剪去.若源節(jié)點(目的節(jié)點)上面l層處的父節(jié)點不是目的節(jié)點(源節(jié)點)，則分別查找源節(jié)點和目的節(jié)點到協(xié)調(diào)器節(jié)點處的路徑，將這兩個路徑連通，并為這個路徑上的節(jié)點添加(1)中去掉的網(wǎng)絡(luò)鏈路，將此外的一切節(jié)點和鏈路剪去.此步采用自適應(yīng)策略，根據(jù)目的節(jié)點和源節(jié)點之間的路徑自適應(yīng)剪枝.

(3)利用AODVjr算法為剪枝之后的網(wǎng)絡(luò)尋找源節(jié)點到目的節(jié)點的最佳路徑.過程如圖3所示.

圖2 去掉同層節(jié)點間網(wǎng)絡(luò)鏈路的ZigBee網(wǎng)絡(luò)Fig.2 ZigBee network cleared away network link between horizontal nodes

(a) 選定源節(jié)點和目的節(jié)點 (b) 尋找源節(jié)點和目的節(jié)點之間的路徑

(c) 增加所尋路徑及路徑上節(jié)點的同層鏈路 (d) 剪枝操作 圖3 自適應(yīng)剪枝算法實例Fig.3 An example of adaptive pruning algorithm

3.2 能耗均衡策略

能耗均衡，即對于路由算法所尋得的路徑，一方面要保證能耗較小，一方面要保證網(wǎng)絡(luò)中每個節(jié)點的能耗均衡，避免由于部分節(jié)點剩余能量太低，引起網(wǎng)絡(luò)分割，進而影響網(wǎng)絡(luò)壽命.基于此，在3.1中描述的自適應(yīng)剪枝策略的基礎(chǔ)上提出能耗均衡策略.

假設(shè)源節(jié)點為ns，目的節(jié)點為ne，經(jīng)過自適應(yīng)剪枝之后，源節(jié)點和目的節(jié)點之間有k條路徑，設(shè)第i條路徑上的能量消耗為Cost(i)，其中i=1,2,…,k，第i條路徑上剩余能量最低的節(jié)點的能量為Source(i).為了既保證所選路徑消耗能量少，又保證各節(jié)點的能耗均衡，采用如下步驟進行路徑選擇：

(2) 將Cost(i)按照升序排序，并保留前m個Cost(i)對應(yīng)的路徑；

(3) 將Source(i)按照降序排序，并保留前m個Source(i)對應(yīng)的路徑；

(4) 對步驟(2)、(3)中的結(jié)果取并集，若并集的結(jié)果為空，則令m=m+1，并返回步驟(2),否則進行步驟(5)；

(5) 設(shè)取并集之后的結(jié)果中包含h條路徑，設(shè)選擇的路徑為r，則：

j=1,2,…,h.

(1)

從式(1)可以看出，路徑的選擇兼顧了路徑的總能耗較低和路徑中節(jié)點的能耗均衡.

4 實驗與結(jié)果分析

為了驗證算法的性能，基于NS-2模擬仿真軟件對AODVjr路由算法和本文所提出的AP-ECB路由算法進行了仿真驗證，網(wǎng)絡(luò)中有路由器10個，終端30個，每個節(jié)點的總能量為1000J.圖4為兩種算法在網(wǎng)絡(luò)整體能耗方面的對比，由于改進算法通過剪枝操作，有效地控制了被喚醒的節(jié)點的數(shù)目，因而能耗較小.

圖4 AODVjr和AP-ECB路由算法在網(wǎng)絡(luò)能耗方面的比較Fig.4 Comparation of AODVjr and AP-ECB routing algorithm in network energy consumption

圖5為AODVjr路由算法和本文所提出的AP-ECB路由算法在死亡節(jié)點方面的比較，因為路由選擇過程中直接放棄了剩余能量很低的節(jié)點，所以死亡節(jié)點的數(shù)目大大減少.另外，由于減少了訪問節(jié)點的數(shù)目，相比AODVjr路由算法，AP-ECB路由算法大大降低了時間和空間開銷.

圖5 AODVjr和AP-ECB路由算法在死亡節(jié)點數(shù)目方面的比較Fig.5 Comparation of AODVjr and AP-ECB routing algorithm in death nodes numbers

5 結(jié)論

本文設(shè)計了一個基于ZigBee網(wǎng)絡(luò)的AP-ECB路由算法.經(jīng)過實驗驗證，可知該算法在能耗降低和網(wǎng)絡(luò)壽命方面較AODVjr路由算法都有優(yōu)勢.AP-ECB路由算法采用的自剪枝策略可以快速去除無用的路徑，將盡量多的節(jié)點設(shè)置為睡眠模式，有效地節(jié)約能耗；AP-ECB路由算法采用的能耗均衡策略兼顧了路徑總能耗較少和路徑上死亡節(jié)點較少，提高了網(wǎng)絡(luò)的壽命，降低了網(wǎng)絡(luò)被分割的可能性.該算法還可以擴展到其他網(wǎng)絡(luò)中使用，提高其網(wǎng)絡(luò)壽命.

[1] Akkaya K, Younis M. A survey on routing protocols for wireless sensor networks[J]. Ad Hoc Networks, 2005, 3(3): 325-349.

[2] Olivier B,Florenee M,Laurent M.Modeling and analysis of wireless sensor networks[EB/OL].(2006-01-01).http://pop-art.inrialpes.fr/～girault/Synchron06/Slides/samper. pdf.

[3] 張文靜. 基于CC2530的ZigBee網(wǎng)絡(luò)節(jié)點的低功耗設(shè)計[J]. 機電信息, 2014(9): 123-124.

[4] 謝 川. 基于ZigBee的AODVjr算法研究[J]. 計算機工程, 2011, 37(10):87-89.

[5] 羅 華. 基于ZigBee的無線傳感器網(wǎng)絡(luò)路由算法研究[D]. 長沙：中南大學(xué), 2010.

[6] 劉艷鳳. 基于ZigBee網(wǎng)絡(luò)的分層網(wǎng)絡(luò)框架體系分析[J].信息與電腦：理論版,2014(10):89.

[7] Li C, Zhang M, He H, et al. Research of improved ZigBee-based AODVjr routing algorithm in cloud manufacturing[J]. International Journal of Online Engineering, 2015, 11(2):20-25.

[8] Pan Q, Wu J, Wang Y, et al. Implementation of ZigBee network layer based on AODVjr and tree hirarchical route algorisms[J]. Journal of Software Engineering & Applications, 2011(4):487-490.

[9] 高守瑋，吳燦陽. ZigBee技術(shù)實踐教程：基于CC2430/31的無線傳感器網(wǎng)絡(luò)解決方案[M]. 北京：北京航空航天大學(xué)出版社，2009: 40-41.

[10] 徐麗華，王宜懷．一種ZigBee網(wǎng)絡(luò)的設(shè)計與實現(xiàn)[J]．微計算機信息，2007,23(32): 72-74．

[11] Feeney L M, Nilsson M. Investigating the energy consumption of a wireless network interface in an ad hoc networking environment[C]//IEEE. Infocom 20th Joint Conference of the IEEE Computer and Communications Societies. Pennsylvania: IEEE, 2001:1548-1557.

Routing Algorithm of Adaptive Pruning and Energy Consumption Balancing Based on ZigBee Network

WangHong,ZengFandi,TianShasha

(College of Computer Science, South-Central University for Nationalities, Wuhan 430074, China)

A routing algorithm of adaptive pruning and energy consumption balancing based on ZigBee network was proposed to not only ensure the lowest energy consumption in the selected route, but also ensure the selected route do not contain the nodes which left energy is less, when communication was built between two nodes in ZigBee network. The algorithm includes two improved strategies: Adaptive pruning strategy and energy consumption balancing strategy. In adaptive pruning strategy, an effective pruning strategy is used to put more nodes to sleep and save the energy consumption. In energy consumption balancing strategy, the nodes that left energy is less, would not be selected into the route. This ensure the availability of the ZigBee network. By simulating and verifying the AODVjr and AP-ECB routing algorithm, it can be concluded that the route selected by AP-ECB routing algorithm save more energy and contains less death nodes.

routing algorithm；adaptive pruning；energy consumption balancing；death node

2017-02-27

汪 紅(1968-)，女，副教授，研究方向：計算機系統(tǒng)結(jié)構(gòu)，嵌入式系統(tǒng)，E-mail: wanghong_2010@foxmail.com

國家自然科學(xué)基金資助青年項目(61603420)；湖北省自然科學(xué)基金資助項目(2014CFB413)

TP274.5

A

1672-4321(2017)02-0129-04