Mobile Ad-hoc-Netzwerke

Telekommunikationsnetzwerke haben sich innerhalb der letzten 20 Jahre dramatisch verändert, von den herkömmlichen Telefonnetzen über das Internet bis hin zu den inzwischen allgegenwärtigen Netzwerken zur Mobilkommunikation. Trotz dieser Entwicklung haben alle diese Netzwerke zumindest eine Gemeinsamkeit: Es gibt eine klare Trennung zwischen der Infrastruktur, wie etwa Kabeln, Routern und Sendemasten, einerseits und den Endsystemen, z. B. Telefone und Computern, andererseits. Damit verbunden ist die Unterscheidung zwischen den Dienstanbietern, die diese Infrastruktur – meist gegen entsprechende Bezahlung – bereitstellen und den Kunden, die die Infrastruktur mit ihren Endsystemen nutzen.

Mit der weiten Verbreitung mobiler Endsysteme wie Laptops, PDAs und mobiler Telefone, die in der Lage sind, Daten per Funk zu empfangen und zu versenden, stellt sich jedoch die Frage, ob nicht auch ein fundamental anderes Vorgehen möglich ist. Wenn diese Geräte flächendeckend vorhanden sind, können sie auch selbst ein Netzwerk bilden, um Daten von einem beliebigen Sender zu einem beliebigen Empfänger weiterzuleiten, ohne dabei auf eine feste Infrastruktur angewiesen zu sein. In einem solchen Netzwerk müssen Endsysteme bereit und in der Lage sein, Daten für andere Endsysteme weiterzuleiten. Wäre dies nicht der Fall, könnten nur diejenigen Geräte miteinander kommunizieren, die sich in unmittelbarer Funkreichweite zueinander befinden. In der Tat ist die Idee der Kommunikation ohne Infrastruktur zum jetzigen Zeitpunkt Gegenstand intensiver akademischer und industrieller Forschung. Da die betrachteten Endsysteme meist mobil sind und die Netzwerkverwaltung spontan, selbstorganisierend und ohne den Eingriff von Benutzern erfolgen muss, nennt man diese Art der Netzwerke auch mobile Ad-hoc- Netzwerke.

Es ist unmittelbar einsichtig, dass mobile Ad-hoc-Netzwerke interessante Eigenschaften besitzen: Da keine Infrastruktur zur Verfügung gestellt werden muss, können diese Netzwerke beispielsweise auch dann eingesetzt werden, wenn keine Infrastruktur vorhanden ist. Allerdings stellt sich auch die Frage, ob und wie es möglich ist, in einem Netzwerk, in dem alle Knoten mobil sind, Nachrichten effizient von einem Sender an einen Empfänger weiterzuleiten.

Im Folgenden werden zunächst die Charakteristika mobiler Ad-hoc-Netzwerke vorgestellt und mögliche Einsatzgebiete diskutiert. Anschließend werden Algorithmen zur Wegewahl präsentiert, die es ermöglichen, Datenpakete in einem Netzwerk aus mobilen Knoten von einem Sender zu einem Empfänger weiterzuleiten. Abschließend erfolgt eine Diskussion offener Fragestellungen und ein Ausblick auf mögliche Weiterentwicklungen im Bereich mobiler Ad-hoc-Netzwerke.

Charakteristika mobiler Ad-hoc-Netzwerke

Wenn man zunächst annimmt, dass alle algorithmischen und technischen Probleme für die Realisierung von Ad-hoc-Netzwerken gelöst werden können, dann stellt sich die Frage, welche Eigenschaften diese Netzwerke besitzen. Weiterhin ist es wichtig zu verstehen, in welchen Einsatzgebieten diese Eigenschaften von besonderem Vorteil sind.

Die am leichtesten zu erkennende Eigenschaft ist, dass mobile Ad-hoc-Netzwerke nach ihrer Definition keine Infrastruktur benötigen. Damit können sie in Gebieten verwendet werden, in denen keine Infrastruktur (mehr) vorhanden ist. Dies ist insbesondere für die Kommunikation bei Einsätzen in Krisengebieten und nach Katastrophen von wesentlicher Bedeutung. Diese Einsatzgebiete waren auch die ursprüngliche Motivation für Forschungsarbeiten auf dem Gebiet der infrastrukturlosen Kommunikation.

