A Centrality-based RSU Deployment Approach for Vehicular Ad Hoc Networks

Abstract : This paper studies the RSU deployment problem in a 2-D road scenario of a vehicular ad hoc network. To optimize RSU deployment, we introduce the notion of centrality in a social network to RSU deployment, and use it to measure the importance of an RSU position candidate in RSU deployment. Based on the notion of centrality, we propose a centrality-based RSU deployment approach and formulate the RSU deployment problem as a linear programing problem with the objective to maximize the total centrality of all position candidates selected for RSU deployment under the constraint of a given deployment budget. To solve the formulated problem, we analogize the problem to a 0-1 Knapsack problem and thus employ a 0-1 Knapsack algorithm to solve the problem. In the analogy, the budget in the RSU deployment problem is analogous to the bag's capacity in the Knapsack problem, the cost of deploying an RSU is analogous to an item's weight, and the centrality of a position candidate is analogous to an item's value. Simulation results show that the proposed centrality-based deployment approach can effectively improve the efficiency of the RSU deployment in terms of the coverage time ratio as compared to a random deployment approach.
Document type :
Conference papers
Liste complète des métadonnées

Cited literature [11 references]  Display  Hide  Download

Contributor : Nathalie Mitton <>
Submitted on : Wednesday, June 7, 2017 - 10:54:28 AM
Last modification on : Friday, January 19, 2018 - 4:20:01 PM
Document(s) archivé(s) le : Friday, September 8, 2017 - 12:23:44 PM


Files produced by the author(s)


  • HAL Id : hal-01465393, version 1



Zhenyu Wang, Jun Zheng, Yuying Wu, Nathalie Mitton. A Centrality-based RSU Deployment Approach for Vehicular Ad Hoc Networks. ICC-AHNS 2017 - IEEE International Conference on Communication 2017 Ad-Hoc and Sensor Networking Symposium , May 2017, Paris, France. pp.5. ⟨hal-01465393⟩



Record views


Files downloads