Teilprojekt A1
From GRK-Wiki
zum übergeordneten Forschungsbereich
Contents |
Opportunistisches Routing in dichten drahtlosen Multihop-Netzen
Konventionelle Routing-Protokolle für drahtlose Multihop-Netze basieren auf Modellen der drahtgebundenen Kommunikation: Entweder besteht zwischen zwei Knoten ein Link (die Knoten sind miteinander verbunden), oder es besteht kein Link (die Knoten sind nicht miteinander verbunden). Dabei wird eine wesentliche Eigenschaft des drahtlosen Mediums ignoriert, dass nämlich in Wirklichkeit alle Knoten miteinander verbunden sind – jedoch in graduell unterschiedlicher Qualität. In vielen (aber nicht in allen) Fällen wird ein verschicktes Paket nicht nur vom Next-hop-Knoten empfangen, sondern sogar von einem Nachfolgeknoten auf dem Pfad von der Quelle zum Ziel. Wie weit ein Paket bei einer einzelnen Übertragung weitergeleitet wird, lässt sich effektiv nicht vorhersagen, da die Qualität der Links sich dynamisch ändert und vielen Einflüssen unterliegt. Opportunistisches Routing besagt, dass ein Knoten seine Daten gleichzeitig an eine Vielzahl von Next-hop-Kandidaten unter Ausnutzung des natürlichen Broadcasts der physikalischen Ebene schickt. Abhängig von den bei der Übertragung herrschenden aktuellen Umständen werden einige der Kandidaten das Paket empfangen und andere nicht – jedoch in nicht vorhersehbarer Weise. Kann nun aus der Menge der erfolgreichen Empfängerknoten derjenige ermittelt werden, der dem Ziel am nächsten ist, so sollte dieser das Paket weiterleiten. Die Zwischenknoten werden also, immer abhängig vom konkreten Einzelfall, einfach übersprungen. Dies führt zu einer Reduktion der durchschnittlichen Pfadlänge und damit einer kürzeren Übertragungszeit im Vergleich zu konventionellen Routing-Protokollen.
Stand des Wissens
Opportunistische Routing-Protokolle erinnern auf den ersten Blick an intelligentes Fluten (network flooding), wie z. B. in LAR [1]. ExOR ist ein erster Versuch, die Robustheit des Flutens mit der Effizienz des Unicast-Routings zu kombinieren [2]; jedoch sind zurzeit noch keine Implementierungen von ExOR erfolgt. Die Resultate in [2] basieren auf Simulationen, deren zugrunde liegende Annahmen noch zu diskutieren wären, speziell für den Fall dichter Netze mit hoher Interferenz. Multipath-Routing-Techniken, wie z. B. von Ganesan u. a. vorgestellt [3], versuchen ebenfalls mehrere Routen parallel zu nutzen, um die Robustheit und vielleicht sogar die Geschwindigkeit der Paketweiterleitung zu erhöhen, nutzen dabei jedoch nicht explizit die parallelen Übertragungen aus, die durch den Broadcast-Charakter des drahtlosen Mediums gegeben sind. Floyd [4] inspirierte den Slotted-ACK-Mechansimus von [2], der zur Sicherung der Multicast-Übertragung dient (explizite Bestätigung eines empfangenen Pakets durch einen zuvor unbekannten Empfänger). Unbekannt ist noch, ob sich in dichten Netzen, z. B. im innerstädtischen Bereich, überhaupt nennenswerte Einsparungen in Form kürzerer Pfade durch opportunistische Routing-Verfahren erzielen lassen.
Vorarbeiten der beteiligten Wissenschaftler
Mehrjährige umfangreiche Forschungsarbeiten auf dem Gebiet der selbstorganisierenden Netze existieren in der Arbeitsgruppe Rechnerorganisation und Kommunikation (M. Malek) [5], sowie in der Arbeitsgruppe Systemarchitektur, deren Leiter J.-P. Redlich bis zur Berufung im Sommer 2004 beim Forschungslabor der Firma NEC in Princeton/USA maßgeblich an der Erforschung selbstorganisierender Zugangsnetze beteiligt war und mehrere Projekte leitete [6], [7], [8], [9], [10] [11]. Über das vom Lehrstuhl Systemarchitektur (J.-P. Redlich) betriebene Projekt Berlin Roof Net [12] ist die Erprobung neuer Routing-Protokolle an einem realen System möglich.
Geplante Arbeiten
Zunächst soll eine Übersicht über alternative Routing/Forwarding-Technologien für drahtlose Multihop-Netze erstellt werden. Anschließend sind Routing-Protokolle, die von der zeitweisen Existenz schwacher Links profitieren, z. B. in Anlehnung an [2] zu entwerfen. Diese Protokolle sollen durch Simulation (vergl. Teilprojekt B2) und später durch Experimente im Berlin Roof Net bezüglich ihrer Leistungsfähigkeit bewertet werden. Außerdem sollen Auswirkungen auf traditionelle Transportprotokolle, insbesondere TCP und UDP, untersucht werden. Mobilität, die über das gelegentliche Umpositionieren von Knoten hinausgeht, ist kein Schwerpunkt dieses Themas.
Referenzen
[1] Y.-B. Ko, V. Nitin: Location-Aided Routing (LAR) in mobile networks. ACM/IEEE MobiCom, October 1998.
[2] S. Biswas, R. Morris: Opportunistic Routing in Multi-Hop Wireless Networks. ACM SIGCOMM Computer Communication Review Vol 34(1), pp. 69-74, Jan 2004.
[3] D. Ganesan, R. Govindan, S. Shenker, D. Estrin: Heighly resilient, energy-efficient multipath routine in wireless sensor networks. ACM Mobile Computing and Communications Review, 5(4), October 2001.
[4] S. Floyd, V. Jacobson, C. Liu, L. Zhang: A reliable multicast framework for light-weight sessions and application level framing. IEEE/ACM Transactions on Networking, 5(6), 1997.
[5] M. Malek, N. Milanovic, A. Davidson, V. Milutinovic: Routing and Security in Mobile Ad Hoc Networks. IEEE Computer, February 2004.
[6] R. D. Gitlin, K. Kim, J.- P. Redlich, E. Shim: Load-Balancing in the Wireless Internet. NEC-Internal REPORT, Report No: 2003-L055, May 2003.
[7] Z. Haas, J.- P. Redlich: SOSAETI- Self-Organizing, Secure, wireless Access nETwork Infrastructure. NEC-Internal REPORT, Report No: 2004-L010, March 2004.
[8] J. -P. Redlich, M. Suzuki, S. B. Weinstein: Creating IP Services for Organizations Implementing Customized Services at the Network Edge, International Conference on Applications of the Internet in Business and Education, Minsk, Belarus, June 2000.
[9] S. Ali, J.- P. Redlich, N. Simonovski, S. B. Weinstein: A Field Trial of Transparent Wired/Wireless Access Using GuestIP, and of Conference-Oriented Media Services. NEC-Internal REPORT, Report No: 2000-C032, January 2001.
[10] T. Kühnel, W. Müller, J. P. Redlich: Multi-ISP Controlled Public Internet Access, Based on Third-Party Operated Public Access Stations. NEC-Internal REPORT, Report No: 2001-C002N, January 2001.
[11] R. D. Gitlin, J.- P. Redlich, E. Shim: Secure Candidate Access Router Discovery. NEC-Internal REPORT, Report No: 2002-C032, July 2002.
[12] Berlin Roof Net Projekt. http://sarwiki.informatik.hu-berlin.de/BerlinRoofNet.
