Construction algorithms for k-connected m-dominating sets in wireless sensor networks

Abstract

A Connected Dominating Set (CDS) working as a virtual backbone is an effective way to decrease the overhead of routing in a wireless sensor network. Furthermore, a k-Connected m-Dominating Set (kmCDS) is necessary for fault tolerance and routing flexibility. Some approximation algorithms have been proposed to construct a kmCDS. However, most of them only consider some special cases where k = 1,2 or k ≤ m, or are not easy to implement, or have high message complexity. In this paper, we propose a novel distributed algorithm LDA with low message complexity to construct a kmCDS for general k and m whose size is guaranteed to be within a small constant factor of the optimal solution when the maximum node degree is a constant. We also propose one centralized algorithm ICGA with a constant performance ratio to construct a kmCDS. Theoretical analysis as well as simulation results are shown to evaluate the proposed algorithms.