一种基于判定区域的AODV路由的自适应修复算法

刘 思 张德干 刘晓欢 张 婷 吴 昊

(计算机视觉与系统省部共建教育部重点实验室(天津理工大学) 天津 300384) (天津市智能计算及软件新技术重点实验室(天津理工大学) 天津 300384)406690108@qq.com)

移动自组织网络(mobile ad hoc networks， MANET)是不依赖基础设施，自组织、可重构的多跳无线网络[1-3].在抢险救灾环境中，散布的节点之间的通信依靠MANET实现.在MANET网络中，节点的移动性以及通信半径的限制，使得数据的传输相比传统网络更加复杂[4-5].适用实际环境的高效路由技术的研究尤其重要.目前针对MANET的路由协议已取得一些成果，本文主要研究针对抢险救灾环境，使用路由协议的自适应修复技术.

在实施抢险救灾时，为了迅速实施救灾，自组建立MANET.这是一种节点被统一调配的网络，即节点接受统一调配的高速移动的MANET网络.针对自组织网络特点和路由需求，国内外相关研究人员和机构以避免路由环路、控制路由开销、动态适应网络为目的，设计开发了不同方式的路由协议[6-8].按照路由建立方式的不同，网络路由协议可分为先应式路由协议、按需路路协议和混合型路由协议[9-12].无线自组网按需平面距离向量(ad hoc on-demand distance vector， AODV)路由协议作为典型的按需路由协议之一，可以自适应在移动自组织网络中完成数据传输[13-16].路由建立的过程为：源节点首先通过组播方式广播路由请求(routing request， RREQ)信息.网络中的其他节点(不是目的节点)接收到RREQ后，在该节点缓存的路由记录里搜寻包含可以传送到目标节点的路由.如果包含，则该节点单向广播路由应答(routing response， RREP)信息；不包含，则继续广播RREQ信息[17-20].

根据AODV的性质可知，当路由发生故障时，AODV路由自身会进行路由维护，如果在维护时间内路由没有完成修复，故障节点则向源节点发送错误信息，源节点接收到错误信息以后，会再次发起路由建立的过程[21-24].关于AODV路由协议的防洪控制改进算法有一些进步，但是针对环境的自适应修复很少，所以基于防洪控制的自适应修复算法研究很有必要[25-27].

为了解决AODV路由在路径失效后才进行路由修复引起的网络延迟、扩大开销、影响网络生命周期等问题，提出了基于判定区域的AODV路由协议的自适应修复算法(an adaptive repair algorithm for AODV routing based on decision region， AR-AODV)，目的是使改善后的路由更适应抢险救灾的MANET网络.本文首先根据网络中节点做统一性移动的特性，建立最优搜寻公式，并求出该公式的最优解；提出自修复过程发起的条件阈值；最后给出确定寻优区域的算法.仿真结果表明，该算法改善了平均端到端时延，减少了控制开销，并提高了数据包分组交付率.

1 相关研究

已有的相关研究中，文献[28]提出了一种具有速度感知的AODV路由改进算法SA-AODV.SA-AODV在路由发现阶段，根据节点的位置和通信半径以及节点间的相对移动速度选出一部分在通信范围内且与数据发送节点相对移动速度较小的路由节点，然后通过节点间的相对移动速度评估出每条可到达目的节点的路由线路的有效生存时间，根据有效生存时间的长短选择最佳路由方案.实验表明，SA-AODV路由算法更适合运用在高速移动的节点网络中.文献[29]提出了一种基于网络拓扑变化，结合源路由的按需距离矢量路由算法DS-AODV.DS-AODV协议根据网络拓扑复杂性，采用高效的路由发现维护策略，使节点合理的使用网络带宽资源；根据对相邻节点移动预测链路持续时间结合节点最大速度分析网络拓扑稳定性，并通过不同稳定程度在路由发现过程加入源路由机制和路由维护周期更新机制，从而选择稳定性高的路由.结果表明，在拓扑变化不同的各种环境下提出的方法的平均分组投递率高，且综合端到端时延小.

为了更适应抢险救灾的MANET网络，解决AODV路由在路径失效后才进行路由修复引起的网络整体效率的问题，提出了基于判定区域的AODV路由协议的自适应修复算法(AR-AODV).通过实验仿真以及实际场景测试，证明该算法有效改善了路由的效率.

