%0 Conference Proceedings
%T Decentralized Computation of Homology in Wireless Sensor Networks Using Spanning Trees
%+ University of Ljubljana
%+ Jozef Stefan Institute [Ljubljana] (IJS)
%A Šoberl, Domen
%A Kosta, Neža, Mramor
%A Škraba, Primož
%Z Part 1: MAKE Topology
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 1st International Cross-Domain Conference for Machine Learning and Knowledge Extraction (CD-MAKE)
%C Reggio, Italy
%Y Andreas Holzinger
%Y Peter Kieseberg
%Y A Min Tjoa
%Y Edgar Weippl
%I Springer International Publishing
%3 Machine Learning and Knowledge Extraction
%V LNCS-10410
%P 25-40
%8 2017-08-29
%D 2017
%R 10.1007/978-3-319-66808-6_3
%K Wireless sensor networks
%K Coverage problem
%K Simplicial homology
%K Computational homology
%K Rips complex
%Z Computer Science [cs]
%Z Humanities and Social Sciences/Library and information sciencesConference papers
%X When deploying a wireless sensor network over an area of interest, the information on signal coverage is critical. It has been shown that even when geometric position and orientation of individual nodes is not known, useful information on coverage can still be deduced based on connectivity data. In recent years, homological criteria have been introduced to verify complete signal coverage, given only the network communication graph. However, their algorithmic implementation has been limited due to high computational complexity of centralized algorithms, and high demand for communication in decentralized solutions, where a network employs the processing power of its nodes to check the coverage autonomously. To mitigate these problems, known approaches impose certain limitations on network topologies. In this paper, we propose a novel distributed algorithm which uses spanning trees to verify homology-based network coverage criteria, and works for arbitrary network topologies. We demonstrate that its communication demands are suitable even for low-bandwidth wireless sensor networks.
%G English
%Z TC 5
%Z TC 8
%Z TC 12
%Z WG 8.4
%Z WG 8.9
%Z WG 12.9
%2 https://inria.hal.science/hal-01677133/document
%2 https://inria.hal.science/hal-01677133/file/456304_1_En_3_Chapter.pdf
%L hal-01677133
%U https://inria.hal.science/hal-01677133
%~ SHS
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC5
%~ IFIP-WG
%~ IFIP-TC12
%~ IFIP-TC8
%~ IFIP-WG8-4
%~ IFIP-WG8-9
%~ IFIP-LNCS-10410
%~ IFIP-CD-MAKE
%~ IFIP-WG12-9