Content area

Abstract

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.

Details

Title
Sensor Strip Cover: Maximizing Network Lifetime on an Interval
Author
Baumer, Benjamin
Year
2012
Publisher
ProQuest Dissertations & Theses
ISBN
978-1-267-34440-3
Source type
Dissertation or Thesis
Language of publication
English
ProQuest document ID
1018420341
Copyright
Database copyright ProQuest LLC; ProQuest does not claim copyright in the individual underlying works.