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).