%0 Journal Article
%T Efficient algorithm for finding minimum connected dominating set in wireless sensor networks<br>传感器网络中高效的最小连通支配集求解算法
%A XIE Rong
%A QI De-yu
%A LI Yong-jun
%A QIAN Zheng-ping
%A <br>谢嵘
%A 齐德昱
%A 李拥军
%A 钱正平
%J 计算机应用
%D 2008
%I 
%X 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.
%K wireless sensor network
%K connected dominating set
%K distributed algorithm
%K hierarchical graph<br>无线传感器网络
%K 连通支配集
%K 分布式算法
%K 层次图
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=831E194C147C78FAAFCC50BC7ADD1732&aid=CDD0930CF5870B4769D5A437BF24AC53&yid=67289AFF6305E306&vid=D3E34374A0D77D7F&iid=0B39A22176CE99FB&sid=556C1A86E372B606&eid=A04F01817ECB9A48&journal_id=1001-9081&journal_name=计算机应用&referenced_num=0&reference_num=14