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

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.

• 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

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.