基于中心性的路侧单元部署算法设计

The Algorithm Design for the Deployment of RSUs Based on Centrality

摘要: 本论文考虑的是郊区场景下，成本受限的路侧单元部署问题。在分析问题的过程中，引入了中心性的概念，并基于该概念，分别考虑了度中心性和中介中心性两种情况下的路侧单元部署问题。分析建模的过程中，考虑了匀速行驶的车辆在一跳的情况下的时间覆盖率问题。本论文通过仿真验证了两种中心性路侧单元部署方案的合理性，并且将仿真结果与随机路侧单元部署方案进行比较。仿真结果表明，在部署成本相同的情况下，度中心性部署的时间覆盖率比随机部署的时间覆盖率更好，中介中心性部署得时间覆盖率与随机部署得时间覆盖率差不多。

Abstract: This paper studies the deployment of road side units with limited cost in suburban scenarios. We introduce the concept of centrality and analyze the deployment of RSUs in the case of Degree-Centricity and Betweeness-Centricity, respectively. In the process of analyzing and modeling, the time coverage of vehicles travelling at a uniform speed is considered. Simulation results verify the rationality of the two kinds of deployment scheme and show that the time coverage of Degree-centric deployment is better than that of random deployment, when the time coverage of Betweeness-centric deployment is similar to that of random deployment.

1. 引言

经过100多年的历史发展，汽车更强更快了。但与此同时，化石燃料带来的环境污染问题，还有发生率居高不下的车祸问题以及高速公路节假日期间的拥堵问题等等，都是汽车工业带来的负面影响 [1] [2] [3]。若能及时得到路况信息，这些信息能辅助驾驶员规划更好的行驶路线，降低交通事故发生率，并且减少急加/减速的频率，从而提升驾驶的舒适性和安全性 [4] [5] [6]。经大量的测验表明，当车速在40~50 km/s时车辆油耗比较小 [7]，此速度下可节省化石燃料，降低化石燃料燃烧带来的负面影响，尽量保护环境。车载自组织网络可以更好地帮助我们及时得到路况信息，但是车载自组织网络的拓扑变化快、节点数目众多，这些因素都会影响路况信息的及时获取。路侧单元能够作为中继节点为车与车通信提供协助，又能独立地作为互联网接入点向网内车辆提供资源，可以大大提升路况信息的实时性 [8] [9]。只是路侧单元部署初期费用紧张，能部署的路侧单元数目有限，因此要在成本一定的情况下，选用具有较高性能的部署方案 [10]。

基于车辆密度或者城市热点等动态参数的部署方案仅仅只针对某一具体的路段或者某一具体的时间段，所以这些部署方案对于其它路段或者此路段的其它时间段而言，可能无法达到预期的结果 [11]。若能避开这些动态因素，部署方案就能适用于更多的路段。本论文引入中心性的概念，在无需道路实时动态参数的情况下，得出一种路侧单元时间覆盖率较高的部署方案。王振宇在文献中通过仿真对比，得出了基于度中心性的部署方案比基于接近中心性的部署方案 [12]。本论文在他的工作的基础上构建了基于度中心性和基于中介中心性的部署方案，并与随机部署方案进行了对比。仿真结果表明，在郊区路段中基于度中心性的部署方案更好。

2. 网络模型

本论文考虑的是郊区路段的场景。图1是江苏省常州市钟楼区的一小块卫星地图，从这张地图中可以看到白色的道路十分规整，基本上是横平竖直。本论文将此卫星图的每一个十字路口视为一个节点，节点与节点之间用线相连，将一些斜的路段规整化处理后得到图二的简化路段。

十字路口的车流量较大，所以十字路口可作为候选点。不同的车载单元的通信范围不一样，因此仅考虑一跳的情况。若两个路口间的距离大于两倍的路侧单元通信半径，从通信覆盖面考虑，将这两个路口的中心点也设为候选点。最后根据固定成本下计算得出的最大中心性的部署方案在候选点部署路侧单元。

