基于能量均衡的ZigBee路由算法优化

李予东， 黄宏光， 向西西

(四川大学电气信息学院，四川成都610065)

0 引 言

ZigBee是一种低成本、低功耗、低速率的短距离双向无线通信技术，主要针对低速率的无线传感网络而设计。文献[1]针对ZigBee无线通信协议从物理层、数据链路层到网络层、应用汇聚层进行了全面地剖析，给出了各层协议实现技术的细节。文献[2-3]在介绍ZigBee网络配置、网络拓扑结构和网络层各项关键技术的基础上进行仿真，得出AODVjr[4]的控制开销小于AODV；Cluster-Tree[5]适合存储能力受限的节点，具有较大的平均端到端时延，不需要路由发现过程，然而在节点分布不均匀的网络中，容易造成业务量分布不均衡；AODVjr需要足够的存储空间来储存路由表，而且具有较高的控制开销；Cluster-Tree+AODVjr算法能够找到最优或相对于Cluster-Tree较优的路由，减少平均端到端时延，使网络中业务量分布不均衡的情况也得到了缓解，在保证分组递交率的情况下，具有较低的控制开销和平均时延。

通常通信网络路由算法主要考虑如何实现较少的路由跳数和较短的端到端时延。考虑到WSN网络的具体情况，节点的能量供应采用电池形式，在能量耗尽后无法更换电池既成为死亡节点，不能继续承担收发数据的功能，导致路由链的断裂，甚至割裂整个WSN网络，致使通信中断。因此在WSN网络中牺牲一定的路由跳数和端到端时延来换取节点更长的生存时间就成为一种必要。本文在Cluster-Tree+AODVjr算法基础上详细阐述了对现有基于能量均衡的ZigBee路由算法的改进方案并辅以仿真，对比分析加以说明。

1 问题的提出

1.1 邻居表

文献[6]针对节点间的父子关系提出了一种改进方案，即当目的节点为当前节点的父类节点时，不适合向当前节点的后裔子节点发送RREQ分组，反之当目的节点为当前节点后裔子节点时，不适合向当前节点的父类节点发送RREQ分组。但考虑到节点间的位置关系，如目的节点在当前节点一跳或者较少跳范围内时，仍然可以发现高效的路由路径，因此需要对其做出改进，本文中加入邻居表，保证在适当控制AODVjr泛洪方向的同时能寻找到比文献[6]有效的路由。如表1所示定义了邻居表。

表1 邻居表定义

ZigBee网络中的每个节点被分成4种类型：Coordinator、RN+、RN-、RFD。如果待发送数据的目的节点是自己的邻居，直接通信即可。Coordinator和RN+可以启动AODVjr，主动查找到目标节点的最佳路由，且可以扮演路由代理的角色，帮助其它节点查找路由；RN-只能使用Cluster-Tree算法，它可通过计算判断把数据包交给自己的父节点还是由某个子节点转发；而RFD只能充当Cluster-Tree的叶子，把数据交给父节点转发。除RFD节点外每个节点都存储一张邻居表，记录该节点与其它节点的邻居关系，在邻居表中有四个字段：

Address：邻居节点的地址；

NodeType：邻居节点的设备类型，0表示该邻居节点不具有路由功能，只能接收数据或者转发给其父节点，1具有路由功能；

RoutingCost为该邻居节点的路由代价；若节点为类型为RFD，因其不具备路由功能，则该值为无效值0xFFFF，表示路由代价无限大。

RNRouting为RN-节点邻居表的特殊值，由于RN-节点不能存储路由表，该值为1表示该节点是RN-节点的下一跳，用于路由建立后转发数据，为0表示该节点是RN-节点的上一跳，用于接收路由建立时由目的节点向源节点返回的 RREP包。在 Coordinator、RN+节点的邻居表中该值被置为无效值0xFFFF。

RN-节点只能使用Cluster-Tree算法，它可通过计算判断该把数据包交给自己的父节点还是由某个子节点转发。文献[7]针对Cluster-Tree提出了一种计算邻居表内节点到目的节点路由的思路，但仅比较了目的地为非当前节点的子节点的情况。文献[8]仅基于节点能量来计算Cluster-Tree算法的路由路径代价。本文充分利用邻居表，比较邻居表中节点与Cluster-Tree算法中下一条节点的路由代价，选择路由代价最小的节点作为下一跳节点，从而达到针对RN-节点改进Cluster-Tree算法的目的。

1.2 路由代价

文献[9]中对节点路由代价定义仅划分了中心协调器和普通路由节点，而忽略了各个普通路由节点仍有很大的特性，本文中对除RFD节点以外的所有节点定义了统一的路由代价如下公式所示

路由代价用于表示路由发现过程中该节点被选择为新的路由节点的概率，路由代价越大，则被选为新的路由节点的概率越小。

