Algorithmen für Sensor- und Ad Hoc-Netze
Allgemeines
- Dozenten: Prof. Dr. Dorothea Wagner, Frank Schulz
- Betreuer: Dipl.-Math. Steffen Mecke
- Vorlesung: Wöchentlich dienstags 11.30-13.00 in SR 301 (Info)
vom 12.04. bis 12.07.2005 - Übung: 14-täglich mittwochs 11.30-13.00 in SR -108 (Info)
vom 13.04. bis 13.07.2005
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] |
Übungen
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. |