Access points planning in Urban area for data dissemination to drivers

Tan Yan, Wensheng Zhang, Guiling Wang, Yujun Zhang

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


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 languageEnglish (US)
Article number6557533
Pages (from-to)390-402
Number of pages13
JournalIEEE Transactions on Vehicular Technology
Issue number1
StatePublished - Jan 2014
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Aerospace Engineering
  • Electrical and Electronic Engineering
  • Computer Networks and Communications
  • Automotive Engineering


  • Graph theory
  • NP-complete
  • heuristics
  • vehicular ad hoc network (VANET)


Dive into the research topics of 'Access points planning in Urban area for data dissemination to drivers'. Together they form a unique fingerprint.

Cite this