认知视角下能量感知的ZigBee网络树型路由优化算法

滕志军， 张明儒， 张 力， 许建军

(东北电力大学 信息工程学院， 吉林 吉林 132012)



认知视角下能量感知的ZigBee网络树型路由优化算法

滕志军， 张明儒， 张 力， 许建军

(东北电力大学 信息工程学院， 吉林 吉林 132012)

为解决ZigBee Cluster-Tree路由算法路径选择不优的问题，提出了一种能量感知的ZigBee树型路由EZTR(Energy-Aware ZigBee tree routing)算法. 该算法利用每个节点感知的地址信息，按照ZigBee网络树型结构计算下一跳邻居节点到目的节点之间的跳数可避免网络的环路效应，通过引入认知概念，在跳数集合中选出最短路径以降低跳数. 在ZigBee网络节点能量的感知过程中，当所选路径存在低能量节点时，及时启用备用节点，从而避免节点因能量过度消耗成为失效节点. NS2(Network simulator version 2)仿真实验表明，EZTR算法可提高网络分组递交率，有效减少节点转发跳数和平均网络延时，减小网络整体能耗，为提高网络的实时性和延长网络生命周期提供理论支持.

无线传感器网络；认知；能量感知；ZigBee树型路由算法

以IEEE 802.15.4标准为底层技术的ZigBee技术具有高可靠性、低功耗以及低成本等优势[1-3]，广泛应用于电力系统、火灾预警、智能农业、智能交通、现代化军事以及智能家居等领域[4-6]. ZigBee树型路由ZTR(ZigBee Cluster-Tree routing)算法由于没有任何路由发现和低的存储耗能而被广泛应用，但选择路径不是最优的.

国内外学者对无线传感器网络路由算法研究较多，但是针对ZigBee网络树型路由算法研究较少. Taehong Kim等[7]提出了采用邻居表改进的最短ZigBee路由改进算法，利用ZigBee网络路由分配机制和父子节点之间的关系，选择出最短路径，但是选择的路径未考虑邻居节点的剩余能量和网络的拥塞程度，会造成网络传输的拥堵或者因节点过度消耗能量而成为失效节点. Wanzhi Qiu等[8]提出一种增强型的ZigBee路由算法，除利用父子节点之间的链路关系外，还利用一跳范围内的邻居表来寻找最短路径，同样存在未考虑节点的剩余能量问题. Atefeh Khatiri等[9]提出一种能量高效的路由(Energy shortcut tree routing，ESTR)算法，考虑通信链路的品质指示、跳数以及节点的忙碌状态，通过权重因子来综合加权选择最优路径，但权重因子不容易选择，很容易陷入局部最优. L.K. Wadhwa等[17]提出一种通过分担数据量多路径传输的优化ZigBee路由算法，在一定程度上虽然避免了网络的拥塞，但并未降低平均网络延时.

随着认知技术在无线传感器网络WSN(Wireless sensor network)中的应用逐渐扩大，MOUGY[10]和SULEIMAN Z等[11]提出的认知路由协议，已被用来提高网络性能. 传感器节点性能取决于处理、存储和能量3个因素，其中能量是最需要着重考虑的. 能量路由试图使能耗最小化，但一个节点可能同时被多条路径选择，可能导致其利用率过高，从而使得其为失效. 因此，本文在选择出最短路径的同时，还兼顾了节点的忙碌状态和节点的剩余能量，通过对ZigBee网络节点能量的认知过程，及时启用备用节点.

1 ZigBee路由算法

1.1 ZigBee地址分配机制

(1)

Ak=Ap+Cskip(d)·Rm+k. (1≤k≤Cm-Rm)

式中:Ai为ZigBee网络中协调器或路由节点分配给第i个路由节点的地址，Ak为ZigBee网络中协调器或者路由节点分配给第k个终端节点的地址.

1.2 Cluster-Tree路由算法

由ZigBee网络分配机制可知，ZTR算法数据传输方向可分为向上传输和向下传输，逻辑树结构如图1所示. 如果节点地址满足D

图1 逻辑树结构

1.3 邻居表

