P3: Joint optimization of charger placement and power allocation for wireless power transfer

Wireless power transfer is a promising technology to extend the lifetime of, and thus enhance the usability of, the energy-hungry battery-powered devices. It enables energy to be wirelessly transmitted from power chargers to energy receiving devices. Existing studies have mainly focused on maximizing network lifetime, optimizing charging efficiency, minimizing charging delay, etc. Different from these works, our objective is to optimize charging quality in a 2-D target area. Specifically, we consider the following charger Placement and Power allocation Problem (P³): Given a set of candidate locations for placing chargers, find a charger placement and a corresponding power allocation to maximize the charging quality, subject to a power budget. We prove that P³ is NP-complete. We first study P³ with fixed power levels, for which we propose a (1-1/e)-approximation algorithm; we then design an approximation algorithm of factor 1-1/e / 2L for P³, where e is the base of the natural logarithm, and L is the maximum power level of a charger. We also show how to extend P³ in a cycle. Extensive simulations demonstrate that, the gap between our design and the optimal algorithm is within 4.5%, validating our theoretical results.