35/2004 : Fault Tolerant Communication Topologies for Wireless Ad Hoc Networks

RR Number

35/2004

Conference

1st Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS'04)

Author(s)

Bernd Thallner

Abstract

We present a construction of a fixed node-degree overlay network that facilitates efficient fault-tolerant multi-hop communication in large-scale distributed systems: Given a weighted graph where the weight of an edge represents the cost of a connection, the constructed subgraph is $mydelta$-regular, $mydelta$-node connected, ensures failure locality, and has low total weight. Moreover, there is a distributed algorithm for constructing this subgraph, which adapts to dynamic changes of the environment, is guaranteed to converge, and exhibits good average case performance as well. As a by-product, our construction builds a hierarchy of clusters that reflects the node density in the network, with guaranteed and localized fault-tolerant communication between any pair of cluster members. It is hence well suited for both establishing fault-tolerant communication topologies and clustering in wireless sensor networks, and for constructing robust overlay graphs in peer-to-peer systems.

Bibtex

@article{ thallner:2004-35,
  author =       "Bernd Thallner",
  title =        "Distributed Construction of Fault-Tolerant Overlay Networks",
  journal =      "1st Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS'04)",
  year =         "2004",
  month =        "Jun."
}

Download

Get diwans04.pdf - Adobe PDF-format, (116.77 KB; posted at October 24 2005)