Seminar: Algorithmen für Sensornetze

Allgemeines

Inhalt

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.

Termine

Datum Vortragende® Thema Betreuer
02.11. Dorothea Wagner Einführung: Was gehört zu einer erfolgreichen Seminarteilnahme? [pdf]
02.11. Kurzvorträge
16.11. M. K. Clustering mecke
30.11. J. S. Lokalisierung mecke
14.12. M. N. Topologiekontrolle schulz
14.12. M. B. Geometrisches Routing schulz
21.12. S. H. Directed Diffusion schulz
11.01. Speicherhierarchien I
fällt aus Speicherhierarchien II

Allgemeines

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.

Themen

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.

[Clu1] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer:
Initializing Newly Deployed Ad Hoc and Sensor Networks.
10th Annual International Conference on Mobile Computing and Networking (MOBICOM), Philadelphia, USA, September 2004.
[Clu2] Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer:
Radio Network Clustering from Scratch.
12nd Annual European Symposium on Algorithms (ESA), Bergen, Norway, September 2004.

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

[Loc1] Craig Gotsman and Jehuda Koren:
Distributed Graph Layout for Sensor Networks.
12th International Symposium on Graph Drawing, New York City, New York, USA, September 2004.
[Loc2] Nissanka B. Priyantha, Hari Balakrishnan, Erik Demaine, and Seth Teller:
Anchor-Free Distributed Localization in Sensor Networks.
MIT Laboratory for Computer Science, Tech. Report #392, April 2003.

Topologiekontrolle: Welche Sensoren sind benachbart und kommunizieren miteinander?

[Top1] Martin Burkhart, Pascal von Rickenbach, Roger Wattenhofer, Aaron Zollinger:
Does Topology Control Reduce Interference?.
5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Roppongi Hills, Tokyo, Japan, May 2004.
[Top2] Prosenjit Bose, Pat Morin, Ivan Stojmenovi and Jorge Urrutia:
Routing with Guaranteed Delivery in Ad Hoc Wireless Networks.
Wireless Networks 7, pages 609-616, Kluwer, 2001.
[Geo1] Fabian Kuhn, Roger Wattenhofer, Yan Zhang, Aaron Zollinger:
Geometric AdHoc Routing: Of Theory and Practice.
22nd ACM Symposium on the Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, July 2003.
[Geo2] E. Chávez, S. Dobrev, E. Kranakis, J. Opatrny, L. Stacho, and J. Urrutia:
Route Discovery with Constant Memory in Oriented Planar Geometric Networks.
Proceedings of ALGOSENSORS 2004, LNCS 3121, pages 147-156, Springer, 2004.
[Geo3] Christos H. Papadimitriou and David Ratajczak:
On a Conjecture Related to Geometric Routing.
Proceedings of ALGOSENSORS 2004, LNCS 3121, pages 9-17, Springer, 2004.

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.

[Dir1] Chalermek Intanagonwiwat, Ramesh Govindan, and Deborah Estrin:
Directed Diffusion: A Scalable and Robust Communication Paradigm for Sensor Networks.
International Conference on Mobile Computing and Networking (MobiCom 2000), pages 56-67, ACM, 2000.
[Dir2] John Heidemann, Fabio Silva, Chalermek Intanagonwiwat, Ramesh Govindan, Deborah Estrin, and Deepak Ganesan:
Building Efficient Wireless Sensor Networks with Low-Level Naming.
18th ACM Symposium on Operating Systems Principles, ACM, 2001.
[Dir3] Bhaskar Krishnamachari, Deborah Estrin, Stephen Wicker:
Modelling Data-Centric Routing in Wireless Sensor Networks.
Proceedings of the Twenty First International Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM 2002), IEEE, 2002.
[Dir4] Deborah Estrin, Ramesh Govindan, John Heidemann, and Satish Kumar:
Next Century Challenges: Scalable Coordination in Sensor Networks.
International Conference on Mobile Computing and Networks (MobiCom 99), ACM, 1999.
[Dir5] Chalermek Intanagonwiwat, Deborah Estrin, Ramesh Govindan, and John Heidemann:
Impact of Network Density on Data Aggregation in Wireless Sensor Networks.
Proceedings of International Conference on Distributed Computing Systems (ICDCS), July 2002.

Weitere Literatur

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