一种降低节点能量开销的ZigBee路由算法优化

焦慧平 孔国利

摘 要： 为解决ZigBee网络由于不合理的路由策略导致节点能量浪费和网络陷入局部死亡的问题，提出一种降低节点能量开销的ZBR路由算法。所提ZBR优化算法在路由发送阶段，利用节点自动维护的邻居表信息，优先实现两跳路由传输；在路由发现过程中，根据最大传输跳数和节点间的父子关系，控制ZigBee网络中RN+节点RREQ分组的洪泛，减少能量浪费；在路由选择时，设计节点能量标志位和能量感知的路由成本函数，减少能量偏低节点的使用概率，降低网络开销和提高节点生存率。通过与原ZBR算法及其他几种改进ZBR算法进行剩余能量和节点生存率对比仿真实验，结果表明：改进的ZBR算法的平均剩余能量提高了7.74%，在网络运行80 s时节点生存率提高了20.29%，也高于其他几种改进ZBR算法，该算法可有效减少网络能量消耗，大大提高节点生存率。

关键词： ZigBee网络； 路由策略； 能量开销； 能量标志； 节点生存率

中图分类号： TN926?34； TP393.2 文献标识码： A 文章编号： 1004?373X（2016）08?0068?04

Optimization of a ZigBee routing algorithm for reducing node energy consumption

JIAO Huiping， KONG Guoli

（Information Engineering College， Zhongzhou University， Zhengzhou 450044， China）

Abstract： Due to unreasonable routing algorithm， the ZigBee networks encounter node energy over?consumption and partial death. To solve these problems， a ZigBee routing（ZBR） optimization algorithm for reducing node energy consumption is proposed. The proposed ZBR optimization algorithm， in the routing delivery stage， makes use the nodes to maintain neighbor table information automatically， and takes priority for a two?hop routing transmission； in the discovery process of routing， controls the RREQ packet of RN+ node to reduce energy dissipation according to the maximum hop number and the father?son relationship among the nodes； during routing selection， adds energy flags to the RN? node to reduce the transmission probability of low energy nodes and utilizes an energy?aware routing cost function designed to cut down the network energy cost and improve the node's survival rate. Compared with the original ZBR algorithm and several other improved ZBR algorithms of the residual energy and node survival rate in the simulation experiment， the average remaining energy of the improved ZBR algorithm is increased by 7.74% and the node survival rate is increased by 20.29% in 80 s running of the network. The algorithm can effectively reduce the network's energy consumption and improve node's survival rate.

Keywords： ZigBee network； routing strategy； energy expenditure； energy flag； node survival rate

0 引 言

ZigBee是一种短距离、低功耗和低速率的无线通信技术，ZigBee网络节点主要依靠电池供电，由于节点体积小，节点的能量十分有限[1]，所以降低网络能耗是解决阻碍ZigBee网络应用发展的关键。ZigBee无线网络根据拓扑结构的不同主要采用AODVjr路由和Cluster?tree路由两种算法[2]。Cluster?tree算法是静态路由算法，由簇树之间的父子关系进行路由，但路由效率较低，能量开销和服务时延较大。AODVjr算法则通过大量洪泛来寻找最优路由路径，其路由开销较大。ZBR（ZigBee routing）算法结合了两种算法特性，以求满足不同的应用需求，是当前最适用于ZigBee无线网络的算法[3?4]。此外RFD节点因不具有路由功能，由其父节点完成路由，但是由于AODVjr和Cluster?tree两种算法的固有不足，ZBR算法在能量效率和负载控制方面还有较大改进空间。

为了解决ZBR算法存在网络能量消耗大和节点死亡率高的问题，班艳丽等将节点临界能量机制引入到ZigBee路由算法中[5]，且控制RREQ的大致传输方向，减少死亡节点数，降低网络能量消耗，算法完全避免使用低能量节点进行路由转发，但全由RN+节点组成的传输路径却不一定是最优路径。张擎等在对Cluster?tree结构进行改进以节省路由开销和均衡负载[6]，之后对RREQ和RREP分组处理，以保护能量偏低节点；然而该方案缺乏对RN-节点相应的改进。Taehong K等考虑路由成本提出了利用邻居表建立短路径路由协议算法[7]。

