Algorithmen für Ad-hoc- und Sensornetze

• Dozenten: Dr. Markus Völker, Prof. Dr. Dorothea Wagner
• Vorlesung: Wöchentlich mittwochs 14:00-15:30 Uhr im SR 301 (Infobau Geb. 50.34) vom 18.04.2012 bis 18.07.2012

• Die Vorlesung am 11.07.2012 wurde auf den 18.07.2012 verschoben. Am 18.07.2012 findet daher eine Doppelvorlesung statt.

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.

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 der Vorlesung zu Algorithmen für Ad-hoc- und Sensornetze die im Sommersemester 2009 gehalten wurde. Auf der damaligen Homepage finden sich zahlreiche Zusatzinformationen zum Umfang und Inhalt der Vorlesung.

Die Vorlesung baut lose auf dem Buch [WW07] auf. Ergänzende Literatur findet sich bei den einzelnen Vorlesungen. Wer seine algorithmischen Grundlagen auffrischen möchte, dem seien die Kurzskripte unseres Lehrstuhls empfohlen:

• Algorithmen und ihre Laufzeit
• Begriffe der Graphentheorie
• Die Komplexitätsklassen P, NP und NPC

In dieser Vorlesung werden wir nach einem kleinen Überblick über Sensornetze und ihre Anwendungen erste Algorithmen für Sensornetze kennenlernen.

• Foliensatz VL01, Version 1, 18. April 2012 (4 Folien/Seite)

Bekannte Knotenpositionen und der enge Zusammenhang zwischen Positionen und Vernetzung in Sensornetzen hat mit dem Geographischen Routing ein eigenes Routingparadigma ermöglicht, das wir in dieser Vorlesung kennenlernen werden.

• Foliensatz VL02, Version 2, 25. April 2012 (4 Folien/Seite)

Georouting ist ein relativ einfaches Mittel, Nachrichten an einen Zielknoten zu schicken, dessen geographische Position bekannt ist. Was aber, wenn man Knoten anhand einer ID auffinden muss, zum Beispiel, weil sie sich bewegen? Eine Infrastruktur, die so eine Positionsanfrage beantwortet, heißt Location Service. In dieser Vorlesung werden wir zwei ähnliche, aber an entscheidender Stelle voneinander abweichende Verfahren kennenlernen, die so eine Infrastruktur bieten.

• Foliensatz VL03, Version 2, 2. Mai 2012 (4 Folien/Seite)

Topologiekontrolle ist die Kunst, ein Kommunikationsnetz auf das Wichtigste zu beschränken. Durch Beschränken der Sendeleistung oder gezieltes Auswählen von aktiven Kanten kann man Energie sparen, besser routen oder Interferenz minimieren.

• Foliensatz VL04, Version 1, 9. Mai 2012 (4 Folien/Seite)

Gastvortrag von Prof. Christos Zaroliagis, University of Patras. Nähere Informationen gibt es auf der Ankündigungsseite unseres Forschungsseminars.

Viele Algorithmen in Sensornetzen nutzen Knotenpositionen auf die eine oder andere Weise. Was ist, wenn die nicht einfach zur Verfügung stehen? Was verrät das Netz über die Positionen, was kann man aus lokalen Messungen schließen?

• Foliensatz VL05, Version 1, 23. Mai 2012 (4 Folien/Seite)

Routing in drahtlosen Netzen setzt nicht immer die Kenntnis oder Rekonstruktion von Knotenpositionen voraus. In dieser Vorlsung lernen wir drei Algorithmische Ideen kennen, die sich aus der Betrachtung von Sensornetzen für das Routing entwickelt haben.

• Foliensatz VL06, Version 1, 30. Mai 2012 (4 Folien/Seite)

Die Aufgabe von echten Sensornetzen besteht oft nicht aus sehr viel mehr als dem Problem, Daten aus dem Netz zur Senke zu bringen. Was aussieht wie eine relativ klare Anforderung, teilt sich aber in sehr viele unterschiedliche, zum Teil voneinander abhängige Probleme auf, abhängig von der Art und Regelmäßigkeit des Datenflusses, von der Optimierungsebene und von den Annahmen an die Kommunikation. In dieser Vorlesung werden wir nur einen Teil der Aspekte wirklich vertiefen können, darüber hinaus aber hoffentlich einen breiten Blick auf alle Facetten werden können.

