基于回报加权的Ad Hoc预测路由协议的研究

李 晶 肖忠良 吴桂华

1(娄底市第一人民医院 湖南 娄底 417000)2(娄底职业技术学院电子信息工程学院 湖南 娄底 417000)3(湖南电子科技职业学院 湖南 长沙 410205)

0 引 言

随着无线通信技术的发展，可移动终端设备的应用场景越来越广泛，人们对无线网络提出了更高的要求[1]。移动Ad Hoc网络是由一组带无线收发功能的移动终端设备组成的自组织无线网络[2]。与传统的有基站的网络不同，Ad Hoc网络没有固定的基础设施，无须设置任何中心控制节点，且由于每个节点都是移动的，因此Ad Hoc支持无基站的快速组网和网络恢复，特别适用于动态网络拓扑结构中的无线数据传输[3]。

Ad Hoc网络是一种不依赖任何固定网络设施就能快速布设的自组织网络技术，具有独立组网能力自组织特点[4]。每个节点都是动态地保持与其他节点的联系。无线Ad Hoc网络的任意某个节点A与另一个节点B在进行数据的分组传输，当目的节点B不在节点A的无线频率覆盖范围时，它们可以通过一个或多个中间节点转发报文进行通信[5]。每个节点都可以提供到其他节点的路由发现以及路由维持功能[6]。

由于Ad Hoc网络中的节点处于移动中，随着节点的移动，网络拓扑结构在不断变化，断链容易频繁发生，节点之间的连通性也会快速变化[7]。确保动态环境下两个节点之间高质量高效率的通信是移动Ad Hoc网络应用中的一个挑战，其中路由协议的设计目前仍然是Ad Hoc网络研究的热点和难点[8]。

1 相关研究

针对移动Ad Hoc网络的路由协议已经有了很多研究。在众多的路由协议中，无线自组网按需平面距离向量路由协议 (Ad hoc On-Demand Distance Vector Routing, AODV)是一种典型的反应式路由协议，是移动Ad Hoc网络中按需生成路由的典型协议，节点不需要维护及时准确的路由信息，当需要发送数据时才发起路由查找过程，更能适应Ad Hoc网络的特点[9]。但由于它仅以最小跳数作为路由选择的依据，容易导致网络资源分配不均，链路经常中断，节点通信过程中数据丢包严重[10]。

近几年，国内外许多研究者针对标准AODV协议在移动Ad Hoc网络中的应用[11]做了大量的研究与改进。文献[12]在MANET的应用场景中提出了一种M-AODV协议，在路由不能维持当前通信时，该协议从源节点开始路由重建的操作，在特定条件下，能获得比原始AODV路由协议更好的性能；文献[13]提出了一种基于AODV的能量感知路由协议，该协议将转发决策与中间节点的节点能量阈值相结合，并基于最小能量算法进行路由，以增加网络的生命周期，但该路由协议未充分考虑网络的动态性；文献[14]提出了基于网格的多路径路由方案，找出所有可能的路径，再利用海豚回声定位算法(Dolphin Echolocation Algorithm，DEA)找到最佳路径；文献[15]提出的基于模糊神经网络的稳定AODV协议改进方案，综合考虑节点稳定度、链路稳定性与跳数，选择稳定且跳数较小的路径。以上对AODV协议的研究与改进，在一定程度上改善了Ad Hoc网络的性能。但这些对路由协议的研究中，一部分协议会较早地建立起备用路由，无法保证启用备用路由时的路由质量，还有一部分在当前通信路由中断之后再启动路由的重建机制，在路由中断到路由重建完成的这段时间里，源节点和目的节点之间无法进行数据包的传输，极大地降低了网络的吞吐量，增加了数据包传输的延时。

路由的断开和路由的重建是影响Ad Hoc网络性能的关键因素[16]，本文提出一种基于回报加权的预测路由协议(Calculation-AODV, CAODV)。以标准AODV协议为基础，利用hello消息机制，周期性地计算自身的稳定值，预测通信路由的可靠性。在路由发现的过程中，避免使用不可靠的节点，在路由维护过程中，发现不可靠节点，及时启动路由的重建机制，提高通信的效率。

2 预测路由模型

2.1 信号功率强度

