WSN中基于链路质量和节点能量的AODV路由算法研究*

杜海韬，李　强，丁广太，王营冠，朱磊基

（1.上海大学计算机工程与科学学院，上海200444；2.中国科学院上海微系统所与信息技术研究所，上海201899；3.上海物联网有限公司，上海201899）

WSN中基于链路质量和节点能量的AODV路由算法研究*

杜海韬1，2，李强2，3*，丁广太1，王营冠2，朱磊基3

（1.上海大学计算机工程与科学学院，上海200444；2.中国科学院上海微系统所与信息技术研究所，上海201899；3.上海物联网有限公司，上海201899）

为了满足无线传感网络能量的高效使用以及数据传输的稳定性的要求，需要对无线传感网络路由层协议进行改进。本文提出一种基于节点之间链路质量和节点能量状态的LE-AODV路由协议，LE-AODV路由协议采用跨层设计，路由发现过程中通过MAC层和物理层获取链路质量信息和节点能量信息来选取最优路径，并通过节点能量状态更新机制避免网络中热点的产生。本文使用Castalia仿真器对LE-AODV路由协议进行仿真，仿真结果表明，LE-AODV路由协议可以有效的提高分组投递率和网络生存时间。

无线传感网络；链路质量；节点能量；LE-AODV路由协议；Castalia仿真器

EEACC:6150Pdoi:10.3969/j.issn.1004-1699.2016.07.016

无线传感网络WSN（Wireless Sensor Network）［1］是随着无线通信技术、嵌入式计算技术、传感器技术和网络技术的发展出现的一种新型的数据监控网络，被认为是21世纪最重要的技术之一，它能够实施监测、感知和采集网络分布区域内各种环境或监测对象的信息，并对其进行合理的处理，获得详尽而准确的现场信息。WSN由于其快速展开、自组网、抗毁性强、检测精度高、覆盖区域大等特点，在军事通信安防监控，城市交通管理，家庭保健，环境监测，抢险，远程控制等许多领域都有重要的科研价值和巨大的使用价值。目前WSN的研究主要集中在网络层和链路层，网络层路由协议和算法是WSN研究热点。WSN与传统无线网络有很大不同，传统网络路由协议设计目标是降低通讯延迟，提高网络带宽利用率，进行流量控制，而WSN由于具有分布式、节点能量有限、通讯链路容易受环境影响等特点，因此WSN路由协议更加关注网络能量的高效使用以及数据传输的稳定性［2］。本文结合WSN的特点对AODV（Ad Hoc on Demand Distance Vector）［3］路由协议进行了改进，提出了基于链路质量和节点能量的LE-AODV（AODV Routing Dased on Link Quality and Energy）路由协议，改进了AODV路由协议的路由发现过程和选取路径的机制，提高了数据传输的稳定性，使网络中节点能量消耗更加均衡，延长了网络生存时间［4］。

1　相关工作

AODV路由协议是一种反应式按需路由协议［5］。当一个节点需要一条路由时，它通过广播路由请求RREQ（Route Request）消息启动路由发现过程，每个节点转发RREQ消息直到这个节点存在到目的节点的路径或者这个节点就是目的节点，这时这个节点会发送一个路由回复RREP（Route Replay）消息给源节点并忽略之后从其他路径发送过来的RREQ消息，因此AODV路由协议路由发现过程中选取的是最短路径。这样的路由发现过程存在以下不足之处：首先，最短路径意味着路由跳数较少，那么节点之间的距离较长，长距离的链路质量较差，容易受到噪声和干扰的影响而造成丢包；其次，AODV路由协议没有对点能量消耗进行管理，容易在网络中产生热点现象［6］，如图1所示，由于选取最短路径，节点6～节点8都通过节点5向Sink节点发送信息，节点5被过度使用了，造成节点5能量消耗过快，使整个网络的能量消耗分布不均衡，最终在网络中产生能量空洞；最后，对于给定的目的节点，AODV路由协议只保存一条最短路径，如果这条路径失效了，那么必须重新进行路由发现过程，这样会需要更多的时间造成发包的迟延。因此AODV路由协议路由发现的过程和选取最短路径的机制不能满足WSN对能量的高效使用以及数据传输的稳定性的要求。

图1　热点现象

