Energy efficient monitoring in sensor networks

Amol Deshpande*, Samir Khuller, Azarakhsh Malekian, Mohammed Toossi

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationLATIN 2008
Subtitle of host publicationTheoretical Informatics - 8th Latin American Symposium, Proceedings
Number of pages13
StatePublished - 2008
Event8th Latin American TheoreticalINformatics Symposium, LATIN 2008 - Buzios, Brazil
Duration: Apr 7 2008Apr 11 2008

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4957 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference8th Latin American TheoreticalINformatics Symposium, LATIN 2008

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)


Dive into the research topics of 'Energy efficient monitoring in sensor networks'. Together they form a unique fingerprint.

Cite this