摘要
针对车联网城市环境下限制数量的路侧单元(RSU)的最佳部署位置难以确定的问题,将RSU对车辆的覆盖转化为对区域内划分子路段的覆盖,通过各路段上车辆的密度和平均速度计算路段上的数据传输时延,设计基于Dijkstra的0-1覆盖矩阵求解算法,将时延约束的RSU部署问题(DBRD)转化为集合覆盖问题。提出改进遗传算法的RSU部署方案(IGARD),在限定RSU部署数的前提下从候选位置集中选出最佳部署位置以最大化时延内覆盖路段的数量。与传统的遗传算法相比,IGARD方案基于贪心算法的思想产生初始种群,新解产生时根据设计的交叉算子和变异算子执行交叉和变异操作,且在执行过程中对不满足约束条件的潜在解进行修复,这样不仅可以将带约束条件的研究问题转化为无约束条件问题,避免了确定罚函数的困难,而且平衡了算法的集中搜索和多样性搜索能力。仿真结果表明:在相同的时延约束下,利用IGARD方案部署RSU可以将路段覆盖率提高5%以上。IGARD方案能够在时延约束下确定RSU的最佳部署位置,提高网络的性能,并为相同应用场景下的RSU部署提供一定的参考。
A Dijkstra based 0-1 covering matrix computing algorithm is designed through the vehicles density and average speed on the roads to solve the problem that the deployment location of number-limited RSU(road side unit) in urban VANET is difficult to determine. The algorithm converts the coverage of vehicles into coverage of divided sub-roads in the deployment area and the delay-bounded RSU deployment problem(DBRD) is converted into a set-covering problem. Then an RSU deployment scheme based on an improved genetic algorithm(IGARD) is proposed. The best deployment location is selected from candidates under the premise of limiting the number of RSUs to maximize the number of covering roads in the bounded delay. A comparison with the traditional genetic algorithm shows that IGARD scheme utilizes the idea of greedy algorithm to generate initial population, and uses the designed crossover operator as well as the mutation operator to execute the crossover operation and the mutation operation. Moreover, the potential solution is also repaired in the execution process. This not only turns the constrained optimization problem into an unconstrained problem and avoids the difficulty of selecting penalty function, but also balances the algorithm’s ability of focused search and diversified search. Experimental results show that using IGARD scheme for RSU deployment gains an over 5% increase in the road coverage ratio under the same bounded delay. Therefore, IGARD scheme can get the best location among candidates, promote network performance, and provide reference for RSU deployment under the same scene.
作者
贾宗璞
杨焕焕
谢果君
JIA Zongpu;YANG Huanhuan;XIE Guojun(School of Computer Science and Technology,Henan Polytechnic University,Jiaozuo,Henan 454000,China)
出处
《西安交通大学学报》
EI
CAS
CSCD
北大核心
2019年第4期128-135,166,共9页
Journal of Xi'an Jiaotong University
基金
国家自然科学基金资助项目(61300124)
河南省科技攻关计划资助项目(132102210123)
关键词
车联网
路侧单元
时延约束
遗传算法
vehicular ad-hoc networks
road side unit deployment
delay-bounded
genetic algorithm
