AODV中稳定兼能量感知的路由改进协议

刘期建，郑 涛

（中国民用航空飞行学院 计算机学院，四川 广汉618307）

0 引 言

前人对MANET 已经提出了多种路由协议，基于路由发现原则，将其分为先应式和反应式［1］。反应式或按需路由协议仅当需要发送某个数据包时，才使用广播查询应答（PREQ－RREP）过程来确定路由。大多数协议采用最小跳数作为路由选择度量。前人发现最短路径路具有较短的寿命，尤其在高密度自组织网络中，即使由于边缘效应导致了低移动性［2］。然而，它们都没有解决在数据传输过程中如何降低链路断开的问题。在大多数按需路由算法中，它需要一定的时间来检测链路故障，然后启动路由恢复过程［3，4］，这会消耗大量资源，如带宽、能量等，还引入额外的延迟。由于再次进行路由发现，网络的效率大大降低。

本文提出一种 “先接后断”机制，来增强RSEAAODV 中的路由维护性。当存在移动性、能量消耗和拥塞等任何可能导致链路中断的原因时，可通过跨层法找到一个数据传输的替代路径。仿真结果表明，在高负载和高动态环境下，本文所提方法的性能优于RSEA 和LAER。

1 相关研究

文献 ［5］将链路稳定性定义为链路的稳定程度和通信持续的时间长短的一个度量。信号强度是一个用于评估链路稳定性的参数。文献 ［6］中提出一种跨层法和节点移动性预测改进路由协议，实现基于跨层调解和节点位置预测的稳定性路由。文献 ［7］提出了利用图论的方法实现网络的重连接以此实现稳定路由。这些协议在不同程度上实现了稳定路由，但各有适用的范围。

文献 ［8］中N.Sharma根据接收到的信号强度计算出链路稳定性和路由稳定性，进而提出RSQR，其基于阈值，将链路分为稳定链路和不稳定链路。

文献 ［9］提出EBL，作者认为链路稳定性和剩余电池容量都很重要。EBL不仅提高了能量利用率，而且减少了网络的分割。文献 ［10］提出LAER，它们将链路稳定性和能量流失率的联合指标考虑进路由发现之中，从而减少了控制开销，以及平衡了流量负载。

借助备份路由，AODV－BR［12］在不可预知的链接中断时，实现了路由的快速恢复，其是通过监测数据包和RREP包来更新。在高度密集的网络中这会导致很高的控制信息开销和碰撞。

2 问题的描述

MANET 的拓扑结构表示为无向图G ＝（V，E），其中V 是节点集合，E 是节点连接的边的集合。令P（u，v）＝｛P0，P1，P2，...，Pn｝，其中每个Pi是一个u和v间的可行路径。考虑到路由稳定性和剩余能量，从源到目的节点选择最优路径的问题可描述为

其中

并且Ri＞EThr1，qi＜QThresh。

其中Ri和Fi分别是节点的剩余能量和全部容量。

对目标的每个指标提供重要度因子w1和w2，上面的最优化可转换成一个单目标问题，表示如下

最大化目标的和，表示如下

三级节点。三级节点主要是对水域附近资源点的介绍以及交通指引，安全提示，珍惜动植物，特殊地质地貌景观，文化景观、历史遗迹的介绍性解说和警告性解说。比如对于黄鞠灌溉工程的资源点介绍等。

3 所提的改进路由协议

本节 主 要 讨 论RSEA－RM （route stability and energy aware routing with route maintenance）路由的具体步骤，其主要包括路由发现、路由选择及路由维护。

3.1 路由发现

当节点需要发送数据包到某个目的节点时，它会搜索路由缓存中的路由。如果到达目的节点D 的路由不可达时，源节点S会将其路由请求RREQ 广播发送给邻居节点。当收到RREQ 数据包后，中间节点检测其强度，这样它就接收了节点的数据包和剩余能量。如果信号强度和剩余能量超过了阈值，节点检查其负载指标，否则它将会丢弃该路由请求。如果队列长度超过QThresh值，那么路由请求数据包将会丢失，以避免接下来的数据传输拥塞。如果信号强度超过SThrl，那么LS 就设置为1。如果信号强度在SThr1 和SThr2 之间，那么LS 就根据分化的信号强度（differentiated signal strength，DSS）计算得到。

