Home Bookmarks Papers Blog

Approximation Algorithms for Two Optimal Location Problems in Sensor Networks

Alon Efrat, Sariel Har-Peled and Joseph S. B. Mitchell.


This paper studies two problems that arise in optimization of sensor networks: First, we devise provable approximation schemes for locating a base station and constructing a network among a set of sensors each of which has a data stream to get to the base station. Subject to power constraints at the sensors, our goal is to locate the base station and establish a network in order to maximize the lifespan of the network.

Second, we study optimal sensor placement problems for quality coverage of given domains cluttered with obstacles. Using line-of-site sensors, the goal is to minimize the number of sensors required in order to have each point ``well covered'' according to precise criteria(e.g., that each point is seen by two sensors that form at least angle alpha, or that each point is seen by three sensors that form a triangle containing the point).

Postscript, PDF.


Last modified: Thu Aug 5 19:05:23 CDT 2004