本文首先分析了ZBR算法中RN+，RN-节点采用算法存在的缺点，然后提出了一种改进的ZBR路由算法。改进方案通过利用邻居列表完成两跳范围之内的传输和对RN+节点RREQ冗余分组的减少和丢弃，减少了网络能量的浪费。此外，在RN-节点设置能量标志位，以减少RN-节点的使用概率，延长网络的整体寿命。

1 ZBR算法存在的问题

RREQ分组冗余：AODVjr算法采用广播通信机制，虽然可以找到最短路径，但AODVjr算法在路由发现过程中会产生大量的RREQ分组。随着网络规模的增加，这些RREQ分组数量显著增加。大量的RREQ分组为了降低分组传输时延，提高分组递交率，在ZigBee网络中形成洪泛。部分RREQ分组的寻址范围超过网络的最大跳数，当传输次数达到时会被节点丢弃，造成网络能力的浪费。此外，现有RREQ分组的路由方法没有考虑簇树的父子关系，形成冗余洪泛。冗余RREQ分组会浪费网络能量，降低网络整体能量消耗可通过降低RREQ分组洪泛开销来实现。

能效不均衡的路由策略：RN-节点虽然采用Cluster?tree算法节约了能量，但能量偏低的RN-节点如果继续被频繁用于数据传输，当能量耗尽时会成为死亡节点。在网络运行后期，当节点能量普遍不足时，RN-节点将变为RN+节点参与路由，但死亡节点无法转变，其他节点传输数据时必须绕过死亡节点，造成能量浪费，所以在路由时应尽量降低RN-节点作为传输节点的概率。

缺乏高效的邻居节点路由：RN+，RN-节点为路由节点，都自动存储维护一张邻居表，拥有离自己一跳距离的相邻节点信息，如果目的节点可以通过源节点的邻居节点传输，则可以通过使用邻居表减少能量消耗[8]。网络节点分布如图1所示。从图1中可看出，若不考虑邻居节点的使用，节点7到节点10的数据传输路径为7?4?0?3?10，若使用邻居节点，数据传输路径为7?12?10，缩短了路由路径，且避免广播RREQ分组，降低网络能量消耗，但原ZBR算法却忽略了邻居表的使用。

本文针对ZBR算法的三个主要问题，提出各自的解决方案，达到降低网络功耗、提高节点生存率的目的。

图1 邻居节点路由

2 降低节点能量开销的ZBR路由算法

2.1 基于邻居表的两跳传输机制

网络在初始化时每个RN+，RN-节点都更新维护自己的邻居表信息。邻居表存储内容如表1所示。

表1 邻居表格式

在图1中，节点4的邻居表存储其邻居节点1，3，7，13的相关信息。在寻找目的节点时，RN+，RN-节点都应首先充分使用邻居表，避免开启路由发现时洪泛RREQ寻址消耗能量。具体机制为：如果目的节点在邻居表内，就直接转发分组到目的节点，如果将数据从节点4发给目的节点3，只需一跳传输即可发送数据。如果与目的节点存在共同节点，则将数据发送给共同节点，然后由共同节点将数据转发给目的节点，在两跳范围内完成数据传输，如路径7?12?10。

2.2 RN+节点中RREQ冗余分组的处理

RN+节点在数据传输时存在冗余RREQ分组，其中一种冗余产生的原因是由于RREQ分组的传输跳数超过了ZigBee网络的最大传输跳数。最大传输跳数定义为源节点到目的节点的深度之和：

[L=d+d0-2dc] （1）

式中：d为源节点深度；d0为目的节点深度；dc为源节点与目的节点的公共父节点的深度。当RREQ分组的寻址范围大于[L]，该分组会在传播次数耗尽时丢弃，而对寻找目的节点没有意义，浪费网络能量。此类RREQ分组的大量洪泛还会引起网络拥塞现象，因此，当节点收到此类RREQ分组时应立即丢弃。

另外一种冗余RREQ分组的产生的原因是RN+节点采用广播通信机制时没有考虑网络中存在的父子关系引起的。并不是所有的邻居节点都能寻找出最优路径，因此需要对RREQ分组进行定向，去除冗余RREQ分组[9]。

2.3 能量标志位

为防止RN-节点被过度使用而使节点死亡，改进的ZBR算法在RREQ分组中加入能量标志位E?flag。能量标志位表示当前分组的传输路径中存在RN-节点。将E?flag置为1，表明路径中存在能量偏低节点，路由选择算法应该避免使用低能量节点。避免使用低能量节点之后，ZBR算法还需要进一步优化，以提高全网能量使用效率。原ZBR算法中，路由成本函数考虑了跳数，剩余能量和链路质量，能够很好表征路径的能量效率。路由P的成本为：