借助计算累计路径稳定性 （accumulated path stability，APST）和累计能量 （accumulated energy，AE）函数，并且在发往邻居节点前，在RREQ 数据包的头段进行更新。计算的稳定值也将会在邻居信息表中更新。然后路由请求就带着更新的APST 和AE值转发到它的邻居节点了。

3.2 路由选择

当目的地节点收到第一个RREQ，它就将计时器Δt启动t秒。根据目标函数 （式5）、路由请求中收到的APST和AEC值来计算路径的可靠性。它存储了包含在路由缓存中的可靠性值的所有的RREQ。在定时器超时后，它找出了具有最小目标值的路径，然后将RREP 发送给它。在计时器Δt完成计时后，将丢弃到达的路由请求。

算法1：目标节点执行

3.3 路由维护

“先接后断”机制如算法2所示，对于因移动性、能量流失和拥塞引起的链路中断，其能迅速适应。每隔t1秒执行一次，以监测路由建立的状态，其中t1值根据节点的移动性设置。

如果中间节点处于电池电量严重不足的状态或者接收的信号包非常微弱，那么它将会创建一个TTL 设置为1的HLP分组，然后将其发送给邻居节点。邻居节点接收到HLP数据包后，根据HLP 数据包的描述，在其目的节点路由表中检查路由的可用性。如果路由可用，那么它将路由返回给该节点发送的HLP数据包中的下游节点。下游节点收到路由后，更新路由表。数据包在新的路由中进行传输，防止由于链路中断导致的数据包丢失。

如果具有电量不足的节点为目的节点时，那么它会给源节点发送停止传输的指示，以避免可能的数据包丢失和资源浪费。同样也检查接口队列长度是否超过了QThresh，以避免拥塞。

如果计时器计时完成后，即超时，还没有可以替代的单跳节点路由，那么该节点会向源节点发送路由更改请求（route change request，RCR）。源节点接收到RCR 后，会进行目的节点的路由发现，在现有路由的链路中断前找出一个替代路由。与此同时，邻居节点的路由表将随着路由改变而更新。如果总能量将要流失的节点是源节点，它则继续传输数据直到总能量流失结束。

如果在局部路由修复过程中，存在去往目的节点的替代路由，该机制将迅速适应网络的变化。这样就增加数据包传输率，并且减少了丢包数量和延时的发生。避免数据包传输到不可用的中间节点，减少了资源浪费。

算法2：路由维护

4 实验结果及分析

4.1 性能指标

归一化控制开销 （normalized control overhead，NCO）指的是传输的控制包与目的节点接收到的控制包的比值；数据包传输率 （packet delivery ratio，PDR）指的是目的节点接收到的数据包数量与源节点发送的数据包数量的比值；节点剩余能量方差：该指标计算了节点间能量使用的分布；端到端延迟：是衡量数据包到达目的地平均时间的指标。

4.2 模拟参数

本文在仿真工具NS2［12］上进行模拟。模拟环境参数如表1所示。其中，节点数50，拓扑大小为1000m×500m，流数为10，节点的传输范围为250 m，每个数据包大小为512字节。

表1 模拟参数

4.3 仿真结果分析

针对多个不同的移动速度0，5，10，15和20，进行了一组广泛的模拟。运行10次模拟，给出所得结果的平均值作为性能指标的数值。

图1可以观察到由于链路中断和路由修复过程引起的NCO 随着移动性的增加而增加。在较低移动性时，所提方法、RSEA 和LAER 的 NCO 分 别 为5.1%、5.4% 和6.3%。在高移动性时，所提方法、RSEA 和LAER 的NCO 分别为22.8%、26.2%和31.3%。RSEA 在高速动态环境中，显示出更好的性能。因为 “先接后断”和局部路由修复机制，这导致了相对其它两种协议更少的控制开销。更早地预测链路中断，数据传输能够在原路由链路中断前切换到替代路由。

从图2可观察到，在所有3个协议中，PDR 随着速度的增加而降低。降低的原因是速度提高时频繁的链路中断和路由的再次寻找。在高速移动性时，所提方法、RSEA和LAER 的PDR 分别为94.7%，93.8%和91.3%。所提方法相对于RSEA 来说PDA 增加了1%，这是因为它结合了 “先接后断”路由维护机制，这大大减少了由于不可预测的链路中断导致的数据包丢失的数量。

