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_26: Most existing topology control algorithms assume homogeneous wireless networks with uniform maximal transmission power, and cannot be directly applied to heterogeneous wireless networks where the maximal transmission power of each node may be different. We present two localized topology control algorithms for heterogeneous networks: Directed Relative Neighborhood Graph (DRNG) and Directed Local Spanning Subgraph (DLSS). In both algorithms, each node independently builds its neighbor set by adjusting the transmission power, and defines the network topology by using only local information. We prove that: 1) both DRNG and DLSS can preserve network connectivity; 2) the out-degree of any node in the resulting topology generated by DRNG or DLSS is bounded by a constant; and 3) DRNG and DLSS can preserve network bi-directionality. Simulation results indicate that DRNG and DLSS significantly outperform existing topology control algorithms for heterogeneous networks in several aspects.
@cite_23: Summary form only given. The XTC ad-hoc network topology control algorithm introduced shows three main advantages over previously proposed algorithms. First, it is extremely simple and strictly local. Second, it does not assume the network graph to be a unit disk graph; XTC proves correct also on general weighted network graphs. Third, the algorithm does not require availability of node position information. Instead, XTC operates with a general notion of order over the neighbors' link qualities. In the special case of the network graph being a unit disk graph, the resulting topology proves to have bounded degree, to be a planar graph, and - on average-case graphs - to be a good spanner.
The Directed Relative Neighborhood Graph (DRNG) protocol @cite_26 removes an edge @math if and only if there exists a path @math such that @math . In the Directed Local Spanning Subgraph (DLSS) protocol @cite_26 , each node creates a local spanning tree from the subgraph induced by itself and its neighbors. A node @math retains the edge @math in the topology-controlled graph if and only if the edge @math exists in the local spanning tree generated at node @math . As proved in @cite_26 , any edge that is removed by DRNG is also removed by DLSS and therefore, DLSS achieves a sparser graph than DRNG. The fewer edges in DLSS often leads to a lower energy consumption, but it can sometimes lead to longer paths and therefore higher energy consumption than DRNG. A generalization of the DRNG protocol is the XTC protocol which was conceived independently and uses the notion of link quality' in making its topology control decision instead of energy costs @cite_23 . When link quality between two nodes is measured by the energy cost of a transmission between them, the XTC protocol reduces to DRNG.