Hybrid Heterogeneous Wireless Chargers Placement
摘要
This paper presents the first study on the problem of Hybrid heterogeneous wireless chARgers Placement (HARP), i.e., given a number of heterogeneous deployed rechargeable devices, determining deployment positions for multiple heterogeneous stationary chargers with a given cardinality of each type and partial selected devices with energy allocation for multiple mobile chargers to maximize the overall charging utility. The HARP problem is essentially NP-hard and non-submodular, which poses huge challenges. We first propose an approach to approximate the nonlinear charging power and partition the whole area into multi-power constant subareas, after that, we present a charging discretization method and construct a mapping function over the selected device set to transform the problem of deploying a single mobile charger into maximizing a monotone submodular function subject to a general routing constraint. It allows us to propose a benefit-cost ratio algorithm to solve it. Finally, we propose an efficient approximation algorithm that achieves \(\frac{1-1/e}{5-1/e}\) -approximation ratio to address HARP. We conducted extensive simulations and field experiments verifying that our algorithm outperforms the comparison algorithms by at least \(17.49\%\) on average.