汪 紅，曾繁迪，田莎莎

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

基于ZigBee網絡的自適應剪枝能耗均衡路由算法

汪 紅，曾繁迪，田莎莎

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

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

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

1 ZigBee無線傳感器網絡結構與能耗分析

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

圖1 ZigBee網絡示意圖Fig.1 Schematic diagram of ZigBee network

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

2 AODVjr路由算法及其分析

2.1 AODVjr路由算法原理

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

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

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

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

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

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

2.2 AODVjr路由算法分析

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

3 自適應剪枝能耗均衡路由算法

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

3.1 自適應剪枝策略

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

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

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

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

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

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

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

3.2 能耗均衡策略

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

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

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

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

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

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

j=1,2,…,h.

(1)

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

4 實驗與結果分析

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

圖4 AODVjr和AP-ECB路由算法在網絡能耗方面的比較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 結論

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

[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網絡節(jié)點的低功耗設計[J]. 機電信息, 2014(9): 123-124.

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

[5] 羅 華. 基于ZigBee的無線傳感器網絡路由算法研究[D]. 長沙：中南大學, 2010.

[6] 劉艷鳳. 基于ZigBee網絡的分層網絡框架體系分析[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技術實踐教程：基于CC2430/31的無線傳感器網絡解決方案[M]. 北京：北京航空航天大學出版社，2009: 40-41.

[10] 徐麗華，王宜懷．一種ZigBee網絡的設計與實現(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)結構，嵌入式系統(tǒng)，E-mail: wanghong_2010@foxmail.com

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

TP274.5

A

1672-4321(2017)02-0129-04