Lade Inhalt...

Routing in 3D Networks

Studienarbeit 2010 15 Seiten

Informatik - Technische Informatik

Leseprobe

Inhaltsverzeichnis

1 Einleitung

2 Routing in 3D Netzwerken
2.1 Routing-Algorithmen für 3D Netzwerke
2.2 3D Routing-Algorithmus
2.2.1 Regionbeschränkte zufällige Versuche
2.2.2 Random Walk auf der Ober äche
2.2.3 Spärliche Subgraphen
2.2.4 Kraft des Random Walk

3 Dual Graph
3.1 Aufbau
3.2 Ownership Selection
3.3 Verbindungen im Dual Graph
3.4 Routing auf dem Dual Graph

4 Simulation

Literaturverzeichnis

1 Einleitung

Sensor und Wireless Netzwerke haben in letzter Zeit viel Aufmerksamkeit erfahren, nicht nur auf Grund der unzähligen Anwendungen als auch der exiblen Einsatzgebiete. Das Fundamentale in einem Netzwerk ist neben der Blockblidung, der Austausch von Informationen zwischen den einzelnen Netzwerkknoten. Das bedeutet, die Aktion des Sendens einer Nachricht vom Sendeknoten bis hin zum Zielknoten. Um dies erfolgreich zu ermöglichen sind so genannte RoutingAlgorithmen notwendig, welche die Nachrichten durch das Netzwerk leiten. Es existieren zahlreiche Routing-Algorithmen, z.B. für das Internet mit dem IP Die unterschiedlichen Anforderungen der verschiedenen Netzwerke erfordern technologiespezi sche Routingtechniken. In dieser Ausarbeitung werden RoutingAlgorithmen für groÿe ad hoc Netzwerke betrachtet. Im Speziellen untersucht die Arbeit Algorithmen für 3-dimensionale Netzwerke. Im Gegensatz zum IP, auf dem das Internet basiert, welches groÿe Forwarding Tables nutzt, kann es nicht für ad hoc Verbindungen eingesetzt werden.

Ein Routing-Algorithmus für ad hoc Netzwerke muss nicht nur das Problem des instabilen Netzwerkes, sondern auch mit den begrenzten Ressourcen und den geringen alternativen Zweigen umgehen können. Das instabile Netzwerk ist auf der Mobilität der Knoten begründet und der Fluktuation des drahtlosen Kommunikations-Mediums, welches im Gegensatz zum Kabel sehr veränderlich ist. Die beschränkenden Hardwareanforderungen erschweren das Routing weiter. Die Knoten haben einen kleinen Speicher und dürfen nur wenig Strom verbrauchen. Die Geräte sind oft batteriebetrieben.

Geogra sche Routing Protokolle leiten die Pakete an den Nachbarn, der näher am Zielknoten ist, weiter. Diese Strategie wird solange fortgesetzt, bis die Nachricht beim Empfänger angelangt ist. Dafür muss jeder Knoten sich selbst und seine Nachbarn kennen. Ein Knoten kann durch weitere Hardwareunterstützung die Position lernen, wie z.B. bei GPS oder mit Lokalisierungsalgorithmen. Weiterhin muss die Position des Zielknotens in jedem Routingschritt bekannt sein. Die Anfrage 1

Internet-Protokoll

1 Einleitung

über die Position eines Netzwerkknotens wird durch einen Lokalisierungs-Service gewährleistet.

Geogra sche Routing-Algorithmen werden so de niert, dass die Basis der Entscheidung nur auf Kenntnis der aktuellen eigenen Position, seiner Nachbarn und des Zielknotens beruht. Dabei wird vorausgesetzt, dass die Netzwerkknoten speicherlos sind, d.h. die Knoten speichern keine Zustände von Nachrichten. Dadurch ist der Routingzustand unsichtbar. Der zusätzliche Speicheroverhead wird reduziert, welcher zuvor die Anzahl der weitergeleiteten Pakete limitiert hat. Weiterhin existiert keine globale Sicht der Knoten auf das Netzwerk. Jede Entscheidung wird nur auf Grundlage der lokalen Informationen gefällt. Das erleichtert die Aktualisierung der Daten, z.B. wenn es eine Veränderung im Netzwerk gibt. Im Gegensatz dazu stehen die Routing-Algorithmen, bei denen eine globale Netzwerksicht existiert. Bei diesen Algorithmen ist es möglich, den optimalen Pfad zu nden, aber bei einer Änderung muss das ganze Netzwerk rekon guriert werden. Dies ist ideal für statische Netze, aber nicht für ad hoc Netzwerke, wo eine kontinuierliche Veränderung der Topology unvermeidbar ist.

