Joint UAV Flight and Opportunistic Routing under Reinforcement Learning for Delay-Tolerant Networks

Stellen Sie sich eine Welt vor, in der es das Internet nicht gibt, oder zumindest nicht die Art von Internet, die Ihr Telefon jede Sekunde mit einem Server verbindet. An Orten wie Katastrophengebieten, abgelegenen Wäldern oder sogar belebten Städten mit gestörten Signalen können Nachrichten nicht einfach sofort vom Sender zum Empfänger „fliegen“. Stattdessen müssen sie ein Spiel wie „heiße Kartoffel“ spielen. Dies ist die Welt der Delay-Tolerant Networks (DTNs). Denken Sie an es wie an ein Fangenspiel, bei dem die Spieler fahrende Autos und Drohnen sind. Eine Nachricht ist das „Es“-Etikett. Wenn man das Etikett fängt, hält man es fest, bis man jemanden trifft, der es weiter tragen kann. Man speichert es, trägt es und leitet es erst weiter, wenn man jemandem nahe genug kommt. Dies wird „Store-Carry-Forward“ (Speichern, Tragen, Weiterleiten) genannt.

Der schwierige Teil ist, dass diese Netzwerke oft dünn besiedelt und chaotisch sind. Die „Spieler“ (Autos und Menschen) bewegen sich auf festen Straßen, und das „Etikett“ (die Nachricht) hat ein Zeitlimit, bevor es abläuft. Wenn sich die Spieler nicht oft genug treffen oder wenn sie zu voll werden und keine Taschen mehr haben, um die Etiketten zu halten, geht die Nachricht verloren. Um dies zu beheben, haben Wissenschaftler begonnen, Unmanned Aerial Vehicles (UAVs), oder Drohnen, als fliegende Boten einzusetzen. Drohnen können über den Verkehr fliegen, weiter reichen und genau auswählen, wohin sie gehen sollen. Aber hier ist die große Frage: Wie sagt man den Drohnen, wohin sie fliegen sollen, und sagt gleichzeitig den Autos am Boden, wann sie eine Nachricht übergeben sollen, ohne dass ein zentraler Chef alles steuert? Wenn die Drohnen in die falsche Richtung fliegen, treffen sich die Autos vielleicht nie. Wenn die Autos Nachrichten an die falschen Leute weitergeben, fliegen die Drohnen vielleicht zu leeren Stellen.

Dies ist genau das Rätsel, das die Forscher Xiao Wang und Shun-Ren Yang in ihrer Arbeit über JUROR (Joint UAV flight and Opportunistic Routing) lösen wollen. Sie haben nicht einfach nur geraten; sie haben ein intelligentes System unter Verwendung einer Art künstlicher Intelligenz namens Reinforcement Learning (Bestärkendes Lernen) aufgebaut. Stellen Sie sich ein Team aus Drohnen und Autos vor, die gemeinsam ein Videospiel spielen. Sie haben keinen Plan für die Zukunft, aber sie lernen durch Ausprobieren. Wenn sie eine Nachricht erfolgreich übergeben, bekommen sie einen „Punkt“. Wenn eine Nachricht abläuft oder eine Drohne mit einer Gruppe anderer Drohnen kollidiert, verlieren sie Punkte. Die Arbeit simuliert dieses Szenario tausende Male, um die Drohnen und Autos zu lehren, wie sie kooperieren können.

Die wichtigste Erkenntnis ist, dass die Nachrichtenlieferung massiv ansteigt, wenn die Drohnen und Autos lernen, als ein einziges Team zusammenzuarbeiten, anstatt nur festen Regeln zu folgen. Die Forscher entdeckten, dass die Drohnen „steuerbar“ sein müssen – das heißt, das System entscheidet, wohin sie fliegen, basierend darauf, wo der Verkehr gestaut ist. Sie fanden auch heraus, dass die Drohnen zwar während des Lernens im Simulator einen „Referenzleitfaden“ (globale Informationen) nutzen können, sie aber in der echten Welt eigenständige Entscheidungen treffen müssen, indem sie nur das nutzen, was sie lokal sehen können. Dieser Ansatz, der Centralized Training and Decentralized Execution (CTDE) (Zentralisiertes Training und dezentrale Ausführung) genannt wird, erwies sich als das Geheimrezept.

