基于车辆移动相似性的VANETs 簇群算法*

袁小艳 许晓红

（四川文理学院智能制造学院 达州 635000）

1 引言

车联网（Vehicular Ad Hoc Networks，VANETs）已成为智能交通系统（Intelligent Transportation System，ITS）的重要组成部分［1~3］。通过VANETs 可实现多类应用，如车间信息传输、协作驾驶、紧急消息传输等。然而，这些应用的实现是建立于良好的通信网络。目前，主要存在两类通信协议标准：专用的短距离通信（Dedicated Short-range Communication，DSRC）［4］和C-V2X［5］。DSRC 只能实现短距离通信，相比下，C-V2X 通信通过借助于4G 和5G 无线通信网络，能够实现大范围的通信覆盖和高速率。

然而，车辆的高速移动以及障碍物导致网络呈间歇性连通，增加了网络接入的不稳定性，容易丢失数据包。簇群技术是提高数据传输成功率的有效策略。将道路上的车辆划分为簇，每个簇产生一个簇头（Cluster Header，CH），簇内其他车辆称为本簇的簇成员（Cluster Members，CM）。CH 收集本簇内的CMs的车辆数据。

由于车辆的高速移动，构建稳定的簇群是一项具有挑战性的任务。文献［6］利用5G 的基站（gNB）形成簇，并利用多项指标构建CH。但是由于拥塞以及非视距环境，基站不能与多个车辆通信。文献［7］提出基于车间距离因子的构簇算法。但是，由于车辆的高速移动，车间距离可能一直在变化，这增加了构建簇的频率。文献［8］提出基于Q-学习的构建簇算法，进而减少gNB 的开销。但是该算法在每个簇内形成多个CHs，这增加了算法本身的复杂性。同时，在进行Q-学习时需要训练数据，这增加处理时延。文献［9］提出基于飞蛾扑火算法（Moth-Flame Optimization，MFO）为车辆构建虚拟的网格。但是该算法旨在优化簇数，没有讨论网络的性能。

综上所述，目前缺乏从网络连通性角度，构建自适应的簇群技术。为此，提出基于车辆移动相似性的簇群（Compatibility of Vehicle Mobility-based Clustering，CVMC）算法。CVMC算法先通过基站接收车辆的信号强度决策一个车辆作为簇头，再依据车辆离基站的距离、车辆间相对速度以及车辆间重叠的路段计算车辆间的移动相似性，再利用车辆间的移动相似性形成簇。仿真结果表明，提出的CVMC算法有效地提升吞吐量。

2 CVMC算法

2.1 网络模型

车联网主要由车辆、gNBs 构建，如图1 所示。每辆车上安装一个OBU［10］。每个OBU 配备了双重收 发 器：1）基 于802.11p 的DSRC 或 者 是3GPP C-V2X；2）4G 或者5G。车辆通过OBU 与其他车辆、gNBs进行通信。

图1 系统模型

每辆车中的OBU 具有防攻击设备（Tamper Proof Device，TPD），存储相关的数据。在VANETs中，车辆通过交互Beacon 包与其邻居节点交互信息，进而获取邻居车辆的信息。

此外，路边单位（Road-Side Units，RSUs）或者是5G 的eNBs 作为基站gNBs，它们能够传输蜂窝信号，并且它们之间通过高速的X2链路连接。

假定系统中有n辆车，它们构成车辆集V={ϑ1，ϑ2，…，ϑn} 。令Dij表示车辆ϑi与车辆ϑj间的欧式距离：

式中：(xi，yi)、(xj，yj)分别表示车辆ϑi、ϑj的位置坐标。

2.2 车辆间的相似性

为了计算车辆间的相似性，对车辆连通目的节点道路进行分段划分。令Sgi表示车辆ϑi所在路段的分段，假定分割成q个等间隔的路段。且如图2 所示，车辆ϑk离其目的地的道路被划分为3 段（q=3），即Sgk=

图2 车辆路段划分示例

将每辆车通往目的地的路段进行分段后，相邻车的路段存在重叠。为此，将整个路段进行编号sg_id_*，其中“*”表示编号。如图2 所示，对整个路 段 进 行 从A、B、C 至G 的 编 号，即{sg_id_A，sg_id_B，sg_id_C，sg_id_D，sg_id_E} 。

接下来，计算两辆车在通往目的地的重叠路段，用Ni，j=Sgi∩Sgj表示车辆ϑi与车辆ϑj的重叠路段集。例如，如图2 所示，车辆ϑj与车辆ϑk间的重 叠 路 段 为Nk，j=Sgk∩Sgj={sg_id_D，sg_id_E，sg_id_F}。

如果两车辆间的重叠路段数超过预定阈值Sgth，则认为它们间的移动存在相似性。为此，引入布尔变量Fij。如果车辆ϑi与车辆ϑj间重叠路段数大于Sgth，则Fij=1，否则为零：

接下来，计算两辆车间的移动相似性。令SMi，j表示车辆ϑi与车辆ϑj间的移动相似性，其定义如式（3）所示：

式中：0 ＜Dij＜R限定两辆车在彼此的通信范围内；Δνij表示车辆ϑi与车辆ϑj间相对速度，其定义如式（4）所示。

从式（3）的定义可知，车辆间距离越小、相对速度越小，它们间的相似性越大。

2.3 簇头及簇形成

每个车辆周期Beacon 包，向gNB 传输报告它自己的位置以及速度等信息。gNB 依据接收的Beacon包消息的信号强度，选择具有最大信号强度（Received Signal Strength，RSS）的车辆作为簇头：

