基于ZigBee网络的AODV路由改进算法

摘要：针对AODV协议算法会产生冗余RREQ报文，导致网络拥塞的缺点，提出一种能量有效的改进算法EE-AODV。EE-AODV在路由发现过程中，通过设定定时器选择跳数少、剩余能量高、链路质量好的节点进行数据包的转发。实验证明，EE-AODV减少了ZigBee网络中RREQ报文的数量、降低了数据包的时延，降低了网络整体能耗，提高了网络生存周期。

关键词：ZigBee；AODV路由；能量有效；剩余能量；链路质量

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2017）06-0022-02

Abstract：The AODV protocol has disadvantage of large numbers of redundant data which will lead to network congestion.An energy efficient improved AODV routing （EE-AODV） was proposed. EE-AODV choose the nods which have lower number of hops， higher level of the， remaining energy， and higher of the link quality to broadcast the packet during the route-discovery process. Experiment shows that the EE-AODV prolongs the ZigBee networks lifetime for reducing the number of RREQs the energy consumption， and decreasing the network delay.

Key words：Zigbee； AODV routing； energy efficient； remaining energy； link quality

1 概述

ZigBee作为物联网的关键技术之一，以其功耗低、数据传输可靠、组网灵活、数据传输安全性好和低成本的优势广泛地应用于智能家居、智能交通、工业自动化以及医疗等各个领域[1]。在网络层，ZigBee采用树路由和AODV两种路由协议。AODV协议适用于Mesh网络，具有较低的数据传输时延，但是该协议在路由发现过程中，会产生大量冗余的RREQ报文。如果网络规模过大，就会产生广播风暴，造成网络拥塞，浪费了网络资源。现有研究结果 [2-6]表明，传统的AODV改进算法都没有将转发节点选择和限制广播报文进行有机结合。另外一些过于复杂的算法，增加节点到计算和存储开销，反而加大了网络的整体能耗。本文提出一种能量有效的AODV改进算法，称为EE-AODV（Energy Efficient-AODV），选择最优节点进行转发数据包，限制RREQ报文数量，减少了网络能耗，提高了ZigBee网络的命周期。

2 AODV算法存在的问题

AODV（Ad hoc On-demand Distance Vector）是一种按需路由协议，每个节点只有在有需要的时候才开启路由发现过程。当源节点要发送数据给目的节点时，若路由表中没有相应的路由，首先广播RREQ报文来开启路由发现过程，节点收到RREQ报文以后，如果自身不是目的节点则继续广播该报文。最终目的阶段接收到RREQ分钟以后，停止广播，回复一个RREP报文。当源节点收到目的节点RREP报文后，路由建立完毕，开始发送数据帧。AODV在路由发现过程中产生大量的广播报文，随着网络规模的增加，这些RREQ报文数量急剧增加，在网络中造成洪泛，会导致数据包传送时延增大，数据包丢失，严重的情况下会出现网络拥塞，导致网络中断。此外，部分RREQ报文的传输范围超过网络的最大跳数，传输次数达到最大时会被节点丢弃，造成网络能力的浪费。

AODV算法在选择转发路由中总是选择最少跳数的路由。但是如果最短路径中的某些节点如果能量偏低，频繁使用该路径会导致节点能量提前耗尽能量，使得路由失效。节点重新发起路由发现过程又会导致网络中大量RREQ报文泛滥，加大了网络能耗。同样的，如果最短路径中某些节点之间的通信链路质量差，会导致数据包丢失的概率增大，节点将不得不耗费大量精力进行数据包的重传，导致节点提前耗尽能量。

3 AODV改进算法

EE-AODV在路由发现过程中，设定一个定时器来选择最优节点发送的RREQ报文，以减少路由发现过程中RREQ报文的数量，降低数据包洪泛的发生。定时器的设置以后，节点接收到第一个数据包以后，等待一段时间接受更多的RREQ包，从中选择最优的RREQ包，以选择最佳的转发节点。定时器时间和节点接收到的RREQ包的数量成正比，定时器按照下面公式设置：

