基于蚁群算法的自适应车路协作消息传输方法研究*

刘明剑 张思佳 孙华

（1.大连海洋大学，大连 116023；2.大连海洋大学，设施渔业教育部重点实验室，大连 116023）

主题词：车载自组织网络 路侧单元 协作通信 蚁群算法 中继选择

1 前言

车载自组织网络（Vehicular Ad-hoc Network，VANET）通过车辆与道路基础设施节点的相互通信，形成信息交互共享的自组织通信网络，但在车辆高速移动和网络拓扑结构快速变化等情况下，大文件传输以及高精内容精准分发效率过低[1-2]。目前，许多学者正在试图利用车载容迟网络（Vehicular Delay Tolerant Network，VDTN）解决这一问题。VDTN借助于智能交通基础设施路侧单元（Road Side Unit，RSU），在车辆相遇或车辆到达RSU覆盖区域时通过无线网络进行数据交换，使得RSU可以延伸车辆数据转发的覆盖范围，增加网络中数据传播种类和传输量[3]，对于传输时延要求相对较低的VANET非行车安全类应用是一种高效的数据传输模式。

基于VDTN模式实现车路协同，提升网络传输性能已经取得了一些研究成果：Gred[4]等人以节点之间欧几里得距离为输入，设计了基于贪婪算法的信息分发策略；Spray[5]等人提出了基于地理位置的多副本路由机制，选择位置最优车辆作为载体进行消息转发；Jalooli[6]等人设计了一种城市路网中路侧单元优化部署方法，能够提高信息传输效率，缩短信息传输延时；文献[7]、文献[8]采用基于货币交易的激励机制，鼓励节点间进行合作通信。在此基础上，文献[9]～文献[11]基于博弈论，选择进行协作的路侧单元进行信息交互，最终达到纳什均衡状态，提高信息传输的效率；Li[12]等人设计基于车辆数据缓存机制的信息传输方法，路侧单元在覆盖范围内，将信息传输至特定车辆，其他车辆可以从指定车辆获取相关内容，降低路侧单元通信压力；杨月辉[13]基于图划分理论，提出了基于重边粗化的多级联盟划分（Multilevel Hyper-Graph Partitioning Based on Heavy Edge Matching Scheme，MHEMs）车路协作策略。

上述方案均能提高车路协作条件下的信息传输效率，但存在如下问题：需要在车辆自组织网络中获得路网的全局拓扑结构；基于博弈理论，多RSU形成协作组考虑了协作组内利益而忽略某些个体RSU 的利益；基于图划分理论的合作系统考虑网络整体利益，而忽略了协作组内部各RSU和车辆之间的协作关系。

本文针对上述问题，提出基于蚁群算法的自适应车路协作消息传输方法，能够在快速变换的车辆拓扑结构中，拓宽车辆信息的传输范围，为VANET数据的高效传输提供支持。

2 车路协作消息传输问题建模

2.1 车路协同消息传输模式分析

基于车路协作的消息传输的目的是通过车车和车路协作发掘VANET 的潜在通信能力，提高整个网络中信息的传输效率。假设某个路网区域包含2 个RSU 节点，并且RSU之间可以进行协作，向其覆盖范围内的车辆发送不同类型的数据，如图1所示。RSU1向其覆盖范围内驶向RSU2的车辆发送数据c1，同时RSU2向其覆盖范围内驶向RSU1的车辆发送数据c2，当相向行驶车辆相互靠近至某一范围时，依靠V2V 方式交换已经获得的不同的数据c1和c2。通过上述传输模式，车辆无需经过多个RSU 便可以获取所需的多种类型数据，从而提高路网中单位时间内信息的传输数量和类型，有效解决车辆因高速运动在RSU覆盖范围内通行时间较短导致下载数据量有限的问题。

图1 RSU间协作式通信

虽然在图1 所示的车路协作模式下可以有效提高信息传输效率，但是这种模式需要在多个RSU 之间进行同步，并协调需要发送的数据类型，这一过程会增加因维持多个RSU 进行协作所带来的成本（如维持一个特定信道来交换信息）。当网络中需要传输的信息量有限或者路网规模较小时，RSU间协作进行消息传输所花费的成本高于带来的收益，因此需要设计一种高效的车路协作通信方法，依据RSU 间相向车流量形成多个车路通信协作组，在组内采用协作通信模式，组与组之间采用非协作模式，不仅能够有效发掘出潜在的车路协作通信能力，同时可控制多个RSU同步所带来的成本。

