战术MANET中基于链路可用时间的AODV路由协议研究＊

周 胶，田 杰，戴晨铖，李婷君

（武警工程大学研究生管理大队，陕西 西安 710086）

1 引言

移动Ad Hoc网络[1]（MANET）是指由一组无线移动节点组成，不需要依靠现有固定通信网络基础设施并能够迅速投入使用的网络体系，具有很高的可靠性和灵活性。移动Ad Hoc网络的高机动性和快速开展使其在加强战场通信和提高战场通信系统的生存能力方面有广泛的应用[2]，战术MANET 就是MANET 在战场环境下的应用。MANET 中移动节点位置的快速变化导致网络拓扑结构改变、网络信息（例如路由表）作废以及节点间链路断开[3]。为了保证网络中数据传输的稳定性，减少重路由过程，通过研究路由协议在网络中找到一条相对稳定的路径一直是Ad Hoc网络研究的热点[4]。近年来突出链路稳定性的路由协议[5]、网络安全的路由协议[6]以及车载自组网路由协议[7]等仍是研究的热点。

AODV[8]路由协议是一种经典的按需路由协议。在路由发送过程中，选取路径时只考虑路由的跳数、新旧程度等，而不能保证选取路径的相对稳定性；在路由维护阶段，只有在链路断开时才启动路由维护过程，降低了数据发送的稳定性。在文献[9]中，节点通过计算转发角来发送数据，数据发送的成功率有所降低，同时计算链路失效时间没有考虑节点的移动对下一时刻链路失效时间的影响。文献[10]通过能量预测链路的可用性，对于链路状况的预测准确度要比GPS（Global Positioning System）定位系统差。

本文在深入研究AODV路由协议的基础上，针对其选取链路的不稳定性、路由修复较慢等特点提出一种改进路由协议LAT-AODV，该协议结合GPS系统，能够与部队的实际作战需求充分结合。LAT-AODV路由协议通过GPS定位系统计算链路可用时间以及路径的最大可用时间，使得源节点在路由建立过程中把路径的最大可用时间作为选取路径的标准。在路由恢复阶段，通过设定时间触发器，当链路可用时间低于阈值时则认为链路不可用，启动链路修复机制，在链路断开以前切换路径，保证数据的稳定传输。

2 预测式链路可用时间算法

假设在战术MANET 中每个节点都配置GPS定位系统，而且本模型中电源的可用时间远大于通过计算得出的链路生存时间。预测式链路可用时间算法的核心思想是：相邻节点通过GPS系统交换时标和坐标信息，计算节点间的链路生存时间。当中间节点转发路由请求和路由应答时，通过记录前几次的链路生存时间，借助随机停留点模型计算下一段时间链路连续可用的概率，计算链路可用时间。

2.1 链路生存时间

假设节点n1、n2为两相邻节点，在t1、t2时刻节点n1的坐标为（x1n1，y1n1）和（x2n1，y2n1），节点n2的坐标为（x1n2，y1n2）和（x2n2，y2n2）。在以n1为坐标原点的极坐标中，t1、t2时刻，n2在极坐标系中的坐标为（R1，α1）和（R2，α2），通过计算可得出：

如图1a所示，点A 和点B 表示n2在t1和t2时刻的位置，图中的箭头表示n2相对于n1的移动方向，则可以根据位置信息和时间信息计算出n2相对于n1的运动速度：

Figure 1 Two nodes movement图1 两节点运动方式

假设在预测的过程中节点从B 运动到C 的过程中速度不变，当节点n2运动到C 时即将脱离n1的通信范围，所以节点n2从B 运动到C 的时间即为n1n2间链路的生存时间。两节点间的链路生存时间为：

其中，R 表示节点的通信范围，即图1a中大圆的半径，T＝e （n1，n2）即为链路n1n2的链路生存时间。

图1a表示两节点距离先近后远的情况，图1b表示两节点反向运动的情况，R 表示节点的通信范围，即图1b中大圆的半径，其计算过程如下：

根据以上公式，可以计算出每个节点与其相邻节点链路生存时间e（n1，n2）。

2.2 链路危险时间

链路危险时间是指当链路可用时间小于阈值时，即视为链路即将断裂。在路由请求过程中，若链路可用时间低于链路危险时间，则节点不转发上一跳节点的路由请求RREQ（Route REQuest），既保证了链路的可靠性又限制了路由请求的广播范围。在路由维护阶段，当链路的可用时间低于链路危险时间时，启动路由维护过程，在链路真正断开前进行路由维护，保证数据稳定传输。LATAODV路由协议的路由维护过程包括：路由危险警告或者路由出错和路由建立。现考虑最坏的情况，每种消息经过的跳数都是网络直径的值，路由建立过程包括路由请求和路由应答，则改进后AODV路由维护过程的总跳数为网络直径的三倍。假定链路的可用时间小于最大的路由维护时间，则认为链路处于一种危险状态，实验选择的网络直径为NET＿DIAMETER，根据文献[8]可知，每一跳的传输时延为30ms，则链路危险时间为：

