FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks

Li, Ning; Hou, Jennifer C.

Permalink

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

Description

Title

FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks

Author(s)

• Li, Ning
• Hou, Jennifer C.

Issue Date

2004-04

Keyword(s)

• Wireless Networks
• Fault Tolerance

Abstract

The development of wireless communication in recent years has posed new challenges in system design and analysis of wireless networks, among which energy efficiency and network capacity are perhaps the most important issues. As such, topology control algorithms have been proposed to maintain network connectivity while reducing energy consumption and improving network. However, by reducing the number of links in the network, topology control algorithms actually decrease the degree of routing redundancy, and hence the topology thus derived is more susceptible to node failures/departures. In this paper, we consider k-vertex connectivity of a wireless network. We first present a centralized greedy algorithm, called Fault-tolerant Global Spanning Subgraph (FGSS), which preserves k-vertex connectivity. FGSS is min-max optimal, i.e., FGSS minimizes the maximum transmission power used in the network, among all algorithms that preserve the k-vertex connectivity. Based on FGSS, we then propose a localized algorithm, called Fault-tolerant Local Spanning Subgraph (FLSS). We formally prove that FLSS preserves k-vertex connectivity while maintaining bi-directionality of the network. We also prove FLSS is min-max optimal among all strictly localized algorithms. Finally, we relax several widely used assumptions for topology control, in FGSS and FLSS so as to enhance their practicality. Simulation results show that FLSS is more power-efficient than other existing distributed/localized topology control algorithms.

Type of Resource

text

Permalink

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

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