2.2 协作式车-路通信系统模型

分析车路协作的信息传输模式可知，车路协作消息传输需要解决如下问题：如何在路网中合理选择RSU建立协作组内稳态的链接完成信息传输，从而提升VANET 中合作信息分发的效率；如何将不同的数据类型和内容分发给能够相遇的车辆，从而拓展车辆的信息获取范围，最大化提升车路协作的效用。

针对上述需求，建立协作式车-路通信系统模型。在城市道路网络中，设车辆节点集合为V：

式中，vi为车辆节点集合V中第i个车辆的节点。

路侧单元节点集合为R：

式中，ri为路侧单元集合R中的第i个RSU节点。

从集合V和R中选取参与者进行协作通信，在集合R中ri和rj（i≠j）进行协作的依据是RSU 之间能够进行车-车通信共享信息的车对数，设Rcop∈R为某一个进行协作的RSU节点集合，在Rcop中如果ri和rj之间存在直达道路，有效通信路程设为d，那么能够发生这种相对车-车通信共享信息的车对数为mij：

式中，δ∈[0,1]为ri和rj之间每距离1 km 其间相向行驶车辆能够进行V2V 通信的比例；vij为某一时段所有从ri驶向rj的车辆的节点集合，|vij|表示vij中车辆节点的数量。

在协作组Rcop中，车辆节点vk∈vij在从ri驶向rj过程中，能够下载获得的平均数据量为pk,i，pk,i主要由2个部分组成：车辆节点vk在ri通信范围内下载获得的平均数据量pkV2I；车辆节点vk从ri驶向rj过程中，通过V2V 通信进行信息交互获得的平均数据量pkV2V。pk,i的表达式为：

式中，pkV2I=dkI·punit(V2I)/vkI；dkI为车辆节点vk在ri覆盖范围内能够进行数据下载的有效距离；punit(V2I)为单位时间内车辆能够下载的平均数据量；vkI为车辆节点vk依据移动模型和车流量密度在ri覆盖范围内行驶的平均速度；pkV2V=mij·dkij·punit(V2V)/vkij；dkij为车辆节点vk在ri与rj覆盖范围内能够进行数据下载的有效距离；punit(V2V)为单位时间内车辆在相遇过程中能够交换进行传输的平均数据量；vkij为车辆节点vk依据移动模型和车流量密度从ri驶向rj覆盖范围内行驶的平均速度；R(ri)为ri的通信范围。

需要进行传输的数据类型集合为C={ci|1≤i≤L}，数据类型数量为L=|C|；ci∈C为车辆节点vk从ri下载到的数据；wci∈(0,1)为数据ci的权重，且wc1＞wc2＞…＞wci＞…＞wcL。

通过采用上述路侧单元协作机制，对于单一协作组Rcop，建立某一时段产生的总收益目标函数为：

其中，单个协作组采用车路协作通信模式所获得的收益为：

式中，bc={bi|1≤i≤L,L∈N}为在此协作组中每个RSU选择一种要传输给车辆的数据类型组成的集合；bi为ri从数据集合C中选择的要传输给车辆的数据类型；Bc为bc的排列所组成的所有元组的集合；β∈(0,1)为车辆节点vk每下载一个数据块，协作组所能够获得的收益系数。

式（6）描述了单个协作组的收益，然而在整个城市路网中，可以形成多个RSU 集合进行车路协作，因此基于式（4），建立整个城市路网中车路协作的收益函数fall：

其中：

式中，E为在集合R中形成RSU协作组的集合；ε为E中的一个车路协作组；λ 为协作组ε中与ri∈ε采用协作式通信方式的RSU节点集合。

3 基于蚁群算法的车路协作消息传输方法

3.1 RSU间协作通信蚁群算法

为了提高整个路网中的收益，进而提升VANET 数据传输效率，发挥车路协作通信模式的实时效用，本文设计了基于蚁群算法的车辆协作消息传输方法：

a.假设将ma只蚂蚁，在路网RSU节点集合R中随机选择一个RSU 节点（设nr为路网中RSU 的数量，一般情况下ma=nr），每只蚂蚁以选定的ri为起点，根据转移概率选择协作通信可能性最大的rj（i≠j），并进行局部信息素更新；

