基于链路连通时间的移动Ad Hoc网络路由

林 勇，宋三华

(1.重庆电子工程职业学院 通信工程学院，重庆 401331；2. 黄淮学院 信息工程学院，河南 驻马店 463000;)

0 引 言

移动Ad Hoc网络是一种无中心、自组织的、由多个具有通信能力的移动节点组成的无线网络架构。这些移动节点可自行组建网络[2]，既可独立运行，也可转发数据，扮演路由器的角色。由于无线Ad Hoc网络具有灵活、自行组织特点，它广泛应用于救援、军事行动等灵活的通信系统应用场合。然而，节点移动是无线Ad Hoc网络典型特性，加大了网络拓扑的动态变化，这使得无线Ad Hoc网络的数据传输成为挑战。

目前，针对无线Ad Hoc网络，研究人员提出不同的路由协议，比如DSR、OLSR[3]、AODV和DSDV[4]路由。按需距离矢量(Ad Hoc On-demand Distance Vector，AODV)是典型的无线Ad Hoc网络路由，但是AODV路由仍存在一些不足。这些路由并没有考虑了节点移动性。为此，研究人员提出了AODV的改进路由。

曹文君等[5]提出基于链路连通寿命的AODV的改进路由。它先计算节点间的速度差，再构建速度差最低的稳定的路径传输数据。而刘大勇等[6]从时延角度选择路由，降低端到端传输时延。此外，蔡菁等[7]也对AODV路由进行优化，利用单播和广播的混合方式传输控制包，再减少广播帧数量，最后提高路由稳定性。

然而，这些路由只从节点移动信息方面决策路由，并没有考虑到信道衰减信息。而实际上，无线网络链路容易受到外界环境影响，这更加剧了网络拓扑的变化，最终影响了路由的稳定性。

为此，本文针对无线Ad Hoc网络的数据传输问题，展开分析，提出基于LET-RP路由。LET-RP路由首先了计算链路连通时间，然后从选择连通时间长的节点作为下一跳转发节点，从而构建稳定的路由，克服无线Ad Hoc网络的拓扑动态性。在估计链路连通时间时，不仅考虑了节点的移动信息，还考虑了信道衰减统计信息，这有利于提高路由稳定性。实验数据表明，提出的LET-RP路由有效地降低了端到端传输时延，并提高了吞吐量。

1 LET-RP路由算法

LET-RP路由是从稳定链路角度选择下一跳转发节点。为此，先利用节点的移动参数和信道衰落统计信息计算链路的连通时间，然后选择连通时间最长的节点作为下一跳转发节点。

1.1 链路连通时间

链路的连通时间受到节点移动和信道衰落两方面影响。为此，先利用节点移动信息估计链路的连通期望时间。

假定车辆i与j的链路表示为ij，它们的位置坐标分别为(xi,yi)、(xj,yj)。结合文献[8]，链路ij的连通期望时间LETij：

(1)

其中θi、θj分别表示车辆i和j的移动方向。而ϑi、ϑj分别表示车辆ϑi和ϑj的瞬时移动速度。同时，a=ϑicosθi-ϑjcosθj、b=xi-xj、c=ϑisinθi-ϑjsinθj、d=yi-yj。

接下来，分析引用反映信道衰落的变量ε，其定义如式(2)所示。在无衰落的理想传输环境，ε=0。而在含有建筑物的都市环境，ε一般较大。

ε=1-E[φ]

(2)

其中φ表示链路ij连通概率。通常认为，接收到的信号功率大于预定的阈值，就可认为链路是连通的。而E[φ]表示φ的期望。

最后，依据LETij和变量ε估计链路的连通时间ELLTij，如式(3)所示：

ELLTij=LETij×(1-ε)

(3)

1.2 基于信道统计的E[φ]估计

首先，引用基于Nakagami-m的无线信道模型[9]。若所接收的信号功率表示为p，信号功率阈值表示为Rth。因此，连通概率φ可表示为p和Rth的函数，如式(4)所示：

(4)

结合文献[9]，也可用车辆间距离d和车辆传输距离R表示连通概率φ，如式(5)所示：

(5)

然而，车辆i、j不断移动，它们间的距离d是不断变化的。据此，概率φ也是动态变化的。为此，先引用连续随机变量Z替换式(5)中的距离d，然后，再结合文献[10]，可计算φ的期望，如式(6)所示：

(6)

其中fZ(z)为概率密度函数。

由于E[φ]与车辆间距离d相关，依据车辆相对移动方向，分三种情况讨论E[φ]。

(1)车辆i与j以等速，同向移动。在这种情况下，它们间的距离dij为常数。据此，E[φ]可表示为：

(7)

(2)当车辆i与j反向移动。此时，它们间距离逐渐增加，如图1所示。在这种情况下，先计算Z的概率密度函数：

图1 反向移动的通信链路

(8)

最后，利用式(8)计算E[φ]：

(9)

(3)当车辆同向移动，且车速不同，如图2所示。在这种情况下，变量Z的概率密度函数如式(10)所示：

(10)

图2 同向通信连接

类似地，再利用式(10)计算E[φ]，如式(11)所示：

(11)

1.3 转发节点的选择策略

LET-RP算法引用基于竞争转发(Contention-based Forwarding, CBF)[8]的策略，选择下一跳节点。基于CBF的转发节点选择方案是属分布，即每辆车依据移动参数和链路的多径衰落参数自己选择下一跳的转发节点。这种策略提高了消息的分发效率。

