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

doi:10.23919/INM.2017.7987300

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

Centro Federal de Educação Tecnológica - MG
Departamento de Computação
Universidade Federal de São João del-Rei

Research output: Chapter in Book/Published conference output › Conference publication

8 Citations (Scopus)

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 language	English
Title of host publication	Proceedings of the IM 2017 - 2017 IFIP/IEEE International Symposium on Integrated Network and Service Management
Publisher	IEEE
Pages	369-376
Number of pages	8
ISBN (Electronic)	9783901882890
DOIs	https://doi.org/10.23919/INM.2017.7987300
Publication status	Published - 20 Jul 2017
Event	15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017 - Lisbon, Portugal Duration: 8 May 2017 → 12 May 2017

Conference

Conference	15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017
Country/Territory	Portugal
City	Lisbon
Period	8/05/17 → 12/05/17

Funding

This work was partially funded by CNPq, FAPEMIG, CAPES and CEFETMG.

Access to Document

10.23919/INM.2017.7987300

Cite this

@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 = jul,

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",

note = "15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017 ; Conference date: 08-05-2017 Through 12-05-2017",

}

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

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 - https://www.scopus.com/pages/publications/85029417809

U2 - 10.23919/INM.2017.7987300

DO - 10.23919/INM.2017.7987300

M3 - Conference publication

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

T2 - 15th IFIP/IEEE International Symposium on Integrated Network and Service Management, IM 2017

Y2 - 8 May 2017 through 12 May 2017

ER -

A GRASP based heuristic for Deployment Roadside Units in VANETs

Abstract

Conference

Funding

Access to Document

Other files and links

Fingerprint

Cite this