Constructing Distributed Connected Dominating Sets in Growth-Bounded Graphs
Yanjing Sun, Jiansheng Qian · 2008
When modeling the network as a graph, the most widely used concept for defining a virtual backbone is the connected dominating set (CDS). We present a distributed algorithm for finding an approximation of a Minimum connected dominating sets to construct a virtual backbone in the growth- bounded graph. 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 O(TMIS+log*n/epsivO(1)), where TMISis the time required to compute a maximal independent set in the graph and n denotes the number of nodes. The only information required by the nodes is the set of their direct neighbors. Our algorithm guarantees that the computed CDS has constant stretch and constant degree.