剩余节点能量的方差如图3所示。该参数表征了协议的负载平衡能力。观察到，随着移动性的增加，由于频繁的路由转换，节点剩余能量方差逐渐减小。低移动时，所提方法、RSEA 和LAER 的能量方差百分比分别为18.8%，19.2%和21.54%。高 移 动 性 时，所 提 方 法、RSEA 和LAER 的能量方差百分比分别为7.8%，8.3%和11.3%。

如图4所示，3个协议的端对端延迟随移动性的增加而增加，这是由于频繁的路径中断的缘故。高移动性时，所提方法、RSEA 和LAER 的平均端对端延迟分别为0.18s，0.21s和0.32s。所提方法延迟最低的原因是避免了由于节点移动性和电池能量流失引起的链路中断。RSEA 协议中结合了 “先接后断”路由维护机制，可以很快适应网络的变化。在高速移动性时，所提方法性能上比RSEA 高出14%。

图1 控制开销与节点移动性的关系

图2 PDR 与节点移动性的关系

图3 能量方差与节点移动性的关系

图4 端对端延迟与节点移动性的关系

5 结束语

本文主要讨论RSEA－RM 路由的具体步骤，其主要包括路由发现、路由选择及路由维护，通过实验将该协议与其它类似路由协议如RSEA 及LAER 在NS2上，在多种情形下进行多次模拟和对比，实验结果表明，所提方案通过预先警报显著提高了数据包传输率，减少了由不可预测链路中断引起的控制开销和延迟。它与LAER 相比，也减少了节点能量方差，增加了网络分区的时间。在高速动态网络中，它表现出更优越的性能。在移动性较低的情况下，所改进方法与LAER 相比，延迟略高。今后，在不同节点密度、流量和移动模型中，所提协议将会是研究的一部分。

［1］ZHANG Guoyin，LI Jun.Mobile peer－to－peer network ［J］.Journal of Software，2013，24 （1）：139－152 （in Chinese）.［张国印，李军.移动对等网络覆盖网 ［J］.软件学报，2013，24 （1）：139－152.］

［2］LU Yang，TIAN Yiming，WEI Zhen，et al.Complex－network effects of multi－radio wireless ad hoc networks ［J］.Journal of Applied Science，2012，30 （2）：111－115 （in Chinese）.［陆阳，田一鸣，魏臻，等.多射频无线ad hoc网络的复杂网络效应 ［J］.应用科学学报，2012，30 （2）：111－115.］

［3］Minhas UF，Zhang J，Tran T，et al.Towards expanded trust management for agents in vehicular ad－hoc networks［J］.International Journal of Computational Intelligence Theory and Practice，2010，5 （1）：3－15.

［4］Morteza Maleki，Karthik，Pedram.Power－aware source routing protocol for mobile ad hoc networks ［C］／／ISLPED，2008.

［5］LIU Rong，WANG Dong，LI Xiaohong.Based on the remaining time to live link stability routing protocol in mobile ad hoc network ［J］.Engineering and Computer Science，2012，34（12）：9－15 （in Chinese）.［刘荣，王东，李晓鸿.移动ad hoc网络中基于剩余生存时间的链路稳定性路由协议 ［J］.计算机工程与科学，2012，34 （12）：9－15.］

［6］Noppakum Y，Phongsak K.AODV improvement for vehicular networks with cross layer technique and mobility prediction ［J］.Intelligent Signal processing and Communication Systems，2011，8 （2）：89－95.

［7］Panichpapiboon S，Ferrari G，Tonguz OK.Connectivity of ad hoc wireless networks：An alternative to graph－theoretic approaches［J］.Wireless Networks，2010，16 （3）：793－811.

［8］Nityananda Sharm，Sukumar Nandi.Route stability based QoS routing in mobile ad hoc networks［J］.Wireless Personal Com－munications，2010，54 （1）：203－224.

［9］Park GW，Lee S.A routing protocol for extent network lifetime through the residual battery and link stability in MANET［C］／／Applied Computing Conference，2008.

［10］Jinchang L，Maode M.Cross－layer QoS support framework and holistic opportunistic scheduling for QoS in single carrier WiMAX system ［J］.Journal of Network and Computer Applications，2011，34 （2）：765－773.

［11］Nityananda S，Sukumar N.Route stability based QoS routing in mobile ad hoc networks［J］.Wireless Personal Communications，2010，54 （1）：203－224.

［12］Geng Y，He J，Pahlavan K.Modeling the effect of human body on TOA based indoor human tracking ［J］.International Journal of Wireless Information Networks，2013，20 （4），306－317.