2 自修复算法原理

2.1 寻优算法原理

定义1.自修复节点.在AODV路由中任意一条数据传输路径，如果在某一时间，链路发生故障，导致路径失效，则该故障链路的上一跳节点称为自修复节点.

定义2.最优节点.把自修复节点为了修复失效路由而搜索出的下一跳节点，称为最优节点.

定义3.联合概率密度.设最优节点分布在网络拓扑中的位置为M(xt,yt)，自修复节点的分布位置设为G(xt,yt)，则自修复节点寻找最优节点的过程(寻优过程)与最优节点的分布位置的联合概率密度设为pf(m,G)：

pf(m,G)dm=P[m≤M≤m+dm|SG(φ)],

(1)

其中，0≤φ≤t，SG(φ)表示自修复节点朝G(φ)这个方向没有搜寻到最优节点.

搜寻最优节点的概率h：

(2)

其中，region表示最优节点在网络中分布的范围.

自修复节点搜寻最优节点的寻优过程的公式为

(3)

设T为自修复节点搜寻到最优节点的时间，则搜寻成功的所需要的平均时间为

(4)

假设在不同时间点对最优节点进行搜寻的过程是相互独立的，则自修复节点在t1时的联合概率分布为：

pf(mt+Δt,U)=pf(mt,U)(1-h(mt,U)Δt),

(5)

t1=t+Δt，h(mt,U)表示自修复节点沿着路径U搜寻最优节点的概率函数.

得到统一性调配的寻优公式：

(6)

其中，N为网络的最大节点数.

引理1.网络拓扑中节点接受统一调配，此场景下自修复节点可以通过Ray-Algorithm搜寻出最优节点[30].

证明. 由节点接受统一调配，此场景下建立的寻优等式(6)得出：

(7)

(8)

且mj(0)=m0.

得出：

dpfdv=-pf[Ω+h(mt,t(φ),U(φ))],

(9)

pf(0)=pf0(m0).

利用Ray-Algorithm求式(9)的解，表示为

(10)

至此，采用Ray-Algorithm可计算出最优节点的寻优寻公式的解，即自修复节点可以通过Ray-Algorithm搜寻出最优节点得证.

证毕.

定理1.节点受统一性调配的MANET，对AODV路由的任意自修复节点采用Ray-Algorithm搜寻最优节点其搜寻结果是最优解.

证明. 1)根据引理1可知AODV路由的任意自修复节点采用Ray-Algorithm可以搜寻出最优节点.

2) 设在t时，最优节点在搜索范围空间内的位置为m(x,y)，自修复节点为m(x0,y0)，使在t时以m(x0,y0)为起点的射线通过m(x,y).如果pf0(m(x0，y0))=0，有pf(mt(x,y),U)=0，算法结束；否则，根据等式(10)计算方程pf(mt(x,y),U)=0[30].所以，采用Ray-Algorithm搜寻的结果是最优解.

至此，节点受统一性调配的MANET，AODV路由的任意自修复节点采用Ray-Algorithm搜寻到的最优节点为最优解得证.

证毕.

定义4.寻优区域.根据定理1，将自修复节点搜寻最优节点区域设为以自修复节点为顶点、自修复节点与目的节点的连线为中轴线的扇形区域，称为寻优区域.

设定的寻优区域可以在减少控制开销的同时增大自修复过程的成功率.而寻优区域的半顶角ψ的取值由MANET网络中节点运动状态、移动速度和能量大小等决定.当ψ0=0时，寻优区域为经过目的节点的射线，搜寻到的节点则为通过Ray-Algorithm求得的最优解；当ψ0=2π时，寻优区域变成整个圆区域，寻优过程转换为AODV路由自带修复过程.所以，顶角增大，寻优区域就变大，而控制开销则增多.

2.2 发起自修复的条件算法

AODV路由发生失效时，以全网泛洪的方式广播路由信息[31]，增加了网络的控制开销，本文将通过限定区域来研究如何以更小的开销，建立发起自修复与网络环境的映射关系.

