Greedy Sparse Approaches for Homological Coverage in Location-Unaware Sensor Networks

Report No. ARL-TR-8235
Authors: Terrence J Moore
Date/Pages: December 2017; 42 pages
Abstract: Solving certain sensor network coverage problems in a location-unaware environment has become feasible using algebraic topology techniques. The coverage of the network can be modeled using a simplicial complex, where simplices correspond to cliques in the communication graph. Homological methods can determine various properties of the coverage. One particular problem of interest is the sparse coverage problem (i.e., how many nodes are needed to maintain certain coverage quality). This can be translated to finding homology-preserving reduction algorithms. This report details 3 such distributive approaches based on greedy node removals. The first is a simple calculation of the potential change in homology locally. The second approach is based on strong collapsing, which has previously been applied in the hole localization problem. The last approach recognizes the connection between homology and the Euler characteristic, and calculates the potential change in the characteristic locally. Simulations are provided to validate each approach.
Distribution: Approved for public release
  Download Report ( 0.762 MBytes )
If you are visually impaired or need a physical copy of this report, please visit and contact DTIC.

Last Update / Reviewed: December 1, 2017