| Topology control has crucial impact on the system performance of wireless ad hoc networks. We propose several topology control algorithms that can maintain network connectivity while reducing energy consumption and improving network capacity. Being fully localized, these algorithms adapt well to mobility, and incur less overhead and delay. They not only significantly outperform existing schemes in terms of energy efficiency and network capacity, but also provide performance guarantees such as degree bound and min-max optimality.; We first present Local Minimum Spanning Tree (LMST) for homogeneous wireless ad hoc networks where each node has the same maximal transmission power, and prove several desirable properties. Then we show that most existing algorithms cannot be directly applied to heterogeneous networks where nodes have different maximal transmission power, and propose Directed Relative Neighborhood Graph (DRNG) and Directed Local Spanning Subgraph (DLSS). To the best of our knowledge, this is one the first efforts to address the connectivity and bi-directionality issues in heterogeneous wireless networks. We prove that the out-degree of any node in the resulting topology by LMST, DLSS or DRNG is upper-bounded by a constant. To incorporate fault tolerance into network topologies, we propose Fault-tolerant Local Spanning Subgraph (FLSS), which preserves k-vertex connectivity and is min-max optimal (i.e., the maximal transmission power among all nodes in the network is minimized) among all strictly localized algorithms.; We also examine several widely used assumptions in topology control (e.g., obstacle-free communication channel, the capability of obtaining position information), and discuss how to relax these assumptions to make our algorithms more practical.; Finally, we consider power-efficient broadcast in wireless ad hoc networks as an application of the proposed topology control algorithms, and propose Broadcast on Local Spanning Subgraph (BLSS), which broadcasts in a constrained flooding fashion over the network topology by FLSS. We show that BLSS is scalable, power-efficient, reliable, and significantly outperforms existing localized broadcast algorithms. |
