caa a22 4500 445804785 CHVBK 20180317145153.0 cr unu---uuuuu 170323e20110101xx s 000 0 eng 10.1007/s00453-010-9407-z doi (NATIONALLICENCE)springer-10.1007/s00453-010-9407-z Energy Efficient Monitoring in Sensor Networks [Elektronische Daten] [Amol Deshpande, Samir Khuller, Azarakhsh Malekian, Mohammed Toossi] 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 givenk. 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. We also consider generalizations of this problem in several different directions. First, we allow each sensor to be active in α different sets (time-slots). This means that the battery life is extended by a factor of $\frac{k}{\alpha}$, and allows for a richer space of solutions. We also consider different coverage requirements, such as requiring that all targets, or at least a certain number of targets, be covered in each time slot. In the Set k-Cover formulation, there is no requirement that a target be monitored at all, or in any number of time slots. We develop a randomized rounding algorithm for this problem. We also consider extensions where each sensor can monitor only a bounded number of targets in any time-slot, and not all the targets adjacent to it. This kind of problem may arise when a sensor has a directional camera, or some other physical constraint might prevent it from monitoring all adjacent targets even when it is active. We develop the first approximation algorithms for this problem. Springer Science+Business Media, LLC, 2010 Algorithms nationallicence Complexity nationallicence Approximation algorithm nationallicence Sensor networks nationallicence Energy efficiency nationallicence Target monitoring nationallicence Deshpande Amol Computer Science Department, University of Maryland, College Park, MD, USA aut Khuller Samir Computer Science Department, University of Maryland, College Park, MD, USA aut Malekian Azarakhsh Computer Science Department, University of Maryland, College Park, MD, USA aut Toossi Mohammed Google, Mountain View, CA, USA aut Algorithmica Springer-Verlag 59/1(2011-01-01), 94-114 0178-4617 59:1<94 2011 59 453 https://doi.org/10.1007/s00453-010-9407-z text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9407-z text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Deshpande Amol Computer Science Department, University of Maryland, College Park, MD, USA aut NATIONALLICENCE 700 1- Khuller Samir Computer Science Department, University of Maryland, College Park, MD, USA aut NATIONALLICENCE 700 1- Malekian Azarakhsh Computer Science Department, University of Maryland, College Park, MD, USA aut NATIONALLICENCE 700 1- Toossi Mohammed Google, Mountain View, CA, USA aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 59/1(2011-01-01), 94-114 0178-4617 59:1<94 2011 59 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer