TY - GEN

T1 - Energy efficient monitoring in sensor networks

AU - Deshpande, Amol

AU - Khuller, Samir

AU - Malekian, Azarakhsh

AU - Toossi, Mohammed

PY - 2008/5/12

Y1 - 2008/5/12

N2 - In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k-Cover, which can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots) and activate each partition in a different time-slot. The goal is to find the partitioning that maximizes the coverage of the regions. This problem is known to be NP-hard. We first develop improved approximation algorithms for this problem based on its similarities to the max k-cut problem. We then consider a variation, called Set (k, α)-cover, where each sensor is allowed to be active in α different time-slots. We develop a randomized routing algorithm for this problem. We then consider extensions where each sensor can monitor only a bounded number of regions in any time-slot. We develop the first approximation algorithms for this problem. An experimental evaluation of the algorithms we propose can be found in the full version of the paper.

AB - In this paper we study a set of problems related to efficient energy management for monitoring applications in wireless sensor networks. We study several generalizations of a basic problem called Set k-Cover, which can be described as follows: we are given a set of sensors, and a set of regions to be monitored. Each region can be monitored by a subset of the sensors. To increase the lifetime of the sensor network, we would like to partition the sensors into k sets (or time-slots) and activate each partition in a different time-slot. The goal is to find the partitioning that maximizes the coverage of the regions. This problem is known to be NP-hard. We first develop improved approximation algorithms for this problem based on its similarities to the max k-cut problem. We then consider a variation, called Set (k, α)-cover, where each sensor is allowed to be active in α different time-slots. We develop a randomized routing algorithm for this problem. We then consider extensions where each sensor can monitor only a bounded number of regions in any time-slot. We develop the first approximation algorithms for this problem. An experimental evaluation of the algorithms we propose can be found in the full version of the paper.

UR - http://www.scopus.com/inward/record.url?scp=43049084793&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=43049084793&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-78773-0_38

DO - 10.1007/978-3-540-78773-0_38

M3 - Conference contribution

AN - SCOPUS:43049084793

SN - 3540787720

SN - 9783540787723

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 436

EP - 448

BT - LATIN 2008

T2 - 8th Latin American TheoreticalINformatics Symposium, LATIN 2008

Y2 - 7 April 2008 through 11 April 2008

ER -