Suppose that n sensors are deployed on a one-dimensional region (a strip, or interval) that we wish to cover with a wireless sensor network. Each sensor is equipped with a finite battery, and has an adjustable sensing range, which we control. If each sensor's battery drains in inverse linear proportion to its sensing radius, which schedule will maximize the lifetime of the resulting network? We study this Sensor Strip Cover problem and several related variants. For the general Sensor Strip Cover problem, we analyze performance in both the worst-case and average-case for several algorithms, and show that the simplest algorithm, in which the sensors take turns covering the entire line, has a tight 3/2-approximation ratio. Moreover, we demonstrate a more sophisticated algorithm that achieves an expected lifetime of within 12% of the theoretical maximum against uniform random deployment of the sensors. We show that if the sensing radii can be set only once, then the resulting Set Once Strip Cover problem is NP-hard. However, if all sensors must be activated immediately, then we provide a polynomial time algorithm for the resulting Set Radius Strip Cover problem. Finally, we consider the imposition of a duty cycling restriction, which forces disjoint subsets of the sensors (called shifts) to act in concert to cover the entire interval. We provide a polynomial-time solution for the case in which each shift contains at most two sensors. For shifts of size k, we provide worst-case and average-case analysis for the performance of several algorithms.
展开▼
