ZigBee路由算法的改进

【摘要】网络层的路由协议是ZigBee协议规范的研究重点之一，因为网络节点中节点的能量资源、计算能力和带宽都非常有限，路由算法优化与否对整个网络的性能有着至关重要的作用。从控制RREQ分组以及能量均衡的角度出发，对AODVjr算法提出了改进。通过仿真实验，将改进的算法与原AODVjr算法进行性能参数的比较分析，实验结果验证了改进后的算法的有效性。

【关键词】ZigBee路由算法AODVjr无线传感器网络

一、引言

近年来，作为在低速率的无线传感器网络和控制网络中最受瞩目的技术之一，ZigBee以其低成本、低功耗、低速率、高可靠性等特性，广泛应用于工业、医疗、军事、智能家居等需要低功耗、低成本，对数据传输速率和服务质量要求不高的无线通信应用场合[1]。

ZigBee网络层（NWK）介于MAC层和应用层之间，是由ZigBee联盟制定的。ZigBee网络层的主要功能就是确保ZigBee的MAC层能正常工作，并且提供适合的服务接口给应用层。网络层提供了两个必要的功能服务实体用于向应用层提供接口：数据服务实体和管理服务实体[1-2]。

NWK主要功能有：（1）加入和离开网络；（2）帧的安全机制管理；（3）根据路由发送帧到目的地址；（4）发现和维护路由；（5）发现单跳邻居节点和维护邻居节点信息。

二、ZigBee网络层技术简介

2.1网络拓扑结构及地址分配

ZigBee网络中存在三种网络节点，分别为中心协调器、路由节点和终端节点。协调器是整个ZigBee网络的中心，是协调点，负责整个网络的组织、维护和管理工作，必须由FFD（全功能设备）构成；路由节点负责数据的传输和转发功能，必须由FFD构成，但路由节点必须由协调器控制；终端节点负责自身数据的发送并接收其他节点传过来的数据，可以由FFD或RFD（精简功能设备）构成。

ZigBee网络有星型、网状型和树型三种拓扑组织形式。由于树型网络结合了星型结构和网状结构的优点，且具有较好的扩展性，所以ZigBee网络一般采用簇树拓扑结构组织节点。中心协调器启动后就创建一个网络，设置自身网络地址为0，路由节点和终端节点选择相应的有路由功能的父节点加入网络，形成父子关系。成功加入网络后，该节点获得父节点分配的一个唯一的网络地址。

规定每个父节点最多可以连接Cm个子节点，这些子节点中最多可以有Rm个路由节点，网络的最大深度为Lm，Cskip（d）是网络深度为d的父节点为其子节点分配的地址之间的偏移量，它的值按公式（1）计算，分配给第k个子路由节点的地址Ak满足式（2），分配给第n个子路由器节点的地址Ak满足式（3）。其中，Afather代表父节点的地址。

2.2Cluster-tree路由算法

Cluster-tree算法根据树结构转发分组，如果终端节点要发送数据包到网络中的其他节点，则直接将该数据包转发给其父节点，由父节点进行转发。

如果一个路由器节点要转发数据包到网络地址为D的目的节点，已知该路由器节点的网络地址和深度分别为A和d。

首先，该路由器节点会依据下述表达式判断目的节点是否是其后裔节点：

RREQ分组。

此外，由于网络中某些节点传输数据量过大，特别是距离中心协调器越近的节点，从而提前耗尽自身能量，容易造成网络分割，影响了整个网络的通信，缩短了网络的寿命。

针对以上问题，本文从控制RREQ分组以及能量均衡的角度出发，提出一种改进的算法，有效的限制AODVjr路由发现过程中的RREQ的广播，延迟网络分割出现的时间，从而提高网络的性能。

3.2改进的路由算法M_ZBR

3.2.1冗余RREQ分组的控制

改进的路由算法M_ZBR在路由发现阶段，利用Cluster-tree结构及算法的特点，根据公式（4）判断出目的节点与当前节点的关系，从而判断出RREQ分组转发最佳的大致方向。因此，M_ZBR算法在RREQ分组中增加一个标志位flag。当目的节点为当前节点的后裔节点时，flag=0，即表示当前节点的父节点不宜转发该RREQ分组；当目的节点不是当前节点的后裔节点时，flag=1，即表示当前节点的后裔节点不宜转发该RREQ分组。

另外，从树结构可以看出，若在使用Cluster-tree路由算法时，可能存在的最长路径应是网络最大深度的2倍。由此，M_ZBR算法通过设定最大传输跳数也可以减少部分冗余的RREQ分组，本算法中，当跳数hops>2Lm时，节点便丢弃该RREQ分组。

3.2.2节点能量的控制

