Planning roadside infrastructure for information dissemination in intelligent transportation systems
Planning roadside infrastructure for information dissemination in intelligent transportation systems
复制标题
DOI：
10.1016/j.comcom.2009.11.021
复制
发表时间：
2010-03-01
影响因子：
6
通讯作者：
Barcelo Ordinas, J. M.
中科院分区：
文献类型：
--
作者：
Trullols, O.;Fiore, M.;Barcelo Ordinas, J. M.
我们考虑一个智能交通系统，其中必须部署一定数量的基础设施节点(称为传播点，DPS)来向城市地区的车辆传播信息。我们将问题描述为最大覆盖问题(MCP)，并寻求在所考虑的区域内最大限度地增加与DPS接触的车辆数量。众所周知，MCP在其标准公式中是NP-Hard的，因此我们通过启发式算法来解决它，这些算法呈现出不同的复杂性水平，并且需要关于系统的不同知识。接下来，我们将解决保证大量车辆在一个或多个DPS的覆盖范围内行驶足够时间的问题。因此，我们给出了问题的不同公式，然而，该问题仍然是NP难的，需要启发式方法来解决。通过在现实的城市环境中评估所提出的解决方案，我们观察到，即使在大规模场景中，简单的启发式算法也能提供接近最优的结果。然而，我们指出，只有在了解车辆的机动性特征的情况下，才能实现对移动用户的近乎最佳的覆盖。(C)2009爱思唯尔B.V.保留所有权利。
We consider an intelligent transportation system where a given number of infrastructured nodes (called Dissemination Points, DPs) have to be deployed for disseminating information to vehicles in an urban area. We formulate our problem as a Maximum Coverage Problem (MCP) and we seek to maximize the number of vehicles that get in contact with the DPs over the considered area. The MCP is known to be NP-hard in its standard formulation, therefore we tackle it through heuristic algorithms, which present different levels of complexity and require different knowledge on the system. Next, we address the problem of guaranteeing that a large number of vehicles travel under the coverage of one or more DPs for a sufficient amount of time. We therefore give a different formulation of the problem, which however is still NP-hard and requires a heuristic approach to be solved. By evaluating the proposed solutions in a realistic urban environment, we observe that simple heuristics provide near-optimal results even in large-scale scenarios. However, we remark that a near-optimal coverage of mobile users can be achieved only when the characteristics of vehicular mobility are known. (C) 2009 Elsevier B.V. All rights reserved.