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

Roadsides
Communication
Heuristics

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
Sarubbi, João F.M. ; Silva, Taís R. ; Martins, Flávio V.C. ; Wanner, Elizabeth F. ; Silva, Cristiano M. / A GRASP based heuristic for Deployment Roadside Units in VANETs. Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management. IEEE, 2017. pp. 369-376
@inproceedings{64351bb0d2aa4829965b6a04e8774d8c,
title = "A GRASP based heuristic for Deployment Roadside Units in VANETs",
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.",
author = "Sarubbi, {Jo{\~a}o F.M.} and Silva, {Ta{\'i}s R.} and Martins, {Fl{\'a}vio V.C.} and Wanner, {Elizabeth F.} and Silva, {Cristiano M.}",
year = "2017",
month = "7",
day = "20",
doi = "10.23919/INM.2017.7987300",
language = "English",
pages = "369--376",
booktitle = "Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management",
publisher = "IEEE",
address = "United States",

}

Sarubbi, JFM, Silva, TR, Martins, FVC, Wanner, EF & Silva, CM 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., 7987300, IEEE, pp. 369-376, 15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017, Lisbon, Portugal, 8/05/17. https://doi.org/10.23919/INM.2017.7987300

A GRASP based heuristic for Deployment Roadside Units in VANETs. / Sarubbi, João F.M.; Silva, Taís R.; Martins, Flávio V.C.; Wanner, Elizabeth F.; Silva, Cristiano M.

Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management. IEEE, 2017. p. 369-376 7987300.

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

TY - GEN

T1 - A GRASP based heuristic for Deployment Roadside Units in VANETs

AU - Sarubbi, João F.M.

AU - Silva, Taís R.

AU - Martins, Flávio V.C.

AU - Wanner, Elizabeth F.

AU - Silva, Cristiano M.

PY - 2017/7/20

Y1 - 2017/7/20

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85029417809&partnerID=8YFLogxK

U2 - 10.23919/INM.2017.7987300

DO - 10.23919/INM.2017.7987300

M3 - Conference contribution

AN - SCOPUS:85029417809

SP - 369

EP - 376

BT - Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management

PB - IEEE

ER -

Sarubbi JFM, Silva TR, Martins FVC, Wanner EF, Silva CM. 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. IEEE. 2017. p. 369-376. 7987300 https://doi.org/10.23919/INM.2017.7987300