Greedy Sparse Approaches for Homological Coverage in Location Unaware Sensor Networks
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 08, 2017
- Accession Number
- AD1042918
Entities
People
- Terrence J. Moore
Organizations
- United States Army Research Laboratory