A Memetic Algorithm Approach to Deploy RSU s Based on the Gamma Deployment Metric

摘要

Vehicular ad hoc networks (VANETs) are considered a practical application of mobile and ad hoc networks. They have potential to ease traffic management, lower accident rates, and they are essential to autonomous vehicles. In this work, we propose a Memetic Algorithm, called Gamma-LSGA, for solving the allocation of roadside units (RSUs) in VANETs. The Gamma-LSGA algorithm uses two hill climbing-based heuristics. To assure quality of service, we use a metric called Gamma Deployment. That metric is based on two aspects: (i) the intercontact time between vehicles and RSUs and (ii) the percentage of vehicles fulfilling such inter-contact time. We run experiments using a mobility trace from the city of Cologne, Germany, and compared our results with the ones delivered by the deterministic heuristic Gamma-G, previously proposed. For almost all comparison cases, the memetic approach provided results with fewer RSUs than Gamma-G, with gains up to 32.7%.