3rd International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks

Research Article

Algorithm design for base station placement problems in sensor networks

  • @INPROCEEDINGS{10.1145/1185373.1185391,
        author={Yi  Shi and  Y. Thomas Hou and Alon  Efrat},
        title={Algorithm design for base station placement problems in sensor networks},
        proceedings={3rd International ICST Conference on Quality of Service in Heterogeneous Wired/Wireless Networks},
        publisher={ACM},
        proceedings_a={QSHINE},
        year={2006},
        month={8},
        keywords={},
        doi={10.1145/1185373.1185391}
    }
    
  • Yi Shi
    Y. Thomas Hou
    Alon Efrat
    Year: 2006
    Algorithm design for base station placement problems in sensor networks
    QSHINE
    ACM
    DOI: 10.1145/1185373.1185391
Yi Shi1,*, Y. Thomas Hou1,*, Alon Efrat2,*
  • 1: Dept. of Electrical and Computer Engineering, Virginia Tech, Blacksburg, VA, USA.
  • 2: Dept. of Computer Science, University of Arizona, Tucson, AZ, USA.
*Contact email: yshi@vt.edu, tho@vt.edu, alon@cs.arizona.edu

Abstract

Base station placement has significant impact on sensor network performance. Despite its significance, results on this problem remain limited, particularly theoretical results that can provide performance guarantee. This paper proposes a set of procedure to design (1 -- ε) approximation algorithms for base station placement problems under any desired small error bound ε > 0. It offers a general framework to transform infinite search space to a finite-element search space with performance guarantee. We apply this procedure to solve two practical problems. In the first problem where the objective is to maximize network lifetime, an approximation algorithm designed through this procedure offers 1 / ε2 complexity reduction when compared to a state-of-the-art algorithm. This represents the best known result to this problem. In the second problem, we apply the design procedure to address base station placement problem for maximizing network capacity. Our (1 -- ε) approximation algorithm is the first theoretical result on this problem.