Title: Heuristic Algorithms for Constructing Connected Dominating Sets with Minimum Size and Bounded Diameter in Wireless Networks
Abstract: Connected dominating set (CDS) is widely used in wireless networks as a virtual backbone for communication and routing between nodes. In order to measure the quality of a CDS, most researches in this area focus on reducing the size of a CDS, neglecting other important metrics, such as diameter between two communication parties. This paper considers the diameter as a quality factor for CDS construction, and develops two new heuristic algorithms. In particular, the CDS computed by the first algorithm has constant ratios 9 and 3 for its size and diameter, respectively. And that of the second algorithm has constant ratios 5 + ln 10 and 2. Both theoretical analysis and simulation show out the performance of the algorithms.
Publication Year: 2010
Publication Date: 2010-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 10
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot