Author(s): Manju | Arun K Pujari
Journal: International Journal of Ad Hoc, Sensor & Ubiquitous Computing
ISSN 0976-2205
Volume: 2;
Issue: 1;
Start page: 45;
Date: 2011;
VIEW PDF
DOWNLOAD PDF 
Original page
Keywords: Target Coverage Problem | Greedy Heuristic | Wireless Sensor Networks | Energy-Efficiency | Network Lifetime.
ABSTRACT
Target coverage problem in wireless sensor networks is concerned with maximizing the lifetime of thenetwork while continuously monitoring a set of targets. A sensor covers targets which are within thesensing range. For a set of sensors and a set of targets, the sensor-target coverage relationship isassumed to be known. A sensor cover is a set of sensors that covers all the targets. The target coverageproblem is to determine a set of sensor covers with maximum aggregated lifetime while constraining thelife of each sensor by its initial battery life. The problem is proved to be NP-complete and heuristicalgorithms to solve this problem are proposed. In the present study, we give a unified interpretation ofearlier algorithms and propose a new and efficient algorithm. We show that all known algorithms arebased on a common reasoning though they seem to be derived from different algorithmic paradigms. Wealso show that though some algorithms guarantee bound on the quality of the solution, this bound is notmeaningful and not practical too. Our interpretation provides a better insight to the solution techniques.We propose a new greedy heuristic which prioritizes sensors on residual battery life. We showempirically that the proposed algorithm outperforms all other heuristics in terms of quality of solution.Our experimental study over a large set of randomly generated problem instances also reveals that a verynaïve greedy approach yields solutions which is reasonably (appx. 10%) close to the actual optimalsolutions.
Journal: International Journal of Ad Hoc, Sensor & Ubiquitous Computing
ISSN 0976-2205
Volume: 2;
Issue: 1;
Start page: 45;
Date: 2011;
VIEW PDF
DOWNLOAD PDF Original pageKeywords: Target Coverage Problem | Greedy Heuristic | Wireless Sensor Networks | Energy-Efficiency | Network Lifetime.
ABSTRACT
Target coverage problem in wireless sensor networks is concerned with maximizing the lifetime of thenetwork while continuously monitoring a set of targets. A sensor covers targets which are within thesensing range. For a set of sensors and a set of targets, the sensor-target coverage relationship isassumed to be known. A sensor cover is a set of sensors that covers all the targets. The target coverageproblem is to determine a set of sensor covers with maximum aggregated lifetime while constraining thelife of each sensor by its initial battery life. The problem is proved to be NP-complete and heuristicalgorithms to solve this problem are proposed. In the present study, we give a unified interpretation ofearlier algorithms and propose a new and efficient algorithm. We show that all known algorithms arebased on a common reasoning though they seem to be derived from different algorithmic paradigms. Wealso show that though some algorithms guarantee bound on the quality of the solution, this bound is notmeaningful and not practical too. Our interpretation provides a better insight to the solution techniques.We propose a new greedy heuristic which prioritizes sensors on residual battery life. We showempirically that the proposed algorithm outperforms all other heuristics in terms of quality of solution.Our experimental study over a large set of randomly generated problem instances also reveals that a verynaïve greedy approach yields solutions which is reasonably (appx. 10%) close to the actual optimalsolutions.