Implementierung von Clustering-Algorithmen in der Wiselib

Themengebiet

Sensornetzwerke haben sich in den letzten Jahren als Forschungsgebiet etabliert. So sind verschiedene Arten von Sensorknoten im Handel erhältlich, die allerdings in der Hardwareausstattung stark variieren. So läuft der ScatterWeb MSB Knoten mit einem MSP430 mit 48kB ROM und 10kB RAM, wohingegen der iMote2 über 32MB ROM und 32MB RAM verfügt. Ahnlich vielfältig sind die Betriebssysteme, die auf den Sensorknoten eingesetzt werden. Auf dem MSB können sowohl die eigene, frei erhältliche ScatterWare als auch das bekannte Contiki benutzt werden. Der iMote2 lässt sogar die Installation eines Embedded Linux zu.

Ein Problem, das eine solche Vielfalt mit sich bringt, ist das Entwickeln von Anwendungen (bzw. Algorithmen), da ein einmal implementierter Algorithmus nicht ohne Weiteres auf eine andere Plattform (bzw. ein anderes OS) portiert werden kann.

Die Wiselib soll solche Portierungsproblem lösen, in dem sie ein Entwicklungsframework bietet, mit dem Algorithmen einmal implementiert werden und dann ohne Änderung des Sourcecodes für verschiedene Plattformen kompiliert werden können. Dabei kommen moderne Softwareentwicklungstechniken zum Einsatz, um eine möglichst effiziente Umsetzung für die jeweiligen Plattformen zu gewährleisten.

So wird die Wiselib in C++ entwickelt und benutzt durchgehend Templates, um den erforderlichen Performanzgewinn zu erzielen. Dieser Ansatz wurde schon erfolgreich in Bibliotheken wie der STL, CGAL oder Boost eingesetzt, kam bisher aber noch nicht in eingebetteten Systemen zum Einsatz.

Aufgabenstellung

In dieser Arbeit sollen für die Wiselib beispielhaft zwei Clustering-Algorithmen implementiert werden und testweise auf verschiedenen Systemen evaluiert werden (zumindest auf unserem hauseigenen Testbed und dem Simulator Shawn). Im Anschluss daran soll auf den erzeugten Clustern ein Routingalgorithmus entwickelt und implementiert werden.

Bei den zu implementierenden Clusteringprotokollen handelt es sich um LEACH, ein randomisiertes Verfahren, das 1-hop-Cluster erzeugt und REED (Robust Energy-Efficient Distributed clustering), das vor allem auf k-Fehlertoleranz ausgelegt ist. Vor der Implementierung sollen die Anforderungen an die Schnittstelle zum darunterliegenden OS identifiziert werden.

Arbeitsschritte

• Einlesen und Verstehen der zu implementierenden Clustering-Algorithmen
• Ausarbeitung der Anforderungen an die Schnittstelle zum unterliegenden OS
• Implementierung der Algorithmen
• Evaluation auf Testbed und Shawn
• Dokumentation der Arbeit

Voraussetzungen

Folgende Kenntnisse sind zum erfolgreichen Abschluss dieser Arbeit erforderlich. Es ist wünschenswert, wenn zumindest grundlegende Kenntnisse vorhanden sind. Zumindest jedoch sollten die Fähigkeit und der Wunsch vorhanden sein, dieses Wissen autodidaktisch zu erlangen.

• C++-Kenntnisse, insbesondere Erfahrungen mit Templates
• Erfahrungen im Umgang mit Mikrocontrollern
• Umgang mit Versionskontrolle Subversion

Links

• Wiselib
• Shawn
• LEACH
• REED

Weiterführende Literatur

• Survey on Clustering in Sensor Networks
• ACE: An Emergent Algorithm for Highly Uniform Cluster Formation
• HEED: A Hybrid, Energy-Efficient, Distributed Clustering Approach for Ad-hoc Sensor Networks