Seite drucken

SelfWISE

Ein Rahmenwerk zur Entwicklung selbststabilisierender Algorithmen

Projektbeschreibung

Fehlertoleranz ist eine wichtige Eigenschaft die hoch verteilte Systeme besitzen sollten. Das Konzept der Selbststabilisierung bietet dabei eine inhärente Toleranz gegenüber temporären Störungen, wie z.B. Veränderung von Nachrichten oder des Speichers. Häufig beschränkt sich die Betrachtung von selbststabilisierenden Algorithmen auf theoretische Problemstellungen. Eine Umsetzung oder Untersuchung unter realen Bedingen, wie z.B. in drahtlosen Netzen, wird nur selten betrachtet.

Das Rahmenwerk SelfWISE ermöglicht die Programmierung von drahtlosen Netzen in selbststabilisierender Weise. Durch die Verwendung von SelfWISE werden die Entwicklung, die Evaluierung und das Debuggen von selbststabilisierenden Algorithmen erheblich vereinfacht. SelfWISE besteht aus einer Sprache die es erlaubt selbststabilisierende Algorithmen zu beschreiben, einer Laufzeitumgebung zur Simulation der Algorithmen und Werkzeugen für die Auswertung.

Durch die Verwendung einer formalen Spezifikationssprache für die Beschreibung der Algorithmen werden systemnahe Einzelheiten abstrahiert, wie die Eigenschaften des drahtlosen Kanals oder andere hardwarespezifische Beschränkungen. Dadurch sind die Details des drahtlosen Netzes versteckt und der Entwickler kann sich auf die Entwicklung von selbststabilisierenden Algorithmen konzentrieren. Da viele solcher Algorithmen für eine serielle Ausführung entwickelt wurden, sind diese nicht direkt ausführbar in einem drahtlosen Netz. Um solche Algorithmen auch in einer verteilten Umgebung zu testen existieren Transformatoren, die die Algorithmen in eine verteilte Version transformieren unter der Beibehaltung ihrer selbststabilisierenden Eigenschaften. SelfWISE bietet eine einfache Schnittstelle solche Transformatoren zu entwickeln und das Verhalten dieser in verschiedenen Szenarien für unterschiedliche Algorithmen zu untersuchen.

Publikationen

Andreas Lagemann, Jörg Nolte, Christoph Weyer und Volker Turau. Mission Statement: Applying Self-Stabilization to Wireless Sensor Networks. In Proceedings of the 8th GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze" (FGSN'09), August 2009, pp. 47–49. Hamburg, Germany.
@InProceedings{Telematik_LNWT_2009_SelfWISE, author = {Andreas Lagemann and Jörg Nolte and Christoph Weyer and Volker Turau}, title = {Mission Statement: Applying Self-Stabilization to Wireless Sensor Networks}, booktitle = {Proceedings of the 8th GI/ITG KuVS Fachgespräch "Drahtlose Sensornetze" (FGSN'09)}, pages = {47-49}, day = {13-14}, month = aug, year = 2009, location = {Hamburg, Germany}, }
Abstract: Long living and unattended deployments of wireless sensor networks requires fault-tolerant solutions. Self-stabilizing algorithms are providing these properties in an elegant and verifiable way. Recently, a lot of research has been performed to determine appropriate means to apply these promising technique to wireless sensor networks. In this paper the current state of the art in this field is given. Additionally, three major challenges are presented for achieving self-stabilizing sensor networks.
Christoph Weyer, Volker Turau, Andreas Lagemann und Jörg Nolte. Programming Wireless Sensor Networks in a Self-Stabilizing Style. In Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSORCOMM'09), Juni 2009. Athens, Greece.
@InProceedings{Telematik_WLT_2009_SelfWISE, author = {Christoph Weyer and Volker Turau and Andreas Lagemann and Jörg Nolte}, title = {Programming Wireless Sensor Networks in a Self-Stabilizing Style}, booktitle = {Proceedings of the Third International Conference on Sensor Technologies and Applications (SENSORCOMM'09)}, day = {18-23}, month = jun, year = 2009, location = {Athens, Greece}, }
Abstract: Wireless Sensor Networks (WSNs) operate in an unstable environment and thus are subject to arbitrary transient faults. Self-stabilization is a promising technique to add tolerance against transient faults in a self-contained non-masking way. A core factor for the applicability of a given self-stabilizing algorithm is its convergence time. This paper analyses the average stabilization time of three algorithms commonly regarded as central building blocks for WSNs. The analysis is accomplished with SelfWISE, a framework providing programming abstractions for selfstabilizing algorithms. The performed analysis considers the target models as well as network size and density. This demonstrates the usability of SelfWISE for evaluating selfstabilizing algorithms under a wide range of models.
Christoph Weyer und Volker Turau. SelfWISE: A Framework for Developing Self-Stabilizing Algorithms. In Proceedings of the 16th ITG/GI - Fachtagung Kommunikation in Verteilten Systemen (KiVS'09), März 2009, pp. 67–78. Kassel, Germany.
@InProceedings{Telematik_TW_2009_SelfWISE, author = {Christoph Weyer and Volker Turau}, title = {SelfWISE: A Framework for Developing Self-Stabilizing Algorithms}, booktitle = {Proceedings of the 16th ITG/GI - Fachtagung Kommunikation in Verteilten Systemen (KiVS'09)}, pages = {67-78}, day = {2-6}, month = mar, year = 2009, location = {Kassel, Germany}, }
Abstract: This paper introduces SelfWISE, a framework for enabling wireless sensor networks to be programmed in a self-stabilizing manner. The framework eases the formal specification of algorithms by abstracting from low-level details such as wireless channel and hardwarespecific characteristics. SelfWISE consists of a language for expressing self-stabilizing algorithms, a runtime environment for simulating algorithms in wireless sensor networks, and supporting tools. The hereby applied transformation of formally described algorithms into the simulation environment preserves the self-stabilizing properties. Development, evaluation, and debugging of self-stabilizing algorithms is considerably facilitated by utilizing SelfWISE.

Studentische Arbeiten

Abgeschlossene Arbeiten