b.每只蚂蚁按照选择的RSU 排列顺序依次选择协作RSU，全部选择完毕后对此次协作选择中每只蚂蚁的适应度进行评价，进行全局信息素更新；

c.根据程序设定循环kmaxiter次后，给出最终分组策略。

图2 给出了路网RSU 协作示例。图2a 中，RSU2和RSU3间为单向车流，其他均为双向车流。图2b中，蚁群算法开始工作：初始RSU 数量nr=5 个，蚂蚁数量ma=5只，其中，蚂蚁a3遍历完成一次路网给出划分策略，如表1所示。

图2 车路协作过程

表1 初步分组策略

3.2 转移概率

a.信息素初始值。初始时刻，设定RSU之间的信息素浓度的初始值τ为：

式中，avg(ri)为与ri存在V2V通信的车辆对数的平均数。

b.信息素分布更新的启发函数为：

式中，iter(ηij)为自适应更新函数；kiter为此时迭代次数；ηmax、ηmin分别为信息素更新的最大值和最小值；rvij为通信能力评估函数。

c.状态转移概率。车联网中RSU 间协作通信的关键是发掘车辆间共享信息的能力，而这与RSU 间存在的车辆数量密切相关。当2 个RSU 之间具有较多可进行V2V通信的车辆时，这2个RSU应划分在同一个协作组中，在路网中蚂蚁会根据转移概率决定从当前的ri到达的下一个rj，即访问同一协作组内部RSU的可能性较大，蚂蚁从ri选取rj的转移概率Pij为：

式中，A为路网中蚂蚁从ri到达的下一个RSU 所有可能性集合；τij(t)为在路网中t时刻ri与rj之间道路上的信息素浓度；ηij(t)为t时刻ri与rj之间的启发信息；α、γ为0～1范围内的常数。

3.3 信息素更新

在用蚁群算法求解车辆协作基本问题过程中，每条线路的选择依据路径上信息素浓度进行。在算法初始阶段，每对RSU之间首先设定初始信息量，蚁群建立的第1条引导信息主要是节点间的潜在车辆数量，所以蚁群在后续经过的路径上留下的信息不一定能反映最优路径的方向。因此蚂蚁在后续选择RSU 过程中，选择可以进行通信的潜在车辆数量最多的路径作为最优搜寻方向，确保蚂蚁创建第1条ri→rj路径便能引导算法找到最优全局路径，但所有蚂蚁在后续搜索过程中留下的信息不能完全反映最佳前进方向，因此不能确保蚁群创建的第1 条路径就能引导蚁群找到全局最优路径。随着算法不停迭代，信息素容易积累到某些局部最优的路径上，最终导致算法陷入局部最优，出现结果迭代的停滞现象。因此，需要在信息素的更新方式以及局部搜索策略等方面进行调整，以寻找最优协作策略。

3.3.1 局部更新规则

局部更新是为了防止算法早熟，找到协作规模相对较弱的情况。在每一只蚂蚁访问完成一个ri，选择要访问的下一个rj时，在路径ri→rj依据局部信息素浓度更新公式为：

为了避免某条路径ri→rj的信息素因累积过少，导致被选中概率较低的情况出现，设τlow为信息素取值的下限，当路径上信息素低于τlow时，强制更新路径ri→rj信息素为τlow。

3.3.2 全局更新规则

在对蚂蚁进行全局更新过程中，为了使得蚂蚁在本次搜索选择过程中获得协作方案，并且不会对之后蚁群搜索协作方案产生误导，需要在每次循环后对路径上的信息素进行相应处理。在每一只蚂蚁完成对集合R中所有RSU的访问后，即完成一次循环后，对残留信息进行更新处理：

式中，Δτij为蚂蚁在路径(i,j)上留下的信息素；ρ∈(0,1)为信息素挥发程度；Lb、Lw分别为在此次求解过程中找到的最优策略和最差策略。

3.4 适应度函数

在车路协作过程中，为提高车联网数据传输效率，需要付出额外成本以维持路侧单元之间的协作，如在某一个车路协作组内部路侧单元间需要进行通信同步、维持一个开放信道来交换信息等。这些成本会在一定程度上抵消车路协作通信所带来的优势，成本增加量与协作组总路侧单元规模成线性相关。为了对这部分成本进行描述，设定成本函数：

