Seminar: Algorithmen für Ad-hoc- und Sensor-Netze

• Betreuung: Prof. Dr. Bastian Katz, Dipl.-Math. Steffen Mecke, Prof. Dr. Dorothea Wagner
• Vorbesprechung: Dienstag, 17. April, 11:30 Uhr

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. Dafür sollte LaTeX verwendet werden.

[0] Friedemann Mattern und Kay Römer: Drahtlose Sensornetze. GI Informatik-Lexikon, 2003.

[1] Fabian Kuhn, Roger Wattenhofer: On the Complexity of Distributed Graph Coloring. PODC 2006.
[2] A Nguyen, N Milosavljevic, Q Fang, J Gao, LJ Guibas: Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks. IEEE INFOCOM 2007 (to appear)
[3] Roland Flury, Roger Wattenhofer: Routing, Anycast, and Multicast for Mesh and Sensor Networks. INFOCOM 2007.
[4] Q Fang, J Gao, LJ Guibas: Locating and Bypassing Holes in Sensor Networks. Mobile Networks & Applications 2006.
[5] Roland Flury, Roger Wattenhofer: MLS: An Efficient Location Service for Mobile Ad Hoc Networks. Mobihoc 2006.
[6] Christoph Ambühl: An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks. ICALP 2005.

Q Fang, J Gao, LJ Guibas, V de Silva, L Zhang: GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. MobiCom 2000.

B Karp, HT Kung: Greedy Perimeter Stateless Routing for Wireless Networks. MobiCom 2000.

J Li, J Jannotti, DSJ De Couto, DR Karger, R Morris: A Scalable Location Service for Geographic Ad Hoc Routing. MobiCom 2000.
I Abraham, D Dolev, D Malkhi: LLS: a Locality Aware Location Service for Mobile Ad Hoc Networks. MobiCom 2000.