Please use this identifier to cite or link to this item:
Fulltext available Open Access
Title: Self-stabilizing algorithms in wireless sensor networks
Language: English
Authors: Siegemund, Gerry 
Keywords: Wireless sensor networks; Internet of things (IoT); Cyber physical systems; Self-stabilization; Distributed algorithms
Issue Date: 2017
Examination Date: 30-Jun-2017
Abstract (english): 
The presented dissertation focuses on the applicability of self-stabilizing algorithms in systems using wireless communication.
Especially wireless sensor networks (WSN) which use low power radios that are prone to message loss and corruption.
Furthermore, temporary node failures (e.g., due to exhausted batteries) are common sources of nonconformances. Thus, distributed algorithms, middleware systems, and applications have to respond to these faults. A typical approach is to foresee such error situations and program routines to react to them. Algorithms defined in a self- stabilizing manner (SSA) on the other hand always converge to a defined system state and remain in it while no fault occurs. Hence, the anticipation of error situations is no longer a necessity.
Entities in a distributed system (nodes) share certain informations among their neighborhood (adjacent nodes) and react following the distinct routine of the used SSA. To this day self-stabilization is primarily a theoretical approach, well studied concerning, e.g., the bounds of execution steps. Profound practical evaluation, espe- cially in the presents of rapidly changing neighbor states, as common in WSNs, is still an open issue.
This work firstly establishes necessities to use SSAs in the wireless domain, con- cluding that a certain degree of forced stability concerning a nodes neighborhood is vital. Nevertheless, such a topology control cannot be rigid, e.g., by using a fixed predefined setup, because node additions or removals cannot be supported. Hence, a topology control algorithm (TCA) is introduced, generating a trade-off between forced stability and agility.
Using this TCA as a cornerstone, multiple SSAs are evaluated, and high level al- gorithms are developed, culminating in a publish/subscribe middleware defined in a self-stabilizing fashion. The publish/subscribe system relies on a self-stabilizing spanning tree algorithm and a novel self-stabilizing virtual ring algorithm. Further- more, the publication routing uses shortcuts in the virtual ring, decreasing routing paths in the process.
The presented algorithms are evaluated using simulations employing realistic radio models, as well as implementation on sensor node hardware with low power radios, low computation power, and restricted memory. The novel publish/subscribe system is executable on such limited hardware, uses less messages to deliver data to pub- lishers than a comparable tree-based approach, due to the mentioned shortcuts, and scales well with the network size. It achieves a compromise between the size and maintenance effort for routing tables and the length of routing paths.
Concluding, the dissertation provides an incentive to use self-stabilization algo- rithms in wireless sensor network applications. As shown, even high level systems like a publish/subscribe middleware can be realized with this inherently fault-tolerant approach.
DOI: 10.15480/882.1426
Institute: Telematik E-17 
Document Type: Thesis
Thesis Type: Doctoral Thesis
Advisor: Turau, Volker 
Referee: Nolte, Jörg 
Project: Tolerance-Zone - Fehlertolerante Middleware-Idiome basierend auf selbststabilisierenden Techniken 
License: In Copyright In Copyright
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
DissSubmittedWSNssa.pdf4,63 MBAdobe PDFView/Open
Show full item record

Page view(s)

Last Week
Last month
checked on May 31, 2023


checked on May 31, 2023

Google ScholarTM


Note about this record

Cite this record


Items in TORE are protected by copyright, with all rights reserved, unless otherwise indicated.