Reactive Construction of and Reactive Routing in Euclidean and Topological Network Spanners over Wireless Ad-Hoc and Sensor Networks

• Applicant: Professor Dr. Hannes Frey
• Subject Area: Theoretical Computer Science ; Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2011 to 2022
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 191449530

Research topic of this project is the development of extremely message efficient, local algorithms for constructing connected, intersection free topologies in wireless network graphs. By means of such topologies, problems like localized routing, distributed data storage, or traversals and identification of network boundaries and void regions, can be solved immediately using well-known local algorithms. However, the discovered intersection free topologies may stretch the pairwise shortest path distances between nodes in the underlying network graph and thus, impair the quality of the local solutions over such topologies. To address this problem, the preferred subjects of study in this project are Euclidean and topological spanners. In such spanners the shortest path between two arbitrary nodes, quantified in Euclidean path length or number of forwarding steps, deviates only by a constant factor from the shortest path in the initial topology. In this project, we are investigating techniques for construction of a node's local view on the topology, such that, in general, after starting with a request message to all neighbors, only a subset of the neighborhood has to answer. This enables construction of topologies using fewer messages compared to conventional local techniques, which require the starting node to exchange messages with every neighbor in the first place. To research and to compare the aforementioned and so called reactive topology construction techniques, we introduce a formal concept which uniquely classifies these techniques with respect to their message overhead and furthermore, provides formal criteria to distinguish between reactive and non-reactive techniques. Soundness theorems on reactive topology control techniques regarding connectivity, planarity, and spanning property have only been proven under the oversimplifying assumptions of the unit disk and quasi unit disk models. When dropping these assumptions, correctness of known techniques is not guaranteed. In this project we research how far, under close to reality, generalized model assumptions, formal correct, graph theoretical and algorithmic statements are still possible. It is planned to research and develop algorithms which, under generalized model assumptions, still work correctly and in the ideal case, are either immediately or with marginal adjustments applicable to real wireless networks.

• DFG Programme: Research Grants