Back to Search
Start Over
Access Points Planning in Urban Area for Data Dissemination to Drivers.
- Source :
-
IEEE Transactions on Vehicular Technology . Jan2014, Vol. 63 Issue 1, p390-402. 13p. - Publication Year :
- 2014
-
Abstract
- Roadside infrastructure can greatly help disseminate data to drivers. In this paper, we study a fundamental problem, i.e., roadside infrastructure planning. We propose a class of algorithms named Tailor to select a minimum number of intersections to install the infrastructure. In the case when the traffic information is not available, we formulate the intersection selection problem, which formally proves its np-completeness, and provide novel heuristics, i.e., the adapted-bipartite-based heuristics (ABS), to solve it, whose worst-case approximation ratio is 4/3. ABS bridges the planar graph and the bipartite graph through topology transformation. With ABS, the approximate solution to all the problems that are NP-hard in a general planar graph but polynomially solvable in a bipartite graph can be efficiently obtained in the planar graph. We also prove that, even with traffic information, the intersection selection problem remains NP-hard. Greedy heuristics is employed to balance the tradeoff between the number of selected intersections and the percentage of reached vehicles. [ABSTRACT FROM PUBLISHER]
- Subjects :
- *CITIES & towns
*AUTOMOBILE drivers
*MOTOR vehicle drivers
*GRAPH theory
*GEOMETRY
Subjects
Details
- Language :
- English
- ISSN :
- 00189545
- Volume :
- 63
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Vehicular Technology
- Publication Type :
- Academic Journal
- Accession number :
- 93764661
- Full Text :
- https://doi.org/10.1109/TVT.2013.2272724