在ZigBee无线传感器网络中，单跳范围内可以直接相互通信的节点称为邻居节点，每个节点都维护其邻居表. 邻居表主要由邻居节点PAN标识符、邻居节点IEEE扩展地址、邻居节点网络地址、邻居节点的类型(RFD或FFD)、邻居节点与当前节点之间的关系以及邻居节点的剩余能量等组成[17]，其结构如图2所示. 由ZigBee路由分配机制可知，ZigBee树型路由算法只能向上或向下传输，虽然网络中存在节点邻居表，但是数据实际传输时并未充分利用其优势. 因此，本文借助邻居表进行路径选择，以降低平均网络延时，进一步提高ZigBee网络的性能.

图2 邻居表的结构

2 ZigBee网络树型路由优化算法

2.1 EZTR算法描述

由ZigBee路由分配机制可知，节点加入网络时会自动建立邻居表. 本文提出的算法在IEEE802.15.4标准框架下，利用节点感知地址信息和邻居表选择最佳路由策略，通过对ZigBee网络节点能量的认知，及时启用备用节点. EZTR算法的优化，不但降低节点的转发跳数，而且还保证了IEEE802.15.4标准的体系化. EZTR算法流程如图3所示.

当节点接收到数据包时，首先判断自己是否为目的节点，若是则直接接收数据，否则，根据节点维护的邻居表(含有节点地址信息、单跳范围内节点的关系、邻居节点的剩余能量等信息)判断目的节点是否为当前节点的子节点、父节点或邻居节点，若目的节点与当前节点是父子关系，直接按照树型结构向上或向下传递数据包，否则向下一跳节点发送带有目的地址的路由请求，采用轮询方式计算所有邻居节点到达目的节点的跳数，利用每个节点感知的地址信息选择最短路径. 若网络中存在多条最短路径，选取剩余能量最多的节点作为下一跳邻居节点. 判断在最少跳数的路径中节点是否为空闲状态，若路径中所有节点均处于空闲状态，选择此路径为最优路径；若在最优路径中存在能量过低的节点，使用备用节点代替，通过设置标志位(Flag)实现节点与备用节点间的替换. Flag=0表示能量过低的节点，Flag=1表示忙碌节点，Flag=2表示备用节点. 此后的中继节点转发也依据此方式进行，不断更新节点维护的单跳范围内的邻居表，直到数据发送到目的节点.

为了尽可能减小因备用节点影响ZigBee网络的拓扑结构，备用节点选取与原节点直接相邻的节点，即选择单跳范围内节点作为备用节点，同时为了避免备用节点再次成为失效节点，选取单跳范围内剩余能量最多的节点作为备用节点，采用轮询的方式将原节点的信息全部复制给备用节点. 如果在一段时间内没有收到“低能量节点” 请求消息或“节点忙碌”请求消息，则备用节点进入睡眠状态，降低因备用节点的存在而使网络付出更多的能量代价.

图3 EZTR算法流程图

图4以EZTR算法路由选择为例分析说明ZTR算法和EZTR算法的传输机制，其中实线代表ZTR算法的路由实现过程，虚线代表EZTR算法的路由实现过程. 从图中可以看出，与ZTR算法相比，图4(a)节省4跳，图4(b)节省5跳，图4(c)节省4跳. 由于传统的ZigBee路由算法完全按照父子之间的关系选择最短路径，所以转发数据需要公共父节点的参与，而EZTR算法利用邻居表和节点地址进行路径选择，不需要公共父节点的参与，因此降低了转发跳数. 另外，从图中也可以看出，越靠近最大公共父节点的节点转发数据越频繁，能量很快耗尽，从而很快就变为失效节点，可能造成网络的中断.

2.2 最佳路径的判断

利用每个节点感知的地址信息选择最短路径. 为了避免ZigBee网络的环路响应，该算法通过树型结构来计算下一跳节点到目的节点之间的路由开销.

节点跳数的计算方法为：找到最大的公共父节点的地址，然后借助最大公共父节点的深度计算EZTRN节点到目的节点之间的跳数，如图5所示. 跳数计算公式和最少跳数选取公式分别为

Count=(Nd-Do)+(Dd-D0)=Nd+Dd-2D0,

min_count=min{counti}, i∈{1,2,3,…,n}.

