Title: Approximation algorithm for minimum connected dominating set in unit disk graphs
Abstract: Minimum Connected Dominating Set(MCDS) problem is a classical optimization issue in the design of wireless networks.For the construction of MCDS in the Unit Disk Graph(UDG) to model wireless sensor networks,an efficient approximation algorithm,DDT,was proposed based on distributed greedy strategy.In each round,it repeatedly selected a node to link a determined node according to weights and state information among one-hop neighborhood,and finally,found a dominating tree for the graph.The maximum node degree in the dominating tree was studied using probabilistic method.By analyzing the relationship between the size of the maximal independent set and the minimum connected dominating set,the algorithm produced a new approximation ratio.The experimental results show the superiority of the DDT algorithm over other existing distributed algorithms in terms of the CDS size.
Publication Year: 2011
Publication Date: 2011-01-01
Language: en
Type: article
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot