Fault tolerant multiple dominating set constructions for wireless AD-HOC networks

Abstract

In wireless network, broadcasting is the most common communication method. To reduce re- dundancy, 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. How- ever, constructing minimum connected dominating set (MCDS) containing minimum number of nodes participating in packet forwarding is an NP-complete problem. Although some ap- proximation algorithms are available, the CDS or its approximation has poor fault tolerance as in a CDS one vertex not in CDS is exactly connected with one vertex in CDS. 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 algo- rithms also ensure load balancing over the network. Finally, we simulate our result to show the improvement of network lifetime and system fault tolerance.