Robust Dominating Set based Virtual Backbones for Wireless Ad hoc Networks

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.