Weitergehend könnte man sich auch vorstellen, mobile Ad-hoc-Netzwerke als Alternative zu einer existierenden Infrastruktur zu betrachten, beispielsweise, weil man für deren Dienste nicht bezahlen möchte. Tatsächlich wurde die Einsatzmöglichkeit mobiler Ad-hoc-Netzwerke als Ersatz für herkömmliche Netzwerke intensiv diskutiert.¹ Bei näherer Betrachtung zeigt sich jedoch, dass dies aufgrund von inhärenten Skalierungsgrenzen² nicht realistisch ist: Die begrenzte Bandbreite, die jedem mobilen Gerät zur Kommunikation mit den unmittelbaren Nachbargeräten zur Verfügung steht, muss auf die Übertragung eigener Daten und das Weiterleiten von Daten für andere Teilnehmer aufgeteilt werden. Je mehr Geräte im Durchschnitt auf einer Route vom Sender zum Empfänger liegen, desto größer wird für jeden Knoten der Anteil fremder Daten, für den die eigene Übertragungskapazität verwendet wird. Besteht beispielsweise eine Route in einem gegebenen Ad-hoc-Netzwerk im Durchschnitt aus zehn Geräten, dann muss jedes Gerät durchschnittlich neun fremde Datenpakete weiterleiten, bevor wieder ein eigenes Datenpaket übertragen werden kann. Somit ist klar, dass mobile Ad-hoc-Netzwerke ungeeignet sind, wenn eine Kommunikation mit hoher Datenrate über lange Distanzen notwendig ist. Sie können daher nur eine Ergänzung, aber keinen Ersatz für existierende Netzwerke darstellen.

Eine besonders wichtige Eigenschaft mobiler Ad-hoc-Netzwerke ist folgerichtig, dass sie die existierenden Mobilkommunikationsnetze in sehr attraktiver Weise ergänzen können: Die beiden zentralen Engpässe in herkömmlichen Mobilkommunikationsnetzen sind einerseits die Kapazität des Frequenzspektrums, die für die Datenübertragung zur Verfügung steht, und andererseits die durch eine Batterie bereitgestellte Energie. Spätestens seit Versteigerung der UMTS-Lizenzen ist bekannt, dass die Kapazität des Frequenzspektrums eine knappe und teure Ressource ist, die optimal ausgenutzt werden sollte. Auch ist unmittelbar einsichtig, dass der Energieverbrauch eines mobilen Gerätes die Zeit begrenzt, in der es im Einsatz sein kann. Die Ausnutzung beider Engpässe wird durch Verwendung mobiler Ad-hoc-Netzwerke deutlich verbessert.

Abbildung 1 zeigt die Situation in einem klassischen Mobilkommunikationsnetz: Das Gerät A schickt Daten direkt an eine Basisstation B. Dies bedeutet, dass das Spektrum mindestens im Kreis um A mit dem Radius des Abstandes von A nach B durch die Übertragung belastet wird. Weiterhin muss A Energie für die Übertragung aufwenden. Die notwendige Energie hängt dabei mindestens zum Quadrat von der Distanz von A nach B ab. Zum Vergleich ist in Abbildung 2 die gleiche Situation dargestellt, in der die anderen Endsysteme als ein mobiles Ad-hoc- Netzwerk bei der Datenübertragung helfen. Dabei übergibt A seine Daten an das nächste Endsystem, das in Richtung der Basisstation liegt. Jedes Endsystem, das diese Daten erhält, sucht sich wiederum einen Nachfolger, an den die Daten übertragen werden, bis schließlich die Basisstation erreicht wird. Betrachtet man Abbildung 3, dann kann man erkennen, dass die Belastung des Spektrums auf ein kleineres Gebiet reduziert wurde. Zusätzlich ist die Summe der Quadrate der zurückgelegten Einzeldistanzen kleiner als das Quadrat der Distanz von A nach B. Daher ist die Summe des Energieaufwandes über alle Einzelübertragungen kleiner als der Energieaufwand für eine direkte Kommunikation von A nach B. Aufgrund dieser Eigenschaften ist zu erwarten, dass mobile Ad-hoc-Netzwerke in Zukunft als Zugangsnetzwerk zu infrastrukturbasierten Netzwerken verwendet werden.³

Eine weitere wichtige Eigenschaft mobiler Ad-hoc-Netzwerke ist die direkte Kommunikation zwischen Endsystemen. Dies ist besonders für zeitkritische Anwendungen von großer Bedeutung. In infrastrukturbasierten Netzwerken zur Mobilkommunikation tauschen Anwender ihre Daten immer über eine Basisstation miteinander aus. Dies führt zu einer nicht unerheblichen Verzögerung. In aktuellen UMTS-Netzwerken liegt die Verzögerung beispielsweise in der Größenordnung von einer Zehntelsekunde. In mobilen Ad-hoc-Netzwerken können dagegen wenigstens die direkten Nachbarn unmittelbar erreicht werden, ohne dass die Übertragung einer Nachricht durch das Einschalten einer Basisstation verzögert wird. Daher wird derzeit der Einsatz mobiler Ad-hoc-Netzwerke für die Kommunikation zwischen Fahrzeugen intensiv untersucht.⁴ Insbesondere sollen durch diese Kommunikation Notfall- und Warnmeldungen, wie etwa "Glatteis erkannt", "starkes Bremsen", "Airbag ausgelöst" und "Vorsicht Stauende", schnell an alle durch die Situation betroffenen Fahrzeuge übermittelt werden. Eine Verzögerung durch Verwenden einer Basisstation ist insbesondere für die direkten Nachbarn des sendenden Fahrzeuges in einer solchen Situation nicht akzeptabel. Andererseits sollen die Warnungen auch an Fahrzeuge verbreitet werden, die sich der Gefahrenstelle nähern und noch nicht in direkter Sendereichweite desjenigen Fahrzeuges sind, das diese verschickt. Aus der Kombination beider Anforderungen folgt, dass für dieses Anwendungsgebiet der Einsatz mobiler Ad-hoc-Netzwerke besonders vorteilhaft ist.

