Practical Heterogeneous Wireless Charger Placement with Obstacles

摘要

This paper considers the problem of practical Heterogeneous wireless charger Placement with Obstacles (HIPO), i.e., given a number of heterogeneous rechargeable devices distributed on a 2D plane where obstacles of arbitrary shapes exist, deploying heterogeneous chargers with a given cardinality of each type, i.e., determining their positions and orientations, the combination of which we name as strategies, on the plane such that the rechargeable devices achieve maximized charging utility. After presenting our practical directional charging model, we first propose to use a piecewise constant function to approximate the nonlinear charging power, and divide the whole area into multi-feasible geometric areas in which a certain type of chargers have constant approximated charging power. Next, we propose the Practical Dominating Coverage Set extraction algorithm to reduce the unlimited solution space to a limited one by exacting a finite set of candidate strategies for all multi-feasible geometric areas. Finally, we prove the problem falls in the realm of maximizing a monotone submodular function subject to a partition matroid constraint, which allows a greedy algorithm to solve with approximation ratio of 1/2 - epsilon. We conduct experiments to evaluate the performance. Results show that our algorithm outperforms the comparison algorithms by at least 33.49 percent on average.