移动Ad hoc网络基于链路可用时间的动态源路由协议

　　摘要：为了提高链路的稳定性，增加路径可用时间，提出一种应用于移动Ad hoc网络的基于链路可用时间的动态源路由协议(LARP)。该协议以路径可用时间作为路径评价的参数，优先选择具有最大路径可用时间的路径进行数据包传递。路径可用时间反映了当前节点移动对路径稳定性的影响，其数值取决于路径中的最小链路可用时间。仿真结果表明该协议相对于动态源路由协议(DSR)，提高了路径稳定性，减少了路由发现次数，有效提高了吞吐量等网络性能。

　　0 引言

　　移动Ad hoc网络(MANET)是一种不依赖于任何固定设施的无线网络。网络中的节点可以自由移动，具有数据转发的功能，从而形成了网络的多跳特性。因此，路由成为移动Ad hoc网络中进行数据通信的核心问题。

　　目前国内外有很多关于路由协议的研究。主要可以分为先验式路由协议和反应式路由协议。先验式路由协议定期更新路由信息，对拓扑结构的变化反应灵敏，但是该类协议需要维护路由表并定期更新路由表信息，费了大量的网络带宽。反应式路由协议仅在需要路由时才进行路由发现，有效节省了网络资源。但是节点的移动可能会导致已有的链路发生断裂，使已有的路径失效，从而发启新的路由发现过程。这不仅会降低数据包的成功发送率，还会带来新的路由发现开销。

　　因此，为了减少移动性带来的链路断裂，提高链路的稳定性，本文提出了一种基于链路可用时间的路由协议。该协议可以有效增加路径可用时间，并提高网络吞吐量等性能。

　　1 基于链路可用时间的动态源路由协议

　　本文提出的路由协议LARP选择具有最大路径可用时间的路径进行路由。路径可用时间由路径中的最小链路可用时间决定，而链路可用时间可以通过节点之间的相互运动模型进行计算。另外，为了减少节点随机移动带来的影响，通过历史链路可用时间信息，预测下一时刻的链路可用时间。

　　1.1 路由选择参数

　　1.1.1 链路可用时间

　　图1呈现了发送节点s和接收节点r之间的相对移动过程。假设点S代表节点s在时刻t1时所处的位置，在时间t1、t2、t3，节点r相对于节点s的位置分别为R1、R2和R3，这三个时刻s和r之间的距离分别为D1、D2和R，而这些距离可以通过无线传播模型计算得到。节点s和节点r相对地面的移动速度分别为vs和vr，则以s为参照系，如图1所示，节点r相对于节点s的相对移动速度为v，v=vr-vs。

　　已知节点r在时刻t1和时刻t2的位置，而节点r移动出发送者范围的时刻t3未知。为了求得链路可用时间，需要对时刻t3进行预测。根据余弦定理知道以下公式：

　　式(1)中存在三个未知变量θ、v、t3，但只有两个有效的等式，因而求解还需要另一个包含这三个未知变量的额外的公式。根据面积相等SSR1R3=SSR1R2+SSR2R3和海伦公式

　　式(1)和式(2)中存在三个未知变量θ、v、t3，且存在三个有效的等式，因而可以求得这三个未知变量。从而，计算得到链路的可用时间TL(s，r)=t3-t2。

　　1.1.2 链路可用时间预测

　　节点移动具有随机性，处于一个动态变化的过程，可能造成实际链路可用时间值的急剧波动。因此，获得准确的实时值是非常困难的。本文利用链路可用时间的历史信息值，预测当前的链路可用时间。

　　假设T时刻的链路可用时间为，T-1时刻的链路可用时间为，则T+1时刻的链路可用时间为

　　其中，0≤a≤1，表示之前时间段对当前链路可用时间的影响因子，不失一般性，选取a为0.7。

　　1.1.3 路径可用时间

　　假设存在路径P：S，…，i，j，…，D，源节点S进行路由发现过程，发送路由请求包到目的节点D。路由请求包经过链路(i，j)，在时刻tj预测出链路可用时间为。当tD时刻路由请求包到达目的节点D时，链路(i,j)的可用时间并非tj时刻预测的值，变为。因而，可以求得路径上每个链路的链路可用时间。

　　路径可用时间为各个链路可用时间的最小值，因为当路径中存在一条链路不可用时，则整个路径不可用。路径可用时间为

　　其中，任意链路(i，j)∈P。

　　1.2 LARP路由协议

　　LARP路由协议建立在DSR协议的基础上，分为路由发现和路由维护两个部分。其中，路由维护部分与DSR相同，主要区别存在于路由发现的选择过程中。

　　LARP协议的路由请求包在DSR的基础上添加了预测的链路可用时间字段LAT(Link Available Time)和当前时钟字段CT(Current Time)，用于记录路由路径中各个预测的链路可用时间和路由请求包经过各个链路的时间。在各个节点的路由表中也增加了路径可用时间字段PAT(Path Available Time)，用于存放各个路径的可用时间信息。

　　(1)在路由发现阶段，路由请求包在增加的LAT和CT两个字段中记录沿途各个链路的可用时间和路由请求包经过相应链路的时间。

　　(2)当路由请求包到达目的节点后，提取其中的预测链路可用时间参数(LAT)和时钟参数(CT)，利用式(4)计算出该路径的可用时间。

　　(3)目的节点收到的多个路由请求包代表从源节点到该目的节点的多个可能路径，求出每条路径的可用时间信息后，目的节点为每个路由请求包回复一个路由应答包，将链路信息和路径可用时间信息回复给源节点，并在路由表中相应地记录链路信息和路径可用时间。

　　(4)当源节点需要再次发送数据包时，首先查找路由表，若路由表中已存在到达目的节点的路径，则在这些路径中选择具有最大路径可用时间的路径进行数据转发;若路由表中不存在可用路径，则进行路由发启过程。

　　(5)路由维护过程和DSR相同。

　　2 实验结果与分析

　　仿真实验使用NS-2.34，在DSR的基础上实现了所提出的LARP路由协议。实验参数如下：网络中有50个节点，拓扑区域为1000×1000m，网络节点随机分布。移动模型采用随机位点模型(RWP)，节点最大速度为15m/s。MAC层采用IEEE 802.11协议。节点通信范围均为250m。在实验中随机选取了12条固定比特率(CBR)的数据流，每个源节点每秒发送120个512字节的CBR分组。仿真时间为1000s。结果如下：

　　图2显示了网络吞吐量，随着节点移动速度的增加，这两种路由协议的吞吐量都呈减小趋势，但LARP协议的网络吞吐量明显高于DSR。这是因为LARP协议选择具有最大路径可用时间的路径进行数据包转发，有效提高了链路的稳定性，减少了移动性带来的影响。

　　图3显示了节点移动速度对数据包投递率的影响。LARP协议的路径由于具有更高的稳定性，因而减少了链路断裂带来的丢包，有效地提高了数据包投递率。图中可以看到，LARP协议的数据包投递率高于DSR。

　　3 结束语

　　本文提出了一种基于链路可用时间的动态源路由协议。该协议以路径可用时间作为路径评价的参数，选择具有最大路径可用时间的路径，避免了频繁的链路断裂，提高了链路稳定性，从而减少了路由发现次数。仿真结果显示，本文提出的LARP协议同DSR协议相比，显著地提高了路径稳定性，减少了路由发现次数，有效提高了吞吐量等网络性能。