A Greedy Algorithm on Constructing the Minimum Connected Dominating Set in Wireless Network

被引：10
作者：
Fu, Deqian [1 ,2 ]
Han, Lihua [1 ]
Yang, Zifen [1 ]
Jhang, Seong Tae [3 ]
机构：
[1] Linyi Univ, Sch Informat, Linyi 276005, Peoples R China
[2] Univ Jinan, Prov Key Lab Network Based Intelligent Comp, Jinnan 250022, Peoples R China
[3] Univ Suwon, Dept Comp, Hwaseong Si 445743, Gyeonggi Do, South Korea
来源：
INTERNATIONAL JOURNAL OF DISTRIBUTED SENSOR NETWORKS | 2016年 / 12卷 / 07期
基金：
中国国家自然科学基金;
关键词：
DISTRIBUTED CONSTRUCTION; APPROXIMATION; CDS;
D O I：
10.1177/155014771703201
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In the past 20 years, the connected dominating set (CDS) as a virtual backbone network has been widely used in the wireless networks. Many researchers have been devoted to designing approximate algorithms for CDS problem since constructing the minimum CDS (MCDS) is NP-hard problem. Different from the most existing algorithms with two phases, we employ greedy strategy to design a centralized algorithm GR CDS in only one phase to get MCDS, with the time complexity of O((Delta(2) + logn)n). Afterwards, another algorithm P_CDS is designed for pruning redundant nodes in the obtained MCDS with the time complexity of O(n(2)).
引用
收藏
页数：6
相关论文
共 24 条
[1]   An optimization algorithm for the minimum k-connected m-dominating set problem in wireless sensor networks [J].
Ahn, Namsu ;
Park, Sungsoo .
WIRELESS NETWORKS, 2015, 21 (03) :783-792
[2]  
[Anonymous], 1999, P 3 INT WORKSHOP DIS, DOI DOI 10.1145/313239.33261
[3]  
[Anonymous], 2004, HDB COMBINATORIAL OP
[4]   A polynomial-time approximation scheme for the minimum-connected dominating set in ad hoc wireless networks [J].
Cheng, XZ ;
Huang, X ;
Li, DY ;
Wu, WL ;
Du, DZ .
NETWORKS, 2003, 42 (04) :202-208
[5]   UNIT DISK GRAPHS [J].
CLARK, BN ;
COLBOURN, CJ ;
JOHNSON, DS .
DISCRETE MATHEMATICS, 1990, 86 (1-3) :165-177
[6]  
Das A, 2011, 2011 IEEE WIRELESS COMMUNICATIONS AND NETWORKING CONFERENCE (WCNC), P790, DOI 10.1109/WCNC.2011.5779233
[7]  
Das B, 1997, ICC'97: 1997 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS - TOWARDS THE KNOWLEDGE MILLENNIUM, CONFERENCE RECORD - VOLS 1-3, P376, DOI 10.1109/ICC.1997.605303
[8]   Routing in ad hoc networks using a spine [J].
Das, B ;
Sivakumar, R ;
Bharghavan, V .
SIXTH INTERNATIONAL CONFERENCE ON COMPUTER COMMUNICATIONS AND NETWORKS, PROCEEDINGS, 1997, :34-39
[9]   Multi-resolution state retrieval in sensor networks [J].
Deb, B ;
Bhatnagar, S ;
Nath, B .
PROCEEDINGS OF THE FIRST IEEE INTERNATIONAL WORKSHOP ON SENSOR NETWORK PROTOCOLS AND APPLICATIONS, 2003, :19-29
[10]  
Di W, 2006, IEEE ICC, P4008
123