Distributed computation of a sparse cover in sensor networks without location information

Alireza Tahbaz-Salehi*, Ali Jadbabaie

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations

Abstract

In this paper, we present a distributed algorithm for detecting redundancies in a sensor network with no location information. We demonstrate how, in the absence of localization devices, simplicial complexes and tools from computational homology can be used in providing valuable information on the properties of the cover. In particular, we capture the combinatorial relationships among the sensors by the means of the Rips complex, which is the generalization of the proximity graph of the network to higher dimensions. Our approach is based on computation of a certain generator of the second homology of the Rips complex of the network relative to the boundary. We formulate the problem of detecting redundant sensors as an optimization problem to compute the sparsest generator of the second relative homology classes. We also demonstrate how subgradient methods can be used in solving this optimization problem in a distributed manner. Finally, nontrivial simulations are provided that illustrate the performance of our algorithm.

Original languageEnglish (US)
Title of host publicationCISS 2008, The 42nd Annual Conference on Information Sciences and Systems
Pages1285-1290
Number of pages6
DOIs
StatePublished - Sep 22 2008
EventCISS 2008, 42nd Annual Conference on Information Sciences and Systems - Princeton, NJ, United States
Duration: Mar 19 2008Mar 21 2008

Publication series

NameCISS 2008, The 42nd Annual Conference on Information Sciences and Systems

Other

OtherCISS 2008, 42nd Annual Conference on Information Sciences and Systems
CountryUnited States
CityPrinceton, NJ
Period3/19/083/21/08

ASJC Scopus subject areas

  • Computer Science Applications
  • Information Systems
  • Control and Systems Engineering

Fingerprint Dive into the research topics of 'Distributed computation of a sparse cover in sensor networks without location information'. Together they form a unique fingerprint.

Cite this