Reference : Robust Dominating Set based Virtual Backbones for Wireless Ad hoc Networks
Dissertations and theses : Doctoral thesis
Engineering, computing & technology : Computer science
Robust Dominating Set based Virtual Backbones for Wireless Ad hoc Networks
Schleich, Julien [University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)]
University of Luxembourg, ​Luxembourg, ​​Luxembourg
Université Paul Verlaine - Metz, ​​France
Docteur en Informatique
Bouvry, Pascal mailto
Thi Hoai An, Lé
[en] mobile ad hoc network ; connected dominating set ; virtual backbone ; decentralized algorithms ; global optimization
[en] Ad hoc networks are infrastructure-less spontaneous networks generally composed of wireless and mobile devices. From a practical point of view, ad hoc technologies offer solutions when infrastructure-based network are too costly, damaged or not suitable. Despite a wide panel of scenarios and the huge number of ad hoc capable devices currently in use, this technology is not widely used because of technical considerations mainly related to the lack of a global coordinator. In this thesis, we propose two different approaches to create virtual backbones in order to organize ad hoc networks. In a first time, we propose a centralized algorithm based on DC programming and DCA to solve the Min m-Vertex Dominating Set Problem and in a second part, we develop distributed and asynchronous algorithms, relying on 2-hop knowledge only, to build k-Vertex Connected m-Vertex Dominating Set-based Virtual Backbones. A global overview of the domain is provided through an extensive state-of-the-art and a hierarchical classification. The efficiency of both approaches is demonstrated with a wide panels of simulations, from randomly generated graphs to more realistic scenarios.

File(s) associated to this reference

Fulltext file(s):

Open access
Schleich-Thesis.pdfAuthor postprint3.31 MBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.