Optimising small-world properties in VANETs: Centralised and distributed overlay approaches

Abstract : Advantages of bringing small-world properties in mobile ad hoc networks (MANETs) in terms of quality of service has been studied and outlined in the past years. In this work, we focus on the specific class of vehicular ad hoc networks (VANETs) and propose to un-partition such networks and improve their small-world properties. To this end, a subset of nodes, called injection points, is chosen to provide backend connectivity and compose a fully-connected overlay network. The optimisation problem we consider is to find the minimal set of injection points to constitute the overlay that will optimise the small-world properties of the resulting network, i.e., (1) maximising the clustering coefficient (CC) so that it approaches the CC of a corresponding regular graph and (2) minimising the difference between the average path length (APL) of the considered graph and the APL of corresponding random graphs. Two accurate evolutionary algorithms (namely, NSGAII and MOCHC) are used to find an upper-bound of high quality solutions to this new multi-objective optimisation problem, on realistic instances in the city-centre of Luxembourg. The obtained sets of solutions are then used to assess the performance of five novel heuristics proposed to solve the problem, i.e., two centralised and three decentralised. The results provided by these heuristics turned out to be extremely accurate with respect to the solutions found by the evolutionary algorithms.
Type de document :
Article dans une revue
Applied Soft Computing, Elsevier, 2014, 21, pp.637-646. 〈10.1016/j.asoc.2014.03.045〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00997510
Contributeur : Dorronsoro Bernabe <>
Soumis le : mercredi 28 mai 2014 - 11:51:07
Dernière modification le : jeudi 11 janvier 2018 - 06:22:13

Identifiants

Citation

Julien Schleich, Gregoire Danoy, Bernabé Dorronsoro, Pascal Bouvry. Optimising small-world properties in VANETs: Centralised and distributed overlay approaches. Applied Soft Computing, Elsevier, 2014, 21, pp.637-646. 〈10.1016/j.asoc.2014.03.045〉. 〈hal-00997510〉

Partager

Métriques

Consultations de la notice

213