基于可靠稳定性评价的MANET多路径路由优化算法

李智楠 杨晓冬②



基于可靠稳定性评价的MANET多路径路由优化算法

李智楠*①杨晓冬①②

①(哈尔滨工程大学信息与通信工程学院 哈尔滨 150001)②(日本明星大学联合研究中心 东京 191-8506)

针对移动Ad hoc网络动态拓扑特性，该文提出一种以可靠路径稳定度估计为基础的多路径路由优化算法。该算法从路径剩余生存期统计特性出发，充分考虑相邻链路生存期相关性，从而消除已有算法在路径稳定度估计中存在的理论误差，并利用优化后的稳定度准则实现路由发现进程的多路径选取和基于备用路径支持的快速路由修复。仿真对比结果表明，该算法具有较快的收敛速度，能够有效提高网络吞吐量，缩短数据传输时延并降低路由开销，更好地保证较高节点移动度下的数据传输稳定性。

移动Ad hoc网络；路径剩余生存期；稳定性估计；多路径路由；路由修复

1 引言

为了缓解移动Ad hoc网络(MANET)时变拓扑特性对移动传输的不利影响，近年来基于链路或路径剩余生存期(Residual Link/Path Lifetime, RLL/ RPL)估计的链路动态特性分析[1]及“稳定性”优先路由策略成为了MANET研究关注的重点。虽然现有算法一定程度上实现了网络优化，但仍存在很多不足。首先，以RLL估计为基础的路由算法强调链路级别的逐跳路由决策[5,6]，造成大量网络资源及节点能量消耗；其次，路径稳定性分析中的RPL估计均忽略了由节点共享引起的相邻链路RLL相关性[3,7]，造成的估计误差使算法在优化能力方面具有很大局限性；另外，上述问题同样存在于已有的多路径稳定性路由策略中，限制了算法可靠性。

为了弥补这一不足，本文在充分考虑相邻链路RLL相关性前提下，提出一种以路径RPL统计特性作为稳定性评价标准的多路径路由优化算法(RELiability-enhanced Multipath Source Routing, REL_MSR)。该算法基于反应式(reactive)源路由协议，改进了路由发现进程中路由请求(Route REQuest, RREQ)和路由应答(Route REPly, RREP)报文格式及其转发处理机制，能够实现备用路径支持的快速路由修复。

2 RPL统计特性及稳定性标准

该稳定性标准提出的目的在于：(1)在RPL估计中充分考虑相邻链路RLL统计相关性，提高理论建模准确性；(2)提供更可靠的多路径选取准则，增强MANET动态环境下的通信连续性。

2.1 多条链路RLL联合概率密度分布

目前绝大部分MANET路由优化策略[3,12,13]在RLL与RPL统计特性分析中，为简化计算或降低算法复杂度，均沿用如下结论：多跳路径生存期()服从指数分布[3,13]且可由构成该路径的条链路生存期()表示为[12]

以上结论前提条件为：(1) 路径中各链路生存期保持统计独立[12]；或(2) 路径跳数足够多，各链路长度足够大(渐进条件)[13]。如图1所示，链路和生存期同时受共享节点移动性的影响，必然存在相关性，文献[14]给出了该相关性的仿真证明，因此条件(1)中的独立性假设并不成立；实际MANET部署受能量供给和通信质量影响，节点传输范围和路径跳数均受限，因此条件(2)很难满足。针对上述问题，本文在已有工作[14]基础上，以充分考虑RLL相关性为前提，提出一种更准确的链路及路径稳定性统计定义方法。根据图1给出的多跳路径移动参数，设节点传输半径为,为RLL估计时刻与相对距离，,为速度和方向角，为的RLL(且)。文献[14]中式(15)给出当固定时的概率密度分布(PDF)表达式：

(2)

(4)

(5)

(7)

进一步利用已知变量可得

(9)

(11)

各链路RLL联合CDF为

(13)

虽然与链路独立条件下的结果相比，本文理论建模复杂度有所增加，但当网络中路径跳数较少，各节点遵循统一且较为简单的移动模型(如)时，很容易得到式(12)的解析解。

图1 多跳路径节点移动参数及RLL与RPL相互关系

图2 ,与的相对速度及空间方位关系

2.2 链路及路径稳定度评价准则

基于上述理论建模，本文进一步给出如下链路及路径稳定度定义：

定义1 链路稳定度(Link RELiability, LREL)为链路RLL不小于特定时间间隔的概率，对于：

定义2 路径稳定度(Path RELiability, PREL)为路径RPL不小于的概率，对于路径(含条链路)：

(15)

