In Proceedings of the 2002 IEEE africon, 6th AFRICON CONFERENCE IN AFRICA, Volume 1, 2-4 October 2002, University of Pretoria in George, South Africa, 273-276: paper.
1st Workshop on Dependability Issues in Wireless Ad Hoc Networks and Sensor Networks (DIWANS'04), June 2004, Florence, Italy: paper.
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 delta-regular, delta-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.
In Proceedings of the third International Workshop on Intelligent Solutions in Embedded Systems (WISES 2005), May 2005, Hamburg, Germany: paper.
Abstract: Energy efficiency and fault-tolerance are the most important issues in the development of next-generation wireless ad hoc and sensor networks. Topology control as a low level service (typically below the traditional layer structure) governs communication among all nodes and is hence the primary target for saving energy and increasing connectivity. We present a topology construction algorithm for energy-efficient and fault-tolerant multi-hop communication in a two-tier network consisting of a huge number of wireless nodes and a few gateway nodes (e.g. base stations responsible for exchanging data with other networks). Using only local information, like distance/channel attenuation to neighbors, our fully distributed algorithm efficiently constructs and continuously maintains a k-regular overlay graph with low overall transmission power, which uses the minimal number of links, is k-node-connected and ensures failure locality. It automatically adapts to a dynamically changing environment, is guaranteed to converge, and exhibits good average case performance as well. As a by-product, our algorithm 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.
2nd ACM/SIGMOBILE Workshop on Dependability (DIWANS 2006), Issues in Wireless Ad Hoc Networks and Sensor Networks, Los Angeles, USA, September 2006, co-located with ACM Mobicom 2006: paper.
Abstract: This paper presents a proven correct implementation of a distributed topology construction algorithm based upon agreement on minimal-weight clusters for creating a delta-regular, delta-node connected fault-tolerant communication network. It adapts to crashing nodes, moving nodes and changing communication cost and is guaranteed to converge. We analyze the requirements imposed upon the system model by this class of agreement-based algorithms and show that our implementation works in asynchronous distributed systems augmented with unreliable failure detectors.
Abstract: Fault-tolerant communication and energy efficiency are important requirements for future-generation wireless ad hoc networks, which are increasingly being considered also for critical application domains like embedded systems in automotive and aerospace. Topology control, which enables multi-hop communication between any two network nodes via a suitably constructed overlay network, is the primary target for increasing connectivity and saving energy here. In this paper, we present a fault-tolerant distributed topology control algorithm that constructs and continuously maintains a k-regular and k-node-connected overlay for energy-efficient multi-hop communication. As a by-product, it also 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. The construction algorithm automatically adapts to a dynamically changing environment, is guaranteed to converge, and exhibits good performance as well.
Authors: Bernd Thallner, Heinrich Moser and Ulrich Schmid
Springer Netherlands, Wireless Networks, Volume 16, Number 2 / Februar 2010, DOI: 10.1007/s11276-008-0139-9, ISSN: 1022-0038 (Print), ISSN: 1572-8196 (Online), SpringerLink