Wegewahl in mobilen Ad-hoc-Netzwerken

Aus technischer Sicht gibt es eine Vielzahl interessanter Probleme, die gelöst werden müssen, bevor mobile Ad-hoc-Netzwerke tatsächlich in der Praxis eingesetzt werden können. Dies beinhaltet unter anderem Bereiche wie Fairness, Sicherheit und Optimierung der Hardware. Die zentrale Frage ist jedoch, wie es möglich ist, Daten von einem Sender über mehrere Endsysteme zu einem Empfänger zu leiten, wenn alle beteiligten Systeme mobil sind und jederzeit ihre Position verändern können. Die Aufgabe, für Daten einen Weg durch ein Kommunikationsnetzwerk zu finden, bezeichnet man als Wegewahl oder Routing. Die zentrale Herausforderung beim Routing in mobilen Ad-hoc-Netzwerken besteht darin, dass sich die Topologie – also die Nachbarschaftsbeziehungen – des Netzwerkes sehr schnell verändern kann. Klassische Verfahren, wie sie beispielsweise im Internet verwendet werden, berücksichtigen dies nicht. Um die daraus resultierenden Schwierigkeiten zu vermeiden, wurden eine Reihe von Algorithmen speziell für das Routing in mobilen Ad-hoc-Netzwerken entwickelt.

Prinzipiell kann man Routing-Algorithmen für mobile Ad-hoc-Netzwerke in drei Klassen einteilen: Klassische Routing-Algorithmen gehören zu den proaktiven Verfahren. Elemente dieser Klasse zeichnen sich dadurch aus, dass sie Informationen über die Topologie des Netzwerkes vorhalten, unabhängig davon, ob diese aktuell für das Routing benötigt werden. Reaktive Verfahren wurden speziell für mobile Ad-hoc-Netzwerke entwickelt. Bei Einsatz eines reaktiven Verfahrens werden Topologieinformationen nur dann bestimmt, wenn diese direkt für das Weiterleiten von Nachrichten benötigt werden. Schließlich wird bei positionsbasierten Verfahren die geografische Position der beteiligten Endsysteme verwendet, um Daten in Richtung des Empfängers weiterzuleiten. Diese Verfahren erfordern typischerweise, dass jedes Endsystem seine eigene Position bestimmen kann, beispielsweise über das Global Positioning System (GPS).

Im Folgenden werden alle drei Klassen genauer vorgestellt und bezüglich ihrer Eigenschaften diskutiert.⁵ Dabei werden die folgenden Begriffe verwendet: Ein Knoten in einem Ad-hoc-Netzwerk ist ein beliebiges Endsystem. Ein Knoten B ist Nachbar von Knoten A, wenn er per Funk direkt von A erreicht werden kann. In der Regel geht man davon aus, dass die Nachbarschaftsbeziehung symmetrisch ist, d. h., wenn Knoten B Nachbar von A ist, dann ist auch A Nachbar von B. Dies muss aufgrund der Ausbreitung von Funkwellen in der Realität nicht der Fall sein, stellt aber häufig eine sinnvolle Vereinfachung dar. Die Topologie eines Ad-hoc-Netzwerkes ist die Menge aller Nachbarschaftsbeziehungen. Als Datenpaket oder Paket wird eine Übertragungseinheit von Daten in einem Netzwerk bezeichnet.

Proaktive Routing-Algorithmen

Ein Beispiel für einen proaktiven Routing-Algorithmus ist das so genannte Link State Routing. Link State Routing wird mit dem Routing-Protokoll Open Shortest Path First (OSPF)⁶ sehr erfolgreich und häufig für die Wegewahl in Teilen des Internets verwendet. Die prinzipielle Vorgehensweise von Link State Routing ist wie folgt: Jeder Knoten kennt zu jedem Zeitpunkt die Topologie des gesamten Netzwerkes. Basierend auf dieser Kenntnis bestimmt jeder Knoten den kürzesten Weg zu jedem anderen Knoten mit Hilfe des so genannten Dijkstra- Algorithmus⁷. Wenn ein Empfängerknoten vorgegeben wird, kann daher jeder Knoten die Daten an seinen Nachfolger auf dem kürzesten Pfad zum Empfänger weiterleiten.