当节点A的传输路径li=1，路由中任意节点A的最大传输距离为R，稳定传输距离为r.当节点A的邻居节点位于稳定区域内时，传输路径强健；而当邻居节点移动到最大距离区域时，传输路径开始变得不稳定.因此节点从传输稳定距离移出进入最大距离时，应为最佳发起自修复时刻，所以稳定传输距离的边界设定为路由发起修复的条件.当节点B到达稳定传输距离边界时，节点B向节点A广播路由修复判定分组(route repair decision report， RRDR)，节点A接收到RRDR后，发起路由自修复.

为了减少控制开销，本文以节点的接收功率来判断节点移动变化，进而确定是否发起路由修复.也就是说，把稳定传输的距离的边界接收功率设为条件阈值，建立距离与路由修复的映射关系，在路由情况变差前提前发起修复.如图1所示：

Fig. 1 Initiating self-repairing mapping relationships图1 发起自修复的映射关系

计算节点的接收功率Sr：

Sr=Srdn,

(11)

其中，d表示发送数据节点与接收数据节点间的距离,Ss表示节点的发送功率.n是可调参数，本文设n=3.

因为稳定传输距离的边界接收功率为条件阈值，则发起路由修复的条件阈值为

Sth=Ssern,

(12)

其中，r=R-τ.

节点的接收功率的平均值为：

(13)

当Sr-av

算法1.发起路由修复的条件算法.

Ptmp=Pmatrix(hopE,:);*条件算法*

Precv=mean(Ptmp(find(Ptmp<100)));

ifPrecv

Trepair=Trepair+1;

CounterRRDR=1;*跳数计数器*

end if

ifflag1=1

ifdistance(hopE)>(distance(hopS)+transmat(hopS,hopE))

distance(hopE)=(distance(hopS)+transmat(hopS,hopE));

queue=[queue,hopE];

end if

end if

Fig. 2 The angle of nodes located in the network图2 节点所处网络的角度

2.3 寻优区域的判定算法

通过确定寻优区域，必先确定最优节点所在位置.为了计算方便，减少不必要的控制开销，本文以最优节点的角度来代替其所处拓扑的位置.而节点的角度以节点接受数据的角度代替.AODV数据传输的是从上一跳节点向邻居节点传输.以i代表节点Ai的跳数值.设节点Ai在网络中的角度为αi，表示从跳数为i+1的节点接收数据的角度.跳数为i的节点直接向目的节点传输数据的角度为δi.如图2所示：

(14)

其中，αj∈(-π,+π].如图2所示，处于x轴上方的传输方向为正向.

节点的寻优区域的判定算法处理步骤，描述如下：

1) AODV中某条路由中节点C的传输路径lC=1，某一时刻，计算得出节点C的平均接收功率小于阈值，判定传输路径不稳定，节点C向上一跳节点B发送RRDR.RRDR包含IDMAC,Sr,tr三个信息，其中Sr代表节点的接收功率，tr代表节点的接收时间.当网络中的节点收到一个RRDR，就在判定报告RRDR中更新IDMAC,Sr,tr信息.

2) 节点B接收到RRDR，发起路由自修复过程，广播路由修复请求(query repair， QRYR)，QRYR记录角度δB信息，并加入一个预设的半顶角ψ0.

3) 节点A收到QRYR，计算节点A、节点B与目的节点D的夹角∠ABD=ψ，由已知的节点A和节点E的角度αA和αE，可以计算得出ψ=|αA+αE+δB|，其中|αA|=-αA，|αE|=+αE，|δB|=-δB.如图3所示:

Fig. 3 Calculating for all angles图3 各个角度计算

4) 当ψ≤ψ0时，节点A位于寻优区域内.利用式(14)计算得到节点的δA，并记录到QRYR中.如果当ψ>ψ0时，节点A不在寻优区域内，该节点删除QRYR报告.

算法2.角度计算.

theta0=arctan((Y(hopE)-Y(hopS))

(X(hopE)-X(hopS)));*角度的计算*

ifflag2==1

theta0=arctan((Y(hopE)-Y(hopS))

(X(hopE)-X(hopS)));

dist2=dismatrix(hopE,:);

[V,I]=sort(dist2);

end if

2.4 AR-AODV算法描述