用集合V={v1,v2,…,vN}表示Ad Hoc网络某个地理区域中的N个无线节点。两个处在彼此通信范围内的节点vi、vj，vi，vj∈V，vj节点为vi的邻居节点，当网络中的节点移动时，节点之间的距离会变化。对于网络中的每一个节点，利用无线信号传输模型来计算信号功率强度值。假设节点之间的距离为d，接收信号功率值pij可以表述为：

(1)

式中：pi,j为节点vi接收邻居节点vj的信号功率；pj为邻居节点vj的发射功率；Gj为发射天线增益；Gi为接收天线增益；λ为波长，单位为m；d为节点vi与邻居节点vj之间的距离，单位为m；L为与传播无关的损耗(传输线衰减、滤波损耗、天线损耗)。功率与增益的单位都为W。

2.2 路由可靠性维护

Ad Hoc网络中的节点具有自主性和移动性，有路由器的功能，因此，Ad Hoc网络中的每个节点都能发现和维护到其他节点的路由。针对Ad Hoc网络节点位置不固定，通信链路容易断开的特点，在传统的AODV路由协议的基础上，综合物理层、MAC层和网络层，提出一种预测路由机制。周期性评估节点的稳定性，判断通信链路的传输性能，为通信节点是否需要更新路由提供依据。

建立如图1所示的基于回报加权的路由预测模型。节点之间的相对运动可以分为相向运动和背向运动，根据节点的相对运动定义节点的相对稳定性。Ad Hoc网络中的节点，通过hello消息周期性地进行信息的交互，假设通信中的节点根据hello消息感知下一跳节点的距离变化和信号强度变化，根据定义的节点相对稳定性，通信节点获取下一跳节点的稳定值，预测当前路由的可靠性，判断路由重建的时机。Ad Hoc网络中的无线通信节点根据预测的结果决定是否更新路由。

图1 预测路由模型

2.3 路由重建时机的判定

Ad Hoc网络中节点的移动性会引起网络拓扑结构的动态变化。标准的AODV协议只维持一条源节点到目的节点之间的路由，若在通信路由发生中断后节点再启动路由的重建，此时通信已经中断，新路由的建立需要一定时间，会降低系统的吞吐量，也会降低数据传输的及时性。但是，若在不必要的时候引入备用路由，会增加系统的开销，增加网络复杂度，降低系统的效率，且Ad Hoc网络的拓扑结构不固定，随着节点的移动，在通信路由中断而启用备用路由时，备用路由的可用性变得不可知。选择合适的时机建立新的路由显得尤为重要。综合考虑上述问题，改进了标准AODV协议，提出了一种根据节点的相对运动方式定义节点稳定性的方法，给出判断启动路由重建的信号感知判据，在预测到通信路由不稳定时，发出路由重建的信号，以避免增大通信时延和增加系统开销。图2为t时刻节点vi周围的网络拓扑结构，其中：虚线的圆形区域为节点vi的最大传输范围，传输半径为R，在此范围之内的圆点表示节点vi的邻居节点；实线的圆形区域为节点vi的可靠传输范围，在此区域之内的圆点表示节点vi相对可靠的邻居节点，可靠传输半径为r。

图2 节点相对稳定性示意图

经过时间T，节点vi的邻居节点vj的可能运动方向有四种。当节点vj运动到节点vi的可靠传输范围以外，并且经过时间周期T接收到的信号功率强度与t时间接收到的数据包功率强度相比已经减小时，可以预测网络[17]中两个节点正超出彼此的无线信号范围，链路断开的可能性增大。

四种运动形式如图3所示，在图3(a)中，节点vj相对于节点vi最不稳定，如果节点vi与节点vj之间当前正在传输数据，则通信中断的可能性较大。

图3 节点相对运动示意图

(2)

根据式(1)，式(2)可变换如下：

(3)

式中：d表示节点vj与节点vi之间的距离；dt代表t时刻vj与vi之间的距离；dt+T代表t+T时刻vj与vi之间的距离；r代表可靠传输半径；任何时刻节点之间相对稳定性均有str(i,j)∈[0, 1]。

当节点vj运动到节点vi的可靠传输半径r之外，即d≥1且str(i,j)<1时，则可以认为邻居节点vj的信号强度正逐渐减弱，稳定性不能满足需求，在这种情况下，若节点vi正在通信的路由节点集合B={v1,v2,…,vK}包含邻居节点vj，则认为路由B已经不可靠，随时可能中断通信。