目前WSN中对AODV路由协议主要有以下一些改进，L-AODV［7］是基于链路质量的改进的 AODV路由协议，L-AODV使用 LQI［8］（Link Quality Indicator）来表示链路质量，通过设定一个LQI阈值LQIth来判断链路的好坏，LQI值低于这个LQI阈值的链路是差的链路，LQI值高于这个LQI阈值的链路是好的链路。在路由发现的过程中对路径中差的链路的数量进行统计，并在RREQ消息和RREP消息中添加一个Link字段来记录这个值，通过比较Link值的大小来选取路径。L-AODV选取是链路质量最好的路径提高了网络数据传输的稳定性，但是由于L-AODV没有考虑节点能量，网络中仍然会产生热点，造成网络能量消耗不均衡。E-AODV［9］是基于能量的改进的AODV路由协议，E-AODV考虑整条路径的能量消耗和整条路径中节点的最低能量状态，E-AODV在RREQ中添加了一个字段来记录路径中节点的最低能量状态，通过设定一个Energy阈值Eth来判断路径中是否有节点被过度使用而成为热点。当一个节点在t时刻能量状态为E（t），如果E（t）与t-1时刻的能量状态E（t-1）的差值大于Eth，那么说明该节点发生了热点现象，如果某条路径中存在热点，则选择其他路径。EAODV提高了网络能量消耗的均衡性，延长了网络生存时间，但是由于E-AODV没有考虑节点之间的链路质量，因此E-AODV的数据传输稳定性不佳。

综上所述，本文结合WSN的特点，采用跨层的设计［10］，如图2，依据物理层和MAC层提供的具体的链路信息和节点能量信息，提出了基于链路质量和节点能量的LE-AODV路由协议。仿真实验将LE-AODV路由协议与AODV、L-AODV、E-AODV路由协议进行比较，结果表明，LE-AODV路由协议能有效改善网络能量消耗均衡性，延长了网络生存时间，提高了数据传输稳定性。

图2　跨层设计

2　AODV路由协议算法改进

2.1路由发现和最优路径选取机制

LE-AODV路由协议在路由发现过程中，发送的RREQ消息通过物理层和MAC层获得节点之间的链路质量LQI和节点的剩余能量，在RREQ消息中添加Link和Energy这两个字段，Link表示路径中链路质量较差的链路的数量Q，Energy表示路径中最低节点能量状态E，LE-AODV路由协议RREQ消息帧格式如表1所示。LE-AODV路由协议路由表中存储多条到达目的节点的路径，当一个节点需要发送数据包到目的节点时，该节点会从路由表中选取一条最优路径。

表1　RREQ消息帧格式

①低质量链路数Q［11］：

假设一条路径L的跳数为N+1，则L经过N个中间节点，节点i与节点i+1之间链路质量L为：

整条路径中低质量链路数Q为：

设定LQI阈值为LQIth，当L＞LQIth时，节点之间链路数据传输稳定，不容易丢包，当L＜LQIth时，节点之间链路数据传输不稳定，容易丢包。LQI阈值LQIth可由实际场景下的实验得到，当节点之间链路的分组投递率PDR［9］（Packet Delivery Radio）达到80%以上时，说明这条链路传输数据是稳定的，取此时链路的LQI值作为LQIth阈值。链路的LQI值容易受环境的影响，在实际的室内场景中，使用CC2420芯片作为WSN工作节点，实验测得LQI值与PDR之间的关系如图3所示，取LQIth值为220。

图3　CC2420分组投递率PDR与LQI之间的关系

②路径中最低节点能量状态E［12］：

中间节点i的能量状态为节点剩余能量和初始能量的比值：

整条路径中节点最低能量状态为：

③路径跳数差H［13］：

假设一个节点到目的节点还存在一条路径L1，L1的跳数为M+1，则L与L1的跳数差H为：

在LE-AODV路由协议中最优路径的选取机制中，对于同一个目的节点，可能存在多条路径，设定一个跳数差阈值Hth，路径之间的跳数差不能超过Hth。Hth是对新发现路径跳数的限制，如果没有对路径的跳数进行限制，在LE-AODV路由协议的路由发现过程中，节点会收到大量路由回复RREP消息，RREP消息的爆炸性增长会降低路由发现的效率，同时路径的数量并不是越多越好。Hth越大，路由发现过程中产生的可选路径越多，考虑到在实际的应用场景中，如果整个网络的节点数较少，可以取Hth值为2，如果整个网络的节点数量较多达到上百个节点，Hth的值需要通过仿真实验来确定。

LE-AODV路由协议最优路径选取综合考虑路径中路径中链路质量较差的链路的数量Q和节点最低能量状态E以及路径之间的跳数差H，算法流程图如图4所示。