Ein solches Verfahren ist sehr gut für klassische Netzwerke geeignet, in denen sich die Topologie selten ändert: Jeder Knoten lernt einmal die Topologie des Netzwerkes kennen und bestimmt dann, an welchen Nachbarn Daten für ein gegebenes Ziel weitergegeben werden müssen. Wenn sich die Topologie jedoch häufig ändert, wird dieses proaktive Vorgehen problematisch: Immer wenn eine Nachbarschaftsbeziehung hinzukommt oder wegfällt, müssen alle Knoten des Netzwerkes darüber informiert werden. Ab einer gewissen Rate von Topologieänderungen wird dann die gesamte Kapazität des Netzwerkes ausschließlich für das Übertragen von Topologieinformationen verwendet, während für eigentliche Nutzdaten keine Kapazität mehr zur Verfügung steht. Zusätzlich wird der lokale Aufwand für das häufige Ausführen des Dijkstra-Algorithmus schnell so groß, dass er ressourcenarme Geräte überfordert. Beide Eigenschaften sind typisch für proaktive Routing- Algorithmen im Allgemeinen. Bemerkenswert ist insbesondere, dass der Aufwand von proaktiven Verfahren auch dann anfällt, wenn überhaupt keine Datenkommunikation stattfindet.

Reaktive Routing-Algorithmen

Im Unterschied zu proaktiven Verfahren werden bei reaktiven Routing-Algorithmen nur Informationen über diejenigen Pfade im Netzwerk aufrechterhalten, die zurzeit tatsächlich in Verwendung sind. Ein bekannter Vertreter dieser Klasse ist Dynamic Source Routing (DSR).⁸ Als Beispiel für den Einsatz von DSR sei ein Netzwerk mit der in Abbildung 3 dargestellten Topologie gegeben. Nun entscheidet Knoten A, dass er Daten an Knoten G senden möchte. Da es sich bei DSR um ein reaktives Verfahren handelt, ist im Netzwerk zunächst kein Weg von A zu G bekannt. Daher schickt A einen so genannten Route- Request an alle seine Nachbarn (B und D). In diesem Route-Request ist die Information enthalten, dass ein Pfad von A nach G gesucht wird. Alle Knoten, die den Route- Request erhalten, fügen diesen Informationen ihre eigene Kennung hinzu und leiten ihn ihrerseits an alle Nachbarn weiter. Wenn also D den Route-Request von A empfängt, fügt er seine Kennung hinzu und leitet ihn an B, F und E weiter. Bei diesem Vorgang merken sich die Knoten anhand einer vom Sender vergebenen Sequenznummer, welche Route-Requests sie schon weitergeleitet haben und ignorieren den erneuten Empfang desselben Route-Requests. Hat im Beispiel B den Route-Request von A bereits empfangen, bearbeitet und weitergeleitet, wird der gleiche Route-Request, wenn er von D an B weitergeleitet wird, einfach ignoriert.

Sofern eine Route vom Sender zum gewünschten Empfänger existiert, wird der Empfänger schließlich den Route-Request (unter Umständen mehrfach auf verschiedenen Routen) erhalten. In dem Route-Request haben alle Knoten, die auf dem Weg vom Sender zum Empfänger liegen, ihre Kennung eingetragen. Daher kennt der Empfänger nun einen gültigen Weg vom Sender zum Empfänger. Im Beispiel könnte G, je nach Ablauf, den Route-Request zweimal erhalten: einmal über die Route A-B-C und einmal über die Route A-D-F. Nun muss der Empfänger den Sender über eine dieser Routen informieren. Dafür erzeugt G einen so genannten Route-Reply. Darin enthalten ist eine der Routen, beispielsweise diejenige, die G zuerst empfangen hat. Außerdem gibt G vor, welchen Weg der Route-Reply durch das Netzwerk nehmen soll: G schreibt die Folge der Knoten in den Route-Reply, die auf dem Pfad von G nach A durchlaufen werden sollen. Dies ist einfach der umgedrehte Pfad von A nach G. Im Beispiel könnte G also den Pfad A-B-C-G an A auf dem Weg G-C-B-A schicken. Jeder Knoten auf diesem Pfad leitet den Route-Reply an seinen im Route-Reply aufgeführten Nachfolger weiter. Sobald der Sender diese Nachricht erhält, kennt er einen gültigen Weg zum Empfänger und kann die eigentlichen Daten versenden. Dies geschieht analog zum Übertragen des Route-Reply: Der Sender gibt die Route explizit vor, auf der die Datenpakete übertragen werden sollen.

