Connected dominating sets in wireless ad hoc and sensor networks – A comprehensive survey

Topology control is a fundamental issue in wireless ad hoc and sensor networks. Due to intrinsic characteristic of flatness, hierarchical topology can achieve the scalability and efficiency of a wireless network. To solve this problem, one can construct a virtual backbone network by using a connected dominating (CDS) set of a wireless network. In past few years, efficiently and fast construct a CDS in a wireless network as a virtual backbone has been the main research problem in hierarchical topology control. In this paper, we give a comprehensive survey for CDSs and related problems with various network models and specific applications. To conclude, some open problems and interesting issues in this field are proposed.