In ihren Simulationen übertraf das JUROR-System ältere, traditionelle Methoden deutlich. In einem Testszenario, in dem 69 Nachrichten versendet wurden, schafften die alten Methoden etwa die Hälfte der Zustellungen, während das JUROR-System über 57 Nachrichten lieferte (etwa 83 %). Die Arbeit legt nahe, dass es nicht ausreicht, einfach nur Drohnen hinzuzufügen; die Drohnen müssen aktiv gesteuert werden, um neue Treffpunkte für die Bodenfahrzeuge zu schaffen, und die Fahrzeuge müssen entscheiden, wann sie Nachrichten übergeben, basierend darauf, was die Drohnen tun. Es ist ein feiner Tanz, bei dem die Flieger und die Läufer synchron agieren müssen, um den Informationsfluss aufrechtzuerhalten, selbst wenn das Netzwerk unterbrochen oder dünn besiedelt ist.

Die Geschichte der fliegenden Boten

Wie funktioniert JUROR also eigentlich? Stellen Sie sich eine belebte Stadtstraße vor. Sie haben eine Menge Autos (die Bodenknoten), die im Stau stehen, und ein paar Drohnen (die UAVs), die darüber summen. Die Autos haben Nachrichten, die sie an bestimmte Ziele bringen müssen, aber sie können nur mit anderen Autos oder Drohnen kommunizieren, wenn sie in der Nähe sind. Wenn die Autos in einem Stau feststecken, können sie niemanden anderen erreichen. Wenn die Drohnen einfach in zufälligen Kreisen fliegen, übersehen sie den Stau vielleicht komplett.

Die Forscher erkannten, dass das Problem eine „Henne-Ei-Situation“ ist. Die Autos brauchen die Drohnen, damit diese zu ihnen fliegen, um Nachrichten zu verbreiten, aber die Drohnen müssen wissen, wo die Autos dicht gedrängt stehen, um zu wissen, wohin sie fliegen sollen. Um dies zu lösen, behandelt JUROR das gesamte Netzwerk wie ein Team von Teamkollegen. Jedes Auto und jede Drohne ist ein „Agent“ mit eigenem Gehirn.

Der Lernprozess: Versuch und Irrtum
Das System verwendet eine Methode namens Proximal Policy Optimization (PPO). Stellen Sie sich vor, Sie bringen einem Welpen das Apportieren bei. Sie sagen dem Welpen nicht genau, wie er laufen soll; Sie werfen nur den Ball und sagen „Braver Hund!“, wenn er ihn zurückbringt. Mit der Zeit lernt der Welpe, welche Bewegungen zu einer Belohnung führen. JUR-OR macht dasselbe, aber mit Mathematik.

1. Die Simulation: Die Forscher schufen eine virtuelle Welt (einen Simulator) mit 70 Knoten: 65 Autos und 5 Drohnen. Sie legen verschiedene Verkehrsszenarien fest, wie einen plötzlichen Nachrichtenansturm oder einen stetigen Verkehrsfluss.
2. Die Team-Belohnung: Anstatt nur eine einzelne Drohne oder ein einzelnes Auto zu belohnen, vergibt das System einen „Team-Score“. Wenn eine Nachricht zugestellt wird, bekommt jeder einen Punkt. Wenn eine Nachricht abläuft (die Zeit vergeht) oder ein Puffer (Speicher) voll wird und eine Nachricht verwirft, verlieren alle Punkte. Dies zwingt die Drohnen und Autos zur Kooperation. Wenn eine Drohne an einen Ort fliegt, an dem keine Autos sind, hilft das dem Team-Score nicht. Wenn ein Auto eine Nachricht zu lange hält, verliert das Team Punkte.
3. Der „Referenzleitfaden“ vs. das echte Leben: Hier liegt der clevere Teil. Wenn das System trainiert (lernt), kann der „Lehrer“ (der Kritiker) das gesamte Spielfeld sehen. Er weiß genau, wo sich jedes Auto und jede Drohne befindet, wie viel Speicher sie haben und wo die Staus sind. Er nutzt diese „globale Sicht“, um den Agenten zu sagen: „Hey, das war ein guter Zug!“ oder „Das war ein schlechter Zug!“. Aber wenn das System eingesetzt wird (in der realen Welt arbeitet), können die Drohnen und Autos nur das sehen, was direkt vor ihnen liegt. Sie können nicht die ganze Stadt sehen. Sie wissen nur, wen sie gerade berühren oder mit wem sie gerade kommunizieren. Die Arbeit zeigt, dass die Agenten selbst mit dieser begrenzten Sicht immer noch unglaublich gut abschneiden können, weil sie mit Hilfe des „Referenzleitfadens“ trainiert wurden.

Der neue Job der Drohnen
In älteren Systemen flogen Drohnen vielleicht nach einem vorgegebenen Muster, wie ein Rasenmäher, der hin und her fährt. Aber JUROR lehrt die Drohnen, intelligent zu sein. Sie schauen auf „Stressfelder“. Stellen Sie sich vor, die Stadt hat unsichtbare Heatmaps, die zeigen, wo sich Nachrichten anhäufen. Wenn eine Gruppe von Autos in einem Bereich mit vielen Nachrichten feststeckt, leuchtet dieser Bereich rot auf. Die Drohnen lernen, in die roten Zonen zu fliegen, um Nachrichten aufzunehmen und wegzutragen.