Bei proaktiven Verfahren wie DSR führt eine Veränderung der Topologie des Netzwerkes nur dann zu Aufwand, wenn die Änderung eine Route betrifft, die gerade in Verwendung ist. Verwendet A beispielsweise die Route A-B-C-G, wird ein Wegfall der Verbindung D-F keine Auswirkungen haben. Entfällt dagegen die Verbindung C-G, dann können die Daten nicht mehr auf der von A vorgegebenen Route weitergeleitet werden. In diesem Fall verwirft C die Daten und generiert einen Route-Error, der an den Sender der Daten zurückgeleitet wird. A wird daraufhin mit dem bereits beschriebenen Verfahren eine neue Route zu G suchen.

Die wesentliche Eigenschaft reaktiver Verfahren besteht also darin, dass nur aktive Routen gepflegt werden. Sofern in einem Netzwerk nur wenige Routen zu jedem beliebigen Zeitpunkt tatsächlich verwendet werden, vermindert dies den Aufwand erheblich. Allerdings haben auch reaktive Ansätze Probleme:

• Bevor Daten übertragen werden können, muss zunächst eine Route durch das Netzwerk gesucht werden. Dies erfordert sowohl Zeit als auch Ressourcen zur Übertragung von Nachrichten für das Suchen einer Route.
• Obwohl die Last zur Aufrechterhaltung von benutzten Routen geringer ist als der Aufwand zur Aufrechterhaltung aller Routen, kann diese bei sehr dynamischen Netzwerken immer noch sehr hoch sein.
• In hoch dynamischen Ad-hoc-Netzwerken kann eine Verbindung bereits wieder ungültig sein, bevor auch nur ein einziges Datenpaket zugestellt wurde.
• Wird eine Route ungültig, während auf ihr Datenpakete transportiert werden, so müssen diese häufig verworfen werden.

Positionsbasierte Routing-Algorithmen

Positionsbasiertes Routing vermeidet einige Einschränkungen der bisher vorgestellten Ansätze durch die Verwendung von zusätzlichen Informationen. Insbesondere wird erwartet, dass jeder Knoten seine eigene geografische Position bestimmen kann. Dies kann durch den Einsatz von GPS geschehen, es sind jedoch auch andere Mechanismen vorstellbar.⁹ Durch das regelmäßige Senden von so genannten Beacons teilt jeder Knoten seinen Nachbarn die eigene Position mit. Diese Informationen werden in einer Nachbarschaftstabelle gespeichert.

Möchte ein Sender ein Paket an einen bestimmten Knoten schicken, so bestimmt er die geografische Position des Empfängers mit Hilfe eines Positionsdienstes. Anschließend wird das Paket einem Nachbarn übergeben, der in Richtung der Position des Empfängers liegt. Idealerweise kann dies dann von Knoten zu Knoten fortgesetzt werden, bis der Empfänger erreicht ist.

Entsprechend dieses generellen Vorgehens müssen für ein konkretes positionsbasiertes Routing-Verfahren Algorithmen für die Lösung der beiden zentralen Probleme bereitgestellt werden: Zum einen ist dies ein Algorithmus, der als Positionsdienst für den Sender eines Paketes die geografische Position des Empfängers ermittelt; zum anderen wird eine Strategie benötigt, nach der ein Knoten anhand der eigenen Position, der Position seiner Nachbarn und der Position des Empfängers denjenigen Nachbarn ermittelt, an den die Daten weiterzuleiten sind.

Ein offensichtliches Verfahren für die Realisierung eines Positionsdienstes besteht darin, dass ein Sender, der die Position des Empfängers erfahren möchte, einfach das Netzwerk mit dieser Anfrage flutet. Analog zu einem Route-Request bei DSR leitet dabei jeder Knoten die Anfrage einmal an alle seine Nachbarn weiter. Sobald die Anfrage bei dem gesuchten Knoten ankommt, schickt dieser eine Antwort an den Sender der Anfrage zurück. Damit die Antwort per positionsbasierter Wegewahl verschickt werden kann, beinhaltet die Anfrage die Position des Senders. Prinzipiell hat dieses Vorgehen den gleichen Aufwand wie das Finden einer Route bei reaktiven Ansätzen.

