In dieser Ausarbeitung werden Routing-Algorithmen 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.
Sensor und Wireless Netzwerke haben in letzter Zeit viel Aufmerksamkeit erfahren, nicht nur auf Grund der unzähligen Anwendungen und der flexiblen 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 Routing-Algorithmen 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 echnologiespezifische Routingtechniken.
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 Oberflä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
Zielsetzung & Themen
Die vorliegende Arbeit untersucht effiziente Routing-Methoden für 3D-Ad-hoc-Netzwerke, wobei der Fokus auf speicherlosen Algorithmen liegt, die ohne globale Netzwerkinformationen auskommen. Ziel ist es, Strategien zu entwickeln und zu evaluieren, die das bekannte "Greedy-Forwarding"-Prinzip aus der 2D-Welt für den dreidimensionalen Raum adaptieren und so eine zuverlässige Zustellung von Nachrichten in dynamischen Topologien ermöglichen.
- Geografisches Routing in drahtlosen Ad-hoc-Netzwerken
- Adaption von 2D-Routing-Konzepten auf 3D-Topologien
- Entwicklung und Optimierung von 3D-Routing-Algorithmen
- Konstruktion und Nutzung von Dual-Graphen zur Pfadfindung
- Vergleichende Simulation verschiedener Routing-Ansätze
Auszug aus dem Buch
3.1 Aufbau
Der existierende Graph G mit den Knoten V und den Verbindungen E wird auf einen so genannten dual Graph G´ = (V´, E´) abgebildet. Das Routing erfolgt dann nur noch auf G´. Der Dual Graph stellt ein abstraktes Würfelgitter dar. An den Verbindungspunkten des imaginären Gitters liegen die Dual Vertices(DV). Ein DV ist als eine Art Kugel vorstellbar, wobei der Radius p einen Einzugsbereich für die Punkte im Gitter definiert. Die DV´s werden nur neben realen Knoten platziert, um ein Gitter ähnlich wie G zu erhalten. Somit werden die Knoten vom realen irregulären Netzwerk auf das virtuelle reguläre Netzwerk abgebildet, indem die Knoten mit Hilfe der DV´s auf die Verbindungspunkte des Gitters gezogen werden. Die Relation zwischen G und G´ ist jedoch nicht bijektiv. Verbindungen in G´ exisiteren nur zwischen direkten Nachbarn. Wenn eine Verbindung in G´ zwischen 2 DV´s besteht, impliziert dies eine Verbindung in G zwischen den enthaltenen Knoten von den DV´s. Umgekehrt gilt das Gleiche.
Zusammenfassung der Kapitel
1 Einleitung: Dieses Kapitel erläutert die Herausforderungen beim Routing in drahtlosen Ad-hoc-Netzwerken und begründet die Notwendigkeit spezieller Algorithmen für den dreidimensionalen Raum.
2 Routing in 3D Netzwerken: Hier werden grundlegende Konzepte wie "Greedy Forwarding" und die spezifischen Anforderungen für 3D-Topologien sowie verschiedene Optimierungsstrategien zur Verbesserung der Routing-Effizienz vorgestellt.
3 Dual Graph: Dieses Kapitel beschreibt die mathematische Konstruktion eines virtuellen Würfelgitters (Dual Graph), welches dazu dient, das Routing durch eine strukturierte Abbildung des irregulären physischen Netzwerks zu vereinfachen.
4 Simulation: Das abschließende Kapitel evaluiert die vorgestellten Routing-Verfahren anhand verschiedener Netzwerkkonfigurationen und vergleicht deren Performance hinsichtlich des auftretenden Overheads.
Schlüsselwörter
Geografisches Routing, Ad-hoc-Netzwerke, 3D Netzwerke, Greedy Forwarding, Dual Graph, Random Walk, Routing-Algorithmen, Drahtlose Kommunikation, Netzwerktopologie, Speicherlose Algorithmen, Datenweiterleitung, Simulationsanalyse.
Häufig gestellte Fragen
Worum geht es in dieser Arbeit grundsätzlich?
Die Arbeit beschäftigt sich mit den theoretischen Grundlagen und praktischen Ansätzen für das Routing von Nachrichten in dreidimensionalen Ad-hoc-Netzwerken.
Was sind die zentralen Themenfelder?
Die Schwerpunkte liegen auf der geografischen Adressierung, der Abbildung von Netzwerkknoten auf virtuelle Strukturen (Dual Graphen) und der Optimierung des Routings durch zufallsbasierte Verfahren.
Was ist das primäre Ziel der Arbeit?
Das Hauptziel ist die Entwicklung speicherloser Routing-Algorithmen, die auch in 3D-Topologien eine erfolgreiche Paketzustellung ohne globale Netzwerksicht garantieren können.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit kombiniert theoretische Herleitungen zur Graphentheorie mit einer simulationsbasierten Leistungsanalyse, um verschiedene Routing-Verfahren empirisch zu vergleichen.
Was wird im Hauptteil behandelt?
Der Hauptteil analysiert die Schwächen herkömmlicher 2D-Ansätze, führt den Dual-Graph-Ansatz zur Abstraktion ein und diskutiert Optimierungstechniken wie Random Walks.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind geografisches Routing, Ad-hoc-Netzwerke, Dual Graph, Greedy Forwarding und netzwerkübergreifende Zustellgarantie.
Was ist die spezifische Funktion eines Dual Vertices (DV)?
Ein Dual Vertex dient als lokaler Repräsentant für einen oder mehrere Netzwerkknoten innerhalb eines virtuellen Würfelgitters, um das Routing zu vereinfachen.
Wie unterscheidet sich der hier vorgestellte Ansatz vom klassischen "Face Routing"?
Im Gegensatz zum 2D-Face-Routing, das eine planare Topologie voraussetzt, nutzt der 3D-Ansatz eine "Greedy-Random-Greedy"-Strategie, da im 3D-Raum keine direkt übertragbare Definition von "Faces" existiert.
- Quote paper
- Peter Hillmann (Author), 2010, Routing in 3D Networks, Munich, GRIN Verlag, https://www.grin.com/document/353346