Figure 1. Satellite map of a place in Zhong Lou area of Changzhou City, Jiangsu Province

图1. 江苏省常州市钟楼区某地卫星图

3. 中心性概念

中心性起源于社会网络的研究，通过不同的定义确定节点在网络中的重要性 [13]。车载自组织网络也可将中心性的概念引入，通过计算得出每个候选点的中心性大小，再根据不同地点的部署成本，在总成本有限的情况下，计算得出中心性最大的部署方案。

中心性有很多定义，本论文主要选择其中的两个进行研究：度中心性和中介中心性 [14]。

1) 度中心性(Degree Centrality, DC)：在无向图

$C_D\left(N_i\right)={\displaystyle \underset{j=1}{\overset{g}{\sum }}{x}_{ij}\left(i\ne j\right)}$ (1)

其中 $C_D\left(N_i\right)$ 表示节点i的度中心度， ${\text{x}}_{\text{ij}}$ 表示节点i与节点j是否联系， $x_{ij}=1$ 表示节点i与节点j有直接联系， $x_{ij}=0$ 表示节点i与节点j无直接联系。

如此测量的节点的度中心性，反映了每个节点与其它节点的关联性，但其数值大小也与节点的数目有关。为了避免节点数目对度中心性计算结果的影响，斯坦利·沃瑟曼(Stanley Wasserman)和凯瑟琳·福斯特(Katherine Faust) (1994)提出了一个标准化的测量公式：

${C^{\prime }}_D\left(N_i\right)=\frac{C_D\left(N_i\right)}{g-1}$ (2)

在这个标准化度中心性测量公式中，使用节点i的度中心性值除以其它g-1个节点最大可能的连接数，得到与节点i有直接联系的网络节点的比例。

本文采用标准化的度中心性(公式(2))来计算。度中心性越高，意味着与其直接相连的节点也就与多，有更大的概率通过更多的车辆，所以可以为更多的车辆提供服务。

2) 中介中心性(Betweeness Centrality, BC)：中介指在不同事物或同一事物内部对立的两极之间起居间联系作用的环节。中介中心性就是一个节点的联系作用的衡量标准,其计算公式：

$C_B\left(v\right)={\displaystyle \underset{s\ne v\ne t\in V}{\sum }\frac{{\sigma }_{st}\left(v\right)}{{\sigma }_{st}}}$ (3)

其中 ${\sigma }_{st}\left(v\right)$ 表示经过节点v的节点s到节点t的最短路径条数， ${\sigma }_{st}$ 表示节点s到节点t的最短路径条数，V表示所有的节点。

4. 问题描述

根据图2的网络模型，假设有N个部署候选点，令B为总成本，p(k)表示第k个路侧单元的部署成本，c(k)为第k个路侧单元的中心性，x(k)表示是否部署第k个路侧单元，部署则 $x\left(k\right)=\text{1}$，不部署则 $x\left(k\right)=0$。

优化目标： $\max \left({\displaystyle \sum x\left(k\right)\ast c\left(k\right)}\right),k\in \left[1,N\right]$ (4)

限制目标： ${\displaystyle \sum p\left(k\right)\ast x\left(k\right)}\le B,k\in \left[1,N\right]$ (5)

Figure 2. A simplified map of suburban road

图2. 郊区道路简化图

5. 基于中心性的路侧单元部署算法设计

步骤一：对各个节点初始化，给每一个节点设定坐标，再根据已知节点的坐标计算得出处于路段中间的候选点的坐标。再对每一个候选点赋一个成本值。

步骤二：随机部署路侧单元/根据公式(2)算出每一个节点的度中心性，通过动态规划求解出部署方案，部署路侧单元/根据公式(3)算出每一个节点的中介中心性，通过动态规划求解出部署方案，部署路侧单元。

步骤三：随机部署车辆，设置行驶速度和时间，得出时间覆盖率。

步骤四：绘制折线图，对比并得出结论。

具体流程图见图3。