由图4可知，当路由发现过程中发现了一条到达目的节点新的路径B，将路径B与当前正在使用的最优路径A进行比较。如果路径A和路径B的节点最低能量状态相等，那么需要比较路径A和路径B的跳数HA、HB，如果路径B的跳数HB大于路径A的跳数HA，那么显然路径A仍为最优路径，路径B的跳数多会比路径A消耗更多的能量，如果路径B的跳数HB小于路径A的跳数HA，这时需要使用跳数差阈值Hth对跳数进行限制，如果满足HA-HB＞Hth且路径A的低质量链路数QA大于等于路径B的低质量链路数QB，那么路径B为最优路径；当路径A的节点最低能量状态小于路径B时，如果满足HB-HA＜Hth且路径A的低质量链路数QA大于等于路径B的低质量链路数QB，此时选择路径B为最优路径；当路径A的节点最低能量状态大于路径B时，如果满足路径A的低质量链路数QA大于等于路径B的低质量链路数QB且HA-HB＞Hth时，此时路径B为最优路径。最优路径选取算法综合考虑了可选路径的跳数，路径中节点的能量状态以及整条路径的链路质量。

图4　LE-AODV路由协议最优路径选取算法流程图

2.2节点能量状态更新机制

在LE-AODV路由协议中，节点周期性的维护自身的能量状态和周围邻居节点的能量状态，并通过发送EnergyPacket数据包来更新自身能量状态和邻居节点的能量状态，EnergyPacket数据包帧格式如表2所示。设定一个能量状态变化阈值Eth，在t时刻节点的能量状态为E（t），如果E（t）与t-1时刻的能量状态E（t-1）的差值大于Eth，，说明自身能量消耗过快，发生了热点现象，那么该节点通过发送EnergyPacket数据包来更新邻居节点中自身的能量状态，并且更新相关路由表中路径的最低节点能量状态。Eth的值需要通过仿真实验确定，如果Eth过大，那么节点不能感知到热点的产生，会造成能量消耗的不均衡，如果Eth过小，那么节点需要发送更多的EnergyPacket数据包来进行节点能量的更新，会消耗更多的节点能量。

表2　EnergyPacket数据包帧格式

节点能量状态更新机制流程图如图5所示。

图5　节点能量状态更新机制

3　仿真过程与结果分析

本文采用Castalia仿真器［14］对LE-AODV路由协议和AODV、E-AODV、L-AODV路由协议进行仿真对比实验，分别从节点能量消耗、分组投递率PDR、网络生存时间、节点存活数量这几个方面进行比较分析，验证了LE-AODV路由算法可以提高网络能量利用率，延长网络生存时间，提高数据传输稳定性。Castalia仿真器是Linux操作系统下的、基于OMNET++平台的、针对WSN场景的低能耗嵌入式设备仿真器，本文使用的Castalia仿真器版本为Castalia-3.2。在仿真过程中设计了两种仿真场景：仿真场景一仿真区域较小，节点数较少，模拟室内场景，通过对比分析不同Eth值情况下LE-AODV路由协议的网络生存时间，确定Eth的值；仿真场景二仿真区域较大，节点数较多，模拟室外场景，通过比较分析不同Hth值情况下LE-AODV路由协议的分组投递率，来选取合适的Hth值。

仿真场景一仿真参数如表3所示。

表3　仿真场景一参数表

Eth取不同的值时，LE-AODV路由协议网络中平均能量状态随时间变化的关系如图6所示。

由图6可以发现当Eth大于6时，网络的生存时间反而降低了，这是因为Eth较大时，LE-AODV路由协议并不能及时发现成为热点的节点，整个网络的能量消耗会不均匀，导致了网络生存时间的降低。Eth=2时的网络生存时间比Eth=4时的网络生存时间多2 min，Eth=2时的网络生存时间最高，因此取Eth=2。

图6　不同Eth下网络平均能量状态随时间变化的关系

取 Eth=2，在上述仿真场景下仿真 AODV、E-AODV、L-AODV和LE-AODV路由协议，仿真时间为12 min，图7和图8分别为节点的分组投递率PDR和节点的能量状态。

由图7、图8可以发现LE-AODV、E-AODV、LAODV路由协议中节点的分组投递率PDR和节点能量状态都要高于AODV路由协议。LE-AODV路由协议中节点的分组投递率PDR与L-AODV路由协议接近，LE-AODV路由协议中节点能量状态与E-AODV路由协议接近，同时在AODV路由协议中，节点5的分组投递率最低，这因为AODV路由协议选取的是最短路径，节点（7、8、9）向节点5发送的数据包较多，造成了节点5分组投递率的降低，结合图7可以发现节点5的能量状态也最低，说明节点5需要转发更多的数据包，消耗更多的能量。图7和图8说明E-AODV路由协议能提高网络能量利用率，但是由于E-AODV路由协议没有考虑链路质量，因此E-AODV路由协议不能改善网络数据传输的稳定性，L-AODV路由协议提高了网络数据传输的稳定性，但是由于没有考虑节点能量，因此L-AODV没有改善网络能量的利用率，而LE-AODV路由协议由于综合考虑了链路质量和节点能量，因此LE-AODV路由协议不仅可以提高网络能量利用率也能提高网络数据传输的稳定性。