式中，θ为维护车路协作组进行协作的成本常量。

湖口县汉族女性MTHFR C677T位点的基因型分布与尚志、乌鲁木齐、长春、涞水、银川、淄博、新乡、镇江、眉山、荆州、惠州、柳州和琼海等地差异有统计学意义(P<0.05)；MTHFR A1298C位点的基因型分布与尚志、长春、涞水、淄博、新乡、镇江、惠州、柳州和琼海等地差异有统计学意义(P<0.05)；MTRR A66G位点的基因型分布与长春、淄博、新乡、镇江、荆州和琼海等地有统计学意义(P<0.05)。

某个协作组产生的总收益更新为：

整个路网中产生收益的集合为：

3.5 时间复杂度分析

评估车路协作消息传输方法执行效率的一个重要指标是系统运行时间，在本文提出的协作方法中，主要考虑RSU 节点从一个协作组转换到另一个协作组中，完成整个路网协作组间动态调整所花费的代价。在每次调整过程中，需要判断哪些是需要进行转换的RSU 节点，如果存在需要进行转换的节点，则需要进行转换操作，直至所有符合要求节点完成转换为止，本次协作组转换工作完成，建立新的协作组。故转换次数决定了算法的执行时间。基于蚁群算法的自适应车路协作消息传输方法（ANT Control）执行时间定义为：

式中，count(ANT)为RSU 节点进行转换的次数；|R|为整体路网中RSU 节点的总数量；|E|为形成RSU 协作组的规模；time(rk,Rcopi,Rcopj)为某个RSU 从一个协作组转换到另一个协作组需要的时间，转换的时间复杂度为O(N2)；time(s)为更新的RSU节点参加过的历史协作组，时间复杂度为O(N)。

4 仿真结果

为了对本文提出的基于蚁群算法的车路协作消息传输策略（ANT Control）的准确性和执行效率进行验证，在交通仿真器SUMO 中，以本地地图选择真实地理结构构建路网，在信息传输量与路网收益等指标方面，对ANT 协作策略与非协作、联盟博弈（Coalition Formation Games，CGS）[11]和MHEMs[13]策略的性能进行对比评估。

4.1 仿真参数设定

在构建的路网中选取包含15个交叉路口的交通区域，某个时刻车流量情况如图3 所示，箭头代表此时刻路段中车流量正在行驶的方向，在SUMO中每个交叉路口均布置1 个路侧单元：为了便于仿真，假设路侧单元设置在路口中心点；设置路侧单元之间可以通过有线网络进行消息传输；车辆行驶速度依据交通流变化进行调整，初始设定RSU 通信范围为300 m，车辆通信范围为150 m，生成车辆数量分布服从泊松分布，交通流分布服从格林希尔治（Greenshiedl）模型；路网中需要传输3 种数据类型，C={c1,c2,c3}，相对应的权重为{wc1=0.9,wc2=0.8,wc3=0.5}。在仿真过程中，设定每30 s 对路网中每一条通路进行车流量数据采集，仿真获得1 000组模拟的车流量数据。

图3 某时刻仿真路网

4.2 仿真结果分析

4.2.1 初始路网固定参数对比验证

4.2.1.1 数据块传输量

在路网中，在仿真运行时间小于0.8 h时，所有策略处理数据传输量的能力基本持平，但当仿真运行时间超过1 h时，本文提出的ANT协作策略与CGS策略处理数据传输量高于其他2种策略。当运行时间超过1.3 h时，ANT 策略能够处理超过6 000 个数据块，性能优与其他策略，如图4所示。

图4 数据块传输量对比

4.2.1.2 路网RSU协作规模分析

在路网中，设置RSU 规模不超过于3 个时，每种协作策略获得的平均收益基本持平，当RSU规模超过3个时，RSU平均收益均呈现出增加趋势，在RSU规模为4～9 个时，RSU 平均收益出现波动状态，这是因为新增加路网区域中车流量相对较低而导致平均收益下降，但ANT协作策略获得的平均收益较其他协作策略高，相对于CGS 和MHEMs 策略，RSU 平均收益分别增加了7.2%和7.9%，如图5所示。

图5 RSU平均收益关系

4.2.2 路网参数变化情况下的对比验证

