Abstract:Spanners play important role in topology control of wireless (ad hoc, sensor) networks since they not only decrease the number of links and preserve connectivity of the final topology graph but also ensure that the cost between any pair of communication nodes is within some constant factor from the shortest possible cost. For topology control of wireless networks, a large number of spanner construction algorithms have been presented to efficiently satisfy various kinds of topological characteristics for the network design requests, such as locality, sparseness, lightness, small maximum degree, and fault-tolerance. In this comprehensive survey, the taxonomy for spanners is given according to the definition and different types of classification methods. For spanner construction, the typical centralized and localized algorithms and algorithms possessing one or more topological characteristics are analyzed, and some open problems worth of future research are proposed. The further work is to find simpler algorithms with better performance combining with novel and more practical models in wireless networks.