TY - GEN
T1 - Bundle Charging
T2 - 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019
AU - Wang, Ning
AU - Wu, Jie
AU - Dai, Haipeng
N1 - Publisher Copyright: © 2019 IEEE.
PY - 2019/7
Y1 - 2019/7
N2 - Using a mobile charger to wirelessly charge sensors is a promising yet not well-solved technique. Existing trajectory planning schemes for wireless charger either (1) fail to optimize the one-to-many characteristic of wireless charging or (2) fail to jointly optimize the charger movement cost and the charging cost. The objective of this paper is to find the optimal trajectory planning for a mobile charger in terms of energy minimization in the quadratic attenuation charging model. There exists a trade-off between charging efficiency and trajectory distance. If the mobile charger comes close to sensors, the charging efficiency is high, but the entire charging trajectory of the charger will be long and vice versa. To address this trade-off, we propose the idea of charging bundle and optimize the charger's trajectory based on the charging bundle rather than each sensor. The optimal charging bundle generation problem and the bundle trajectory optimization problem are discussed gradually. Both of them are proven to be NP-hard. Then, we first propose a greedy bundle generation algorithm with an approximation ratio of lnn, where n is the number of sensors. After that, we propose a TSP-based solution and further optimize the TSP-trajectory by jointly considering the adjacent charging locations. Theorems are proposed to effectively find the optimal location. Extensive experiments show that our scheme achieves a much better performance than traditional schemes.
AB - Using a mobile charger to wirelessly charge sensors is a promising yet not well-solved technique. Existing trajectory planning schemes for wireless charger either (1) fail to optimize the one-to-many characteristic of wireless charging or (2) fail to jointly optimize the charger movement cost and the charging cost. The objective of this paper is to find the optimal trajectory planning for a mobile charger in terms of energy minimization in the quadratic attenuation charging model. There exists a trade-off between charging efficiency and trajectory distance. If the mobile charger comes close to sensors, the charging efficiency is high, but the entire charging trajectory of the charger will be long and vice versa. To address this trade-off, we propose the idea of charging bundle and optimize the charger's trajectory based on the charging bundle rather than each sensor. The optimal charging bundle generation problem and the bundle trajectory optimization problem are discussed gradually. Both of them are proven to be NP-hard. Then, we first propose a greedy bundle generation algorithm with an approximation ratio of lnn, where n is the number of sensors. After that, we propose a TSP-based solution and further optimize the TSP-trajectory by jointly considering the adjacent charging locations. Theorems are proposed to effectively find the optimal location. Extensive experiments show that our scheme achieves a much better performance than traditional schemes.
UR - https://www.scopus.com/pages/publications/85074828323
UR - https://www.scopus.com/pages/publications/85074828323#tab=citedBy
U2 - 10.1109/ICDCS.2019.00085
DO - 10.1109/ICDCS.2019.00085
M3 - Conference contribution
T3 - Proceedings - International Conference on Distributed Computing Systems
SP - 810
EP - 820
BT - Proceedings - 2019 39th IEEE International Conference on Distributed Computing Systems, ICDCS 2019
PB - Institute of Electrical and Electronics Engineers Inc.
Y2 - 7 July 2019 through 9 July 2019
ER -