Title :
Construction of distributed connected dominating sets in growth-bounded graphs
Author :
Qian, Jiansheng ; Sun, Yanjing
Author_Institution :
Sch. of Inf. & Electr. & Eng., China Univ. of Min. & Technol., Xuzhou
Abstract :
A distributed algorithm for finding approximation minimum connected dominating sets to construct a virtual backbone in the growth-bounded graph for wireless sensor network is presented. This approach consists of three phases: firstly construct an MIS by network decomposition; secondly find a minimum dominating set and finally use Marking process and ruling K to optimize the virtual backbone. The algorithms run with adjustable transmission range and computer a (1+epsiv)-approximation MCDS. The time complexity is 0(TMIS+log*n/epsivO(1)), where TMIS is the time required to compute a maximal independent set in the graph and n denotes the number of nodes.
Keywords :
ad hoc networks; distributed algorithms; telecommunication computing; wireless sensor networks; MCDS; Marking process; distributed algorithm; growth-bounded graphs; network decomposition; wireless sensor network; Computer networks; Distributed algorithms; Interference; Network topology; Polynomials; Routing; Spine; Sun; Wireless networks; Wireless sensor networks;
Conference_Titel :
Industrial Electronics and Applications, 2008. ICIEA 2008. 3rd IEEE Conference on
Conference_Location :
Singapore
Print_ISBN :
978-1-4244-1717-9
Electronic_ISBN :
978-1-4244-1718-6
DOI :
10.1109/ICIEA.2008.4582755