因为不同位置的路侧单元的部署成本不一样，每个点的中心性也不一样，既要保证总中心性最大，又要使总成本在限制范围内，这和0-1背包问题是同一个类型的问题 [15]，本论文通过动态规划求解此问题。

成本a从15,000元(单个路侧单元部署成本p最低为15,000元，最小相差2500元)开始，以2500作为步进值，直到B。设 $S\left(i,a\right)$ 为部署成本为a时，部署路侧单元后，从第i到N个路侧单元候选点的最大总中心性：

$S\left(i,a\right)=\max \left(S\left(i+1,a\right),S\left(i+1,a-p\left(i\right)\right)+c\left(i\right)\right),a\ge p\left(i\right);$ (6)

$S\left(i,a\right)=S\left(i+1,a\right)\text{,}a<p\left(i\right),i\in \left[1,N\right]$ (7)

$S\left(N,a\right)=c\left(N\right)\text{,}a\ge p\left(N\right);$ (8)

$S\left(N,a\right)=0,a<p\left(N\right).$ (9)

当 $a=B$ 且 $i=1,2,3,\cdots ,N$ 时就得到了最优解。即 $S\left(1,B\right)$ 就是总中心性最大的值，此时可以从候选点1开始回溯，a从B开始降低，以2500作为步进值，当 $S\left(i,a\right)=S\left(i+1,a\right)$ 说明第i个候选点没有部署路侧单元，反之则部署，部署后将a减去p(i)继续运行。

Figure 3. Algorithm flowchart

图3. 算法流程图

算法设计程序如下：

6. 数值结果分析

本仿真基于MATLAB设计和实现，针对中心性的部署方法(Central Deployment Approach, CDA)和随机部署(Random Deployment Approach, RDA)两种方案进行比较，其中中心性部署采用度中心性(Central Deployment Approach-Degree Centrality, CDA-DC)和中介中心性(Central Deployment Approach-Betweeness Centrality, CDA-BC)作为计算依据，仿真参数设置如表1所示。基于中心性的部署方案与随机部署方案只有部署点的选择不一样，条件相同的情况下，基于度中心性或者基于中介中心性的部署方案有且仅有一种部署方法，但是随机部署每次得出的部署方法都不一样。

Table 1. Parameter setting

表1. 参数设置

扩展图2的简化后的方格里的交叉点数目，并给每个交叉点(图4中较大的圆圈)赋予相应的坐标值，其对应坐标如图4所示。横轴的坐标间隔是1000 m，这个数值可以用来判断图2中的交叉点之间的距离是否大于1000米，即是否需要增加候选部署点。在图4中，空心圆圈为十字路口，实心圆圈为带红路灯的十字路口，点为增加的路段中间的候选点。

为了较为直观的对比各个方案的好坏，引入时间覆盖率作为性能指标，时间覆盖率的定义为车辆行驶在路侧单元通信范围内的时间占行驶总时间的比值。

Figure 4. Intersection and candidate point simulation

图4. 路口及候选点仿真

图5~8是点度中心性的部署结果，黑色圆圈代表的是已部署的路侧单元的通信范围。

图5是15万成本的部署方案，几乎全选择的是中间的节点，有红绿灯的十字路口的部署费用较低且度中心性较大，因此处于中间位置的有红绿灯的十字路口都被选择了。

Figure 5. B is 150,000 yuan

图5. B = 150,000元

图6是20万的部署方案，可以看到因为成本的增加，可部署数量多了起来，这次把之前未选择的有红绿灯的十字路口也选上了。

Figure 6. B is 200,000 yuan

图6. B = 200,000元

图7是25万的部署结果，相比20万，已部署的路侧单元没有改变，未部署的候选点中有三个被选中加入，其中最上面两个新增的是剩余所有候选点中部署成本最低的。

Figure 7. B is 250,000 yuan

图7. B = 250,000元

图8是30万成本下的部署方案，可以看到通信范围覆盖了大部分地区，成本越多，效果越好。

