Algorithmen für Ad-hoc- und Sensornetze

Sommersemester 2009

Allgemeines

Aktuelles

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

Errata

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.

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.

Literatur

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:

[WW07] D. Wagner, R. Wattenhofer (Eds.). Algorithms for Sensor and Ad Hoc Networks, 2007, Springer LNCS 4621

Alle Termine

Einführung und erste Schritte (22. April:)

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

[AW04] H. Attiya, J. Welch: Distributed Computing Wiley, 2004.
[BST03] C. Busch, S. Surapaneni und S. Tirthapura: Analysis of Link Reversal Routing Algorithms for Mobile Ad Hoc Networks Proc. ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 210-219, 2003.

Geographisches Routing (29. April)

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.

[KSU99] E. Kranakis, H. Singh, J. Urrutia: Compass Routing on geometric networks. In Proceedings of the 11th Canadian Conference on Computational Geometry, 1999
[San05] P. Santi: Topology Control in Wireless Ad Hoc and Sensor Networks. Wiley, 2005
[KWZZ03] F. Kuhn, R. Wattenhofer, Y. Zhang, A. Zollinger: Geometric ad-hoc routing: Of theory and practice. In Proceedings of the 22nd ACM Symposium on Principles of Distributed Computing (PODC'03)

Location Services (6. Mai)

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.

[LJCKM00] J. Li, J. Jannotti,D. S. J. De Couto, D. R. Karger, R. Morris: A scalable location service for geographic ad hoc routing. In: MobiCom '00: Proceedings of the 6th annual international conference on Mobile computing and networking, 2000
[FW06] R. Flury, R. Wattenhofer: MLS: an efficient location service for mobile ad hoc networks. In: Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing

Topologiekontrolle (13. Mai)

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.

[San05] P. Santi: Topology Control in Wireless Ad Hoc and Sensor Networks. Wiley, 2005
[KKKP00] L. Kirouses, E. Kranakis, D. Krizanc, A. Pelc: Power consumption in packet radio networks. In: Theoretical Computer Science 243, 289–305, 2000
[WZ04] R. Wattenhofer, A. Zollinger: XTC: A practical topology control algorithm for ad-hoc networks. In: 18th IEEE Int'l Parallel and Distributed Processing Symposium (IPDPS'04), IEEE Press, 2004
[BRWZ] M. Burhart, P. von Rickenbach, R. Wattenhofer, A. Zollinger: Does Topology Control Reduce Interference?. In Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing (MobiHoc'04), 2004

Lokalisierung, virtuelle Koordinaten und Topologieerkennung (20. Mai)

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?

[OD05] R. O'Dell, R.Wattenhofer: Theoretical aspects of connectivity-based multi-hop positioning. In: Theoretical Computer Science 344:1, pp. 47-68, 2005
[BK93] H. Breu, D.G. Kirkpatrick: Unit Disk Graph Recognition is NP-Hard. In: Computational Geometry. Theory and Applications 9, 1993
[FMW04] F. Kuhn, T. Moscibroda, R. Wattenhofer: Unit Disk Graph Approximation. In: ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), 2004

Routing (3. Juni)

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.

[PR05] C. H. Papadimitriou, D. Ratajczak: On a conjecture related to geometric routing. In: Theor. Comput. Sci., 344(1):3–14,2005
[WWW05] M. Wattenhofer, R. Wattenhofer, P. Widmayer: Geometric Routing without Geometry. In: 12th Colloquium on Structural Information and Communication Complexity (SIROCCO), 2005
[FSC+05] R. Fonseca, S. Ratnasamy, J. Zhao, C. T. Ee, D. Culler, S. Shenker, I. Stoica: Beacon Vector Routing: Scalable Point-to-Point in Wireless Sensornets. In: Proceedings of the Second USENIX Symposium on Networked Systems Design and Implementation (NSDI), 329–342, 2005
[FW07] R. Flury, R. Wattenhofer: Routing, Anycast, and Multicast for Mesh and Sensor Networks. In: 26th Annual IEEE Conference on Computer Communications (INFOCOM), 2007

Datenfluss und -aggregation (10. Juni)

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.

[KLW07] F. Kuhn, T. Locher, R. Wattenhofer: Tight Bounds for Distributed Selection. In: 19th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), 2007
[KMW08] B. Katz, S. Mecke, D. Wagner: Efficient Scheduling of Data Harvesting Trees. In: Proceedings of the 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (ALGOSENSORS), 2008

Network Coding (17. Juni)

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.

[RW04] P. von Rickenbach, R. Wattenhofer: Gathering Correlated Data in Sensor Networks. In: ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), 2004

Clustering (Teil 1: 29./30. Juni, Teil 2: 1. Juli)

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!

[C79] V.Chvatal: A greedy heuristic for the set covering problems. In: Operations Research 4(3), Seiten 233–235, 1979
[SW06] S. Schmid, R. Wattenhofer: Algorithmic Models for Sensor Networks. In: 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 2006 (Invited Paper)
[L85] M. Luby: A simple parallel algorithm for the maximal independent set problem. In: Proc. of the 17th Annual ACM Symp. on Theory of Computing (STOC'85), 1985

MAC/Coloring (Teil 1: 1. Juli, Teil 2: 8. Juli)

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

[GPS87] A. Goldberg, S. Plotkin, G. Shannon: Parallel symmetry-breaking in sparse graphs. In: Proceedings of the nineteenth annual ACM symposium on Theory of computing, 1987

Kapazität und Scheduling (Mittwoch, 8. Juli)

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.

[SW06] S. Schmid, R. Wattenhofer: Algorithmic Models for Sensor Networks. In: 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 2006 (Invited Paper)
[GK00] P. Gupta, P. R. Kumar: The Capacity of Wireless Networks. In: IEEE Transactions onj Information Theory, 46(2), 2000
[M07] T. Moscibroda: The Worst-Case Capacity of Wireless Sensor Networks. In: International Conference on Information Processing in Sensor Networks, 2007

Zeitsynchronisation (Mittwoch, 15. Juli)

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.

[A85] B. Awerbuch: Complexity of network synchronization. In: Journal of the ACM, 32(4):804–823, 1985
[LW06] T. Locher, R. Wattenhofer: Oblivious Gradient Clock Synchronization. In: 20th Int'l Symp. on Distributed Computing (DISC'06), 2006

Paralipomena (Mittwoch, 22. Juli)

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.

[SW06] S. Schmid, R. Wattenhofer: Algorithmic Models for Sensor Networks. In: 14th International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS), 2006 (Invited Paper)
[BW02] C. Bettstetter, C. Wagner: The Spatial Node Distribution of the Random Waypoint Mobility Model. In: Mobile Ad-Hoc Netzwerke, 1. deutscher Workshop über Mobile Ad-Hoc Netzwerke WMAN, 2002
[YLN03] J. Yoon, M. Liu, B. Noble: Random waypoint considered harmful. In: IEEE In Proceedings of the 22nd Annual Joint Conference of the IEEE Computer and Communications Societies (INFOCOM), 2003