图7　节点的分组投递率对比图

图8　节点能量状态对比图

仿真场景二仿真参数如表4。

表4　仿真场景二参数表

在仿真节点数量为100时，取不同Hth值，通过比较分析不同Hth值情况下LE-AODV路由协议的分组投递率，来选取合适的Hth值，仿真结果如图9所示。当Hth取不同值时，整个网络的分组投递率都超过了80%，当Hth值从2增加到5时，整个网络的分组投递率逐渐增加，而当Hth值继续增加时，整个网络的分组投递率开始降低，这说明Hth值增加，备选路径的数量也会增加，虽然LE-AODV路由协议最优路径选取的算法可以选取到最优路径，但是较多备选路径和产生的大量的路由回复信息RREP会增加整个网络的延迟，降低整个网络的生存时间。因此综合考虑分组投递率和整个网络的效率，Hth值可以取5。

图9　不同Hth取值LE-AODV路由协议的分组投递率

取Hth值为5，设定仿真时间设为60 min，改变节点的数量，图10为不同节点数量情况下的网络生存时间。由图10可知，节点数量的增加会增加网络生存时间，这是因为更多的节点提供了更多的路径选择，LE-AODV、E-AODV路由协议的网络生存时间要高于AODV、L-AODV路由协议。在图10中，在节点数量为120时，LE-AODV路由协议的网络生存时间为58 min，AODV路由协议的网络生存时间为42 min，网络生存时间增加了16 min，在节点数量为60时，LE-AODV路由协议的网络生存时间为51 min，AODV路由协议的网络生存时间为41 min，网络生存时间增加了10 min。随着节点数量的增加，LE-AODV路由协议能增加更多的网络生存时间。LE-AODV、E-AODV路由协议由于考虑了节点能量，避免了网络中发生热点现象，延长了网络生存时间，但是由于E-AODV路由协议没有最优路径的选取机制，E-AODV路由协议需要频繁的发起路由发现的过程，因此会消耗额外的能量，导致E-AODV路由协议的网络生存时间要低于LE-AODV路由协议。

图10　网络生存时间对比图

图11为不同节点数量情况下分组投递率PDR。由图11可知，随着节点数的增加，网络的分组投递率会降低，这是因为节点数量增加后，路径的跳数会增加，跳数增加后提高了丢包的可能性导致了分组投递率的下降。在图11中，LE-AODV、L-AODV路由协议的分组投递率要高于AODV、E-AODV路由协议，说明AODV、E-AODV路由协议由于没有考虑链路质量，选取的路径丢包的可能性增加，因此分组投递率低于LE-AODV、L-AODV。LE-AODV路由协议的分组投递率要高于L-AODV路由协议，这是因为L-AODV路由协议仅考虑了链路质量，因此L-AODV路由协议路由发现过程中可能选取到跳数比较多的路径，跳数比较多的路径也会降低分组投递率，而LE-AODV路由协议由于有最优路径选取的机制，阈值Hth限制了LE-AODV路由协议路径的跳数，随着节点数量的增加，LE-AODV路由协议仍能保持较高的分组投递率，保证了数据传输的稳定性。

图11　分组投递率对比图

4　总结

本文针对WSN对网络能量的高效使用以及数据传输的稳定性的要求，考虑节点之间链路质量和节点能量，对AODV路由协议进行改进，提出了基于链路质量和节点能量的LE-AODV路由协议。在路由发现过程中选取链路质量较高的链路，通过最优路径选取的机制对路径的最低节点能量状态和跳数进行限制，节点能量状态更新机制避免了网络中热点的产生。仿真结果显示，LE-AODV路由协议能够延长网络生存时间，提高分组投递率，从而保证了WSN网络能量的高效使用和数据传输的稳定性。在本文的研究中，在不同节点数量情况下，路径跳数差Hth阈值的取值对最优路径选取的影响以及在不同的环境情况下，LQIth阈值的设定对路由发现过程的影响还需要进行深入研究。在后续的工作中，需要针对不同Hth阈值和LQIth阈值对路由选取和路径发现的影响进行进一步的研究。

