Reactive Construction of and Reactive Routing in Euclidean and Topological Network Spanners over Wireless Ad-Hoc and Sensor Networks
Security and Dependability, Operating-, Communication- and Distributed Systems
Final Report Abstract
The project covered modeling and algorithmic questions on wireless networked systems. The assumption is that nodes in the network have a position and that they know about their position. Based on this additional information, the algorithms construct a subgraph on the plane from a given graph such that the subgraph does not contain any intersecting edges. Such planar graph constructions are an essential building block for a number of local algorithms from areas such as data communication, tracking in sensor networks, address autoconfiguration, coordination of autonomous mobile robots or distributed geographic hashing of data. It is of particular interest that the planarization itself is correct under the given conditions of the initial graph, detours of paths in these subgraphs are not too large compared to the original one, and that it can also be implemented locally and with as little message overhead as possible. The project results are summarized as follows. As one result, a formal description of so-called reactive methods was introduced as part of the project. The concept means in general to construct the local view of nodes on a planar subgraph only when required with the least possible number of messages. Furthermore, as an extension to the unit disk graph, models were described and investigated that describe wireless networked systems more realistically. On the one hand, this includes the formal and empirical investigation and further development of the concepts of redundancy and coexistence. On the other hand, towards the end of the project, stochastic investigations into the structural graph properties of wireless networked systems were carried out under realistic physical layer models. Finally, results were obtained for the models with regard to cyclic dependencies, which can possibly impair the local ability of structure of graphs. On the algorithmic level, variants of local unicast and multicast communication based on planar drawings were considered, and planar graph constructs were considered from different aspects. This includes reactive constructions as well as k-degree constrained spanners under quasi-unit disk graphs. Furthermore, algorithms for planarization were described for the concepts of redundancy and coexistence properties and modifications thereof and their correctness in terms of non-intersecting edges and connectivity was shown. In addition, it was stochastically examined to what extent algorithms can be executed with a high success rate under real physical layer assumptions. Here, the focus was on determining the frequency of properties under which correct execution is possible, and investigating the extent to which structures that behave similarly to the unit disk graph can be obtained through preprocessing of the network graph, however, preprocessing in such a way that connectivity, or percolation in case of very large graphs, may not be impaired.
Publications
- Foundation of Reactive Local Topology Control. IEEE Communication Letters 19(7), 2015
Florentin Neumann, Hannes Frey
(See online at https://doi.org/10.1109/LCOMM.2015.2432019) - 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
(See online at https://doi.org/10.1007/978-3-319-40509-4_16) - 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
(See online at https://doi.org/10.1007/978-3-030-34405-4_4) - 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
(See online at https://doi.org/10.1145/3345768.3355933) - 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
(See online at https://doi.org/10.1016/j.procs.2021.11.016)
