Charging Task Scheduling for Directional Wireless Charger Networks
Charging Task Scheduling for Directional Wireless Charger Networks
复制标题
DOI：
10.1145/3225058.3225080
复制
发表时间：
2018-08
影响因子：
7.9
通讯作者：
Haipeng Dai;K. Sun;A. Liu;Lijun Zhang;Jiaqi Zheng;Guihai Chen
中科院分区：
文献类型：
--
作者：
Haipeng Dai;K. Sun;A. Liu;Lijun Zhang;Jiaqi Zheng;Guihai Chen
本文研究了定向无线充电网络的充电任务调度问题，即：给定2D区域上的一组可旋转定向无线充电器和一系列离线（在线）充电任务，以集中式离线（分布式在线）方式随时间调度所有充电器的取向，以最大化所有任务的总体充电效用。我们证明了HASTE是NP难的。然后，我们证明了HASTE的放松版本福尔斯属于最大化受分区拟阵约束的子模函数的领域，并提出了一种集中式离线算法，可实现$（1-\rho）（1-\frac{1}{e}）$（1-ρ）（1- 1 e）逼近比来解决HASTE，其中$\rho$ρ是充电器的开关延迟。进一步，我们提出了一个分布式在线算法，并证明了它达到了$\frac{1}{2}（1-\rho）（1-\frac{1}{e}）$12（1-ρ）（1- 1 e）的竞争比。我们进行模拟和现场实验的测试平台，包括8个现成的功率发射器和8个可充电的传感器节点。结果表明，我们的分布式在线算法实现了92.97%的最优充电效用，并优于比较算法高达15.28%的充电效用。
This paper studies the problem of cHarging tAsk Scheduling for direcTional wireless chargEr 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 $(1-\rho)(1-\frac{1}{e})$(1-ρ)(1-1e) approximation ratio to address HASTE where $\rho$ρ is the switching delay of chargers. Further, we propose a distributed online algorithm and prove it achieves $\frac{1}{2}(1-\rho)(1-\frac{1}{e})$12(1-ρ)(1-1e) 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.