Algorithmen für Sensornetzwerke

  • Typ: Seminar
  • Lehrstuhl: Prof. Dr. Peter Sanders, Prof. Dr. Dorothea Wagner
  • Ort:

    SR 131, Geb. 50.34

  • Zeit:

    Dienstag 9:45 - 11:15 Uhr

  • Beginn: 20.10.2009
  • Dozent:

    D. Schieferdecker, M. Völker

  • SWS: 2
  • LVNr.: 24374
  • Prüfung:

    nein

Seminar Algorithmentechnik (WS09/10)

Algorithmen für Sensornetzwerke

 

Allgemeines

  • Betreuer: Bastian Katz, Dennis Schieferdecker, Markus Völker
  • Vorbesprechung: Dienstag, 20. Oktober 2009, 09:45 in SR 131, Informatikgebäude am Fasanengarten (50.34)
  • Teilnahme: Die Teilnehmerzahl ist voraussichtlich auf acht Personen beschränkt.

 

Aktuelles

  • 09. März 2010: Seminarscheine können im Sekretariat von Prof. Sanders (Raum 218) abgeholt werden
  • 24. Februar 2010: Fertige Ausarbeitungen und Vorträge online gestellt
  • 07. Januar 2010: Raumverlegung am 19.01.10 nach Raum -120
  • 03. Dezember 2009: Termin für Vortrag von Bastian Katz hinzugefügt ( 19.01.10 )
  • 23. November 2009: Termin Kurzvorträge verschoben auf Mittwoch, 02.12.09, 09:45, Raum 315
  • 22. Oktober 2009: Links zu Material hinzugefügt
  • 20. Oktober 2009: Teilnehmer und Termine eingetragen
  • 19. Oktober 2009: Termine und Vortragsthemen aktualisiert
  • 16. Oktober 2009: Vortragsthemen und Material aktualisiert
  • 03. Juli 2009: Seminar-Seite online gestellt

 

Inhalt

Drahtlose Sensornetzwerke haben sich in den letzten Jahren zu einem sehr aktiven Forschungsgebiet entwickelt. Ein solches Sensornetz besteht aus einer Vielzahl kleiner Sensorknoten, die drahtlos miteinander kommunizieren und ihre Umwelt mit Hilfe ihrer Sensorik beobachten können. Ihre Entwicklung stellt die Forscher nicht nur vor neue technische Herausforderungen: Drahtlose Sensornetze lassen sich mit keinem vorhandenen Berechnungsmodell zufriedenstellend abbilden, und durch den engen Zusammenhang von Geometrie und der Vernetzung stellen sich neuartige algorithmische, geometrische und graphentheoretische Probleme.

 

Voraussetzungen

Voraussetzung für die Teilnahme an diesem Seminar sind grundlegende Kenntnisse aus der Algorithmentechnik. Kenntnisse aus der Vorlesung Algorithmen für Ad-hoc- und Sensornetze sind nützlich, werden aber nicht vorausgesetzt. Da alle zu bearbeitenden Artikel auf Englisch vorliegen, sollten entsprechende Englisch-Kenntnisse vorhanden sein (Vortrag und Ausarbeitung erfolgt auf Deutsch).

 

Geplante Themen

  • Randerkennung
  • Lokalisierung
  • Intrusion Detection
  • Topologiekontrolle
  • Scheduling
  • Routing

 

vorläufige Vortragstermine

Termin Vortragender Betreuer Thema Ausarbeitung Folien
20.10.2009  Betreuer  -  Einführungsvortrag  -  PDF
02.12.2009  alle Teilnehmer  alle Betreuer  Kurzvorträge  -  -
19.01.2010  Bastian Katz  -  t.b.a.  -  -
26.01.2010  Thomas Gramer  Dennis Schieferdecker  Randerkennung  PDF  PDF
26.01.2010  Moritz v. Looz  Markus Völker  Lokalisierung  PDF  -
02.02.2010  Christof Doll  Markus Völker  Scheduling  PDF  PDF
02.02.2010  Markus Völker  -  Topologiekontrolle  PDF  -
09.02.2010  Hannes Wächter  Dennis Schieferdecker  Routing  PDF  PDF
09.02.2010  Dennis Schieferdecker  -  Intrusion Detection  PDF  -

 

