Distributed computation of coverage in sensor networks by homological methods

Recent work on algebraic-topological methods for verifying coverage in planar sensor networks relied exclusively on centralized computation: a limiting constraint for large networks. This paper presents a distributed algorithm for homology computation over a sensor network, for purposes of verifying...

Full description

Saved in:
Bibliographic Details
Published in:Applicable algebra in engineering, communication and computing communication and computing, 2012-04, Vol.23 (1-2), p.29-58
Main Authors: Dłotko, P., Ghrist, R., Juda, M., Mrozek, M.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Computer Hardware
Computer Science
Original Paper
Symbolic and Algebraic Manipulation
Theory of Computation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Recent work on algebraic-topological methods for verifying coverage in planar sensor networks relied exclusively on centralized computation: a limiting constraint for large networks. This paper presents a distributed algorithm for homology computation over a sensor network, for purposes of verifying coverage. The techniques involve reduction and coreduction of simplicial complexes, and are of independent interest. Verification of the ensuing algorithms is proved, and simulations detail the improved network efficiency and performance.
ISSN:0938-1279
1432-0622
DOI:10.1007/s00200-012-0167-7