基于链路时间预测的移动Ad Hoc网路由

胡 君,叶俊杰

(1.湖南科技职业学院软件学院,长沙 410004;2.湖南科技大学商学院,湖南 湘潭 411100)

移动Ad Hoc网络MANETs(Mobile Ad Hoc Networks)是由移动节点组成的无中心无线网络[1]。MANETs未采用任何固定的基础设施,属于自治系统、能够自行组网,已应用于抗险救灾、科学考察等领域。MANETs内的节点既可充当主机,又具有路由功能。

然而,节点的自由移动导致网络拓扑呈动态变化。这就使得节点间的通信链路不稳定。为此,研究人员对MANETs路由协议进行了大量研究。现有的MANETs路由可分两大类:①反应式按需路由;②先应式表驱路由。而按需距离矢量AODV(Ad Hoc On-demand Distance Vector)[2]就典型的反应式按需路由。

然而,若链路断裂或发现更短的路径时可能会发生路由重建,而依照AODV的路由策略,重建路由的成本过高[3]。此外,一旦链路已断裂,再去重建路由往往会导致数据包的丢失。而链路的连通时间直接反映了链路能否连通或断裂。因此,可通过预测链路的连通时间,提前判断链路是否能完成数据包的传输,进而提高数据包传输成功率。

据此,研究人员针对链路预测问题,进行了较深入研究。例如,文献[4]通过计算节点移动速度差对AODV进行改进。先用速度差最小的链路构建路由,进而提高路由的稳定性。文献[5]针对链路断裂问题,采用链路时间预测及路由重建方案,并引用链路备份机制。文献[5]提出基于冗余机制的AODV路由RAODV(Reduntant AODV)。RAODV路由引用多路径路由。文献[6]引用牛顿均差插值多项式预测链路的链路的连通时间,并预测节点的剩余时间。

尽管这些方案考虑了链路连通时间,并从预测链路连通时间角度,缓解链路断裂问题。但是,在构建路由时,只考虑链路连通时间是远远不够。路由的稳定性受多个因素影响。

为此,针对MANETs的路由,提出基于节点运动信息的链路稳定路由LDPR。LDPR路由利用节点的运动信息估计链路的生存时间,并考虑双路由机制。再通过链路生存时间构建路由,选择路由生存时间长的路由传输数据,进而提高路由的稳定性。

1 LDPR路由

LDPR路由先依据节点运动信息估计链路连通时间。然后,再估计链路长度。

1.1 链路连通时间

LDPR路由利用节点间的相对速度矢量估计这两个节点所连通的链路时间[7-8]。

以节点i和节点j为例,分析估计它们间链路的连通时间。令节点i和节点j在时刻t1的速度矢量ϑi和ϑj。它们的相对矢量矢量可表示为:

Δϑ=ϑj-ϑi

(1)

为了简化分析,将节点i视为固定不动,节点j以相对速度矢量Δϑ进行移动。在时刻t1,节点j在节点i的通信范围内[9-10]。当节点j运动了一段时间t,节点j可能会离开节点i的通信范围,移动至位置A,如图1所示。

图1 链路稳定性预测模型

令ћ表示节点j在时间t内所移动的距离。依据余弦定理,可建立方式(2):

R2=ћ2+d2-2ћdcos(π-θ)ћ=(ћ+dcosθ)2+(dsinθ)2

(2)

其中R表示节点的通信半径。d为在时刻t1节点i与节点j间的距离。而距离d可用式(3)进行计算:

(3)

其中(xi,yi)、(xj,yj)分别表示节点i与节点j在时刻t1的位置坐标。

对式(2)进行变换,可求解ћ,使其成为关于d、θ和R的函数。

(4)

接下来,结合图1计算角度β:

(5)

此外,用另一种形式表述相对速度矢量Δϑ:

Δϑ=|Δϑ|∠φ

(6)

其中|Δϑ|表示Δϑ的幅度,∠φ表示两个速度的角度值。

而三个角度φ、β和θ满足式(7):

θ=φ-β

(7)

最后,可利用ћ(d,θ)和|Δϑ|计算链路的生存时间T:

(8)

1.2 双路由机制

由于节点的移动性,单一路由往往难以成功地传输数据。而一旦路由断裂,又需重新启动路由机制[11],增加了网络开销和数据传输时延。为此,LDPR路由引用双路由机制。源节点同时维护两条路由,一条路由作为主路由,另一条路由作为备份路由。当主路由断裂,就启用备份路由传输数据。

LDPR路由先预测链路的生存时间,并在链路断开之前启动备份路由,减少了路由切换以及重新发现路由的时间。

如图2所示,假定节点S需要向节点D传输数据Data。首先,节点S向邻居广播路由请求控制包RREQ。当节点D接收了RREQ包后,节点D就依着传输RREQ路径返回RREP包。

图2 双路由的网络拓扑

从图2可知,节点S至节点D有两条路径:S→1→2→3→D和S→1→4→5→6→D。将S→1→2→3→D作为主路由,而S→1→4→5→6→D作为备份路由。一旦主路由断开,就直接启用备份路由,而无需又重新发现路由,缩短了传输时延。

