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