Approximation algorithms for two optimal location problems in sensor networks

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 α, or that each point is seen by three sensors that form a triangle containing the point).