Routingalgorithmen für infrastrukturlose Paketfunknetze mit kooperativen mobilen Stationen

Abstract

Die Dissertation beschreibt die Funktionsweise von Routingalgorithmen und deren Einsatz für sogenannte Ad-hoc Funknetzwerke. Diese Netzwerke erfordern keine Infrastruktur, die beteiligten Stationen bilden selbständig ein Kommunikationsnetz, sie kooperieren und leiten dabei Daten anderer Stationen weiter. Durch mobile Stationen und fehleranfällige Funkverbindungen sind spezielle Algorithmen nötig, um Routing in diesen Netzen zu ermöglichen. Die Arbeit beginnt mit einem Überblick der gängigen Standardalgorithmen, daran schliesst sich eine Übersicht und eine Klassifizierung bereits existierender Algorithmen für Ad-hoc Netzwerke an. Anschliessend wird die zentrale Neuentwicklung der Arbeit beschrieben: der “Tree Exchange Routing Algorithm” (TERA), welcher sich durch effiziente Routenverwaltung auszeichnet. Zur weiteren Verbesserung der Bandbreiteneffizienz wird zusätzlich eine Erweiterung von TERA spezifiziert, die eine Neuberechnung von Routen nur bei grossen Netzveränderungen zulässt. Die durchgeführten Simulationen zeigen, dass dadurch die Anzahl von Routingbotschaften halbiert werden kann. Weiterhin wird gezeigt, wie die Belastung einzelner Stationen in Ad-hoc Netzwerken mittels Zufallsverteilungen deutlich verringert werden kann. Ausserdem werden Verfahren zur Anbindung von Ad-hoc Netzwerken an das Internet vorgestellt. Dabei werden Sicherheitsprobleme diskutiert und Protokollanpassungen erläutert, die für eine erfolgreiche Kooperation von Adhoc Routing mit dem Festnetzrouting nötig sind.

This dissertatiom introduces some improvements in ad hoc network routing. This kind of networking does not require any kind of infrastructure, all participating hosts have to cooperate to build up a self organizing communication network. Host mobility and error-prone wireless links require special routing algorithms for this environment. The dissertation starts with an introduction to standard routing algorithms and continues with a description and a classification of existing ad hoc routing algorithms. After that, a new algorithm called the “Tree Exchange Routing Algorithm (TERA)” is presented, which offers a highly efficient path calculation method. A further improvement in bandwidth efficiency is achieved by extending TERA with restricted route optimization. This extension limits new route calculations to major topology changes of the network. Simulations show that these improvments allow a reduction of routing messages up to 50 %. An additional chapter explains the implementation of load distribution in TERA to reduce the network load of single hosts by randomizing the data flow. After that, some advanced methods for connecting ad hoc networks to the internet are described. This includes a discussion of security problems and a description of necessary protocol adaptations to enable interaction between ad hoc and internet routing.