In der heutigen Zeit spielt die Vernetzung von Computern und Systemen eine immer größere Rolle. In der Vergangenheit waren Datennetze überwiegend drahtgebunden bzw. basierten auf Lichtwellenleiter. Auch heute und in Zukunft werden die Lichtwellenleiter vor allem im Backbone-Bereich weiterhin dominieren, während drahtgebundene Netze in der LAN-Verkabelung eingesetzt werden. Allerdings finden sich immer mehr Anwendungen, die eine feste Verkabelung nicht sinnvoll erscheinen lassen oder ihr widersprechen. So ist die Anzahl der Mobiltelefone in Deutschland inzwischen größer, als die der Festnetztelefone. Und in immer mehr Bereichen soll die Funktionalität durch Funkübertragung und spontane Kommunikation erhöht werden. Drahtlose Netze gewinnen also immer mehr an Bedeutung. Sie werden dabei in zwei verschiedenen Arten unterteilt, die Infrastrukturnetze und die Ad-hoc-Netze.
Mobile Infrastruktur - Netzwerke sind Netzwerke, in denen wichtige Netzteile Bestandteil eines fest verkabelten Netzes sind. Es existieren Basisstationen, die eine zentrale Bedeutung haben. Eine Kommunikation zwischen mobilen Teilnehmer ohne Basisstation ist nicht vorgesehen. Es handelt sich also um Single-Hop-Netzwerke. Die Basisstationen sind untereinander verbunden evtl. auch über eine Funkstrecke. Die mobilen Teilnehmer melden sich dabei an einer Basisstation an.
Beispiele für Infrastrukturnetzwerke sind IEEE 802.11 WLAN , GSM, Bluetooth oder auch DECT. Infrastrukturnetze sind inzwischen weit verbreitet und basieren auf meist ausgereiften Technologien.
Mobile Ad-hoc-Netzwerke besitzen keine festen Basisstationen. Alle Teilnehmer dieser Netzwerke sind mobil und fungieren sowohl als Endstation als auch als Router. Grundlage der meisten Ad-hoc-Netzwerke ist der beaconing - Mechanismus (Leuchtfeuer). Jeder Teilnehmer (Node) sendet in regelmäßigen Abständen ein beacon - Signal. Dies ist notwendig, damit jeder Teilnehmer seine Nachbarn kennt, die er direkt erreichen kann. Alle Teilnehmer nutzen beim Senden dieselbe Frequenz, was natürlich die Kapazität des Netzes begrenzt.
Die gesamte Netzstruktur entsteht dynamisch durch Selbstorganisation und Selbstverwaltung.Es gibt also keine zentrale Stelle, die das Routing oder die Netzstruktur festlegt, das Management in Ad-hoc-Netzwerken ist somit verteilt. Aufgrund der Mobilität der Teilnehmer ist die Netzstruktur zeitvariant. Der Eintritt in ein Ad-hoc-Netzwerk erfolgt durch Interaktion mit anderen Teilnehmern. Natürlich kann ein Teilnehmer eines Ad-Hoc-Netzwerkes auch Schnittstelle zu einem festen Netzwerk sein.
Die Verbindungen zwischen den einzelnen Nodes erfolgt peer-to-peer. Es handelt sich dabei oft um Multi-Hop-Verbindungen. Daten können also nicht nur über direkte Verbindungen transportiert werden, sondern gelangen auch zu entfernten Stationen.
Typische Anwendungsgebiete sind Koordinierung von Rettungsaktionen in Krisengebieten oder Einsatz in militärischen Kampfgebieten. Ein weitere Bereich ist die Verkehrstelematik.
Verschiede mobile Ad-Hoc-Netzwerk-Verfahren befinden sich derzeitig in der Diskussion. Federführend ist MANET, eine Untergruppe der Internet Engineering Task Force. Die RFC 2501 "Mobile Ad hoc Networking (MANET): Routing Protocol Performance Issues and Evaluation Considerations" wurde bereits veröffentlicht. Auf der Homepage von MANET gibt ausserdem Links zu diversen nicht offiziellen Veröffentlichungen. Ad-hoc-Netzwerke sind ebenfalls schon länger bekannt. Sie sind als Option auch in Bluetooth und IEEE 802.11 vorhanden. Allerdings hat dies Form des Netzaufbaus aufgrund von technologischen Einschränkungen noch keine weite Verbreitung gefunden. Es besteht weiterhin großer Forschungsbedarf, um Einschränkungen zu beseitigen. Diese Arbeit geht insbesondere auf das Routing in Ad-hoc-Netzwerken ein.
Ken Tang beschreibt unter [3] einige Probleme, die mit der klassischen Medium Access Methode CSMA/CD bei Funknetzen auftreten. Wie bereits erwähnt, nutzen alle Nodes in Ad-Hoc-Netzwerken die gleichen Frequenzen. Diese MAC-Probleme existieren demzufolge auch bei Ad-hoc-Netzwerken.
Wenn das Medium in der Nähe des Transmitters frei ist, besteht trotzdem die Möglichkeit, dass das Medium beim Empfänger belegt ist.
Das Hidden Terminal Problem entsteht in diesem Beispiel dadurch, dass sich die Station A nicht im Empfangsbereich der Station B befindet und umgekehrt. Deshalb kann ein klassischer Carrier Sense Mechanismus hier nicht funktionieren, beide Messages kollidieren in der Station C.
Ebenso kann es vorkommen, dass das Medium beim Sender besetzt ist aber beim Empfänger ist es frei.
Das Exposed Terminal Problem stellt ebenfalls ein Carrier Sense Problem dar. Hier sei Station B am Senden. C erkennt, dass B sendet und betrachtet das Medium als besetzt, obwohl C in Richtung D übertragen könnte.
Es ist klar das CSMA/CD nicht für Drahtlose Netze geeignet ist. In [3] werden diverse Alternativen genannt, unter anderem packet sense (ohne Carrier sense), carrier sense with collision avoidance (CSMA/CA), RTS/CTS, ACKs. Diverse Kombinationen dieser Methoden wurden umgesetzt, unter anderem in MACA (RTS/CTS), FAMA (CSMA/RTS/CTS), MACAW (RTS/CTS/ACKs, control frames) und IEEE 802.11 (CSMA/CA/RTS/CTS/ACK).
In seinen Untersuchungen stellte Ken Tang fest, dass die Kombination aus CSMA/CA,RTS/CTS und ACK die beste Lösung ist. Diese Verfahren wurde auch in IEEE 802.11 umgesetzt.
Es existieren weitere Verfahren wie PAMAS[23], welche andere Zielsetzungen wie Stromsparfähigkeit betonen. Hierbei wird, basierend auf MACA, ein separater Signalisierungskanal verwendet.
Übersichten über Routing-Protokolle in Ad-hoc-Netzwerken finden sich unter [2],
Hier wird unterschieden zwischen tabellenbasierten (proaktiv) und source-initiated on-demand driven (reaktiv) Protokollen. Bei tabellenbasierten Protokollen speichert jeder Node Routinginformationen für das ganze Netz, die global state-Informationen. Beim source-initiated on-demand driven routing werden nur Informationen über die lokalen Nachbarn gespeichert, die local state-Informationen.
Weiterhin kann man zwischen flachen und hierarchischen Protokollen unterscheiden. Flache Protokolle bieten sich für kleinere Netze an, während hierarchische Protokolle in großen Netzen von Vorteil sind. Hierarchische Netze werden in so genannte Cluster aufgeteilt, der Pfad wird entlang der Cluster bestimmt und nicht mehr entlang einzelner Nodes. Eine weitere Form der Hierarchie sind virtuelle Backbones. Unterteilung ist deshalb wichtig, weil die Routenbestimmung eine hohe Komplexität besitzt, mobile Endgeräte aber nur über beschränkte Rechenleistung verfügen.
Es ist klar, dass die Routing-Protokolle Mechanismen enthalten sollten, die Schleifenbildung verhindern. Diese Forderung wird von den meisten Protokollen erfüllt.
Es gibt klassische Ansätze, die auf Unicast aufbauen, um Multicast zu gewährleisten. Hierbei werden die Datenströme in einem Router bzw. Zwischennode vervielfältigt. Das kann zu unnötiger Redundanz führen. In [16] wird der "ST-WIM"-Algorithmus vorgestellt. Dieser ist unabhängig vom darunter liegenden Routing-Protokoll. Hierbei wird an einem Rendezvous-Punkt ein dynamischer, verteilter Baum aufgespannt. Bei verstärkter Mobilität muss dieses Protokoll jedoch verstärkt Performance-Einbußen hinnehmen.
Neue Ansätze, die Kanaleigenschaften nutzen, wurden in [17] propagiert. Dabei will man die natürliche Broadcast-Eigenschaft der Funkwellen ausnutzen. In einem theoretischen Ansatz wird ein Verfahren vorgestellt, welches auf einem reduzierten flooding- Verfahren namens hyper-flooding beruht. Einmal gesendete Daten können von mehreren Teilnehmern empfangen werden. Mit dieser Kenntnis kann Redundanz verringert werden. Diese Reduktion der gesendeten Pakete kann aber zur Folge haben, dass einige Mitglieder der Gruppe Daten nicht empfangen. Dieses Problem tritt insbesondere bei Topologieänderungen in Kombination mit Paketwiederholungen auf. Deshalb muss ein Kompromiss zwischen Effizienz und Robustheit gefunden werden.
Eine besonders große Herausforderung ist die Integration der verschiedenen Multicast - Strategien in festen Infrastrukturnetzwerken, mobilen Infrastrukturnetzwerken und Ad-hoc-Netzwerken. Optimalerweise sollte es egal sein, ob sich ein Gruppenmitglied in mobilen oder festen Netzwerken befindet. Multicastfähigkeit ist ein Gebiet, auf dem weiterhin großer Forschungsbedarf besteht.
Ein Ad-hoc-Netzwerk sollte seine Struktur nicht nur starr anhand von Verbindungen aufbauen, sondern sollte seine Topologie auch an den Bandbreitenbedarf der einzelnen Verbindungen anpassen. So könnten selbst größere Umwege eines Paketes stark frequentierte Bereiche des Netzes entlasten und somit zu einer höheren Geschwindigkeit führen. Allerdings ist diese Forderung stark an QoS-Fähigkeit gebunden.
Mobile Geräte haben oft Einschränkungen hinsichtlich Größe und Gewicht. Dies hat Auswirkungen auf Energievorrat und Reichweite, was von den Protokollen berücksichtigt werden sollte. Die Datenmenge und die Sendehäufigkeit sollte so gering wie möglich sein. Ebenso sollten für die Berechnung der Route effiziente Algorithmen verfügbar sein.
Die Forderung ergibt sich auch aus der Vorherigen. Die Bandbreite von mobilen Funkstrecken ist außerdem bedeutend kleiner als die Bandbreite von Kabelnetzen. Deshalb sollten Routing-Protokolle in Ad-hoc-Netzen bandbreiteschonend sein.
Funkwellen sind sehr einfach abzuhören und zu stören. Deshalb müssen Maßnahmen ergriffen werden, die Eingriffe von außen verhindern. Eine mögliche Lösung wäre Verschlüsselung.
Quality of Service gewinnt immer mehr an Bedeutung. Im klassischen Internet war QoS nicht vorgesehen. Die Datenübertragung auf IP - Basis verläuft verbindungs- und zustandslos. Die Router wissen also nichts über evtl. Ströme zwischen einer Quelle und Senke. RFC 2386 beschreibt neuere QoS - Aspekte im klassischen Internet. QoS ist nur sinnvoll, wenn Datenströme fließen und zwischen zwei Nodes eine Art Verbindung besteht. In RFC 2386 wird QoS als "A set of service requirements to be met by the network while transporting a flow" klassifiziert. Anforderungen an das Netzwerk gibt es zum Beispiel hinsichtlich Jitter, Verzögerung und verfügbarer Bandbreite. Der Begriff QoS bedeutet also immer eine festgelegte anwendungsspezifische Auswahl von Kriterien, die garantiert werden soll. Interessant in Ad-hoc-Netzen sind vor allem die Verzögerungszeit und das Bandbreitenmanagement. Dafür sollten effektive Algorithmen zur Verfügung stehen.
Mobile Netze besitzen Einschränkungen, die eine Gewährleistung der QoS besonders schwierig machen. Nodes haben oftmals begrenzte Energie und Reichweite. Außerdem kommen Störungen der Funkstrecken oft vor und sind unberechenbar. Prinzipbedingt gibt es keine zentrale Managementstation. Die Zugriffs- und Routing-Techniken müssen für die Einhaltung der QoS sorgen, indem die Routen so gewählt werden, dass die Anforderungen erfüllt werden.
Ein Netz heißt combinatorial stable, wenn die Topologieveränderung langsam genug vonstatten gehen, um immer konsistente Routen in allen Nodes zu haben. Dies ist ein wichtige Vorraussetzung, um Quality of Service zu gewährleisten (notwendige Bedingung).
Wenn ein Netz die Quality of Service unabhängig von möglichen Topologie-Wechseln garantieren kann, heißt es QoS - robust. Eine abgeschwächte Form ist QoS - preserving. Hier wird nur das Beibehalten der Quality of Service im Zeitrahmen von einem erfolgreichen Topologie-Wechsel bis zum nächsten garantiert.
Der Fall, dass ein Node, z.B. durch Funkstörungen, komplett die Verbindung zum Netz verliert, wird nicht in die Quality of Service Betrachtung mit einbezogen, da das Netz darauf keinen Einfluss haben kann. Topologie - Updates treten vor allem auf, wenn neue Nodes dem Netz beitreten oder vorhandene Nodes das Netz (absichtlich) verlassen. Dies sollte die Quality of Service für den nicht von Änderungen betroffen Teil des Netzes nicht beeinflussen. Die Funkstrecke ist ein Shared-Medium-Netz. Je größer die Anzahl der Nodes ist, desto größer kann die Verzögerungszeit werden. Deshalb ist eine genügend große Kanal - Kapazitätsreserve nötig, um einen Höchstwert für die Verzögerung garantieren zu können.
QoS - Routing besteht aus 2 Teilabschnitten. Die erste Aufgabe ist das Finden einer Route, die die geforderten Qualitätsbedingungen erfüllt. Der zweite Schritt ist das Reservieren dieser Route für einen Datenfluss. Natürlich müssen danach die Metriken und Bandbreiten für die anderen Nodes neu berechnet werden.
Die optimale Routenbestimmung zur Erfüllung aller QoS - Parameter ist ein aufwendigen Verfahren mit zum Teil NP - vollständiger Komplexität. Deshalb werden oftmals approximierende Filterregeln angewandt, die eine semioptimale Suche gestatten. Es werden mehrere Routen bestimmt, die ein wichtiges Kriterium gut bzw. optimal erfüllen. Danach wird diese Liste anhand des nächsten Kriteriums untersucht. Dies geht so weiter bis zur letzten QoS - Anforderung.
Sollten mehrere Routen übrig bleiben, wird eine per Zufall ausgewählt.
Die Auswahl der Route hängt von einer möglichst genauen Kenntnis des Netzwerkzustandes ab. Es gibt local state und global state Information. Die local state Informationen sind Informationen über den Node selber. Sie beinhalten verbleibende CPU - Leistung sowie diverse Informationen über alle direkten Verbindungen zu den Nachbarn. Sie ist in jedem Node sofort verfügbar und entspricht dem Stand des Netzes. Die Gesamtheit aller local states wird als global state bezeichnet. Sie wird bei tabellenbasierten Routingverfahren ebenfalls in jedem Node gespeichert. Diese Information muss aber erst durch Austausch von Informationen gewonnen werden. Diese Topologie - Updates geschehen in regelmäßigen Abständen. Es wird dabei unterschieden zwischen link-state und distance-vector Protokollen. Dabei werden entweder die lokalen Zustände oder passende Distanz-Vektoren übertragen. In großen Netzen ist es ratsam, das Netz hierarchisch zu partitionieren. Dort werden nur die Zustände der einzelnen Cluster ausgetauscht.
Es gibt verschiedene Verfahren zur Festlegung einer Route. Beim source routing legt die Quelle einen mögliche Pfad mittels gespeichertem global state fest und teilt allen Nodes in diesem Pfad Vorgänger und Nachfolger mit. Das destination routing ist vergleichbar, hierbei ist jedoch das Ziel für die Route verantwortlich.
Das zweite Verfahren ist das distributed oder hop-by-hop routing. Hierbei sind mehrere Nodes am Festlegen des nächsten passenden Hops beteiligt. Die letzte Form ist das hierarchical routing. Hierbei werden die global states der einzelnen Cluster zur Bestimmung der Route herangezogen. In [4] werden zwei Routing-Mechanismen beschrieben. Ein Algorithmus nutzt nur die local state Informationen, während der andere auch global state Informationen voraussetzt [1]. Beide Algorithmen suchen bei Verlust einer Route nach einer neuen Route, die ebenfalls die QoS erfüllt. Bis zum Bestehen der neuen Route werden Pakete bestmöglich verschickt.
Um eine die Quality of Service dauerhaft zu gewährleisten, sollten Kontrollpakete höhere Priorität haben als Nutzdatenpakete. Ebenso sollten Pakete mit höhere Priorität Vorrang vor Paketen mit niedriger Priorität besitzen. Dies kann in Hochlastsituationen dazu führen, das für niederpriorisierte Pakete die QoS nicht mehr garantiert werden kann.
Beim Ausfall einer Route passiert in den Nodes folgendes: Abhängig vom Aufbau des Netzes kann der Router, der an dem Ausfall beteiligt ist, entweder selbst eine Ersatzroute aufbauen oder er teilt der Vorgängerstation bzw. dem Sender mit, dass die Route nicht mehr verfügbar ist. In diesem Fall muss die Quelle eine neue Route bestimmen.
Alternativ kann der Ausfall der Route für die Quelle ebenfalls sichtbar werden, durch Ausbleiben von regelmäßigen rückwärts gerichteten Refresher - Paketen.
Um die Gefahr einer QoS - Verletzung zu verringern, bietet sich die Nutzung von redundanten Routen an. Es gibt 3 verschieden Stufen der Redundanz. Die sicherste Stufe der Redundanz ist die Reservierung mehrerer paralleler Routen - fällt eine Route aus wird automatisch die zweite genutzt. Die zweite Möglichkeit ist das Speichern von Alternativrouten, ohne diese zu reservieren. Erst bei Ausfall der ersten Route wird die Ersatzroute reserviert. Unter Umständen ist die Route dann allerdings nicht mehr verfügbar oder bereits anderweitig vergeben. Die einfachste und unsicherste Variante ist die Neusuche beim Ausfall der Route.
Viele Routingprotokolle gehen davon aus, bidirektionale Verbindungen zu nutzen. Oftmals wird der Rückweg benutzt, um funktionierende Routen zu melden. Leider kann es passieren, dass Funkstrecken nur unidirektional arbeiten. Diese Funkstrecken werden von vielen Protokollen als fehlerhaft angesehen und nicht genutzt. Das Ziel von intelligenten Routingprotokollen sollte sein, diese unidirektionalen Routen mit zu nutzen. Allerdings wird in [18] gezeigt, dass bei Distance-Vector-Protokollen die Menge der zu übertragenen Informationen mit O(n²) statt mit O(n) steigt. Deshalb widerspricht die Nutzung von unidirektionalen Verbindungen anderen Kriterien wie Bandbreiteneffizienz und Energiesparsamkeit.
DSDV ist ein flaches Routing-Protokoll. Jeder Node hat eine Tabelle, die die Route zu allen bekannten Nodes enthält. Das Verfahren ist ähnlich zu Bellman-Ford. Die Tabelle enthält dabei mögliche Ziele und Anzahl der Hops. Im Gegensatz zu Bellman-Ford wird Schleifenfreiheit durch Sequenznummern gewährleistet. Mittels dieser Sequenznummern werden unterbrochene Routen von neuen Routen unterschieden. Um über das aktuelle Netz informiert zu sein, sind regelmäßige Updates nötig, was zusätzlich Bandbreite benötigt. Es gibt zwei Arten von Update - Nachrichten. Ein vollständiges Update enthält alle Information, es werden evtl. mehrere Datenpakete benötigt. Die zweite Möglichkeit ist das Verschicken von Änderungen. Diese Updates passen in der Regel in eine network data unit.
Zum Routing wird immer die Route mit der aktuellsten Sequenznummer wird genutzt. Falls zwei Updates mit der selben Sequenznummer einen Node erreichen, wird die Route mit der kleineren Metrik genutzt.
CGSR ist ein hierarchischen Protokoll, welches auf DSDV aufsetzt. Es benutzt zusätzlich diverse Heuristiken, um das Routing festzulegen. Mehrere Nodes werden zu Clustern zusammengefasst. Ein Node übernimmt die Rolle des cluster heads. Dafür gibt es einen Cluster-head-selection-Algorithmus. Bei sehr mobilen Teilnehmern kommt es oft zu aufwendigen Wechseln des Cluster-heads. Deshalb wird ein Least Cluster Change Algorithmus verwendet, der den cluster head nur ändert, wenn zwei cluster heads in direkten Kontakt geraten oder ein Node keinen Kontakt mehr zu irgendeinem cluster head bekommt.
Das Routing geht von der Quelle über Ihren cluster head zu einem gateway node und von dort aus zu einem anderen cluster head. Dieser routet das Pakt dann weiter.
Gatway nodes sind Teilnehmer, die in Kontakt mit 2 oder mehreren cluster heads sind. Für dieses Protokoll sind je Node zwei Tabellen notwenig, die cluster member table und die routing table.
Dies ist ein Routing-Protokoll, welches das Ziel hat, dass alle Nodes die nötigen Routing-Informationen besitzen. Jeder Node hält vier Tabellen: Die distance table, die routing table, die link-cost table and die message retransmission list (MRL).
Auch hier werden zwischen direkten Nachbarn Update Messages ausgetauscht, wobei festgelegt werden kann, welche Updates zu bestätigen sind. Dabei speichert die MRL, welche Updates nochmals verschickt werden müssen bzw. welche Bestätigungen noch ausstehen. Neue Nodes erfahren von ihren Nachbarn durch Empfangen von Update Messages. Wenn ein Node keine Messages zu verschicken hat, benutzt er Hello-Messages. Wenn innerhalb eines Timeouts keine Message empfangen wird, gilt die Verbindung als gestört. Neuen Nodes werden Kopien der eigenen Routing-Tabellen geschickt. Die Besonderheit liegt in einem Verfahren, welches Schleifenfreiheit gewährleistet. Das count-to-infinity-Problem wird vermieden, indem alle Nodes einen Konsistenzcheck aller Informationen der Nachbarn machen.
AODV ist ein Routing-Protokoll, welches auf dem DSDV-Algorithmus beruht. Es minimiert aber die Anzahl der benötigten Broadcasts, indem die Routen nur bei Bedarf bestimmt werden. Es werden also keine kompletten Routing-Tabellen erstellt. Nodes, die sich nicht im Pfad befinden, aktualisieren auch nicht ihre Routing-Informationen und tauschen auch keine Routing-Informationen aus.
Wenn ein Node Daten senden will, ohne die Route zum Ziel zu kennen, wird ein path discovery process gestartet. Dabei werden route request (RREQ) broadcasts geflutet, bis das Ziel oder ein Node mit einer Route zum Ziel erreicht worden ist. Dieser Node schickt in Richtung Vorgänger ein route reply (RREP) Nachricht zurück. Dieser schickt dieses zu seinem Vorgänger und speichert die Route zum Zielhost. Bei AODV werden Sequenznummern eingesetzt. Jeder Node erhöht seine Sequenznummer mit jedem gesendetem RREQ. Zusammen mit der Adresse des Nodes sind die RREQs damit einzigartig. Falls ein RREQ doppelt ankommt, wird er verworfen. Wenn sich Teilnehmer bewegen, ist eine Neuberechnung der Route notwendig. Bewegt sich die Quelle, kann sie die Berechnung neu anstoßen. Wenn eine andere Station sich bewegt, erkennt das die Vorgängerstation und schickt eine link failure message zu ihrem Vorgänger. Diese wird bis zur Quelle weitergereicht, die eine Neuberechnung veranlassen kann.
Wenn sich der Zielhost nicht im Cache befindet, wird wie eine route request broadcast message mit einer ID, Ziel- und Quelladresse verschickt. Jeder Node, der diese Message erhält, fügt seine Adresse zu einer Liste hinzu. Erhält ein Node ein Paket, dessen ID er bereits kennt oder in dessen Route er bereits steht, verwirft er diese Message. Kennt ein Empfänger eine funktionierende Route zum Ziel oder erreicht die Message den Empfänger, wird die Route vervollständigt und zurück geschickt. Dabei kann der route reply Huckepack in einem neuen route request zurück geschickt werden. Hin- und Rückweg können sich also unterscheiden. Dies erlaubt die Nutzung von unidirektionalen Verbindungen. Wenn eine Verbindung unterbrochen wird, wird diese Verbindung aus dem Cache gelöscht und route error messages werden verschickt. Alle Stationen, die diese Meldungen empfangen, schneiden Ihre Routen an der entsprechenden Stelle ab. Weiterhin werden acknowlegdements benutzt, um korrekte Verbindungen anzuzeigen. Dazu gehören auch passive ACKs, d.h. Mithören, dass weitergesendet wurde.
TORA ist ein verteiltes Routing-Verfahren, welches auf link reversal beruht. Das Ziel von TORA ist die Konzentration der Kontrollmessages auf die nähere Umgebung von Topologieveränderungen. Die Nodes müssen Routing-Informationen nur für alle angrenzende Nodes speichern. Routen werden dabei über direkte azyklische Graphen mit der Höhe als Metrik bestimmt. Dabei werden den Links Richtungen zugewiesen. Daten werden nur Downstream von "höhere" Nodes an "niedrigere" Nodes weitergeleitet. TORA ist ähnlich zu LMR. Topologieveränderungen bewirken dabei eine Umkehrung der Richtung von angrenzenden Verbindungen.
TORA setzt eine gleichmäßige Zeitbasis auf allen Nodes voraus, z.B. durch GPS, da die Kontrollmessages auch eine Zeit beinhalten. Dies soll eine schnellere Konvergenz der Routen ermöglichen.
ABR definiert eine neue Metrik für Ad-hoc-Netzwerke: degree of association stability. Anhand dieser Metrik werden die Routen festgelegt. Jeder Node schickt dabei in regelmäßigen Abständen ein beaconing Signal. Für jedes empfangene beaconing Signal erhöht eine Node den associativity tic (Assoziativitätszähler) für den Sender. Der Assoziativitätszähler wird zurück gesetzt, wenn die Nachbarn oder der Node selber sich aus der Reichweite bewegen. Das Ziel dieses Verfahrens ist die Nutzung lang bestehender stabiler Routen.
Bei der Routensuche werden die Assoziativitätszähler für die Route mit übertragen und in einer Liste gespeichert. Das Ziel kann dann aus mehreren Routen die beste wählen und schickt den REPLY auf dem selben Weg zurück. Die Nodes, die den REPLY weiterleiten, markieren die Route als gültig. Routenwartung wird ebenfalls über Kontrollpakete mit Assoziativitätszähler gelöst.
SSR nutzt als Metriken die Signalstärke und Mobilität von Teilnehmern. Das Ziel ist die Nutzung von Routen mit großen Signalstärken. Dieses Protokoll ist unterteilt in das Dynamic Routing Protokoll (DRP) und das Static Routing Protocol (SRP). Das DRP verwaltet die Signal Stability Table und die Routing Table. Deshalb nimmt DRP alle empfangenen Pakete entgegen und passt alle Tabellen entsprechend an. Danach werden die Pakete an das SRP weitergereicht. SRP leitet die Pakete weiter oder legt sie in den Stack. Falls keine Route zum Weiterleiten vorhanden ist, wird ein Route Request geschickt. Dieser wird nur weitergeleitet, wenn er über ein starkes Signal empfangen wird. Der Zielnode schickt die Antwort auf demselben Weg zurück. Erreicht die Quelle keine Antwort, schickt sie nach einem Timeout einen neuen Request mit abgesenker Anforderung an die Signalstärke. Bei einem Fehler wird die Quelle benachrichtigt, die ihrerseits über eine erase-message alle beteiligten Nodes informiert.
Spine Routing ist weder ein reines On-Demand-Routing-Verfahren, noch ein ein tabellenbasiertes Verfahren. Hierbei wird eine Struktur namens Spine (Wirbelsäule) genutzt. Das Spine besteht aus einem kleinen, relativ stabilen Subnetz, welches zur Routenbildung genutzt wird. Es fungiert als virtuelles Backbone. Es soll nicht dazu dienen, die Informationen zu transportieren. Dies geschieht nur, wenn andere Routen nicht verfügbar sind. Allerdings wird das Spine als Multicast-Backbone genutzt. Per Definition ist ein Node entweder selbst Teil des Spines oder ist zumindest Nachbar eines entsprechenden Nodes. Dadurch wird ein geringer Wartungsaufwand erreicht, da die Anzahl der Spine Nodes geringer ist als die Gesamtzahl der Nodes und jeder Node Kontakt zum Spine hat. In [19] werden zwei Varianten beschrieben: (a) Optimal Spine Routing OSR, welches ein komplettes und aktuelles Wissen über die Toplogie voraussetzt und (b) Partialknowledge Spine Routing PSR, welches nicht die komplette Topologie kennen muss.
Die Suche nach einem optimalen Spine erfolgt mittels einem minumum connected dominating set (MCDS). Dies ist ein NP-vollständiges Problem. Deshalb müssen dafür Approximationsalgorithmen verwendet werden.
Die Routenbestimmung in LMR ist ähnlich zu TORA ein Link-Reversal-Mechanismus, bei dem fehlerhafte Verbindungen die Richtung der upstream-Verbindungen umkehren, bis die Topologie wieder eine komplette Downstream-Verbindung von der Quelle zum Ziel hat.
LMR setzt dabei keine gemeinsame Zeitbasis voraus. Die hat den Nachteil,
dass bei Link-Fehlern die Gefahr besteht, dass LMR temporär falsche
Routen bildet, die das Netz in zwei Teile spalten.
CEDAR [20] ist ein Routing-Verfahren, welches sich für QoS-Anforderungen eignet. Hier wird ebenfalls ein Subset des Netzes erzeugt, welches als Core bezeichnet wird. Die Zustände der Verbindungen werden weiter verbreitet (links state propagation). Dabei ist das Ziel, dass stabile bandbreitenstarke Verbindungen auch entfernten Nodes bekannt sind, während schwache, dynamische Verbindungen nur lokal gepeichert werden.
Bei der Routenberechnung wird zuerst eine Core-Verbindung von der Quellendomäne bis zur Zieldomäne gesucht. Dabei wird iterativ ein Weg von der Quelle zur am weitesten möglichen Zwischenstation des Cores gesucht. Der Weg muss dabei die Bandbreiteanforderungen erfüllen. Diese Zwischenstation wird dann die neue Quelle und sucht weiter, bis die Zieldomäne erreicht ist.
RDMAR [21] ist ein reaktives Routing-Protokoll, welches konzipiert wurde, um Bandbreite zu sparen.
| Verfahren | Routenbestimmung | QoS | Schleifen- frei | Flach/ hierarchisch | Multicast- fähig |
| DSDV | proaktiv | ja | flach | ||
| CGSR | proaktiv | ja | Hierarchisch
cluster |
Mit Aufsatz[5] | |
| WRP | proaktiv | ja | flach | ||
| AODV | reaktiv | ja | flach | ja | |
| DSR | reaktiv | ja | flach | ||
| TORA | reaktiv | ja | flach | Mit Aufsatz[6] | |
| ABR | reaktiv | ja | ja | flach | |
| SSR | reaktiv | ja | flach | ||
| CEDAR | reaktiv | ja | ja | Hierarchisch
Backbone |
|
| Spine Routing | reaktiv | ja | Hierarchisch
(virtueller) Backbone |
ja | |
| RDMAR | reaktiv | ja | flach |
Weitere Vergleiche hinsichtlich Komplexität und Speicherbedarf wurden in [2] vorgenommen.
Es existieren noch viele weitere Routing-Protokolle, die einige der oben genannten Prinzipien kombiniert oder auch neue Methoden zur Lösung benutzen. Insbesondere Multicast und QoS-Aspekte verdienen noch weitere Betrachtung. Allerdings ist Routing nur ein Teil des Netzes. Viele Eigenschaften der Routing-Protokolle können erst genutzt werden, wenn die Sicherungsschicht bestimmte Eigenschaften erfüllt. Ein weiterer Forschungsaspekt sollte also die Integration der verschiedenen Schichten sein. Hier bieten sich Performance-Tests und Qualitätsuntersuchungen an. Weitere Forschungsgebiete sind Anwendungsmöglichkeiten. In [24] wird z.B. die Umsetzung von TCP in Ad-hoc Netzen mittels ATCP betrachtet, was einen großen Spieraum für Anwendungen gibt.