Heuristic Algorithms for Constructing Connected Dominating Sets with Minimum Size and Bounded Diameter in Wireless Networks

摘要

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.