Institut für Theoretische Informatik, Algorithmik

Algorithmen für Ad-hoc- und Sensornetze

Wintersemester 2015/2016

Allgemeines

  • Vorlesungstermine: wöchentlich Donnerstag 15:45-17:15 in Raum 236 (Ausweichtermine: Dienstag 9:45-11:15 Uhr im SR -118 / Montag 9:45-11:15 Uhr im SR -101) [alle Räume im Infobau, Geb. 50.34]
  • Für die Vorlesung werden 5 Leistungspunkte (Credits) vergeben.
  • Die Vorlesung kann in den Modulen IN4INAHSN, IN4INNWA und IN4INAEA im Master Informatik, sowie IW4INAADA und IW4INAALGOB im Master Informationswirtschaft geprüft werden.
  • Die Prüfung findet mündlich nach Ende der Vorlesung statt, die Termine werden rechtzeitig bekanntgegeben.

Aktuelles

Prüfungstermine (mündlich): 9. Februar und 19. Februar. Bei Interesse bei Dr. Fabian Fuchs melden
  • 26.11.15: Ab jetzt regelmäßig donnerstags, Ausweichtermin montags. Übersicht
  • 24.11.15: Achtung, am 26.11 besprechen wir die weiteren Vorlesungstermine!
  • 13.11.15: Am 17. und 19. November findet keine Vorlesung statt
  • 02.11.15: Die Vorlesung am 3. November 9:45 Uhr wird auf 4. November 11:30 Uhr verschoben (Raum 315, Besprechungsraum 3. OG)
  • 26.10.15: Erstes Übungsblatt inkl. Projektcode ist verfügbar
  • 19.10.15: Zur Info: Spätestens am morgen der Vorlesung sollten Inhalte hier verfügbar sein.
  • 07.10.15: Informationen zur Übung eingestellt
  • 01.10.15: Übersicht über (voraussichtliche) Vorlesungs- und Übungstermine eingefügt

Inhalt

buch.jpg Drahtlose Sensornetze bestehen aus einer Vielzahl kleiner Sensorknoten, vollwertiger, aber sehr leistungsarmer Kleinstrechner, die drahtlos miteinander kommunizieren und ihre Umwelt mit Hilfe zumeist einfacher Sensorik beobachten. Die Entwicklung solcher Sensorknoten ist durch immer kleiner und leistungsfähiger Komponenten möglich geworden und hält nicht nur technisch neue Herausforderungen parat: 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.Werbefolie VL Sensornetze

In dieser Vorlesung werden einige der interessantesten Themengebiete auf diesem noch sehr jungen Gebiet vorgestellt. Dabei wird der Schwerpunkt auf den neuartigen kombinatorischen und geometrischen Fragestellungen und Beweistechniken, sowie dem Entwurf verteilter Algorithmen liegen.

Der Inhalt der Vorlesung orientiert sich weitestgehend an den bisherigen Vorlesungen zu Algorithmen für Ad-hoc- und Sensornetze (Sommersemester 2009 und 2012). Auf der damaligen Homepage finden sich zahlreiche Zusatzinformationen zum Umfang und Inhalt der Vorlesung.

Übung

Simulationsoberfläche von Sinalgo Im Rahmen der Übung sollen ausgewählte Algorithmen für Ad-hoc- und Sensornetzwerke im Netzwerksimulator Sinalgo implementiert werden. Der Simulator selbst in Java implementiert und kann damit unabhängig vom Betriebssystem genutzt werden. Der Simulator bietet eine übersichtliche Simulationsoberfläche mittels deren die Algorithmen getestet werden können (siehe rechtes Bild).

Das Setup des Simulators in Eclipse wird im Sinalgo Tutorial behandelt. Pro Übung wird ein „Project“-Ordner zur Verfügung gestellt, der in den Sourcecode des Simulator kopiert werden kann (regular Release herunterladen, dann unter src/projects/). Zur Implementierung der Übungsaufgaben muss und sollte der Simulator selbst nicht erweitert / verändert werden.

Termin Übungsblatt Zusatzmaterial Thema Folien Lösung
27.10 Blatt 1 Sinalgo Projektfiles Einführung, Leader Election Slides Ü1 Lösung
05.11 Blatt 2 Sinalgo Projektfiles Greedy Routing Slides Ü2 Lösung
24.11 Blatt 3 Sinalgo Projektfiles Topology, GR+Facet Routing Slides Ü3 Lösung
03.12 Blatt 4 Sinalgo Projektfiles Lubys MIS siehe VL09 Lösung-MIS Lösung-CDS
17.12 Blatt 5 Beispiele Arduino - RxTx RandColor
17.01 Blatt 6 Sinalgo Simulator für Übung 6 (neu!) SINR und Coloring Slides Ü6

Termine

Termin VL/Ü Thema Folien Druckversion
20.10 VL Einführung & erste Schritte VL01 VL01-P
22.10 VL Geographisches Routing VL02 VL02-P
27.10 Übung siehe oben
29.10 VL Besprechung / Location Services VL03 VL03-P
04.11 VL Topologiekontrolle VL04 VL04-P
05.11 Übung Nachtrag MLS, Ü: Greedy Routing
05.11 VL Vorgeschoben: Lokalisierung VL05 VL05-P
12.11 VL Routing VL06 VL06-P
17.11 - entfällt
19.11 - entfällt
24.11 VL/Übung Topologiekontrolle & Routing
24.11 VL/Übung Data Gathering VL07 VL07-P
26.11 VL Network Coding (Version 2, 01.12) VL08 VL08-P
- - ab hier: nur donnerstags regelmäßig - -
03.12 VL/Übung Clustering + Ü4 VL09 VL09-P
07.12 (Montag) VL Kapazität, Scheduling und Coloring VL10 VL10-P
10.12 VL Rest VL10 und Coloring / Medium Access VL11 VL11-P
- - Übung 6 ist eine überarbeitete Form der VL11
17.12 Ü Arduino
Weihnachten
14.01 VL Synchronisation VL12
18.01 (Montag) Ü SINR und Coloring
21.01 VL Abschluss und Fragerunde VL13