能量高效的ZigBee路由算法

邓宇，徐思燕

（西华大学计算机与软件工程学院，成都　610039）

能量高效的ZigBee路由算法

邓宇，徐思燕

（西华大学计算机与软件工程学院，成都610039）

传统ZigBee网络路由协议中没有保护剩余能量低的节点，在路由发现中进行广播RREQ等问题。考虑传播路径上的能量消耗，RREQ的发送方向，节点之间的邻居关系，提出一种基于能量的高效路由算法，算法仿真结果表明，改进后的算法有效地减少RREQ的发送数量，增加节点的存活率，延长网络的生存时间。

ZigBee网络；RREQ；路由算法；能量；仿真

0　引言

ZigBee是一种低成本、低速率的短距离双向无线通信新技术，该技术物理层和MAC层主要是基于IEEE802.15.4标准，网络层通过ZigBee联盟制定。在医疗、军事、监控、智能家居、工业控制、环境监测等领域得到了广泛的应用［1］。由于ZigBee网络节点能量限制，所以网络拓扑结构和网络的路由策略的选择，对于整个ZigBee网络的有效性起着至关重要的作用。

在ZigeBee网络中，主要采用Cluster-Tree和AODVjr算法相互结合的策略来完成转发操作。Cluster-Tree算法是静态算法，通过节点之间的拓扑关系来进行转发过程，不需要存储路由表，但是数据在转发选择中并非是最优的路径，而是严格按照拓扑关系进行转发，缺少相应的灵活性和伸缩性。AODVjr算法是在传统的AODV算法中改进来的，可以通过广播请求来进行路由查找和路由维护。但由于两个算法固有局限，使得原有的算法在路由发现、均衡网络负载、能量消耗等方面存在不足。

本文以节省能量和减少网络广播为主要目标，对路由算法进行分析，改进原有的AODVjr路由发现过程，使得在路由过程中能节省能量、减少RREQ广播、延长网络生存时间。

1　ZigBee网络层路由通信原理

1.1Cluster-Tree及地址分配

ZigBee网络把节点分为了协调器、路由节点、终端节点三种类型。网络地址是16位的，最多可以分配65536个节点，假设每个父节点最大可接纳的子节点数为Cm，可接纳的最大的路由节点数为Rm，以及网络的最大深度为Lm［2］，经过分布式的地址分配策略，可以根据公式（1）计算出深度为d的父节点为其子节点（路由节点和终端节点）预留的地址偏移量Cskip，根据子节点的类型，采用的分配方式也有一定的区别［1］。

如果子节点是第n个新加入的路由节点，父节点为其分配的路由地址通过公式（2）计算。

父节的地址为Ap，如果子节点是第n个新加入的终端节点，父节点为其分配的路由地址通过公式（3）计算。

在该路由算法中，源节点到目的节点下一跳的方向通过目的节点网络地址计算出来。源节点先需要判断和目的节点的关系，判断后再进行下一跳的路径的选择，若目标节点是源节点的子节点，直接转发给目的节点。否则将源节点的数据转发给父节点，通过父节点来进行转发的接力。

1.2AODVjr及其路由选择

AODVjr路由分为路由发现和路由维护两个过程。

RREQ：主要是在发起路由的功能，通过广播该分组，询问收到该分组的节点是否知道到达目的节点的路由。

RREP：该分组只能由目标节点进行回复，RREP分组的传送路径为路由建立过程中的反向路由，产生从源节点到目标节点的可靠路由。

2　改进的路由算法

AODVjr是一种改进的AODV算法，AODVjr路由的基本原理就是通过广播RREQ来实现按需的路由发现的功能，最早到达目标节点的RREQ回复做出响应，可以避免造成路由环路，选出路径。但是传统的AODVjr在路由发现时候是广播RREQ，并未根据网络的拓扑结构选择合适的方向，可能造成网络在某种程度上拥塞和网络带宽等资源的浪费［3］。

由于AODVjr算法存在不同程度的缺陷，为了获取更好的网络生存时间和网络数据传输效率，充分利用节点的能量划分，本文提出一种基于能量的高效路由算法，分别通过邻居表和路由发现两方面进行改进。

2.1邻居表

每一个节点加入ZigBee网络都维护自己邻居点的信息，记录着本节点与其他节点已存在的路由信息。邻居表是由每一个ZigBee节点自动维护的，所以如果能在发起路由请求之前通过邻居表寻址目的节点，将会避免路由发现等流程，能降低网络能量的消耗和避免网络的拥塞［4-5］。