当路由建立成功之后，节点会利用有效的路由进行通信。同时，节点与邻居节点之间会利用hello消息周期性计算str值。在检测到通信节点不稳定时，重新启动路由发现过程。

如图4所示，节点v21和v22都属于通信链路中的节点，且v22是v21的邻居节点。在邻居节点信息交换的过程中，如果v21发现与邻居节点v22的传输距离大于可靠传输半径且稳定值小于1，此时，可以认为路由vs-v21-v22-vd已不可靠，需要立即启动路由重建机制，在新路由建立成功后，立即将通信链路切换到新路由。

图4 Ad Hoc网络的路由重建

3 基于回报加权的预测路由机制

3.1 回报权重值函数

3.1.1潜能值Rs

在Ad Hoc网络中，数据的传输是节点能量消耗主要原因。潜能函数R主要考虑传输的能耗，定义接收(发送)单位数据所需能量为en，解码(编码)单位数据所需能耗为em，则接收转发lbit数据包消耗的能量为：

E=2l(en+em)

(4)

在Ad Hoc网络中，若节点vs选择路由C中的节点作为新的路由，则潜能值可计算如下：

(5)

式中：Ei为Ad Hoc网络中，路由C中的节点vi的剩余能量；ξC表示路由C包含的节点集合。

3.1.2节点可信度

对于新路径选择的可信度评估值为传输距离。如图5所示，假设节点之间的相对距离与网络中的实际距离成正比且节点的响应时间相同，可以很明显看出，路径s1：vs-v31-v32-vd比路径s2：vs-v41-v42-v43-vd短，如果vs同时通过路径s1、s2向节点vd发送信息，由于s1的传输距离短，则经由s1路径的信息很可能比s2先达到目的节点vd，即s1比s2可信度更高。

图5 可选路由的可信度模型

用Fs,d,C表示节点vs与节点vd之间活跃路径集合C中的节点距离之和，则节点vs的路径C的可信度Fs,d,C计算如下(考虑响应时间)：

(6)

考虑到一些关键任务的重要度，引入权重因子α来表示每一种资源的重要度。节点vs与节点vd的路由C的回报值JC计算如下：

(7)

由于Ad Hoc网络中的节点的位置和状态处于动态变化中，对于给定的可靠传输半径r，当节点vj超出节点vi的可靠传输距离且稳定值str<1时，则启动节点vs到vd之间路由的重建机制，根据回报权重值挑选出最佳路径，立即更新路由。因此，在预测到通信路由中有即将失效或者传输性能不能满足需求的节点时，都要对其他活跃路径集合的状态进行实时的评估，在通信中断之前放弃旧路由，启用新路由。

3.2 路由协议的改进

在标准AODV路由协议基础上进行改进，过程如下：

(1) 节点的邻居信息表增加两个字段：与邻居节点的当前通信距离，邻居节点稳定值。字段里的数值将根据hello消息的发送周期性地更新。路由应答(RouteReply, RREP)包增加两个字段，即节点剩余能量值和当前节点与下一跳节点之间的距离，用于源节点选择回报值最大的路径发送数据。增加一个WARNING警告信息，信息中包含节点的IP地址，当节点不稳定时，会发送WARNING信息给源节点，启动路由重建。

(2)在路由发现过程中，对于超出节点可靠传输距离且稳定值小于1的节点，可以认为是不稳定的节点。

路由发现开始时，源节点会发送RREP包，发起到目的节点的路由发现过程，中间节点接收到RREP包后，会通过当前通信距离与稳定值判断与上一跳节点之间的稳定性，如果中间节点认为自身相对于上一跳节点不稳定，则将RREP包直接丢弃，如果中间节点认为自身稳定性较好，则进行相应的转发。与传统的AODV不同，节点会综合自身的回报加权值和接收到的RREP包中的参数，计算出新的值取代RREP包中原有的回报加权值，再将数据包转发出去，完成路由的回报值计算。

目的节点对于接收到的多条路径的RREP数据包，选取回报值较高的路由发出RREP数据包进行应答。

算法的部分伪代码如下：

set radiusThreshold=220;

while receive a packet

do

if transrange > radiusThreshold

then

if strengthvalue < 1

then

update. stabilitylist ( );

droppacket ( );

end

else

update. stabilitylist ( );