Es sind jedoch auch sehr viel elegantere Verfahren für die Realisierung von Positionsdiensten möglich, die insbesondere ohne das Fluten des gesamten Netzwerkes auskommen. Homezone ist ein besonders einfaches Beispiel hierfür.¹⁰ Die Homezone ist ein geografisches Gebiet, meist ein Kreis. Die Position der Homezone eines Knotens ermittelt sich aus dessen eindeutiger Kennung (z. B. der IP- Adresse) durch Anwenden einer Hash-Funktion. Ein Knoten schickt regelmäßig per positionsbasiertem Routing Informationen über seine aktuelle Position an alle Knoten in seiner Homezone. Bei Positionsanfragen muss lediglich wieder die Hash-Funktion auf die Kennung des gesuchten Knotens angewendet werden und dann eine Anfrage an einen beliebigen Knoten in der entsprechenden Homezone gestellt werden.

Zur Weiterleitung eines Paketes bei positionsbasiertem Routing benötigt ein Knoten drei Arten von Informationen: (1) seine eigene Position, die beispielsweise mit Hilfe von GPS bestimmt werden kann, (2) die durch den Positionsdienst bestimmte Position des Empfängers und (3) die aufgrund von Beacons bekannte Position seiner Nachbarn.

Mit Hilfe dieser Informationen sucht sich der weiterleitende Knoten einen Nachbarn aus, der geografisch in Richtung des Empfängers liegt. Prinzipiell sind für die positionsbasierte Wahl des Nachbarn verschiedene Strategien möglich, von denen einige in Abbildung 4 dargestellt sind. Hierbei ist der weiterleitende Knoten mit S und der Empfänger mit E gekennzeichnet. Der Kreis mit dem Radius r kennzeichnet die Sendereichweite von S. Eine nahe liegende Strategie ist die Weiterleitung des Paketes an denjenigen Nachbarn, der den größten Fortschritt in Richtung des Empfängers verspricht. Im Beispiel wäre dies der Knoten C. Diese Strategie ist auch als most forward within radius (MFR) bekannt und minimiert die Anzahl der Knoten auf dem Weg vom Sender zum Empfänger.¹¹

Ist ein Knoten in der Lage, seine Sendeleistung an die Distanz zu einem Kommunikationspartner anzupassen, dann ist es sinnvoll, denjenigen Nachbarn zu wählen, der sowohl einen Fortschritt in Richtung des Empfängers erzielt als auch am dichtesten am weiterleitenden Knoten liegt. Im Beispiel wäre dies der Nachbar A. Diese Strategie vermindert das Risiko, dass sich mehrere gleichzeitig stattfindende Übertragungen gegenseitig stören und erhöht somit den Erwartungswert des Paketfortschritts in Richtung des Empfängers. Diese Strategie wird als nearest with forward progress (NFP) bezeichnet.¹²

Schließlich ist es auch möglich, die geografische Strecke zu minimieren, die ein Paket vom Sender zum Empfänger zurücklegt. Dies geschieht, indem ein Nachbar gewählt wird, der am nächsten zu der Verbindung von weiterleitendem Knoten und Empfänger liegt. Im Beispiel ist dies Knoten B. Dieses Vorgehen ist unter dem Namen compass routing bekannt.¹³

Da bei allen beschriebenen Verfahren ausschließlich lokale Informationen verwendet werden, besteht die Gefahr, ein lokales Optimum zu erreichen, das das Verfahren selbständig nicht mehr verlassen kann. Ein Beispiel hierfür ist in Abbildung 5 zu sehen. In diesem Beispiel liegt der weiterleitende Knoten S näher am Empfänger E als alle Nachbarn von S, obwohl es einen gültigen Weg von S nach E gibt. Somit kann keine der oben beschriebenen Strategien einen geeigneten Nachbarn für das Weiterleiten des Paketes bestimmen.

Ein Mechanismus für die Lösung dieses Problems wurde für die Ad-hoc-Routing-Verfahren face-2¹⁴ und Greedy Perimeter Stateless Routing (GPSR)¹⁵ vorgeschlagen. Die Idee ist, das Ad-hoc-Netzwerk als einen planaren Graphen zu betrachten und mit Hilfe der so genannten Rechtehandregel aus einem lokalen Optimum zu entkommen. Sobald das Paket einen Knoten erreicht, der näher am Empfänger liegt als das lokale Optimum, wird es wieder auf Positionsbasis weitergeleitet.

Die Vorgehensweise dieses Mechanismus ist in Abbildung 6 illustriert, wobei die dargestellte Situation nur zur Verdeutlichung der Rechtehandregel dient, da übersichtlichkeitshalber kein lokales Optimum vorliegt. Bei Anwendung der Rechtehandregel wird zunächst die Verbindung zwischen weiterleitendem Knoten im lokalen Optimum und Zielknoten bestimmt. Dann erfolgt die Weiterleitung des Paketes auf der nächsten Kante gegen den Uhrzeigersinn von dieser Verbindung. Der empfangende Knoten leitet das Paket dann auf der nächsten Kante gegen den Uhrzeigersinn weiter, sofern diese nicht die Verbindung zwischen dem Knoten, in dem die Rechtehandregel begonnen wurde, und dem Empfänger schneidet. Wenn dies der Fall ist, wird die Kante ausgelassen und die nächste Kante gegen den Uhrzeigersinn gewählt. Es kann gezeigt werden, dass die Rechtehandregel immer den Zielknoten findet, vorausgesetzt, dass das Netzwerk nicht partitioniert ist.¹⁶ Interessant ist, dass alle Informationen für dieses Vorgehen entweder lokal vorhanden sind oder im Paket mit wenig Aufwand mitgeführt werden können, so dass keine globale Sicht auf das Netzwerk notwendig ist.

