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.
Original language | English (US) |
---|---|
Article number | 6557533 |
Pages (from-to) | 390-402 |
Number of pages | 13 |
Journal | IEEE Transactions on Vehicular Technology |
Volume | 63 |
Issue number | 1 |
DOIs | |
State | Published - Jan 2014 |
Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Aerospace Engineering
- Electrical and Electronic Engineering
- Computer Networks and Communications
- Automotive Engineering
Keywords
- Graph theory
- NP-complete
- heuristics
- vehicular ad hoc network (VANET)