Institut für Theoretische Informatik, Algorithmik

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

Allgemeines

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

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.

Ablauf

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.

Vorträge

Vortragender Thema (Betreuer) Ausarbeitung/Folien
Bastian Katz/ Steffen Mecke Einführung Folien
Alle Teilnehmer Kurzvorträge
Andreas Gemsa On the Complexity of Distributed Graph Coloring [1] (SM) Ausarbeitung
Dominic Telaar Locating and Bypassing Holes in Sensor Networks [4] (BK) Ausarbeitung
Florian Merz Routing, Anycast, and Multicast for Mesh and Sensor Networks [3] (SM) Ausarbeitung
Roland Stühmer MLS: An Efficient Location Service for Mobile Ad Hoc Networks [5] (BK) Ausarbeitung
Felix Brandt Landmark Selection and Greedy Landmark-Descent Routing for Sensor Networks [2] (BK) Ausarbeitung
Simon Friedberger An Optimal Bound for the MST Algorithm to Compute Energy Efficient Broadcast Trees in Wireless Networks [6] (SM) Ausarbeitung

Themen und Literatur

Einleitende Literatur

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

Vortragsthemen

[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.

Ergänzende Literatur

zu Thema [2]

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

zu Thema [4]

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

zu Thema [5]

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.