Please use this identifier to cite or link to this item:
Title: Maximising lifetime for fault-tolerant target coverage in sensor networks
Authors: Erlebach, Thomas
Grant, Tom
Kammer, Frank
First Published: 2011
Presented at: 23rd ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA, June 04 - 06, 2011.
Publisher: ACM
Citation: Proceedins of the 23rd annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011, pp. 187-196
Abstract: We study the problem of maximising the lifetime of a sensor network for fault-tolerant target coverage in a setting with composite events. Here, a composite event is the simultaneous occurrence of a combination of atomic events, such as the detection of smoke and high temperature. We are given sensor nodes that have an initial battery level and can monitor certain event types, and a set of points at which composite events need to be detected. The points and sensor nodes are located in the Euclidean plane, and all nodes have the same sensing radius. The goal is to compute a longest activity schedule with the property that at any point in time, each event point is monitored by at least two active sensor nodes. We present a (6 + ε)-approximation algorithm for this problem by devising an approximation algorithm with the same ratio for the dual problem of minimising the weight of a fault-tolerant sensor cover and applying the Garg-Könemann algorithm. Our algorithm for the minimum-weight fault-tolerant sensor cover problem generalises previous approximation algorithms for geometric set cover with weighted unit disks and is obtained by enumerating properties of the optimal solution that guide a dynamic programming approach.
DOI Link: 10.1145/1989493.1989521
ISBN: 978-1-4503-0743-7
Version: Post-print
Status: Peer-reviewed
Type: Conference Paper
Rights: Copyright © 2011 ACM. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 23rd Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2011, pp. 187-196 10.1145/1989493.1989521
Appears in Collections:Conference Papers & Presentations, Dept. of Computer Science

Files in This Item:
File Description SizeFormat 
ErlebachSPAA2011_LRA.pdf354.72 kBAdobe PDFView/Open

Items in LRA are protected by copyright, with all rights reserved, unless otherwise indicated.