Greedy Perimeter Stateless Routing in Wireless NetworksGreedy 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ängernameGPSR 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. NachbarschaftIm 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 ProtokollJeder Knoten des Netzwerkes führt die folgenden Schritte aus, wenn er ein Datenpaket erhält:
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 VoraussetzungVoraussetzung 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
|
