Approximate Coverage in Wireless Sensor Networks

Abstract

Recent advances in microelectronic technology have made it possible to construct compact and inexpensive wireless sensors. Sensor networks have received significant attention due to their potential applications from civil to military domains. Since sensors in sensor networks are equipped with energy-limited batteries, energy conservation in such networks is of paramount importance in order to prolong the network lifetime. Sensing coverage and sensor connectivity in sensor networks are two fundamental issues, which have been extensively addressed in the literature, and most existing work on sensing coverage has focused on the (connected) full coverage problem that aims to cover the entire monitored region using the minimum number of sensors. However, in some application scenarios, full coverage is either impossible or unnecessary and a partial coverage with a certain degree guarantee is acceptable. In this paper, we study the connected coverage problem with a given coverage guarantee. We first introduce the partial coverage concept and analyze its properties for the first time in order to prolong the network lifetime. Due to NP-hardness of the concerned problem, we then present a heuristic algorithm which takes into account the partial coverage and sensor connectivity simultaneously. We finally conduct extensive experiments by simulations to evaluate the performance of the proposed algorithm.