Distributed coverage verification in sensor networks without location information

Alireza Tahbaz-Salehi*, Ali Jadbabaie

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

76 Scopus citations


In this paper, we present three distributed algorithms for coverage verification in sensor networks with no location information. We demonstrate how, in the absence of localization devices, simplicial complexes and tools from algebraic topology can be used in providing valuable information about the properties of the cover. Our approach is based on computation of homologies of the Rips complex corresponding to the sensor network. First, we present a decentralized scheme based on Laplacian flows to compute a generator of the first homology, which represents coverage holes. Then, we formulate the problem of localizing coverage holes as an optimization problem for computing a sparse generator of the first homology. Furthermore, we show that one can detect redundancies in the sensor network by finding a sparse generator of the second homology of the cover relative to its boundary. We demonstrate how subgradient methods can be used in solving these optimization problems in a distributed manner. Finally, we provide simulations that illustrate the performance of our algorithms.

Original languageEnglish (US)
Article number5444998
Pages (from-to)1837-1849
Number of pages13
JournalIEEE Transactions on Automatic Control
Issue number8
StatePublished - Aug 2010


  • Combinatorial Laplacians
  • coverage
  • homology
  • sensor networks

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Computer Science Applications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Distributed coverage verification in sensor networks without location information'. Together they form a unique fingerprint.

Cite this