本节提出基于判定区域的AODV路由协议的自适应修复算法.首先对自修复节点搜寻最优节点建立寻优公式，根据Ray-Algorithm确定搜寻结果，并证明该搜寻结果即为搜寻最优节点过程的最优解；然后给出判定自修复的条件算法，确定自修复过程发起的条件阈值.为了减少控制开销，给出寻优区域定义并提出确定寻优区域的算法.具体实现步骤如图4所示:

Fig. 4 Searching for optimal nodes by self-repairing nodes图4 自修复节点搜寻最优节点

具体描述如下：

1) AODV中路由的任意节点，据式(12)计算节点的条件阈值Sth.当节点B根据式(11)得出节点的接收功率的平均值Sr-av，此时，Sr-av

2) 当节点A收到记录CounterRRDR的RRDR报告后，将在ψ0=π3寻优区域内广播记录节点A的与目的节点角度的QRYR修复数据包，调用算法2.根据式(6)(9)建立寻优公式搜寻，此处调用算法3，据式(10)在寻优区域内搜索最优节点.

3) 节点F收到QRYR数据包，计算夹角∠FAD，即ψ，当ψ≤ψ0时，则接收到QRYR报告的节点F位于寻优区域中.该节点根据式(14)计算得到δF，并将结果写入QRYR中重新广播发送.当ψ>ψ0时，节点F处于修复区域之外，该节点将丢弃接收到的节点A的QRYR报告.此处调用算法4.直到目的节点收到QRYR并发送新的QRYR，完成路由更新，则确定路由自适应修复完成.图4给出了AODV协议中任意一个节点自修复的过程.

4) AODV中自修复节点与目的节点间的跳数之差距不能大于修复长度阈值MaxRepair_l，否则自修复节点不能发起修复.QRYR的修复长度Tli设为

max(MinRepair_l,0.5×ith)+LocalAdd_l,

其中ith表示超出传输范围的节点的高度值，MinRepair_l+LocalAdd_l≤1.

5) 在修复定时器Tre时间内，自修复节点收到目的节点的QRYR报告，则AODV自适应修复完成.如果Tre超时，AODV的自修复节点将广播删除报告，删除失效路由.

算法3.寻优搜索最优节点.

ifflag3==1*Ray-Algorithm的伪代码*

Ker=3

forjj=1:Ker

theta(jj)=arctan((Y(I(jj))-

Y(hopS))(X(I(jj))-X(hopS)));

end for

end if

thetatotal=sum(theta);

ifthetatotal>theta0

iftransmat(hopS,hopE)≤MaxRepair_l

queue=[queue,hopE];

parent(hopE)=hopS;

end if

算法4.QRYR数据包处理算法.

ifPrecv

counter=0;

whileflag==1

counter=counter+1;

dist2=dismatrix(hopE,:);

[V,I]=sort(dist2);

Ker=3;

end while

ifKer+counter≥length(I)

flag=0;

forjj=counter:Ker+counter

theta(jj)=arctan((Y(I(jj))-

Y(hopS))(X(I(jj))-

X(hopS)));

thetatotal=sum(theta);

end for

end if

end if

ifthetatotal>theta0*位于修复区域之外*

queue=[];

flag4=1;

ifflag4==1

hNC=lenfth(queue);

sets=max(MinRepair_l,0.5×ith+

LocalAdd_l);

ifsets>MinRepair_l+LocalAdd_l

queue=[queue,hopE];

parent(hopE)=hopS;

end if

end if

end if

iftransmat(hopS,hopE)≤MaxRepair_l

queue=[queue,hopE];

parent(hopE)=hopS;

end if

3 议仿真与分析

3.1 仿真环境设置

本实验借助MATLAB平台，对本文提出的AR-AODV自适应修复算法进行仿真分析.将本文协议和经典的AODV协议及已提出的SA-AODV协议[28]和DS-AODV协议[29]进行对比.分别在不同的节点数据包发送速率、不同的节点移动速度、不同的网络节点数目以及链路失效率，对节点之间平均端到端的时延、数据包分组交付率、路由拓扑控制开销进行仿真分析.本节仍采用Random Way-point移动模型[30]仿真统一性调配运动.仿真参数如表1所示:

Table 1 Simulation Parameters表1 仿真参数

