Skip to main content
Journal cover image

Failure filtrations for fenced sensor networks

Publication ,  Journal Article
Munch, E; Shapiro, M; Harer, J
Published in: International Journal of Robotics Research
August 1, 2012

In this paper we consider the question of sensor network coverage for a two-dimensional domain. We seek to compute the probability that a set of sensors fails to cover given only non-metric, local (who is talking to whom) information and a probability distribution of failure of each node. This builds on the work of de Silva and Ghrist who analyzed this problem in the deterministic situation. We first show that it is part of a slightly larger class of problems which is #P-hard, and thus fast algorithms likely do not exist unless P = NP. The question of whether the specific problem is, in fact, #P-hard remains open. We then give a deterministic algorithm which is feasible in the case of a small set of sensors, and give a dynamic algorithm for an arbitrary set of sensors failing over time which utilizes a new criterion for coverage to give an early warning of potential failure. These algorithms build on the theory of topological persistence. © The Author(s) 2012.

Duke Scholars

Published In

International Journal of Robotics Research

DOI

EISSN

1741-3176

ISSN

0278-3649

Publication Date

August 1, 2012

Volume

31

Issue

9

Start / End Page

1044 / 1056

Related Subject Headings

  • Industrial Engineering & Automation
  • 4603 Computer vision and multimedia computation
  • 4007 Control engineering, mechatronics and robotics
  • 0913 Mechanical Engineering
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Munch, E., Shapiro, M., & Harer, J. (2012). Failure filtrations for fenced sensor networks. International Journal of Robotics Research, 31(9), 1044–1056. https://doi.org/10.1177/0278364912451671
Munch, E., M. Shapiro, and J. Harer. “Failure filtrations for fenced sensor networks.” International Journal of Robotics Research 31, no. 9 (August 1, 2012): 1044–56. https://doi.org/10.1177/0278364912451671.
Munch E, Shapiro M, Harer J. Failure filtrations for fenced sensor networks. International Journal of Robotics Research. 2012 Aug 1;31(9):1044–56.
Munch, E., et al. “Failure filtrations for fenced sensor networks.” International Journal of Robotics Research, vol. 31, no. 9, Aug. 2012, pp. 1044–56. Scopus, doi:10.1177/0278364912451671.
Munch E, Shapiro M, Harer J. Failure filtrations for fenced sensor networks. International Journal of Robotics Research. 2012 Aug 1;31(9):1044–1056.
Journal cover image

Published In

International Journal of Robotics Research

DOI

EISSN

1741-3176

ISSN

0278-3649

Publication Date

August 1, 2012

Volume

31

Issue

9

Start / End Page

1044 / 1056

Related Subject Headings

  • Industrial Engineering & Automation
  • 4603 Computer vision and multimedia computation
  • 4007 Control engineering, mechatronics and robotics
  • 0913 Mechanical Engineering
  • 0906 Electrical and Electronic Engineering
  • 0801 Artificial Intelligence and Image Processing