一种基于链路质量的蚁群优化VANET路由算法

张家波，袁 凯，吴昌玉

(重庆邮电大学 通信与信息工程学院，重庆 400065)

0 引 言

车载自组织网络(vehicular ad hoc network, VANET)是智能交通系统(intelligent transportation system, TIS)不可缺少的重要组成部分，越来越受到学术界和工业界的关注[1-3]。VANET中由于无线接入技术的支持不需要固定的基础设施就能实现车到车和车到基础设施的通信[4-5]。

复杂的交通环境对VANET的通信性能提出了更高的要求，而通信性能好坏一定程度上取决于路由协议的优劣[6]。文献[7]提出一种基于学习方法的决策树理论的多副本VANET机会路由协议，在场景比较密集的情况下投递率和延时有良好的表现。基于地图的路由协议，对于频繁拓扑变化更具有灵活性，但开销较大[8-9]。文献[10]提出的路由协议可以快速应对拓扑的变化，但其不能得到最佳路径，导致延时增加，数据包传输率下降。结合蚁群优化算法的路由协议能较好适应复杂多变的交通环境，找到最优路径[11-13]。文献[11]是一种基于网络连通性与蚁群算法相结合的高效路由协议，通过蚁群算法寻找源节点到目的节点最佳网络连通性的路由，保证了信息传输的网络稳定性。文献[12]提出一种延迟敏感的蚁群优化车载路由协议，该算法在信息传输时延方面有较好的性能，并且能够很好地适应拓扑变化[12]。以上2种路由协议虽然相比传统的蚁群算法性能优良，但其仅仅考虑了影响路由效果的单一影响因素。未考虑网络连通概率、传输时延与分组投递率等因素对路由协议的综合影响，会导致传输链路的不稳定，以及信息传输的不准确，无法保证信息可靠有效的传输。

基于上文的简要分析，源节点到目的节点若要找到通信效果最优的路径，必须考虑整体的链路质量。本文提出了一种基于链路质量的蚁群VANET路由算法(ant colony optimization routing algorithm based on link quality for vanet, LACOR)寻找最优路径。通过建立链路质量模型并进行分析，得出道路环境对链路相关因素的影响，再结合改进的蚁群算法路径选择公式，对所选择的道路进行优化，最后得到最优路径。图1为城市路网模型。

1 链路质量研究

在本节中，我们假设车流比较稀疏，每辆车都装配有全球定位系统(global positioning system, GPS)、电子地图等设备，车辆均为活跃节点参与信息的转发。通过分析道路的连通概率、传输时延、分组投递率，建立链路质量模型，进行评估与分析。链路质量函数为

L(y)=λ1CP(y)+λ2Delay(y)+λ3PDR(y)

(1)

(1)式中：CP(y)为路由y的网络连通概率；Delay(y)为路由y的数据传输时延比率；PDR(y)为路由y的分组投递率。其中，Delay(y)=(Dth-D(y))/Dth，Dth为路由延时的阈值；D(y)为路由y的延时，且λ1+λ2+λ3=1。由于传输性能更多的体现在时延与分组投递率，因此，本文设置λ1=0.2；λ2=0.4；λ3=0.4。同时考虑无线信道的衰落、通信半径、路段长度、车辆密度、数据包的大小等因素对链路的影响。本文先研究单个路段的链路质量，进而分析出整体路由的链路质量。

1.1 连通概率研究与分析

根据本文情况定义路段连通概率：在道路中，2个车辆节点处于彼此的通信半径之内，它们之间能够直接进行通信，由于车流密度比较稀疏使得车辆下一跳通信范围内不一定有车辆而造成连通中断，因此，路段连通概率便是道路中车辆之间连接的概率。

在车辆运行的过程中只要车辆在彼此的通信范围内，就能直接进行通信。由于车辆快速运动使其拓扑变化频繁，很难得到确切的连通概率，根据参考文献[14]将长度为L的道路划分为多个单元格进行分析。假定单元格的大小为车辆的通信半径，即cs=R，则单元格的个数N=L/cs。