• Foliensatz VL07, Version 2, 18. Juli 2012 (4 Folien/Seite)

Network Coding bezeichnet Verfahren, die Datenströme kombinieren, um Energie oder Zeit zu sparen. Die Idee, Datenströme nicht nur getrennt zu betrachten, eröffnet neue Möglichkeiten auch beim Einsammeln der Daten mit verlustfreier Aggregation, wenn also Daten verschiedener Sensoren korrelieren.

• Foliensatz VL08, Version 1, 13. Juni 2012 (4 Folien/Seite)

Eines der meistzitierten Ziele in Sensornetzen ist die Selbstorganisation. Oft gibt es viel mehr Knoten, als man für eine Aufgabe braucht, und für viele Zwecke bietet es sich dann an, Knoten lokal um einen Knoten zu gruppieren. Diese Clusterheads übernehmen dann die Koordination mit dem Rest des Netzes und verteilen ggf. die Aufgaben innerhalb der Gruppe. Gute Mengen von Clusterheads lassen sich leicht charakterisieren, aber sie verteilt und schnell zu approximieren ist keine leichte Aufgabe in allgemeinen Graphen. Wir werden sehen, wie man dabei Eigenschaften von Sensornetzen ausnutzen kann!

• Foliensatz VL09 (Teil 1), Version 2, 18. Juli 2012 (4 Folien/Seite)
• Foliensatz VL09 (Teil 2), Version 1, 27. Juni 2012 (4 Folien/Seite)

In Sensornetzen kann Kommunikation oft nicht gleichzeitig stattfinden: Signale würden so interferieren, dass die Empfänger nicht mehr in der Lage sind, sie zu dekodieren. Auf dem MAC (Medium Access Layer) wird versucht, solche Effekte zu verhindern, indem sich Knoten entweder geschickt verhalten, wenn sie eine Nachricht absetzen wollen (Mithören, auf Freigabe warten) oder indem Übertragungen in einem Zeitraster geplant werden. In erster Näherung wurden (und werden) solche Probleme, Knoten oder Übertragungen nichtinterferierend auf Zeitslots aufzuteilen, als Färbungsprobleme modelliert. Wir werden einen schönen Algorithmus zum verteilten Lösen solcher Probleme kennenlernen

• Foliensatz VL10 (Teil 1), Version 1, 27. Juni 2012 (4 Folien/Seite)
• Foliensatz VL10 (Teil 2), Version 1, 4. Juli 2012 (4 Folien/Seite)

Graphenbasierte Modelle für Interferenz haben große Vorteile. Sie erlauben es, verteilte ALgorithmen zu formulieren, ohne allzuviel Rücksicht auf die vielleicht unbekannte Geometrie nehmen zu müssen. Gleichzeitig macht sie das unrealistisch. In dieser Vorlesung werden wir uns anderen Modellen für Interferenz widmen, vom Protokollmodell bis zum SINR-Modell. Dabei wird sich auch die Natur der Probleme ändern, die man in solchen Modellen noch algorithmisch lösen kann.

• Foliensatz VL11, Version 1, 4. Juli 2012 (4 Folien/Seite)

Eigentlich ist Kommunikation in Sensornetzen hochgradig asynchron. Um trotzdem synchrone Algorithmen laufen zu lassen, gibt es nur zwei Möglichkeiten: entweder wir emulieren die Runden, in denen synchrone Algorithmen ablaufen mit asynchroner Kommunikation, oder wir versuchen, die Uhren der Knoten synchron zu halten. Beide Probleme sind algorithmisch sehr interessant.

• Foliensatz VL12, Version 1, 18. Juli 2012 (4 Folien/Seite)

Ein letztler Blick zurück, wir werden noch einmal den Zusammenhang zwischen verschiedenen Modellen klären, die wir kennengelernt haben und einen kurzen Blick auf fehlende Aspekte, wie die Mobilität von Netzen werfen. Zum Abschluss gibt es dann noch ein paar Hinweise für die Prüfungen.

• Foliensatz VL13, Version 1, 18. Juli 2012 (4 Folien/Seite)