A GRASP based heuristic for Deployment Roadside Units in VANETs

João F.M. Sarubbi, Taís R. Silva, Flávio V.C. Martins, Elizabeth F. Wanner, Cristiano M. Silva

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

In this work we propose a new algorithm, Delta-r-GRASP, for solving the allocation of Roadside Units (RSUs) in a Vehicular Network. Our goal is to find the minimum set of RSUs to meet a Deployment Δρ2 ρ1. The Deployment Δρ2 ρ1 is a metric for specifying minimum communication guarantees from the infrastructure supporting the Vehicular Network. We compare our algorithm with a baseline algorithm, Delta-r. Moreover, we compare our results with the optimal value achieved by solver CPLEX. Our results demonstrate that our approach requires up to 85% fewer RSUs to achieve the same deployment efficiency, and our results differ no more than 15% from the optimal values.

Original languageEnglish
Title of host publicationProceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management
PublisherIEEE
Pages369-376
Number of pages8
ISBN (Electronic)9783901882890
DOIs
Publication statusPublished - 20 Jul 2017
Event15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017 - Lisbon, Portugal
Duration: 8 May 201712 May 2017

Conference

Conference15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017
CountryPortugal
CityLisbon
Period8/05/1712/05/17

    Fingerprint

Cite this

Sarubbi, J. F. M., Silva, T. R., Martins, F. V. C., Wanner, E. F., & Silva, C. M. (2017). A GRASP based heuristic for Deployment Roadside Units in VANETs. In Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management (pp. 369-376). [7987300] IEEE. https://doi.org/10.23919/INM.2017.7987300