Topology Discovery in Wireless Networks via Spatial Graph Entropy
Abstract
Uncertainty is pervasive in modern wireless networks. The sources of this uncertainty range from the humans that interact with the networks and the geographic locations of the nodes down to the transmission protocols and the underlying scattering processes that affect signal propagation. Conventionally, knowledge of these characteristics has been used to construct a model of a wireless system, which can be optimized to achieve a stated objective, such as scheduling traffic or attaining a specified rate of communication at a prescribed error rate. These goals are almost always localized in their outlook. Fundamental questions regarding the global implications of uncertainty on network structure -- for example, topology, degree distribution, and complexity -- have only recently been asked in the context of spatial networks. Yet, the sheer complexity of many modern networks, including wireless sensor networks and multi-tier tactical wireless networks, points to the need to better understand how local uncertainty affects global network performance. To make progress towards this goal, it is desirable to invoke the notion of graph entropy to quantify the uncertainty, complexity, and latent information content inherent in a networkÕs topology. This approach has recently been taken in the physics and complex networks communities, and striking insights into system behavior have been uncovered. Crucially, research on the subject of graph entropy (with application to physical systems) has thus far focused on non-spatial networks, i.e., networks where connectivity does not depend on the spatial embedding. Clearly, wireless communication networks are spatial in nature, since connectivity between devices depends on the distance between them. In an effort to adapt the theory of graph entropy for use in analyzing the structure of wireless communication networks, we recently incorporating elements of stochastic geometry into the graph entropy formalism to create the new framework of spatial graph entropy. These new tools have allowed us to conduct a more formal analysis of the scaling properties of wireless ad hoc network entropy and to propose methods of controlling system complexity in large networks. This proposal is built upon the hypothesis that knowledge of the structural uncertainly of a wireless network -- quantified appropriately using the framework of spatial graph entropy -- can be used to improve topology discovery (TD) in practical systems. Conventionally, TD is performed in practice to construct forwarding tables that are employed at the network layer for routing and scheduling. Hence, this task is of fundamental importance to wireless networks, and can be particularly challenging in dynamic networks, such as ad hoc and mobile tactical networks. The main aim of the project is to develop the theoretical foundations of spatial graph entropy for directed networks, and then to apply these new tools to benchmark leading -D algorithms in terms of overhead and topology acquisition time before developing new methods of performing TD that exploit knowledge of network entropy.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Feb 14, 2019
- Source ID
- W911NF1910048
Entities
People
- Justin Coon
Organizations
- Army Contracting Command
- United States Army
- University of Oxford