Seminar: Algorithmen für Sensornetze

• Termine: Dienstags 11:30-13:00 bzw. 11:30-14:30 (14.12. und 11.01.)
• Raum: SR 301 im Informatik-Hauptgebäude 50.34
• Betreuung: Dipl.-Math. Steffen Mecke, Frank Schulz, Prof. Dr. Dorothea Wagner,
• Das Seminar findet zusammen mit dem Seminar Algorithmen für Speicherhierarchien statt.
• Der Seminartermin am 1. Februar fällt aus und muss leider ersatzlos gestrichen werden.

Mit der heutigen Hardwaretechnologie ist in den Bereich des Möglichen gerückt, winzige Sensoren zu konstruieren, die neben der eigentlichen Aufgabe als Sensor außerdem Messdaten verarbeiten und über ein drahtloses Netzwerk an benachbarte Sensoren oder Basisstationen senden können. Eine Einführung in drahtlose Sensornetze und ihre Anwendungen sowie Verweise auf weiterführende Literatur sind etwa in [1] zu finden.

Die technische Machbarkeit von solchen Sensornetzwerken hat in den letzten Jahren für ein großes Forschungsinteresse gesorgt. Es stellen sich algorithmische Probleme, die im Prinzip auch schon von Kommunikationsnetzen bzw. Ad-Hoc-Netzen bekannt sind, wie z.B. Routing oder Topologiekontrolle. Aufgrund der technologischen Gegebenheiten von Sensoren sind allerdings neue algorithmische Modelle und Verfahren erforderlich. Wir wollen uns in diesem Seminar mit diesen algorithmischen Fragestellungen beschäftigen, die in vielen unterschiedlichen Teilgebieten der Sensornetzwerke auftreten.

Jede Teilnehmerin und jeder Teilnehmer soll sich weitgehend selbständig in das jeweilige Thema einarbeiten. Neben dem Erarbeiten der Inhalte ist das eigentliche Lernziel des Seminars die Präsentation der Inhalte. Einerseits wird in Absprache mit der Betreuerin oder dem Betreuer ein ausführlicher Vortrag von etwa einer Stunde Dauer vorbereitet, der dann im Rahmen des Seminars gehalten wird. Nach dem Vortrag soll sowohl über Inhaltliches als auch über die Präsentation diskutiert werden.

Andererseits ist eine schriftliche Ausarbeitung zu erstellen, die das Thema zusammenfassend wiedergibt. Darin sollte eine objektive Haltung gegenüber dem errungenen Wissen zum Ausdruck kommen. Die Ausarbeitung muss bis zum Ende der Vorlesungszeit (19.02.2005) fertiggestellt sein. Dafür sollte LaTeX verwendet werden. Für den Einstieg in LaTeX kann diese Einführung hilfreich sein.

Die Themen basieren auf aktuellen Entwicklungen und orientieren sich an englischsprachigen Originalarbeiten. Zu folgenden Aspekten der Sensornetze wurde je ein Vortragsthema vergeben:

Clustering: Oft ist es sinnvoll, mehrere Sensoren zu Clustern bzw. zu einer Hierarchie von Clustern zusammenzufassen.

Lokalisierung: Wie kann (ohne dass jeder Sensor ein GPS dabei hat) die Position eines Sensors bzw. eines wahrgenommenen Objektes bestimmt werden?

Topologiekontrolle: Welche Sensoren sind benachbart und kommunizieren miteinander?

Directed Diffusion: Ein Daten-orientiertes Routingprotokoll, bei dem Anfragen an das Sensornetzwerk nicht direkt an Sensoren addressiert, sondern als Anfrage an das Netwzwerk gestellt werden. Ausserdem werden Daten in den Sensoren geeignet gesammelt und gemeinsam zurückgeschickt.