Each node in a wireless multi-hop network can adjust the power level at which it transmits and thus change the topology of the network to save energy by choosing the neighbors with which it directly communicates. Many previous algorithms for distributed topology control have assumed an ability at each node to deduce some location-based information such as the direction and the distance of its neighbor nodes with respect to itself. Such a deduction of location-based information, however, cannot be relied upon in real environments where the path loss exponents vary greatly leading to significant errors in distance estimates. Also, multipath effects may result in different signal paths with different loss characteristics, and none of these paths may be line-of-sight, making it difficult to estimate the direction of a neighboring node. In this paper, we present Step Topology Control (STC), a simple distributed topology control algorithm which reduces energy consumption while preserving the connectivity of a heterogeneous sensor network without use of any location-based information. We show that the STC algorithm achieves the same or better order of communication and computational complexity when compared to other known algorithms that also preserve connectivity without the use of location-based information. We also present a detailed simulation-based comparative analysis of the energy savings and interference reduction achieved by the algorithms. The results show that, in spite of not incurring a higher communication or computational complexity, the STC algorithm performs better than other algorithms in uniform wireless environments and especially better when path loss characteristics are non-uniform.
@cite_15: 
@cite_3: This paper presents a distributed algorithm for wireless ad-hoc networks that runs in polylogarithmic number of rounds in the size of the network and constructs a lightweight, linear size, (1+e)-spanner for any given e > 0. A wireless network is modeled by a d-dimensional α-quasi unit ball graph (α-UBG), which is a higher dimensional generalization of the standard unit disk graph (UDG) model. The d-dimensional α-UBG model goes beyond the unrealistic "flat world" assumption of UDGs and also takes into account transmission errors, fading signal strength, and physical obstructions. The main result in the paper is this: for any fixed e > 0, 0 < α ≤ 1, and d ≥ 2 there is a distributed algorithm running in O(log n•log* n) communication rounds on an n-node, d-dimensional α-UBG G that computes a (1+e)-spanner G' of G with maximum degree Δ(G') = O(1) and total weight w(G') = O(w(MST(G)). This result is motivated by the topology control problem in wireless ad-hoc networks and improves on existing topology control algorithms along several dimensions. The technical contributions of the paper include a new, sequential, greedy algorithm with relaxed edge ordering and lazy updating, and clustering techniques for filtering out unnecessary edges.
@cite_8: Topology Control (TC) is a well-studied technique used in wireless ad hoc networks to find energy-efficient and or low-interference subgraphs of the maxpower communication graph. However, existing work has the following limitations: (1) the energy model adopted is quite unrealistic - only transmit power is often considered and homogeneous decay of the radio signal with distance is assumed; (2) the interference measure does not account for multi-hop communications. In this paper, we show the dramatic effect of the underlying energy and interference model on TC. In particular, we demonstrate that by using more realistic energy models and considering the effects of multi-hop interference, radically different conclusions about TC can be drawn; namely that (1) energy efficient TC is essentially meaningless, since every link turns out to be "efficient", and that (2) topologies identified as "interference-optimal" in the current literature can be extremely bad from the viewpoint of multi-hop interference. Given these observations, we propose a new measure of link interference, extend it to deal with multi-hop interference, and design a corresponding optimal communication subgraph, called ATASP. We prove that, in the worst case, ATASP coincides with the maxpower communication graph, showing that in some unfortunate situations also performing multi-hop interference-based TC is pointless. However, the simulation results with random node deployments presented in this paper show that, on the average, ATASP is a sparse subgraph of the maxpower communication graph, and multi-hop interference-based TC is indeed possible. Since computing ATASP requires global knowledge, we experiment through simulation with known localized algorithms for energy-efficient TC and show that they perform well (on the average) with respect to multi-hop interference.
Among other attempts to accommodate the irregularities of a real wireless environment in topology control are some that allow for uncertainties in whether or not a nearby node is reachable if the distance to that node is above a certain threshold @cite_3 @cite_15 . However, these algorithms assume that each node can know the distances to other nearby nodes, something that cannot be relied upon in a real environments with multipath effects. Some other works have also considered realistic wireless models but they have only presented centralized algorithms @cite_8 .