Options
Self-stabilizing algorithms in wireless sensor networks
Citation Link: https://doi.org/10.15480/882.1426
Publikationstyp
Thesis
Thesis Type
Doctoral Thesis
Publikationsdatum
2017
Sprache
English
Author
Advisor
Referee
Title Granting Institution
Technische Universität Hamburg-Harburg
Place of Title Granting Institution
Hamburg
Examination Date
2017-06-30
Institut
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.
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.
Schlagworte
Wireless sensor networks
Internet of things (IoT)
Cyber physical systems
Self-stabilization
Distributed algorithms
DDC Class
004: Informatik