P3:Joint Optimization of Charger Placement and Power Allocation for Wireless Power Transfer Sheng Zhang',Zhuzhong Qian',Fanyu Kong',Jie Wu,and Sanglu Lu State Key Lab.for Novel Software Technology,Nanjing University,P.R.China +Department of Computer and Information Sciences,Temple University,USA Emails:(sheng.qzz,sanglu)@nju.edu.cn,kongfy @dislab.nju.edu.cn,jiewu@temple.edu Abstract-Wireless power transfer is a promising technology of candidate locations for placing wireless power chargers to extend the lifetime of,and thus enhance the usability of,the (chargers for short in the sequel).The power of each charger energy-hungry battery-powered devices.It enables energy to be wirelessly transmitted from power chargers to energy receiving is adjustable within an appropriate range.The maximum cover devices.Existing studies have mainly focused on maximizing distance of a charger is determined by its power and the network lifetime,optimizing charging efficiency,minimizing environment.The power received by a device from multiple charging delay,etc.Different from these works,our objective is chargers is assumed to be additive [9].Given a power budget, to optimize charging quality in a 2-D target area.Specifically,we the wireless charging service provider wants to maximize its consider the following charger Placement and Power allocation Problem (P3):Given a set of candidate locations for placing revenue,which is proportional to the charging quality defined chargers,find a charger placement and a corresponding power later in the paper.In order to maximize the charging quality,a allocation to maximize the charging quality,subject to a power limited number of chargers with appropriate power levels must budget.We prove that P3 is NP-complete.We first study P3 with be strategically placed at a subset of the candidate locations. fixed power levels,for which we propose a(1-1/e)-approximation This charger Placement and Power allocation Problem(P3) algorithm;we then design an approximation algorithm of factor L for p3,where e is the base of the natural logarithm,and can be briefly stated as follows:Given a set of candidate Ls the maximum power level of a charger.We also show how locations for placing chargers,how to find a charger place- to extend P3 in a cycle.Extensive simulations demonstrate that, ment and a corresponding power allocation to maximize the the gap between our design and the optimal algorithm is within charging quality,subject to a power budget.In this paper,we 4.5%,validating our theoretical results. prove that the P3 problem is NP-complete by reduction from Index Terms-Wireless power transfer,power allocation,sub- the set cover problem [13].To gain a better understanding,we modularity,approximation algorithm first consider the P3 problem with fixed power levels,where the power level of every candidate location is fixed,for which we I.INTRODUCTION propose a(1-1/e)-approximation algorithm.Then,based on We have witnessed the increasing potential of wireless the acquired insights,we design an approximation algorithm devices to improve the quality of our lives in the last few of factor for the p3 problem,where e is the base of the years.To extend the lifetime of,and thus enhance the usability natural logarithm,and L is the maximum power level. of,these battery-powered devices,solutions from different per- We also discuss an extension of p3.When the power spectives have been proposed,including energy harvesting [1],consumption rates of devices exhibit cyclic patterns,how energy conservation [2],and battery replacement [3].However, do we decide a subset of the candidate locations and cor- they remain limited due to various reasons. responding power levels for each time slot in a cycle?We Recent breakthroughs in wireless power transfer [4,5] show that solving this problem is not equivalent to solving provide a promising alternative that has attracted significant multiple consecutive p3 problems,and we propose a attention from both academia and industry.With this technol- approximation algorithm for this problem. ogy,energy can be wirelessly transmitted from power chargers The contributions of this paper are three-fold: to energy receiving devices such as RFID tags,sensors, To the best of our knowledge,we are the first to study the smartphones,and Tesla cars [6.Existing studies regarding this joint optimization of charger placement and power allo- issue have mainly focused on maximizing network lifetime [7], cation problem.We present a formal problem statement optimizing charging efficiency [8].energy provisioning [9]. and prove that the problem is NP-complete. collaboration between chargers [10],minimizing charging de- We develop two approximation algorithms for p3 with lay [11],minimizing maximum radiation point [12],etc. and without fixed power levels,respectively.Evaluations Different from existing works,we consider the following confirm the effectiveness of the proposed algorithms. scenario.A service provider decides to offer a wireless power We discuss how to extend p3 in a cycle and propose a charging service in an area of interest,e.g.,a campus or park. approximation algorithm for this problem. Based on historical data analysis and market investigation, The rest of the paper is organized as follows.We discuss it could predict the location information of future potential related work in Section II.We introduce the problem in customers (i.e.,devices)and then preselect a certain number Section III.We present our solution to P3 in Section IV.BeforeP 3 : Joint Optimization of Charger Placement and Power Allocation for Wireless Power Transfer Sheng Zhang† , Zhuzhong Qian† , Fanyu Kong† , Jie Wu‡ , and Sanglu Lu† †State Key Lab. for Novel Software Technology, Nanjing University, P.R. China ‡Department of Computer and Information Sciences, Temple University, USA Emails: {sheng,qzz,sanglu}@nju.edu.cn, kongfy@dislab.nju.edu.cn, jiewu@temple.edu Abstract—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 (P3 ): 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 P3 is NP-complete. We first study P3 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 P3 , 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 P3 in a cycle. Extensive simulations demonstrate that, the gap between our design and the optimal algorithm is within 4.5%, validating our theoretical results. Index Terms—Wireless power transfer, power allocation, sub￾modularity, approximation algorithm I. Introduction We have witnessed the increasing potential of wireless devices to improve the quality of our lives in the last few years. To extend the lifetime of, and thus enhance the usability of, these battery-powered devices, solutions from different per￾spectives have been proposed, including energy harvesting [1], energy conservation [2], and battery replacement [3]. However, they remain limited due to various reasons. Recent breakthroughs in wireless power transfer [4, 5] provide a promising alternative that has attracted significant attention from both academia and industry. With this technol￾ogy, energy can be wirelessly transmitted from power chargers to energy receiving devices such as RFID tags, sensors, smartphones, and Tesla cars [6]. Existing studies regarding this issue have mainly focused on maximizing network lifetime [7], optimizing charging efficiency [8], energy provisioning [9], collaboration between chargers [10], minimizing charging de￾lay [11], minimizing maximum radiation point [12], etc. Different from existing works, we consider the following scenario. A service provider decides to offer a wireless power charging service in an area of interest, e.g., a campus or park. Based on historical data analysis and market investigation, it could predict the location information of future potential customers (i.e., devices) and then preselect a certain number of candidate locations for placing wireless power chargers (chargers for short in the sequel). The power of each charger is adjustable within an appropriate range. The maximum cover distance of a charger is determined by its power and the environment. The power received by a device from multiple chargers is assumed to be additive [9]. Given a power budget, the wireless charging service provider wants to maximize its revenue, which is proportional to the charging quality defined later in the paper. In order to maximize the charging quality, a limited number of chargers with appropriate power levels must be strategically placed at a subset of the candidate locations. This charger Placement and Power allocation Problem (P3 ) can be briefly stated as follows: Given a set of candidate locations for placing chargers, how to find a charger place￾ment and a corresponding power allocation to maximize the charging quality, subject to a power budget. In this paper, we prove that the P3 problem is NP-complete by reduction from the set cover problem [13]. To gain a better understanding, we first consider the P3 problem with fixed power levels, where the power level of every candidate location is fixed, for which we propose a (1 − 1/e)-approximation algorithm. Then, based on the acquired insights, we design an approximation algorithm of factor 1−1/e 2L for the P3 problem, where e is the base of the natural logarithm, and L is the maximum power level. We also discuss an extension of P3 . When the power consumption rates of devices exhibit cyclic patterns, how do we decide a subset of the candidate locations and cor￾responding power levels for each time slot in a cycle? We show that solving this problem is not equivalent to solving multiple consecutive P3 problems, and we propose a 1−1/e 2L - approximation algorithm for this problem. The contributions of this paper are three-fold: • To the best of our knowledge, we are the first to study the joint optimization of charger placement and power allo￾cation problem. We present a formal problem statement and prove that the problem is NP-complete. • We develop two approximation algorithms for P3 with and without fixed power levels, respectively. Evaluations confirm the effectiveness of the proposed algorithms. • We discuss how to extend P3 in a cycle and propose a 1−1/e 2L -approximation algorithm for this problem. The rest of the paper is organized as follows. We discuss related work in Section II. We introduce the problem in Section III. We present our solution to P3 in Section IV. Before