如图2为双向车道示意图。假定信息以车辆的运动方向优先传递，当运动方向上的传输链路中断，可以利用反向车道中的车辆进行链路修复，增加连通的概率。N个单元格对应有N-1个传输链路。在双向车道上ke和kw分别表示东、西2个车道的单元格cs内的车辆数，ρe和ρw分别为对应单元格内的车辆密度。根据交通流理论车辆速度服从正态分布，到达服从泊松分布[14-15]，则可以得到双向车道的概率密度函数为

(2)

本文以向东的运动方向为信息的传递方向，西行路段方向进行链路修复，Pnr表示西行修复链路车道所在的单元格内没有车辆而造成的不可修复概率，计算公式为

Pnr=f(kw=0)=e-ρwcs

(3)

根据(3)式可以求得链路可修复的概率为1-Pnr，然而一条道路可能存在多条修复链路。设变量q为可修复链路的条数，且q∈{0,1,…,N-1}。由此可得q条可修复链路的概率为

PW|Q(q)=(1-Pnr)q=(1-e-ρwcs)q,N>1

(4)

为了得到路段上的连通概率，还需求得q条断开链路的概率PQ(q)，根据相关定义，通信链路中断，意味着相邻单元格内任意2个车辆之间的距离大于通信半径R。车辆之间的距离S服从指数分布，则可求得链路断开的概率为

Pb{S>R}=e-ρwR

(5)

对于有N-1条传输链路来说，链路是否断开的情况满足二项分布，得到q条断开链路的概率为

(6)

因此，根据全概率公式得到双车道的连通概率为

(7)

1.2 传输延时研究与分析

根据本文的情况，我们定义路段传输时延：指信息从进入路段经过车辆“携带—转发”的方式离开当前路段所花费的时间。

道路中数据的传输方式分为2种：①逐跳转发，所需的时间与跳数及单跳时延相关；②携带-转发，当车辆下一跳范围内没有可以进行传递信息的车辆，则需要先携带信息，直到遇见可以进行转发的车辆再进行转发，所需的时间为逐跳转发时间加上携带时间。其中，单跳传输时延tp是车辆在其通信半径内通过单跳向中继车辆传输信息，确认接收所需要的时间，其影响因素有信道竞争、消息碰撞、竞争窗口等[16]。

当道路长度远大于传输单元长度即N≫1时，信息会通过多跳技术沿着道路进行转发，k表示在双车道上传输单元格cs内的车辆数。由车辆到达服从泊松分布可以得到，车辆数k的概率密度函数为

(8)

现在考虑当双车道的下一跳传输单元格内没有车辆，必须先进行消息携带当遇到车辆时再进行转发的情况。双向传输单元格内没有车辆的情况即k=0时，得到其概率密度函数为

ft=f(k=0)=e-(ρw+ρe)cs

(9)

当单元格个数N≤1时，传输延时为tp。当N>1，一部分是车辆逐跳转发信息花费的时间，与单跳传输时延和跳数有关；另一部分是车辆携带信息花费的时间，与携带运行的长度和相对速度有关，如(10)式

(10)

1.3 分组投递率研究与分析

假设数据在无线信道传输中采用请求发送/清除发送(request to send/clear to send, RTS/CTS)协议,可以减少由隐藏节点问题所造成的冲突机制。但信息在多跳传输过程中会存在数据丢失或者损坏，这种情况下导致道路的数据传输性能不可靠，影响链路性能。因此，先研究在瑞利衰落信道下，2个传输单元格内车辆单跳情况下的误码率(bit error rate, BER)为

(11)

(11)式中：Pt是发射机功率；Gt和Gr是发射机和接收机的增益；fc是载波频率；c是光速；s是发射车辆与接收车辆之间的距离；σf2是瑞利分布的方差；Ptherm是噪声功率。其中，Ptherm=FkT0Rb，F是噪声系数，k是玻尔兹曼常数，T0是室温，Rb是数据发送速率。

(11)式是计算特定单跳长度的BER,实际中，车辆传输信息每一跳的长度是不固定随机分布的，连续2个车辆之间的距离服从指数分布，因此，可以得出其概率密度函数为

(12)

由此，可以得到单跳情况下平均的链路BER为

(13)

根据误码率与分组投递率之间的关系，可以求得单跳情况下的分组投递率为

PDR1hop(s)=(1-(1-cr)E[BERs(s)])psize

(14)