PowerRemaining表示该节点的剩余能量，剩余能量越多则成为新路由节点的概率越大，以减少剩余能量较小节点成为新的路由节点的概率；

Count用于计数当前节点作为路由节点的次数，即每次发现路由过程中若该节点被选为路由节点则其计数值加1，用于表示该节点可能承担的路由分量。因其一旦作为路由节点，则在之后就有可能大量的转发数据、消耗节点能量。因此该值越大，则在新的路由发现过程中被选为路由节点的概率就越小。

Suns表示该节点所拥有的子孙节点数，Depth表示该节点的深度，拥有的子孙节点数越多，在树结构中的深度越小则在Cluster-Tree算法中越有可能作为路由节点，因此应当在发送RREQ分组选择新路由节点过程中尽量绕过这样的节点。

1.3 节点能量等级

文献[9]中将节点能量划分为4个等级，根据不同的能量状况，在接收到RREQ分组选择不同的处理机制。但已经判断过是否为目的节点，警戒状态再次判断没有意义，而濒临失效的节点对目的节点为自身的节点也不回应，既相当于是死亡节点。本文中将节点能量划分为3个等级：充足、偏低和综合警戒、濒临失效节点为警戒一种节点。能量充足节点可以根据节点类型选择Cluster-Tree算法或AODVjr算法发现路由，能量偏低节点根据一定的公式延迟发送AODVjr泛洪包，能量警戒节点只对目的地址是自身的做出回应。

文献[6，9-10]分别定义了不同的节点能量警戒值，均为动态更新，以便警戒节点在一定条件下能够重新恢复为有效路由节点。但充足能量值和偏低能量值均为固定值，不能随网络能量状况的改变而改变，导致大量节点能量等级处于偏低状态，影响路由发现。文献[6]中的警戒值为网络运行时间的函数，网络运行时间越长，警戒值越低，但仅以时间为变量，不能充分描述网络中节点能量的具体情况。文献[9-10]则以成为警戒节点的计数为变量，但公式较复杂。本文简化文献[9-10]的公式，并定义动态更新的节点能量充足值、偏低值和警戒值如下

Power为节点的初始能量值，、和 为固定系数，N为初始值为1的计数值。当警戒节点个数与所有节点个数比Waring Nodes/Nodes达到一定临界值Threshold时则N计数加1。

2 路由算法优化

2.1 初始化

在初始化阶段，中心协凋器Coordinator根据网络地址分配机制[11]为每个节点分配惟一的网络地址；网络中除RFD节点外每个节点初始化本身的邻居列表，记录所有邻居节点的相关信息；并且将自身剩余能量值与节点能量等级部分定义的各个临界值相比较，判断出该节点所在的能量区域，从而在传输数据的时候选择不同的路由策略。

2.2 路由发现

如图1所示，路由发现阶段当节点作为中间节点接收到RREQ包时，将按如下步骤处理：

(1)判断本身是否为目的地，若是则返回RREP包，否则进入下一步。

图1 中间节点对RREQ包处理流程

(2)检测自身剩余能量是否处于警戒状态，若是则直接丢弃RREQ包，并向Coordinator节点发送数据并由Coordinator节点更新警戒节点计数WaringNodes，同时向其所有邻居节点发送数据，由其邻居节点更新各自的邻居表，将该警戒节点的Nodetype置0，以便之后不再向其发送RREQ包；否则进入下一步。

(3)判断目的节点是否在邻居表内，若是则向目的节点发送RREQ包；否则进入下一步。

(4)判断节点类型是否为RN-，若是则扫描邻居表中是否有RNRouting值为1的节点，若有则向该节点发送RREQ包，若无则比较邻居表中节点的路由代价 RoutingCost，并选择RoutingCost最小的节点作为下一跳节点(根据Cluster-Tree算法计算得出的下一跳节点也必然在邻居表内)转发RREQ包，并将邻居表中该节点的RNRouting置1，同时将邻居表中上一跳节点RNRouting置0以便其可以接收到返回的RREP包，从而结合邻居表根据节点能量等级达到优化Cluster-Tree算法的目的；否则进入下一步。

(5)判断目的节点是否在当前节点的父亲节点或子节点的邻居表内，若是则向父亲节点或子节点转发RREQ包；否则进入下一步。

(6)检测自身剩余能量是否充足，若是则判断目的节点为当前节点的父类节点或是后裔节点：若是父类节点，则只向父亲节点转发RREQ包，若是后裔节点则只向子节点转发RREQ包，与步骤5结合达到适当控制AODVjr泛洪方向的目的，否则进入下一步。

(7)此时节点能量等级必为偏低，则按照步骤6转发RREQ包，在转发RREQ包时加入一定的延时T

(8)RFD节点则根据节点能量等级选择延迟或直接转发RREQ包给其父节点。

