TOPOLOGICAL STRUCTURE OF SPATIALLY-DISTRIBUTED NETWORK CODED INFORMATION

Abstract

In this paper we generalize work using topological methods for testing wireless/sensor network coverage to the problem of covering a geographically-distributed wireless network with linear network coded data. We define the coverage complex, a new type of simplicial complex built on the nodes of the network which captures properties of the data coverage, and use tools from algebraic topology, persistent homology, and matroid theory to study it. The coverage complex shares properties with the Rips complex, however it also suffers from a more diverse variety of potential failures. We extend the standard coverage criteria to account for some of these situations using persistent homology, multi-sheeted localized covers of the space, and Mayer-Vietoris sequences. We also investigate the combinatorial properties of the coverage complex, determining the correspondence between it and the lattice of linear subspaces of a vector space. Finally we present algorithms for computing coverage complexes, present a software package designed to compute and experiment with coverage complexes, and provide a summary of ongoing and future work.