式中：count为跳数，Nd为邻居节点的深度，Dd为目的节点的深度，D0为最大公共父节点的深度，最少跳数为min_count，counti为第i条邻居节点到目的节点转发跳数. 其中寻找最大公共父节点的方法为：根据ZigBee路由分配机制，当节点的深度小于网络最大深度(Lm)时，依据式(1)采用轮询的方式来实现.

(a)邻居节点的父节点

(b)邻居节点的子节点

(c)在邻居节点的邻居表中

2.3 低能量节点判断

在WSN实际应用中，某些节点(如图4中最大公共父节点附近的节点)频繁使用，导致能量过度消耗，而其他节点被闲置，会造成节点能量不均衡，因此部分节点因过早失效而引起在最优路径下的“能量空洞”现象，可能会导致网络数据传输中断或出现网络拥塞现象.

图5 源节点和目的节点之间的路由消耗

Fig.5 Routing consumption between the source node and the destination node

式中:E0为节点的初始能量，di为网络中第i个节点的深度.

3 仿真及分析

3.1 搭建ZigBee能量模型

ZigBee网络数据传输的总能耗E包括ET(k，d)为节点A发送k bit数据包到节点B所需能耗和ER(k)为节点B接收k bit数据包所需能耗，d为两个节点之间的通信距离. ZigBee能量模型如图6所示.

节点发送k bit 数据包消耗的能量为

式中:Eelec为发射电路发送1 bit数据包的能耗，εamp为发射放大器处理1 bit数据包传输单位距离所需要的能耗. 假设接收电路与发射电路有相同的能量消耗，则接收k bit数据包的能量消耗为

采用此模型，则一个路由节点的总能耗为

式中M和dm分别是路由节点的跳数和第m跳的发送距离.

图6 能量模型

3.2 评价指标定义

式中: Ri表示第i个节点成功接收的数据分组的个数，Sk表示第k个节点发送数据分组的个数.

式中: NMAC为MAC层转发N个数据包，因为MAC层的作用是确认数据传送和接收; Msour为源节点发送M个数据包.

式中:Tr(i)为接收第i个数据包的时刻，Ts(i)为发送第i个数据包的时刻，Mdes为目的节点成功接收M个数据包.

式中: Ei为第i个节点剩余能量，E0为ZigBee网络中M个节点的初始能量.

3.3 NS2.35仿真参数设置

为了验证EZTR算法的性能，利用IEEE 802.15.4 PHY/MAC协议进行ZTR(经典的ZigBee树型路由)、EZTR(本文提出的优化树型路由)以及参考文献[9]提出的ESTR(能量高效的树型路由)进行网络层协议仿真. 将节点随机分布在100 m×100 m区域中，使用cbrgen产生CBR数据流，实验发送数据包的大小为70 bytes，CBR数据流的带宽为1 Mbit/s.

实验采用表1所列的节点仿真参数，利用awk测试脚本提取Trace文件中的节点数据. 仿真动画效果如图7所示. NAM动画仿真之后，自动生成一个以.tr为格式的trace跟踪文件，该文件可以记录ZigBee节点整个通信过程，使用AWK语言获取需要的数据信息.

表1 节点仿真参数

图7 仿真动画

3.4 仿真结果及分析

分组递交率随节点数目的变化曲线如图8所示. EZTR在分组递交率方面优于ZTR和ESTR，EZTR、ZTR及ESTR的整体分组递交率分别为85.64%、71.81%及80.30%，相应提高了13.83%和5.34%，主要是由于本文提出的EZTR算法考虑了链路的忙碌状态和节点的剩余能量，如果存在能量过低的节点，有可能造成丢包现象；如果链路处于忙碌状态，EZTR算法引入备用节点，避免因数据堵塞而造成丢包现象. 其次，该算法按照树型结构计算路由跳数，避免了网络的环路响应. 最后，EZTR算法选择的路径是最短的，减少了队列的延时，一定程度上也提高了网络的分组递交率.

图8 节点的平均分组递交率随节点数目变化

节点的平均跳数随网络节点数目的变化曲线如图9所示. 随着传感器节点的不断加入，网络拓扑结构越复杂. 3种算法的转发跳数均增加，但是ZTR算法跳数远多于ESTR和EZTR算法，EZTR、ZTR及ESTR的整体跳数分别为4.99、6.92及5.39，相应降低了27.78%和7.42%. 由于EZTR算法在确保链路为空闲状态传输数据和采用备用节点的前提下，选择EZTRN节点到目的节点最少跳数，因此采用EZTR算法转发跳数低于ZTR和ESTR的跳数.

