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

fYear

2008

fDate

3-5 June 2008

Firstpage

1430

Lastpage

1434

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(T_MIS+log*n/epsiv^O(1)), where T_MIS 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;

fLanguage

English

Publisher

ieee

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

Type

conf

DOI

10.1109/ICIEA.2008.4582755

Filename

4582755