¹杭州电子科技大学电子信息学院，浙江 杭州

²杭州云动智能汽车技术有限公司，浙江 杭州

收稿日期：2020年11月28日；录用日期：2020年12月23日；发布日期：2020年12月30日

摘要

路侧单元(Road-Side Unit, RSU)作为连接车辆和外部网络的桥梁，是车联网通信中的核心部分之一，设计合理的RSU部署方案对于充分发挥其单元效益在车联网中十分重要。本文首先通过将自适应t分布引入到蝙蝠算法中，并在算法迭代过程中加入了灾变机制，从而提出一种改进的蝙蝠算法，能够快速收敛到最优解；随后将改进蝙蝠算法应用到路侧单元的部署中，仿真结果表明该方法能够快速收敛到最优部署效益，具有较好的性能。

关键词

车联网，路侧单元，部署问题，蝙蝠算法

Research on Optimization Method of Roadside Unit Deployment in Internet of Vehicles Based on Improved Bat Algorithm

Keqiang Yue¹, Chaohong Lu², Wei Li²

¹College of Electronic Information, Hangzhou Dianzi University, Hanzhou Zhejiang

²Hangzhou Yundong Smart Automobile Technology Co., Ltd., Hanzhou Zhejiang

Received: Nov. 28^th, 2020; accepted: Dec. 23^rd, 2020; published: Dec. 30^th, 2020

ABSTRACT

Road-side unit (RSU) is one of the core parts of communication mode in internet of vehicles. As the bridge connecting vehicles and external networks, it is very important to design a reasonable RSU deployment scheme to give full play to its unit efficiency in the internet of vehicles. In this paper, an improved bat algorithm based on self-adaptive t-distribution and catastrophe mechanism was proposed. In the proposed algorithm, self-adaptive t-distribution adopted to improve convergence speed and catastrophe mechanism in the algorithm iteration process introduced to increase bat population diversity. Then, the improved bat algorithm is applied to the deployment of roadside units. The simulation results show that the proposed method can quickly converge to the optimal deployment benefit and has good performance.

Keywords:Internet of Vehicles, Road-Side Unit, Deployment Problem, Bat Algorithm

Copyright © 2020 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

随着经济的快速发展，汽车占有量的增长导致城市交通拥堵已成为越来越严重的社会问题。车联网是作为智能交通核心内容之一，由车辆位置、速度和路线等信息构成的巨大交互网络，通过车与车、车与路侧单元等方法直接通信来完成信息交互，能有效解决这一问题 [1]。车辆自组织网络通过车联网内的车辆节点与外部网络进行信息的传输，是车联网重要的研究内容，通常由车载单元和路侧单元组成。而路侧单元是实现车辆节点与外部网络的信息传输枢纽，安装成本非常昂贵，需要合理规划其安装数量及路网位置 [2]，从而保障车辆自组网整体具有高效的通讯效率。

在车联网部署初期阶段，通常以车辆是否处于无线通信覆盖范围内作为效益依据，根据路网中的各路段的车辆密度、所处区域特性、车道数等综合确定路段的权重密度实现路侧单元的部署，但存在以车辆节点为对象的覆盖收益具有高度时空动态性和不确定性问题 [3]。Kim等人 [4] 提出新的RSU部署框架，将RSU部署在静态位置，公共移动交通和地方政府所属的车辆上进行均衡，使在一定成本下，实现覆盖的最大化。文献 [5] 中提出根据道路网络的模型采用不同的部署方式，均匀部署用于道路网络几何形状规则的区域，热点部署主要是用于交通密集区域，但是这种部署不能得到精确的最优方案。文献 [6] 针对路侧单元部署提出分析框架，考虑了车辆数据流量的随机性和中断通信信道的统计变化，以保证路侧单元的分组传送延迟限制在一定范围内。然而，现有的关于RSU部署工作的研究主要是优化数据传输时延、RSU覆盖率和RSU部署费用等，以提高网络的性能，但是RSU会受到候选部署点集合、交通特征、道路特征等诸多因素的影响 [7]。通过将路侧单元部署问题模型转化为搜索最优解问题，使用智能优化算法来求解是当前的研究热点。在给定路侧单元数目约束下，以提高连接时间和降低断连时间为目标，由于贪心算法思路简单，易于实现，文献 [8] 关于部署路侧单元的工作将贪心算法作为寻优的部署算法，但是贪心算法在多数情况下无法收敛到全局最优解路；利用遗传算法的选择、交叉和变异三种操作来模拟生物群体的进化过程，能有效提高算法的寻优能力，Manipriya [9] 等提出了利用ORTT模型，通过遗传算法能够找到最优的路侧单元部署位置，并且保证耗费最少成本，但是遗传算法容易陷入局部最优，Lin等 [10] 研究了路侧单元和传感器在双车道环境下的混合部署问题，在保证路侧单元与传感器在道路上能提供满足条件的连接服务同时满足的情况下，提出了改进的粒子群算法来解决混合部署问题，但PSO当遇到病态函数或者复杂多峰函数时，难以保证继续收敛到最优解。蝙蝠算法(Bat Algorithm, BA)模拟自然界中蝙蝠利用一种声纳来寻找猎物和避免障碍物的生物学特性，具有并行性、分布式和收敛速度快等特点 [11]，已经广泛应用于工程设计、分类等领域。本文首先通过将自适应t分布 [12] 引入到蝙蝠算法中，并在位置和速度的更新中加入了灾变机制，提出一种改进的蝙蝠算法，改进算法大大提高了收敛速度和效率，能够快速收敛到最优解；随后将改进蝙蝠算法应用到路侧单元的部署中，结果表明该方法能够逐步逼近最优部署效益，提高了算法的效率。