图9 节点的平均跳数随节点数目变化

随着传感器节点数目的增加，不但节点跳数增加，平均网络延时也不断增加. 3种算法的平均网络延时随网络节点数目变化曲线如图10所示. 从图10可以看出，由于EZTR算法不但考虑转发跳数和链路忙碌状态，还较大幅度地减少转发跳数，虽然在一定程度上因增加算法的复杂度导致程序运行时间增加，但该算法优化节点传输的路径，在实时性方面仍然优于ZTR和EZTR算法，EZTR、ZTR及ESTR的整体时延分别为0.017、0.031及0.022，相应降低了45.01%和22.68%，提高无线传感网络在线监测的实时性.

图10 平均网络延时随节点数目变化

节点平均剩余能量百分比随节点数目变化如图11所示. EZTR、ZTR及ESTR的整体剩余能量百分比分别为0.79、0.67及0.74，相应提高了19.85%和6.75%，主要是由于EZTR算法大幅度降低了节点的转发跳数，虽然一定程度上增加了因算法复杂度提高而消耗一部分能量，但是由于该算法优化了节点转发路径，总体上仍然节约ZigBee网络的能耗.

图11 节点平均剩余能量百分比随节点数目变化

Fig.11 The average percentage of residual energy with the number of nodes changes

为了客观公正的评价EZTR算法的性能，对ZTR算法和EZTR算法在路由控制开销方面进行了仿真实验，路由控制开销仿真结果如图12所示. 从图中可以看出，ZTR算法没有任何路由控制开销，是因为ZTR算法在数据通信时只根据父子节点之间的关系进行数据的传递. ESTR算法与EZTR算法相比，在寻找最优路径时，由于需要额外考虑链路品质因数和合理选取综合加权因子等因素，路由控制开销多于EZTR算法.

图12 路由控制开销随节点数目的变化

4 结 论

本文利用单跳范围内的邻居节点和父子节点之间的关系，在认知视角下提出一种能量感知的ZigBee树型路由(EZTR)算法. 该算法不但在IEEE802.15.4标准体系化框架下能够选出最短路径，还兼顾了节点的忙碌状态和节点的剩余能量，通过对ZigBee网络节点能量的认知，当网络中所选路径存在低能量节点时，及时启用备用节点. NS2仿真结果表明，EZTR算法的性能优于ESTR、ZTR算法. 由于经典的树型路由(ZTR)算法在数据传输时只在父子节点之间进行数据传输，无任何路由控制开销，而EZTR算法需感知最短路径，与ZTR算法相比需要付出增加路由控制开销和占用传输带宽等代价，同时会增加节点的存储和计算能力，该算法的性能还有待于进一步优化.

[1] 庞毅,王超,孙青林,等. Zigbee网络环状分层方法的仿真与实现[J].哈尔滨工业大学学报,2013,45(3):123-128.

PANG Yi,WANG Chao,SUN Qinglin,et al. Simulation and realization of zigbee network annular stratification[J]. Journal of Harbin Institute of Technology,2013,45(3):123-128.

[2]张云洲,蒋培,高亮,等.基于DSP和双目视觉的多媒体传感器网络节点设计与实现[J].通信学报,2014,35(12):210-216.

ZHANG Yunzhou,JIANG Pei,GAO Liang,et al. Design and implementation of wireless multimedia sensor network node based on DSP and binocular vision[J]. Journal on Communications,2014,35(12):210-216.

[3] SHARIFF F, RAHIMA N A, HEW W P. Zigbee based data acquisition system for online monitoring of grid connected photovoltaic system[J]. Expert Systems with Applications,2015,35(42):1730-1742.

[4] SANG Shengbo,FAN Xiao,TANG Xiaoliang,et al. Portable surface stress biosensor test system based on ZigBee technology for health care[J]. Biotechnology & Biotechnological Equipment,2015,45(29):798-804.

[5] NIU Jianwei,WANG Bowei,SHU Lei,et al. An energy-efficient indoor localization system using ZigBee radio to detect WiFi fingerprints[J]. Selected Areas in Communications,2015,33(7):1431-1442.

