Institut für Theoretische Informatik, Algorithmik

Algorithmen für Ad-hoc- und Sensornetze

Sommersemester 2012

Allgemeines

Aktuelles

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

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.

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.

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

Termine und Vorlesungsfolien


Einführung und erste Schritte (18. April 2012)

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 (25. April 2012)

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 (2. 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 (9. 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


Efficient Communication in Mobile Ad Hoc Networks (16. Mai)

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


Lokalisierung und virtuelle Koordinaten (23. 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 (30. Mai)

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 (6. 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 (13. 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: 20. Juni, Teil 2: 27. Juni)

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!

[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: 27. Juni, Teil 2: 4. 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 (4. 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 on 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, 18. 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


Abschlussvorlesung (Mittwoch, 18. 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