Energy Efficient Monitoring in Sensor Networks |
| |
Authors: | Amol Deshpande Samir Khuller Azarakhsh Malekian Mohammed Toossi |
| |
Affiliation: | 1.Computer Science Department,University of Maryland,College Park,USA;2.Google,Mountain View,USA |
| |
Abstract: | We study a set of problems related to efficient battery energy utilization for monitoring applications in a wireless sensor network with the goal to increase the sensor network lifetime. We study several generalizations of a basic problem called Set k-Cover. The problem can be described as follows: we are given a set of sensors, and a set of targets to be monitored. Each target 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 set of sensors in a different time-slot, thus extending the battery life of the sensors by a factor of k. The goal is to find a partitioning that maximizes the total coverage of the targets for a given k. This problem is known to be NP-hard. We develop an improved approximation algorithm for this problem using a reduction to Max k-Cut. Moreover, we are able to demonstrate that this algorithm is efficient, and yields almost optimal solutions in practice. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|