Title: Robust self-organizing pulse synchronization in wireless sensor networks
Language: English
Authors: Leidenfrost, Robert 
Qualification level: Diploma
Keywords: Selbstorganisation; Selbststabilisierung; biologisch inspirierte Algorithmen; fehlertolerante verteilte Uhrensynchronisation; Puls-Synchronisation; Drahtlose Sensornetzwerke
self-organization; self-stabilization; biologically inspired algorithms; fault-tolerant distributed clock synchronization; pulse synchronization; wireless sensor networks
Advisor: Elmenreich, Wilfried
Issue Date: 2009
Number of Pages: 126
Qualification level: Diploma
Abstract: 
Die enormen Fortschritte verschiedenster Technologien erfordern und ermöglichen es, dass komplizierte Architekturen in kleinere und lose gekoppelte Einheiten zerlegt werden, welche überschaubarer und kontrollierbarer sind. Ein sinnvoller Austausch und Vergleich von Beobachtungen unter diesen Einheiten erfordert die Übereinstimmung der lokalen Zeit aller Einheiten mit einer systemweiten gemeinsamen Zeitbasis. Dies ist auch eine wichtige Voraussetzung für die Implementierung von Fehlertoleranz durch Replikation und gilt neben verdrahteten verteilten Systemen ebenso für drahtlose Sensornetzwerke.
Zusätzlich haben Knoten innerhalb von drahtlosen Sensornetzwerken hohe Anforderungen an die effiziente Nutzung von Ressourcen und benötigen folglich ein energieeffizientes Kommunikationsprotokoll. Dies wird für gewöhnlich durch synchronisierte Schlaf-Wach-Phasen erreicht. Als Folge ist Uhrensynchronisation eine unabdingbare Notwendigkeit in nahezu allen verteilten Systemen um Komponierbarkeit, Zuverlässigkeit und zeitliche Koordination zu erreichen.
Diese Arbeit basiert auf einen allgemein bekannten, fehlertoleranten, verteilten Uhrensynchronisationsalgorithmus, welcher für die Anwendung in drahtlosen Sensornetzwerken modifiziert und erweitert wurde. Der modifizierte Algorithmus verbindet die Vorteile zweier unterschiedlicher Ansätze, sodass schlussendlich Selbststabilisierung in fehlerfreien Netzwerken und eine hohe Synchronisationsgenauigkeit in fehlerbehaftete Netzwerken in der Anwesenheit von maximal fSelbststabilisierung im generellen Sinne beschreibt dabei die Eigenschaft eines Systems, sich selbst aus einem beliebigem Ausgangszustand in einen definierten Endzustand, also die Synchronisation aller Einheiten, zu versetzen. Der Algorithmus funktioniert weiters auch in unstrukturierten Multi-hop Netzwerken durch Ausnützung der hohen Redundanz der Kommunikationsverbindungen.
Verschiedenste Simulationsergebnisse in Bezug auf unterschiedliche Netzwerktopologien werden diskutiert und zeigen, dass eine annehmbare Konvergenzzeit und eine hohe netzwerkweite Synchronisationsgenauigkeit bei gleichzeitig niedriger Nachrichtenkomplexität und großen zeitlichen Verzögerungen der Nachrichtenübertragungen erreicht werden kann.

Tremendous advance in technology requires and allows us to build complex architectures by decomposing it into smaller manageable and loosely coupled components. The meaningful exchange and comparison of observations among these components then requires a system wide agreement on a common notion of time. This is, for example, an important issue in the case fault tolerance is implemented by replication. Whereas many wired distributed systems provide enough capabilities in order to achieve agreement, Wireless Sensor Networks demand much higher standards of the available energy resources and consequently necessitate an energy-efficient communication protocol. This is usually achieved by synchronized sleep-wakeup schedules. As a consequence, clock synchronization in complex distributed systems is inevitable to provide composability, dependability, and temporal coordination.
This thesis presents a well-studied and simple fault-tolerant distributed clock synchronization algorithm which was modified for the use in sensor networks and extended in order to be self-stabilizing, i.e., independent of the initial configuration, all devices eventually become synchronized. In other words, the presented approach combines the advantage of two different synchronization algorithms. In detail, whereas the convergence to a synchronized system state is ensured in the fault-free case, synchronicity is maintained even in the presence of at most f
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-36958
http://hdl.handle.net/20.500.12708/11762
Library ID: AC07806289
Organisation: E182 - Institut für Technische Informatik 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

12
checked on Feb 18, 2021

Download(s)

64
checked on Feb 18, 2021

Google ScholarTM

Check


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