(14)式中：psize表示数据包的大小；cr代表错误校正比率，结合1.2节传输延时中的分析得到传输的跳数Hop=(N-1)(1-ft)，所以，求得路段上的分组投递率为

PDRs=PDR1hop(s)Hop

(15)

2 LACOR算法

2.1 蚁群算法

蚁群算法是一种自适应算法，适应于动态组合优化路由等问题的解决。最早是由Dorigo提出的并用于解决旅行商问题。蚁群初期随机地选择前往目的节点的路径，每条路径上都存在一个启发函数τij和期望启发函数ηij，α和β分别代表信息启发因子、期望启发因子。根据走过路径上分泌的信息素浓度以及状态转移概率寻找路径，形成一个正反馈机制，最后逐渐找到最优路径。当蚂蚁k到达当前路段时，选择下一个相邻路段的概率为

(16)

2.2 基于链路质量的蚁群路由算法

根据前文所分析的链路质量，再结合蚁群算法的应用原理，首先将链路质量扩展为2种类型：局部链路质量LQ和全局链路质量GQ，如(17)式，并且将局部链路质量定义为局部信息素，全局链路质量定义为全局信息素，以便与蚁群算法结合分析。

(17)

全局信息素路由y上的连通概率、传输延时、分组投递率分别为

(18)

(18)式中：CP(ei)是路段ei的连通概率；PDR(ei)是路段ei的分组投递率；Delay(ei)是路段ei的传输延时比率。结合链路质量模型引入局部信息素和全局信息素，改进后的蚁群状态转移概率为

(19)

LQij用于帮助蚂蚁获取最新路段信息，并探索出新的路由避免出现路由空洞和高负载的链路。GQij反映的是整条路由的链路质量，有助于算法的快速收敛。通过调节α和β权重因子数值，使其既不影响新路径的探索又能保持最优路径的选择。

若前向蚂蚁到达目的节点并且传输时延满足路径的要求，前向蚂蚁便会转变为后向蚂蚁，否则直接丢弃。后向蚂蚁便会携带由前向蚂蚁记录给出的路由表原路返到目的节点，此时便会得到最新的全局信息素(latest global link quality, LGQ),通过(20)式进行全局信息素的更新。

GQij←(1-δ)·GQij+δ·LGQij

(20)

(20)式中：δ(0<δ<1)为是信息素挥发系数，(1-δ)·GQij为挥发的全局信息素；δ·LGQij为增加的全局信息素。全局信息素的更新可以避免出现搜索停滞，一旦全部的后向蚂蚁回到源节点，便会选出最大的全局路由链路质量L(y)，并将此作为本次蚁群迭代的最优路径。

2.3 LACOR路由算法步骤

蚁群算法中数据包通过携带-转发策略进行传输，根据概率分布函数和信息素的更新选择下一个路段，寻找源节点与目的节点之间的可用路径，经过路径优化，得到最优路径的集合。为了应对车载自组织网频繁的拓扑变化维护路由，当路由集合中的道路信息改变时，LACOR算法就会重新建立一个新的路由。主要的算法步骤如下：首先，进行信息的初始化，如链路信息、蚁群最大迭代次数、蚂蚁总数、权重因子等，源节点向目的节点发送路由请求，若存在路由，则源节点直接发送信息给目的节点，否则，进行蚁群路径寻优；然后开始蚁群迭代，蚂蚁搜索路径，通过判断分析，再结合(19)式进行路段的选择，(20)式进行全局链路质量的更新；最后当蚁群迭代完成后，整理迭代结果，获取最优的路径集合。LACOR算法的具体步骤如下。

输入:初始化道路和蚁群算法基本参数。

1 源车辆节点向目标车辆节点发送信息

2 if 存在路由, then

3 发送信息

4 跳到行20

5 else

6 for k=1: K (迭代次数)

7 for m=1: M (蚂蚁数量)

8 if 前向蚂蚁到达目标车辆节点, then

9 前向蚂蚁变为后向蚂蚁返回源车辆节点，根据(20)式更新全局链路质量

10 else

11 根据(19)式选择下一条道路，返回行8

12 if m=M, then

13 选择最优的路径并保存到路由表中

14 else

15 返回行7

16 if k=K, then

17 得到最优路由

18 else

19 返回行6

20 结束

