Algorithmen für Sensornetzwerke
|
 |
|
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
- 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 |
| 20.10.2009 | Betreuer | - | Einführungsvortrag | |
| 01.12.2009 | alle Teilnehmer | alle Betreuer | Kurzvorträge | - |
| 26.01.2010 | Thomas Gramer | Dennis Schieferdecker | Randerkennung | - |
| 26.01.2010 | Moritz v. Looz | Markus Völker | Lokalisierung | - |
| 02.02.2010 | Christof Doll | Markus Völker | Scheduling | - |
| 02.02.2010 | Markus Völker | - | Topologiekontrolle | - |
| 09.02.2010 | Hannes Wächter | Dennis Schieferdecker | Routing | - |
| 09.02.2010 | Dennis Schieferdecker | - | Intrusion Detection | - |
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: 01.12.2009 (neuer Termin!)
- alle Kurzvorträge an einem Termin
- ca. 5 Minuten pro Vortrag
- Ausarbeitungsphase: 7 Wochen
- 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
Yue Wang, Jie Gao, Joseph S.B. Mitchell: Boundary Recognition in Sensor Networks by Topological Methods. 2006.
[2]: Randerkennung II
Dezun Dong, Yunhao Liu, Xiangke Liao: Fine-Grained Boundary Recognition in Wireless Ad Hoc and Sensor Networks By Topological Methods. 2009.
[3]: Lokalisierung
Sol Lederer, Yue Wang, Jie Gao: Connectivity-based Localization of Large Scale Sensor Networks with Complex Shape. 2008. (Journal Version)
[4]: Intrusion Detection
Santosh Kumar, Ten H. Lai, Anish Arora: Barrier Coverage With Wireless Sensors. 2005.
Sergey Bereg, David Kirkpatrick: Approximating Barrier Resilience in Wireless Sensor Networks. 2009.
[5]: Topologiekontrolle
Pascal von Rickenbach, Stefan Schmid, Roger Wattenhofer, Aaron Zollinger: A Robust Interference Model for Wireless Ad-Hoc Networks. 2005.
Martin Fussen, Roger Wattenhofer, Aaron Zollinger: Interference Arises at the Receiver. 2005.
[6]: Scheduling
Olga Goussevskaia, Yvonne Anne Oswald, Roger Wattenhofer: Complexity in Geometric SINR. 2007.
Olga Goussevskaia, Roger Wattenhofer, Magnus M. Halldorsson, Emo Welzl: Capacity of Arbitrary Wireless Networks. 2009.
[7]: Routing I
Qing Fang, Jie Gao, Leonidas J. Guibas: Landmark-Based Information Storage and Retrieval in Sensor Networks. 2006.
Qing Fang, Jie Gao, Leonidas J. Guibas, Vin de Silva, Li Zhang: GLIDER: Gradient Landmark-Based Distributed Routing for Sensor Networks. 2005.
[8]: Routing II
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang: Distance-Sensitive Routing and Information Brokerage in Sensor Networks. 2006. (Journal Version)
Ergänzende Literatur
[1]: Überblicksartikel
Stefan Schmid, Roger 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.