Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks

Behnam Behdani, Young Sang Yun, J. Cole Smith, Ye Xia

Research output: Contribution to journalArticlepeer-review

37 Scopus citations

Abstract

We address the problem of maximizing the lifetime of a wireless sensor network with energy-constrained sensors and a mobile sink. The sink travels among discrete locations to gather information from all the sensors. Data can be relayed among sensors and then to the sink location, as long as the sensors and the sink are within a certain threshold distance of each other. However, sending information along a data link consumes energy at both the sender and the receiver nodes. A vital problem that arises is to prescribe sink stop durations and data flow patterns that maximally prolong the life of the network, defined as the amount of time until any node exhausts its energy. We describe linear programming and column generation approaches for this problem, and also for a version in which data can be delayed in its transmission to the sink. Our column generation approach exploits special structures of the linear programming formulations so that all subproblems are shortest path problems with non-negative costs. Computational results demonstrate the efficiency of the proposed algorithms.

Original languageEnglish (US)
Pages (from-to)1054-1061
Number of pages8
JournalComputers and Operations Research
Volume39
Issue number5
DOIs
StatePublished - May 1 2012
Externally publishedYes

Keywords

  • Column generation
  • Lifetime maximization
  • Linear programming
  • Mobile sink
  • Wireless sensor network

ASJC Scopus subject areas

  • Computer Science(all)
  • Modeling and Simulation
  • Management Science and Operations Research

Fingerprint Dive into the research topics of 'Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks'. Together they form a unique fingerprint.

Cite this