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

College of Engineering and Physical Sciences

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

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

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

Access to Document

Other files and links

Fingerprint

Cite this