A New Distributed Algorithm for Even Coverage and Improved Lifetime in a Sensor Network

In "area-sensing" applications of sensor networks, such as surveillance or target tracking, each sensor node has a sensing radius within which it can monitor events. Coverage problems in sensor networks have largely focused on such applications, where the goal of good coverage is one of ensuring that each point in the region of interest is within the sensing radius of at least one node. On the other hand, in "spot-sensing" applications, each node makes a measurement (such as temperature or humidity) at the precise location of the node and there is no concept of a sensing radius. In this paper, we introduce a new coverage problem that is more meaningful to spot-sensing applications. In such cases, good coverage usually implies even coverage across points in the region. We borrow from the field of economics and adapt a well-accepted measure of inequality, the Gini index, to develop a metric for the evenness of coverage by a sensor network. Based on mathematical results on the expected distances between neighboring nodes, we present a new distributed algorithm, called EvenCover, for each node to determine if and when it should sleep or sense. We prove that the expected Gini index is 1 - 1radic2 ap 0.293 when the spatial distribution of sensing nodes is given by a Poisson random process. On the other hand, when the sensing nodes are perfectly evenly distributed, we show that the Gini index has a lower bound of 0.2. These two results serve as points of reference to evaluate the coverage achieved by the EvenCover algorithm. We present a thorough simulation-based comparison of EvenCover against other distributed algorithms showing that it achieves better evenness and significantly increased lifetime. In addition, we discover that evenness of coverage permits a graceful degradation of the network as nodes exhaust their energy resources.