Da bei positionsbasiertem Routing in jedem Knoten nur lokale Entscheidungen getroffen werden, die von der Position des Empfängers und der Position der Nachbarn abhängig sind, ist das Aufrechterhalten von Routen nicht nötig. Damit muss kein vollständiger Pfad vom Sender zum Empfänger gepflegt werden; es wird ein großer Teil der für reaktive Routing-Protokolle beschriebenen Probleme vermieden. In Füßler (2003) wird zudem ein positionsbasiertes Verfahren vorgestellt, das auf die Übertragung von Nachbarschaftsinformationen per Beacons verzichtet und damit sowohl den Aufwand reduziert als auch die Robustheit gegenüber Topologieänderungen weiter erhöht.

Allerdings ist die Kenntnis der eigenen Position in allen Knoten eines Ad-hoc-Netzwerkes eine sehr hohe Anforderung. Insbesondere in geschlossenen Räumen kann die eigene Positionsbestimmung nicht mehr über GPS durchgeführt werden und ist somit nur durch erheblichen Mehraufwand zu realisieren. Es gilt daher: Wenn Knoten ihre eigene Position bestimmen können, sollten positionsbasierte Verfahren eingesetzt werden; ansonsten muss auf reaktive oder proaktive Algorithmen zurückgegriffen werden.

Offene Fragestellungen und Ausblick

Die Problematik der Wegewahl in mobilen Ad-hoc-Netzwerken ist zumindest in Theorie und Simulation inzwischen weitestgehend verstanden. Protokolle, die proaktive, reaktive und positionsbasierte Routing-Algorithmen für diese Netzwerke zur Verfügung stellen, befinden sich derzeit in der Standardisierung. Allerdings gibt es eine Fülle von weiteren Fragestellungen, die noch gelöst werden müssen, bevor mobile Ad-hoc-Netzwerke in der Praxis einsetzbar sind.

Eine ganz entscheidende Rolle spielt dabei die Fairness. Zunächst ist nämlich nicht einsichtig, warum sich ein Endsystem am Weiterleiten fremder Daten beteiligen und dafür eigene Energie als knappe Ressource aufwenden sollte. Es besteht die Gefahr, dass sich Endsysteme egoistisch verhalten und nur eigene Daten senden, aber keine fremden Daten weiterleiten. Obwohl es erste Ansätze zur Vermeidung dieses Problems gibt, sind diese noch weit von einer direkten Einsetzbarkeit entfernt. Die bisher vorgeschlagenen Ansätze reichen von der Verwendung von Reputation (wenn Knoten A erfährt, dass Knoten B Pakete für andere Knoten nicht weiterleitet, dann leitet A auch keine Pakete für B weiter) bis hin zur direkten Bezahlung für jedes Weiterleiten mit Hilfe von so genannten Mikropaymentsystemen.

Die zweite wichtige und derzeit noch nicht befriedigend gelöste Problemstellung ist der Schutz eines Ad-hoc-Netzwerkes vor Überlast. Da theoretisch jedes einzelne Endsystem in einem Ad-hoc-Netzwerk so viele Daten senden könnte, dass die gesamte Kapazität des Netzwerkes belegt wird, muss durch geeignete Mechanismen eine Überlastung des Netzwerkes vermieden und die Kapazität gerecht auf alle sendewilligen Endsysteme verteilt werden. Im Internet ist das Transmission Control Protocol (TCP) für diese Aufgabe verantwortlich. Die Mechanismen von TCP sind jedoch nicht direkt auf mobile Ad-hoc-Netzwerke übertragbar, da sie nicht für eine Topologie mit hoher Dynamik entwickelt wurden.

Als letztes Beispiel für offene Fragestellungen sei der Schutz des Netzwerkes vor böswilligen Angriffen genannt. Da in einem Ad-hoc-Netzwerk die Endsysteme für das Weiterleiten von Daten verwendet werden, ist es sehr leicht angreifbar. Jedes Endsystem kann die von ihm weitergeleiteten Daten mitlesen, verfälschen oder verwerfen. Genauso kann jedes Endsystem versuchen, den eingesetzten Routing-Algorithmus zu manipulieren, um Einfluss auf das Verhalten anderer Endsysteme zu nehmen. Zusätzlich gibt es in einem Ad-hoc-Netzwerk in der Regel keine zentrale Instanz, die für Autorisation oder Authentifikation verwendet werden kann. Damit ist die Gewährleistung von Sicherheit für mobile Ad-hoc-Netzwerke eine besondere Herausforderung.

