Failure filtrations for fenced sensor networks

Elizabeth Munch, Michael Shapiro, John Harer

Research output: Contribution to journalArticle

8 Citations (Scopus)

Abstract

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.
Original languageEnglish
Pages (from-to)1044-1056
JournalThe International Journal of Robotics Research
Volume31
Issue number9
DOIs
Publication statusPublished - 1 Jul 2012

Cite this

Failure filtrations for fenced sensor networks. / Munch, Elizabeth; Shapiro, Michael; Harer, John.

In: The International Journal of Robotics Research, Vol. 31, No. 9, 01.07.2012, p. 1044-1056.

Research output: Contribution to journalArticle

Munch, Elizabeth ; Shapiro, Michael ; Harer, John. / Failure filtrations for fenced sensor networks. In: The International Journal of Robotics Research. 2012 ; Vol. 31, No. 9. pp. 1044-1056.
@article{35c88e611dfd4b7f8738c11cb4d169ae,
title = "Failure filtrations for fenced sensor networks",
abstract = "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.",
author = "Elizabeth Munch and Michael Shapiro and John Harer",
year = "2012",
month = "7",
day = "1",
doi = "10.1177/0278364912451671",
language = "English",
volume = "31",
pages = "1044--1056",
journal = "The International Journal of Robotics Research",
issn = "0278-3649",
publisher = "MIT Press",
number = "9",

}

TY - JOUR

T1 - Failure filtrations for fenced sensor networks

AU - Munch, Elizabeth

AU - Shapiro, Michael

AU - Harer, John

PY - 2012/7/1

Y1 - 2012/7/1

N2 - 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.

AB - 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.

U2 - 10.1177/0278364912451671

DO - 10.1177/0278364912451671

M3 - Article

VL - 31

SP - 1044

EP - 1056

JO - The International Journal of Robotics Research

JF - The International Journal of Robotics Research

SN - 0278-3649

IS - 9

ER -