基于链路稳定性预测的Ad Hoc网络路由算法研究

姜延涛

（中国人民解放军65631部队60分队，辽宁 北镇121300）

1 课题来源

移动Ad Hoc网络[1]是一种多跳、自组织、分布式的无线网络，它不需要集中式的网络管理和基础设施。针对Ad Hoc网络的特点，国内外学者提出了很多路由协议。相对于单径路由协议而言，后备路径路由协议更能满足容错、路由可靠性要求，因而成为该领域的研究热点。本文讨论将成本函数应用到后备路由选择中，再结合地理位置预测模型预测链路稳定性来确定主备路由，利用此算法改进AODV协议。最后通过软件仿真的手段，论文实现了LS-BPR协议，并评价了它的路由性能。通过仿真验证算法性能。

2 多路路由算法分析

随着对Ad Hoc网络的研究的不断深入，单路路由协议的研究己经相对成熟。但是，简单的单路路由协议还不能满足容错、路由可靠性等更高层次的路由要求。多路路由恰恰是解决这些问题的一个很好的途径。

3 基于成本函数的后备路径路由算法实现

3.1 成本函数中相关参数的定义及计算

在这里提出一种BPR（Backup Path Routing）算法，它是引入了成本函数作为后备路径的选择原则。在主路径确定之后，再通过主路径和所选路径计算成本函数值，来确定需要的后备路径。

为了能够找到一个路由可靠度的衡量标准，我们需要一个近似的计算公式，来对路由有效期进行计算和比较。为此，BPR算法引入了成本函数的概念。给定备份路由对(λ,λ′)，当路径长度|λ′|越小；节点相似度L(λ,λ′)越小；独立子路径R(λ,λ′)越大时，备份路由对的路由有效期都会越长，路径就会越可靠。因此用备份路由对(λ,λ′)的成本函数值C(λ,λ′)的启发式来估算路由可靠度。成本函数值与路由有效期成反比，C(λ,λ′)的值越小，备份路由对就越可靠。

定义:假设λ是主路径,λ′是后备路径，L(λ,λ′)是主备路径对(λ,λ′)的链路相似度,R(λ,λ′)是主备路径对(λ,λ′)不相交子路径的数目,|λ′|表示后备路径λ′的总跳数，则主备路径对的(λ,λ′)的成本函数定义为:

由于主路径上节点由于频繁的移动造成无线链路发生断裂时，由于后备路径与主路径公用节点的数目较少，所以也就降低了后备路径也同样发生断裂的可能性，所以最可靠的后备路径就要选择使C(λ,λ′)值最小的后备路径。

3.2 基于链路稳定性预测的后备路径选择算法研究

基于ARIMA模型分析方法的基本思路是：对于非平稳的时间序列，用若干次差分使其成为平稳序列，再用ARMA(p,q)模型对该平稳序列建模，之后经反变换得到原序列。并且根据样本自相关函数、偏自相关函数的统计特性来判断随机序列适合哪一模型，进而确定模型阶数[2]。

为了使用ARIMA模型改善BPR算法的性能，所以本文提出了基于运动轨迹预测链路稳定性的后备路径路由算法LS-BPR（Link Stability Prediction Algorithm based on Backup Path Routing）。

LS-BPR算法的基本思想是，在确定源节点到目的节点的后备路径时，考虑节点的移动性所带来的链路稳定性的变化和链路的传输延迟，用链路有效时间来衡量链路稳定性，利用ARIMA预测模型预测节点移动性，提前得知下一时刻该节点的地理位置[3]，即能够提前预测节点的运动轨迹，减少了后备路径在下一时候断开的可能性。通过GPS系统获取节点的地理位置，形成一段时间序列，然后利用ARIMA预测模型对地理位置进行预测，得到下一时刻的地理位置，从而获取一个节点的运动轨迹。

3.3 下一时刻地理位置的使用

在QualNet中，不存在GPS模块，但是可以通过其他方法获取到节点的地理位置，如下方法。

节点的地理位置坐标定义为

通过snt/qualnet/5.0/main/node.cpp文件我们知道节点当前地理位置为：

由于QualNet中只对二维拓扑进行仿真，那么在实际中，z坐标的值为0。

在snt/qualnet/5.0/include/mobility.h中增加定义了移动节点MobilityData的所存储的历史地理位置的信息：

struct MobilityData{

4 基于链路稳定性预测的后备路径路由协议仿真与分析

4.1 仿真环境

根据移动自组网在实际中的应用，本文使用QualNet进行仿真，采用以下仿真场景进行仿真分析，仿真区域是在1500m×1500m的矩形区域，区域内随机分布35个节点。节点的移动方式采用随机路点移动方式，符合Random Waypoint模型，每个节点的移动速度最大值可调节，设备移动间隔尺寸为1m。发送CBR数据包，每个包大小为512字节，网络流量以固定比特率CBR(Constants Bit Rate)产生，采用单信道，带宽为2Mbps，仿真时间为100s，每个节点使用相同的无线收发设备，采用单一增益的全向天线，仿真比较LS-BPRAODV与AODV的性能。

为了反映不同路由协议在所设置场景下的网络性能，本文选用平均端到端时延和数据包投递率作为性能指标，分别从节点最大速度参数变化着手，研究以下两种性能指标的变化规律：

（1）数据包投递率（Packet Delivery Ratio）

分组投递率是成功传递到目的端的数据包数与发送端成功发送的数据包数之比。该指标反映了接收方受网络拓扑变化影响的程度。

（2）平均端到端时延(AverageEndtoEndDelay)

平均端到端时延是从源节点成功到达目的节点的所有数据分组的端到端时延的平均值。

4.2 仿真结果与性能分析

移动速度：

35个节点的最大移动速度分别为5m/s，10m/s,15m/s,20m/s,25m/s,30m/s,35m/s,40m/s时，移动方向随机，共发100个数据包，每个CBR数据包大小为512字节，暂停时间20秒,发包率为1包/秒。仿真结果显示当节点移动速度增加时，两种协议的传输时延都在增大。这是因为节点的运动速度越大，网络拓扑变化越激烈，那么路由断裂的可能性大大增加，路由断裂次数也大大增加，从而导致数据发送需要的等待时间增长，传输时延增加。由图可得，但从图中可以发现LS-BPR AODV受节点最大移动速度的影响相对较小。

仿真结果还显示数据包投递率与最大速度之间的关系。当节点运动速度增加时，LS-BPRAODV与AODV的投递率都在降低。这是因为节点移动速度越大，网络局部拓扑变化越激烈，造成路由中断次数增加，目的节点不可达的现象增多，从而造成网络的丢包率增加。由图可得，LS-BPRAODV的丢包率要明显低于AODV，这是因为在前者的路由算法中，加入了成本函数与地理位置预测算法。LS-BPRAODV偏向于利用丢包率更低的后备路由。同时，加入地理位置预测后，能够提前预知链路的断裂，减少路由中断的次数。通过这两种机制的同时作用，提升了数据包投递率。

［1］陈代武.计算机网络技术[M].北京:北京大学出版社,2009:290-292.

［2］王黎明,王连,杨楠.应用时间序列分析[M].上海:复旦大学出版社,2008:1-85.

［3］林彦汝,周继鹏.基于地理位置的AdHoc路由协议[J].计算机应用,2011(1):225-228.