ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2845 20 30 40 50 60 70 80 8 CONCLUSION 50 1.521.62 1.661.61T 1.71 1.76 1.76 The explosive growth of mobile devices and their increasing 100 1.431.55 1.591.59 1.61 1.58 6 functionality have made them a vital part of our lives. 150 1.401.41 1.57 1.53 1.601.53 1.62 Determining how to replenish these energy-hungry devices (a)The ratio for ISCA in simulations so as to prolong their lifespans and support sustainable operations is of the utmost importance.In this paper,we 20 30 40 50 60 M 70 80 consider the wireless charging service provision using 50 1.56 1.53 1.57 1.73 1.59 1.56 1.63 mobile chargers and study the itinerary selection and charg- 100 1.771.831.971.831.881.89 1.87 ing association problem,i.e.,the ISCA problem.We prove 150 1.86 2.001.972.012.042.06 2.03 that ISCA is NP-complete.For the case in which each itiner- (b)The ratio for ISCA-MP in simulations ary can only be used once,we devise an O(In M)-approxi- mation algorithm and a practical heuristic algorithm;for the Fig.11.The theoretical approximation ratios of GSA for ISCA and PDA case in which each itinerary can be used multiple times,we for ISCA-MP are O(In M)and 10,respectively.We see that the practical performance of GSA and PDA is better than numerical analysis.(For ref- design a 10-approximation algorithm based on the Primal- erence,m50=3.91,ln100=4.61,andm150=5.01.) Dual schema.Real field experiments and extensive evalua- tions have confirmed the performance of our algorithms similar observations as in Fig.9.One thing worth mention- compared with the optimal fractional solutions. ing is that,unlike in Fig.9,PDA performs much better than There are a number of research directions we plan to MMGSA.For example,in Fig.10a,PDA is 197 percent at study following this work.The first is to investigate the case most and 186 percent on average of OPT,while MMGSA is where candidate charging itineraries are not fixed.The sec- 297 percent at most and 273 percent on average of OPT. ond is to incorporate radiation safety into our charging This is because,PDA employs primal-dual schema to cope framework and make sure that no physical point receives with the intractability of ISCA-MP,while MMGSA greedily an electromagnetic radiation that is higher than the safety picks charging itineraries.We also find that for the same set- threshold for human beings. ting (e.g.,Fig.9a and Fig.10a),PDA performs better than GSA.The main reason is that PDA can use each itinerary ACKNOWLEDGMENTS multiple times,giving it more opportunities to optimize the This work was supported in part by NSFC (61502224, objection function. 61472181,61472185,61321491),China Postdoctoral Science As we claimed in Section 5.6,though the approximation Foundation (2015M570434,2016T90444),CCF-Tencent ratios of GSA and PDA are O(In M)and 10,respectively,in Open Research Fund (AGR20160104),Jiangsu NSF reality,they work much better than the bounds.Fig.11 con- (BK20151392,BK20151390),and Collaborative Innovation firms our claim.Fig.11 shows theratio for ISCA and the Center of Novel Software Technology and Industrialization. ratio for ISCA-MP under varying numbers of charging itineraries and rechargeable devices.For GSA,the theoretical REFERENCES approximation ratio is O(In M)(for reference,In50 =3.91, [1]A.Kansal,J.Hsu,S.Zahedi,and M.B.Srivastava,"Power man- In100=4.61,and In150=5.01),while the ratio in simula- agement in energy harvesting sensor networks," ACM Trans. tions is no more than 1.76.Similarly,for PDA,the theoretical Embedded Comput.Syst.,vol.6,Sep.2007,Art.no.32. approximation ratio is 10,while theratio in simulations is 21 A.Dunkels,F.Osterlind,and Z.He,"An adaptive communication architecture for wireless sensor networks,"in Proc.5th Int.Conf. no more than 2.06.We also have examined extremely large Embedded Netw.Sensor Syst.,2007,pp.335-349. instances of ISCA and ISCA-MP,in which the results are 31 B.Tong,G.Wang,W.Zhang,and C.Wang,"Node reclamation always consistent with our numerical analysis. and replacement for long-lived sensor networks,"IEEE Trans. Parallel Distrib.Syst.,vol.22,no.9,pp.1550-1563,Sep.2011. All of the proposed algorithms are very time-efficient in our 4] A.Kurs,A.Karalis,R.Moffatt,J.D.Joannopoulos,P.Fisher,and simulations.For example,when N=80 and M 100,the run- M.Soljacic,"Wireless power transfer via strongly coupled mag- ning time of GSA,MGSA,PDA,and MMGSA are 0.17,1.36, netic resonances,"Science,vol.317,no.5834,pp.83-86,2007. 5] K.Kang,Y.S.Meng,J.Breger,C.P.Grey,and G.Ceder, 11.68,and 2.68,respectively.We note that MGSA achieves a "Electrodes with high power and high capacity for rechargeable better solution than GSA for ISCA,but that its running time is lithium batteries,"Science,vol.311,no.5763,pp.977-980,2006. slightly longer.Similarly,MMGSA achieves a worse solution Androidcentral,(2015,Jul).[Onlinel.Available:http://www.android- central.com/these-android-phones-can-handle-wireless-charging/ than PDA for ISCA-MP,but its running time is shorter. 7 Tesla motors,(2015,Jul.).[Online].Available:http://www Key observations are summarized as follows.First, teslamotors.com/ although GSA has theoretical performance guarantee,MGSA 8] SHARP,(2015,Jul.).[Onlinel.Available:http://www. performs better than GSA for ISCA.Second,PDA employs friendsofcrc.ca/Projects/SHARP/sharp.html 9 Wireless charging market,(2015,Jul.).[Onlinel.Available:http:/ the primal-dual schema to cope with the intractability of www.marketsandmarkets.com/PressReleases/wireless-chargingasp ISCA-MP,and thus gives better results than MMGSA.Third, [10]Y.Peng,Z.Li,W.Zhang,and D.Qiao,"Prolonging sensor net- for the same problem setting,PDA achieves better results work lifetime through wireless charging,"in Proc.IEEE 31st IEEE Real-Time Syst.Symp.,2010,pp.129-139. than GSA;this is because PDA can use each itinerary multiple [11]Y.Shi,L.Xie,Y.Hou,and H.Sherali,"On renewable sensor net times,giving it more opportunities to optimize the objective works with wireless energy transfer,"in Proc.IEEE INFOCOM function.Last,all of the proposed algorithms are time-effi- 2011,P咒.1350-1358. cient.GSA is within 176 percent of OPT in ISCA,and PDA is [12]L.Xie,Y.Shi,Y.T.Hou,W.Lou,H.D.Sherali,and S.F.Midkiff within 206 percent of OPT in ISCA-MP throughout the simu- "On renewable sensor networks with wireless energy transfer The multi-node case,"in Proc.9th Annu.IEEE Commun.Soc.Conf lations,validating our theoretical analyses. Sensor Mesh Ad Hoc Commun.Netw,2012,pp.10-18.similar observations as in Fig. 9. One thing worth mention￾ing is that, unlike in Fig. 9, PDA performs much better than MMGSA. For example, in Fig. 10a, PDA is 197 percent at most and 186 percent on average of OPT, while MMGSA is 297 percent at most and 273 percent on average of OPT. This is because, PDA employs primal-dual schema to cope with the intractability of ISCA-MP, while MMGSA greedily picks charging itineraries. We also find that for the same set￾ting (e.g., Fig. 9a and Fig. 10a), PDA performs better than GSA. The main reason is that PDA can use each itinerary multiple times, giving it more opportunities to optimize the objection function. As we claimed in Section 5.6, though the approximation ratios of GSA and PDA are Oðln MÞ and 10, respectively, in reality, they work much better than the bounds. Fig. 11 con- firms our claim. Fig. 11 shows the GSA OPT ratio for ISCA and the PDA OPT ratio for ISCA-MP under varying numbers of charging itineraries and rechargeable devices. For GSA, the theoretical approximation ratio is OðlnMÞ (for reference, ln50 =3.91, ln100 = 4.61, and ln150 = 5.01), while the GSA OPT ratio in simula￾tions is no more than 1.76. Similarly, for PDA, the theoretical approximation ratio is 10, while the PDA OPT ratio in simulations is no more than 2.06. We also have examined extremely large instances of ISCA and ISCA-MP, in which the results are always consistent with our numerical analysis. All of the proposed algorithms are very time-efficient in our simulations. For example, when N ¼ 80 and M ¼ 100, the run￾ning time of GSA, MGSA, PDA, and MMGSA are 0.17, 1.36, 11.68, and 2.68, respectively. We note that MGSA achieves a better solution than GSA for ISCA, but that its running time is slightly longer. Similarly, MMGSA achieves a worse solution than PDA for ISCA-MP, but its running time is shorter. Key observations are summarized as follows. First, although GSA has theoretical performance guarantee, MGSA performs better than GSA for ISCA. Second, PDA employs the primal-dual schema to cope with the intractability of ISCA-MP, and thus gives better results than MMGSA. Third, for the same problem setting, PDA achieves better results than GSA; this is because PDA can use each itinerary multiple times, giving it more opportunities to optimize the objective function. Last, all of the proposed algorithms are time-effi- cient. GSA is within 176 percent of OPT in ISCA, and PDA is within 206 percent of OPT in ISCA-MP throughout the simu￾lations, validating our theoretical analyses. 8 CONCLUSION The explosive growth of mobile devices and their increasing functionality have made them a vital part of our lives. Determining how to replenish these energy-hungry devices so as to prolong their lifespans and support sustainable operations is of the utmost importance. In this paper, we consider the wireless charging service provision using mobile chargers and study the itinerary selection and charg￾ing association problem, i.e., the ISCA problem. We prove that ISCA is NP-complete. For the case in which each itiner￾ary can only be used once, we devise an Oðln MÞ-approxi￾mation algorithm and a practical heuristic algorithm; for the case in which each itinerary can be used multiple times, we design a 10-approximation algorithm based on the Primal￾Dual schema. Real field experiments and extensive evalua￾tions have confirmed the performance of our algorithms compared with the optimal fractional solutions. There are a number of research directions we plan to study following this work. The first is to investigate the case where candidate charging itineraries are not fixed. The sec￾ond is to incorporate radiation safety into our charging framework and make sure that no physical point receives an electromagnetic radiation that is higher than the safety threshold for human beings. ACKNOWLEDGMENTS This work was supported in part by NSFC (61502224, 61472181, 61472185, 61321491), China Postdoctoral Science Foundation (2015M570434, 2016T90444), CCF-Tencent Open Research Fund (AGR20160104), Jiangsu NSF (BK20151392, BK20151390), and Collaborative Innovation Center of Novel Software Technology and Industrialization. REFERENCES [1] A. Kansal, J. Hsu, S. Zahedi, and M. B. Srivastava, “Power man￾agement in energy harvesting sensor networks,” ACM Trans. Embedded Comput. Syst., vol. 6, Sep. 2007, Art. no. 32. [2] A. Dunkels, F. Osterlind, and Z. He, “An adaptive communication € architecture for wireless sensor networks,” in Proc. 5th Int. Conf. Embedded Netw. Sensor Syst., 2007, pp. 335–349. [3] B. Tong, G. Wang, W. Zhang, and C. Wang, “Node reclamation and replacement for long-lived sensor networks,” IEEE Trans. Parallel Distrib. Syst., vol. 22, no. 9, pp. 1550–1563, Sep. 2011. [4] A. Kurs, A. Karalis, R. Moffatt, J. D. Joannopoulos, P. Fisher, and M. Soljacic, “Wireless power transfer via strongly coupled mag￾netic resonances,” Science, vol. 317, no. 5834, pp. 83–86, 2007. [5] K. Kang, Y. S. Meng, J. Breger, C. P. Grey, and G. Ceder, “Electrodes with high power and high capacity for rechargeable lithium batteries,” Science, vol. 311, no. 5763, pp. 977–980, 2006. [6] Androidcentral, (2015, Jul.). [Online]. Available: http://www.android￾central.com/these-android-phones-can-handle-wireless-charging/ [7] Tesla motors, (2015, Jul.). [Online]. Available: http://www. teslamotors.com/ [8] SHARP, (2015, Jul.). [Online]. Available: http://www. friendsofcrc.ca/Projects/SHARP/sharp.html [9] Wireless charging market, (2015, Jul.). [Online]. Available: http:// www.marketsandmarkets.com/PressReleases/wireless-charging.asp [10] Y. Peng, Z. Li, W. Zhang, and D. Qiao, “Prolonging sensor net￾work lifetime through wireless charging,” in Proc. IEEE 31st IEEE Real-Time Syst. Symp., 2010, pp. 129–139. [11] Y. Shi, L. Xie, Y. Hou, and H. Sherali, “On renewable sensor net￾works with wireless energy transfer,” in Proc. IEEE INFOCOM 2011, pp. 1350–1358. [12] 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. 9th Annu. IEEE Commun. Soc. Conf. Sensor Mesh Ad Hoc Commun. Netw., 2012, pp. 10–18. Fig. 11. The theoretical approximation ratios of GSA for ISCA and PDA for ISCA-MP are Oðln MÞ and 10, respectively. We see that the practical performance of GSA and PDA is better than numerical analysis. (For ref￾erence, ln 50 ¼ 3:91; ln 100 ¼ 4:61, and ln 150 ¼ 5:01.) ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2845