Accession Number:



Greedy Sparse Approaches for Homological Coverage in Location Unaware Sensor Networks

Descriptive Note:

Technical Report,15 Jan 2017,15 Aug 2017

Corporate Author:

US Army Research Laboratory Adelphi United States

Personal Author(s):

Report Date:


Pagination or Media Count:



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.

Subject Categories:

  • Miscellaneous Detection and Detectors

Distribution Statement: