2. 中南大学 地球科学与信息物理学院, 长沙 410083;
3. 清华大学 电子工程系, 北京 100084
为了有效提高网络性能, 基于车载移动数据研究了真实城市环境下的路边单元(RSU)部署问题, 收集并记录了基于北京市的车载移动数据集, 通过差值方法等对车辆轨迹数据进行了预处理, 使得该数据成为研究RSU部署策略的重要支持.基于真实的移动数据, 提出了综合考虑中心性和均匀性的RSU部署算法, 以优化网络整体性能.以真实车载移动轨迹为基础的仿真实验结果表明, 所提出的RSU部署算法可以有效提升网络性能.
2. School of Geosciences and Info-Physics, Central South University, Changsha 410083, China;
3. Department of Electronic Engineering, Tsinghua University, Beijing 100084, China
Vehicular Ad hoc networks (VANETs) have been attracted attentions to the research area for solving the increasingly serious problem of traffic congestion as well as the improving road safety. Besides vehicles with communication capabilities, VANETs also include infrastructure such as roadside units (RSU) which serves as access points. RSU plays animportant role invehicle-to-infrastructurecommunication. The deployment strategies of RSU are critical and should be carefully studied in VANETs. In order to effectively enhance the network performance, the RSU deployment problem was studied under the realistic vehicular mobility traces. A large scale urban vehicular mobility traces in Beijing has been collected, and the method of interpolation has been used to preprocess the traffic traces collected in Beijing; a new RSU deploymentalgorithm that considering both the centricity and uniformity was proposed to deploy RSU in VANETs to optimize the total performance of the network. Realistic vehicular mobility trace-driven simulation experiments show that the new algorithm caneffectively enhance the network performance.
车载通信网络被视为提高道路安全性和建设智能交通系统的关键技术.在车载网络中, 车辆和车辆之间的通信称为V2V(vehicle-to-vehicle), 而车辆和类似路边单元(RSU, roadside units)这样的基础设施间的通信称为V2I[1](vehicle-to-infrastructure).由于V2V通信通常具有较大的机会性和随机性[2], 车辆与RSU间的V2I通信对提升网络性能具有更加重要的作用.在RSU辅助的车载网络中, RSU通常部署在道路两旁[3], 沿着道路行驶的汽车可以与RSU建立更加稳定的连接来传输数据. RSU与车辆间的机会接触可以为数据传输提供高带宽的通信能力, 这也称作一种车载机会网络[3-4].在这种机制下, 如果RSU不能和车辆传送数据, 车辆会将数据先存储到本地缓存中, 带着数据行驶, 然后当出现可用的传输机会时再将数据传递给合适的RSU, 这也称作一次通信接触[4].
目前, 在RSU辅助车载网络中存在很多挑战和开放性问题.例如, 如何在考虑车辆交通状况和城市道路结构的基础上部署RSU[2].由于所部属RSU的能力和数量直接决定了车载网络可以提供的通信容量和服务水平, 所以RSU的部署对整个网络的性能具有重要影响.然而, 部署大量的RSU来提供更高的通信能力会带来极大的设施成本, 所以RSU的部署策略应该依据车载网络的需求而定.因此, 如何结合车辆移动规律和道路结构来对适量的RSU进行部署具有重要的研究意义.
一种旨在提升车载网络协议可扩展性的车载混合网络架构[5]与网状网络的架构很相似, 但是其中的场景仅限于一条简单的高速路, 部署问题也因此简化为依据车辆密度来决定接入点间的距离问题.黄晓敏等[6]提出了结合车辆运动模式和数据业务传输特点的车联网链路传输性能评估模型, 该模型能有效评估不同路由协议建立链路在不同移动速度下传输数据业务的能力, 但是并没有对RSU的部署问题进行研究.因此, 笔者研究了如何结合真实车辆移动规律和道路结构来对适量的RSU进行部署, 对北京市主要交通路口的车流量进行了统计, 提出了一种在中心性与均匀性中寻找平衡的算法, 同时考虑了部署位置的车流量和与其他已部署RSU之间的位置关系.采用了北京市密集地区的数据对算法进行了仿真验证, 并分别研究了中心性和均匀性对网络性能的影响.仿真结果表明, 提出的综合考虑中心性和均匀性的RSU部署算法对车载网络的整体性能有较大的提高.
1 数据收集与预处理1.1 数据集为了使研究具有更大的真实性和实用性, 采用真实数据进行车载机会网络中的车辆移动规律研究, 并使用真实车辆移动轨迹进行仿真实验.使用北京市车辆移动轨迹数据来作为数据集, 样本量很大.实验中使用了北京市2010年5月份一个月在27 000辆北京出租车上的行踪纪录, 这些出租车都配备了GPS接收器.在车辆行驶中使用GPS设备收集出租车的位置信息和对应的时间信息, 并采用GPRS模块将移动中的车辆数据每隔一个时间间隔(如10 s)对基站进行报告.每份报告包含的具体信息有出租车编号、出租车位置的经纬度坐标、数据发送时间、出租车当天的行驶速度及行驶方向，具体数据格式如表 1所示.
|
表 1 北京市车载数据集的数据格式 |
为了得到较为精确的车辆移动轨迹并方便进行接下来的计算和仿真, 需要采集每辆车每隔一个固定时间间隔的位置数据.由于存在车辆停止时不发送数据、数据发送过程中可能会丢失或出错、GPS定位可能不准确、不同车辆发送起始时间不相同等因素, 收集到的原始数据往往不连续.因此在使用数据前, 需要对数据进行预处理.预处理的第1个部分即为一个识别错误数据的过程.在预处理的第2个部分采用线性插值法来生成所需的特定时间点的数据.为了得到某个特定时刻的车辆位置, 线性插值法利用与该时刻前后相邻的2个数据采样点的位置进行线性插值.
插值时认为在前后相邻2个基准采样点间车辆进行匀速直线运动, 假设车辆在t1时刻对应的基准采样点的位置为l1, 在t1后紧邻的t2时刻对应的基准采样点的位置为l2, 该车辆在t时刻(t1＜t＜t2)的位置为
|
(1) |
处理实际数据时将第1个采样点设为第一日的0点, 然后每隔一个时间间隔(如10 s)使用插值法确定一个数据点.由于需要研究车辆的运动规律, 所以对于车辆长时间停车的情况(如出租车收车停在停车场)需要进行排除.将停车分为2种情况:假设所有停车时间超过10 min的情况为长时间停车, 不进行插值; 而停车时间小于10 min的情况为短时间停车(如出租车路口停车或上下客人), 将短时间停车视为车辆运动的一部分, 并会进行插值.由于长时间停车不进行插值, 所以最后得到的数据将会由多段时间上不连续的轨迹组成, 每段轨迹之间有一次长时间停车.插值前后的对比情况如图 1所示.
|
图 1 对北京市数据进行插值前后的示意图 |
图 1中的横向箭头代表时间轴, 每个竖向箭头代表一个数据点, 插值前相邻2个数据点间隔为15 s, 若有数据丢失或损坏、长时间停车或者短时间停车将可能造成数据点中断, 间隔将大于15 s; 插值后相邻2个数据点间隔为10 s, 保留长时间停车(但会将长时间停车时间变为10 s的整数倍), 并补全缺失数据点和短时间停车数据点.
为了验证轨迹的合理性, 将插值后的数据点进行绘制(见图 2)并与北京市的真实地图(见图 3)进行对比, 可以发现由插值后数据点组成的轨迹与真实地图中的道路十分匹配, 这说明插值后的数据具有较好的精确度与实用性.
|
图 2 插值后数据点绘图 |
|
图 3 北京市四环内道路图 |
将RSU部署的目标确定为提升服务可达性与连接规律性.每个RSU相对于整个网络的位置以及其相对于其他部署RSU的位置这2个主要因素将有助于实现上述目标.第1个因素通过研究RSU位置的中心性来进行探究, 第2个因素则反映了RSU分布的规律性, 可被理解为均匀性.
2.1 问题建模下面选取了北京市主要道路的845个路口作为RSU可选部署地点(图 4中小点所示)即.由图 4可以看出, 可选的部署地点基本涵盖了区域内的大部分路口且分布较为均匀.
|
图 4 北京市RSU可选部署地点示意图 |
对于任意节点s, 设其具有一个节点值Js, 其初值为Js=CD(s)=deg(s)/n-1, 而deg(s):=s半径400 m内每日平均车流量, Js的初值即对应了节点s的中心性.
为了体现RSU部署的均匀性, 在每次选中一个RSU部署地点si后, 对所有其他未被选中的位置sj/的节点值进行更新，其中，sc表示能获得最佳性能的部署地点.采用式(2) 所示的更新方法来刻画si对sj的影响.
|
(2) |
其中:Cr为所部署RSU的通信能力, ρ为控制均匀性影响大小的参数, dis(si, sj)为si与sj之间的实际距离.
2.2 部署算法同时考虑中心性与均匀性, 采用图 5所示的方法来设计RSU部署算法.算法的第1~4行对节点的值进行了初始化, 并将所选部署位置集合初始化为空集, 将已选位置数量置为0；第5~12行中, 在每个循环中已部署的位置节点之间挑选当前值最大的节点作为此次选择的部署位置, 将此位置加入到所选集合中, 并对未选位置的节点值进行更新.重复上述循环, 直到选择的RSU部署位置数量与待部署的RSU数量相同.
|
图 5 兼顾中心性与均匀性的RSU部署算法 |
本节使用北京市车载移动数据对算法进行性能仿真.仿真中不仅使用了同时考虑中心性与均匀性的算法(简称兼顾算法), 还使用了单独考虑中心性或者均匀性的算法, 并对不同的算法进行比较.其中, 单独考虑中心性的算法(简称中心性算法)即为直接选择节点中心性最高的R个节点部署RSU, 而单独考虑均匀性的算法(简称均匀性算法)即为随机选择R个节点部署RSU.
首先仿真R=200的情况, 取ρ=0.002, 兼顾算法、中心性算法和均匀性算法所选取的RSU部署位置分别如图 6、图 7和图 8所示.由3幅图可以看出, 中心性算法选出的RSU部署位置基本集中在北京市的几条主干道上, 分布极不均匀, 多处出现小区域内选取了众多部署位置的情况, 很明显这种选取方法不够合理; 对于均匀性算法选取的RSU部署位置, 较为均匀地分散在北京市的各个角落, 但却不能体现出不同地区车流量不同的特点, 很多选取的路口甚至是偏僻的小路口, 车流量极少, 这样的选取策略明显也是不合理的; 而所提出的兼顾算法选取的路口, 不仅对北京市车流量大的主要道路基本实现了覆盖, 而且对其余区域也基本实现了均匀分布, 部署策略和方法更加合理.
|
图 6 兼顾算法选取的RSU部署位置 |
|
图 7 中心性算法选取的RSU部署位置 |
|
图 8 均匀性算法选取的RSU部署位置 |
下面将通过定量计算来考量3种算法对网络性能的影响, 由于延时对网络性能有较大影响, 所以主要考查延时这个指标.使用北京市数据集中一周的车辆移动数据来进行仿真, 选取了其中比较活跃的500辆出租车, 这500辆出租车中的每辆车在这一周的仿真时间期间会随机产生3~8次的服务需求.若该车产生服务需求时正好处于RSU的覆盖范围内(RSU覆盖范围为半径为400 m的圆), 则其将立即被满足服务需求; 若否, 则定义从该时刻起直到该车运动到任意一个RSU覆盖范围内的时间间隔为该次服务的延时.对所有车辆所有服务的延时进行求和, 称为服务延时和, 并用其来作为衡量网络性能的标准.
分别设置待部署的RSU数量为R=50, 100, 200, 400, 将兼顾算法、中心性算法和均匀性算法对应的延时和绘制为折线图，如图 9所示.可以看出, 随着RSU部署数量的增加, 3种算法的延时和均不断减小, 其中兼顾算法的延时和一直最小, 而中心性算法的延时和一直最大, 这说明单独考虑中心性确实是不合理的, 所提出的兼顾算法能有效提升整个网络的性能.
|
图 9 3种算法在不同RSU数量下的总延时对比 |
对车载机会网络中的基础设施部署问题进行了研究, 提出了一个兼顾中心性与均匀性的RSU部署算法(兼顾算法), 并以北京市真实车辆移动数据作为数据集来研究相关问题.为了提高算法的性能, 对数据进行了预处理, 剔除了明显错误的数据点, 并使用线性插值方法统一了数据点的时间刻度, 插值后的数据能较为真实地反映车辆的移动情况.最后, 通过模拟仿真发现采用所提出的兼顾算法来部署RSU的车载网络能有效提升网络的性能.
| [1] | Blum J J, Eskandarian A, Hoffman L J. Challenges of inter-vehicle ad hoc networks[J].IEEE Transactions on Intelligent Transportation Systems, 2013, 5(4): 347–351. |
| [2] | Abdrabou A, Weihua Zhuang. Probabilistic delay control and road side unit placement for vehicular ad hoc networks with disrupted connectivity[J].IEEE Journal on Selected Areas in Communications, 2011, 29(1): 129–139. doi: 10.1109/JSAC.2011.110113 |
| [3] | Lin Xiaodong, Lu Rongxing, Liang Xiaohui, et al. Stap: a social-tier-assisted packet forwarding protocol for achieving receiver-location privacy preservation in vanets[C]//Proceedings of IEEE INFOCOM 2011, IEEE INFOCOM. Shanghai: IEEE Press, 2011: 2147-2155. |
| [4] | Johnson M, De NardisL, RamchandranK. Collaborative content distribution for vehicular ad hoc networks[C]//Proceedings of 44th Allerton Conference on Communication, Control, and Computing. Monticello, IL: [s.n.], 2006: 751-760. |
| [5] | Kaisser F, Veque V. On the scalability problem of highway ad hoc network[C]//Proceedings of Wireless Communications and Networking Conference, WCNC 2009. Istanbul, Turkey: IEEE Press, 2009: 1-6. |
| [6] |
黄晓敏, 汪洋, 张继良, 等. 车联网无线链路传输数据业务性能评估[J]. 北京邮电大学学报, 2014, 37(s1): 66–71.
Huang Xiaomin, Wang Yang, Zhang Jiliang, et al. Performance evaluation of VANETs wireless link transmitting data service[J].Journal of Beijing University of Posts and Telecommunications, 2014, 37(s1): 66–71. |