[6] ChEN S K,KAO T,CHAN C T,et al. A reliable transmission protocol for ZigBee-based wireless patient monitoring[J].IEEE Trans Information Technology in Biomedicine,2012,16(1):6-16.

[7] KIM T, KIM S H,YANG J,et al. Neighbor table based shortcut tree routing in ZigBee wireless networks[J]. IEEE Transcations on Parallel and Distributed Systems,2014,25(3):706-715.

[8] QIU Wanzhi,PENG Hao.Enhanced tree routing for wireless sensor networks[J]. Ad Hoc Networks,2009,39(7):638-650.

[9] KHATIRI A, MIRJALITY G. Energy Efficient Shortcut Tree Routing in ZigBee Networks[C]//Communication Systems and Networks,2012 Fourth International Conference on Computational Intelligence. Harbin: ACM, 2012:117-122.

[10]MOUGY A E,EI Z H,IBNKAHLA,M. Cognitive approaches to routing in wireless sensor networks[C]//IEEE Global Telecommunications Conference.2010.

[11]SULEIMAN Z,NORSHEILA F. Reliable geographical forwarding in cognitive radio sensor networks using virtual clusters[J]. Sensors,2014,14(5):8996-9026.

[12]钱志鸿,朱爽,王雪.基于分簇机制的ZigBee混合路由能量优化算法研究[J].计算机学报,2013,36(3):485-493.

QIAN Zhihong,ZHU Shuang,WANG Xue. An cluster-based ZigBee routing algorithm for Network energy optimization[J]. Chinese Journal of Computers,2013,36(3):485-493.

[13]HUANG Y K,PANG A C,HSIV PC,et al. Distributed throughput optimization for ZigBee cluster-tree networks[J].IEEE Trans. Parallel and Distributed Systems,2012,23(3):513-520.

[14]KIM T, KIM D,PAK N,et al. Shortcut tree routing in ZigBee networks[C]//2007 2nd International Symposium on Wireless Pervasive Computing. 2007:42-47.

[15]YANG Guisong, WANG Zhongjie, WU Chunxue, et al. One-hop expansion ETR protocol for wireless sensor networks[J].Journal of Convergence Information Technology,2012,7(11):169-178.

[16]KWON K, HA M, KIM T, et al. The stateless point to point routing protocol based on shortcut tree routing algorithm for IP-WSN[C]//Proceedings of 2012 International Conference on the Internet of Things. 2012:167-174.

[17]WADHWA L K,RASHMI R S,PRIYE V.Extended shortcut tree routing for ZigBee based wireless sensor network[J]. Ad Hoc Networks,2016,37(2):295-300.

(编辑 王小唯 苗秀芝)

Energy-aware tree routing optimization algorithm for ZigBee networks: a cognitive perspective

TENG Zhijun，ZHANG Mingru， ZHANG Li，XU Jianjun

(School of Information Engineering, Northeast Dianli University, Jilin 132012, Jilin, China)

To improve the problem of failing to well select optimal path for ZigBee Cluster-Tree routing algorithm, ZigBee routing based on Energy-Aware (EZTR) algorithm was proposed. Firstly, using each node perceiving its own address, this algorithm calculated packet forwarding hop-counts that the next hop of node to destination node according to tree structure for avoiding the loop response, by introducing the concept of cognitive for ZigBee network, and selected the shortest routing in hop-counts set to reduce hop-counts. Besides, in order to avoid excessive energy consumption of nodes, which caused nodes to be ineffective, through energy cognitive processing, when there is a low energy nodes selected path, EZTR algorithm timely adopted alternate node. Through comparative analysis of NS2 simulation experiments, packet delivery ratio is improved, hop-counts and average delay are reduced, and network energy consumption is saved, which can provide theoretical support for improving network real-time and extend network lifetime.

wireless sensor network; cognitive; energy-aware; ZigBee tree routing algorithm

10.11918/j.issn.0367-6234.2016.11.017

2015-12-11

国家自然科学基金(51277023)

滕志军(1973—)，男，博士，教授

张明儒，894205629@qq.com

TP393.1

A

0367-6234(2016)11-0109-07