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

39 Scopus citations


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
Issue number5
StatePublished - May 2012
Externally publishedYes


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

ASJC Scopus subject areas

  • General Computer Science
  • Modeling and Simulation
  • Management Science and Operations Research


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