Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes

Chun Han Lin*, Chung Ta King, Ting Yi Chen

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


We aimed to deploy wireless sensor networks with guaranteed lifetimes for outdoor monitoring projects. The provision of a guaranteed lifetime has rarely been studied in previous deployment problems. The use of battery packs as the power source for sensors is common in many applications involving outdoor wireless sensor networks (WSNs). Because unified battery power is unable to provide both efficient collection and balance workload, we address the deployment procedure by considering adjustable battery packs. The key issue is determining the minimum number of battery packs required to guarantee both the system efficiency and lifetime. We formulate a constrained multiple deployment problem with energy models of the battery energy budget and sensor operations. The optimal solution is obtained using integer linear programming. We derived a lower bound of the deployment cost in terms of the number of battery packs. Due to the high time complexity for solving the optimal solution, we also propose two heuristics with polynomial-time complexity: (1) a battery-aware routing algorithm that selects routing paths based on consideration of the battery usage, and (2) a refinement procedure to improve existing WSN deployments by adjusting traffic in order to reduce the cost. Theoretical analyses of the proposed algorithms revealed their time complexity. We performed extensive simulations to evaluate the proposed algorithms in terms of the deployment cost and residual energy. The results show that our algorithm generates deployments close to the lower bound.

Original languageEnglish
Pages (from-to)385-396
Number of pages12
JournalWireless Networks
Issue number2
Publication statusPublished - 2011 Feb
Externally publishedYes


  • Deployment problem
  • Guaranteed lifetime
  • Sensor network

ASJC Scopus subject areas

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


Dive into the research topics of 'Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes'. Together they form a unique fingerprint.

Cite this