Distributed computation of coverage in sensor networks by homological methods
type: Item
instance of: scholarly article
title: Distributed computation of coverage in sensor networks by homological methods
zbMATH Open document ID: 1300.55001
published in: Applicable Algebra in Engineering, Communication and Computing
publication date: 2012-10-11T00:00:00Z
review text: The article is devoted to presenting a distributed homology computation algorithm working over a sensor network with the purpose of coverage verification. The authors' results may be summarized in the following statements from the introduction: 1. We provide a provably correct algorithm for distributed computation of homological coverage criteria. 2. The algorithm can recover specific generators, for use in building minimal or power-reducing covers. 3. Most crucially, the algorithm computes homology in an arbitrary coefficient system. This allows for computations over finite fields, which avoids the roundoff errors present in \(\mathbb R\)-coefficients. 4. Simulations seem to indicate that for a unit-disc graph network of points in the plane, all complexes are completely reducible, indicating that homology computation is of linear algorithmic complexity.
reviewed by: Andreiy Kondrat'yev
Mathematics Subject Classification ID: 55-04
Mathematics Subject Classification ID: 55N99
Mathematics Subject Classification ID: 52B99
zbMATH DE Number: 6092905
zbMATH Keywords: homology
zbMATH Keywords: sensor network
zbMATH Keywords: coverage
zbMATH Keywords: distributed computation
Wikidata QID: Q112198339
author: Paweł Dłotko
author: Robert Ghrist
author: Mateusz Juda
author: Marian Mrozek
describes a project that uses: CHomP
describes a project that uses: RedHom
MaRDI profile type: Publication
full work available at URL: s00200-012-0167-7
OpenAlex ID: W2116085985
cites work: Mayer-Vietoris sequences and coverage problems in sensor networks
cites work: A new distributed algorithm to find breadth first search trees
cites work: Zigzag persistence
cites work: Zigzag persistent homology and real-valued functions
cites work: Vietoris-Rips complexes of planar point sets
cites work: Local approximation schemes for topology control
cites work: Coordinate-free Coverage in Sensor Networks with Controlled Boundaries via Homology
cites work: Q5450061
cites work: Harmonic functions and boundary value problems on a chain complex
cites work: Deterministic boundary recognition and topology extraction for large sensor networks
cites work: Q4783713
cites work: Coreduction homology algorithm
cites work: Coreduction homology algorithm for inclusions and persistent homology
cites work: Asynchronous Logic Circuits and Sheaf Obstructions
cites work: Distributed Coverage Verification in Sensor Networks Without Location Information
DOI: 10.1007/S00200-012-0167-7
description: scientific article; zbMATH DE number 6092905