2.3 链路可用时间

链路的生存时间表示的是某一时刻相邻节点可通信的时间，LAT-AODV路由协议通过三个连续时刻链路的生存时间预测在下一段时间内链路连续可用的时间。

假设n1和n2表示网络中两个相邻的节点，节点n1记录与节点n2最近三个周期中的链路生存时间分别为eT-2（n1，n2）、eT-1（n1，n2）、eT（n1，n2），eT-2（n1，n2）表示当前T 时刻计算出的链路生存时间，eave（n1，n2）表示三个周期链路生存时间的平均值，Δe（n1，n2）表示当前链路生存时间变化率，Δe（n1，n2）的计算方法为：

判断Δe（n1，n2）的大小：

（1）若Δe （n1，n2）≥0，说明两节点有靠近的趋势，则链路处于安全状态，链路可用时间t（n1，n2）计算方法为：

其中α、β、φ 表示历史信息对将来信息的影响，为了不失一般性，三个参数的取值如下：α＝0.6，β＝0.3，φ＝0.1。

（2）若Δe （n1n2）＜0，表示两节点的通信距离有变远的趋势，则可根据随即停留点模型计算链路从T 到T＋t时刻连续可用的概率有[11]：

根据计算出的链路可用性概率P（t），链路的可用时间为：

其中，α＝0.6，β＝0.3，φ＝0.1。

3 LAT-AODV路由算法

与传统的AODV 算法相比，LAT-AODV路由算法有以下四点改进：

（1）在路由请求阶段，在RREQ 数据包中添加链路可用时间和上一跳节点参数，选择性转发上一跳节点的路由请求数据包，降低网络负载，提高所选路径的可靠性。

（2）在回溯阶段，在路由应答数据包RREP（Route REPly）中添加路径可用时间参数和上一跳节点参数，记录每一条路径的可用时间。

（3）当节点发现链路生存时间小于链路危险时间时，启动路由恢复机制，在链路断开前切换路径，保证数据的稳定传输。

（4）在计算路径可用时间时，若一条完整的路由路径中的某一条链路不可用，则整个路径也变得不可用，因此一条路由的可用时间依赖于整个路径中最小的链路可用时间。

3.1 链路建立过程

LAT-AODV路由协议需要在RREQ 数据包中添加上一跳节点Lasthop 和链路可用时间Li-fetime 两参数。如图2所示，Lasthop 表示上一跳节点序列号，Lifetime 表示上一跳节点通过预测式链路可用时间算法计算出来的链路可用时间。LAT-AODV路由协议同时需要在节点路由条目中添加LRoutetime项，表示当前传输路径的可用时间。

Figure 2 Data structure of RREQ图2 RREQ 数据结构

3.1.1 路由请求过程

源节点广播RREQ 数据包发送路由请求。中间节点i接收到RREQ 数据包，其工作过程如图3所示。

Figure 3 Progress of routing request图3 路由请求过程

（1）判断接收到的RREQ 数据包中链路可用时间和链路危险时间的大小，若Lifetime＞TW进入（2）；否则说明该链路不可靠，不进行数据转发。

（2）判断路由表中是否有从节点i到达目的节点的路径，若有则初始化RREP数据包，并回溯至源节点；否则进入（3）。

（3）节点i计算与其相邻节点的链路可用时间，转发新的RREQ 数据包，将本节点序列号和计算的链路可用时间添加到新RREQ 数据包对应的域。

3.1.2 路由回溯过程

在RREP数据包中添加上一跳节点Lasthop和路径可用时间time。路径可用时间time表示上一跳节点到目的节点的路径持续可用时间Route（Lasthop，Dst）。

中间节点i接收到RREP 数据包时工作过程如下：

（1）节点i计算其与上一跳节点的链路可用时间t（i，Lasthop），比较t（i，Lasthop）和Route（Lasthop，Dst）的大小，选取较小的作为路径可用时间Route（i，Dst）。

（2）将time＝Route（i，Dst），Lasthop＝i放入新的RREP 数据包中，同时初始化本地路由表中到达目的节点的路由LRoutetime＝Route（i，Dst），继续回溯。

当源节点S 接收到RREP时，Route（S，Dst）＝min｛t（S，Lasthop），Route（Lasthop，Dst）｝。源节点S 比较所有回溯的路径，选取Route（S，Dst）最大的路径为到达目的节点的路由，同时修改LRoutetime＝Route（S，Dst）。

3.2 路由维护过程

LAT-AODV路由协议路由维护的思想是在链路真正断开前实现路由修复过程，保证数据的稳定传输。当中间节点检测到其与下一跳节点的链路可用时间小于链路危险时间TW时，节点即启动链路修复，其修复过程不影响正在传输的数据，保证数据稳定传输。

4 仿真与分析