2. 路侧单元部署模型

路侧单元是车联网中能与OBU通信的网络基础设施，如何在网络内合理地规划路侧单元的部署位置和数量，已经成为车联网研究的热点问题。对于距离较长的高速公路路段，完全覆盖的RSU部署方案是不合理的，会增加部署RSU的总体成本，同时对于车辆密度较小、车速较快的区域，不需要部署过多的RSU，会造成RSU资源的浪费。RSU部署方案就是在保证网络服务质量满足限制的前提下尽量降低部署RSU的数量，部署问题可以表示为 [3]：

$\{\begin{array}{l}\min {\displaystyle \underset{i=1}{\overset{K}{\sum }}{X}_i}\hfill \\ \text{s}\text{.t}\text{.}{X}_i\in \left\{0,1\right\},\forall i\in \left\{1,2,\cdots ,K\right\}\hfill \\ {\displaystyle \underset{i=1}{\overset{K}{\sum }}{X}_i{C}_i^s\ge C_{\min }}\hfill \\ Y_i^s=1,\text{if}{X}_i=1\text{and}{Y}_i^j\ne 1,\forall j\in S_i-s\hfill \end{array}$ (1)

式(1)中 $X_i$ 为二进制数字串，共有K个元素，每个元素只有两个取值：0或者1。当 $X_i=1$ 表示在第i个子路段中部署一个RSU； $X_i=0$ 则表示不部署RSU。同时式(1)中约束了部署RSU问题的解需要保证整个系统的网络服务质量满足最低限制，不满足最低限制的部署方案是不被接受的。 $Y_i^s=1$ 表示子路段中存在汽车s与RSU进行通信，前提是当前已经部署了RSU； $Y_i^s=0$ 表示没有车辆与RSU通信； $S_i$ 表示第i个子路段中所有汽车的集合，同时式(1)中设定当前子路段中如果汽车s与RSU进行通信，则不会在存在任何除汽车s以外的汽车j与RSU进行通信。

3. 基于改进蝙蝠算法的路侧单元部署研究

3.1. 基本BA算法

由Yang教授于2010年提出的蝙蝠算法 [11] 是一种启发式的群体智能算法，每只蝙蝠为搜索解空间的一个点，由适应度函数来决定蝙蝠位置的优劣。蝙蝠个体的每一次有效飞行就是BA算法的一次迭代更新。蝙蝠的位置和速度更新如下式(2)：

$\{\begin{array}{l}{f}_i=f_{\min }+\left(f_{\max }-f_{\min }\right)\beta \hfill \\ v_i^t=v_i^{t-1}+\left(x_i^t-x^{*}\right)f_i\hfill \\ x_i^t=x_i^{t-1}+v_i^t\hfill \end{array}$ (2)

式中： $f_i$ 是第i只蝙蝠个体所发出的脉冲频率，且 $f_i\in \left[f_{\min },f_{\max }\right],\beta \in \left[0,1\right]$，是均匀分布的随机向量。对于当前的局部搜索区域来说，随机选取个体按下式(3)进行最优解扰动：

$X_{new}=x^{*}+\epsilon A^t$ (3)

式中： $\epsilon$ 为 $\left[-1,1\right]$ 上的随机数值， $A^t$ 为在时刻t所有蝙蝠个体的平均响度。当发现猎物的时候，蝙蝠个体则降低脉冲响度和增加脉冲频度。在BA算法中，响度 $A_i$ 和脉冲频度 $r_i$ 按下式(4)进行更新：

$\{\begin{array}{l}{A}_i^{t+1}=w{A}_i^t\\ r_i^{t+1}=r_i^0\left[1-\exp \left(-\gamma t\right)\right]\end{array}$ (4)

式中： $r_i^0$ 表示初始脉冲频度。 $\gamma$ 是发射脉冲频度增加的系数， $\omega$ 是脉冲响度衰减系数，两者都为常数，其中， $0<\omega <1$，$\gamma >0$。

3.2. 改进蝙蝠算法

基础蝙蝠算法的搜索区域单一，缺乏有效方法保持种群的多样性，搜索性能较差 [13]，需要对蝙蝠算法进行改进以提高搜索性能。文献 [12] 在粒子群算法中引入余弦时变来改进粒子群算法，在加速系数和惯性权重的基础上依据迭代次数t的变化来进行权重的迭代，使得算法保持了粒子群种群的多样性，具有良好的全局探索能力。本文中通过将余弦时变控制权重更新的方式引入蝙蝠算法中，通过余弦时变的作用，有助于算法跳出局部最优。为了更好地平衡时变加速系数在全局和局部的搜索能力，有效控制蝙蝠算法全局搜索和快速收敛到全局最优解，提出一种余弦时变加速系数：

$\eta =b+A\times \cos \left(\frac{t\pi }{T}\right)$ (5)

其中，t为当前迭代次数；T为总迭代次数；b和A为设定值用于控制全局搜索和快速收敛到全局最优解。对于蝙蝠算法中个体，为了避免算法陷入局部最优而无法跳出的情况，使用余弦时变对最优解进行扰动，帮助其跳出局部最优值，收敛到更优的解，如下式(6)所示：

$x_{new}=x^{*}+\eta A^t$ (6)

灾变机制是模拟自然界生物进化过程中，对于不能适应环境的种群进行消亡，重新产生新的种群来改变种群的多样性。本文中对于蝙蝠种群选择一定规模的蝙蝠个体进行消亡操作，使其跳出局部最优解，开始进行新的搜索。具体操作是：在算法迭代过程中，每隔固定周期对群体进行一次扰动，选择适应度函数最差的4个蝙蝠个体进行灾变操作，将灾难发生的个体进行清零操作，并随机植入优良个体。引入的灾变机制，改变了群体多样性，取得了较好的全局搜索效果。

3.3. 改进蝙蝠算法在路侧单元中的应用

将改进的蝙蝠算法应用于路侧单元的部署，选择路侧单元优化部署函数式(1)作为改进蝙蝠算法的适应度函数，基于改进的蝙蝠算法的路侧单元部署优化基本执行步骤如下：

1) 初始化种群。针对改进的蝙蝠算法随机初始化元胞的速度v、位置x、发射脉冲频率f，并给定初始脉冲频度 $r_0$ 和脉冲响度 $A_0$ ；

2) 依据式(1)计算所有蝙蝠个体的适应度值 $Fitness\left(i\right)$，所示的适应度评价函数可以计算出每一个部署方案对应的所需部署的RSU总数，记录下全局最优解 $x^{*}$ 和其对应的适应度值 $f\left(x^{*}\right)$ ；

3) 产生随机数 $rand1$，通过条件 $rand1>r\left(i\right)$ 来判断是否进行最优解扰动来产生新解，其中 $r\left(i\right)$ 为当前蝙蝠个体发出脉冲的频度。如果满足条件，则根据公式(2)和(7)产生局部解替代当前解，并更新并替换当前适应度值。如果不满足则跳过该步。

