Constructing k-Connected m-Dominating Sets in Wireless Sensor Networks

A k-Connected m-Dominating Set (kmCDS) working as a virtual backbone in a wireless sensor network is necessary for fault tolerance and routing flexibility. In order to construct a kmCDS with the minimum size, some approximation algorithms have been proposed in the literature. However, all of those algorithms only consider some special cases where k = 1,2 or k = m. In this paper, we propose one centralized heuristic algorithm CGA and one distributed algorithms, DDA which is deterministic, to construct a kmCDS for general k and m. Simulation results are also presented to evaluate our algorithms and the results show that our algorithms have better performances than the exiting other algorithms.