Die Arbeit testete auch, ob die Drohnen versuchen sollten, vorherzusagen, wo der Verkehr in der Zukunft sein wird (unter Verwendung eines Werkzeugs namens LSTM, das wie ein Kurzzeitgedächtnis für Muster funktioniert). Sie fanden heraus, dass dies zwar in einigen Situationen helfen kann, aber nicht immer notwendig ist. Manchmal reicht es schon, auf den aktuellen Verkehrsstau zu reagieren. Tatsächlich war das System in einigen Szenarien mit schwerem Verkehr sogar etwas schlechter, wenn es versuchte, die Zukunft vorherzusagen, weil die Vorhersagen verrauscht waren und die Drohnen verwirrten.

Was sie herausfanden
Die Ergebnisse waren eindeutig. In den Simulationen war JUROR ein Game-Changer.

• Ohne Drohnen: Wenn man nur Autos hat und keine steuerbaren Drohnen, hat das System Schwierigkeiten. In einem Test wurden nur etwa 13 von 69 Nachrichten zugestellt.
• Mit Drohnen (Lernen): Das Hinzufügen nur einer einzigen steuerbaren Drohne machte einen riesigen Unterschied und lieferte über 45 Nachrichten. Als die Drohnen und Autos als volles Team zusammen lernten, schoss die Zustellrate auf über 57 Nachrichten hoch.
• Vergleich zu alten Methoden: JUROR lieferte in den meisten Szenarien, insbesondere bei schwerem Verkehr, signifikant mehr Nachrichten als die alten Methoden. Die Arbeit stellt jedoch fest, dass in Szenarien mit regulärer, vorhersehbarer Bewegung einige traditionelle Methoden wie PRoPHET immer noch recht gut funktionierten, was zeigt, dass der Vorteil von JUROR vor allem in komplexen, überlasteten oder chaotischen Umgebungen zum Tragen kommt.

Die Arbeit schloss auch einige Ideen aus. Sie fanden heraus, dass man die Drohnen nicht einfach als separates Element von den Autos betrachten kann. Man muss sie gemeinsam optimieren. Wenn man versucht, den Flugpfad der Drohne separat vom Nachrichten-Routing zu optimieren, erreicht das System sein volles Potenzial nicht. Sie fanden auch heraus, dass „Hotspot-Vorhersagen“ (das Erraten, wo der Verkehr sein wird) zwar cool klingen, aber kein Allheilmittel sind. Es hängt stark von der Art des Verkehrs ab. Manchmal hilft es, manchmal schadet es. Das zuverlässigste Setup war dasjenige, bei dem die Drohnen und Autos einfach auf die aktuelle Situation reagierten, trainiert mit Hilfe eines globalen Lehrers.

Warum es wichtig ist
Hier geht es nicht nur darum, E-Mails schneller zu versenden. Es geht darum, was passiert, wenn das Internet ausfällt. Denken Sie an eine Naturkatastrophe, bei der Mobilfunkmasten ausgefallen sind. Sie müssen eine Nachricht von einem Überlebenden zu einem Rettungsteam bringen. Der Überlebende befindet sich vielleicht in einem Auto, und das Rettungsteam befindet sich in einer Drohne. Wenn die Drohne nicht weiß, wohin sie fliegen soll, oder wenn das Auto nicht weiß, wann es die Nachricht übergeben soll, geht die Nachricht verloren. JUROR zeigt einen Weg auf, diese Netzwerke robust zu machen. Es beweist, dass wir, indem wir die fliegenden und die bodengebundenen Teile des Netzwerks lernen lassen, gemeinsam zu tanzen, die Kommunikationslinien offen halten können, selbst wenn die Welt in Chaos versinkt.

Die Forscher haben nicht nur eine Theorie aufgestellt; sie haben die Zahlen geprüft. Sie haben es gegen fünf andere berühmte Methoden (wie PRoPHET und MaxProp) getestet, und JUROR gewann im Allgemeinen, besonders wenn der Verkehr schwer wurde. Die Arbeit kommt zu dem Schluss, dass dieser „gemeinsame“ Ansatz – bei dem der Flugpfad und der Nachrichtenpfad zusammen entschieden werden – der Schlüssel ist, um das volle Potenzial von Delay-Tolerant Networks auszuschöpfen. Es ist eine Erinnerung daran, dass in einer chaotischen Welt der beste Weg, verbunden zu bleiben, darin besteht, als Team zu arbeiten, egal ob man am Boden oder am Himmel ist.