An energy-efficient algorithm for connected target coverage problem in wireless sensor networks

Abstract

A major concern in wireless sensor networks is to maximize network lifetime while maintaining a high quality of services (QOS) such as target coverage and network connectivity. Communication and sensing consume energy, therefore efficient power management can extend network lifetime. in this paper we consider a large number of static sensor nodes are deployed in order to monitor a number of target points in the region. each target point may be redundantly covered by multiple sensors. one approach to conserve energy is to organize the deployed sensors into subsets of sensors, or sensor covers such that each subset can cover all targets in the region and each sensor to be activated is connected to the Base Station (BS). This subsets activated successively and only the sensors from active subset are responsible for monitoring all targets. The more sensor covers can be found, the longer network lifetime can be prolonged. finding maximum number of sensor covers can be solved via transformation to the connected set covers (CSC) problem, wich has been proved to be NP-complete. for this optimization problem, existing algorithms either get unsatisfactory solutions and in most cases take exponential time complexity. In this paper we propose a heuristic solution to solve the CSC problem. the simulation results show that the proposed algorithm can get acceptable solutions with polynomial computation time and can improve the performance of the Greedy-CSC heuristic algorithm in solution quality and it has better performance than IP-CSC heuristic in large scenarios.