Continued (Table 1)

仿真实验主要测量指标有3个：

1) 平均端到端时延.从节点产生数据流或者接收到数据后开始，到该数据成功被下一跳节点接收的平均延时时间.

2) 数据包递交率.每个节点除了发送路由维护信息包之外，还需要发送自己的消息信息数据包，根据源节点发送的数据包数量和目的节点接收到的数据包数量，计算出数据包成功递交率.

3) 拓扑控制开销.由于AODV为按需路由协议，路由请求普遍采用泛洪广播形式.且路由一旦建立，除非出现路由不再使用或路由异常中断这2种情况，否则节点都会维护该路由.所以，对这些维护路由拓扑信息的数据包开销进行分析.

实验仿真的网络拓扑如图5所示：

Fig. 5 Network topology diagram of experimental simulation图5 实验仿真的网络拓扑图

3.2 仿真结果分析

图6～8为在节点速度不变、不同数据包发送速率的情况下各种路由算法的网络性能变化.

Fig. 6 Average end-to-end delay diagrams with different packet delivery rates图6 不同的数据包发送率下平均端到端的时延

Fig. 7 Packet delivery rate with different packet delivery rates图7 不同的数据包发送率下数据包分组交付率

Fig. 8 Routing topology control overhead with different packet transmission rates图8 不同的数据包发送率下路由拓扑控制开销变化

如图6～8所示，随着数据包发送率的提高，网络的平均端到端时延、网络的路由控制拓扑开销都是增长趋势，而数据包交付率则呈整体下降趋势.因为随着数据包发送率的提高，网络中数据增多，导致整个网络拥挤，发送数据需要排队，更加重网络的负载，导致网络延时增大.但是本文提出的AR-AODV算法，相比传统AODV时延减少30%左右，比DS-AODV减少时延21%大小，比SA-AODV减少10%左右.实验仿真表明，提出的算法整体时延减少效果显著.网络负载增大、网络控制请求大量增多导致网络路由控制开销增大.实验仿真结果显示，本文提出的AR-AODV路由算法，比传统AODV控制开销降低35%左右，与DS-AODV，SA-AODV相比，控制开销分别降低28%和19%左右.控制开销改进明显.链路失效、网络拥堵，导致的数据包传输需要排队，导致交付率明显降低，但是本文提出的算法交付率提高明显.比传统AODV数据包交付率提高31%左右，与DS-AODV，SA-AODV相比，数据包交付率分别提高15%和9%左右.

图9～11在不同的节点速度下对网络应用不同的改进路由所产生的网络平均端到端时延、网络的路由控制拓扑开销和数据包交付率进行仿真分析.

Fig. 9 Average end-to-end delay variation with different node speeds图9 不同节点速度下平均端到端时延变化

Fig. 10 Packet delivery rate with different node speeds图10 不同节点速度下数据包分组交付率变化

Fig. 11 Routing topology control overhead with different node speeds图11 不同节点速度下路由拓扑控制开销变化

图9表明随着节点速度增大，4种改进路由的网络的平均端到端时延都是增加趋势.图10表明随着节点速度增大，4种改进路由的数据包分组交付率是减少的.图11表明随着节点速度增大，4种改进路由的路由拓扑控制开销也是增大的.网络的节点速度增大，导致整个网络的移动性加大，链路失效率大大增加，从而导致数据传输受阻，传输数据进行排队等待，网络拥堵网络时延增大明显.而修复路由导致路由控制开销增长、整个网络数据交付率下降.但是本文提出的AR-AODV算法，在减少时延方面，比传统AODV时延减少30%左右，比DS-AODV减少时延20%大小，比SA-AODV减少15%左右.比传统AODV数据包交付率提高28%左右，与DS-AODV，SA-AODV相比，数据包交付率分别提高25%和20%左右；比传统AODV控制开销降低50%左右，与DS-AODV，SA-AODV相比，控制开销分别降低33%和25%左右.控制开销改进效果明显.

图12～14通过不断增大网络密度即增加网络节点数目，来分析网络应用不同的改进路由所产生的网络的平均端到端时延、网络的路由控制拓扑开销和数据包交付率的变化规律.

Fig. 12 Average end-to-end delay with different number of nodes图12 不同节点数目下平均端到端时延变化