M_ZBR算法根据ZigBee路由算法的特点，对ZigBee网络中的路由节点采用了能量控制机制，这对延长网络寿命，延迟死亡节点以及网络分割出现的时间都是十分必要的。因此，M_ZBR算法定义了节点最小路由能量Emin，当节点的能量低于Emin时，路由节点将不再发起路由发现，即不再采用AODVjr路由算法。

在ZigBee网络中，越靠近中心协调器的节点参与数据传输就越频繁，对整个网络的通信来说也就越重要，所以Emin的能量控制应与节点深度成反比，深度越小节点应具有相对较大的最小路由能量，因此，将Emin定义为：

其中，Elimit为节点正常工作需要的最小能量值，为控制系数，可以根据需要人为的控制Emin的大小，d为节点的深度。

此外，M_ZBR算法依据节点最小路由能量的定义，设置一个节点能量警戒值Ewarning：

其中，k为大于1的控制系数。

依据以上节点能量阈值的设置，M_ZBR算法在RREQ分组中增加了能量标志位energy_flag，用于统计RREQ分组传输过程中统计处于能量警戒区内的节点个数。

3.2.3算法流程

（1）当RFD节点要给网络中其他节点发送数据时，直接采用Cluster-tree算法，即将数据转发给其父节点，由其父节点转发。（2）当FFD节点要发送数据到网络中其他节点时，首先查找路由表中有无到目的节点的路由表项，若有则按路由表转发数据包，若无则启动路由发现过程。（3）在路由发现阶段，任意节点收到RREQ分组时，首先检测本节点是不是该RREQ分组的目的节点，如果不是，则转（4）；若是，则转（9）。（4）判断节点自身的剩余能量，如果剩余能量小于节点最小路由能量Emin则直接丢弃RREQ分组，否则转（5）。（5）查看RREQ分组中的跳数值，若hops>2Lm，则丢弃RREQ分组，否则转（6）。（6）查看RREQ分组中的标志位flag，若flag=0，转（7），若flag=1，则转（8）。（7）flag=0表明本节点不宜转发子节点发送的分组，需判断本节点是否为前一跳的父节点，若是，则丢弃RREQ分组；若不是，则判断目的节点是否为当前节点的后裔节点，如果是，flag的值继续为0，直接转发分组，若目的节点是当前节点的后裔节点，则设置flag=1。（8）flag=1表明本节点不宜转发父节点发送的分组，需判断本节点是否为前一跳的子节点，若是，则丢弃该分组；若不是，则需判断目的节点是否为当前节点后裔节点，如果是，则设置flag=0，若目的节点不是当前节点的后裔节点，flag的值继续为1，直接转发分组。（9）当目的节点收到RREQ分组时，判断自身剩余能量，若小于Emin，直接回复RREP；否则将收到的分组放入缓存区，在缓存时间t内，比较各RREQ分组的能量标志位energy_flag，选择energy_flag最小的RREQ分组且回复RREP。

四、仿真结果分析

为了验证改进算法的实际效果，通过仿真实验对比原来的AODVjr算法，分别比较了死亡节点个数以及总能量损耗，仿真结果证明了算法的可行性和有效性。

图3是原AODVjr算法与改进算法死亡节点数的比较，曲线（1）是原AODVjr算法随数据流量增加而变化的死亡节点数，曲线（2）是改进后的算法的死亡节点数。当数据流量较小时，节点能耗就较少，节点死亡数相对就比较少。当数据流量增加时，死亡节点数也会增加，改进的算法通过能量标志位的判断，选取能量标志位最小的RREQ分组并回复，明显比原算法的死亡节点数增加的缓慢。

图4比较了改进算法与原算法的网络总能量耗损。曲线（1）是原AODVjr算法随数据流量增加而变化的网络总能量耗损，曲线（2）是改进后的算法的网络总能量耗损。显然，改进的AODVjr算法通过控制了RREQ分组减少了网络的耗能。

五、结论

本文主要针对ZigBee的路由协议进行分析，基于能量均衡对ZigBee现有的路由算法AODVjr提出了改进，通过限制路由发现过程中的RREQ的广播，很好的延迟网络分割出现的时间，从而提高网络的性能。仿真实验将原算法和改进的算法进行了比较，改进的路由算法有效地减少了总耗能与死亡节点数。

参考文献

[1] ZigBee Alliance. ZigBee Document 053474r13 [S]. December 1， 2006.

[2]朱向庆，王建明. ZigBee协议网络层的研究与实现.电子技术应用. 2006.1：129

[3] Hakeres I D， KleinBerodt. AODVjr，AODV simplified[J]. Mobile Computing and Communication Review， 2002， 6（3）：100-101.[4]班艳丽，柴乔林，王芳.改进的ZigBee网络路由算法.计算机工程与应用，2009，45（5）：95-97

[4]谢川.基于ZigBee的AODVjr算法研究.计算机工程，2011，37（10）：87-89

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