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, submodularity, 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 perspectives 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 technology, 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 delay [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 placement 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 corresponding 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 allocation 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 developed 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 collaboration between mobile chargers to optimize energy usage effectiveness [10, 19]. Dai et al. proposed a near optimal solution 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. Denote 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 coverage 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 placement C ′ and a power allocation H, the charging quality, denoted 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 subcollection 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 C1<Lg」do 3: c-arg max (Q(C'U(c))-Q(C')) CEC\C C←C'U{c ●S2 5:end while ●S3 SN- 6:return C SN (a)Using Equ.(5) (b)Using Equ.(6) 1)Uniform Case:We first look at the uniform case of Fig.4:Motivational examples show that,directly applying Equ.(5)or Equ.(6) to the non-uniform case may perform very bad. power levels,i.e.,h=h2 =...=hN =h.In other words, P1 =p2 =...=PN p(h)=h.Pmin.For convenience,denote the power of each charger by p in this subsection. ·Pc(si）≤Pj:in this case,we have In this case,the objective function (C,H)degenerates into (C),and the P3 problem can be reformulated as follows: Qcuten(sj)-Qc(sj)=min(Pj-Pc(sj),p(c.sj). Given a set C of candidate locations,a set S of devices. Qcue(s）-Qc(s）=min(Pi-Pc(p(c,sh. a power budget B.and a fixed power p,p3 is to find a charger placement C'to maximize O(C),subject to the budget Ifpc,si）≤Pj-Pc(s,then constraint,ie.,IC 2cuc(s）-Qc(s）=pc,sj）=Qcue(si）-Qc.(s In the following,we prove that the objective function (C) has three tractable properties:nonnegativity,monotonicity, If Pi-Pc"(sj)<p(c,sj)<Pj-Pc(sj).then and submodularity,which enable us to propose a(1-1/e)- Qcuc(s）-Qc(s)=pc,s approximation algorithm shown in Alg.1. Definition 2:(Nonnegativity,Monotonicity,and Submod- >Pj-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)<f(A')for all AcA U:f is called submodular ≥Pj-Pc(si）=Qcuc(si)-Qc(s) iffU{e)-f(列≥f(A'U{e)-f')for all Ac A'cu Therefore,we proved that Q(C')is submodular. ■ We have the following theorem: According to the results in [21,22],we have a(1-1/e)- Theorem 2:The objective function O(C')is nonnegative, approx.algorithm shown in Alg.1,which starts with an empty monotone,and submodular. set C',in each iteration,we add the location that maximizes Proof:According to Def.1,O(C')is nonnegative.For all the marginal gain of the objective function into C,i.e., C'C"CC,we have Qc)=∑%cs∑c-(=Qc c-arg max (Q(C'U(c))-Q(C)). (5) CEC\C There are at most N iterations in Alg.1;in each iteration, implying that,(C)is monotone.For all C'C"C,we we need to check at most N locations to find the location that need to prove Q(C'U (c))-Q(C')>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′ | < ⌊ B p ⌋ do 3: c ← arg max c∈C\C′ (Q(C ′ ∪ {c}) − Q(C ′ )) 4: C ′ ← C′ ∪ {c} 5: end while 6: return C ′ 1) Uniform Case: We first look at the uniform case of power levels, i.e., h1 = h2 = ... = hN = h. In other words, p1 = p2 = ... = pN = p(h) = h · pmin. For convenience, denote the power of each charger by p in this subsection. In this case, the objective function Q(C ′ , H) degenerates into Q(C ′ ), and the P3 problem can be reformulated as follows: Given a set C of candidate locations, a set S of devices, a power budget B, and a fixed power p, P3 is to find a charger placement C ′ to maximize Q(C ′ ), subject to the budget constraint, i.e., |C′ | ≤ ⌊ B p ⌋. In the following, we prove that the objective function Q(C ′ ) has three tractable properties: nonnegativity, monotonicity, and submodularity, which enable us to propose a (1 − 1/e)- approximation algorithm shown in Alg. 1. Definition 2: (Nonnegativity, Monotonicity, and Submodularity) Given a non-empty finite set U, and a function f defined on the power set 2U of U with real values, f is called nonnegative if f(A) ≥ 0 for all A ⊆ U; f is called monotone if f(A) ≤ f(A′ ) for all A ⊆ A′ ⊆ U; f is called submodular if f(A∪ {e})− f(A) ≥ f(A′∪ {e})− f(A′ ) for all A ⊆ A′ ⊆ U. We have the following theorem: Theorem 2: The objective function Q(C ′ ) is nonnegative, monotone, and submodular. Proof: According to Def. 1, Q(C ′ ) is nonnegative. For all C ′ ⊆ C′′ ⊆ C, we have Q(C ′ ) = ∑M j=1 QC′ (sj) ≤ ∑M j=1 QC′′ (sj) = Q(C ′′), implying that, Q(C ′ ) is monotone. For all C ′ ⊆ C′′ ⊆ C, we need to prove Q(C ′ ∪ {c}) − Q(C ′ ) ≥ Q(C ′′ ∪ {c}) − Q(C ′′). It is sufficient to show that for any sj ∈ S, we have Q(C′∪{c})(sj) − QC′ (sj) ≥ Q(C′′∪{c})(sj) − QC′′ (sj). Based on Equ. (3) and Equ. (4), we prove the above inequation in three cases: • Pj ≤ PC′ (sj): since PC′′ (sj) ≥ PC′ (sj), we have Q(C′∪{c})(sj) − QC′ (sj) = 0 = Q(C′′∪{c})(sj) − QC′′ (sj). • PC′ (sj) < Pj < PC′′ (sj): in this case, Q(C′′∪{c})(sj) − QC′′ (sj) = 0, and we have Q(C′∪{c})(sj) − QC′ (sj) = min{Pj − PC′ (sj), P(C′∪{c})(sj) − PC′ (sj)} = min{Pj − PC′ (sj), p(c, sj)} ≥ 0 = Q(C′′∪{c})(sj) − QC′′ (sj). c1 s1 c2 s2 cN-1 sN-1 cN sN (a) Using Equ. (5) c1 s1 c2 s2 s3 sN-1 sN (b) Using Equ. (6) Fig. 4: Motivational examples show that, directly applying Equ. (5) or Equ. (6) to the non-uniform case may perform very bad. • PC′′ (sj) ≤ Pj : in this case, we have Q(C′∪{c})(sj) − QC′ (sj) = min{Pj − PC′ (sj), p(c, sj)}, Q(C′′∪{c})(sj) − QC′′ (sj) = min{Pj − PC′′ (sj), p(c, sj)}. If p(c, sj) ≤ Pj − PC′′ (sj), then Q(C′∪{c})(sj) − QC′ (sj) = p(c, sj) = Q(C′′∪{c})(sj) − QC′′ (sj). If Pj − PC′′ (sj) < p(c, sj) < Pj − PC′ (sj), then Q(C′∪{c})(sj) − QC′ (sj) = p(c, sj) > 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]<h then Hi[c←-h cx←-arg max Q(CUlc)-Q(C2) C,eC\C2-Ecreczute PrSB Px 7:end while C2←C2U{cx 8:(C.H)-RemoveDuplicationAndUtilize(C,S,B,H1) 9:end while 9:Z2←0，H2←-0 10:return arg max (C) 1o:while B≥，min p(hg)+Σp(hg)do C∈C1C2 (cih)EZ\Z2 (ci.hse乙2 11: (c,h)←-arg max (c.h)EZ\Z2.Ehrzzuteh p(h)<B Q(Z2Ul(c.h))-Q(Z2) Equ.(5),the charger cw would be picked.However,if we pick 12: Z2←罗Uc,1 ci,c2,...and cN-1,the charging quality would be L.p(ci.s1) 13: ifH2[c]<h thenH[c←h instead of p(c1,s1)+e.When e is approaching zero,using 14:end while Equ.(5)would generate approximately 1/L of the charging quality returned by the optimal solution. 15:(C2.H2)--RemoveDuplicationAndUtilize(C,S,B,H2) 16:return arg max Another intuitive method is that,in each iteration,we pick (C.H)E((C:.H).(C.H2)) (C',H) the location that maximize the marginal ratio of objective gain 17: to power cost,i.e., 18:Sub-procedure:RemoveDuplicationAndUtilize 19:Input:C,S,B,and H Q(C'U lcx))-2(C) cx←arg .c (6) 20:Output:C'and H Px 21:C←-0，B←-0 However,we show in Fig.4(b)that,this method may also 22:for all H[ci]>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 0<e<p(c1,s1).Given a power budget B=L.Pmin,using 26 G←argC{c,H+)-QC',田 Equ.(6).the charger cI would be picked.However,if we pick 27: C←CU{cl,Hcl←-H[cl+l,B←B+Pmim c2,the charging quality would be (L-1).p(c1,s1)+p(c2,SM) 28:end while instead of p(c1,s1).When e is approaching zero,this method 29:return (C,H) would also generate approximately 1/L of the charging quality returned by the optimal solution. Surprisingly enough,if we simultaneously apply the above chargers are 1,2....and L.We use (cih)to denote the two methods to the non-uniform case of p3 with fixed power charger of a constant power level h that can only be placed levels,and return the better one of the two results,we will at ci.Note that there are,in total,N.Lchargers.Given a power get an approx.algorithm (Alg.2)of factor(1-1)according budget B,how do we find a charger placement that maximize to [23].The time complexity of Alg.2 is also O(MN3). the objective function defined below? Let Z be the Cartesian product of C and H;denote by C.Approximation Algorithm for P3 Z'a subset of Z.We redefine several functions for the VP3 We design a probably good approximation algorithm,name- problem via overloading.The power p(ci,sj,h)received by ly TCA,in Alg.3 that simultaneously determines C'and H. device si from ci(its power level is hg)is Denote the set (1,2,...,L)by H;denote by Ii a row vector where the i-th element is 1 and all of the other elements are p(ci,Sj.hk)= p(hg) dc,s）≤Dhk, zeros,i.e.,I;=(0,0.....1....0).We use H[ci]to represent the 10 (7) dc,si）>Dhk. 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 < ϵ < p(c1, s1). Given a power budget B = L · pmin, using Equ. (6), the charger c1 would be picked. However, if we pick c2, the charging quality would be (L − 1) · p(c1, s1) + p(c2, sM) instead of p(c1, s1). When ϵ is approaching zero, this method would also generate approximately 1/L of the charging quality returned by the optimal solution. Surprisingly enough, if we simultaneously apply the above two methods to the non-uniform case of P3 with fixed power levels, and return the better one of the two results, we will get an approx. algorithm (Alg. 2) of factor 1 2 (1− 1 e ) according to [23]. The time complexity of Alg. 2 is also O(MN3 ). C. Approximation Algorithm for P3 We design a probably good approximation algorithm, namely TCA, in Alg. 3 that simultaneously determines C ′ and H. Denote the set {1, 2, ..., L} by H; denote by Ii a row vector where the i-th element is 1 and all of the other elements are zeros, i.e., Ii = (0, 0, ..., 1, ..., 0). We use H[ci] to represent the power level of a candidate location ci . Before giving some explanations about TCA, we first consider the following variant of the P3 problem (VP3 ): For each candidate location ci , we are given L chargers with constant but exactly different power levels, i.e., the power levels of these Algorithm 3 Two-Choice-based Approx. Alg. for P3 (TCA) Input: C, S, and B Output: C ′ and H 1: Z ← C × H 2: Z1 ← ∅, H1 ← 0 3: while B ≥ min (ci ,hk )∈Z\Z1 p(hk) + ∑ (ci ,hk )∈Z1 p(hk) do 4: (c, h) ← arg max (c,h)∈Z\Z1, ∑ (ci ,hk )∈Z1∪{(c,h)} p(hk )≤B Q(Z1 ∪ {(c, h)}) − Q(Z1) 5: Z1 ← Z1 ∪ {(c, h)} 6: if H1[c] < h then H1[c] ← h 7: end while 8: (C ′ 1 , H1) ←RemoveDuplicationAndUtilize(C,S, B, H1) 9: Z2 ← ∅, H2 ← 0 10: while B ≥ min (ci ,hk )∈Z\Z2 p(hk) + ∑ (ci ,hk )∈Z2 p(hk) do 11: (c, h) ← arg max (c,h)∈Z\Z2, ∑ (ci ,hk )∈Z2∪{(c,h)} p(hk )≤B Q(Z2∪{(c,h)})−Q(Z2) p(h) 12: Z2 ← Z2 ∪ {(c, h)} 13: if H2[c] < h then H2[c] ← h 14: end while 15: (C ′ 2 , H2) ←RemoveDuplicationAndUtilize(C,S, B, H2) 16: return arg max (C′ ,H)∈{(C ′ 1 ,H1),(C ′ 2 ,H2)} Q(C ′ , H) 17: 18: Sub-procedure: RemoveDuplicationAndUtilize 19: Input: C, S, B, and H 20: Output: C ′ and H 21: C ′ ← ∅, B ′ ← 0 22: for all H[ci] > 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 total 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)