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

为了使用尽可能少的 RSU 实现对目标区域的有效覆盖,设计 c 街道模型,将对区域的覆盖转化为对区域内街道的覆盖,然后,在该模型下提出基于贪心策略的多项式(GBP,greedy-based polynomial)时间近似算法,得到RSU的部署方案以解决覆盖问题。针对城市中一些地形复杂的区域,设计Cue模型(complex urban environment model),将目标区域划分为子区域,然后提出基于 shifting 策略的多项式时间近似算法,并对算法的近似比率和时间复杂度进行了理论分析与证明。仿真结果表明,算法 GBP 能够有效地解决城市环境车联网中的区域覆盖问题。