Constructing k-connected M-dominating sets in wireless sensor networks

Yiwei Wu, Feng Wang, My T. Thai, Yingshu Li

Research output: Chapter in Book/Report/Conference proceedingConference contribution

68 Scopus citations


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 TO. Simulation results are also presented to evaluate our algorithms and the results show that our algorithms have better performances than the exiting other algorithms.

Original languageEnglish (US)
Title of host publicationMilitary Communications Conference, MILCOM 2007
StatePublished - 2007
EventMilitary Communications Conference, MILCOM 2007 - Orlando, FL, United States
Duration: Oct 29 2007Oct 31 2007

Publication series

NameProceedings - IEEE Military Communications Conference MILCOM


OtherMilitary Communications Conference, MILCOM 2007
Country/TerritoryUnited States
CityOrlando, FL

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'Constructing k-connected M-dominating sets in wireless sensor networks'. Together they form a unique fingerprint.

Cite this