2. 桂林电子科技大学 广西可信软件重点实验室, 广西 桂林 541004
Ad hoc网络中现有的预测路由协议在路由失效前提前修复路由却增大了路由开销.针对路由开销大的问题，提出了一种基于Ad hoc按需距离矢量路由协议并结合两种路由维护方式的预测辅助路由协议.协议中的每个节点都可能发起路由维护，根据节点在路由中的位置选择对应的路由维护方式；根据网络中节点移动特性与网络规模计算节点判决路由失效的能量阈值，确定是否发起路由维护.仿真结果表明，协议在保证网络可靠性的基础上比传统预测算法降低了3%~5%的网络路由开销，尤其适用于节点数目较多且移动速度较慢的网络.
2. Guangxi Key Laboratory of Trusted Software, Guilin University of Electronic Technology, Guangxi Guilin 541004, China
The existing routing protocols for Ad hoc networks maintain routing before routing becomes invalid, but this method leads to a high overhead. To reduce the overhead, a prediction-aided routing protocol based on Ad hoc on-demand distance vector routing was proposed which contained two different methods of routing maintenance modes. Every node can maintain its routing based on prediction-aided routing protocol and compute the threshold which decides whether to maintain the routing with the speed of nodes and network environment. Simulation results demonstrated that proposed protocol could reduce 3%~5% overhead of network than the traditional prediction algorithm on the basis of ensuring the reliability of network, especially suitable for the network environment which has more numbers of nodes and slower mobility of nodes.
在Ad hoc网络中自组织按需距离矢量路由协议(AODV, Ad hoc on-demand distance vector routing)[1]只在路由失效之后才发起路由维护，增加了数据包的丢失率.基于节点接收的信号强度进行预测的方法被提出，该方法估计出节点间的距离从而预测路由是否即将失效[2-3]，并在信号强度低于能量阈值时发起路由维护[4-5].提出了预测辅助的路由协议，协议根据节点在路由中所处位置的不同决定节点执行对应的路由维护方式，再根据路由维护的时间与网络规模预测该节点用于判决路由即将失效的能量阈值，提高了路由的使用率，减小了路由开销.
1 预测辅助路由协议预测辅助路由协议的设计在原有按需路由协议基础上添加了路由失效预测，可分为路由发现、路由失效预测、路由维护3部分.
1.1 路由发现在网络的初始阶段以AODV协议为基础建立路由，源节点在自身路由表中没有查到至目的节点的路由时，以广播路由请求消息[1]的方式建立路由.对于相同的路由请求消息，任意节点只处理第1次接收的，若自身不是目的节点则继续广播该路由请求消息，否则向源节点回复路由回复消息[1].源节点在不超时的情况下接收到路由回复消息，路由建立完成，并开始传输数据，此时该路由也叫做活动路由[6]，且路由中每个节点均已知自身在路由中的跳数、路由总跳数.
1.2 路由失效预测预测辅助路由协议为活动路由中的节点确定了维护路由的方式，不同的维护方式所需要的时间不同，该时间与节点预测的能量阈值有关联.本节先介绍节点维护路由所需的时间.
1) 2种路由维护方式
① 重启路由发现
路由中的节点N需要发起路由维护时，先判断自身在路由中的位置.若节点N距离目的节点D的跳数大于路由总跳数的三分之一，则采用重启路由发现的方法，否则采用本地修复的方法(见下文).
图 1所示节点N经判断后向源节点S发送路由错误消息[1]，节点S收到路由错误消息后执行路由发现.由于此时网络拓扑与路由建立之初相比发生了变化，考虑网络最恶劣的情况[2]，为了避免数据包的丢失提出维护一次路由所需要的时间为
|
图 1 重启路由发现 |
| $ t = 3TK $ | (1) |
其中T为路由消息经过一跳所需的时间K为网络中允许路由建立的最大跳数.然而该时间不够精确.预测辅助路由协议设维护后的路由跳数为H1+H2+α, K两者的最小值，通过预测算法发起一次重启路由，发现所需时间为
| $ t = T\left[{{H_1} + 2{\rm{min}}({H_1} + {H_2} + \alpha, K)} \right] $ | (2) |
其中：H1代表源节点距离当前节点的跳数，H2代表目的节点距离当前节点的跳数，α的取值为经验值，并保证路由以足够大的概率维护成功.
② 本地修复
图 2所示为本地修复过程：节点N距离目的节点D的跳数小于等于路由总跳数的三分之一时，节点N广播路由请求消息以建立新的路径，为了减少路由消息在网络中的泛洪，设置路由请求消息的生存时间值H2+β，β的取值由节点数目所决定.同时也说明预测辅助路由协议维护完成后节点N~D的跳数不大于生存时间，节点通过预测算法发起一次本地修复所需时间为
|
图 2 本地修复 |
| $ t = 2T({H_2} + \beta ) $ | (3) |
2) 能量阈值
路由中每个节点在确定其路由维护方式后计算能量阈值.预测辅助路由协议根据自由空间模型将节点间距离换算成能量值，能量值为
| $ W = \frac{{P{G_1}{G_2}{\lambda ^2}}}{{{{\left( {4{\rm{\pi }}d} \right)}^2}L}} $ | (4) |
其中：P为节点发送信号的能量值，G1为天线发送信号的增益，G2为天线接收信号的增益，λ为波长，d为两节点间距离，L为系统损耗. P、G1、G2、λ、L均为常数.可将式(4) 化简为
| $ W = \frac{C}{{{d^2}}} $ | (5) |
为了使路由在维护完成之前不失效将提前发起路由维护, 将两节点距离为
| $ d=R-tv $ | (6) |
时收到的信号能量强度作为能量阈值, 式(6) 中R为节点的通信半径，t为维护路由所需的时间，v为节点间的相对速度(假设节点可获知)，则能量阈值为
| $ W = \frac{C}{{{{\left( {R-tv} \right)}^2}}} $ | (7) |
3) 判断路由失效
路由中节点监测其下一跳节点，每收到下一跳节点发送的包(如周期发送的HELLO消息，ACK消息等)时将它的信号强度与能量阈值比较，如果信号强度小于阈值则认为路由即将失效，否则继续监测直到该路由不被使用.
1.3 路由维护路由维护只发生在活动路由中，如果中间节点认为路由即将失效，该节点立刻修复路由，使路由在真正失效之前完成新旧路由的切换.若维护失败则在路由真正失效后重新发现路由.
2 仿真与结论为了比较提出算法与文献[2]算法、AODV的性能，进行仿真实验.表 1给出了仿真所使用的具体参数.所有实验结果均为100次实验的平均值.
|
表 1 仿真环境参数 |
归一化路由开销和数据包投递率为最常用的网络性能度量标准.
归一化路由开销：路由消息数与节点发送数据包总数的比值，即每传输一个数据包所需要的路由消息数，反映了网络的路由效率.
数据包投递率：目的节点所接收的数据包与源节点发送的数据包之比，反映了网络传输的可靠性.
2.2 网络性能分析图 3描述了节点数量为50、40、30、20时归一化路由开销与节点移动速度之间的关系.在网络中节点数目相同时，随着节点最大移动速度增加，3种协议的归一化路由开销均增大，这是因为网络中的路由失效次数增加，其中提出算法的归一化路由在节点最大移动速度相同时，随着节点数目的增加，3种协议的归一化路由开销均增大，这是由路由消息以广播方式进行路由发现所导致的.其中提出算法的归一化路由开销相比于文献[2]算法更低，尤其在节点数目较多时，相比文献[2]算法最多可降低5%.
|
图 3 节点移动速度—归一化路由开销 |
图 4描述了节点数量为50、40、30、20时数据包投递率与节点移动速度之间的关系.在节点数目相同时，随着节点最大移动速度从1 m/s增加到20 m/s，3种协议的数据包投递率均减小，其中提出算法的数据包投递率相比文献[2]算法减小了约2%~4%；而在节点数目比较少时更为明显，但是依然大于AODV协议，这是因为节点速度的增加使得网络拓扑变化频繁，而且在节点数目较少时不可达的路由更易出现，使提出算法维护路由成功的概率下降，同时由于预测部分的存在使得数据包的投递率大于没有采用预测的AODV协议.
|
图 4 节点移动速度—数据包投递率 |
Ad hoc网络由多个移动节点组成，网络的拓扑结构不断改变.提出的预测辅助路由协议对现有的预测路由协议改进，基于两种维护方法对路由提前进行维护与切换，有效降低了路由开销.文中并没有对节点间的相对速度，节点移动模型做深入研究，因此做进一步研究对估计能量阈值的精确性有一定的意义.
| [1] | Perkin B C, Royer E M, Das S. RFC 3561—2003, Ad hoc on demand distance vector routing[S]. (200-07-15)[2016-03-10]2003. |
| [2] |
洪利, 黄庭培, 邹卫霞, 等. 基于链路可用性预测的AODV路由协议研究[J]. 通信学报, 2008, 29(7): 118–123.
Hong Li, Huang Tingpei, Zou Weixia, et al. Research of AODV routing protocol based on link availability prediction[J]. Journal on Communications, 2008, 29(7): 118–123. |
| [3] | Husieen N A, Ghazali O, Hassan S, et al. Redirect link failure protocol based on dynamic source routing for MANET[C]//Intemational Conference on Networked Digital Technologies: Heidelberg. Berlin: Springer, 2012:577-591. |
| [4] | Sankar S, Sankaranarayanan V. A predictive route maintenance protocol based on signal strength for dense Ad hoc networks[J]. International Journal of Computer Theory & Engineering, 2012: 570–574. |
| [5] | Yadav A, Singh Y N, Singh R R. Improving routing performance in AODV with link prediction in mobile Ad hoc networks[J]. Wireless Personal Communications, 2015, 83(1): 603–618. doi: 10.1007/s11277-015-2411-5 |
| [6] | Alsaqour O, Alsaqour R, Alahdal T, et al. A comparative study of simulation based performance evaluation of routing protocol for ad hoc networks[J]. Lecture Notes in Electrical Engineering, 2015(313): 215–221. |