基于蚁群算法的延时感知VANET 路由协议

吉 祥， 虞慧群， 范贵生， 孙怀英

（1. 华东理工大学计算机科学与工程系，上海 200237；2. 上海市计算机软件评测重点实验室，上海 201112）

车载自组网络（VANET）作为智能交通系统中的关键技术[1]，近年来已经成为车联网领域的研究热点。VANET 技术通过全球定位系统（GPS）、传感设备等实现车辆状况以及周边交通路况信息的采集；使用车载单元（On Board Unit, OBU）设备实现车辆与外界的信息交互；通过路边单元（Roadside Unit, RSU）或基站等道路基础设施实现车与外部网络的连接，从而提供车载导航、实时预警等综合服务。

VANET 具有自组织、高传输速率、易扩展性等优点，然而，车辆节点的高速移动会造成通信链路的不稳定，这给VANET 路由协议的设计带来了极大的挑战。如何为高度动态的VANET 系统设计高效、可靠的传输技术，成为一项紧迫而又具有挑战性的课题。

已经有一些研究将蚁群算法运用到VANET 中[2-4]，试图通过蚁群在源节点与目标节点间建立完整的路由路径。Correia 等[5]提出了一种基于移动感知与蚁群优化的MAR-DYMO 路由协议，利用车辆位置及速度信息预测其运动轨迹，并寻找生命周期最长的路径，但MAR-DYMO 性能会随着车辆数量的增加明显下降，具有可扩展性方面的问题。Rana 等[6]提出了一种基于ACO 的移动性感知区域路由协议，将网络划分为多个区域，跨区域路由采用主动式路由方式，而区域内采用按需路由。Li 等[7-8]运用蚁群算法来评估各路段的数据包转发延迟、带宽和投递率，提出了VACO 主动式路由算法。假设在每个路口处有一个RSU 来寻找并保存路由信息，但RSU 的代价非常昂贵，尤其是在VANET 部署初期。

由于蚁群算法具有良好的适应性、自组织性、鲁棒性以及容错能力等特点，非常适用于解决VANET中的路由问题，但同时也存在扩展性差、部署成本高等问题。

本文提出了一种基于蚁群算法的延时感知路由算法（ACDAP），将节点间的路由问题转化为交叉路口间的路由问题，可以提高路由路径的复用，减少路由发现开销。ACDAP 通过蚁群算法策略来探测各路段的网络延时和连通性情况，并在交叉路口设置桥节点解析蚂蚁探测包数据，计算区域性路由信息，即路段权重信息；桥节点通过获取的路段权重表信息可以直接或间接地构建源节点与目标节点间的路由路径。仿真实验结果表明，ACDAP 的性能优于传统的GPSR[9]以及GSR[10]算法，且优于同样采用蚁群策略的VACO 算法。

1 基于ACO 的延时感知路由算法

1.1 概述

城市场景中VANET 的路由路径遵循城市道路网络拓扑，并且只会在十字路口改变方向，本文将VANET 路由过程分为直路模式与路口模式。在直路模式下，数据传输采用贪婪转发的方式；而对于路口模式，通过在十字路口选择特殊节点充当桥节点的方式连接各分段道路网络，并利用桥节点进行路由决策。

1.2 桥节点的选择

首先，十字路口区域内的所有车辆都是候选节点，选取那些在路口处逗留时间尽可能长的车辆作为桥节点[11]。因此当有候选车辆因红灯而在路口区域停留时，优先选择这些由于红灯而等候在路口的节点，且红灯的剩余等候时间越长优先级越高；如果剩余等候时间最长的车辆只有一辆，那么直接选择该车辆担任桥节点；如果有多辆车辆符合桥节点竞争条件时，为了简单起见，随机选择其中一辆车作为桥节点。如果没有车辆在路口区域停留，考虑到经过十字路口中心的车辆正驶离路口，应当优先选择那些行驶方向朝路口区域中心且速度较低的节点。

图 1 桥节点选择机制Fig. 1 Bridge node selection at intersections

图1 通过具体示例展示了桥节点选择过程。图中的圈代表了路口区域的限定范围，桥节点候选车辆集合为ζ={V0,V1,V2,V3,V4,V5}，其中V0因红灯而停留等候，其余车辆均处于行驶状态。显然，在这种情况下，V0将被选为桥节点。假设V0节点不存在，那么候选车辆集合为ζ={V1,V2,V3,V4,V5}。可以看出，V2、V3、V4正向中心靠近，而V1和V5正驶离路口区域，因而{V1,V5}被排除出候选行列，此时最终的候选车辆集合为ζ={V2,V3,V4}，选择其中速度最慢的车辆作为桥节点。

