Fault Tolerant Multiple Dominating Set Constructions for Wireless Ad-hoc Networks

In wireless ad-hoc networks, broadcasting is the most common communication method. To reduce redundancy, traffic and collision induced by broadcasting, different virtual backbones are used on top of the physical topology and Connected Dominating Set (CDS) is one of those. However, constructing minimum connected dominating set (MCDS) containing minimum number of nodes is an NP-complete problem. Although some approximation algorithms are available, the CDS or its approximation has poor fault tolerance. In this work, we present two heuristics, one centralized and the other distributed, for constructing multiple connected dominating sets providing enhanced fault tolerance of the network. Both algorithms are intended to maximize network lifetime involving minimal nodes. Moreover, both the algorithms also ensure load balancing over the network. Finally, we simulate our heuristics to show the improvement of network lifetime and system fault tolerance.