Available on ORBilu since
11 February 2014
Doctoral thesis (Dissertations and theses)
Robust Dominating Set based Virtual Backbones for Wireless Ad hoc Networks
Schleich, Julien


Full Text
Author postprint (3.39 MB)

All documents in ORBilu are protected by a user license.

Send to


Keywords :
mobile ad hoc network; connected dominating set; virtual backbone; decentralized algorithms; global optimization
Abstract :
[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.
Disciplines :
Computer science
Author, co-author :
Schleich, Julien ;  University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC)
Language :
Title :
Robust Dominating Set based Virtual Backbones for Wireless Ad hoc Networks
Defense date :
28 September 2010
Institution :
Unilu - University of Luxembourg, Luxembourg, Luxembourg
Université Paul Verlaine - Metz, France
Degree :
Docteur en Informatique
Promotor :
Bouvry, Pascal 
Thi Hoai An, Lé


Number of views
101 (3 by Unilu)
Number of downloads
604 (4 by Unilu)


Similar publications

Contact ORBilu