基于ZigBee网络的自适应剪枝能耗均衡路由算法

2017-06-28曾繁迪田莎莎

中南民族大学学报（自然科学版） 2017年2期

关键词：剪枝路由链路

汪红，曾繁迪，田莎莎

(中南民族大学计算机科学学院，武汉430074)

基于ZigBee网络的自适应剪枝能耗均衡路由算法

汪红，曾繁迪，田莎莎

(中南民族大学计算机科学学院，武汉430074)

在ZigBee网络中建立两个节点的通信时，为了既保证路径中总的能量耗费最低，又令路径中不包括剩余能量较少的节点，尽量延长网络的寿命，提出了基于ZigBee网络的自适应剪枝能耗均衡(AP-ECB)路由算法.该算法包括两个改进的策略：自适应剪枝策略和能耗均衡策略.自适应剪枝策略采用有效的剪枝策略令更多的节点进入休眠状态，节约了能耗；能耗均衡策略规避了将剩余能量较少的节点选入路径，保证了ZigBee网络的可用性.对AODVjr和AP-ECB路由算法进行了仿真验证，结果表明：AP-ECB路由算法选择的路径能耗更少，同时遇到的死亡节点更少.

路由算法；自适应剪枝；能耗均衡；死亡节点

1 ZigBee无线传感器网络结构与能耗分析

ZigBee是基于IEEE802.15.4标准的低功耗局域网协议[9].作为传统的无线传感器网络中的一种，ZigBee实现了低功耗、低数据吞吐量的无线连接.在ZigBee网络中存在3种逻辑设备类型：协调器(Coordinator)、路由器(Router)和终端设备(EndDevice)[10].一个ZigBee网络由一个协调器以及多个路由器和多个终端设备组成，如图1所示.协调器负责整个网络的配置和管理，路由器和终端负责采集和转发数据.这3种逻辑设备构成了ZigBee无线传感器网络的众多节点.

图1 ZigBee网络示意图Fig.1 Schematic diagram of ZigBee network

每一个ZigBee无线传感器网络节点可分为两大部分，即微程序控制器(MCU)模块和射频(RF)模块.与RF模块相比，MCU模块和传感器本身仅消耗小部分能量.因此，降低ZigBee无线传感器网络的功耗，主要是降低RF模块的功耗.RF模块可分为发送状态、接受状态、空闲状态和休眠状态.实验表明：RF模块在休眠状态下的功耗是其它3种状态下的1/20，因此降低RF模块的功耗，关键是在不影响网络正常运行的前提下，将无数据传送任务的RF模块置为休眠状态[11].

2 AODVjr路由算法及其分析

2.1 AODVjr路由算法原理

AODVjr算法有3种路由控制分组，分别为：路由请求(RREQ)、路由应答(RREP)、路由错误(RERR)，其工作过程如下.

(1)源节点以洪泛方式广播一个RREQ路由控制分组；

(2)收到RREQ的节点判断自己以前是否已经收到RREQ分组，若是一个新的RREQ分组，则在其路由表中建立一个反向路由；若不是新的分组则将其丢弃；

(3)RREQ传递到目的节点之后，目的节点需要向源节点回复一个RREP控制分组，此分组会按照步骤(2)中建立的反向路由，从目的节点传送至源节点；

首先是市场定位。成功的市场定位十分重要，在旅游行业发展中起到了十分重要的效能。管理人员按照大数据市场数据分析和内容调研，可对市场构成内容和市场发展特征内容以及消费群体需求内容等进行高效判断与了解。通过科学信息信息数据收集操作和管理操作以及分析操作基础上，创建优质处理模式，综合保障品牌市场个性化定位，在此前提下提升行业间接受度和民众认可度。实践环节内，务必实现资源控制，更深度地对潜在数据资源予以有效挖掘与高效利用。

(4)源节点收到RREP控制分组后，将反向路由反向，建立正向路由，从源节点向目的节点传送数据.

2.2 AODVjr路由算法分析

如图1所示，为了建立任意两个节点的通信，图中大部分节点都参与了通信路径的建立，无法进入休眠状态，造成了能量的损耗.另外，由于整个ZigBee网络中的节点众多，有些节点可能已经能量耗尽，处于死亡状态，若找到的通信路径正好包含死亡节点，将导致数据通信失败.基于AODVjr路由算法的上述两个缺点，本文提出了自适应剪枝能耗均衡路由算法.

3 自适应剪枝能耗均衡路由算法

自适应剪枝能耗均衡路由算法包括两个改进策略：自适应剪枝策略和能耗均衡策略，这两个策略一起保证了所选择的路径消耗能量较少且包含的死亡节点较少.

