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.

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:

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