Charging Task Scheduling for Directional Wireless Charger Networks
Haipeng Dai, Ke Sun, Alex X. Liu, Lijun Zhang, Jiaqi Zheng, Guihai Chen
Abstract
This paper studies the problem of c <u>H</u> arging t <u>A</u> sk <u>S</u> cheduling for direc <u>T</u> ional wireless charg <u>E</u> r networks (HASTE), i.e., given a set of rotatable directional wireless chargers on a 2D area and a series of offline (online) charging tasks, scheduling the orientations of all the chargers with time in a centralized offline (distributed online) fashion to maximize the overall charging utility for all the tasks. We prove that HASTE is NP-hard. Then, we prove that a relaxed version of HASTE falls within the realm of maximizing a submodular function subject to a partition matroid constraint, and propose a centralized offline algorithm that achieves <inline-formula><tex-math notation="LaTeX">$(1-\rho)(1-\frac{1}{e})$</tex-math></inline-formula> approximation ratio to address HASTE where <inline-formula><tex-math notation="LaTeX">$\rho$</tex-math></inline-formula> is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves <inline-formula><tex-math notation="LaTeX">$\frac{1}{2}(1-\rho)(1-\frac{1}{e})$</tex-math></inline-formula> competitive ratio. We conduct simulations and field experiments on a testbed consisting of eight off-the-shelf power transmitters and 8 rechargeable sensor nodes. The results show that our distributed online algorithm achieves 92.97 percent of the optimal charging utility, and outperforms the comparison algorithms by up to 15.28 percent in terms of charging utility.