［1］ 钱志鸿，王义君.面向物联网的无线传感器网络综述［J］.电子与信息学报，2013（1）：215-227.

［2］ 王境，徐桢，刘晓春.基于链路质量的无线传感器网络抗干扰路由协议［J］.传感技术学报，2012，25（1）：87-93.

［3］ 王巍，李丛，王云.基于WSN的AODV路由协议的研究与改进［J］.计算机与现代化，2012（11）：182-185.

［4］ 路纲，周明天，佘堃.无线传感器网络路由协议的寿命分析［J］.软件学报，2009，20（2）：375-393.

［5］ Ren J，Zhang Y，Zhang K，et al.Lifetime and Energy Hole Evolution Analysis in Data-Gathering Wireless Sensor Networks［J］. IEEE Transactions on Industrial Informatics，2015：1.

［6］ 孙彦景，林昌林，江海峰.一种能量高效的分布式非均匀分簇路由算法［J］.传感技术学报，2015，28（8）：1194-1200.

［7］ Butt M R，Akbar A H，Kim K H，et al.LABILE：Link Quality-Based Lexical Routing Metric for REactive Routing Protocols in IEEE 802.15.4 Networks［J］.Journal of Supercomputing，2012，62（1）：84-104.

［8］ Standard I.Wireless Medium Access Control（MAC）and Physical Layer（PHY）Specifications for Low-Rate Wireless Personal Area Networks（LR-WPANs）［C］.IEEE Std.2010.

［9］ Samundiswary P，Bhardwaj H.Performance Analysis of Energy Aware AODV Routing Protocol For IEEE 802.15.4 Enabled WSN［J］.International Journal of Computer Applications，2013，63（19）：43-46.

［10］Mammu A S，Hernandez-Jayo U，Sainz N，et al.Cross-Layer Cluster-Based Energy-Efficient Protocol for Wireless Sensor Networks［J］.Sensors，2015，15（4）：8314-8336.

［11］Gomez C，Boix A，Paradells J.Impact of LQI-Based Routing Metrics on the Performance of a One-to-One Routing Protocol for IEEE 802.15.4 Multihop Networks［J］.Eurasip Journal on Wireless Communications&Networking，2010，4（2）：50-50.

［12］刘大勇，赵春江.基于AODV的农田无线传感器网络路由和休眠算法［J］.微电子学与计算机，2015（10）：115-120.

［13］Farooq H，Jung L T.Energy，Traffic Load，and Link Quality Aware Ad Hoc Routing Protocol for Wireless Sensor Network Based Smart Metering Infrastructure［J］.International Journal of Distributed SensorNetworks，2013，13：264-273.

［14］Boulis A.Castalia a Simulator for Wireless Sensor Networks and Body Area Networks，Version 3.2，User'smanual［EB/OL］.http：// castalia.npc.nicta.com.au/.

杜海韬（1988-），男，硕士研究生。研究领域为无线传感网络路由协议的优化与应用，banehallow@126.com；

李强（1973-），男，山东烟台人，博士，研究员。研究方向为移动通信、超宽带、物联网技术、数据融合等，liqiang@mail.sim.ac.cn；

丁广太（1966-），男，博士，副教授，研究领域为数字图像处理。

The Research of AODV Routing Protocol Based on Link Quality and Node Energy in WSN*

DU Haitao1，2，LI Qiang2，3*，DING Guangtai1，WANG Yingguan2，ZHU Leiji3
（1.School of Computer Engineering and Science，Shanghai University，Shanghai 20044，China；2.Shanghai Institute of Microsystem and Information Technology Chinese Academy of Sciences，Shanghai 201899，China；3.Shanghai Internet of Things CO.LTD，Shanghai 201899，China）

In order to meet the demands of energy efficiency use and data transmission stability，the routing protocol of the wireless sensor network needs to be further improved.This paper proposes a LE-AODV routing protocol based on the link quality and energy status of node.The LE-AODV routing protocol adopts the cross-layer design. During the route discovery process，optimal path is selected by acquiring the link quality information and the node energy information from MAC layer and physical layer.Meanwhile，hot spots in the network will be avoided by the node energy status updating mechanism.In this paper，the Castalia simulator is applied to accomplish the simulation of the LE-AODV routing protocol.The research result shows that the LE-AODV routing protocol can effectively improve the packet delivery rate and prolong the network lifetime.

wireless sensor network；link quality；node energy；LE-AODV routing protocol；castalia simulator

TP393

A

1004-1699（2016）07-1042-07

项目来源：上海市浦江人才计划项目（14PJ1433100）

2016-01-16修改日期：2016-02-24