Title: Construction of distributed connected dominating sets in growth-bounded graphs
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+ε)-approximation MCDS. The time complexity is O(T <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">MIS</inf> +log*n/ε <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">O(1)</sup> ), where T <inf xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">MIS</inf> is the time required to compute a maximal independent set in the graph and n denotes the number of nodes.
Publication Year: 2008
Publication Date: 2008-06-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 1
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot