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 < PT . For 1 ≤ i ≤ T, d(ci , si) ≤ D(1); for any i , j, d(ci , sj) > 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