Algorithm design for a class of base station location problems in sensor networks

Yi Shi, Y. Thomas Hou, Alon Efrat

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


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 when the optimization objective is to maximize network capacity. Our (1- ε) approximation algorithm is the first theoretical result on this problem.

Original languageEnglish (US)
Pages (from-to)21-38
Number of pages18
JournalWireless Networks
Issue number1
StatePublished - Jan 2009


  • Approximation algorithm
  • Base station placement
  • Complexity
  • Network capacity
  • Network lifetime
  • Wireless sensor networks

ASJC Scopus subject areas

  • Information Systems
  • Computer Networks and Communications
  • Electrical and Electronic Engineering


Dive into the research topics of 'Algorithm design for a class of base station location problems in sensor networks'. Together they form a unique fingerprint.

Cite this