AODVjr算法中节点只接受最先到达的RREQ包，这样若节点已经接收到RREQ包，则会丢弃该由于延迟而较晚到达的RREQ包，从而变相的选择了路由代价较小的路由路径。

当目的节点接收到RREQ包时则向源节点沿该RREQ包发送路径返回RREP包，源节点接收到RREP包则路由路径建立。

2.3 路由更新与维护

在数据传递过程中，需要对路由和节点状态进行实时的更新与维护，以反映网络能量状态的变化：节点一旦成为路由节点则其成为路由节点的计数Count加1；节点在每次转发数据后都会更新自己的能量值，判断能量等级是否发生变化，若节点能量等级更新为PowerWaring，则向源节点发送数据表示该路由失效进而使源节点重新启动路由发现，同时向Coordinator节点更新WaringNodes计数，若警戒节点个数与所有节点个数比WaringNodes/Nodes达到临界值Threshold则N计数加1从而根据公式更新节点能量等级值。

3 仿真实现与分析

本仿真实验利用OMNeT++4.0和MF模型实现。网络覆盖面积为100m×100m，网络节点数目设置为100个，节点初始能量均为1000J，、和 分别为0.75、0.5和0.25，为100，Threshold为0.5，采用的传输信道数据传输率为250KB，数据包长度为128bit。

如图2所示，由于本文算法引入了邻居表，选择路由节点时考虑了较文献[10]更多的因素，能量等级均为动态变化且真正实现了AODVjr算法和Cluster-Tree算法的结合，因此能够选择出能量消耗更小的路由路径。虽然在网络初始化阶段网络总体能量消耗与文献[10]算法基本相当，但一旦路由建立，本文算法在网络总体能量消耗上明显优于原算法和文献[10]算法。

图2 网络总体能量消耗

图3 网络死亡节点个数

如图3所示，在网络初始化阶段，每个节点的能量都很充足，3种算法均不会产生死亡节点，随着网络运行时间的增长，原算法没有考虑节点能量状况，有的节点频繁作为路由节点消耗很大的能量，最先出现死亡节点。本文考虑节点能量状况的同时适当控制RREQ包的转发，并且在Cluster-Tree算法中也加入了对节点能量状况的考虑，能够更好的选择能量状况较好的节点作为路由节点，均衡了网络能量消耗，最大化网络生存时间，较文献[10]在死亡节点出现时间和死亡节点个数上均有较大优化。

4 结束语

本文针对原ZigBee路由算法和现有能量均衡算法中的不足，分别提出了基于能量均衡的AODVjr算法和Cluster-Tree算法改进方案，并结合两种算法，有效使用邻居表实现RN-节点的路由功能同时控制RREQ包转发方向；提出了基于节点剩余能量、成为路由节点次数、子孙数目和深度的能够全面体现节点现有和将来能量状况的路由代价；提出了动态更新的节点能量等级，使网络能够选择出能量代价最小的路由路径，同时均衡整个网络的能量消耗。仿真表明本文算法确实优化了ZigBee网络的能量消耗状况。

[1] 任秀丽,于海斌.ZigBee无线通信协议实现技术的研究[J].计算机工程与应用,2007,43(6):143-145.

[2] 杜焕军,张维勇,刘国田.ZigBee路由协议的研究[J].合肥工业大学学报,2008,10(31):1617-1621.

[3] 耿萌,于宏毅,张效义.ZigBee路由协议分析与性能评估[J].计算机工程与应用,2007,43(26):116-120.

[4] Fechner J.ZigBee in industrial applications[C].Nurnberg,Germany:Proceedingsofthe 2006International Conference on Power Electronics Intelligent Motion and Power Quality,2006:61-62.

[5] Leek K,Kims H,Choiy S,et al.A mesh routing protocol using cluster label in the ZigBee network[C].New York:IEEE International Conference on Mobile Ad Hoc and Sensor Systems,2006:801-806.

[6] 班艳丽,柴乔林,王芳.改进的ZigBee网络路由算法[J].计算机工程与应用,2009,45(5):95-116.

[7] 李刚,陈俊杰,葛文涛.一种改进的ZigBee网络Cluster-Tree路由算法[J].测控技术,2009,28(9):52-55.

[8] 王琛,柴乔林,王芳.基于树形结构的ZigBee能量均衡协议研究[J].计算机工程与设计,2009,30(15):3534-3586.

[9] 王芳,柴乔林,班艳丽.一种改进的ZigBee mesh网络路由算法[J].计算机应用,2008,28(11):3534-3586.

[10]班艳丽,柴乔林,王琛.基于能量均衡的ZigBee网络树路由算法[J].计算机应用,2008,28(11):2791-2794.

[11]Asano Y,Imai H,Toyoda M,et al.Finding neighbor communities in the web using an inter-site graph[J].IEICE Transactions on Information and Systems,2004(9):2163-2170.