2 Routing in 3D Netzwerken

Ein wesentliches Konzept beim Geogra schen Routing ist greedy forwarding . Dabei leitet jeder Knoten die Nachricht zu dem Nachbarn weiter, der am nächsten zum Ziel liegt. Diese Art ist sehr einfach, aber e zient für die meisten Netzwerke. Jedoch gibt es Topologien, bei denen dieses Verfahren scheitert. Als Beispiel dient eine Nachricht, die zu einem Knoten gelangt, bei dem alle Nachbarn weiter entfernt zum Ziel liegen als der Knoten mit der Nachricht selbst. Dies tritt dann auf, wenn in einer Region kein Netzwerk vorhanden ist. In 2-dimensionalen Netzwerken kann dies mit face routing oder Varianten davon gelöst werden. Z.B. bei greedyface-greedy wird eine Nachricht solange greedy geroutet, bis es ein Problem gibt. Danach wird mit face geroutet, bis wieder ein Knoten gefunden ist, der einen kleineren Abstand zum Ziel besitzt als zu Beginn, wo das Problem auftrat. Dieser Algorithmus wurde 1999 entwickelt und garantiert ein erfolgreiches Routing. Das Verfahren ist jedoch nicht auf 3-dimensionale Netzwerke anwendbar, da faces eine planarisierte Topology erfordert.

Diese Arbeit zeigt eine Möglichkeit, wie das Verhalten von 2D zu 3D adaptiert werden kann. Als Grundlage gilt weiterhin das greedy-Routing. Um jedoch die Fassetten im Dreidimensionalen zu beschreiben, sind andere Verfahren notwendig als im zweidimensionalen Fall.

2.1 Routing-Algorithmen für 3D Netzwerke

In einer Untersuchung wurde bewiesen, dass es keinen deterministischen, lokalen und gedächnislosen Routing-Algorithmus gibt, der die Zustellung der Pakete garantiert.1 Damit gibt es auch keinen speicherlosen Algorithmus, der dies gewährleisten könnte. Dennoch soll hier solch ein Verfahren konstruiert werden.

Als Motivation dient die künstliche Problemstellung in Abbildung 2.1. Dieses Beispiel stellt z.B. die Erdkugel dar. Auf der Ober äche sind in regelmäÿigen Abständen Knoten verteilt. Von einigen gibt es eine Verbindung in das Innere der Kugel. Auf der Auÿen äche existiert nur ein Meridian, der alle Breitenkreise verbindet. Es soll nun von einem Knoten auf der Ober äche eine Nachricht zum inneren Knoten t geleitet werden. Der Knoten t ist aber nur mit dem Punkt w auf der Auÿen äche verbunden. Somit muss die Nachricht zuerst diesen erlangen. Da nur lokale Informationen zur Verfügung stehen, kann dies nur durch Erkundung der absteigenden Linien auf der Ober äche erreicht werden. Dieses Beispiel ist so speziell konstruiert, dass jeder greedy-Routingalgorithmus scheitern wird, da der ganze Weg bis zum Zielknoten bergauf verläuft. D.h. jeder Knoten auf dem Weg bis zum Knoten w ist weiter entfernt, als der Knoten von dem die Nachricht aus gesendet wird. Ebenfalls nicht geeignet ist ein Random-Routingalgorithmus, da es viel zu viele Möglichkeiten gibt, wobei aber nur ein Weg zum Zielknoten führt.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2.1: Lower Bound Graph aus [RFRW]

[...]


1 Quelle: [DKN]

Details

Seiten
15
Jahr
2010
ISBN (eBook)
9783668397675
ISBN (Buch)
9783668397682
Dateigröße
829 KB
Sprache
Deutsch
Katalognummer
v353346
Institution / Hochschule
Technische Universität Dresden
Note
2,0
Schlagworte
routing networks

Autor

Zurück

Titel: Routing in 3D Networks