While extending the lifetime of a wireless sensor network (WSN) with full coverage has been extensively studied, it was found recently that the lifetime of a WSN can be prolonged significantly if partial covers are used instead. In this paper, we formally define the problem of extending the lifetime of a WSN using partial covers. (Throughout this paper, we assume that each point of the given target region is covered at least k times by the input sensors.) We first present a centralized algorithm using an optimal subroutine which computes the densest strip with width 2r, where r is the minimum sensing radius of all sensors. By using a known 1-D algorithm, we can cover the center of the strip with k full covers and the remaining subproblems can be solved recursively to have the eventual k partial covers. We then introduce a distributed algorithm without any assumption on the coordinates and directions of sensors, as long as each sensor knows the presence of other sensors within its sensing region. Finally, we present some experimental results comparing the performance of these algorithms with the previous homological partial cover solution. In all small instances the results generated by our algorithms are significantly better than those generated by the homological method. For two larger instances (a larger domain with n around 1000), the homological method cannot finish while both of our algorithms generate promising results.
展开▼
