TY - GEN
T1 - Charge me if you Can
T2 - 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2016
AU - Chen, Lin
AU - Lin, Shan
AU - Huang, Hua
N1 - Publisher Copyright:
© 2016 ACM.
PY - 2016/7/5
Y1 - 2016/7/5
N2 - We study a class of generic optimization problems on charger scheduling and charging path planing. These problems arise from emerging networking applications where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, and vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We prove that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design a quasi-polynomial time algorithm that achieves poly-logarithmic approximation to the optimum charging path. Our approximation algorithm can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.
AB - We study a class of generic optimization problems on charger scheduling and charging path planing. These problems arise from emerging networking applications where mobile chargers are dispatched to deliver energy to mobile agents (e.g., robots, drones, and vehicles), which have specified tasks and mobility patterns. We instantiate our work by focusing on finding the charging path maximizing the number of nodes charged within a fixed time horizon. We prove that this problem is APX-hard. By recursively decomposing the problem into sub-problems of searching sub-paths, we design a quasi-polynomial time algorithm that achieves poly-logarithmic approximation to the optimum charging path. Our approximation algorithm can be further adapted and extended to solve a variety of charging path optimization and scheduling problems with realistic constraints, such as limited time and energy budget.
KW - Approximation algorithm
KW - Mobile charger scheduling
KW - Mobile wireless networks
UR - https://www.scopus.com/pages/publications/84979284394
U2 - 10.1145/2942358.2942364
DO - 10.1145/2942358.2942364
M3 - Conference contribution
AN - SCOPUS:84979284394
T3 - Proceedings of the International Symposium on Mobile Ad Hoc Networking and Computing (MobiHoc)
SP - 101
EP - 110
BT - MobiHoc 2016 - Proceedings of the 17th ACM International Symposium on Mobile Ad Hoc Networking and Computing
PB - Association for Computing Machinery
Y2 - 5 July 2016 through 8 July 2016
ER -