Deutsch

Drahtlose Sensornetzwerke (WSN) ermöglichen eine Vielzahl neuartiger Anwendungen, e.g. im Körper eingebettete Messdatenerfassung, Lebensraumerforschung und Beobachtung von Ozeandaten. Dennoch haben diese Netzwerke andere Anforderungen als konventionelle Systeme. Selbst-Konfiguration, energieeffizienter Betrieb, Kollaboration und Datenverarbeitung innerhalb des Netzwerkes sind Beispiele für wichtige Anforderungen. Um diesen Anforderungen gerecht zu werden, spielt die Systemsoftware eines Sensorknotens eine grundlegende Rolle: Sie sollte nützliche Abstraktionen zur Verfügung stellen, um die Entwicklung von Anwendungen zu ermöglichen, und gleichzeitig mit den beschränkten Ressourcen eines Sensorknotens haushalten können. Das Spektrum der möglichen Anwendungen eines Sensorknotens beinhaltet verschiedenartige Aufgaben wie Uhrensynchronisation, Datensammlung, Signalverarbeitung und Datenfusion. Der traditionelle Ansatz auf diesem Gebiet ist es Betriebssystemkonzepte mit dramatisch reduziertem Funktionsumfang anzubieten. In dieser Arbeit präsentieren wir jedoch einen alternativen Ansatz. Unser Betriebssystem ermöglicht potenziell beliebige Funktionalität, welche sich dynamisch an das aktuelle Anforderungsprofil anpasst. Die Grundidee ist es Dienste anzubieten, die über ein Cluster von Knoten verteilt sind, anstatt ein ganzes System auf einem Knoten auszuführen. Kooperation ist das Schlüsselwort um komplexe Aufgaben auf ressourcenbeschränkten Sensorknoten auszuführen. Unser Betriebssystem unterstützt Kooperation unter benachbarten Knoten mit Hilfe des Konzeptes verteilter Dienste. Dafür entwickeln wir eine biologisch inspirierte Heuristik verantwortlich für die Platzierung der Dienste im Sensornetzwerk. Wir entwickelten zwei Versionen der Heuristik mit unterschiedlicher Komplexität und Leistung. Beide arbeiten vollständig verteilt und basieren auf lokalen Informationen und Regeln. Die für die Organisation der Dienste nötige Kommunikation wird mit Hilfe von Stigmergy realisiert. Im zweiten Teil dieser Arbeit stellen wir zwei Clustering-Heuristiken vor, die den Netzwerkgraphen in verbundene Untergraphen (genannt Cluster) aufteilen. Jeder Cluster beinhaltet dann eine vollständige Instanz des Betriebssystems und der Anwendung. Durch die Aufteilung des Netzwerks in Cluster wird der Organisationsaufwand reduziert, da Protokolle, die auf globaler Information beruhen, auf ein einzelnes Cluster beschränkt sind. Dieses verbessert die Skalierbarkeit eines Systems. Das Clustering-Problem wird Minimum-Intrakommunikations-Kosten-Clustering genannt. Die Idee dahinter ist, dass eine minimale Menge von Ressourcen in einem Cluster vorhanden sein muss und die Cluster wohl-verbunden sind. Die erste Heuristik ist für Netzwerke mit einem geringen Maß an Topologieveränderungen geeignet, die zweite dagegen für Netzwerke mit mäßig vielen Veränderungen. Beide Heuristiken basieren auf dem Prinzip der Arbeitsteilung sozialer Insekten. Wir evaluieren unsere Heuristiken mit Hilfe des Shox-Simulators für drahtlose Netzwerke. Die Dienstverteilungsheuristik war in der Lage sehr gute Zuordnungen, nahe dem Optimum, für die meisten Experimente zu erzeugen. Unsere Clusteringheuristik für Systeme mit wenigen Topologieveränderungen übertrifft eine existierende Heuristik (Expanding Ring) im Hinblick auf die Kosten in den meisten Fällen. Sie war in der Lage Cluster zu erzeugen, die maximal im Durchschnitt 1,42 mal das Optimum in allen simulierten Szenarios waren. Ferner weisen die Ergebnisse eine geringe Standardabweichung auf. Die Heuristiken können auf verschiedene Art und Weise erweitert werden. Um die Last, die dem Clusterhead auferlegt wird, besser zu verteilen, kann das Emergente Clustering um eine Clusterhead-Rotation erweitert werden. Darüber hinaus kann eine weitere Verhandlungsphase am Ende der Heuristik eingesetzt werden um ihre Leistung zu verbessern. Über diese Punkte hinaus ist es unser Ziel das Konzept unseres Betriebssystems mit dem Kontrollscript-Mechanismus aus virtuellen Maschinen für WSNs zu kombinieren. Dieses wird eine einfache Entwicklung datenzentrischer Skripte ermöglichen, die die umfangreiche Funktionalität unserer verteilten Dienste nutzen um noch komplexere Aufgaben zu bewältigen.

English

Wireless sensor networks (WSN) enable a myriad of new applications, e.g. human-embedded sensing, habitat exploration and ocean data monitoring. Nevertheless, they have different requirements from conventional systems. Self-configuration, energy-efficient operation, collaboration and in-network processing are examples of important requirements. In order to achieve these requirements, the system software of a sensor node plays a fundamental role: it should provide useful abstractions to enable the development of the applications and at the same time comply with the constrained resources of the sensor nodes. The range of possible applications in a sensor node covers distinct tasks like clock synchronization, data acquisition, signal processing and data fusion. The traditional approach in this area is to provide operating system concepts with dramatically reduced functionality. In this work, we present an alternative approach. Our OS provides potentially arbitrary functionality that dynamically adapts to the actual profile of requirements. The basic idea is to offer services that are distributed over a cluster of nodes instead of having the entire system on each node. Cooperation is the keyword to achieve complex tasks using the restricted sensor nodes. Our operating system (OS) supports this cooperation among neighboring nodes using the concept of distributed services. We are combining the typical OS functionality with the middleware one. Our system is responsible to coordinate the migration and placement of those services. For that, we develop a biologically inspired heuristic responsible to drive the placement of the services in theWSN.We develop two version of the heuristic, with different complexity and performance. Both are completely distributed and based on local information and local rules. The communication necessary for organizing the services is done by means of stigmergy. Further, we present two clustering heuristics responsible to decompose the network graph into connected sub-graphs (called clusters). Each cluster will hold a complete instance of the OS and application. With the network divided in clusters, the organization overhead is reduced, since protocols that rely on some global information are restricted to a single cluster. This enhances the scalability of the system. The clustering problem is called minimum intracommunication-cost clustering. The idea is that a minimum amount of resources must be present in each cluster and the clusters should be well connected. The first heuristic is able to handle networks with low topology changes, whereas the second can deal with moderate changes. Both heuristics rely on the principle of division of labor in social insects. We evaluate our heuristics using the Shox wireless network simulator. The service distribution heuristics were able to produce very good assignments, near to the optimal, for most experiments. Our clustering heuristic for systems with low topology changes outperforms an existing heuristic (expanding ring) in term of cost for most cases. It was able to produce clusters that were, at most, in average 1.43 times the optimal for all simulated scenarios. Moreover, the results have low standard deviation. Several enhancements can be done in our heuristics. In order to better distribute the burden imposed on the clusterhead, clusterhead rotation may be included in the emergent clustering. Moreover, an additional negotiation phase at the end of the heuristic may be included to improve the performance of the heuristic. Moreover, we aim to combine the concept of our OS with the control script mechanism present in virtual machines for WSN. This will enable a straightforward development of data-centric scripts that use the extensive functionality of our distributed services to achieve complex goals.