城市环境车联网中基于近似算法的RSU部署方案

摘要

To minimize the number of RSU deployed to cover a specific area,a c street model transforming the area covering problem to streets covering problem was designed,and a greedy-based polynomial (GBP) time approximation algorithm was developed to obtain the optimal RSU deployment for area coverage.For complex urban environments,a Cue model (complex urban environments model) was proposed.In this model,the target area was divided into different partitions.Then,based on shifting strategy,a polynomial time approximation scheme was designed.Theoretical analysis that include the approximation ratio and time complexity of the proposed algorithm were also presented.Simulation results show that GBP can efficiently solve the coverage problem in urban VANET.%为了使用尽可能少的RSU实现对目标区域的有效覆盖,设计c街道模型,将对区域的覆盖转化为对区域内街道的覆盖,然后,在该模型下提出基于贪心策略的多项式(GBP,greedy-based polynomial)时间近似算法,得到RSU的部署方案以解决覆盖问题.针对城市中一些地形复杂的区域,设计Cue模型(complex urban environment model),将目标区域划分为子区域,然后提出基于shifting策略的多项式时间近似算法,并对算法的近似比率和时间复杂度进行了理论分析与证明.仿真结果表明,算法GBP能够有效地解决城市环境车联网中的区域覆盖问题.