4) 产生随机数 $rand2$，如果更新后的蝙蝠个体i的适应度值 $F_{new}$ 和发射脉冲的响度 $A\left(i\right)$ 满足条件 $F_{new}<Fitness\left(i\right)\&rand2<A\left(i\right)$，则接受该新解。替换个体原来的位置状态并根据式(3)开始脉冲响度A和发射脉冲的频度r更新。如果不满足条件，则比较 $F_{new}$ 与 $Fitness\left(x^{-}\right)$ 的大小，若满足 $F_{new}<Fitness\left(x^{-}\right)$，则接受该新解替代 $x^{-}$，否则跳过该步。

5) 如果接受的新解满足 $F_{new}<f\left(x^{*}\right)$，则替换全局最优解 $x^{*}$ 和其对应的适应度值 $f\left(x^{*}\right)$。

6) 在满足种群持续 $fspNum$ (最大迭代间隔)次迭代没有产生新的全局最优值的情况下，通过灾变的方式对当前种群中质量较差的个体进行灾变，当新解优于原先解时，替换原先解并替换原先适应度值。

7) 重复步骤(2)~(6)，直至满足最优解要求的精度或达到最大迭代次数，当满足要求后输出全局最优解以及其对应的最小适应度值。

4. 系统仿真与结果分析