sendpacket ( );

end

(3) 在路由维护过程中，随着通信的进行，当正在通信路由中，有节点发现下一跳节点变得不稳定，会立即给源节点发送一个WARNING信息，源节点收到WARNING信息后，会启动路由重建，选择回报值最大的路径作为新路由，当新路由建立好之后，立即将通信切换到新路由。

算法的部分伪代码如下：

set radiusThreshold=220;

while receive a packet

do

if transrange > radiusThreshold

then

if strengthvalue < 1

then

send WARNING to source;

rebuild ( link.reward ( ) ) ；

end

else

as before;

end

在路由发现和路由维护的过程中，改进的协议沿用了AODV的hello消息机制，交换节点之间的信息用于判断邻居节点的稳定性以及WARNING消息发送的时机，相对于标准的AODV协议，并不会增加系统的时间复杂度和空间复杂度。

4 仿真及性能分析

为了能够全面分析基于回报加权的预测路由协议的性能，本文通过对标准的AODV协议进行改进，利用NS-2[18]搭建了一个平面网状结构的Ad Hoc网络，对提出的路由协议进行性能评估。Ad Hoc网络中的每一个节点既可以充当路由器，又可以充当终端节点。我们为每个节点添加了邻居节点状态表，该表用于节点记录邻居节点接收hello消息的功率值以及功率差。

在NS-2仿真平台下，对AODV协议、M-AODV协议和CAODV协议进行仿真实验。Pt、Gt、Gr、ht、ht、L采用仿真平台默认值，即Pt=0.281 838 15 W，传输范围为250 m，可靠传输半径为220 m，接收功率阈值为3.652e-10 W，Gt和Gr均为1，ht和ht为1.5 m，L=1。仿真区域为1 000 m×1 000 m，移动模型采用随机移动模型(Random Way Point, RWP)，节点采用全向天线(Omni Antenna),数据源采用恒定比特率(Constant Bit Rate, CBR)。移动仿真参数如表1所示。

表1 仿真参数设置

将AODV、M-AODV、CAODV的性能在由50个和100个节点组成的仿真网络拓扑环境中进行对比，对仿真结果进行比较和评价。

在20 s、30 s、40 s、50 s的仿真时间点，获取网络的数据传输比率。如图6所示，CAODV协议的数据传输比率比AODV协议增加了7%左右，比M-AODV协议增加了5%左右。如图7所示，CAODV协议的数据传输比率比AODV协议增加了9%左右，比M-AODV协议增加了5%左右。对比图6和图7，当仿真节点个数由50个增加到100个时，网络整体的数据传输比率都有一定程度下降，但在仿真节点个数相同的场景下，CAODV协议的数据传输比率优于其他两种协议，能有效降低断链发生的概率。

图6 50个节点仿真的数据传输比率

图7 100个节点仿真的数据传输比率

如图8所示，CAODV协议的网络吞吐量比AODV协议和M-AODV协议增加了9%左右。如图9所示，CAODV协议在20 s到30 s之间，出现吞吐量下降的情况，但随着仿真时间的推进，CAODV协议的网络吞吐量高于其他两种路由协议，CAODV协议的网络吞吐量比AODV协议和M-AODV协议增加了10%左右。

图8 50个节点仿真的网络吞吐量

图9 100个节点仿真的网络吞吐量

在100个节点的仿真场景中，每个节点的初始能量为10 J。如图10所示，从第15 s开始，部分节点会因为能量的消耗而变成无效节点。由于CAODV协议考虑了节点的能耗比和可信度，较好地均衡了网络负载，使用CAODV协议仿真时，节点的消亡速度较缓慢，能更好地延长网络的生存时间。

图10 网络存活节点数量

从图11中可以看出，CAODV协议的平均端到端延时整体优于其他两种协议，这是因为CAODV针对Ad Hoc网络的动态性，采用预测路由的方法。当感知到通信路由不稳定时，启动路由重建，实现新旧路由的实时切换，有效地降低了通信时延。

图11 平均端到端时延

5 结 语

设计一种预测路由模型，提出基于回报加权的预测路由协议CAODV。仿真结果表明，CAODV协议能降低断链发生的概率，有效地提升数据传输比率和网络吞吐量，提升网络通信质量,从而为Ad Hoc网络的实际应用提供有效的通信支撑。