Title
Maximising lifetime for fault-tolerant target coverage in sensor networks
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.
Year
DOI
Venue
2011
10.1145/1989493.1989521
Sustainable Computing: Informatics and Systems
Keywords
Field
DocType
nemann algorithm,dual problem,previous approximation algorithm,maximising lifetime,fault-tolerant target coverage,fault-tolerant sensor cover,sensor node,composite event,approximation algorithm,sensor network,active sensor node,atomic event,unit disk graph,dynamic programming,set cover,fault tolerant
Set cover problem,Approximation algorithm,Dynamic programming,Computer science,Fault tolerance,Duality (optimization),Euclidean geometry,Wireless sensor network,Unit disk graph,Distributed computing
Conference
ISSN
Citations 
PageRank 
Sustainable Computing: Informatics and Systems
6
0.47
References 
Authors
18
3
Name
Order
Citations
PageRank
Thomas Erlebach11233102.74
Tom Grant2161.16
Frank Kammer3748.89