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-3490 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