Math @ Duke

Publications [#243591] of John Harer
Papers Published
 Munch, E; Shapiro, M; Harer, J, Failure filtrations for fenced sensor networks,
International Journal of Robotics Research, vol. 31 no. 9
(2012),
pp. 10441056, ISSN 02783649 [1109.6535v1], [doi]
(last updated on 2018/12/19)
Abstract: In this paper we consider the question of sensor network coverage for a twodimensional domain. We seek to compute the probability that a set of sensors fails to cover given only nonmetric, 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 #Phard, and thus fast algorithms likely do not exist unless P = NP. The question of whether the specific problem is, in fact, #Phard 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