输出: 传输时延和分组投递率。

3 仿真分析与对比

本文通过Matlab仿真软件对路段的链路质量以及LACOR算法进行仿真分析，并与文献[11]算法，文献[12]算法进行对比。相关参数的设置如表2。

表2 仿真参数设置Tab.2 Simulation parameter settings

当道路长度L=1 000 m时，车辆密度与路段连通概率的关系如图3。随着车辆密度从0.01～0.05 vehicle/m增大，双向车道中存在的中断链路被逐渐修复，使得整条道路处于较高的连通状态，提高了网络的连通概率。在车辆密度较小为0.01 vehicle/m的情况下，当通信半径R为250 m要比通信半径为150 m的路段连通概率高出13%。通信半径越大、单元格越大，包含的车辆就越多，2个相邻单元格内车辆进行通信的概率就越大，连通性就越高。

图4为车辆密度与路段传输时延的关系。在道路长度L=1 000 m情况下，当车辆密度较小为0.01 vehicle/m，通信半径为250 m时，车辆速度为10 m/s要比20 m/s的路段传输时延高出2.2 s。随着车辆密度的增加传输时延逐渐减小，当增加到0.03 vehicle/m后，通信半径为200 m和250 m的传输时延分别减小到0.9 s和0.7 s,并且保持不变。由以上分析可知，当车辆密度较小时车传输方式为携带-转发，速度为影响传输时延的主要因素；当车辆密度较大时，传输方式为逐跳转发，车辆通信半径为主要因素。

由图5为道路长度与路段分组投递率的关系，当前的车辆密度为0.03 vehicle/m。通信半径R=150 m时，256 Byte数据包的分组投递率相较于128 Byte的数据包大约低6%。当数据包大小为256 Byte时，通信半径150 m要比180 m大约低2%。随着道路长度的增加，分组投递率呈递减的趋势，同时单元格的数值向上取整，所以会出现某个长度范围内的分组投递率是相同的。数据包越大，信息传输过程中发生错误丢失的概率就越大，导致分组投递率越低，而车辆的通信半径越大，信息转发所需的跳数就越少，信息的丢失也就越少，分组投递率越大。

图6为蚁群迭代次数与传输时延的关系。随着蚁群迭代次数的增加，3种算法的数据传输时延都在减少。文献[12]算法是基于传输时延进行最优路由的选择，因此，该算法最后迭代的时延最低，但是更容易产生长时间的搜索停滞现象。文献[11]算法基于连通概率进行路径的选择优化，初期搜索较慢，并且也会造成搜索停滞使链路处于高负载状态。而LACOR算法最后迭代的时延表现虽然略低于文献[12]算法，但根据图7可知，其分组投递率远远高于文献[12]算法，并且收敛速度最快，没有出现搜索停滞的现象，最后的迭代整体效果最优。

图7为蚁群迭代次数与分组投递率的关系。随着蚁群迭代次数的增加3种算法的分组投递率呈增长趋势。LACOR算法不仅收敛速度快而且分组投递率最高，没有出现搜索停滞，在第74次迭代之后就到达了0.875的分组投递率，并且增涨的幅度是文献[12]算法的1.5倍，虽然文献[11]算法的增长幅度也大，但最终的数值低于LACOR算法，并且根据图6可知，文献[11]算法的传输时延没有LACOR算法表现优良。综上所述，2种对比算法仅仅考虑了单方面的链路性能，并未达到较好的效果，均出现不同程度的搜索停滞现象，整体效果低于本文算法。

4 总结与展望

文中提出了一种城市双车道环境下的车载自组织网LACOR算法。该算法通过考虑道路中车辆密度、通信半径等因素对连通概率、传输时延、分组投递率的影响来研究链路质量，再结合改进后的蚁群算法路段选择公式，以及信息素的更新，求得最优路由。仿真结果表明，该算法收敛速度快、传输延时低、分组投递率高，具有良好的通信性能，能够保证信息的可靠稳定传输。但对于链路质量权值系数的取值方面过于主观，不能根据具体传输性能要求自我调节，是本文接下来需要考虑研究的一个方面。另一方面，未来5G等新兴技术的发展一定会推动车辆自动驾驶、道路安全及通信效率服务等相关V2X车载自组织网技术的研发与应用。