在使用主路由传输数据时,监测每条链路的生存时间。一旦预测链路即将断裂,就启用备份路由。如图2所示,假定预测链路1→4断裂,就在断裂的同时,启用备份路由。

当然,若拥有备份路由,就直接启用备份路由。若没有备份路由,就将数据缓存于队列。并同时触发发现路由工作。

1.3 路由的生存时间

每条路由可能由一条或多条链路构成。而路由的生存时间取决于多条链路的连通时间的最小值。具体而言,假定路由Ln-1由n-1条链路构成。这n-1条链路由n个节点构成。链路ij表示由节点i与节点j所构成的链路,i=1,2,…,n,且i≠j。因此,路由Ln-1的生存时间ETn-1可表示为:

(9)

其中Tij表示链路ij的连通时间。

路由生成

当源节点S需要向目的节点D传输数据时,源节点S就广播RREQ。当接收了RREQ包,首先判断是否之前已接收过此RREQ包。若已接收,则直接丢弃,否则就继续向邻居节点转播[12],直至将RREQ包传输至目的节点D。

当目的节点D接收了RREQ,就沿着传输RREQ包的路径返回RREP包。当源节点S接收到RREP包,源节点就能获取连至目的节点路径。RREQ包和RREQ包的传输过程如图3所示。

图3 路由发现过程

当构建了路由之后,源节点就计算路由的生存时间,并从中选择生存时间长的两条路由,将生存时间最长的路由作为主用路由,另一条路由作为备份路由。

2 仿真分析

2.1 仿真环境

为了更好地分析LDPR路由,利用NS-2.35软件进行分析。令50至200个移动节点随机分布于1 000 m×300 m的矩形中,其中10个节点作为源节点,它们周期地产生数据包,且数据包大小为512 byte。每个节点的传输半径250 m。节点的最大移动速度为30 m/s。具体地仿真参数如表1所示。

表1 网络仿真参数

选用RAODV和AODV-P[13]作为参照,并分析它们的路由开销、吞吐量和数据传输时延。同时,考查节点移动速度对路由性能的影响。每次实验独立重复50次,取均值绘制图。

2.2 数值分析

2.2.1 实验一

本次实验分析节点数对路由性能的影响。节点数从50变化至200,节点最大移动速度为10 m/s。

图4显示了路由开销率随节点数的变化情况。路由开销率等于成功传输一个数据包数与所需传输指控制包的数之比。

从图4可知,路由开销率随节点数的增加而上升。这主要是因为:节点数的增加,加大了节点对信道的竞争。竞争越激烈,构建路由越困难。这就使得需要多次传输控制包,可能才会建立一条路由。与RAODV和AODV-P路由相比,提出的LDPR路由有效地控制了路由开销。

图4 路由开销率随节点数的变化情况

图5显示平均吞吐量随节点数的变化情况。从图5可知,平均吞吐量随节点数增加而下降。原因在于:节点数越多,信道越拥塞,数据传输越不流畅。这必然限制了网络吞吐量。此外,相比于RAODV和AODV-P路由,LDPR路由的吞吐量得到提高,略高于AODV-P路由。

图5 平均吞吐量随节点数的变化情况

图6显示了三个协议的端到端传输时延。从图6可知,节点数的增加提高了数据传输时延。但是,相比RAODV和AODV-P路由,LDPR路由的传输时延较低。这归功于,LDPR路由提前预测链路连通时间,避免了因路由断裂而重新构建路由的时间。

图6 端到端传输时延随节点数的变化情况

2.2.2 实验二

本次实验分析节点移动速度对路由性能的影响。节点数为200,节点最大移动速度从5 m/s至30 m/s变化。

图7显示了端到端传输时延随移动速度的变化情况。从图7可知,三个路由协议的端到端传输时延随风节点最大速度地增加而上升。原因在于:节点移动速度越快,网络拓扑变化激烈,路由连通时间就短,这就增加了数据传输时延。此外,相比于RAODV和AODV-P路由,LDPR路由的时延得到有效控制。这归功于:LDPR路由提高了路由的稳定性,降低路由中断频率。

图7 端到端传输时延随节点移动速度的变化情况

图8显示三个协议的路由开销率随节点移动速度的变化情况。从图8可知,节点移动速度增加,加大了路由开销率。原因在于:节点移动越快,路由断裂概率越高,这就需要频繁地重建路由,必然增加路由开销。相比于RAODV和AODV-P路由,LDPR路由开销率得到有效控制。

图8 平均路由开销率随节点移动速度的变化情况

3 总结

节点的移动加剧了移动Ad Hoc网络拓扑变化,这给路由设计提出了挑战。本文提出基于链路连通时间预测路由LDPR。LDPR路由先依据节点运动信息预测链路的生成时间,并引用双路由机制传输数据包。实验数据表明,提出的LDPR路由缩短了传输时延,并控制了路由开销。后期,将扩大应用场景,如车联网。车联网是移动Ad Hoc网络的特例。在车联网中,车辆移动较快,对路由要求更严格。后期,将LDPR路由应用于车联网,这将是后期的研究方向。