Advantages and limitations of position-based communication in wireless ad-hoc networks

Abstract

Der Begriff "Wireless Ad-hoc Network" lässt sich ungefähr mit drahtloses, infrastrukturloses Netzwerk übersetzen und bezeichnet eine neue Form von drahlosen Netzwerken. Die Teilnehmer (Stationen) in einem solchen Netzwerk können drahtlos (meistens per Funk) miteinander kommunizieren und benötigen keine vorgegebene Infrastruktur oder zentrale Kontrollinstanz. Im Allgemeinen ist es nicht möglich, daß jeder Teilnehmer mit jeden anderen Teilnehmer direkt kommuniziert. Ein Ad-hoc-Netzwerk benötigt für die Datenübertragung zwischen beliebigen Teilnehmern einen oder mehrere Hops, also Teilstrecken zwischen individuellen Stationen. Multi-hop-Systeme werden häufig als Mobilfunksysteme der vierten Generation bezeichnet. Die vorliegende Dissertation präsentiert mit dem SDT/VAR-Protokoll, ein effizientes Kommunikationsprotokoll für die Datenübertragung in Ad-hoc-Netzwerken. Dieses Protokoll verwendet die Prinzipien der Delaunay-Triangulation für den Aufbau einer effizienten Netzwerktopologie und das Voronoi-Diagramm für die Implementierung von Greedy/perimeter-Routing. Ein wichtiger Teil dieser Arbeit beschäftigt sich des Weiteren mit der Fehlertoleranz von Greedy/perimeter-Routing. Wir untersuchen das Verhalten von Greedy/perimeter-Routing in einem fehleranfälligen Netzwerk und bestimmten den Aufwand, der notwendig ist, um die Datenübertragung in einem Netzwerk mit Crash-Fehlern zu garantieren. Des Weitern analysieren wir die Zuverlässigkeit von positionsbasierenden Protokollen (wie Greedy/perimeter-Routing) wenn keine exakten Positionsangaben verfügbar sind und zeigen das Perimeter-Routing die Kommunikation nicht garantieren kann, wenn die Teilnehmer im Netzwerk mobil sind.<br />

Wireless ad-hoc networks are a hot topic in wireless computing that attract a lot of attention to military, government and commercial customers. Wireless ad-hoc networks are made up of nodes that communicate with each other over a wireless medium in the absence of a fixed infrastructure and any centralized control. Direct communication between two arbitrary nodes is generally not possible. Communication between arbitrary nodes hence requires a multi-hop routing protocol. This thesis presents SDT/VAR, an efficient protocol for communication in wireless ad-hoc networks. The Short delaunay triangulation (SDT) is a powerful topology based on the construction rules of the Delaunay triangulation and the Voronoi-aided routing (VAR) protocol is an efficient implementation of the well known greedy/perimeter routing approach. The big advantage of our approach is efficiency: The computation of the Short delaunay triangulation yields automatically to local Voronoi diagrams for the efficient implementation of Voronoi-aided routing. Algorithms proposed until today generally separate topology control and routing, but a common development upon one efficient data structure lead to considerably increased performance. An important part of this thesis is on the fault-tolerance and on the reliability of greedy/perimeter routing. Most existing wireless ad-hoc network routing protocols assume a fault-free environment during message delivery. However, this assumption does not hold in realistic environments. We analyze the behavior of greedy/perimeter routing in the context of crash failures and the reliability of greedy/perimeter routing with respect to imprecise position information and mobile nodes.