[C（P）=i=1L-1TC[Di，Di+1]] （2）

式中：TC{[Di，Di+1]}为节点Di到Di+1链路成本；L为链路最大长度。链路成本的函数表达式如下：

[TCl=7min（7，round（1P4l））] （3）

考虑节点剩余能量对路径选择的影响，提高网络整体有效寿命，本文方案设计了能效优化的链路成本函数Pl，定义Pl如下：

[Pl=α·LQI+β·REnergy] （4）

式中：α，β（0≤α，β≤1，α+β=1）为固定系数，用来权衡每个影响因素的重要性；[LQI]是MAC层和PHY层所提供的每一帧的LQI的平均值；REnergy则表示节点剩余能量。由于改进的路由成本函数考虑了节点的剩余能量，使得路径中含有低能量节点的路由成本增加。在路由选取阶段，含有低能量节点的路由能够以较低的概率被使用，避免了低能量节点被过度使用导致网络死亡。

因此，当目的节点收到RREQ分组后，查看其能量标志位。若能量标志位为1，表明路径中含有能量偏低的RN-节点。此时，应当优先选择能量标志位为0的路径进行传输。其次，在能量标志位为1的路径集合中选择路由成本最低的路径进行传输。由于路由成本公式考虑了节点剩余能量的影响，含有RN-节点的路径代价增大，降低其被选中概率。

2.4 改进ZBR算法路由策略

改进算法的路由策略主要分三个阶段，分别为查询邻居表阶段、RREQ寻址阶段和目的节点选择路径阶段。节点处理RREQ分组的过程如下：

Step1：当一个分组到达节点时，该节点查找邻居表。若存在目的节点，则直接转发给目的节点；若与目的节点存在共同节点，则定向发送给共同节点。

Step2：通过Step1无法寻址到目的节点时，节点开启路由发现，转发RREQ分组前待转发节点首先判断与目的节点父子关系，而后RN+和RN-节点根据自己的功能特性转发RREQ分组。若在转发节点的后裔簇树中存在目的节点，则转发节点将RREQ分组递交到该后裔簇树的根节点。否则该分组信息转发到转发节点的父节点处理。另外RREQ分组到达一个不具有路由功能的RFD节点时，该分组直接被递交回该RFD节点的父节点。

Step3：ZigBee网络中等待路由时间是由中心协调器设置，一般为某个常数，超过设置的时间则停止等待[10]。等待时间结束后，目的节点会收到来自不同路径的RREQ分组。目的节点首先根据能量标志位E?flag进行路由分类，在E?flag为0的路由中选择路由成本最小的路径进行数据传输。由于从式（4）中得出，剩余能量越大的路由成本越小。因此该路由选择算法能够达到降低能量节点传输数据的概率，延长节点寿命的目的。

以上改进算法在路由传播阶段，针对节点的能量状况，在RREQ分组中添加E?flag标志位，避免能量偏低的过度使用，提高节点生存率，延长网络寿命。在路由发现阶段，对RREQ分组根据最大跳传输限制进行丢弃，然后对剩余RREQ分组根据簇树结构的父子关系进行定向传播，避免过多RREQ分组洪泛的产生。在路由选择阶段，路由成本由式（4）计算，公式简单，且可由各节点独立计算完成。假设邻居节点个数为n，各节点查找邻居表时，算法遍历每个邻居节点，算法的时间复杂度为O（n），算法可在多项式时间内完成。

3 仿真实验结果

为验证改进算法的性能，通过系统仿真对网络的关键性指标进行考察。网络仿真平台使用开源的NS2，平台实现了IEEE 802.15.4协议的PHY层和MAC层。整个网络范围设置为100 m×100 m，信息源采用CBR作为数据信息源，网络节点数为100，节点一跳传输距离为15 m，节点初始能量10 J。

仿真主要通过文献[5]和文献[6]提出的改进ZBR 路由算法和本文提出的改进ZBR算法、原ZBR算法在网络能量消耗和节点生存率上进行对比分析。

3.1 剩余能量

