Efficient Algorithms for Topology Control Problem with Routing Cost Constraints in Wireless Networks

摘要

Topology control is one vital factor to a wireless network's efficiency. A Connected Dominating Set (CDS) can be a useful basis of a backbone topology construction. In this paper, a special CDS, named alpha Minimum rOuting Cost CDS (alpha-MOC-CDS), will be studied to improve the performance of CDS based broadcasting and routing. In this paper, we prove that construction of a minimum alpha-MOC-CDS is NP-hard in a general graph and we propose a heuristic algorithm for construction of alpha-MOC-CDS.