Lossy Compression of Spatial Network Topologies and Structures
Abstract
It is a fundamental task of many networks to deduce, store, and communicate the network structure to coordinating devices, both during the establishment of the network and periodically as the network state evolves. In particular, the availability of network topology and performance information is crucial for the operation of large wireless systems comprising low-power devices that are required to provide low-latency, high-reliability services, as can be observed in some sensing and tactical contexts. Many network characteristics can be inferred by observing end-to-end data, which often takes the form of packet probes. The general field of study concentrating on such techniques is known as network tomography. Over the past twenty years, the field of network tomography has been developed to include the inference of link loss statistics (loss tomography), internal queuing delays (delay tomography), and structural characteristics (topology tomography). To date, however, little effort has been devoted to investigating efficient ways to store and communicate structural spatial network data once it has been estimated. In other words, the task of determining optimal compressors for spatial graphs is an open problem. Most of the research on graph compression can be traced to contributions in the fields of network science and computer science, and many of these results derive from heuristic methods. There are notable exceptions, of course, which cast the graph compression problem in a more rigorous information-theoretic framework. Yet, most of those studies do not treat spatial graphs. The investigator of this project has, on the other hand, developed a number of results for lossless spatial graph compression. For such cases, there is a non-zero probability that structural network data cannot be compressed (i.e., there is a possibility that all networks are typical). Yet, practical reasons may exist for reducing the volume of traffic on a network in some contexts, and thus it is natural to consider the possibility of compressing structural and topological network data in a lossy manner. A few works on lossy graph compression exist; however, they are, again, largely heuristic in nature and do not deal with spatial networks. The proposed project is positioned to develop the field of lossy spatial graph compression in a systematic manner. To this end, the proposal is built upon the hypothesis that the problem of efficient lossy compression of spatial (wireless) network topologies and structures (i.e., graph automorphisms) can be cast in the classical framework of rate-distortion theory. The main project aims are threefold: 1. To develop a theory of lossy compression, rooted in rate-distortion theory, for spatial networks; 2. To develop methods that yield optimal lossy spatial graph compression subject to commonly chosen distortion constraints; 3. To devise lossy compression techniques for efficiently representing dynamic features of spatial networks.
Document Details
- Document Type
- DoD Grant Award
- Publication Date
- Jun 30, 2022
- Source ID
- W911NF2210070
Entities
People
- Justin Coon
Organizations
- Army Contracting Command
- United States Army
- University of Oxford