路由节点在发起路由发现过程前，先执行对邻居表的扫描，实现通过邻居表搜索目的节点的功能。

2.2路由发现策略

如果目标节点不在邻居表的范围内，那么就需要开启路由发现过程。通过广播到目的节点的RREQ分组来实现最短路径的查找，在路由发现过程中，有一些节点的频繁使用一段时间后，节点的能量耗尽，造成网络一定程度分割，节点就需要通过路由维护来重新查找路由的路径，这样会加重网络的延迟和网络负担加重［4-5］。为了避免网络节点过度使用和降低网络的能量消耗，在路由发现时，解决如下两个问题：（1）尽量避免使用能量低于阈值线的节点；（2）控制RREQ传播方向。这样既能保护剩余能量较小的节点，也能降低网络的能量消耗。

设节点的能量为E，初始能量为Eo，当E＞=30%Eo的时候节点才参与RREQ的转发。否则当低于阈值时候，收到RREQ直接抛弃。

由Cluster-Tree的传播特性可知，若已知目的节点为当前节点的父节点，将分组向当前节点的子节点传播是消耗节点能量，只会增加网络的拥塞和浪费网络的能量、带宽。因此在节点转发分组前，如果能事先进行判断目的节点的方向，则可以减少网络中的冗余的RREQ发送，避免网络资源的浪费。

当前节点在对收到的RREQ进行转发前，先通过下面的伪代码判断RREQ往下的传播方向：

节点I收到其他节点发送给它的一个RREQ路由请求分组后，对RREQ的处理执行如下伪码：

路由具体流程如下图：

图1　

图2　节点存活率

3　仿真验证

为了评估改进后的算法性能，本文利用NS-2，对改进前后的路由算法进行仿真。在仿真环境中，网络大小设置为120m×120m，节点数为100，数据包的类型为CBR，初始能量为100J，数据流大小为50Byte，Cm=4、Rm=4、Lm=5，总仿真时间为400s。

图1对算法改变前后的节点存活率进行了比较分析，可以看出改进后的算法在节点存活率上优于传统的算法。

图3对算法改变前后的RREQ发送数量进行分析，可以看出改进后的算法在发送RREQ包上有明显的减小，降低了网络风暴，延缓了网络的分割。

4　结语

本文为了减少RREQ的发送数量、增加节点存活率、提高ZigBee网络效率，提出一种基于能量的高效路由算法，该算法可以根据邻居表选择路径，计算请求路径上的节点剩余能量作为阈值线，考虑路径上的能量因素，改进原有RREQ传播方向，仿真结果证明，改进后的算法有效地减少了RREQ的发送数量，提高了节点的存活率，延长网络的生存时间。

图3　RREQ发送对比图

［1］刘兆孟，吴锡生.能量高效的ZigBee路由算法.计算机仿真，2013-09-15

［2］王琛，柴乔林，王芳.基于树形结构的ZigBee能量均衡协议研究.计算机工程与设计，2009-08-16

［3］刘兆孟.ZigBee无线传感网络路由协议的研究与设计.江南大学硕士论文，2013-06-01

［4］班艳丽.基于能量有效的ZigBee网络路由算法研究［D］.山东大学硕士论文，2009－6：68－71．

［5］张擎，刘淑美，柴乔林．能量高效的ZigBee网络改进路由策略［J］．计算机工程，2010，36（7）：108-111.作者简介：

邓宇（1991-），男，四川泸州人，硕士研究生，研究方向为嵌入式系统及其应用

徐思燕（1986-），女，四川宜宾人，硕士研究生，研究方向为嵌入式系统及其应用

Energy Efficient Routing Algorithm for ZigBee

DENG Yu，XU Si-yan
（College of Computer and Software Engineering，Xihua University，Chengdu 610039）

Traditional ZigBee network routing protocols do not protect the low residual energy of nodes，broadcasting in the routing discovery RREQ，etc.Considers the energy consumption of the propagation path，the sending direction of RREQ，relationship between neighbor nodes，puts forward a kind of efficient routing algorithm based on energy，the algorithm simulation results show that the improved algorithm effectively can reduce the number of sending RREQ，increase the survival rate of the node，prolong the survival time of the network.

ZigBee Network；RREQ；Routing Algorithm.Energy；Simulation

1007-1423（2016）26-0023-004DOI：10.3969/j.issn.1007-1423.2016.26.005

2016-06-28

2016-09-05