2013/07/19 by Vivek Bagaria, Bagaria, Vivek Kumar, Ashwin Pananjady +3 · 1 citation
Computer Science · Environmental Science · #Data Structures and Algorithms (cs.DS) #Energy Efficient Wireless Sensor Networks #FOS: Computer and information sciences #Mobile Ad Hoc Networks #Networking and Internet Architecture (cs.NI) #Optimization and Search Problems #Per- and polyfluoroalkyl substances research
paper · pdf · doi:10.48550/arxiv.1307.5230
openalex publication_date 2013/07/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider the problem of maximizing the lifetime of coverage (MLCP) of\ntargets in a wireless sensor network with battery-limited sensors. We first\nshow that the MLCP cannot be approximated within a factor less than \ln n by\nany polynomial time algorithm, where n is the number of targets. This\nprovides closure to the long-standing open problem of showing optimality of\npreviously known \ln n approximation algorithms. We also derive a new \ln n\napproximation to the MLCP by showing a \ln n approximation to the maximum\ndisjoint set cover problem (DSCP), which has many advantages over previous MLCP\nalgorithms, including an easy extension to the k-coverage problem. We then\npresent an improvement (in certain cases) to the \ln n algorithm in terms of\na newly defined quantity "expansiveness" of the network. For the special\none-dimensional case, where each sensor can monitor a contiguous region of\npossibly different lengths, we show that the MLCP solution is equal to the DSCP\nsolution, and can be found in polynomial time. Finally, for the special\ntwo-dimensional case, where each sensor can monitor a circular area with a\ngiven radius around itself, we combine existing results to derive a\n1+\ε approximation algorithm for solving MLCP for any \ε >0.\n