Zusammenfassend kann festgestellt werden, dass mobile Ad-hoc-Netzwerke sehr interessante Eigenschaften besitzen und für viele Anwendungsgebiete besonders attraktiv sind. Insbesondere im Bereich der Fahrzeug-zu-Fahrzeug-Kommunikation arbeiten inzwischen nahezu alle Automobilhersteller gemeinsam an einer standardisierten Kommunikation zwischen Fahrzeugen auf Basis mobiler Ad-hoc-Netzwerke. Die zentrale Frage nach dem Routing in diesen Netzwerken konnte inzwischen weitestgehend beantwortet werden. Allerdings sind noch eine Reihe spannender Probleme zu lösen, bis tatsächlich Produkte auf Basis dieser Technologie entstehen können.

Literatur

BOSE, P., P. MORIN, I. STOJMENOVIC und J. URRUTIA. "Routing with guaranteed delivery in ad hoc wireless networks", 3rd ACM International Workshop on Discrete Algorithms and Methods for Mobile Computing and Communications (DIALM) (1999), 48-55.

CAPKUN, S.,M. HAMDI und J. P. HUBAUX. "GPS-free Positioning in Mobile Ad-Hoc Networks", Cluster Computing Journal 2 (2002), 157-167.

DIJKSTRA, E. W. "A Note on Two Problems in Connexion with Graphs", Numerische Mathematik Oktober 1959, 269-271.

ENKELMANN, W., L. WISCHOF, A. EBNER und H. ROHLING. "FleetNet – Anwendungen für mobile Ad-hoc-Netzwerke", Praxis der Informationsverarbeitung und Kommunikation 4 (2003), 197-202.

FÜSSLER, H.,J. WIDMER, M. KÄSEMANN, M. MAUVE und H. HARTENSTEIN. "Contention-Based Forwarding for Mobile Ad-Hoc Networks", Elsevier Ad Hoc Networks 4 (2003), 351-369.

GIORDANO, S. und M. HAMDI. Mobility Management: The Virtual Home Region. Technischer Bericht SSC/1999/037, EPFL, Oktober 1999.

GIORDANO, S., M. HAMDI, J. P. HUBAUX und J. Y. LE BOUDEC. "The Terminodes Project: Towards Mobile Ad-Hoc WANs", MOMUC ‘99, San Diego, November 1999, 124-128.

GUPTA, P. und P. R. KUMAR. "The Capacity of Wireless Networks", IEEE Transactions on Information Theory 2 (2000), 388-404.

HOU, T.-C. und V. O. K. LI. "Transmission Range Control in Multihop Packet Radio Networks", IEEE Transactions on Communications 1 (1986), 38-44.

JOHNSON, D. und D. A. MALTZ. "Dynamic Source Routing in Ad Hoc Wireless Networks", in: T. IMIELINSKI und H. KORTH (Hrsg.). Mobile Computing Band 353. Boston, MA, 1996, 153-181.

KARP, B. und H. T. KUNG. "Greedy Perimeter Stateless Routing for Wireless Networks", 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom) (2000), 243-254.

KRANAKIS, E., H. SINGH und J. URRUTIA. "Compass Routing on Geometric Networks", 11th Canadian Conference on Computational Geometry (1999), 51-54.

MAUVE, M., J. WIDMER und H. HARTENSTEIN. "A Survey on Position-Based Routing in Mobile Ad-Hoc Networks", IEEE Network Magazine 6 (2001), 30-39.

MAUVE, M., H. HARTENSTEIN, H. FÜSSLER, J. WIDMER und W. EFFELSBERG. "Positionsbasiertes Routing für die Kommunikation zwischen Fahrzeugen", it + ti 5 (2002), 278-286.

MOY, J. T. OSPF Version 2. IETF Network Working Group RFC 2328 (1998).

ROYER, E. und C.-K. TOH. "A review of current routing protocols for ad-hoc mobile wireless networks", IEEE Personal Communications 6(2) (1999), 46-55.

TAKAGI, H. und L. KLEINROCK. "Optimal Transmission Ranges for Randomly Distributed Packet Radio Terminals", IEEE Transactions on Communications 3 (1984), 246-257.

ZIRWAS, W., J. HABETHA und H. KARL. "Ziel-orientierter Entwurf von Multi-hop Medienzugriffsprotokollen", Praxis der Informationsverarbeitung und Kommunikation 4 (2003), 184-189.