当桥节点即将驶出路口区域时，将触发新的桥节点选择过程，并且旧的桥节点会将桥节点角色所有的相关信息交付给新的桥节点，这样可以保证车载网络在交叉路口场景中的持续连通。

1.3 基于延时感知的路段权重计算

1.3.1 蚂蚁探测包PAnt位于十字路口处的桥节点持续间断性产生轻量级控制包（称为蚂蚁探测包，PAnt）用于探测路段连通性情况，并将PAnt发送至相邻路段中，PAnt产生的时间间隔记作TAnt。PAnt在直路阶段通过单播方式向前转发，直至抵达下一个交叉路口的桥节点。

图2 示出了蚂蚁探测包转发过程。在交叉路口I1处，V1被选中为桥节点，其产生一个新的PAnt并发送至下一个路口，例如I2；在选择中继节点时，采用贪婪转发策略，V1选择邻居范围内离I2最近的节点V3作为下一跳的转发节点；当PAnt被路口I2处的桥节点V2接收时，I2将被记录到PAnt中，然后V2从{S23,S24,S25}路段（Sij表示路口Ii与Ij之间的路段）中选择一个路径继续转发PAnt，且信息素高的路段被选中的概率更高。对于一般情况，假设Ii有K 个相邻交叉路口，分别记为 I1, I2,…, IK，当PAnt到达Ii处时，根据式（1）选择概率pij最高的路段作为PAnt的下一个方向路径。

图 2 蚂蚁探测包转发过程Fig. 2 Forwarding process of ant packets

其中：ψij表示路段Sij的信息素值；f 表示PAnt刚经过的路口ID；pR(Sij)表示选择路段Sij的随机概率，pR∈(0,1)。

1.3.2 PAnt的设计 PAnt的设计如图3 所示。可以看出，PAnt由以下几部分组成：

（1）Type：说明包的类型。

（2）Packet_ID：包的标识信息，由产生PAnt的路口ID 以及产生的序列编码组成，中间通过“_”连接，如{Intersection_ID}_{Serial_Number}形式。

（3）Target_Intersection：PAnt将要发送至的交叉路口，包括路口的标识ID 以及位置（Position）信息。

（4）Intersection_Sequence：PAnt经过并记录的交叉路口序列，包括了路口的ID、Position 以及PAnt到达该路口时的时间戳（Timestamp），根据该时间戳可以计算出PAnt经过路段的延时情况。

（5）Intersection_Count：初始值为0，PAnt每经过一次交叉路口时值加1；超过一定阈值时，PAnt被丢弃，相当于lifetime 功能。

1.3.3 路段权重计算 蚂蚁每经过一个路段会沉积信息素（Pheromone）[12]，因此当桥节点接收到PAnt时，桥节点会计算相应路段的信息素。如果PAnt中的Intersection_Sequence 显示其经过了相邻的交叉路口Ii与Ij，则说明这两个路口间道路是连通的，则相应的信息素会被更新：

其中：ψij(t)与ψij(t+1)分别表示更新前与更新后路段Sij的信息素；Δψij表示蚂蚁更新信息素，表示如下：

其中：dij表示PAnt从Ii传输至Ij所需延时； dMij表示桥节点所记录的该路段蚂蚁探测包的最低延时；ω 表示一个常量。可以看出，当ω 设置为 ω∈(0,0.5)时，Δψij始终小于1，且dij越小，Δψij越大。

蚂蚁所留下的信息素会随着时间挥发，挥发过程定义如下：

其中：Teva表示信息素挥发过程的时间间隔；ηph表示信息素挥发因子，ηph∈(0,1)；τmin表示信息素的最低阈值。

结合式（2）、式（3）、式（4）可以看出，只要初始信息素值ψij(0)∈(0,1)，无论信息素如何更新，始终有ψij∈(0,1)；且ψij越大，代表路段Sij上网络连通性越好。

路段信息素更新之后，桥节点将更新相应路段的权重值。对于路段Sij，路段长度表示为Lij，则路段权重定义为如下形式：

ωij越小代表路段传输延时越小，连通性越好。

1.4 路由建立

桥节点通过对PAnt包携带信息的分析以及路段权重的计算，可以获取周围一片区域内道路的连通性情况，为路由转发提供全局性的视野，避免因贪婪转发而容易陷入局部最优的问题。图4 示出了一片区域的地图示例及相对应的道路权重矩阵。

在ACDAP 路由协议中，通过将车辆间路由的问题转换为终端交叉路口间路由的问题，以减少路由的重复探索，简化路由过程。当源节点Vsrc需要发送数据包时，其首先产生一个格式为＜Vsrc, Vdest, msg,Options＞的数据包Data_Packet，其中，Vdest表示数据包的目标车辆，msg 代表了具体的消息，Options 用于保存附加的路由信息。Vsrc与 Vdest之间数据传输的问题可以转变为在与Vsrc、 Vdest分别相邻的交叉路口Isrc、Idest间寻找合适的路由路径的问题。

