ISBN 9783843906081

978-3-8439-0608-1, Reihe Informationstechnik

Rico Radeke
Beiträge zum Geographischen Routing auf Virtuellen Koordinaten für Kommunikationsnetze

213 Seiten, Dissertation Technische Universität Dresden (2011), Softcover, A5

Zusammenfassung / Abstract

Geographisches Routing ist ein bekannter Ansatz, um topographische Informationen als Basis für Weiterleitungsentscheidungen für Datenpakete in Kommunikationsnetzen zu nutzen. Im Vergleich zu anderen Routingalgorithmen wird weniger Overhead benötigt, da beim Geographischen Routing keine Routen festgelegt werden müssen, sondern jeder Netzknoten eine eigene Weiterleitungsentscheidung trifft.

Topographische Informationen bilden zumeist die topologischen Eigenheiten des zugrunde liegenden Kommunikationsnetzes nur unzureichend ab. Speziell die topographisch kürzesten Wege in Richtung Ziel müssen nicht immer topologisch sinnvoll sein. So nutzen Rao et al. in NoGeo anstatt der geographischen virtuelle Koordinaten, die aus der topologischen Lage der Knoten im Netz abgeleitet werden.

Der ursprüngliche NoGeo-Ansatz wird in der vorliegenden Arbeit aufgegriffen, vereinfacht und verbessert. Dazu wird das neue, strikt k-lokale Verfahren Spring+ konzipiert. Dieses nutzt das Modell eines Feder-Masse-Systems, bei dem Knoten im Netz auf Massepunkte und Kanten im Netz auf Federn abgebildet werden. Simulativ wird belegt, dass Spring+ in der Initialphase schneller virtuelle Koordinaten zuweist, kürzere Routen und höhere Zustellungswahrscheinlichkeiten für ein einfaches Geographisches Routing ermöglicht.

Es erfolgt eine analytische und simulative Untersuchung der Zusammenhänge von Knotengrad und durchschnittlicher Entfernung von n-Hop-Nachbarn in zufallsbasierten Unit-Disc-Graphen, um eine verbesserte Distanzschätzung zwischen Knoten in einem Netzwerk zu ermöglichen. Um komplexere Netzstrukturen (z. B. nichtplanare Graphen) besser abbilden zu können, wird ein dreidimensionales Geographisches Routing konzipiert, welches 3D-Hindernisse auf deren Oberfläche mittels lokalem Fluten umrundet.

Schließlich werden Dienst- und Netzgüteparameter von Kommunikationsnetzen genutzt, um virtuelle Koordinaten für Knoten zu bestimmen. Gewünschte Kanten (mit zu bevorzugenden Metriken) werden durch kurze Federn ersetzt, um Knoten nah aneinander zu platzieren, die auf "`guten"' Kommunikationspfaden liegen. Ein Geographisches Routing auf diesen virtuellen Metrik-basierten Koordinaten erzielt hinsichtlich der zum Aufbau vorher genutzten Metrik eine bessere Leistung. Simulative Untersuchungen zeigen, dass nicht immer optimale Wege gefunden werden, jedoch der Overhead beim Einsatz des k-lokalen Verfahrens gut skaliert und das Gesamtverfahren akzeptable Ergebnisse liefert.