Lifetime and Coverage Guarantees Through Distributed Coordinate- Free Sensor Activation

Wireless Sensor Networks are emerging as a key sensing technology, with diverse military and civilian applications. In these networks, a large number of sensors or nodes perform distributed sensing of a target field. Each sensor is a small battery-operated device that can sense events of interest in its sensing range and can communicate with neighboring sensors. A k-sensor cover is a subset of the set of all sensors such that every point in the target field is in the interior of the sensing ranges of at least k different sensors in the subset, where k is a given positive integer. The lifetime of the network is the time from the point the network starts operation until the set of all sensors with non-zero remaining energy is not a k-sensor cover, such that a k-sensor cover is active in every time slot over the lifetime. An important goal in sensor networks is to design a schedule, that is, a sequence of k-sensor covers to activate in every time slot, so as to maximize the lifetime of the network. In this paper, we design a polynomial-time, distributed algorithm for maximizing the lifetime of the network and prove that its lifetime is at most a factor O(log n * log nB) lower than the optimal lifetime achieved by a centralized algorithm, where n is the number of sensors and B is an upper bound on the initial energy of each sensor. Our algorithm does not require knowledge of the locations of nodes or directional information, which is difficult to obtain in sensor networks. Each node only needs to know the distances between adjacent nodes in its transmission range and their sensing radii. In every slot, the algorithm first assigns a weight to each node that is exponential in the fraction of its initial energy that has been used up so far. It then finds a k-sensor cover with the minimum weight up to an O(log n) factor and activates it in that slot. We develop a distributed approximation algorithm for finding the minimum weight k-sensor cover by adapting an existing distributed algorithm for the multicover version of the dominating set problem. Finally, we evaluate the performance of our lifetime maximization algorithm via simulations.