TY - JOUR

T1 - Maximum lifetime coverage problems with battery recovery effects

AU - Fu, Norie

AU - Suppakitpaisarn, Vorapong

AU - Kimura, Kei

AU - Kakimura, Naonori

N1 - Publisher Copyright:
© 2014 IEEE.

PY - 2014

Y1 - 2014

N2 - Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.

AB - Scheduling sensors to prolong the lifetime of covering targets in the field is one of the central problems in wireless sensor networks. This problem, called the maximum lifetime coverage problem (MLCP), can be formulated as a linear programming problem with exponential size, and has a constant-factor approximation algorithm. In reality, however, batteries of sensors have recovery effects, which is a phenomenon that the deliverable energy in batteries can be replenished by itself if it is left idling for sufficient duration. Thanks to that effects, we can obtain much longer lifetime of sensors if each sensor is forced to take a sleep at some interval. In this paper, we introduce two models that extend the MLCP, incorporating battery recovery effects. The first model represents battery recovery effects in a deterministic way, while the second one uses a probabilistic model to imitate the effects. We then propose efficient algorithms that work for both models by extending approximation algorithms for the original MLCP. Numerical experiments show that the lifetime of our schedule is 10-40% longer than one without battery recovery effects.

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

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

U2 - 10.1109/GLOCOM.2014.7036794

DO - 10.1109/GLOCOM.2014.7036794

M3 - Conference article

AN - SCOPUS:84988287130

SN - 2334-0983

SP - 118

EP - 124

JO - Proceedings - IEEE Global Communications Conference, GLOBECOM

JF - Proceedings - IEEE Global Communications Conference, GLOBECOM

M1 - 7036794

T2 - 2014 IEEE Global Communications Conference, GLOBECOM 2014

Y2 - 8 December 2014 through 12 December 2014

ER -