Topology control for fault-tolerant communication in wireless ad hoc networks

Abstract

Problemstellungen bei der Entwicklung zukünftiger drahtloser Ad-hoc und Sensor-Netzwerke. Topology Control ist ein Basisdienst (low-level Service) der die Kommunikation zwischen den Teilnehmern regelt. Daher ist Topology Control einer der Hauptangriffspunkte zur Verbesserung der Energieeffizienz und des Netzwerkzusammenhangs (Connectivity). Wir präsentieren einen Topologie Konstruktionsalgorithmus für energieeffiziente und fehlertolerante multi-hop Kommunikation in einem zweigeteilten Netz, das aus einer großen Anzahl an Funkknoten und wenigen Schnittstellenknoten (Gateway-Knoten) besteht. (Schnittstellenknoten sind zB. zuständig für den Datenaustausch mit anderen Netzwerken.) Unter Verwendung von lokaler Information wie zB. dem Knotenabstand oder der Kanaldämpfung zwischen den Knoten erstellt und wartet unser Algorithmus einen k-regulären Graphen mit niedrigem Energieverbrauch. Der konstruierte Graph verwendet die minimale Anzahl an Verbindungen, is k-fehlertolerant und hält die Auswirkung von Fehlern lokal (failure locality). Die Topologie Konstruktion passt sich automatisch an Änderungen im Netz an, konvergiert und kann effizient erstellt werden. Als Nebenprodukt erzeugt der Algorithmus eine Hierachie von Clustern welche die Knotendichte im Netzwerk repräsentiert und fehlertolerante Kommuniktion zwischen beliebigen Clustermitgliedern garantiert.<br />

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.