为了验证改进蝙蝠算法在路侧单元部署中的性能，在MATLAB环境下进行仿真。仿真高速公路RSU部署问题，仿真参数如 [3] 设置方式，实验采用VanetMobisim模拟生成的车辆轨迹数据，设定需要部署RSU的高速公路路段的长度为3 km，一共有500辆汽车在这一路段行驶，每一辆车的行驶速度在60 km与100 km/h之间，设定每一辆汽车与RSU的通信半径均为100 m。并与GA算法 [9]、PSO算法 [10]、IDCS算法 [3] 的求解结果进行对比分析。改进蝙蝠算法蝙蝠个体总数为20，搜索脉冲频度范围 $\left[0,2\right]$，最大脉冲频度 $r=0.5$，最大脉冲音强 $A=0.25$，脉冲频度增加系数 $\gamma =0.9$，脉冲响度衰减系数 $\alpha =0.9$，最大迭代间隔 $fspNum=10$。

为验证本文算法所提算法在高速场景RSU部署效果，仿真了本文算法与对比文献的算法在解决RSU部署中问题的收敛速度，图1给出了4种算法的迭代次数与RSU部署数量的关系曲线图，图中算法最大迭带次数设置为200次。

图1. 迭带次数与RSU数量关系曲线

由图1可知，随着迭带次数增加，四种算法都能够收敛，但是每种算法收敛的速度和得到的最优解不同。GA算法在180次完成收敛，取得最优解；PSO算法在第190次完成收敛，取得算法的最优解；IDCS 算法在160次完成收敛，取得最优解，本文算法在140次完成收敛，取得最优解。由图可知，本文所提IBA算法取得的收敛速度优于其他算法，能够在较少次数下实现快速收敛。

图2给出了四种算法在不同公路长度下，部署方案需要的RSU数量对比图。从图中可以看出，随着公路长度的增加，四种方案下的部署RSU数量均增加，其中GA算法增加的速度最快，需要的RSU数量最多，基于本文所提的IBA算法的部署方案所需的RSU数量更少，表明该算法具有良好的性能和适合解决高速公路场景下的RSU部署优化问题。

图2. 公路长度与RSU数量关系曲线图

路段覆盖率是衡量部署方案有效性的指标，是部署方案性能的直接体现，定义为RSU部署的有效覆盖面积与RSU的部署的总面积的比值。本文仿真了四种算法的RSU数量与覆盖率之间的关系曲线图如图3所示。

图3. RSU数量与有效覆盖率关系曲线图

由图3可知，四种算法的RSU覆盖率都会随着RSU数量的增加而增加，这是因为随着RSU部署数量的增加，更多的路段被覆盖，提高了路段的覆盖率；同时本文算法的路段覆盖率最高，这是因为随着RSU增加，RSU之间的重复覆盖路段也逐渐增加，本文算法能够有效提高部署增益，从而取得了较好的效果。

5. 总结

车联网是作为智能交通核心内容之一，能有效解决城市交通拥堵问题。车联网中路侧单元部署问题是车联网的重要研究内容，早期车联网部署通常以车辆是否处于无线通信覆盖范围内作为效益依据，当前用智能优化算法来解决部署问题是当研究热点。本文首先提出一种改进的蝙蝠算法，通过将自适应t分布和灾变机制引入到蝙蝠算法中；随后将改进蝙蝠算法应用到路侧单元的部署中，并仿真了路侧单元部署效率、覆盖率与路侧单元数量的关系，结果表明所提算法方法能够逐步逼近最优部署效益，具有较好性能。

基金项目

论文得到浙江省重点研发计划项目(项目编号：2019C01070)资助。

文章引用

岳克强,卢朝洪,李 巍. 基于改进蝙蝠算法的车联网路侧单元部署优化研究
Research on Optimization Method of Roadside Unit Deployment in Internet of Vehicles Based on Improved Bat Algorithm[J]. 计算机科学与应用, 2020, 10(12): 2354-2360. https://doi.org/10.12677/CSA.2020.1012249

参考文献