TY - JOUR
T1 - Efficient scheduling of multiple mobile chargers for wireless sensor networks
AU - Xu, Wenzheng
AU - Liang, Weifa
AU - Lin, Xiaola
AU - Mao, Guoqiang
N1 - Publisher Copyright:
© 2015 IEEE.
PY - 2016/9
Y1 - 2016/9
N2 - In this paper, we study the deployment of multiple mobile charging vehicles to charge sensors in a large-scale wireless sensor network for a given monitoring period so that none of the sensors will run out of energy, where sensors can be charged by the charging vehicles with wireless energy transfer. To minimize the network operational cost, we first formulate a charging scheduling problem of dispatching multiple mobile charging vehicles to collaboratively charge sensors such that the sum of travelling distance (referred to as the service cost) of these vehicles for this monitoring period is minimized, subject to that none of the sensors will run out of energy. Due to NP-hardness of the problem, we then propose a novel approximation algorithm with a guaranteed approximation ratio, assuming that the energy consumption rate of each sensor does not change for the given monitoring period. Otherwise, we devise a heuristic algorithm through modifications to the approximation algorithm. We finally evaluate the performance of the proposed algorithms via experimental simulations. Simulation results show that the proposed algorithms are very promising, which can reduce the service cost by up to 20% in comparison with the service costs delivered by existing ones.
AB - In this paper, we study the deployment of multiple mobile charging vehicles to charge sensors in a large-scale wireless sensor network for a given monitoring period so that none of the sensors will run out of energy, where sensors can be charged by the charging vehicles with wireless energy transfer. To minimize the network operational cost, we first formulate a charging scheduling problem of dispatching multiple mobile charging vehicles to collaboratively charge sensors such that the sum of travelling distance (referred to as the service cost) of these vehicles for this monitoring period is minimized, subject to that none of the sensors will run out of energy. Due to NP-hardness of the problem, we then propose a novel approximation algorithm with a guaranteed approximation ratio, assuming that the energy consumption rate of each sensor does not change for the given monitoring period. Otherwise, we devise a heuristic algorithm through modifications to the approximation algorithm. We finally evaluate the performance of the proposed algorithms via experimental simulations. Simulation results show that the proposed algorithms are very promising, which can reduce the service cost by up to 20% in comparison with the service costs delivered by existing ones.
KW - Approximation algorithms
KW - Combinatorial optimization problems
KW - Mobile chargers
KW - Periodic charging cycles
KW - Rechargeable sensor networks
KW - Wireless energy transfer
UR - http://www.scopus.com/inward/record.url?scp=84991010623&partnerID=8YFLogxK
U2 - 10.1109/TVT.2015.2496971
DO - 10.1109/TVT.2015.2496971
M3 - Article
SN - 0018-9545
VL - 65
SP - 7670
EP - 7683
JO - IEEE Transactions on Vehicular Technology
JF - IEEE Transactions on Vehicular Technology
IS - 9
M1 - 7362022
ER -