Files in this item



application/pdfFLSS - A Fault- ... for Wireless Networks.pdf (350kB)
(no description provided)PDF


Title:FLSS: A Fault-Tolerant Topology Control Algorithm for Wireless Networks
Author(s):Li, Ning; Hou, Jennifer C.
Subject(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.
Issue Date:2004-04
Genre:Technical Report
Rights 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).
Date Available in IDEALS:2009-04-14

This item appears in the following Collection(s)

Item Statistics