imported>Unermüdlich: unnötig

2021-10-02T18:09:41Z

unnötig

Neue Seite

'''Greedy Perimeter Stateless Routing in Wireless Networks''' ([[Englische Sprache|engl.]] „Greedy-Perimeter-Wegewahl in Funknetzen“, [[Abkürzung]] '''GPSR''') ist ein [[Routing]]-Protokoll für [[Mobiles Ad-hoc-Netz|mobile Ad-hoc-Netze]], also ein Verfahren, mit dem [[Datenpaket]]e in spontan aufgebauten [[Rechnernetz]]en an ihr Bestimmungsziel gelotst werden sollen.

Das Protokoll wurde von B. Karp entwickelt und verdankt seinen Namen seiner Funktionsweise, da es abwechselnd zielstrebig wie ein [[Greedy-Algorithmus]] vorgeht und den Zielpunkt auf dem [[Perimeter]] umkreist.

== Koordinaten statt Empfängername ==
GPSR ist ein [[Geo-Routing]]-Verfahren, d. h. Datenpakete werden nicht an spezielle Empfänger, sondern an Koordinaten verschickt; die Pakete sollen dann demjenigen Netzwerkknoten zugestellt werden, der diesen Koordinaten geographisch am nächsten ist. Voraussetzung dafür ist natürlich, dass jeder Netzwerkknoten seine eigene Position in Koordinaten kennt.

== Nachbarschaft ==
Im Folgenden wird der Begriff der „Nachbarschaft“ verwendet. Zunächst sind zwei Knoten benachbart, wenn mindestens einer der beiden den anderen über das Kommunikationsmedium direkt erreichen kann. In einem Ad-hoc-Netzwerk sind diese Nachbarschaftsbeziehungen nicht offensichtlich, denn durch die Verwendung von Kommunikationsmedien mit begrenzter Reichweite – z. B. [[Funktechnik|Funk]] – kann meist ''nicht'' jeder Knoten jeden anderen direkt kontaktieren. Später kann es notwendig sein, dass einige Knoten einige ihrer Nachbarn „aus dem Gedächtnis streichen“, siehe Abschnitt [[#Planare Graphen sind Voraussetzung|Planare Graphen sind Voraussetzung]].

== Das Protokoll ==
Jeder Knoten des Netzwerkes führt die folgenden Schritte aus, wenn er ein Datenpaket erhält:
# Endbedingung. Steht dein Name im Paket-[[Header]], so bist du der Knoten, der dem Ziel am nächsten ist. Verarbeite das Paket und schicke es ''nicht'' weiter. Ansonsten weiter mit 2.
# '''Greedy-Modus.''' Wähle denjenigen deiner Nachbarn aus, der den Zielkoordinaten des Pakets am nächsten ist. Ist dieser Nachbar näher am Ziel als du, dann schicke ihm das Paket. Ansonsten weiter mit 3.
# '''Perimeter-Modus'''. Schreibe deinen Namen in den Paket-Header. Schau in Richtung Zielpunkt und drehe dich so lange entgegen dem [[Uhrzeigersinn]], bis du den ersten deiner Nachbarn siehst. Schicke diesem das Paket.
Das Verfahren ist hier sehr ''menschlich'' erklärt. Die tatsächliche Umsetzung des letzten Schrittes bestimmt den [[Winkel]] zwischen dem [[Vektor]] „aktueller Knoten – Zielpunkt“ und allen Vektoren „aktueller Knoten – Nachbarknoten“ und schickt das Paket an denjenigen Nachbarn weiter, zu dem der kleinste Abweichungswinkel berechnet wurde. Die Drehrichtung ''entgegen'' dem Uhrzeigersinn ist natürlich willkürlich gewählt, weil es die in der [[Mathematik]] übliche Drehrichtung ist; genauso gut könnte ''im'' Uhrzeigersinn gedreht werden – einzige Bedingung ist, dass ''alle'' Knoten die gleiche Drehrichtung verwenden.

== Planare Graphen sind Voraussetzung ==
Voraussetzung für die korrekte Funktionsweise des Protokolls ist, dass das Netzwerk als [[planarer Graph]] darstellbar ist: Zeichnet man alle Knoten in ein Koordinatennetz ein und verbindet alle ''benachbarten'' Knoten, so dürfen sich diese Verbindungslinien nirgends kreuzen. Tun sie es doch, so muss das Netzwerk „geebnet“ werden, bevor das GPSR-Protokoll korrekt funktionieren kann – dazu müssen einige Knoten einige ihrer Nachbarn „vergessen“. Wie ein solcher Algorithmus zur ''Planarisierung'' aussieht, wird im Artikel [[Planarer Graph]] eingehender behandelt.

Wird das GPSR-Protokoll in einem ''nicht-planaren'' Netzwerk verwendet, so können ''Zyklen'' auftreten, d. h. ein Datenpaket wird immer wieder im Kreis herum geschickt, ohne jemals sein Ziel zu erreichen. Das ist natürlich unerwünscht, denn Pakete in einem Zyklus sind verloren und das Netzwerk wird unnötig beansprucht.

== Literatur ==
* B.Karp: Challenges in Geographic Routing: Sparse Networks, Obstacles, and Traffic Provisioning. In DIMACS Workshop on Pervasive Networking, Piscataway, NJ, May, 2001
* B.Karp: Geographic Routing for Wireless Networks. Ph.D. Dissertation, Harvard University, Cambridge, MA, October, 2000
* B.Karp, H.T.Kung: Greedy Perimeter Stateless Routing for Wireless Networks. In Proceedings of the Sixth Annual ACM/IEEE International Conference on Mobile Computing and Networking (MobiCom 2000), Boston, MA, August, 2000, pp. 243–254

[[Kategorie:Routingprotokoll]]

Greedy Perimeter Stateless Routing in Wireless Networks - Versionsgeschichte

imported>Unermüdlich: unnötig