Statistics

Programming language

Engineering

Approximation algorithm

Power (physics)

Set (abstract data type)

Range (aeronautics)

Geometry

Constraint (computer-aided design)

Wireless power transfer

Greedy algorithm

Telecommunications

Set cover problem

Physics

Aerospace engineering

Submodular set function

Mathematics

Wireless

Mathematical optimization

Quantum mechanics

Computer science

Matroid

Algorithm

Monotone polygon

Discrete mathematics

Plot (graphics)

IEEE/ACM Transactions on Networking

Wireless power transfer technology has witnessed huge development because of its convenience and reliability. This paper concerns the fundamental issue of wireless charger PLacement with Optimized charging uTility (PLOT), i.e., given a fixed number of chargers and a set of points where rechargeable devices can be placed with orientations uniformly distributed in the range of [0, 2π) positions and orientations of chargers such that the overall expected charging utility for all points is maximized. To address PLOT, we propose a 1 - 1/ε - ε approximation algorithm. First, we present techniques to approximate the nonlinear charging power and the expected charging utility to make the problem almost linear. Second, we develop a dominating coverage set extraction method to reduce the continuous search space of PLOT to a limited and discrete one without a performance loss. Third, we prove that the reformulated problem is essentially maximizing a monotone submodular function subject to a matroid constraint, and propose a greedy algorithm to address this problem. We conduct both simulation and field experiments to validate our theoretical results, and the results show that our algorithm can outperform comparison algorithms by at least 32.9%.

Wireless Charger Placement for Directional Charging