Paper Info
Title
Decomposition algorithms for maximizing the lifetime of wireless sensor networks with mobile sinks
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.
Year
DOI
Venue
2012
10.1016/j.cor.2011.06.013
Computers & OR
Keywords
DocType
Volume
consumes energy,Wireless sensor network,shortest path problem,Mobile sink,sink location,linear programming,column generation approach,Linear programming,linear programming formulation,wireless sensor network,data flow pattern,mobile sink,decomposition algorithm,vital problem,Lifetime maximization,Column generation
Journal
39
Issue
ISSN
Citations 
5
Computers and Operations Research
6
PageRank 
References 
Authors
0.48
11
4
Name
Order
Citations
PageRank
Behnam Behdani1512.68
Young Sang Yun260.48
J. Cole Smith361043.34
Ye Xia4594.76