University of Illinois Urbana-Champaign

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

Li, Ning; Hou, Jennifer C.

Content Files
FLSS - A Fault-Tolerant Topology Control Algorithm for Wireless Networks.pdf

Permalink

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

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
Date of Ingest
2009-04-14T20:51:32Z
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
Genre of Resource
Technical Report
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

Research and Tech Reports - Computer Science PRIMARY