A novel centralized algorithm for constructing virtual backbones in wireless sensor networks

Abstract Finding the minimum connected dominating set (MCDS) is a key problem in wireless sensor networks, which is crucial for efficient routing and broadcasting. However, the MCDS problem is NP-hard. In this paper, a new approximation algorithm with approximation ratio H(Δ)+3 in time O(n 2) is proposed to approach the MCDS problem. The key idea is to divide the sensors in CDS into core sensors and supporting sensors. The core sensors dominate the supporting sensors in CDS, while the supporting sensors dominate other sensors that are not in CDS. To minimize the number of both the cores and the supporters, a three-phased algorithm is proposed. (1) Finding the base-core sensors by constructing independent set (denoted as S 1), in which the sensors who have the largest |N2(v)||N(v)| $\frac {|N^{2}(v)|}{|N(v)|}$ (number of two-hop neighbors over the number of one-hop neighbors) will be selected greedily into S 1; (2) Connecting all base-core sensors in S 1 to form a connected subgraph, the sensors in the subgraph are called cores; (3) Adding the one-hop neighbors of the core sensors to the supporter set S 2. This guarantees a small number of sensors can be added into CDS, which is a novel scheme for MCDS construction. Extensive simulation results are shown to validate the performance of our algorithm.