以上定义的合理性及优越性在于：(1)节点移动复杂度较低时，移动模型不受限；(2)充分体现了链路或路径在规定时间内保持有效性的能力。另外，文献[14]中表1给出：忽略链路RLL相关性会导致PREL估计值偏高，不利于路由选取。因此，本文所给定义能够为路由算法提供更准确的稳定性评价标准。

2.3 PREL对网络性能的影响

从网络层角度，PREL的重要性主要体现在以下两方面。首先实际代表某一预期时延为的数据经过路径的成功传输概率。若时间内有个数据被成功接收，则网络吞吐量可定义为

由式(17)可知：路由算法所选路径PREL值与TD成反比，进一步证明了提高PREL的重要意义。

3 REL_MSR算法实现

与主动式(proactive)路由协议不同，反应式路由协议只在数据传输请求产生时创建节点间路由，节省了路由维护成本。动态源路由协议(Dynamic Source Routing, DSR)是经典的反应式路由协议，其最大特点为：RREQ中可携带通信节点间完整路由信息，便于LREL与PREL估计。这是REL_MSR算法优化的基础。

3.1 RREQ转发及参数更新

3.2 多路径选取及RREP发送

REL_MSR算法采用基于LREL和PREL估计的多路径选取，其特点为：主路径(MP)和备用路径(BP)允许“部分相交(partially disjoint)”[4](链路共享)。这一准则依据为：(1)节点间严格不相交(node disjoint)路径数量受限于最小割定律[8]，且稳定度往往无法满足传输要求；(2)若允许共享的链路足够稳定，则可消除因单条链路断裂导致多路径同时失效的可能性，从而保证备用路径数量和路由修复的有效性。

3.3 路由修复机制

基本源路由协议不具备路由修复机制。当数据传输中路径失效，只能通过RREQ泛洪重启路由发现进程，造成大量的路由开销。REL_MSR算法利用备用路径策略实现快速路由修复，具体方法为：当首先负责数据传输的MP失效，断裂链路的上游节点向发送路由错误(Route ERRor, RERR)报文，选取PREL最高的BP作为新的MP进行数据续传，若多条BP同时满足要求，则选择其中跳数最少的路径。

图3 REL_MSR算法RREQ及RREP报文格式

表1 目的节点处路由选取算法

算法1 目的节点处RREQ处理及路由选取描述： 目的节点收到来自上游节点的RREQ报文1 if () or (RREQ中路径与已记录的具有相同(,)的某条路径重合) or (PREL<)2 丢弃RREQ报文3 else 将添加到RREQ的中4 if (为(,)对应第1条路径)5 设置该路径为MP6 为(,)设置选取BP7 else if ((,)路径记录已存在) and ()8 丢弃RREQ报文9 else if (与已有(,)路径严格不相交)10 将该路径加入并记录其PREL11 else找出与已有(,)路径的共享链路12 if (共享链路不包含)13 跳转到15行14 else计算并设定15 检验所有共享链路16 if (所有检验结果 == 1)17 将该路径加入并记录其PREL计算结果18 else丢弃RREQ报文19 end all if

4 性能仿真及分析

运用MATLAB仿真平台实现MANET建模，将本文REL_MSR算法与另外两种稳定性路由算法PRMLE[3]和LEBR[6]进行对比。首先比较3种算法的路由发现收敛时间，再进一步通过吞吐量()、平均数据传输时延()和路由开销()的仿真结果比较，验证本文算法的有效性和优越性。表2给出了3种算法核心思想(不涉及PRMLE算法中继节点网络编码部分)。其中LEBR基于按需距离矢量路由协议(Ad hoc On-demand Distance Vector, AODV)。AODV的 RREQ和RREP报文中只包含其转发节点的一跳信息。PRMLE本地路由修复机制是指当数据传输路径中某条链路稳定度降低时，中间节点可以进行数据缓存并启动路由发现机制建立与目的节点的新路径，而REL_MSR算法的路由修复则是由集中控制。

表2 3种算法核心思想及实现方法

算法名称链路稳定性准则路径稳定性准则算法类别路由修复链路相关性 PRMLE链路生存期()：相邻节点接收功率周期性采样，文献[3]式(1)~式(18)路径生存期()：改进DSR单BP中间节点本地修复不考虑 LEBR链路有效性(L)：链路LL与平均LL之比，文献[6]式(29)和式(30)路径有效性(): 改进AODV无BP无不考虑 REL_MSRLREL：式(14)PREL：式(15)改进DSR多BP源节点修复考虑

4.1 算法收敛时间仿真对比

