Greedy Perimeter Stateless Routing in Wireless Networks


Greedy Perimeter Stateless Routing in Wireless Networks

Greedy Perimeter Stateless Routing in Wireless Networks (engl. „Greedy-Perimeter-Wegewahl in Funknetzen“, Abkürzung GPSR) ist ein Routing-Protokoll für mobile Ad-hoc-Netze, also ein Verfahren, mit dem Datenpakete in spontan aufgebauten Rechnernetzen 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.

Inhaltsverzeichnis

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. 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.

Das Protokoll

Jeder Knoten des Netzwerkes führt die folgenden Schritte aus, wenn er ein Datenpaket erhält:

  1. 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.
  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.
  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ötigt 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

Wikimedia Foundation.

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Greedy — steht für Greedy Algorithmus, spezielle Klasse von Algorithmen in der Informatik Greedy (Film), US amerikanische Filmkomödie von Jonathan Lynn aus dem Jahr 1994 Greedy Perimeter Stateless Routing in Wireless Networks (GPSR), Routing Protokoll für …   Deutsch Wikipedia

  • List of ad-hoc routing protocols — An Ad hoc routing protocol is a convention or standard that controls how nodes come to agree which way to route packets between computing devices in a mobile ad hoc network (MANET).In ad hoc networks , nodes do not have a priori knowledge of… …   Wikipedia

  • Drahtlose Sensornetzwerke — Ein Sensornetz (von engl. wireless sensor network) ist ein Rechnernetz von Sensorknoten, winzigen („Staubkorn“) bis relativ gross („Schuhkarton“) per Funk kommunizierenden Computern, die entweder in einem infrastruktur basierten (Basisstationen)… …   Deutsch Wikipedia

  • Drahtloses Sensornetzwerk — Ein Sensornetz (von engl. wireless sensor network) ist ein Rechnernetz von Sensorknoten, winzigen („Staubkorn“) bis relativ gross („Schuhkarton“) per Funk kommunizierenden Computern, die entweder in einem infrastruktur basierten (Basisstationen)… …   Deutsch Wikipedia

  • Sensornetzwerk — Ein Sensornetz (von engl. wireless sensor network) ist ein Rechnernetz von Sensorknoten, winzigen („Staubkorn“) bis relativ gross („Schuhkarton“) per Funk kommunizierenden Computern, die entweder in einem infrastruktur basierten (Basisstationen)… …   Deutsch Wikipedia

  • WSN — Ein Sensornetz (von engl. wireless sensor network) ist ein Rechnernetz von Sensorknoten, winzigen („Staubkorn“) bis relativ gross („Schuhkarton“) per Funk kommunizierenden Computern, die entweder in einem infrastruktur basierten (Basisstationen)… …   Deutsch Wikipedia

  • Sensornetz — Ein Sensornetz (von engl. wireless sensor network) ist ein Rechnernetz von Sensorknoten, winzigen („Staubkorn“) bis relativ groß („Schuhkarton“) per Funk kommunizierenden Computern, die entweder in einem infrastruktur basierten (Basisstationen)… …   Deutsch Wikipedia

  • GPSR — Cette page d’homonymie répertorie les différents sujets et articles partageant un même nom.   Sigles d’une seule lettre   Sigles de deux lettres   Sigles de trois lettres > Sigles de quatre lettres …   Wikipédia en Français