2nd International ICST Conference on Broadband Networks

Research Article

Approximation algorithms for two optimal location problems in sensor networks

  • @INPROCEEDINGS{10.1109/ICBN.2005.1589677,
        author={Alon Efrat and Sariel Har-Peled and Joseph S. B. Mitchell},
        title={Approximation algorithms for two optimal location problems in sensor networks},
        proceedings={2nd International ICST Conference on Broadband Networks},
        publisher={IEEE},
        proceedings_a={BROADNETS},
        year={2006},
        month={2},
        keywords={},
        doi={10.1109/ICBN.2005.1589677}
    }
    
  • Alon Efrat
    Sariel Har-Peled
    Joseph S. B. Mitchell
    Year: 2006
    Approximation algorithms for two optimal location problems in sensor networks
    BROADNETS
    IEEE
    DOI: 10.1109/ICBN.2005.1589677
Alon Efrat1,2,*, Sariel Har-Peled3, Joseph S. B. Mitchell4,5,*
  • 1: Department of Computer Science; University of Arizona, Tucson, Arizona 85721
  • 2: Work on this paper was partially supported by an NSF CAREER award (CCR-0348000) and an ITR/Collaborative Research grant (0312443)
  • 3: Work on this paper was partially supported by a NSF CAREER award CCR-0132901
  • 4: Applied Mathematics & Statistics; Stony Brook University; Stony Brook, New York 11794-3600;
  • 5: Work on this paper was partiallysupported by grants from NASA Ames Research (NAG2-1620), the National Science Foundation (CCR-0098172, ACI-0328930), Metron Aviation, and the U.S.-Israel Binational Science Foundation (No. 2000160).
*Contact email: alon@cs.arizona.edu, jsbm@ams.sunysb.edu

Abstract

This paper study 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. We assume "line-of-site", sensors, that sense a point only if the straight segment connecting the sensor to this point (the "line-of-site") does not cross any obstacle. so obstacles occludes area from 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 a, or that each point is seen by three sensors that form a triangle containing the point).