式中：RSSϑ1表示车辆ϑ1的信号强度值RSS。

一旦选举了簇头后，簇头就向邻居节点传输通告消息Mes_CH。其他节点接收Mes_CH 消息，计算与簇头的间移动相似值。如果与簇头间的移动相似性低于阈值SMth，则车辆就直接与gNB 通信。若大于阈值SMth，车辆就从中选择具有最大移动相似性车辆作为自己簇头，并向该簇头发送确认消息Mes_ACK，如算法1所示。

算法1：簇形成过程

if 如果车辆不是簇头

接收到Mes_CH 后，车辆就依据式（3）计算与簇头的移动相似性

ifSMi，j小于阈值SMththen

车辆就直接与gNB直接通信

else

车辆就从中选择具有最大移动相似的簇头作为自己的簇头，并向其传输Mes_ACK。

end if

else

传输消息Mes_CH

接收消息Mes_ACK

end if

图3 给出基于车辆移动相似性的簇群模型。依据车辆位置以及它们移动速度的相近性构建簇。图中灰色实线范围表示一个簇群，而不是深色实线范围。从理论上讲，考虑了车辆移动速度的相近性所构建簇群稳定性更好，由于车辆以相近的速度移动以及位置相近，它们能够保持更好的连通性，链路持续时间更长。

图3 基于车辆移动相似性的簇群示例

3 基于簇的接入信道性能分析

由于蜂窝网络采用正交频分多址接入技术给C-V2X 用户分配资源，需采用随机接入信道方式进行信道竞争。因此，gNBs 以随机方式给用户分配资源。

假定总共有k个车辆同时向gNBs请求M 个资源。若没有簇群技术，车辆能够获取资源的概率为

采用簇群技术可以减少接入上行链路的资源的车辆数。假定 ||Ci表示簇群的平均车辆数，则车辆接入资源的概率提升为

4 性能分析

4.1 仿真环境

在Windows 7 操作系统、8GB 内存，core i7 CPU的PC 上进行实验仿真。采用SUMO 软件［11］建立城市车辆移动轨迹数据，仿真区域为300 m×1500 m，车辆数从50~500变化。

在网络层选用按需矢量距离（Ad-Hoc On-Demand Distance Vector，AODV）［12］路由传输数据，并选用LENA mmWave 模块，并考虑Friss 传播模型［13~14］。道路参数：40 个交叉路口，最大车道数为3，每个车道宽不超过50m，如图4所示。

图4 SUMO道路拓扑

每辆车采用20dB 的传输功率，传输范围为145m，具体的仿真参数如表1所示。

表1 仿真参数

4.2 阈值Sgth 对数据包传递率的影响

考虑两类情况：Sgth=5 和Sgth=2 。Sgth越大，簇的稳定性以及连通性越好，而Sgth越小构建簇的频率越高。图5（a）显示了车辆数和Sgth对数据包传递率的影响。从图可知，CVMC 算法的数据包传递率在80%至91%。此外，车辆数的增加对数据包传递率的影响并不大。

但是，车辆速度对数据包较大影响，如图（b）所示。当车辆随机速度在50m/s~60m/s，CVMC 算法的数据包传递率达到91%。然而，车速的增加降低了数据包传递率。此外，从图5 可知，Sgth的增加提升了数据包传递率，这符合预期。

图5 Sgth 对数据包传递率的影响

4.3 性能对比分析

选择文献［8］提出的两层簇算法（Two-Level Cluster Algorithm，TLCA）和文献［6］提出的多跳移动区域算法（Multi-hop Moving Zone Clustering，MMZC）作为参照。分析车辆数和车速对CVMC 算法、TLCA 算法和MMZC 算法的吞吐量影响，如图6、7所示。

图6 车辆数对吞吐量的影响

如图6 所示，当车辆数为100 时，CVMC 算法的吞吐量达到11 Mbps，而TLCA 算法的吞吐量达到约12 Mbps。但是当车辆数增加至200 时，TLCA 算法的吞吐量迅速下降。当车辆数增加至500 时，TLCA 算法的吞吐量下降至4 Mbps，而CVMC 算法的吞吐量仍达到8 Mbps。幸运的是，CVMC 算法的吞吐量随车辆数的增加保持较稳定的性能。

相比于CVMC 算法和TLCA 算法，MMZC 算法的吞吐量最低。在车辆数为100 时，MMZC 算法的吞吐量只有8 Mbps。而当车辆数增加至500，MMZC算法的吞吐量只有1 Mbps。

图7 给出车速对吞吐量的变化情况。从图可知，车速的增加降低，使吞吐量呈下降趋势。原因在于：车速越快，车间通信链路的持续时间越短，这不利于数据包的传输。此外，相比于TLCA 算法和MMZC 算法，CVMC 算法的吞吐量仍保持较高的水平。这归功于：CVMC 算法利用车间移动相似性构建簇，提高了簇的稳定性。

图7 车速对吞吐量的变化情况

5 结语

本文针对车联网中的构簇算法，提出车辆移动相似性的簇群CVMC 算法。CVMC 算法充分利用车辆的移动信息，通过计算车辆在道路中移动行为，构建簇，提高簇的稳定性。仿真结果表明，相比于MMZC 和TLCA 算法，提出的CVMC 算法的吞吐量提高了近2Mbps~4Mbps。

本文考虑的仿真场景较为简单。后期，将考虑更为复杂场景，使提出的CVMC算法能够应用于真实场景，这将是后期的研究工作。