3.1 自适应剪枝策略

AODVjr算法在执行过程中，大部分节点都参与了通信路径的建立，造成了能量的大量损耗.造成这个结果有如下几个原因：首先，ZigBee网络中节点之间的联系都是双向的；其次，ZigBee网络中低层的节点可以对高层节点反向传送数据；最后，源节点与目的节点之间通信路径的建立是向各个方向发散的，没有方向性.基于上述原因，本文提出了自适应剪枝策略，该策略可描述如下.

(1)将ZigBee网络中同层节点之间的网络链路暂时去掉，以图1为例，去掉同层节点之间的网络链路后如图2所示.

(2)设源节点的网络深度为ls，目的节点的网络深度为lo，若l=ls-lo>0，则令源节点向上面l层处寻找父节点；否则，就令目的节点向上面l层处寻找父节点.若源节点(目的节点)上面l层处的父节点即为目的节点(源节点)，则保存此路径上的各个节点，并为这些节点添加(1)中去掉的网络链路，将此外的一切节点和链路剪去.若源节点(目的节点)上面l层处的父节点不是目的节点(源节点)，则分别查找源节点和目的节点到协调器节点处的路径，将这两个路径连通，并为这个路径上的节点添加(1)中去掉的网络链路，将此外的一切节点和链路剪去.此步采用自适应策略，根据目的节点和源节点之间的路径自适应剪枝.

(3)利用AODVjr算法为剪枝之后的网络寻找源节点到目的节点的最佳路径.过程如图3所示.

图2 去掉同层节点间网络链路的ZigBee网络Fig.2 ZigBee network cleared away network link between horizontal nodes

(a) 选定源节点和目的节点 (b) 寻找源节点和目的节点之间的路径

3.2 能耗均衡策略

能耗均衡，即对于路由算法所寻得的路径，一方面要保证能耗较小，一方面要保证网络中每个节点的能耗均衡，避免由于部分节点剩余能量太低，引起网络分割，进而影响网络寿命.基于此，在3.1中描述的自适应剪枝策略的基础上提出能耗均衡策略.

假设源节点为ns，目的节点为ne，经过自适应剪枝之后，源节点和目的节点之间有k条路径，设第i条路径上的能量消耗为Cost(i)，其中i=1,2,…,k，第i条路径上剩余能量最低的节点的能量为Source(i).为了既保证所选路径消耗能量少，又保证各节点的能耗均衡，采用如下步骤进行路径选择：

(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)可以看出，路径的选择兼顾了路径的总能耗较低和路径中节点的能耗均衡.

4 实验与结果分析

为了验证算法的性能，基于NS-2模拟仿真软件对AODVjr路由算法和本文所提出的AP-ECB路由算法进行了仿真验证，网络中有路由器10个，终端30个，每个节点的总能量为1000J.图4为两种算法在网络整体能耗方面的对比，由于改进算法通过剪枝操作，有效地控制了被唤醒的节点的数目，因而能耗较小.

图4 AODVjr和AP-ECB路由算法在网络能耗方面的比较Fig.4 Comparation of AODVjr and AP-ECB routing algorithm in network energy consumption

图5为AODVjr路由算法和本文所提出的AP-ECB路由算法在死亡节点方面的比较，因为路由选择过程中直接放弃了剩余能量很低的节点，所以死亡节点的数目大大减少.另外，由于减少了访问节点的数目，相比AODVjr路由算法，AP-ECB路由算法大大降低了时间和空间开销.

图5 AODVjr和AP-ECB路由算法在死亡节点数目方面的比较Fig.5 Comparation of AODVjr and AP-ECB routing algorithm in death nodes numbers

5 结论

本文设计了一个基于ZigBee网络的AP-ECB路由算法.经过实验验证，可知该算法在能耗降低和网络寿命方面较AODVjr路由算法都有优势.AP-ECB路由算法采用的自剪枝策略可以快速去除无用的路径，将尽量多的节点设置为睡眠模式，有效地节约能耗；AP-ECB路由算法采用的能耗均衡策略兼顾了路径总能耗较少和路径上死亡节点较少，提高了网络的寿命，降低了网络被分割的可能性.该算法还可以扩展到其他网络中使用，提高其网络寿命.

[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网络节点的低功耗设计[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网络的设计与实现[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-)，女，副教授，研究方向：计算机系统结构，嵌入式系统，E-mail: wanghong_2010@foxmail.com

国家自然科学基金资助青年项目(61603420)；湖北省自然科学基金资助项目(2014CFB413)

TP274.5

1672-4321(2017)02-0129-04