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

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

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2012-05, Vol.39 (5), p.1054-1061
Main Authors: Behdani, Behnam, Yun, Young Sang, Cole Smith, J., Xia, Ye
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Column generation
Columns (structural)
Computer science
control theory
systems
Computer systems and distributed systems. User interface
Computing time
Exact sciences and technology
Information retrieval. Graph
Lifetime maximization
Linear programming
Mathematical programming
Mobile sink
Networks
Operational research and scientific management
Operational research. Management science
Operations research
Optimization algorithms
Sensors
Software
Studies
Theoretical computing
Wireless communication
Wireless networks
Wireless sensor network
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2011.06.013