首先，在路由发现过程中的RREQ报文中增加节点的剩余能量和RSSI的值，原AODV包中，跳数已包含在里边。节点第一次接收RREQ，开启定时器。在定时结束之前，若节点接收到RREQ，根其报文中的跳数、剩余能量和RSSI值，采用上面公式计算权值，若比存储的值高，则更新存贮的权值。在定时器到期之后，节点转发广播最高权值的RREQ包。目的节点回复的也是具有最高转发权值的RREP。EE-AODV算法伪代码如表1所示：

4 EE-AODV算法分析

如图1所示的ZigBee Mesh网络中，节点上方的数字为其转发权值。若节点S发送数据给节点D，开启路由发现过程，如果采用AODV 算法，在路由发现过程中广播的RREQ广播顺序如表1左边所示。当节点G最先转发广播的RREQ包给目的节点D。这D就会回复RREP包给节点G，按照最短路径原则，此时，选择的转发路线为S，C，G，D。若采用文本提出的EE-AODE算法，每个节点在接收到RREQ以后，启动定时器，等待更多的RREQ包到来，然后根据公式（2）计算转发权值，从中选择最优的一个节点进行转发。例如步骤4，节点E之前接收到A，B转发的RREQ包，但是节点B的权值为0.86，比节点A的权值高。因此，E将丢弃节点A广播的RREQ包，因此，只向B，F，H三个节点广播RREQ包。最后目的节点收到G，F，H三个节点广播的RREQ包以后，只回复权值最高的节点F。此时，路由转发线路为S，B，F，D也是4跳。虽然跳数不变，但是此路线中节点的剩余能量和线路状况都优于前者，发送数据过程中丢包率更小，能耗更低。此外，在图1所示的9个节点的RREQ广播过程中，AODV算法广播的数据包有31个，EE-AODV广播的书数据包26个，广播包数减少了17%。随着网络规模的扩大，RREQ广播包就减少的越多，因此，本算法非常适合大规模的ZigBee Mesh网络。

5 算法仿真结果

将EE-AODV算法和AODV路由算法在NS 2.35环境下分别进行仿真比较。在仿真场景中，在 网络节点数分别为50、100、150、200、250、300的情况下，各自运行50次仿真，将结果平均值。仿真参数设置公式（2）的权值为α=0.5、β=0.3、γ=0.2。仿真结果如图2，图3。

网络能耗对比如图3所示，本文提出的算法基于跳数、节点的剩余能量和链路质量三者均衡考虑，在转发节点选择过程中，剩余能量、链路质量好的节点。随着节点数的增多，EE-AODV算法的能量明显优于AODV算法，因此网络存活的时间更长。

网络时延的对比如图2所示。由于EE-AODV算法减少了网络中RREQ数据包的数量，抑制了广播风暴的产生，这减少了网络中数据包的碰撞机会，使得数据包的端对端时延更小。

6 结论

本文提出的能量有效的AODV算法简单易用，不需要很多额外的计算和存储开销，算法能够降低网络的整体能耗，减小数据包的到达时延，可以提高网络的生存周期。本算法在工I、医疗以及监控领域的大规模的ZigBee Mesh网络中都具有广泛的应用价值。

参考文献：

[1] Bandyopadhyay D， Sen J. Internet of Things： Applications and Challenges in Technology and Standardization[J]. Wireless Personal Communications， 2011， 58（1）：49-69.

[2] 徐沛成， 胡国荣. 改进的ZigBee网络路由算法[J]. 计算机工程与设计， 2013， 34（9）：3019-3023.

[3] 徐艳， 王茜， 武剑. ZigBee路由协议优化仿真研究[J]. 计算机仿真， 2013， 30（6）：292-295.

[4] 狄万昕， 江明. 基于权重和均衡能量的ZigBee改进路由算法[J]. 安徽工程大学学报， 2016， 31（2）：78-81.

[5] Kasraoui M， Cabani A， Mouzna J. ZBR-M： A New Zigbee Routing Protocol[J]. International Journal of Computer Science & Applications， 2013， 10（2）： 15-32.

[6] 谢忠明， 何华冰， 李云飞， 等. 一种基于链路状态感知的 Zigbee 多径路由算法[J]. 微电子学与计算机， 2015（9）： 65-69.