Topology control algorithms allow each node in a wireless multi-hop network to adjust the power at which it makes its transmissions and choose the set of neighbors with which it communicates directly, while preserving global goals such as connectivity or coverage. This allows each node to conserve energy and contribute to increasing the lifetime of the network. In this paper, in contrast to most previous work, we consider (i) both the energy costs of communication as well as the amount of available energy at each node, (ii) the realistic situation of varying rates of energy consumption at different nodes, and (iii) the fact that co-operation between nodes, where some nodes make a sacrifice by increasing energy consumption to help other nodes reduce their consumption, can be used to extend network lifetime. This paper introduces a new distributed topology control algorithm, called the Cooperative Topology Control with Adaptation (CTCA), based on a game-theoretic approach that maps the problem of maximizing the network's lifetime into an ordinal potential game. We prove the existence of a Nash equilibrium for the game. Our simulation results indicate that the CTCA algorithm extends the life of a network by more than 50 compared to the best previously-known algorithm. We also study the performance of the distributed CTCA algorithm in comparison to an optimal centralized algorithm as a function of the communication ranges of nodes and node density.
Traditional topology control algorithms such as Small Minimum-Energy Communication Network (SMECN) @cite_9 , Minimum Spanning Tree (MST) @cite_27 , DRNG @cite_35 , DLSS @cite_35 and STC @cite_25 usually start the topology control process with each node transmitting at its maximum transmission power to discover all of its neighbors. Local neighborhood and power-level information is next exchanged between neighbors. The minimum transmission power of each node such that the graph is still connected is later computed at each node without further communication between nodes. The Weighted Dynamic Topology Control (WDTC) @cite_3 algorithm improves upon the work of MST, and considers the remaining energy of each node in addition to the energy cost of communication across each pair of nodes. The algorithm, however, forces bidirectional communication between each pair of nodes and, in addition, requires periodic communication by each node at its maximum possible power level. Other related algorithms seek to offer a robust topology where the graph can stand multiple channel failures; for example, a @math -connected graph is sought in @cite_19 @cite_6 and a two-tiered network in @cite_26 .
@cite_35 @cite_26 @cite_9 @cite_3 @cite_6 @cite_19 @cite_27 @cite_25
2090407537 2003012549 2114600896 1597141356
In this paper a new energy-aware weighted dynamic topology control (WDTC) algorithm is proposed to extend the lifetime of wireless network and balance the nodes’ energy consumption. The idea is that each node builds its local minimum spanning tree (MST) based on the energy-aware weighted graph and the network topology is adjusted accordingly. It was proved theoretically that the topology under WDTC algorithm could preserve the network connectivity and a sufficient condition for the degree of no more than 6 was also given. Simulation shows that WDTC algorithm can effectively prolong the network lifetime and has good topological features. 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. The STC algorithm avoids the use of GPS devices and also makes no assumptions about the distance and direction between neighboring nodes. 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. 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. In this paper, we present a minimum spanning tree (MST) based topology control algorithm, called local minimum spanning tree (LMST), for wireless multi-hop networks. In this algorithm, each node builds its local minimum spanning tree independently and only keeps on-tree nodes that are one-hop away as its neighbors in the final topology. We analytically prove several important properties of LMST: (1) the topology derived under LMST preserves the network connectivity; (2) the node degree of any node in the resulting topology is bounded by 6; and (3) the topology can be transformed into one with bidirectional links (without impairing the network connectivity) after removal of all uni-directional links. These results are corroborated in the simulation study.