仿真实验采用NS-2.35[12]，实验在1 000m×1 000m的矩形仿真场景中选取40个节点，节点的移动速度变化范围为10m／s～35m／s，仿真实验参数参见表1。

Table 1 Experimental parameters表1 实验参数

实验中两组算法性能比较结果如图4～图6所示。

Figure 4 Packet delivery ratio图4 数据包投递率

Figure 5 Network end-to-end throughput图5 网络吞吐量

Figure 6 Network end-to-end delay图6 端到端时延

当节点的移动速度从10m／s增加到35m／s时，LAT-AODV路由协议的包投递率降低了32个百分点，AODV路由协议的包投递率降低了41个百分点；LAT-AODV路由协议的网络吞吐量降低了36个百分点，AODV路由协议的网络吞吐量降低了48 个百分点；LAT-AODV路由协议的网络时延增加了500ms，AODV路由协议的网络时延增加了630ms。当节点的移动速度增加到25m／s以后，节点的快速移动导致网络的拓扑结构快速变换，链路稳定性降低，两种协议的网络性能都显著降低。但是，LAT-AODV路由协议的性能要明显高于AODV路由协议，这是因为LATAODV 在路由建立过程中充分考虑路径的稳定性，在路由维护阶段对可能断开的链路提前进行路由维护，保证了数据的稳定传输。

5 结束语

本文在AODV路由协议的基础上，运用链路可用时间算法，提出LAT-AODV路由协议。基于GPS定位系统，利用位置信息计算链路的可用时间，在路由建立阶段为源节点找到路径可用时间最大的路由，在路由维护阶段对可能断开的链路提前维护，保证数据的稳定传输。仿真实验表明，LATAODV路由协议在数据包投递率、网络吞吐量、端到端时延方面有显著的提高。下一步在链路可用时间计算上，根据链路生存时间的变化趋势，通过拟合函数计算下一时间段的链路可用时间，验证新算法得出的LAT-AODV路由协议性能。

[1]Chen Lin-xing，Zeng-xi.Mobile Ad hoc networks：Self-organizing packet radio network technology[M].Beijing：Publishing House of Electronics Industry，2006：4-11.（in Chinese）

[2]Sharret I P.WIN-T—The army's new tactical intranet[C]∥Proc of IEEE MILCOM'99，1999：1383-1387.

[3]Jun Luo，Hubaux J-P.Joint sink mobility and routing to maximize the lifetime of wireless sensor networks：The case of constrained mobility[J].IEEE Transactions on Networking，2010，18（3）：871-884.

[4]Tyagi S，Chauhan R.Performance analysis of proactive and reactive routing protocols for ad hoc networks[J].International Journal of Computer Applications，2010，1（14）：27-30.

[5]Rajendiran M，Srivatsa S K.Stable route link in on-demand multicast routing protocol for ad hoc networks[J].Procedia Engineering，2012，38：1391-1398.

[6]Qabajeh L K，Kiah M L M，Qabajeh M M.A more secure and scalable routing protocol for mobile ad hoc networks[J].Security and Communication Networks，2012，6（3）：286-308.

[7]Bhaumik M，DasGupta S，Saha S.Affinity based clustering routing protocol for vehicular ad hoc networks[J].Procedia Engineering，2012，38：673-679.

[8]Perkings C，Belding E，Royer B，et al.RFC365l，Ad hoc ondemand distance vector（AODV）routing[S].IETF，2003.

[9]Xia Zi-jun，Liu Chun-feng，Zhao Zeng-hua，et al.Routing algorithm in vehicular Ad Hoc network based on link prediction[J].Computer Engineering，2012，38（4）：110-111.（in Chinese）

[10]Hong Li，Huang Ting-pei，Zou Wei-xia.Research of AODV routing protocol based on link availability prediction[J].Journal on Communications，2008，2.（7）：118-123.（in Chinese）

[11]Bettstetter C，Hartenstein H，Perez-costa X.Stochas-tic properties of the random waypoint mobility model[J].ACM／Kluwer Wireless Networks，2004，10（5）：555-567.

[12]Ke Zhi-heng，Cheng Rong-xiang，Deng De-xie.Simulation of NS2—Multimedia and wireless communication networks[M].Beijing：Publishing House of Electronics Industry，2009.（in Chinese）

附中文参考文献：

[1]陈林星，曾曦，曹毅.移动Ad Hoc网络：自组织分组无线网络技术[M].第2版.北京：电子工业出版社，2006.

[9]夏梓峻，刘春凤，赵增华，等.基于链路预测的VANET路由算法[J].计算机工程，2012，38（4）：110-111.

[10]洪利，黄庭培，邹卫霞，等.基于链路可用性预测的AODV路由协议研究[J].通信学报，2008，2.（7）：118-123.

[12]柯志亨，成荣祥，邓德隽.NS2仿真实验——多媒体和无线网络通信[M].北京：电子工业出版社，2009.