Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes

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

Research output: Contribution to journalArticle

5 Citations (Scopus)

Abstract

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
Volume17
Issue number2
DOIs
Publication statusPublished - 2011 Feb 1

Fingerprint

Wireless sensor networks
Costs
Sensors
Routing algorithms
Linear programming
Polynomials
Monitoring

Keywords

  • Deployment problem
  • Guaranteed lifetime
  • Sensor network

ASJC Scopus subject areas

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

Cite this

Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes. / Lin, Chun-Han; King, Chung Ta; Chen, Ting Yi.

In: Wireless Networks, Vol. 17, No. 2, 01.02.2011, p. 385-396.

Research output: Contribution to journalArticle

@article{5d2ed19e04b6456297099ab9475a92d3,
title = "Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes",
abstract = "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.",
keywords = "Deployment problem, Guaranteed lifetime, Sensor network",
author = "Chun-Han Lin and King, {Chung Ta} and Chen, {Ting Yi}",
year = "2011",
month = "2",
day = "1",
doi = "10.1007/s11276-010-0286-7",
language = "English",
volume = "17",
pages = "385--396",
journal = "Wireless Networks",
issn = "1022-0038",
publisher = "Springer Netherlands",
number = "2",

}

TY - JOUR

T1 - Constrained multiple deployment problem in wireless sensor networks with guaranteed lifetimes

AU - Lin, Chun-Han

AU - King, Chung Ta

AU - Chen, Ting Yi

PY - 2011/2/1

Y1 - 2011/2/1

N2 - 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.

AB - 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.

KW - Deployment problem

KW - Guaranteed lifetime

KW - Sensor network

UR - http://www.scopus.com/inward/record.url?scp=79951514745&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=79951514745&partnerID=8YFLogxK

U2 - 10.1007/s11276-010-0286-7

DO - 10.1007/s11276-010-0286-7

M3 - Article

AN - SCOPUS:79951514745

VL - 17

SP - 385

EP - 396

JO - Wireless Networks

JF - Wireless Networks

SN - 1022-0038

IS - 2

ER -