仿真实验中，节点剩余能量与时间的关系如表2所示。从表2可以看出，本文提出的改进ZBR算法利用了节点自身维护的邻居表寻址目的节点，通过邻居表能找到目的节点将能大大降低网络能量消耗，而原ZBR算法和文献[5]却忽略了邻居表的使用，所以能量消耗比ZBR和文献[6]大。再者，本文的改进ZBR算法降低了RREQ分组引起的能量浪费，虽然文献[5]和文献[6]也控制了RREQ分组的冗余，但对于能量偏低的RN-节点却没有相应的改进。而改进ZBR算法利用公式（4）降低RN-节点参与路由转发的概率，减少RN-节点死亡引发的网络能量浪费现象。由表2数据得出，改进的ZBR算法降低了网络能量消耗，比原ZBR算法的平均剩余能量提高了7.74%，且始终高于文献[5]和文献[6]的两种改进算法。

3.2 节点生存率

节点生存率为网络可用节点率。如果一个节点的剩余能量低于初始能量的3%，则被看作是死亡节点。网络运行结束后，计算生存节点个数。节点生存率公式为：

[λ=NableNtotal×100%] （5）

式中：Nable是网络运行结束后生存节点个数；Ntotal是网络总节点个数。四种算法的仿真实验结果如图2所示。

在网络运行初期，节点能量充足，节点生存率降低幅度不大。在网络运行后期，节点能量普遍不足，节点死亡速度加快，各算法的节点生存率下降幅度都有所增大，原ZBR算法下降幅度最为明显。本文改进ZBR算法首先通过控制RREQ分组的冗余降低了RN+节点的能量消耗，延长了RN+节点退化为RN-节点的时间；其次，算法降低了RN-节点被使用的概率，减少了RN-节点的死亡几率。图2表明改进ZBR算法在网络运行80 s时节点生存率比原ZBR算法提高了20.29%，且始终高于文献[5]和文献[6]的两种改进算法。

4 结 语

ZigBee是一种易部署和适应性强的短距离无线通信技术，但因其使用电池供电，常常由于不合理的路由算法导致网络过早死亡。为此，本文从利用邻居表两跳传输优先、设置能量标志位和能量感知的路由成本函数和根据节点的父子关系减少RREQ分组冗余三个方面着手，提出了能量均衡的改进ZBR路由算法。在开启路由发现过程前充分使用节点邻居表，减少网络发送寻址RREQ的能量消耗，提高网络能量利用效率。在路由发现阶段，利用父子关系控制RREQ分组的转发取向，减少RREQ分组洪泛带来的能量损耗。在路由选择阶段，利用能量标志位和能效感知的路由成本函数均衡全局节点剩余能量。通过仿真实验，改进的ZBR算法比原ZBR算法的平均剩余能量提高了7.74%，在网络运行80 s时的生存率提高了20.29%，也高于引用文献中的方法。

参考文献

[1] 李小龙，彭美平.基于OPNET的改进型Zigbee传感器网络仿真系统[J].江苏大学学报（自然科学版），2012，33（6）：671?677.

[2] 楼亮亮，周苗，何为，等.基于ZigBee协议OTA技术的改进方法研究[J].现代电子技术，2014，37（23）：1?4.

[3] 穆嘉松，刘开华，史伟光.ZigBee网络中基于节点移动性的路由选择策略[J].天津大学学报（自然科学与工程技术版），2012，45（4）：301?308.

[4] 吴许俊，王永利.基于两跳邻居的ZigBee网络借地址分配算法[J].科学技术与工程，2013，13（28）：8333?8338.

[5] 班艳丽，柴乔林，王芳.改进的ZigBee网络路由算法[J].计算机工程与应用，2009，45（5）：95?97.

[6] 张擎，刘淑美，柴乔林.能量高效的zigbee网络改进路由策略[J].计算机工程，2010，36（7）：108?111.

[7] TAEHONG K， DAEYOUNG K， NOSEONG P， et al. Shortcut tree routing in ZigBee networks [C]// Proceedings of the 2nd International Symposium on Wireless Pervasive Computing. [S.l.]： ISWPC， 2007： 42?47.

[8] 陈建锐，何增颖.基于动态优化因子的Zigbee协议优化仿真算法[J].计算机仿真，2013，30（7）：272?275.

[9] 钱志鸿，朱爽，王雪.基于分簇机制的ZigBee混合路由能量优化算法[J].计算机学报，2012，36（3）：485?493.

[10] 刘丽君，陈志奎.一种适用于密集传感器网络中的DV?Hop改进算法[J].微电子学与计算机，2010，27（7）：190?193.