Title: Efficient algorithm for finding minimum connected dominating set in wireless sensor networks
Abstract: The Connected Dominating Set(CDS)has been widely used for efficient routing in wireless sensor networks.Although finding the Minimum Connected Dominating Set(MCDS)in an arbitrary graph is a NP-hard problem,many approximation algorithms have been proposed to construct a serviceable CDS.To address the weaknesses of these existing algorithms,we proposed a new distributed approximation algorithm,CDS-HG,to construct the CDS for wireless sensor networks.This algorithm models a wireless sensor network as a hierarchical graph,in which a competition-based greedy strategy is used to select nodes at a certain level to route messages to the next level.Formal analysis and simulation studies show that our proposed CDS-HG algorithm generates the smallest CDS while requiring the least message complexity.
Publication Year: 2008
Publication Date: 2008-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot