Localized Topology Control in Wireless Networks

Li, Ning

Permalink

https://hdl.handle.net/2142/11046 Copy

Description

Title

Localized Topology Control in Wireless Networks

Author(s)

Li, Ning

Issue Date

2005-08

Keyword(s)

wireless networks

Abstract

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.

Type of Resource

text

Permalink

http://hdl.handle.net/2142/11046

Copyright and License Information

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the University of Illinois at Urbana-Champaign Computer Science Department under terms that include this permission. All other rights are reserved by the author(s).

Owning Collections