Institut für Theoretische Informatik, Algorithmik

Algorithmen für Sensor- und Ad Hoc-Netze

Allgemeines

Einführung

Mit der heutigen Hardwaretechnologie ist in den Bereich des Möglichen gerückt, winzige Sensoren zu konstruieren, die neben der eigentlichen Aufgabe als Sensor außerdem Messdaten verarbeiten und über ein drahtloses Netzwerk an benachbarte Sensoren oder Basisstationen senden können. Die technische Machbarkeit von solchen Sensornetzwerken hat in den letzten Jahren für ein großes Forschungsinteresse gesorgt. Es stellen sich algorithmische Probleme, die im Prinzip auch schon von Kommunikationsnetzen bzw. Ad-Hoc-Netzen bekannt sind, wie z.B. Routing oder Topologiekontrolle. Wir wollen uns in dieser Vorlesung mit solchen algorithmischen Fragestellungen beschäftigen, die in vielen unterschiedlichen Teilgebieten der Sensor- und Ad-Hoc-Netze auftreten.

Vorlesung

Datum Thema Folien Literatur
12.04. Einführung in Sensor- und Ad-Hoc-Netze [MR03]
19.04. Verteilte Algorithmen - Grundlagen pdf4x1 [AW04]
26.04. Minimum Spanning Trees pdf4x1 [GHS83]
03.05. Dominating Set - robustes PTAS pdf4x1 [M+95, NH04]
10.05. Dominating Set - verteilter Algorithmus pdf4x1 [KW03]
17.05. Topologiekontrolle und Interferenz [MSVG02]
24.05. Topologiekontrolle und Interferenz [BRWZ05, RSWZ05]
31.05. Topologiekontrolle und Interferenz
07.06. Routing: Link Reversal pdf4x1 [GB81,BST03]
14.06. Geometrisches Routing pdf4x1 [KSU99,KWZ02]
21.06. Geometrisches Routing pdf4x1
28.06. Lokalisierung [GK04, KMW04]
05.07. Lokalisierung [MOWW04, BGJ05]

Verfügbare Folien komplett (Teil I): pdf4x1, pdf

Verfügbare Folien komplett (Teil III): pdf4x1, pdf

Übungen

Nr. Ausgabe Abgabe Besprechung PDF Sonstiges
0 13.04. pdf
1 19.04. 26.04. 27.04. pdf
2 03.05. 10.05. 11.05. pdf
3 17.05. 24.05. 25.05. pdf pdf
4 31.05. 07.06. 08.06. pdf
5 14.06. 21.06. 22.06. pdf pdf
6 28.06. 05.06. 06.06. pdf

Weiterführende Literatur

[AW04] H. Attiya, J. Welch: Distributed Computing. Wiley, 2004.
[CLR97] T. H. Cormen, C. E. Leiserson und R. L. Rivest Introduction to Algorithms. MIT Press, 1997.
[PSI90] F. P. Preparata und M. I. Shamos: Computational Geometry. Springer, 1990.
[BGJ05] J. Bruck, J. Gao und A. A. Jiang:
Localization and Routing in Sensor Networks by Local Angle Information. Proc. 6th ACM Int. Symp. on Mobile Ad Hoc Networking and Computing (MOBIHOC), Urbana-Champaign, Illinois, USA, May 2005.
[BRWZ05] M. Burkhart, P. von Rickenbach, R. Wattenhofer und A. Zollinger.
Does Topology Control Reduce Interference? Proc. 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing (MOBIHOC), Roppongi Hills, Tokyo, Japan, May 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.
[GB81] Eli M. Gafni und Dimitri P. Bertsekas:
Distributed Algorithms for Generating Loop-Free Routes in Networks with Frequently Changing Topology. IEEE Transactions on Communications, 29:1, 1981.
[GHS83] R. G. Gallager, P. A. Humblet, und P. M. Spira:
A Distributed Algorithm for Minimum-Weight Spanning Trees.
ACM Transactions on Programming Languages and Systems 5:1, 66-77, 1983.
[GK04] C. Gotsman und Y. Koren:
Distributed Graph Layout for Sensor Networks. Proc. International Symposium on Graph Drawing, New York, September 2004.
[KMW04] F. Kuhn, T. Moscibroda und R. Wattenhofer:
Unit Disk Graph Approximation. Proc. ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004.
[KSU99] E. Kranakis, H. Singh und Jorge Urrutia:
Compass Routing on Geometric Networks.
Canadian Conference on Computational Geometry, 51-54, 1999.
[KW03] F. Kuhn und R. Wattenhofer:
Constant-Time Distributed Dominating Set Approximation.
Proceedings 22nd ACM Symposium on Principles of Distributed Computing (PODC), Boston, Massachusetts, USA, Juli 2003.
[KWZ02] F. Kuhn, R. Wattenhofer und Aaron Zollinger:
Asymptotically Optimal Geometric Mobile Ad-Hoc Routing.
Dial-M'02, September 2002.
[M+95] M. V. Marathe, H. Breu, H.B. Hunt III, S. S. Ravi, und D. J. Rosenkrantz:
Simple Heuristics for Unit Disk Graphs. Networks 25, 59–68, 1995.
[MOWW04] T. Moscibroda, R. O'Dell, M. Wattenhofer und R. Wattenhofer:
Virtual Coordinates for Ad hoc and Sensor Networks. Proc. of the ACM Joint Workshop on Foundations of Mobile Computing (DIALM-POMC), Philadelphia, Pennsylvania, USA, October 2004.
[MR03] Friedemann Mattern und Kay Römer:
Drahtlose Sensornetze. GI Informatik-Lexikon, 2003.
[MSVG02] F. Meyer auf der Heide, C. Schindelhauer, K. Volbert und M. Grünewald:
Energy, congestion and dilation in radio networks. SPAA '02: Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures
[NH04] T. Nieberg und J. L. Hurink:
A PTAS for the minimum dominating set problem in unit disk graphs. Memorandum No. 1732, University of Twente, 2004.
[RSWZ05] P. von Rickenbach, S. Schmid, R. Wattenhofer und A. Zollinger:
A Robust Interference Model for Wireless Ad-Hoc Networks. Proc. 5th International Workshop on Algorithms for Wireless, Mobile, Ad Hoc and Sensor Networks (WMAN), Denver, Colorado, USA, April 2005.
[LW98] Annegret Liebers und Dorothea Wagner:
Kurzskripte Algorithmen und ihre Laufzeit, Begriffe zu Graphen, Die Komplexitätsklassen //P, NP// und //NPC//. Universität Konstanz, 1998.