Reaktive Konstruktion von und reaktives Routing in Euklidischen und Topologischen Netzspannern über drahtlosen Ad-hoc- und Sensornetzen
Sicherheit und Verlässlichkeit, Betriebs-, Kommunikations- und verteilte Systeme
Zusammenfassung der Projektergebnisse
Das Projekt befasste sich mit Modellierungs- und algorithmischen Fragen zu drahtlos vernetzen Systemen. Hierbei ist angenommen, dass Knoten des Netzes eine Position haben und diese den Knoten bekannt ist. Die Aufgabe ist, auf Basis dieser Zusatzinformation aus einem gegebenen Graphen, einen Teilgraphen auf der Ebene zu konstruieren, der keine schneidenden Kanten enthält. Solche planaren Graphkonstruktionen sind ein wesentlicher Baustein für eine Reihe an lokalen Algorithmen aus Bereichen wie Datenkommunikation, Tracking in Sensornetzen, Adressautokonfiguration, Koordination von autonomen mobilen Robotern oder verteiltes geographisches Hashing von Daten. Hierbei ist insbesondere von Interesse, dass die Planarisierung selber unter gegebenen Voraussetzungen der Ausgangsgraphen korrekt ist, als Teilgraph möglichst keine zu großen Umwege erzeugt und zudem ebenfalls lokal und mit möglichst wenig Nachrichtenaufwand realisierbar ist. Die Projektergebnisse sind zusammengefasst wie folgt. Als ein Projektergebnis wurde die formale Beschreibung sogenannter reaktiver Verfahren eingeführt, also solche Verfahren, die nur bei Bedarf mit möglichst geringem Nachrichtenaufwand die lokale Sicht von Knoten auf einen planaren Teilgraphen konstruieren. Des Weiteren wurden als Erweiterung zum Unit-Disk-Graphen Modelle beschrieben und untersucht, die realitätsnäher drahtlos vernetzte Systeme beschreiben. Dies beinhaltet zum einen die formale und empirische Untersuchung sowie Weiterentwicklung der Konzepte Redundanz- und Koexistenzeigenschaft. Zum anderen wurden gegen Ende des Projektes stochastische Untersuchungen zur Graphstruktureigenschaft von drahtlos vernetzten Systemen unter realitätsnahen Modellen der physikalischen Schicht durchgeführt. Letztlich wurden zu den Modellen Ergebnisse hinsichtlich zyklischer Abhängigkeiten, die die lokale Strukturierbarkeit von Graphen möglicherweise beinträchtigen können, erzielt. Auf der algorithmischen Ebene wurden Varianten der lokalen Unicast- und Multicast-Kommunikation auf Basis planarer Zeichnungen betrachtet, sowie planare Graphkonstrukte unter verschiedenen Aspekten betrachtet. Dies beinhaltet reaktive Konstruktionen sowie k-Grad beschränkte Spanner unter Quasi-Unit-Disk-Graphen. Des Weiteren wurden für die Konzepte Redundanz- und Koexistenzeigenschaft sowie Abwandlungen davon Algorithmen zur Planarisierung beschrieben und deren Korrektheit im Sinne nicht schneidender Kanten sowie Zusammenhang gezeigt. Darüber hinaus wurde stochastisch untersucht, inwieweit Algorithmen unter realen Annahmen zur physikalischen Schicht mit hoher Erfolgsrate ausführbar sind. Hier lag der Schwerpunkt auf dem Nachweis der Häufigkeit von Eigenschaften, unter denen eine korrekte Ausführung möglich ist, sowie die Untersuchung inwieweit durch Vorverarbeitung des Netzgraphen Strukturen erreicht werden können, die sich ähnlich dem Unit-Disk-Graphen verhalten, ohne dabei jedoch Graphzusammenhang beziehungsweise Perkolation im Falle sehr großer Graphen zu verlieren.
Projektbezogene Publikationen (Auswahl)
-
Foundation of Reactive Local Topology Control. IEEE Communication Letters 19(7), 2015
Florentin Neumann, Hannes Frey
-
Structural Network Properties for Local Planarization of Wireless Sensor Networks. Proceedings of the International Conference on Ad Hoc Networks and Wireless (ADHOC‐NOW), 2016
Florentin Neumann, Daniel Vivas Estevao, Frank Ockenfeld, Jovan Radak, Hannes Frey
-
Existence of Connected Intersection‐Free Subgraphs in Graphs with Redundancy and Coexistence Property. Proceedings of the International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), 2019
Lucas Böltz, Hannes Frey
-
Stochastic Modeling and Simulation for Redundancy and Coexistence in Graphs Resulting from Log‐Normal Shadowing. Proceedings of the International ACM Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM), 2019
Steffen Böhmer, Daniel Schneider, Hannes Frey
-
Local Construction of Connected and Plane Spanning Subgraphs under Acyclic Redundancy. Proceedings of the International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks (WiOPT), 2020
Steffen Böhmer, Lucas Böltz, Hannes Frey
-
Local Construction of Connected Plane Subgraphs in Graphs Satisfying Redundancy and Coexistence. Proceedings of the Latin and American Algorithms, Graphs and Optimization Symposium (LAGOS), 2021
Lucas Böltz, Benjamin Becker, Hannes Frey