本文针对反应式路由算法改进，为了考察算法收敛速度，比较REL_MSR与PRMLE, LEBR算法的路由发现收敛时间，即路由建立时间[15](平均完成单个(,)路由请求的耗时)。仿真实现方法为：(1)将个移动节点随机分布于面积为100 m×100 m的区域内，各算法以=5 s为周期执行单次路由发现，共进行100次；(2)各周期(,)随机选取，于周期初始时刻广播RREQ，当成功接收规定数量的RREP报文时，路由发现结束；(3)单周期内各节点移动速度和方向服从均匀分布(V~U(0,max),且保持恒定；(4)各算法每隔记录路由发现耗时，最终取100次输出记录的平均值作为结果。

为了排除网络协议栈其他各层因素(如节点间通信退避机制，传输带宽配置)、单个节点计算延迟及路由表存储对算法性能评估的影响，仿真进一步假设：(1)路由发现过程中只有可以发送RREP报文，中间节点只负责报文转发和处理；(2) RREQ在各转发节点所需更新时间统一设为20 ms，即转发同步(不考虑各算法在计算所需参数时的复杂度差异)；(3)相邻节点报文传输耗时均为40 ms；(4)PRMLE和本文REL_MSR算法处RREP接收(路径选取)时限为60 ms，仿真为LEBR算法设置相同的路径选取时限，目的是使其在单次路由决策中选出最优路径；(5)链路断裂条件为两节点间距离大于传输半径=15 m，若负责RREP传输的链路在其经过前发生断裂，则路由建立失败，需立即重新广播RREQ再次尝试路由发现。

图4 节点数变化时仿真结果

图5 节点移动度变化时仿真结果

4.2 网络性能指标仿真对比

现考虑算法改进对网络整体性能影响，首先做如下假设：(1)仿真中不考虑MAC层及物理层环境影响(如信道衰落或乱序造成的传输误差)，数据到达即视为正确接收；(2)链路具有足够带宽避免网络拥塞；(3) RREP报文均能被正确接收；(4)路由修复允许数据续传，无需重启路由发现；(5)若路由发现重新启动，则丢弃数据流中已接收到的部分，等待重传；(6)各节点随机移动模型相同：V。

仿真参数设置如表3所示。仿真中应用层采用的每个CBR数据流预期传输时延(time slot)。本文REL_MSR算法及估计中取。为算法预设因子，设置目的在于：理论上规定并保证各链路(路径)RLL(RPL)值大于。仿真中设。其次，各组参数下系统在仿真周期()初始时刻分配60个数据请求(含不同,)，后输出并记录各项性能指标，仿真截止(100)后各指标取其所有输出值的均值作为最终统计结果。最后，仿真中若路由发现进程重启3次后数据传输仍无法完成，则数据丢失。另外，设PRMLE算法用于功率采样的HELLO报文发送周期为1 (time slot)。

表3 网络性能仿真参数设置

参数名称参数设置 仿真区域400 m×400 m 节点数600~800 仿真周期100 time slot 仿真运行时间100 数据类型固定速率数据流(CBR) 单个数据尺寸100 packets 发送速率2 packet/time slot 路由协议PRMLE/LEBR/REL_MSR 路径选取时限Timer =2 (time slot) 节点传输半径50 m 节点最小速率0 节点最大速率1~6 m/s

综上所述，图6-图11的仿真结果充分验证了本文算法的有效性及优越性：与现有算法相比，REL_MSR算法充分考虑了相邻链路RLL相关性，能够建立更准确、可靠的稳定性评估准则，使数据传输依赖于生存期更长的路径，有效减弱节点高速移动对数据传输造成的不利影响，具有更强的适应性，并且在提高网络，缩短数据的同时保证较低的，实现稳定性与资源利用的合理兼顾。

图6 节点数变化时仿真结果

图7 节点数变化时仿真结果

图8 节点数变化时仿真结果

图9 节点移动度变化时仿真结果

图10 节点移动度变化时仿真结果

图11 节点移动度变化时仿真结果

5 结束语

本文在路径RPL统计特性分析基础上，充分考虑相邻链路RLL相关性，提出一种优化的路径稳定性评估准则，进而提出一种基于可靠路径稳定度估计的多路径路由优化算法。仿真对比结果表明：与已有稳定性路由算法相比，本文算法能够提供更可靠的路径稳定性评估准则，在网络拓扑动态性较高的情况下依然能够保持较快的收敛速度，并且能够有效降低节点移动度上升对数据传输造成的不利影响，在提高MANET网络吞吐量，缩短数据传输时延，减少路由开销方面具有重要意义。

[1] 郑博, 黄国策, 张衡阳. 三维移动Ad hoc网络链路动态性研究[J]. 电子与信息学报, 2011, 33(11): 2605-2609. doi: 10.3724/SP.J.1146.2011.00191.

ZHENG Bo, HUANG Guoce, and ZHANG Hengyang. Link dynamics in three-dimensional mobile Ad hoc networks[J].&, 2011, 33(11): 2605-2609. doi: 10.3724/SP.J.1146.2011.00191.

[2] MOUSSAOUI A and BOUKEREAM A. A survey of routing protocols based on link-stability in mobile ad hoc networks[J]., 2015, 47: 1-10. doi: 10.1016/j.jnca.2014.09.007.

[3] WU Dapeng, WANG Ruyan, and ZHEN Yan. Link stability- aware reliable packet transmitting mechanism in mobile ad hoc network[J]., 2012, 25(12): 1568-1584. doi: 10.1002/dac.1323.

[4] SALEEM M, ULLAH I, KHAYAM S A,. On the reliability of ad hoc routing protocols for loss-and-delay sensitive applications[J]., 2011, 9(3): 285-299. doi: 10.1016/j.adhoc.2010.07.012.

[5] AKBARI TORKESTANI J and MEYBODI M R. A link stability-based multicast routing protocol for wireless mobile ad hoc networks[J]., 2011, 34(4): 1429-1440. doi: 10.1016/j.jnca. 2011.03.026.

[6] LEI Lei, WANG Dan, ZHOU Liang,. Link availability estimation based reliable routing for aeronautical ad hoc networks[J]., 2014, 20: 53-63. doi: 10.1016/ j.adhoc.2014.03.005.

[7] WU Dapeng, ZHOU Jianer, and WANG Ruyan. Received signal strength based link lifetime estimating mechanism in MANET[C]. IEEE Conference Anthology, Chongqing, China, 2013: 1-4. doi: 10.1109/ANTHOLOGY.2013.6784986.

[8] SANTOS M A S, PORRAS D E T, SILVEIRA R M,. Multipath source routing strategies for video transmission in ad hoc wireless networks[J]., 2014, 21(3): 859-869. doi: 10.1007/s11276-014-0823-x.

[9] KUMAR C N and SATYANARAYANA N. Multipath QoS routing for traffic splitting in MANETs[J]., 2015, 48: 414-426. doi: 10.1016/j.procs. 2015.04.115.

[10] YI J, ADNANE A, DAVID S,. Multipath optimized link state routing for mobile ad hoc networks[J]., 2011, 9(1): 28-47. doi: 10.1016/j.adhoc.2010.04.007.

[11] YANG Wenjing, YANG Xinyu, YANG Shusen,. A greedy-based stable multi-path routing protocol in mobile ad hoc networks[J]., 2011, 9(4): 662-674. doi: 10.1016/j.adhoc.2010.09.004.

[12] Triviño-Cabrera A, García-de-la-Nava J, Casilari e,. Application of path duration study in multihop ad hoc networks[C]. IFIP Advances in Information and Communication Technology, Prague, Czech Republic, 2007: 63-74. doi: 10.1007/s11235-008-9094-0.

[13] HAN Y, LA R J, Makowski a m,. Distribution of path durations in mobile ad hoc networks-Palm’s theorem to the rescue[J]., 2006, 50(12): 1887-1900. doi: 10.1016/j.comnet.2005.10.005.

[14] LI Zhinan and HAAS Z J. On residual path lifetime in mobile networks[J]., 2016, 20(1): 185-188. doi: 10.1109/LCOMM.2016.2520467.

[15] FENG Renjian, LI Tongling, WU Yinfeng,. Reliable routing in wireless sensor networks based on coalitional game theory[J]., 2016, 10(9): 1027-1034. doi: 10.1049/iet-com.2015.0884.

Optimized Multipath Routing Algorithm for MANET Based on Reliable Stability Estimation

LI Zhinan①YANG Xiaodong①②

①(,,150001,)②(,191-8506,)

To deal with dynamic network topology in Mobile Ad hoc NETworks (MANETs), a reliability-enhanced multipath source routing algorithm is proposed based on accurate path stability estimation. In order to eliminate theoretical errors existing in current approaches, statistical properties of residual path lifetime are exploited by fully introducing correlation among neighboring links’ residual link lifetime. Optimized link and path stability metric is then provided to realize a multipath-enabled routing discovery procedure and a backup path-support fast routing recovery mechanism. Simulation results show that the proposed routing algorithm can achieve fast routing discovery convergence, increase network throughput, reduce data transmission delay, and lower routing overhead. Furthermore, high network reliability can be well guaranteed even under high node mobility degree.

Mobile Ad hoc NETworks (MANETs); Residual path lifetime; Stability estimation; Multipath routing; Routing recovery

TN929.5

A

1009-5896(2017)03-0605-08

10.11999/JEIT160462

2016-05-09；改回日期：2016-11-21；

2017-01-11

李智楠 zhinan5447@163.com

李智楠： 女，1987年生，博士生，研究方向为无线通信系统理论、MANET路由优化算法.

杨晓冬： 男，1963年生，教授，博士生导师，主要研究方向为现代通信系统技术与理论、现代天线技术.