LET-RP算法引用链路稳定函数(Link Stability, LS)作为选择下一跳转发节点的度量指标，其定义如式(13)所示：

(12)

其中k是一个常数，其决定了函数的增长率。

为此，每个车辆依据LS设置定时器，如式(13)所示：

t(LS)=T×(1-LS)

(13)

其中T表示最大的转发时延。

依据式(13)可知，车辆定时时间取决于LS。如果，当两个或多个车辆的LS相近，则可能会产生数据包冗余。为此，需要采取策略抑制冗余。为此，在利用LS设置定时器时，再引用另一参数，进而降低发生数据包冗余的概率[11-12]。

众所周知，路径长度是路由性能的一个重要指标。路径越长，参数的节点越多，竞争越激烈。为此，引用衡量路径长度的变量P，其定义如式(14)所示：

(14)

再结合LS和P参数，并引用权重均值构造函数f：

f=α×LS+(1-α)×P

(15)

最后，依据函数f设置定时器，如式(16)所示：

t(f)=T×(1-f)

(16)

2 下一跳转发节点选择流程

当节点(假定为节点i)需要转发数据包，就将先广播路由请求控制包RREQ。邻居节点(假定为节点j)一旦接收了RREQ包，首先检测是否接收过此包，若已接收了，就丢弃，否则就依据式(13)设置定时器，并开始计时。一旦定时完毕，并且在定时过程无监听到其他节点向节点i回复RREP包时，节点j就立即回复RREP。

一旦接收RREP包，节点i就将此节点作为数据包的下一跳转发节点。从式(13)可知，链路的连通时间越长，定时时间越短，此节点就第一时间回复RREP包。下一跳转发节点的选择过程如图3所示。

图3 选择下一跳节点的流程图

通过图3所示的策略，选择下一跳转发节点，从而形成连通时间长的路由传输数据包。若从一条路由角度分析，整条路由连通时间等于构建这条路由的多条链路中的最短的连通时间。

具体而言，令Rn-1表示由n-1条链路构成的路由，并且这n-1条链路由n个车辆构成。因此，路由Rn-1的有效寿命(Effective Route Life Time, ERLT)就是这n-1条链路寿命的最小值，如式(17)所示：

(17)

如图4所示，车辆(移动节点)L、M被选为转发节点，进而构成从RSU至车辆S的路由。从图5可知，从RSU至车辆S的路由三条链路构成，并且这三条链路的ELLT值分别为12 s、8 s和10 s，最小值为8 s。因此，路由连通时间为8 s。

图4 路由示意图

3 实验仿真

3.1 实验环境

为了更好地分析LET-RP路由性能，利用NS-2.35软件建立仿真平台。网络仿真参数如表1所示。

表1 网络仿真参数

此外，移动节点在750 m×750 m区域内移动，并且每个节点以Random Way Point 模型移动。具有而言，节点随机移动至一个目的地，再暂停一段时间后，又随机选择一个目的地再移动。具体的移动参数如表2所示。

表2 移动参数

每次实验独立重复50次，取平均值作为最终数据。同时选择AODV和AODV-P[13]作为参照，同时比较它们的路由开销、吞吐量和端到端传输时延性能。

3.2 数值分析

首先分析三个路由协议的路由开销。实验数据如图5所示，其中路由开销是指每成功接收一个数据包，所产生的控制包。

图5描绘了节点数对路由开销率的影响。从图5可知，节点数的增加，提高了路由开销率。原因在于：节点数越多，信道竞争越激烈，增加了冗余包。

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

从图5可知，提出的LET-RP路由的路由开销低于AODV和AODV-P。原因在于：AODV采用泛洪方式传输数据，而AODV-P采用固定概率传输控制包，它们并没有考虑到节点的移动信息和信道衰减情况，这必然加大了建立路由的控制包数量。

接下来分析三个路由协议的吞吐量随节点数的变化情况，实验数据如图6所示。从图6可知，节点数的增加，降低了网络的平均吞吐量。这主要是因为：节点数的增加，加剧了信道资源的竞争，激发了网络拥塞，进而降低了网络吞吐量。从图6可知，提出的LET-RP的平均吞吐量高于AODV和AODV-P。这要归功于LET-RP路由通过选择稳定路由传输数据，提高了数据传输的可靠性。

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

最后，分析三个协议的平均端到端时延，其是指将数据包传输至目的节点所需的平均时间。实验数据如图7所示。

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

从图7可知，端到端传输时延随节点数的增加而增大。原因在于：节点数越多，信道资源越激烈，降低了数据传输的流畅性，这必然加大了传输时延。同时，也增加排队时延。与AODV和AODV-P相比，提出的LET-RP路由的时延得到有效控制。这要归功于LET-RP通过融合移动信息和信道衰减信息，建立连通时间长的路由，减少了频繁建立路由的概率，提高了数据传输的流畅性，进而控制了时延。

4 结 语

本文针对移动Ad Hoc网络的数据传输问题，提出基于链路连通时间的移动Ad Hoc网络路由LET-RP。与传统的移动Ad Hoc网络路由不同，LET-RP路由只不仅考虑节点的移动信息，还考虑了信道衰减信息，从而建立稳定链路。实验数据表明，提出的LET-RP路由有效地降低。