Topology control algorithms have been proposed to maintain network connectivity while improving energy efficiency and increasing network capacity. However, by reducing the number of links in the network, topology control algorithms actually decrease the degree of routing redundancy. As a result, the derived topology is more susceptible to node failures or departures. In this paper, we resolve this problem by enforcing k-vertex connectivity in the topology construction process. We propose a fully localized algorithm, fault-tolerant local spanning subgraph (FLSS), that can preserve k-vertex connectivity and is min-max optimal among all strictly localized algorithms (i.e., FLSS minimizes the maximum transmission power used in the network, among all strictly localized algorithms that preserve k-vertex connectivity). It can also be proved that FLSS outperforms two other existing localized algorithms in terms of reducing the transmission power. We also discuss how to relax several widely used assumptions in topology control to increase the practical utility of FLSS. Simulation results indicate that, compared with existing distributed/localized fault-tolerant topology control algorithms, FLSS not only has better power-efficiency, but also leads to higher network capacity. Moreover, FLSS is robust with respect to position estimation errors.

A fully connected network topology is critical to many fundamental operations in wireless ad hoc networks. We study the problem of deploying additional wireless nodes to improve the connectivity of an existing wireless network. Given a disconnected network, we consider the connectivity improvement (CI) problem, i.e., how to deploy as few additional nodes as possible so that the augmented network is connected. We first prove the NP-completeness of CI, and then present a Delaunay triangulation-based algorithm, connectivity improvement using Delaunay triangulation (CIDT). We discuss several variations of CIDT, and propose two additional optimization techniques to further improve the performance. Finally, we demonstrate the effectiveness of CIDT, and compare the performance of its variations via J-Sim simulation.

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.

In this paper, we present a minimum spanning tree (MST)-based algorithm, called local minimum spanning tree (LMST), for topology control in wireless multihop networks. In this algorithm, each node builds its LMST 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 unidirectional links. Simulation results show that LMST can increase the network capacity as well as reduce the energy consumption.

Previous work on topology control usually assumes homogeneous wireless nodes with uniform transmission ranges. In this paper, we propose two localized topology control algorithms for heterogeneous wireless multihop networks with nonuniform transmission ranges: directed relative neighborhood graph (DRNG) and directed local minimum spanning tree (DLMST). In both algorithms, each node selects a set of neighbors based on the locally collected information. We prove that (1) the topologies derived under DRNG and DLMST preserve the network connectivity; (2) the out degree of any node in the resulting topology by DLMST is bounded; while the out degree of nodes in the topology by DRNG is not bounded; and (3) the topologies generated by DRNG and DLMST preserve the network bi-directionality.

Topology control algorithms usually reduce the number of links in a wireless network, which in turn decreases the degree of connectivity. The resulting network topology is more susceptible to system faults such as node failures and departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized algorithm, Fault-tolerant Global Spanning Subgraph (FGSSk), which preserves k-vertex connectivity. FGSSk is min-max optimal, i.e., FGSSk minimizes the maximum transmission power used in the network, among all algorithms that preserve k-vertex connectivity. Based on FGSSk, we propose a localized algorithm, Fault-tolerant Local Spanning Subgraph (FLSSk). It is proved that FLSSk preserves k-vertex connectivity while maintaining bi-directionality of the network, and FLSSk is min-max optimal among all strictly localized algorithms. We then relax several widely used assumptions for topology control to enhance the practicality of FGSSk and FLSSk. Simulation results show that FLSSk is more power-efficient than other existing distributed/localized topology control algorithms.

The power-efficient broadcast for multi-hop wireless networks is discussed in this paper. We first investigate the trade-off between (i) using larger transmission power to reach more nodes in one hop and (ii) using smaller power and relaying broadcast messages through multiple hops. Analysis indicates that multi-hop broadcast is more power-efficient if /spl alpha/ /spl ges/ 2.2, where the power consumption model is P(r, /spl alpha/) = c/sub 0/ /spl middot/ r/sup /spl alpha// + c/sub 1/. Based on the analysis, we propose broadcast on local minimum spanning tree (BLMST). An underlying topology is first derived using local minimum spanning tree (LMST), a localized topology control algorithm. Broadcast messages are then simply relayed through the derived topology in a constrained flooding fashion. BLMST is fully localized, scalable, and power-efficient. Simulation results show that the performance of BLMST is comparable to that of existing centralized algorithms.

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.