可以看到随着部署费用的增加，路侧单元的数目也逐渐增加，但已部署的不会再次改变位置，对后期的维护和增加部署为提供了便利，在初期费用紧张的情况下，可以优先部署15万元的方案，在后续费用跟上后可以按照上图的顺序逐一增添。

Figure 8. B is 300,000 yuan

图8. B = 300,000元

图9~12是中介中心性的部署结果，黑色圆圈是已部署路侧单元的通信范围，中介指的是一个事物与其他事物联系好坏的优劣，所以中介中心性高的那个点的点度中心性不一定高，但是却是连接比较重要的两个事物的桥梁。

图9是总成本为15万元的部署方案，相比度中心性少部署一个。图10是20万的部署方案，大部分依旧集中在边缘地带，虽然和度中心性一样，也是有11个路侧单元，但是很分散，不集中。图11是25万下的部署方案，依旧是边缘较多。图12是30万的部署方案，左下角和右上角的部署单元占了绝大多数，且比30万的度中心性部署少部署一个路侧单元，资源利用不是很好。

Figure 9. B is 150,000 yuan

图9. B = 150,000元

Figure 10. B is 200,000 yuan

图10. B = 200,000元

Figure 11. B is 250,000 yuan

图11. B = 250,000元

图13是时间覆盖率与成本的关系，在成本相同下且车辆数一定的情况下(30辆车)，标准郊区路段度中心性部署优于随机部署和中介中心性部署，且随着投入成本的增加，三种部署方案的时间覆盖率都在上升，这意味着车辆行驶在路侧单元通信范围内的时间占行驶总时间的比值越来越大，车辆能与路侧单元通信的时间也相对越来越长。在30万成本下，度中心性的时间覆盖率有70%左右，这意味着此路段中，车辆在路上开一个小时，有42分钟能和路侧单元直接通信。

随机部署和中介中心性部署相差不大，原因是随机部署变化太大，取平均之后处于一个较低的水平，中介中心性则因为部署点几乎全在边缘地带，所以也不会有很好的性能。

Figure 12. B is 300,000 yuan

图12. B = 300,000元

Figure 13. The relationship between time coverage and cost

图13. 时间覆盖率与成本的关系

图14是时间覆盖率与车辆数的关系。由图14可知，在部署成本一定的情况下车辆的数目对时间覆盖率几乎没有影响，这也是因为一开始就没有考虑车辆密度这个动态参数，所以基于中心性的部署方案是具有极高的普适性的。依旧可以看出度中心性部署是三者当中最优的方案。

Figure 14. The relationship between time coverage and the number of vehicles

图14. 时间覆盖率与车辆数的关系

由于中介中心性本身的特殊性，可能不太适合这种横平竖直的标准郊区路段，所以它的表现和随机部署差不多。但是这并不意味着中介中心性不好，只是它没有遇上合适的路段。

综上所述，车辆数这个动态参数对此方案的影响不大，而且依旧是点度中心性更加适合这样纯粹的路段。

7. 总结

本论文主要针对的是路侧单元在标准郊区路段上的部署问题，在前人得出度中心性比接近中心性好的基础上，加入中介中心性部署，将其与度中心性进行比较。中心性的计算基于动态规划，结合简化的实际场景，在固定成本下进行分析对比。仿真结果显示，成本一定的情况下，度中心性部署的时间覆盖率明显优于中介中心性部署，中介中心性部署则和随机部署相差不大。不论是哪种部署方式，车辆数对时间覆盖率的影响都微乎其微。这证明这种部署方式的普适性高，较为容易推广。今后的工作可以考虑将特征向量中心性加入计算，依旧和度中心性进行同类型仿真对比，研究相应的路侧单元部署方法。

基金项目

国家自然科学基金(No. 61901196)，江苏省高等学校自然科学研究面上项目(No. 19KJB0026)，江苏理工学院人才引进项目(No. KYY18008)，2020年江苏省省级大学生实践创新训练项目省级重点项目(No. 90100021934-3)。

NOTES

^*通讯作者。