Organisatorisches

Die Vorbesprechung findet am Dienstag, den 20. Oktober 2009, um 09:45 Uhr in Raum 131 im Informatikgebäude am Fasanengarten (50.34) statt. Die Verteilung der Themen findet in der ersten Veranstaltung statt. Für weitere Informationen könnt Ihr euch gerne an Dennis Schieferdecker oder Markus Völker wenden.

 

 

Geplanter Ablauf:

  • Vergabe der Themen: 20.10.2009
  • Einarbeitungsphase: 6 Wochen
  • Kurzvorträge aller Teilnehmer: 02.12.2009, 09:45, Raum 315 (neuer Termin und Raum!)
    • alle Kurzvorträge an einem Termin
    • ca. 5 Minuten pro Vortrag
  • Ausarbeitungsphase: 7 Wochen
  • Zusatzvortrag: 19.01.2010, 09:45, Raum -120 (neuer Raum!)
  • Endvorträge: ab 26.01.2010 (neuer Termin!)
    • 2 Vorträge pro Termin
    • 30 Minuten pro Vortrag + 15 Minuten Diskussion
  • Abgabe der Ausarbeitung: bis 13.02.2010 (Vorlesungsende)
    • 10 Seiten

 

Ablauf

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 dem Betreuer ein ausführlicher Vortrag von etwa 45 Minuten Dauer vorbereitet, der dann im Rahmen des Seminars gehalten wird. Nach dem Vortrag soll sowohl über Inhaltliches als auch über die Präsentation diskutiert werde.

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.

 

Literatur

Literatur für die Vortragsthemen

[1]: Randerkennung I
Y. Wang, J. Gao, J. S. B. Mitchell: Boundary Recognition in Sensor Networks by Topological Methods. 2006.

[2]: Randerkennung II
D. Dong, Y. Liu, X. Liao: Fine-Grained Boundary Recognition in Wireless Ad Hoc and Sensor Networks By Topological Methods. 2009.

[3]: Lokalisierung
S. Lederer, Y. Wang, J. Gao: Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape. 2008.
(Journal Version)

[4]: Intrusion Detection
S. Kumar, T. H. Lai, A. Arora: Barrier Coverage With Wireless Sensors. 2005.
S. Bereg, D. Kirkpatrick: Approximating Barrier Resilience in Wireless Sensor Networks. 2009.

[5]: Topologiekontrolle
P. v. Rickenbach, S. Schmid, R. Wattenhofer, A. Zollinger: A Robust Interference Model for Wireless Ad-Hoc Networks. 2005.
M. Fussen, R. Wattenhofer, A. Zollinger: Interference Arises at the Receiver. 2005.

[6]: Scheduling
O. Goussevskaia, Y. A. Oswald, R. Wattenhofer: Complexity in Geometric SINR. 2007.
O. Goussevskaia, R. Wattenhofer, M. M. Halldorsson, E. Welzl: Capacity of Arbitrary Wireless Networks. 2009.

[7]: Routing I
Q. Fang, J. Gao, L. J. Guibas: Landmark-Based Information Storage and Retrieval in Sensor Networks. 2006.
Q. Fang, J. Gao, L. J. Guibas, V. Silva, L. Zhang: GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. 2005.

[8]: Routing II
S. Funke, L. J. Guibas, A. Nguyen, Y. Wang: Distance-Sensitive Routing and Information Brokerage in Sensor Networks. 2006.
(Journal Version)

Ergänzende Literatur

[1]: Überblicksartikel
S. Schmid, R. Wattenhofer: Algorithmic Models for Sensor Networks. 2006.

 

Material & Links

Vorlagen

[1]: LaTeX Folien-Vorlage (Stand: 29.10.09)
Vorlage für das LaTeX-beamer Paket im KIT-Stil.

[2]: Powerpoint Folien-Vorlage
Vorlage für Powerpoint-Folien im KIT-Stil.

[2]: Ausarbeitungs-Vorlage
Vorlage für die Ausarbeitung im LNCS-Stil.

freie Software

[1]: ipe
Freies Vektorgrafikprogramm unter Linux.

[2]: Microsoft Visio (MSDN AA an der Universität Karlsruhe)
Für Studenten über MSDN-AA frei verfügbares Zeichenprogramm.