Minimum Connected Dominating Set Using a Collaborative Cover Heuristic for Ad Hoc Sensor Networks.

A minimum connected dominating set (MCDS) is used as virtual backbone for efficient routing and broadcasting in ad hoc sensor networks. The minimum CDS problemis NP-complete even in unit disk graphs. Many heuristics-based distributed approximation algorithms for MCDS problems are reported and the best known performance ratio has (4:8 + ln 5). We propose a new heuristic called collaborative cover using two principles: 1) domatic number of a connected graph is at least two and 2) optimal substructure defined as subset of independent dominator preferably with a common connector. We obtain a partial Steiner tree during the construction of the independent set (dominators). A final postprocessing step identifies the Steiner nodes in the formation of Steiner tree for the independent set of G. We show that our collaborative cover heuristics are better than degree-based heuristics in identifying independent set and Steiner tree. While our distributed approximation CDS algorithm achieves the performance ratio of (4:8 + ln 5)opt + 1:2, where opt is the size of any optimal CDS, we also show that the collaborative cover heuristic is able to give a marginally better bound when the distribution of sensor nodes is uniform permitting identification of the optimal substructures. We show that the message complexity of our algorithm is O(nΔ2);Δ being the maximum degree of a node in graph and the time complexity is O(n). [ABSTRACT FROM AUTHOR]