图 3 PAnt 格式Fig. 3 Frame format of PAnt

图 4 区域地图示例及相应的权重矩阵Fig. 4 Map of a city area as an example and the corresponding adjacency matrix

为了方便表述，将Vsrc与Vdest统称为终端车辆，Isrc与Idest统称为终端路口。由于终端车辆有两个相邻的交叉路口，需要对其进行选择。这里主要通过考虑终端车辆与路口之间的距离以及车辆行驶方向选择合适的相邻路口作为终端路口，具体的参数设计如下：

其中：Si表示相邻交叉路口的选择权重，值比较高的一方被选为终端路口；dti表示终端车辆与相邻路口间的距离；Lt表示所在路段的总长度； χ 表示参数系数，本文设置为0.5；λdir(Vt)表示终端车辆的移动方向。

路由算法的具体步骤如下：

Step 1 源节点Vsrc首先将Data_Packet 发送至Isrc处的桥节点；

Step 2 桥节点解析路由包查看Idest是否包含在其权重矩阵中，如果是，则跳到Step 3；否则，桥节点找出权重矩阵中离Idest最近的交叉路口作为临时目标终端Itd；

Step 3 桥节点通过Dijkstra 算法计算Isrc与 Idest（或Itd）之间的最短路径，并将获得的路口序列存放至Data_Packet 包头之中，然后沿着所选路径转发Data_Packet，转发过程采用贪婪转发策略。

Step 4 如果Data_Packet 到达Itd，则重复Step 2～Step 4；否则，Data_Packet 到达Idest后，由Idest处的桥节点判断Vdest所在的路段，并将Data_Packet 沿着该路段转发至Vdest。

2 仿真实验和讨论

2.1 实验环境

本文采用NS2（Network Simulation-2）进行仿真实验。首先利用OpenStreetMap 地图获取真实的城市道路场景，并通过SUMO 生成道路网格文件和车辆节点运动轨迹作为NS2 的输入文件。每组仿真实验时长600 s，其中前100 s 让生成的车辆节点在地图环境中随机运动，其后的500 s 再统计相关的性能指标数据。通过改变参数中的车辆密度以及最大车速来获得不同的仿真场景，以考察不同因素对路由性能的影响。每组仿真实验独立重复20 次，并取其所得结果的平均值作为最终的实验结果。仿真参数的具体设置如表1 所示。

表 1 仿真参数Table 1 Simulation parameters

2.2 对比算法

为了评估ACDAP 算法的性能，实验中使用GPSR、GSR、VACO 算法作为对比方法。其中GPSR是一种基于贪婪转发的路由策略；GSR 是一种经典的基于地图的路由算法；VACO 是一种基于蚁群算法的路由算法，它利用ACO 算法来衡量道路的网络状态，包括延时、带宽以及分组投递率，并借助RSU保存路由信息并进行主动式路由发现。这3 种方法及本文算法都采用贪婪转发策略，但构建路由路径的策略不同，因此选择上述3 种算法作为对比算法具有可比性。

2.3 实验结果与分析

为了评估ACDAP 算法的性能，从两个方面对算法进行评估，分别为数据分组投递率（Packet Delivery Ratio, PDR）和平均端到端延时（Average End-to-End Delay, E2ED）。

2.3.1 数据分组投递率 数据分组投递率是指被目标节点成功接收的数据分组数量与源节点所发出的数据分组数量的比值。

图5 示出了数据分组投递率与车辆节点数目的关系。可以看出，VANET 网络中的节点密度直接影响了网络的性能，且车辆节点密度越高，各算法的分组投递率也越高。这是因为当节点数量过少时，网络的分离状况导致大量的数据分组不能被交付，导致数据分组投递率较低。

图 5 不同车辆节点密度下的分组投递率Fig. 5 Packet delivery rates for varying number of vehicles

图6 示出了数据分组投递率与车辆移动速度的关系。实验结果显示，随着车辆移动速度的增加，数据分组投递率呈下降趋势。这是因为车载网络的拓扑结构受到节点移动性的影响，车速越快，网络拓扑变化越频繁，导致连接链路的频繁断开，造成分组数据丢包率的增加。

图 6 不同车速下的分组投递率Fig. 6 Packet delivery rates for vary vehicular velocity