4.2.2.1 不同收益系数β对比

在路网中，设θ=10，pk,i=10个数据块，δ=0.8，评估收益系数β取值变化对策略性能的影响。收益系数β从0.2增加至1.0过程中，统计不同路网规模下的ANT策略的执行效率情况，如图6所示，随着β的增大，ANT策略的RSU平均收益均提高，路网中RSU数量越多，则取得收益越大。

图6 不同路网规模条件下ANT性能

4.2.2.2 不同RSU通信覆盖范围对比

设置RSU 通信覆盖距离为分别为200 m、250 m、300 m和350 m，对ANT策略执行效率进行评估，车辆通信距离设置仍为150 m，punit(V2I)和punit(V2V)取值均为3 个数据块，设β=1.0。

随着路网中RSU 规模的增加，在不同RSU 通信范围覆盖下，ANT策略整体收益均增加，但当RSU节点超过4个时，不同RSU通信覆盖范围下ANT策略产生的收益增加开始放缓。在RSU 节点达到15 个时，ANT 策略在通信范围为350 m较300 m、250 m和200 m收益分别提高了9%、26%、45%，可见随着RSU 通信覆盖范围增加，路网平均收益也在提高，但收益提升程度随着通信范围增加逐步降低，如图7所示。

图7 不同RSU通信覆盖范围ANT策略性能对比

4.2.2.3 参数δ变化对比

δ对RSU间协作通信的影响至关重要，不同参数δ条件下RSU平均收益如图8所示，设路网中RSU数量为10个，随着能够进行V2V通信车辆的比例系数提升，RSU平均收益均增加（除非合作策略），这是因为δ提升使得道路中车路间共享数据的能力明显加强，当δ＞0.4时，ANT协作策略使RSU能够获得更多的平均收益，当δ=1.0时，ANT协作策略能使路侧单元平均收益增加达到最优状态，与CGS和MHEMs协作策略相对比，分别提升了5.72%、10.88%。

图8 不同参数δ条件下RSU平均收益

4.2.3 系统运行效率分析

4.2.3.1 系统运行时间分析

当RSU 数量为15 个时，随着δ增大，ANT 与CGS、MHEMs 策略的转换次数均增加，但相较于CGS、MHEMs策略，ANT的转换次数明显低于上述2种策略，如图9所示。

图9 不同参数δ条件下RSU转换次数

设δ=0.8，不同路网规模下RSU 转换时间如图10 所示，随着路网规模增加，每种策略的RSU转换时间均增加，ANT策略在路网中RSU数量不超过7个时，转换时间低于其他2种策略，当RSU数量大于7个时，ANT策略的转换时间长于MHEMs 策略所花费时间，但仍然维持在可接受时间范围内，基本满足系统对运算时间的要求。

图10 不同路网规模下RSU转换时间对比

4.2.3.2 系统运行精度分析

建立一个能够以全遍历方式进行搜索的全局搜索策略（Global Search），与ANT策略在执行效率方面进行对比评估。在路网中设置RSU规模取值2～15个。设定每次取值，通过全遍历暴力搜索方式获取最优的RSU平均收益率为100%，ANT 策略按照实际获得收益与全局搜索策略相比较，进行百分比转换，对ANT策略性能进行评估，设置δ=0.8。执行效率分析结果如图11所示，随着路网规模的增加，ANT 策略获得RSU 平均收益呈现下降趋势，但ANT 控制策略仍高于全局搜索策略获得RSU平均收益的90%，基本满足系统性能需求。

图11 执行效率分析

5 结束语

针对车辆自组织网络中车辆高速移动以及拓扑变化快速条件下车路协作过程中车辆只能与路侧单元维持较短通信时间，限制信息传输的数量与种类的问题，本文提出基于蚁群算法的车路协作消息传输方法，将网络划分成若干个车辆通信协作组，达到提高数据传输效率，并降低通信成本的目的。由仿真分析结果可知，相对于非协作、联盟博弈方案与多级联盟划分方案，路网中RSU平均收益显著提升，提升了VANET信息传输效率。

然而，本文在理想通信条件（不存在丢包和延时等情况）下开展分析，并不能完全反映真实路网情况，因此未来将开展在无线通信环境下仍能高效运行的车辆协作控制策略设计，在趋近于真实交通环境中，提高路网中的信息传输效率。