计算机科学与技术（参考文献）P3 - Joint Optimization of Charger Placement and Power Allocation for Wireless Power Transfer

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.Before

P 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

we conclude the paper in Section VI,we evaluate our design in Section V】 II.RELATED WORK S2 S2 S, 83 C Kurs et al.experimentally demonstrated that energy can be efficiently transmitted between magnetically resonant objects kD(1) D(2) without any interconnecting conductors [4].Intel develope- d the wireless identification and sensing platform (WISP) for battery-free programmable monitoring [14].Motivated by Fig.1:Illustration of basic concepts.The maximum cover distance of a power these enabling technologies,most of prior studies envisioned level is indicated by the radius of a dashed circle.If we set C'=[ei.c2)and H=(2,2).we have pc(s1)=p(c1.s1)+p(c2.51),and pc(s3)=p(c2,53). employing mobile vehicles equipped with wireless chargers to deliver energy to sensor nodes. Peng et al.optimized the charging sequence for network B.Charging Model lifetime maximization [7].Li et al.proposed routing and charging strategies for the same objective [15].Shi et al. We assume that the power of each charger is adjustable. investigated the problem of periodically charging sensors to Each charger can be operated at L different power levels.De- maximize the ratio of the charger's vacation time (time spent note the power of charger ci by pi;without loss of generality, we define: at the home service station)over the cycle time [8,16].Tong et al.evaluated the performance of multi-node simultaneous p:=ph;)=h:…Pmin charging [17].To minimize the total charging delay,Fu et al.proposed an approx.algorithm for determining the mobile where hie(1,2,...,L]is the power level of ci,and pmin charger stop locations and the corresponding stop durations via is the minimum power of a charger.Note that,this kind of discretizing charging power [11].He et al.[9]investigated the discretization is for simplicity:in fact,as long as the number of energy provision problem of finding the minimum number of allowable power levels of each charger is limited,the proposed solutions are still valid.A power allocation can be denoted by RFID readers to cover a given network.Wang et al.designed efficient energy monitoring and reporting protocols based on a vector H=(h1,h2,...,hN). NDN-related mechanisms [18].Zhang et al.leveraged col- According to the profiling experiments in [9],the power laboration between mobile chargers to optimize energy usage p(ci,sj)received by device sj from charger ci can be quantified effectiveness [10,19].Dai et al.proposed a near optimal solu- by an empirical model as follows: tion for determining the maximum electromagnetic radiation (d(c.s)B p(hi) d(ci,sj）≤Dh) point in a given plane [12].Different from them,our work p(Ci,si)= (1) jointly determines charger placement and power allocation to 0 d(ci,sj)>D(hi) improve the charging quality,subject to a budget constraint. where a and B are know constants determined by hardware III.PROBLEM FORMULATION of chargers and devices and the environment,and D(hi)is the maximum cover distance of a charger with power level hi. A.Network Model When a device is far away from a charger,the device would receive negligible power that cannot be rectified to useful We consider a set of M stationary rechargeable devices electrical energy.The threshold of this negligible power is S=(s1,s2,..sM)distributed in a two-dimensional plane.The preselected candidate locations for placing stationary wireless denoted by prh.By letting power chargers is denoted by a set C=fc1.c2....cN).We also use ci to denote the charger placed at a candidate location ci (D(h+B(hi)=Ph. if no confusion is caused.A charger placement is denoted by we have C',which is a subset of C. The location of a device s;can be localized using techniques D(hi)= -p(hi)-B (2) in [20]and represented as (x[si],y[sil).The location of ci is (x[ci],y[cil).The distance function d (CS,CUS)R That is,given constants a,B,and pth,the maximum cover- gives the Euclidean distance between two objects(chargers or age radius of a charger ci is determined by its power pi p(hi). devices),e.g.,the distance between charger ci and device sj In Fig.1,when we place a charger ci with a power level h is defined as being 1,its maximum coverage radius is D(1),and thus ci cannot transfer power to s,which is more than D(1)distance d(ci,sj)=(x[ci]-x[sjl+(y[ci]-y[sjl)2 away from ci. As evidenced by [17],a charger can transfer energy to Fig.I is an illustration of some basic concepts.There are multiple devices simultaneously without significantly reducing 2 candidate locations and 3 devices in the example. the received power at one device

we conclude the paper in Section VI, we evaluate our design in Section V. II. Related Work Kurs et al. experimentally demonstrated that energy can be efficiently transmitted between magnetically resonant objects without any interconnecting conductors [4]. Intel develope￾d the wireless identification and sensing platform (WISP) for battery-free programmable monitoring [14]. Motivated by these enabling technologies, most of prior studies envisioned employing mobile vehicles equipped with wireless chargers to deliver energy to sensor nodes. Peng et al. optimized the charging sequence for network lifetime maximization [7]. Li et al. proposed routing and charging strategies for the same objective [15]. Shi et al. investigated the problem of periodically charging sensors to maximize the ratio of the charger’s vacation time (time spent at the home service station) over the cycle time [8, 16]. Tong et al. evaluated the performance of multi-node simultaneous charging [17]. To minimize the total charging delay, Fu et al. proposed an approx. algorithm for determining the mobile charger stop locations and the corresponding stop durations via discretizing charging power [11]. He et al. [9] investigated the energy provision problem of finding the minimum number of RFID readers to cover a given network. Wang et al. designed efficient energy monitoring and reporting protocols based on NDN-related mechanisms [18]. Zhang et al. leveraged col￾laboration between mobile chargers to optimize energy usage effectiveness [10, 19]. Dai et al. proposed a near optimal solu￾tion for determining the maximum electromagnetic radiation point in a given plane [12]. Different from them, our work jointly determines charger placement and power allocation to improve the charging quality, subject to a budget constraint. III. Problem Formulation A. Network Model We consider a set of M stationary rechargeable devices S = {s1, s2, ..., sM} distributed in a two-dimensional plane. The preselected candidate locations for placing stationary wireless power chargers is denoted by a set C = {c1, c2, ..., cN}. We also use ci to denote the charger placed at a candidate location ci if no confusion is caused. A charger placement is denoted by C ′ , which is a subset of C. The location of a device sj can be localized using techniques in [20] and represented as (x[sj], y[sj]). The location of ci is (x[ci], y[ci]). The distance function d : (C ∪ S, C ∪ S) → R gives the Euclidean distance between two objects (chargers or devices), e.g., the distance between charger ci and device sj is defined as d(ci , sj) = √ (x[ci] − x[sj])2 + (y[ci] − y[sj])2 . Fig. 1 is an illustration of some basic concepts. There are 2 candidate locations and 3 devices in the example. c1 s1 s2 c2 D(1) D(2) s3 Fig. 1: Illustration of basic concepts. The maximum cover distance of a power level is indicated by the radius of a dashed circle. If we set C ′ = {c1, c2} and H = (2, 2), we have pC′ (s1) = p(c1, s1) + p(c2, s1), and pC′ (s3) = p(c2, s3). B. Charging Model We assume that the power of each charger is adjustable. Each charger can be operated at L different power levels. De￾note the power of charger ci by pi ; without loss of generality, we define: pi = p(hi) = hi · pmin where hi ∈ {1, 2, ..., L} is the power level of ci , and pmin is the minimum power of a charger. Note that, this kind of discretization is for simplicity; in fact, as long as the number of allowable power levels of each charger is limited, the proposed solutions are still valid. A power allocation can be denoted by a vector H = (h1, h2, ..., hN). According to the profiling experiments in [9], the power p(ci , sj) received by device sj from charger ci can be quantified by an empirical model as follows: p(ci , sj) =    α (d(ci ,sj)+β) 2 p(hi) d(ci , sj) ≤ D(hi) 0 d(ci , sj) > D(hi) (1) where α and β are know constants determined by hardware of chargers and devices and the environment, and D(hi) is the maximum cover distance of a charger with power level hi . When a device is far away from a charger, the device would receive negligible power that cannot be rectified to useful electrical energy. The threshold of this negligible power is denoted by pth. By letting α (D(hi) + β) 2 p(hi) = pth, we have D(hi) = √ α pth p(hi) − β. (2) That is, given constants α, β, and pth, the maximum cover￾age radius of a charger ci is determined by its power pi = p(hi). In Fig. 1, when we place a charger c1 with a power level h1 being 1, its maximum coverage radius is D(1), and thus c1 cannot transfer power to s1, which is more than D(1) distance away from c1. As evidenced by [17], a charger can transfer energy to multiple devices simultaneously without significantly reducing the received power at one device

Symbol Meaning Hardness the number of candidate locations P3 with fixed the set of candidate locations analysis power levels C a charger placement,i.e.,a subset of C Ci a candidate location or a charger P the power of charger ci P3 in a cyde hi the power level of charger c Pth the threshold of negligible power Fig.3:Flowchart of our solution Pmin the minimum power of a charger L the maximum power level of a charger D(hi) the maximum coverage radius with respect to h; H■ a power allocation,i.e.,(hi,h2,...,hN) IV.SOLUTION TO P3 M the number of stationary devices Fig.3 shows the flowchart of our solution.In this section, S the set of stationary devices Si an energy consuming device we first show that p3 is NP-complete,then we propose Pi the maximum power consumption rate of device sj an approximation algorithm for a simplified case of the p3 B the power budget problem,where the power level of each candidate location is d(c.s)the distance between charger ci and device s; fixed,and finally we present aapproximation algorithm p(Ci,si) the power received by device s;from charger ci for the p3 problem.We also discuss an extension of p3 and Pc(si) the total power received by si with respect to C Qo(si) the charging quality of C on device s, propose a provably good solution to it. Q(C.H)the charging quality with respect to C'and H A.Hardness Analysis Fig.2:Main notations for quick reference. Theorem 1:The p3 problem is NP-complete Proof:We prove this theorem by reduction from the Set We assume the power received by one device from multiple Cover problem(SC)[13].which is NP-complete.The decision chargers is additive [9].That is,given a charger placement C', version of the SC problem is as follows:Given a universe the total power pc(s;)received by device s;is u=le1,e2,m of m elements and an integer y,a collection of subsets of u.R =[R1.R2,....Rl,does there exist a sub- pe(s)=∑ptG,s (3) collection of R of size y that covers all elements of w? CIEC Given an instance of the decision version of the SC problem. we construct an instance of the P3 problem as follows.We let For example,in Fig.1,if we set C=(c1,c2)and H=(2,2),L=1,i.e.,every charger can only operated at the fixed power we have pc(s1)=p(c1,51)+p(c2,51),Pc(s2)=p(c1,52),and Pmin.For each element ej in u,we construct a device sj Pc(s3)=p(c2,53). in p3.We assume that all devices have the same maximum power consumption rate,i.e.,P1=P2 =...,=Pm =P.For C.Problem Definition each RER,we add a candidate location c;to P3.For each element ej in Ri,we move sj into the coverage of ci.We also The maximum power consumption rate of device s;is make sure that,as long as a device s;is within the coverage represented by Pj.If the total power pc(sj)received by device of a location ci,p(ci,sj)>P;this can be achieved by setting sj is larger than Pj.the over-received power,i.e.,pc(sj)-Pj. Pmin to a sufficiently large value. would be useless.Therefore,we define the charging quality Combining these together,we get the following special case Qc(sj)of C'on device sj as: of the decision version of the P3 problem:Given a candidate location set C of size k.and a device set S of size m,does Qc(s）=minlPc(s,Pl (4) there exist a charger placement Cof sizesuch that QC,(1,1,,1)≥mP? Main notations are summarized in Fig.2 for quick reference. It is not hard to see that the construction can be finished in We define our objective function as follows: polynomial time;thus,we reduce solving the NP-complete SC Definition I:(Charging Quality)Given a charger place-problem to solving a special case of the P3 problem,implying ment C'and a power allocation H,the charging quality,denot- that p3 is NP-hard.It is easy to verify that P3 is in NP;the ed as (C',H),is defined as the sum of the charging qualities theorem follows immediately. ■ of C'and H on all devices,i.e..(C'.H)=c(sj) The main problem studied in this paper is: B.Approximation Algorithm for p3 with Fixed Power Levels Problem 1:(Charger Placement and Power Allocation In this subsection,we study the p3 problem where the Problem,P3)Given a set C of candidate locations,a set S charger at each location can only work at a fixed power of devices,and a power budget B.p3 is to find a charger level,ie..h is constant for all candidate locations.The placement C'and a power allocation H to maximize Q(C',H), approximation algorithms designed here will serve as basics subject to the power budget constraint,ie..Ec Pis B. of the algorithm for p3 proposed in the next subsection

Symbol Meaning N the number of candidate locations C the set of candidate locations C ′ a charger placement, i.e., a subset of C ci a candidate location or a charger pi the power of charger ci hi the power level of charger ci pth the threshold of negligible power pmin the minimum power of a charger L the maximum power level of a charger D(hi) the maximum coverage radius with respect to hi H a power allocation, i.e., (h1, h2, ..., hN) M the number of stationary devices S the set of stationary devices sj an energy consuming device Pj the maximum power consumption rate of device sj B the power budget d(ci , sj) the distance between charger ci and device sj p(ci , sj) the power received by device sj from charger ci pC′ (sj) the total power received by sj with respect to C ′ QC′ (sj) the charging quality of C ′ on device sj Q(C ′ , H) the charging quality with respect to C ′ and H Fig. 2: Main notations for quick reference. We assume the power received by one device from multiple chargers is additive [9]. That is, given a charger placement C ′ , the total power pC′ (sj) received by device sj is pC′ (sj) = ∑ ci∈C′ p(ci , sj). (3) For example, in Fig. 1, if we set C ′ = {c1, c2} and H = (2, 2), we have pC′ (s1) = p(c1, s1)+ p(c2, s1), pC′ (s2) = p(c1, s2), and pC′ (s3) = p(c2, s3). C. Problem Definition The maximum power consumption rate of device sj is represented by Pj . If the total power pC′ (sj) received by device sj is larger than Pj , the over-received power, i.e., pC′ (sj)− Pj , would be useless. Therefore, we define the charging quality QC′ (sj) of C ′ on device sj as: QC′ (sj) = min{pC′ (sj), Pj}. (4) Main notations are summarized in Fig. 2 for quick reference. We define our objective function as follows: Definition 1: (Charging Quality) Given a charger place￾ment C ′ and a power allocation H, the charging quality, denot￾ed as Q(C ′ , H), is defined as the sum of the charging qualities of C ′ and H on all devices, i.e., Q(C ′ , H) = ∑M j=1 QC′ (sj) The main problem studied in this paper is: Problem 1: (Charger Placement and Power Allocation Problem, P3 ) Given a set C of candidate locations, a set S of devices, and a power budget B, P3 is to find a charger placement C ′ and a power allocation H to maximize Q(C ′ , H), subject to the power budget constraint, i.e., ∑ ci∈C′ pi ≤ B. P 3 with fixed power levels P 3 Hardness analysis P 3 in a cycle Fig. 3: Flowchart of our solution. IV. Solution to P 3 Fig. 3 shows the flowchart of our solution. In this section, we first show that P3 is NP-complete, then we propose an approximation algorithm for a simplified case of the P3 problem, where the power level of each candidate location is fixed, and finally we present a 1−1/e 2L -approximation algorithm for the P3 problem. We also discuss an extension of P3 and propose a provably good solution to it. A. Hardness Analysis Theorem 1: The P3 problem is NP-complete. Proof: We prove this theorem by reduction from the Set Cover problem (SC) [13], which is NP-complete. The decision version of the SC problem is as follows: Given a universe U = {e1, e2, ..., em} of m elements and an integer y, a collection of subsets of U, R = {R1,R2, ...,Rk}, does there exist a sub￾collection of R of size y that covers all elements of U? Given an instance of the decision version of the SC problem, we construct an instance of the P3 problem as follows. We let L = 1, i.e., every charger can only operated at the fixed power pmin. For each element ej in U, we construct a device sj in P3 . We assume that all devices have the same maximum power consumption rate, i.e., P1 = P2 = ..., = Pm = P. For each Ri ∈ R, we add a candidate location ci to P3 . For each element ej in Ri , we move sj into the coverage of ci . We also make sure that, as long as a device sj is within the coverage of a location ci , p(ci , sj) ≥ P; this can be achieved by setting pmin to a sufficiently large value. Combining these together, we get the following special case of the decision version of the P3 problem: Given a candidate location set C of size k, and a device set S of size m, does there exist a charger placement C ′ of size ⌊ B pmin ⌋, such that Q(C ′ , (1, 1, ..., 1)) ≥ mP? It is not hard to see that the construction can be finished in polynomial time; thus, we reduce solving the NP-complete SC problem to solving a special case of the P3 problem, implying that P3 is NP-hard. It is easy to verify that P3 is in NP; the theorem follows immediately. B. Approximation Algorithm for P3 with Fixed Power Levels In this subsection, we study the P3 problem where the charger at each location can only work at a fixed power level, i.e., hi is constant for all candidate locations. The approximation algorithms designed here will serve as basics of the algorithm for P3 proposed in the next subsection

Algorithm 1 The Greedy Placement Algorithm(GPA) Input:C,S,B,and p Output:C C 8N-1 1:C←0 N-1 S1 2:while C1Pj-Pc(s）=Qcue(s）-Qc(sj ularity)Given a non-empty finite set and a function f IfPi-Pc(s）≤pc,s),then defined on the power set 2u of U with real values,f is called nonnegative if f(列）≥0 for all Acu;f is called monotone Q(cuten(sj)-Qc(sj)=Pj-Pc(sj) if f(A)Q(C"U(cl)-Q(C").It maximizes the marginal gain.It takes O(MN)time to compute is sufficient to show that for any sieS,we have (C),thus,the time complexity of Alg.1 is O(MN3). Qcue(s）-Qc(s）≥Qicrule(s）-Qc(sj: 2)Non-uniform Case:We then study the non-uniform case of power levels,in this case,P3 can be reformulated as follows: Based on Equ.(3)and Equ.(4),we prove the above inequation Given a set C of candidate locations,a set S of devices,a in three cases: power budget B,and a power allocation H=(h,h2....,hN). ·Pj≤Pc(si:since Pc(si)≥Pc(sid,we have p3 is to find a charger placement C'to maximize (C).subject Qcuc(s）-Qc(s）=0=Qcuc(s）-Qc(s. to the budget constraint,.ie,∑c,ecpi≤B. To solve this problem,an intuitive method is using the same ·Pc(si）<P)j<Pc(sl:in this case,Qicule(s）- greedy idea as in Equ.(5).However,we show in Fig.4(a)that, Oc"(sj)=0,and we have this method may perform very bad.In Fig.4(a),there are N=L+1 candidate locations and M=N devices:h=h2= Qcue(si）-Qc(si) ...hN-1=1,and hN =L;the radii of dashed circles indicate =min(P,-Pc(si,Pcuc(si）-Pc(s》 the maximum coverage distance of each charger;p(c1,s)= =min(P,-Pc(spc,s》 p(c2,52)=...=p(cN-1,SN-1)=p(cN,SN)-E,where e satisfies 20=Qc"uen(si）-Qc(s 0<E<p(CN,SN).Given a power budget B =L.Pmin,using

Algorithm 1 The Greedy Placement Algorithm (GPA) Input: C, S, B, and p Output: C ′ 1: C ′ ← ∅ 2: while |C′ | Pj − PC′′ (sj) = Q(C′′∪{c})(sj) − QC′′ (sj). If Pj − PC′ (sj) ≤ p(c, sj), then Q(C′∪{c})(sj) − QC′ (sj) = Pj − PC′ (sj) ≥ Pj − PC′′ (sj) = Q(C′′∪{c})(sj) − QC′′ (sj). Therefore, we proved that Q(C ′ ) is submodular. According to the results in [21, 22], we have a (1 − 1/e)- approx. algorithm shown in Alg. 1, which starts with an empty set C ′ , in each iteration, we add the location that maximizes the marginal gain of the objective function into C ′ , i.e., c ← arg max c∈C\C′ (Q(C ′ ∪ {c}) − Q(C ′ )). (5) There are at most N iterations in Alg. 1; in each iteration, we need to check at most N locations to find the location that maximizes the marginal gain. It takes O(MN) time to compute Q(C ′ ), thus, the time complexity of Alg. 1 is O(MN3 ). 2) Non-uniform Case: We then study the non-uniform case of power levels, in this case, P3 can be reformulated as follows: Given a set C of candidate locations, a set S of devices, a power budget B, and a power allocation H = (h1, h2, ..., hN), P 3 is to find a charger placement C ′ to maximize Q(C ′ ), subject to the budget constraint, i.e., ∑ ci∈C′ pi ≤ B. To solve this problem, an intuitive method is using the same greedy idea as in Equ. (5). However, we show in Fig. 4(a) that, this method may perform very bad. In Fig. 4(a), there are N = L + 1 candidate locations and M = N devices; h1 = h2 = ... = hN−1 = 1, and hN = L; the radii of dashed circles indicate the maximum coverage distance of each charger; p(c1, s1) = p(c2, s2) = ... = p(cN−1, sN−1) = p(cN, sN)−ϵ, where ϵ satisfies 0 < ϵ < p(cN, sN). Given a power budget B = L · pmin, using

Algorithm 2 Approx.Alg.for P3 with Known Power Levels Algorithm 3 Two-Choice-based Approx.Alg.for P3 (TCA) Input:C,S,B,and H Input:C,S,and B Output:C' Output:C'and H 1:C1←-0，C2←-0 1:Z←-CxH 2:while B≥∑p;+minp:do 2:Z1←0，H1←-0 CrECI CIEC\CI c←arg max (Q(CI U Ic])-2(C1)) 3:while B≥min p(he)+∑_p(h)do EC\C,2Capm≤B (cih)EZ\Z (chE乙1 C1←-C1U{c} 4: 4 (C,）←arg (che-Ze2 P(h) max 5:end while (ZIU((c,h)))-Q(Zi) 6:while B≥Σpi+minp:do 5: Z1←-乙1U{(c,h)} CIEC2 GEC\C, 6: ifH[c]0 do perform badly.In Fig.4(b),there are 2 candidate locations and 23: C'←CU{ch,B←-B+pHcl) M=L+1 devices;h 1,and h2 L;p(c1.s1)=p(c2.S2)= 24:end for p(c2,53)...p(c2,SM-1)=p(c2,SM)+E,where E satisfies 25:while B-B≥Pmin do 0Dhk. power level of a candidate location ci. Before giving some explanations about TCA,we first con- Correspondingly,given a charger placement Z,the to- sider the following variant of the P3 problem (VP3):For each tal power pz(sj)received by device sj is pz(sj)= candidate location ci.we are given L chargers with constant X(ehez p(ci.sj.hk).The charging quality of Z'on sj is but exactly different power levels,i.e.,the power levels of these Qz(s）=min(pz(sj,Ph (8)

Algorithm 2 Approx. Alg. for P3 with Known Power Levels Input: C, S, B, and H Output: C ′ 1: C1 ← ∅, C2 ← ∅ 2: while B ≥ ∑ ci∈C1 pi + min ci∈C\C1 pi do 3: c ← arg max c∈C\C1, ∑ ci ∈C1∪{c} pi≤B (Q(C1 ∪ {c}) − Q(C1)) 4: C1 ← C1 ∪ {c} 5: end while 6: while B ≥ ∑ ci∈C2 pi + min ci∈C\C2 pi do 7: cx ← arg max cx∈C\C2, ∑ ci ∈C2∪{cx} pi≤B Q(C2∪{cx})−Q(C2) px 8: C2 ← C2 ∪ {cx} 9: end while 10: return arg max C′∈{C1,C2} Q(C ′ ) Equ. (5), the charger cN would be picked. However, if we pick c1, c2, ..., and cN−1, the charging quality would be L · p(c1, s1) instead of p(c1, s1) + ϵ. When ϵ is approaching zero, using Equ. (5) would generate approximately 1/L of the charging quality returned by the optimal solution. Another intuitive method is that, in each iteration, we pick the location that maximize the marginal ratio of objective gain to power cost, i.e., cx ← arg max cx∈C\C′ , ∑ ci ∈C′∪{cx} pi≤B Q(C ′ ∪ {cx}) − Q(C ′ ) px . (6) However, we show in Fig. 4(b) that, this method may also perform badly. In Fig. 4(b), there are 2 candidate locations and M = L + 1 devices; h1 = 1, and h2 = L; p(c1, s1) = p(c2, s2) = p(c2, s3)... = p(c2, sM−1) = p(c2, sM) + ϵ, where ϵ satisfies 0 0 do 23: C ′ ← C′ ∪ {ci}, B ′ ← B ′ + p(H[ci]) 24: end for 25: while B − B ′ ≥ pmin do 26: ci ← arg max H[ci]+1≤L Q(C ′ ∪ {ci}, H + Ii) − Q(C ′ , H) 27: C ′ ← C′ ∪ {ci}, H[ci] ← H[ci] + 1, B ′ ← B ′ + pmin 28: end while 29: return (C ′ , H) chargers are 1, 2, ..., and L. We use (ci , hk) to denote the charger of a constant power level hk that can only be placed at ci . Note that there are, in total, N·L chargers. Given a power budget B, how do we find a charger placement that maximize the objective function defined below? Let Z be the Cartesian product of C and H; denote by Z′ a subset of Z. We redefine several functions for the VP3 problem via overloading. The power p(ci , sj , hk) received by device sj from ci (its power level is hk) is p(ci , sj , hk) =    α (d(ci ,sj)+β) 2 p(hk) d(ci , sj) ≤ D(hk), 0 d(ci , sj) > D(hk). (7) Correspondingly, given a charger placement Z′ , the to￾tal power pZ′ (sj) received by device sj is pZ′ (sj) = ∑ (ci ,hk )∈Z′ p(ci , sj , hk). The charging quality of Z′ on sj is QZ′ (sj) = min{pZ′ (sj), Pj}. (8)

The objective function is M Q(Z')= Qz (sj). The main idea of TCA is as follows.We use the two C3 greedy heuristics (i.e.,Equ.(5)and Equ.(6))to solve the VP3 problem defined above,and get two results Z1 and Z2. respectively.Note that,there may be more than one charger placed at a candidate location in Zi or Z2.We then invoke the RemoveDuplicationAndUtilize sub-procedure to transform Fig.5:There are 3 candidate locations and 2 devices.The radii of dashed circles show the maximum cover distances of four different power levels. ZI and Z2 into two solutions to p3,respectively. The transformation works as follows (take ZI for example): For each location ci,we set Hi[ci]to be the maximum value of (resp.C and H2),for each location,we retain the charger hg among all (ci,hg)EZ1,i.e.,Hi[ci]max(ehez hg (line that has the largest power level,if any.Therefore,we have 6 of Alg.3).For each location ci,if Hi[ci]>0,we add it into C.which is equivalent to C=(cil(ci,h)EZi)(lines 22-24). As Alg.3 shows,we retain only one charger for each location Qc,≥，dQc≥2 L in transforming Zi into C and H,which implies that there Combining them together.we have may be some unused budget for C and H1.We thus try to improve C and HI by utilizing the remaining budget(B-B) 2C,田=max0C,H.Q(C2,H≥max0z(z2》 (lines 25-28).In each iteration,we allocate a fixed power Pmin L to the location that maximizes the marginal objective gain. 2≥lezz'acr L We choose the better one of (C.H1)and (C2.H2)as the fi- nal solution to P3.The time complexity of TCA is O(MN3L3). The following theorem gives the bound on the worst case performance of TCA.Later,we will see in the simulations D.A Concrete Example that,the gap between TCA and the optimal solution is 4.5% In this subsection,we provide an example that helps readers at most and 2.0%on average. better understand TCA.There are 3 candidate locations and 2 Theorem 3:TCA is a factor approx.algorithm for P3 devices in the plane,as shown in Fig.5.Following existing Proof:Denote by (C',H')the optimal solution to p3,and works [9,11,12],we assume that,pmin 50,L 4. by (C',H)the solution returned by TCA.We want to prove Ph=0.01,a=0.64,and B=30.Given these parameters,we that, have D1)≈27，D2)=50,D(3)≈68，andD(4)≈83.The Q(C,田、1-1/e radii of dashed circles show the maximum cover distances of QC,Hr≥ 2L four different power levels.We also knows that,d(c1,s1)=20, Let Z'be the optimal solution to VP3,and let dc1,s2)=70,dc2,s2)=40,andd(c3,s2)=60.The maximum power consumption rate of si or s2 is 0.07,i.e., arg() P1 =P2 =0.07.Given a power budget B =500,we now check how TCA computes the result. where Zi and Z2 are the solution generated by lines 3-7 In lines 2-7 of Alg.3,we first check which (c,h) and 9-14 of TCA,respectively.According to the results in gives the maximal marginal objective gain.For cI,we have Section IV-B,we know Q{(c1,1)）=0.0128.Q(c1,2)》=0.0256,Q({(c1,3)》）= 0.0384,and ([(c1,4)))=0.064;for c2 and c3,we can ez≥1-，1yez compute these values in a similar way.Thus,in the first 2 iteration of lines 2-8,we add (c1,4)into Z1.It is worth Notice that,if we restrict the number of chargers that can noting that,in the second iteration,(((c1,4)U((c1,2)))- be placed at each candidate location to one,the Vp3 problem Q(c1,4)D=mintp(c1,s1,2),P-pc1,s1,4)}=0.0188(see is equivalent to P3.From this viewpoint,we have Equ.(7)and Equ.(8)).The reader can check that,Zi would be{(c1,4),(c2,4),(c1,2)h. (Z)>(C'.H). Note that,for each location,we retain only one charger In Z (resp.Z2),we can place at most L chargers for one which has the largest power level in Z1.Then we get C= location.When transforming Z (resp.Z2)into C and H (c1,c2}and H =(4,4).In lines 25-28,we try to utilize the remaining budget 500-(4+4)x 50 =100.We find that,the INote that,we can further improve lines 25-28 of TCA by applying both distance between c3 and s2 is larger than D(2),thus,there is Equ.(5)and Equ.(6)and choosing the better one.However,the improvement no need to allocate the remaining 100 units of power to c3. would be little.We choose the current form of TCA for brevity. And we have C=(c1,c2}and H1=(4,4)

The objective function is Q(Z′ ) = ∑ M j=1 QZ′ (sj). The main idea of TCA is as follows. We use the two greedy heuristics (i.e., Equ. (5) and Equ. (6)) to solve the VP3 problem defined above, and get two results Z1 and Z2, respectively. Note that, there may be more than one charger placed at a candidate location in Z1 or Z2. We then invoke the RemoveDuplicationAndUtilize sub-procedure to transform Z1 and Z2 into two solutions to P3 , respectively. The transformation works as follows (take Z1 for example): For each location ci , we set H1[ci] to be the maximum value of hk among all (ci , hk) ∈ Z1, i.e., H1[ci] = max(ci ,hk )∈Z1 hk (line 6 of Alg. 3). For each location ci , if H1[ci] > 0, we add it into C ′ 1 , which is equivalent to C ′ 1 = {ci |(ci , hk) ∈ Z1} (lines 22-24). As Alg. 3 shows, we retain only one charger for each location in transforming Z1 into C ′ 1 and H1, which implies that there may be some unused budget for C ′ 1 and H1. We thus try to improve C ′ 1 and H1 by utilizing the remaining budget (B− B ′ 1 ) (lines 25-28). In each iteration, we allocate a fixed power pmin to the location that maximizes the marginal objective gain1 . We choose the better one of (C ′ 1 , H1) and (C ′ 2 , H2) as the fi- nal solution to P3 . The time complexity of TCA is O(MN3L 3 ). The following theorem gives the bound on the worst case performance of TCA. Later, we will see in the simulations that, the gap between TCA and the optimal solution is 4.5% at most and 2.0% on average. Theorem 3: TCA is a factor 1−1/e 2L approx. algorithm for P3 . Proof: Denote by (C ∗ , H ∗ ) the optimal solution to P3 , and by (C ′ , H) the solution returned by TCA. We want to prove that, Q(C ′ , H) Q(C∗ , H ∗ ) ≥ 1 − 1/e 2L . Let Z∗ be the optimal solution to VP3 , and let Z′ = arg max Z′∈{Z1,Z2} Q(Z′ ) where Z1 and Z2 are the solution generated by lines 3-7 and 9-14 of TCA, respectively. According to the results in Section IV-B, we know Q(Z′ ) ≥ 1 − 1/e 2 Q(Z∗ ). Notice that, if we restrict the number of chargers that can be placed at each candidate location to one, the VP3 problem is equivalent to P3 . From this viewpoint, we have Q(Z∗ ) ≥ Q(C ∗ , H ∗ ). In Z1 (resp. Z2), we can place at most L chargers for one location. When transforming Z1 (resp. Z2) into C ′ 1 and H1 1Note that, we can further improve lines 25-28 of TCA by applying both Equ. (5) and Equ. (6) and choosing the better one. However, the improvement would be little. We choose the current form of TCA for brevity. c1 s2 s1 c2 c3 Fig. 5: There are 3 candidate locations and 2 devices. The radii of dashed circles show the maximum cover distances of four different power levels. (resp. C ′ 2 and H2), for each location, we retain the charger that has the largest power level, if any. Therefore, we have Q(C ′ 1 , H1) ≥ Q(Z1) L , and Q(C ′ 2 , H2) ≥ Q(Z2) L . Combining them together, we have Q(C ′ , H) = max{Q(C ′ 1 , H1), Q(C ′ 2 , H2)} ≥ max{Q(Z1), Q(Z2)} L = Q(Z′ ) L ≥ 1 − 1/e 2L Q(Z∗ ) ≥ 1 − 1/e 2L Q(C ∗ , H ∗ ). D. A Concrete Example In this subsection, we provide an example that helps readers better understand TCA. There are 3 candidate locations and 2 devices in the plane, as shown in Fig. 5. Following existing works [9, 11, 12], we assume that, pmin = 50, L = 4, pth = 0.01, α = 0.64, and β = 30. Given these parameters, we have D(1) ≈ 27, D(2) = 50, D(3) ≈ 68, and D(4) ≈ 83. The radii of dashed circles show the maximum cover distances of four different power levels. We also knows that, d(c1, s1) = 20, d(c1, s2) = 70, d(c2, s2) = 40, and d(c3, s2) = 60. The maximum power consumption rate of s1 or s2 is 0.07, i.e., P1 = P2 = 0.07. Given a power budget B = 500, we now check how TCA computes the result. In lines 2-7 of Alg. 3, we first check which (c, h) gives the maximal marginal objective gain. For c1, we have Q({(c1, 1)}) = 0.0128, Q({(c1, 2)}) = 0.0256, Q({(c1, 3)}) = 0.0384, and Q({(c1, 4)}) = 0.064; for c2 and c3, we can compute these values in a similar way. Thus, in the first iteration of lines 2-8, we add (c1, 4) into Z1. It is worth noting that, in the second iteration, Q({(c1, 4)} ∪ {(c1, 2)}) − Q({(c1, 4)}) = min{p(c1, s1, 2), P1 − p(c1, s1, 4)} = 0.0188 (see Equ. (7) and Equ. (8)). The reader can check that, Z1 would be {(c1, 4), (c2, 4), (c1, 2)}. Note that, for each location, we retain only one charger which has the largest power level in Z1. Then we get C ′ 1 = {c1, c2} and H1 = (4, 4). In lines 25-28, we try to utilize the remaining budget 500 − (4 + 4) × 50 = 100. We find that, the distance between c3 and s2 is larger than D(2), thus, there is no need to allocate the remaining 100 units of power to c3. And we have C ′ 1 = {c1, c2} and H1 = (4, 4)

Similarly,after running lines 9-14,we would have Z2=ers form an ad-hoc network in which they deliver energy (c1,4).(c1.1).(c2.2).(c2,3)).Through removing duplications.amongst themselves. we have C2=(c1,c2}and H2 =(4,3).After utilizing remaining budget,we also have C2=(ci,c2)and H2 =(4,4). V.PERFORMANCE EVALUATION The final solution is C'=(c1,c2)and H =(4,4),yielding In this section,we conduct extensive simulations to evaluate an objective of O(C.H)=0.0902. our design under different network settings and reveal insights of the proposed design performance. E.P3 in A Cycle A.Baseline Setup In this subsection,we provide an extension of p3 from the time perspective. Since currently there is no algorithm available for the p3 Suppose the power consumption rates of devices exhibit problem,we introduce three algorithms for comparison. cyclic patterns,and a cycle contains T time slots.We assume Optimal Algorithm (OPT):P3 in general is NP-complete. that the battery of each device is large enough to store(T. We simply use brute force to find the optimal solution.Due maxsjes Pj)energy.In other words,if a device receives (T. to its high time complexity O(MLN).it is only practical for maxses Pj)energy in the Ist time slot of a cycle,it could small instances of the p3 problem. sustain its operations over the next T-1 time slots.We extend Fixed Level Algorithm (FLA):It consists of two phases. P3 to p3(T):Given a power budget T.B.how do we find a The first phase is to compute the optimal power level of each location irrespective of the other locations,i.e.,we set charger placement C and a power allocation H,for each time slot te(1,2.....T]to maximize the total charging quality? ∑12es》 It is easy to see that,P3(T)becomes p3 when T=1.How- hi=arg max hee(1.p(hi) ever,solving P(T)is not equivalent to solving T consecutive P3 problems.The following example shows that solving T The second phase is to invoke Alg.2 to generate a charger consecutive P3 problems may perform badly for P3(T). placement for P3 with fixed power levels. Assume that there are T locations and T devices.The Random Algorithm (RAN):It should generate each possible maximum power consumption rate of sr is larger than that solution with the same probability.We implement it as follows. Let b=0 at the beginning.In the i-th iteration,we uniformly of any other device,i.e.,P1 P2 =..=Pr-1 Pr.For 1≤i≤T,dc,s)≤D1):for any i≠，dc,s)>D(1).We generate a random integer xi in the range [1,L],let b =b+xi; further assume that,,forl≤i≤T,p(ci,s)≥T.Pi,even when if (B/pmin-b)is no less than L,go to the next iteration,else the power level of ci is 1. let xitl be (B/Pmin-b).Suppose the index of the last iteration Given a power budget T.Pmin,if we run TCA with budget is k,for k+1 s js N,we let xj be 0.We then sort x1,x2. Pmin in each time slot independently,since we can only place ...xN randomly to get a random permutation )For only one charger with a power of Pmin,and Pr P1=P2= each ci,we set H[ci]=x in the random solution. ..=Pr-1,in each time slot TCA would allocate pmin to cr.B.Experiment Setup And the final charging quality is T.Pr.However,the optimal We assume wireless devices and candidate locations are solution is to allocate Pmin to c(r+1-in the i-th time slot, randomly distributed over a 1,000mx1,000m two-dimensional leading to a total charging quality of+T.Pr.When 2 square area.The default number of candidate locations is 20. Pr approaches P1,the optimal solution is O(T)times as large The minimum power Pmin of a charger is 50.By default,the as the result generated by solving T consecutive P3 problems. maximum power level L of a charger is 6.The default number We propose to solve P3(T)in a similar way as TCA.We first of devices is 200.Following prior works [9,11,12],we set solve a variant of this problem,and then transform the solution a =0.64 and B=30 in the charging model (Equ.(1)).The to the variant into the solution to P3(T).The variant problem is: threshold ph of negligible power is 0.01.Therefore,the min- For each candidate location in the k-th time slot,we are given imum coverage radius is D(1)=v0.64 x 50/0.01-3027m L chargers with constant but exactly different power levels. (see Equ.(2)),and by default the maximum coverage radius We use (ci.hi.t)to denote the charger of a constant power is D(6)=V0.64 x 300/0.01 -30 109m.The maximum level hi that can only be placed at ci in the k-th time slot.Note power consumption rate of each device is uniformly generated that there are,in total,T.N.L chargers.Given a power budget between 0.02 and 0.03.The default power budget is 3,000. T.B,how do we find a charger placement that maximize the total charging quality?The solution transformation process is C.Performance Comparison similar to that in Alg.3.We can also prove that this algorithm As we have mentioned,it is impractical to run OPT using is a factor approx.algorithm for P(T).We omit the brute force in general,we thus use the following setting to details due to space limitations. generate some small instances for comparing TCA with OPT: As a final note,we are also thinking about offering wireless N=8.M 50.B 800.L 4.and the side length of charging services in some scenarios without any electric the 2-D plane is 300m.Fig.6 shows the results of different wires,e.g.,disaster areas (no infrastructure),and temporal experiment setups of small instances.We ran each different conferences.A natural method to cope with this no/low- setup ten times and averaged the results.The max and min infrastructure challenge is relying on collaboration,i.e.,charg- values among ten runs are also provided in the figures

Similarly, after running lines 9-14, we would have Z2 = {(c1, 4), (c1, 1), (c2, 2), (c2, 3)}. Through removing duplications, we have C ′ 2 = {c1, c2} and H2 = (4, 3). After utilizing remaining budget, we also have C ′ 2 = {c1, c2} and H2 = (4, 4). The final solution is C ′ = {c1, c2} and H = (4, 4), yielding an objective of Q(C ′ , H) = 0.0902. E. P3 in A Cycle In this subsection, we provide an extension of P3 from the time perspective. Suppose the power consumption rates of devices exhibit cyclic patterns, and a cycle contains T time slots. We assume that the battery of each device is large enough to store (T · maxsj∈S Pj) energy. In other words, if a device receives (T · maxsj∈S Pj) energy in the 1st time slot of a cycle, it could sustain its operations over the next T −1 time slots. We extend P 3 to P3 (T): Given a power budget T · B, how do we find a charger placement C ′ t and a power allocation Ht for each time slot t ∈ {1, 2, ..., T} to maximize the total charging quality? It is easy to see that, P3 (T) becomes P3 when T = 1. How￾ever, solving P3 (T) is not equivalent to solving T consecutive P 3 problems. The following example shows that solving T consecutive P3 problems may perform badly for P3 (T). Assume that there are T locations and T devices. The maximum power consumption rate of sT is larger than that of any other device, i.e., P1 = P2 = ... = PT−1 D(1). We further assume that, for 1 ≤ i ≤ T, p(ci , si) ≥ T ·Pi , even when the power level of ci is 1. Given a power budget T · pmin, if we run TCA with budget pmin in each time slot independently, since we can only place only one charger with a power of pmin, and PT > P1 = P2 = ... = PT−1, in each time slot TCA would allocate pmin to cT . And the final charging quality is T · PT . However, the optimal solution is to allocate pmin to c(T+1−i) in the i-th time slot, leading to a total charging quality of T(T−1) 2 P1 + T · PT . When PT approaches P1, the optimal solution is O(T) times as large as the result generated by solving T consecutive P3 problems. We propose to solve P3 (T) in a similar way as TCA. We first solve a variant of this problem, and then transform the solution to the variant into the solution to P3 (T). The variant problem is: For each candidate location in the k-th time slot, we are given L chargers with constant but exactly different power levels. We use (ci , hi , tk) to denote the charger of a constant power level hi that can only be placed at ci in the k-th time slot. Note that there are, in total, T ·N·L chargers. Given a power budget T · B, how do we find a charger placement that maximize the total charging quality? The solution transformation process is similar to that in Alg. 3. We can also prove that this algorithm is a factor 1−1/e 2L approx. algorithm for P3 (T). We omit the details due to space limitations. As a final note, we are also thinking about offering wireless charging services in some scenarios without any electric wires, e.g., disaster areas (no infrastructure), and temporal conferences. A natural method to cope with this no/low￾infrastructure challenge is relying on collaboration, i.e., charg￾ers form an ad-hoc network in which they deliver energy amongst themselves. V. Performance Evaluation In this section, we conduct extensive simulations to evaluate our design under different network settings and reveal insights of the proposed design performance. A. Baseline Setup Since currently there is no algorithm available for the P3 problem, we introduce three algorithms for comparison. Optimal Algorithm (OPT): P3 in general is NP-complete. We simply use brute force to find the optimal solution. Due to its high time complexity O(MLN ), it is only practical for small instances of the P3 problem. Fixed Level Algorithm (FLA): It consists of two phases. The first phase is to compute the optimal power level of each location irrespective of the other locations, i.e., we set hi = arg max hi∈{1,...,L} ∑M j=1 Q{ci}(sj) p(hi) . The second phase is to invoke Alg. 2 to generate a charger placement for P3 with fixed power levels. Random Algorithm (RAN): It should generate each possible solution with the same probability. We implement it as follows. Let b = 0 at the beginning. In the i-th iteration, we uniformly generate a random integer xi in the range [1, L], let b = b+ xi ; if (B/pmin − b) is no less than L, go to the next iteration, else let xi+1 be (B/pmin −b). Suppose the index of the last iteration is k, for k + 1 ≤ j ≤ N, we let xj be 0. We then sort x1, x2, ..., xN randomly to get a random permutation (x ′ 1 , ..., x ′ N ). For each ci , we set H[ci] = x ′ i in the random solution. B. Experiment Setup We assume wireless devices and candidate locations are randomly distributed over a 1, 000m×1, 000m two-dimensional square area. The default number of candidate locations is 20. The minimum power pmin of a charger is 50. By default, the maximum power level L of a charger is 6. The default number of devices is 200. Following prior works [9, 11, 12], we set α = 0.64 and β = 30 in the charging model (Equ. (1)). The threshold pth of negligible power is 0.01. Therefore, the min￾imum coverage radius is D(1) = √ 0.64 × 50/0.01 − 30 ≈ 27m (see Equ. (2)), and by default the maximum coverage radius is D(6) = √ 0.64 × 300/0.01 − 30 ≈ 109m. The maximum power consumption rate of each device is uniformly generated between 0.02 and 0.03. The default power budget is 3,000. C. Performance Comparison As we have mentioned, it is impractical to run OPT using brute force in general, we thus use the following setting to generate some small instances for comparing TCA with OPT: N = 8, M = 50, B = 800, L = 4, and the side length of the 2-D plane is 300m. Fig. 6 shows the results of different experiment setups of small instances. We ran each different setup ten times and averaged the results. The max and min values among ten runs are also provided in the figures

1 0.8 N.number of candidate locations M.number of devices L,maximum power level of a charger (a)Varying the number of locations (b)Varying the number of devices (c)varying the power budget (d)Varying the maximum power level Fig.6:Evaluation results on small instances (the default setting is N=8.M=50.B=800.L=4,and the side length of the 2-D plane is 300m). 300 1000 devices locations 800 2D0 154 10 200 devices locations 5( 100 150 200 250300 200 400 600 000 Fig.7:A small instance visualization example Fig.8:A large instance visualization example In general,TCA achieves a near optimal solution and outperforms the other algorithms.Specifically,the gap be- In the figure,we use circle radius to indicate the allocated tween TCA and OPT is 4.5%at most and 2.0%on average. power level of a location.The charging quality (see Def.1) This observation validates our theoretical results.FLA uses a of this solution is 0.77.In Fig.8,TCA picks 35 out of 50 candidate locations for charging 200 devices.The allocated similar idea as our algorithm,thus,it performs much better power levels consist of four 1's,three 4's,and twenty-eight than RAN,which has the worst performance in all setups.On average,the charging quality RAN achieves is roughly 64.4% 6's,yielding a charging quality of 3.34. of that of TCA. Fig.9 depicts the performance of TCA,FLA,and RAN In Figs.6(a)and 6(d).when the number of candidate on large p3 instances.Most of the findings from Fig.6 still locations increases or the maximum power level of a candidate hold here.We would like to highlight that,in Fig.9(c), location increases,the chance of having a better solution goes the increasing speed of the charging quality tends to slow up,so the overall charging quality increases.Since a charger down gradually,e.g.,the increment of TCA between the first can transfer power to multiple devices simultaneously [17], three consecutive groups are 0.21,0.18,and 0.12.This is in when the number of energy receiving devices increases,the accordance with the submodularity of the objective function. total power received by all devices would be larger than before, We also conduct evaluations based on large instances of so the charging quality increases as well.This is what we P3.Fig.10 gives the comparison results on running time of noticed in Fig.6(b).Fig.6(c)presents the performance of TCA,FLA,and RAN.Remember that the worst case time the four algorithms when the power budget is varying.As complexity of TCA is O(MN3L3),thus,it is expected that we can see,when the budget increases,our objective function the running time of TCA increases as one of M,N,and increases as expected. L increases.An interesting observation is that,TCA runs For easy understanding,we visualize two charger place- averagely faster when L increases.The main reason behind this ments and the corresponding allocated power levels generated phenomenon is that,when L increases,the number of iterations by TCA for two instances of p3 in Figs.7 and 8.respectively. in each while-loop (i.e.,lines 3-7 and 10-14)becomes smaller, In Fig.7,there are in total 9 candidate locations and 50 which may shorten the running time. devices.TCA picks 6 of them,and the corresponding power In summary,the proposed algorithm TCA performs very levels are 4,3,1,4,1,and 3.As we mentioned in Equ.(2),the closely to OPT (the gap is no more than 4.5%of OPT).and maximum coverage distance is determined by the power level. outperforms the other two baseline algorithms

0 0.2 0.4 0.6 0.8 1 1.2 5 6 7 8 9 10 Q, network charging quality N, number of candidate locations OPT TCA FLA RAN (a) Varying the number of locations 0 0.5 1 1.5 2 30 50 70 90 110 130 Q, network charging quality M, number of devices OPT TCA FLA RAN (b) Varying the number of devices 0 0.2 0.4 0.6 0.8 1 1.2 500 600 700 800 900 1000 Q, network charging quality B, power budget OPT TCA FLA RAN (c) varying the power budget 0 0.2 0.4 0.6 0.8 1 1.2 3 4 5 6 Q, network charging quality L, maximum power level of a charger OPT TCA FLA RAN (d) Varying the maximum power level Fig. 6: Evaluation results on small instances (the default setting is N = 8, M = 50, B = 800, L = 4, and the side length of the 2-D plane is 300m). Fig. 7: A small instance visualization example In general, TCA achieves a near optimal solution and outperforms the other algorithms. Specifically, the gap be￾tween TCA and OPT is 4.5% at most and 2.0% on average. This observation validates our theoretical results. FLA uses a similar idea as our algorithm, thus, it performs much better than RAN, which has the worst performance in all setups. On average, the charging quality RAN achieves is roughly 64.4% of that of TCA. In Figs. 6(a) and 6(d), when the number of candidate locations increases or the maximum power level of a candidate location increases, the chance of having a better solution goes up, so the overall charging quality increases. Since a charger can transfer power to multiple devices simultaneously [17], when the number of energy receiving devices increases, the total power received by all devices would be larger than before, so the charging quality increases as well. This is what we noticed in Fig. 6(b). Fig. 6(c) presents the performance of the four algorithms when the power budget is varying. As we can see, when the budget increases, our objective function increases as expected. For easy understanding, we visualize two charger place￾ments and the corresponding allocated power levels generated by TCA for two instances of P3 in Figs. 7 and 8, respectively. In Fig. 7, there are in total 9 candidate locations and 50 devices. TCA picks 6 of them, and the corresponding power levels are 4, 3, 1, 4, 1, and 3. As we mentioned in Equ. (2), the maximum coverage distance is determined by the power level. Fig. 8: A large instance visualization example In the figure, we use circle radius to indicate the allocated power level of a location. The charging quality (see Def. 1) of this solution is 0.77. In Fig. 8, TCA picks 35 out of 50 candidate locations for charging 200 devices. The allocated power levels consist of four 1’s, three 4’s, and twenty-eight 6’s, yielding a charging quality of 3.34. Fig. 9 depicts the performance of TCA, FLA, and RAN on large P3 instances. Most of the findings from Fig. 6 still hold here. We would like to highlight that, in Fig. 9(c), the increasing speed of the charging quality tends to slow down gradually, e.g., the increment of TCA between the first three consecutive groups are 0.21, 0.18, and 0.12. This is in accordance with the submodularity of the objective function. We also conduct evaluations based on large instances of P 3 . Fig. 10 gives the comparison results on running time of TCA, FLA, and RAN. Remember that the worst case time complexity of TCA is O(MN3L 3 ), thus, it is expected that the running time of TCA increases as one of M, N, and L increases. An interesting observation is that, TCA runs averagely faster when L increases. The main reason behind this phenomenon is that, when L increases, the number of iterations in each while-loop (i.e., lines 3-7 and 10-14) becomes smaller, which may shorten the running time. In summary, the proposed algorithm TCA performs very closely to OPT (the gap is no more than 4.5% of OPT), and outperforms the other two baseline algorithms

0 12 3 9L.nua0erotCie 350 00 200 4000 L.maximum power level of a charger (a)Varying the number of locations (b)Varying the number of devices (c)varying the power budget (d)Varying the maximum power level Fig.9:Evaluation results on large instances (the default setting is N 20,M=200.B=3,000.L=6,and the side length of the 2-D plane is 1,000m). 10 FT ◆CA ELAG RAN [3]B.Tong,G.Wang,W.Zhang,and C.Wang,"Node reclamation and replacement for long-lived sensor networks,"IEEE Transactions on 0 Parallel and Distributed Systems,vol.22,pp.1550-1563,Sept.2011. 12 16 locat 28 32 umbe [4]A.Kurs,A.Karalis,R.Moffatt,J.D.Joannopoulos,P.Fisher,and 107 M.Soljacic,"Wireless power transfer via strongly coupled magnetic 0 resonances,"Science,vol.317,no.5834.pp.83-86,2007. [5]"Wireless power consortium,"http:/www.wirelesspowerconsortium.com/. 与 100 150 M.nuber ot ces 00 300 350 [6]"Tesla motors,"http:/www.teslamotors.com. 30FT [7]Y.Peng.Z.Li,W.Zhang.and D.Qiao,"Prolonging sensor network lifetime through wireless charging"in Proc.of IEEE RTSS 2010. Pp.129-139. 2000 4000 4500 [8]Y.Shi,L.Xie,Y.Hou,and H.Sherali,"On renewable sensor networks 10 with wireless energy transfer,"in Proc.of IEEE INFOCOM 2011, 5 Pp.1350-1358. 01 [9]S.He,J.Chen,F.Jiang.D.K.Yau,G.Xing,and Y.Sun,"Energy L miaximum power level of a charger provisioning in wireless rechargeable sensor networks,"in Proc.of IEEE 1NF0C0M201L,Pp.2006-2014 [10]S.Zhang.J.Wu,and S.Lu,"Collaborative mobile charging,"Accepted Fig.10:Running time comparison to appear in IEEE Transactions on Computers,2014. [11]L.Fu,P.Cheng.Y.Gu,J.Chen,and T.He,"Minimizing charging delay in wireless rechargeable sensor networks,"in Proc.of IEEE INFOCOM VI.CONCLUSIONS 2013,Pp.2922-2930. [12]H.Dai,Y.Liu,G.Chen,X.Wu,and T.He,"Safe charging for wireless In this paper,we have studied the joint optimization problem power transfer,"in Proc.of IEEE INFOCOM 2014,pp.1105-1113. of charger placement and power allocation for wireless power [13]V.V.Vazirani.Approximation Algorithms.Springer,2003. [14]A.P.Sample,D.J.Yeager,P.S.Powledge,A.V.Mamishev,and transfer.We proved that this problem is NP-complete by J.R.Smith,"Design of an rfid-based battery-free programmable sensing reduction from the set cover problem.We first considered the platform,"IEEE Transactions on Instrumentation and Measurement P3 problem with fixed power levels,and proposed a(1-1/e)- vol.57,no.11,Pp.2608-2615,2008. [15]Z.Li.Y.Peng.W.Zhang,and D.Qiao."Study of joint routing and approximation algorithm.Based on the acquired insights,we wireless charging strategies in sensor networks,"in Proc.of WA.SA 2010, then designed TCA for P3,which achieves an approximation Pp.125-135. guarantee of We also discussed an extension of p3 [16]L.Xie,Y.Shi,Y.T.Hou,W.Lou.H.D.Sherali,and S.F.Midkiff,"On renewable sensor networks with wireless energy transfer:The multi-node namely ps in a cycle.Extensive simulation results confirmed case,"in Proc.of IEEE SECON 2012,pp.10-18. the performance of our algorithm compared with the optimal [17]B.Tong.Z.Li.G.Wang.and W.Zhang."How wireless power charging technology affects sensor network deployment and routing,"in Proc.of algorithm and two other heuristic algorithms. IEEE1CDCS2010,pp.438-447. [18]C.Wang.J.Li.F.Ye,and Y.Yang,"NETWRAP:An NDN based real- ACKNOWLEDGMENTS timewireless recharging framework for wireless sensor networks."/EEE We would like to thank the anonymous reviewers for Transactions on Mobile Computing,vol.13.pp.1283-1297,June 2014. [19]S.Zhang.J.Wu,and S.Lu,"Collaborative mobile charging for sensor their insightful suggestions.This work was supported in part networks,"in Proc.of IEEE MASS 2012.pp.84-92. by NSFC(61321491,61472185,61100196.and91218302). [20]N.Patwari,A.O.Hero,M.Perkins,N.S.Correal,and R.J.O'dea, Key Project of Jiangsu Research Program(BE2013116),EU "Relative location estimation in wireless sensor networks,"IEEE Trans- FP7 IRSES MobileCloud Project (612212),and Collaborative acrions on Signal Processing,vol.51.no.8.pp.2137-2148.2003. [21]G.L.Nemhauser.L.A.Wolsey.and M.L.Fisher,"An analysis of ap- Innovation Center of Novel Software Technology and Indus- proximations for maximizing submodular set functionsti,"Mathematical trialization. Programming,vol.14,no.1,pp.265-294,1978. [22]D.Yang.X.Fang,and G.Xue,"ESPN:Efficient server placement REFERENCES in probabilistic networks with budget constraint,"in Prof.of IEEE NF0C0M2011,Pp.1269-1277. [1]A.Kansal,J.Hsu,S.Zahedi,and M.B.Srivastava,"Power management [23]J.Leskovec.A.Krause,C.Guestrin,C.Faloutsos,J.VanBriesen,and in energy harvesting sensor networks,"ACM Transactions on Embedded N.Glance."Cost-effective outbreak detection in networks,"in Proc.of Computing Systems,vol.6.Sept.2007. ACM SIGKDD 2007,pp.420-429. [2]A.Dunkels.F.Osterlind.and Z.He."An adaptive communication architecture for wireless sensor networks,"in Proc.ofACM SenSys 2007 Pp.335-349

0 0.5 1 1.5 2 12 16 20 24 28 32 Q, network charging quality N, number of candidate locations TCA FLA RAN (a) Varying the number of locations 0 0.5 1 1.5 2 2.5 3 100 150 200 250 300 350 Q, network charging quality M, number of devices TCA FLA RAN (b) Varying the number of devices 0 0.5 1 1.5 2 2000 2500 3000 3500 4000 4500 Q, network charging quality B, power budget TCA FLA RAN (c) varying the power budget 0 0.5 1 1.5 2 4 5 6 7 8 9 Q, network charging quality L, maximum power level of a charger TCA FLA RAN (d) Varying the maximum power level Fig. 9: Evaluation results on large instances (the default setting is N = 20, M = 200, B = 3, 000, L = 6, and the side length of the 2-D plane is 1,000m). Fig. 10: Running time comparison VI. Conclusions In this paper, we have studied the joint optimization problem of charger placement and power allocation for wireless power transfer. We proved that this problem is NP-complete by reduction from the set cover problem. We first considered the P 3 problem with fixed power levels, and proposed a (1−1/e)- approximation algorithm. Based on the acquired insights, we then designed TCA for P3 , which achieves an approximation guarantee of 1−1/e 2L . We also discussed an extension of P3 , namely P3 in a cycle. Extensive simulation results confirmed the performance of our algorithm compared with the optimal algorithm and two other heuristic algorithms. Acknowledgments We would like to thank the anonymous reviewers for their insightful suggestions. This work was supported in part by NSFC (61321491, 61472185, 61100196, and 91218302), Key Project of Jiangsu Research Program (BE2013116), EU FP7 IRSES MobileCloud Project (612212), and Collaborative Innovation Center of Novel Software Technology and Indus￾trialization. References [1] A. Kansal, J. Hsu, S. Zahedi, and M. B. Srivastava, “Power management in energy harvesting sensor networks,” ACM Transactions on Embedded Computing Systems, vol. 6, Sept. 2007. [2] A. Dunkels, F. Osterlind, and Z. He, “An adaptive communication ¨ architecture for wireless sensor networks,” in Proc. of ACM SenSys 2007, pp. 335–349. [3] B. Tong, G. Wang, W. Zhang, and C. Wang, “Node reclamation and replacement for long-lived sensor networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 22, pp. 1550 –1563, Sept. 2011. [4] A. Kurs, A. Karalis, R. Moffatt, J. D. Joannopoulos, P. Fisher, and M. Soljaˇci´c, “Wireless power transfer via strongly coupled magnetic resonances,” Science, vol. 317, no. 5834, pp. 83–86, 2007. [5] “Wireless power consortium,” http://www.wirelesspowerconsortium.com/. [6] “Tesla motors,” http://www.teslamotors.com/. [7] Y. Peng, Z. Li, W. Zhang, and D. Qiao, “Prolonging sensor network lifetime through wireless charging,” in Proc. of IEEE RTSS 2010, pp. 129–139. [8] Y. Shi, L. Xie, Y. Hou, and H. Sherali, “On renewable sensor networks with wireless energy transfer,” in Proc. of IEEE INFOCOM 2011, pp. 1350–1358. [9] S. He, J. Chen, F. Jiang, D. K. Yau, G. Xing, and Y. Sun, “Energy provisioning in wireless rechargeable sensor networks,” in Proc. of IEEE INFOCOM 2011, pp. 2006–2014. [10] S. Zhang, J. Wu, and S. Lu, “Collaborative mobile charging,” Accepted to appear in IEEE Transactions on Computers, 2014. [11] L. Fu, P. Cheng, Y. Gu, J. Chen, and T. He, “Minimizing charging delay in wireless rechargeable sensor networks,” in Proc. of IEEE INFOCOM 2013, pp. 2922–2930. [12] H. Dai, Y. Liu, G. Chen, X. Wu, and T. He, “Safe charging for wireless power transfer,” in Proc. of IEEE INFOCOM 2014, pp. 1105–1113. [13] V. V. Vazirani, Approximation Algorithms. Springer, 2003. [14] A. P. Sample, D. J. Yeager, P. S. Powledge, A. V. Mamishev, and J. R. Smith, “Design of an rfid-based battery-free programmable sensing platform,” IEEE Transactions on Instrumentation and Measurement, vol. 57, no. 11, pp. 2608–2615, 2008. [15] Z. Li, Y. Peng, W. Zhang, and D. Qiao, “Study of joint routing and wireless charging strategies in sensor networks,” in Proc. of WASA 2010, pp. 125–135. [16] L. Xie, Y. Shi, Y. T. Hou, W. Lou, H. D. Sherali, and S. F. Midkiff, “On renewable sensor networks with wireless energy transfer: The multi-node case,” in Proc. of IEEE SECON 2012, pp. 10–18. [17] B. Tong, Z. Li, G. Wang, and W. Zhang, “How wireless power charging technology affects sensor network deployment and routing,” in Proc. of IEEE ICDCS 2010, pp. 438–447. [18] C. Wang, J. Li, F. Ye, and Y. Yang, “NETWRAP: An NDN based real￾timewireless recharging framework for wireless sensor networks,” IEEE Transactions on Mobile Computing, vol. 13, pp. 1283–1297, June 2014. [19] S. Zhang, J. Wu, and S. Lu, “Collaborative mobile charging for sensor networks,” in Proc. of IEEE MASS 2012, pp. 84–92. [20] N. Patwari, A. O. Hero, M. Perkins, N. S. Correal, and R. J. O’dea, “Relative location estimation in wireless sensor networks,” IEEE Trans￾actions on Signal Processing, vol. 51, no. 8, pp. 2137–2148, 2003. [21] G. L. Nemhauser, L. A. Wolsey, and M. L. Fisher, “An analysis of ap￾proximations for maximizing submodular set functionsłi,” Mathematical Programming, vol. 14, no. 1, pp. 265–294, 1978. [22] D. Yang, X. Fang, and G. Xue, “ESPN: Efficient server placement in probabilistic networks with budget constraint,” in Prof. of IEEE INFOCOM 2011, pp. 1269–1277. [23] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen, and N. Glance, “Cost-effective outbreak detection in networks,” in Proc. of ACM SIGKDD 2007, pp. 420–429