Algorithmen für Ad-hoc- und Sensornetze

• Dozent: Dr. rer. nat. Bastian Katz
• Vorlesung: Wöchentlich mittwochs 14:00-15:30 Uhr im SR 301 vom 22.04.2008 bis 22.07.2008

• 27. Juli: Die Folien der letzten Vorlesung sind online, zukünftige Verbesserungen an Folien werden unter Errata aufgeführt.

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.

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, Druckversion, v03, 24. April '09 (4 Folien/Seite)
• Foliensatz Nachspielzeit VL01, Druckversion, v02, 30. April '09 (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, Druckversion, v03, 30. April '09 (4 Folien/Seite)
• Foliensatz Nachspielzeit VL02, Druckversion, v01, 30. April '09 (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, Druckversion v03, 7. Mai '09 (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, Druckversion v02, 15. Mai '09 (4 Folien/Seite)

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, Druckversion v02, 31. Mai '09 (4 Folien/Seite)
• Foliensatz Nachspielzeit VL05, Druckversion v02, 5. Juni '09 (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, Druckversion v02, 5. Juni '09 (4 Folien/Seite)
• Foliensatz Nachspielzeit VL06, Druckversion v02, 12. Juni '09 (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, Druckversion v04, 22. Juni '09 (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, Druckversion v03, 22. Juni '09 (4 Folien/Seite)

Eine 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 auch nur 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, Druckversion, v03, 6. Juli '09 (4 Folien/Seite)
• Foliensatz Update zu VL09, Druckversion, v02, 6. Juli '09 (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, Druckversion v03, 13. Juli '09 (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, Druckversion v03, 13. Juli '09 (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, Druckversion v02, 21. Juli '09 (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, Druckversion v02, 27. Juli '09 (4 Folien/Seite)
• Das Video zur Erkennung natürlicher Cluster mit Hilfe von Randerkennung findet man auf der Homepage von Alexander Kröller (unter 2006)