Several recent works have studied mobile charging under the “one-to-many” charging pattern where a single charger can charge multiple devices simultaneously. However, most of them focus on path planning and charging time allocation, but overlook the underlying dependence of the charging efficiency on initial deployment positions of chargers. This paper studies the problem of P lacing directional w I reless chargers with L imited m O bili T y (PILOT), that is, maximize the overall charging utility for a set of static rechargeable devices on a 2D plane by determining deployment positions, stop positions and orientations, and portions of time for all deployed chargers that can move in a limited area after their deployment. To the best of our knowledge, we are the first to study placement of mobile directional chargers under the “one-to-many” pattern. To address PILOT, we propose a

$(\frac{1}{2}-\epsilon)$

-approximation algorithm. First, we present a method to approximate nonlinear charging power of chargers, and further propose an approach to construct Maximal Covered Set uniform subareas to reduce the infinite continuous search space for stop positions and orientations to a finite discrete one. Second, we present geometrical techniques to further reduce the infinite solution space for candidate deployment positions to a finite one without performance loss, and transform PILOT to a mixed integer nonlinear programming problem. Finally, we propose a linear programming based greedy algorithm to address it. Simulation and experimental results show that our algorithm outperforms six comparison algorithms by

$19.74 \% \sim 500.01 \%$

Xuzhen Lin

Publications