A New Comprehensive RSU Installation Strategy for Cost-Efficient VANET Deployment
A New Comprehensive RSU Installation Strategy for Cost-Efficient VANET Deployment
复制标题
用于经济高效的 VANET 部署的全新综合 RSU 安装策略
DOI：
10.1109/tvt.2016.2598253
复制
发表时间：
2017-05-01
影响因子：
6.8
通讯作者：
Lee, Sejin
中科院分区：
文献类型：
--
作者：
Kim, Donghyun;Velasco, Yesenia;Lee, Sejin
近年来，车载自组织网络（VANET）的研究由于其巨大的潜力而蓬勃发展。路边单元 (RSU) 是将移动车辆与其他基础设施连接起来的 VANET 基础设施的关键组成部分。为了最大限度地提高 RSU 的可用性，RSU 应密集部署。否则，可能会存在盲点，导致车辆失去与基础设施的连接。不幸的是，大规模部署 RSU 以无缝覆盖整个感兴趣的区域（可能是一个巨大的大都市）可能非常昂贵。由于VANET的有效性和优势尚未得到充分证明，如此大规模的部署目前很难成为可行的选择。受这一观察的启发，本文研究了一种如何最好地部署 RSU 的新策略，以便在有限的预算下最大化其时空覆盖范围。具体来说，我们在文献中首次考虑了一种创新的 RSU 部署框架，它是三种不同方法的均衡组合：在静态位置、公共移动交通和地方政府拥有的完全可控车辆上部署 RSU。我们首先引入一种新策略，将城市区域地图抽象为网格图。然后，我们将该问题表述为一个新的优化问题并显示其 NP 难度。为了解决这个问题，我们将这个问题转化为另一个优化问题。然后，我们针对该问题提出了一种新的多项式运行时间近似算法，并表明性能比（所提出算法的输出质量与最佳可能解决方案的质量之间的比率）至少是最佳可能比率的一半。我们还在各种设置下进行模拟，以研究所提出方法的有效性。
Recently, studies on vehicular ad hoc networks (VANETs) are booming due to their huge potential. The road side unit (RSU) is a key component of the VANET infrastructure connecting mobile vehicles to the rest of the infrastructure. To maximize the availability of RSUs, RSUs should be densely deployed. Otherwise, blind spots may exist in which vehicles lose the connection to the infrastructure. Unfortunately, the massive deployment of RSUs to seamlessly cover the whole area of interest, which could be a vast metropolitan, can be very expensive. As the effectiveness and the benefits of the VANET have yet to be fully proven, such large scale deployment can hardly be a currently viable option. Motivated by this observation, this paper investigates a new strategy of how to best deploy RSUs so that their spatiotemporal coverage is maximized under a limited budget. In detail, for the first time in the literature, we consider an innovative RSU deployment framework, which is a well-balanced combination of three different approaches: deploying RSUs on static locations, public mobile transportation, and fully controllable vehicles owned by the local government. We first introduce a new strategy to abstract a map of city area into a grid graph. Then, we formulate the problem as a new optimization problem and show its NP-hardness. To solve this problem, we transform this problem into another optimization problem. Then, we propose a new polynomial running time approximation algorithm for the problem and show that the performance ratio (the ratio between the quality of an output of the proposed algorithm and the quality of the best possible solution) is at least half of the best possible ratio. We also conduct simulations under various settings to study the effectiveness of the proposed approach.