Fig. 13 Packet delivery rate with different number of nodes图13 不同节点数目下数据包分组交付率变化

Fig. 14 Routing topology control overhead with different number of nodes图14 不同节点数目下路由拓扑控制开销变化

图12表明随着网络密度的增大，网络的平均端到端时延增大.图13表明随着节点数目增多，数据包分组交付率也随之降低.图14所示随着节点数目增多，路由拓扑控制开销也增大.网络中节点数目增多，路由失效率降低，路由修复导致的时延、开销也增大，而数据包交付率降低速度也减慢.本文提出的改进算法随着节点数目增多效果越明显.提出的AR-AODV算法，在减少时延方面，比传统AODV时延减少45%左右，比DS-AODV减少时延40%大小，比SA-AODV减少35%左右.比传统AODV数据包交付率提高70%左右，与DS-AODV，SA-AODV相比，数据包交付率分别提高30%和25%左右；比传统AODV控制开销降低60%左右，与DS-AODV，SA-AODV相比，控制开销分别降低30%和25%左右.整体控制开销改进效果明显.

Fig. 15 Average end-to-end delay with different link failure rates图15 不同链路失效率下平均端到端时延变化

如图15所示，在不同的链路失效率，对网络应用不同的改进路由所产生的网络的平均端到端时延的变化进行仿真分析.结果表明随着链路失效率的增大，4种改进路由的网络的平均端到端时延都是增加趋势.网络的链路失效率增大，数据传输受阻，网络拥堵网络时延增大明显.但是本文提出的AR-AODV路由修复算法，在减少时延方面，比传统AODV时延减少39%左右，比DS-AODV减少时延37%大小，比SA-AODV减少34%左右.在改进路由修复方面效果明显.

3.3 实际场景测试

本文研究基于实际抢险救灾等服从统一调配的应用背景下，即网络节点做确定性移动的环境.为了验证本改进算法的实际效果，我们在实际救险环境中，在1 000 m×1 000 m的范围内实际随机布置50个车载等移动网络节点，统一调配.实验参数布置如表2所示:

Table 2 Test Parameters表2 测试参数

Fig. 16 The topology of MANET network图16 MANET网络拓扑结构

MANET在被灾害所导致无线基站被毁、通信线路瘫痪、道路交通受限的极端环境中仍能够实现稳定高效的通信，满足抢险救援过程中的通信指挥功能需求.MANET网络拓扑结构如图16所示:

Fig. 17 Network performance with different number of nodes图17 不同节点数目下网络性能变化

如图17～1显示，提出的AR-AODV改进算法在实际环境的结果略低于仿真效果，但是与仿真结果基本一致，且与SA-AODV协议[28]和DS-AODV协议[29]相比，无论在控制开销、数据包交付率，还是端到端时延都有明显的改善.说明所提出的算法在实际抢险环境中能够取得期待效果，能够降低控制开销同时减少网络时延.AR-AODV算法基本实现改进效果.

Fig. 18 Network performance with different link failure rates图18 不同链路失效率下网络性能变化

4 结 论

本文主要研究了针对抢险环境构建的MANET网络在应用AODV进行数据传输时，网络环境变化导致路径失效后的修复问题.目的是使改进后的AODV更适应抢险救灾网络的数据传输.首先将AODV路由的修复问题转换成自修复节点对最优节点的寻优问题,建立统一性调配网络的寻优公式，求出公式解，并证明该解为最优解;然后将发起路由自修与节点距离建立映射关系，提出节点进行自修复的条件算法，计算出条件阈值，根据节点距离变化自适应地发起路由修复;最后提出自修复节点的寻优区域确定算法，既提高了路由的自修复的成功率，又减少了控制开销.仿真结果表明，提出的AR-AODV自适应算法在改善网络控制开销方面效果明显，在提高数据包分组交付率方面也获得明显的效果，明显改善了节点之间平均端到端的时延.为了进一步分析所提算法的实际应用效果，以车载等移动设备为网络节点，并服从统一调配，在实际抢险救灾环境中进行测试.结果显示，提出的AR-AODV算法在实际场景中大大减低了控制开销，提高了数据包交付率，且改善了端到端时延，整体性能改善明显.