在4 种算法中，GPSR 的分组投递率始终最低。这是因为GPSR 采用贪婪策略，选择离当前节点较远的节点作为中继节点，而距离越远，信号衰弱越严重，链路质量也越差，因而丢包的情况也越严重。同样采用贪婪转发策略，GSR 利用地图计算得到了源节点与目标节点间的最短路径，但GSR 在计算最短路径时，只考虑了距离因素，而没有考虑网络的实际情况，因此其网络性能改进并不显著。VACO 利用蚁群算法获得了网络质量的诊断信息，从而获得了更为合理的路由转发路径，相比GPSR 算法有了明显的性能提升。然而，VACO 采用的是主动式的路由发现过程。由于VANET 中节点的快速移动以及网络拓扑的频繁变化，主动式路由方式往往具有一定的迟滞性。同样利用蚁群算法进行路段网络性能的诊断，ACDAP 主要考虑网络传输延时，延时越小意味着网络的连通性越好。实验结果表明，ACDAP 的数据分组投递率始终高于其他3 种算法。尽管都是采用贪婪转发，但不同的路由路径选择机制决定了各算法获得了不同的性能结果。ACDAP 通过蚁群探测包采集各路段的连通性信息，获得了所在区域的路段权重情况，选择了连通性高的路段构成了路由路径，避免了传统贪婪策略所面临的局部最优问题。

2.3.2 平均端到端延时 平均端到端延时是指网络中所有分组数据从源节点发出到被目标节点接收所需的平均时间间隔。

图7 示出了平均端到端延时与车辆节点数目的关系。从实验结果可以看出，随着节点密度的增加，节点在转发数据包时有更多的邻居节点作为候选，且遇到路由空洞的概率降低，因此所有算法的端到端延时都随着节点密度的增加而呈现下降趋势。尤其当网络中的节点数目小于900 时，可以看到GPSR与GSR 随着节点数目增多，端到端延时大幅下降，VACO 与ACDAP 算法的延时也有明显下降。这是因为网络空洞对路由延时的影响很大，当路由转发遇到网络空洞时往往需要采用存储-携带-转发的方式进行转发，而车辆携带行驶的速度显然无法和无线信号的传输速率相提并论。当节点密度较稀疏时，网络空洞数量较多，造成了传输延时较大。对于VACO 与ACDAP 算法，由于在选择转发路径时考虑了网络中各路段的实际网络性能，在转发过程中遭遇网络空洞陷入局部最优的概率大大降低，因此即使在稀疏场景下也具备一定的稳定性。

图 7 不同车辆节点密度下的平均端到端延时Fig. 7 Average end-to-end delay for varying number of vehicles

图8 示出了平均端到端延时与车辆移动速度的关系。实验结果显示，随着车辆速度的增加，所有算法的端到端延时呈上升趋势。这是因为车辆节点移动性越强，车载网络的拓扑结构变化越剧烈，网络连通性和稳定性下降，导致了传输延时的增加。

图 8 不同车辆速度下的平均端到端延时Fig. 8 Average end-to-end delay for varying vehicular velocity

可以看出，GPSR 算法的端到端延时在4 种算法中最高，GSR 比GPSR 的延时略有降低，ACDAP 的延时最低。GSR 算法在GPSR 基础上利用地图信息获取最短路由路径，但只是考虑了静态道路长度信息而没有考虑实际的网络状况，因此性能的提升并不明显。VACO 与ACDAP 都利用了蚁群算法获取道路中实际的网络性能，但VACO 采用主动式路由发现，而主动式路由发现过程需要消耗一定的时间，且VANET 中节点移动性较高，网络环境随时会改变；而ACDAP 利用桥节点保存区域路段权重信息，当有路由请求时，可以根据权重表通过最短路径算法直接选择出到目标节点或与目标节点较近的路口之间的最优化路径，因而ACDAP 获得了更低的网络延时。

3 结束语

本文提出了一种基于蚁群算法的延时感知路由策略。首先利用蚁群算法中信息素的更新机制以及蚁群对最优化路径的探索过程，提出了一种基于延时感知的分段网络权重分析方法，并建立面向局部区域的路段权重矩阵，然后根据该权重矩阵，提出了一种区域路由算法，有效解决了现有路由算法容易陷入局部最优的问题。实验结果表明ACDAP 能够保障VANET 数据传输的可靠性，并提高传输效率。

本文利用蚁群算法探索路段网络的连通性情况，并构建了优化路由转发路径，保障了VANET 中数据传输的可靠性和效率。然而，ACDAP 在路由路径上的转发依然采用的是贪婪转发策略，该策略虽然可以通过减少转发跳数而降低传输延时，但同时也增加了数据包丢失的风险。未来将完善ACDAP算法中的转发策略，在选择中继节点时考虑链路的稳定性等因素，提高数据的分组投递率。