IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.16.NO.10,OCTOBER 2017 2833 Optimizing Itinerary Selection and Charging Association for Mobile Chargers Sheng Zhang,Member,IEEE,Zhuzhong Qian,Member,IEEE,Jie Wu,Fellow,IEEE, Fanyu Kong,and Sanglu Lu,Member,IEEE Abstract-Wireless power transfer provides a promising way to extend the battery lifetime of our energy-hungry rechargeable devices Previous studies have envisioned using mobile vehicles/robots/drones equipped with high capacity batteries as mobile chargers to replenish those devices,and they mainly focus on maximizing network lifetime,optimizing efficiency of charging scheduling,minimizing total charging delay,etc.However,existing methods may be insufficient and inflexible when the energy consumption of rechargeable devices fluctuates over time,or when rechargeable devices are sparse.In this paper,we consider how to efficiently provide flexible wireless charging using pre-planned charging itineraries.We present the Itinerary Selection and Charging Association(ISCA)problem: given a set of rechargeable devices and a set of candidate charging itineraries,how can we select itineraries and determine a corresponding charging association to minimize the amount of energy which is due to mobile chargers'movement and wireless charging loss,so that every device gets its required energy.We prove that ISCA is NP-complete by reducing the set cover problem to it. We start solving this problem by first looking at the case in which an itinerary can only be used once,and we propose an algorithm with approximation ratio of O(In M)and a practical heuristic algorithm,where M is the number of devices.For the general case in which an itinerary may be used multiple times,we propose an approximation algorithm of factor 10 using the Primal-Dual schema.Evaluations results from real field experiments and extensive simulations show that the proposed algorithms have near-optimal performance and PDA reduces the amount of wasted energy by up to 65 percent compared with a set cover-based algorithm. Index Terms-Wireless power transfer,approximation algorithm,Primal-Dual schema 1 INTRODUCTION Wulty f e ov t away,with approximately 40 percent efficiency.Kang et al.[5]experimentally demonstrated that rechargeable are battery-powered they remain operational only for a lim-lithium batteries can have high energy densities and high ited amount of time before connecting to wired chargers.To charge/discharge capabilities.These two technologies extend the lifetime of these energy-hungry devices,and together provide a promising paradigm to extend the bat- thus enhance their usability,various approaches from dif- tery lifetimes of our daily-use devices and have led to the ferent perspectives have been proposed,including energy development of several commercial products.30+kinds of harvesting [1],which extracts energy from the environment popular phones are beginning to embrace wireless charg- (e.g.,solar,wind,and vibration),energy conservation [21, ing [61,and even vehicles [7]and unmanned planes [8]are which focuses on slowing down the energy consumption now supporting wireless charging.It is predicted that this rate and battery replacement [3].However,energy harvest- market will be worth $13.78 billion by 2020 [9]. ing remains limited in practice due to its partial predictabil- With these enabling technologies,existing studies [101, ity and the relatively large size of harvesting panels;energy [111,[12],[13],[14],[15]proposed periodically employing conservation cannot compensate for depletion;battery static or mobile chargers to replenish rechargeable devices, replacement is costly and impractical. such as RFID tags,sensors,smartphones,tablets,and cars, Recently,Kurs et al.[4]experimentally demonstrated for the purpose of maximizing the lifetime of the underlying that energy can be efficiently transmitted between magneti- network [10],optimizing the efficiency of charging schedul- cally resonant objects without any interconnecting conduc- ing [111,[12],minimizing total charging delay [13],etc. tors,e.g.,powering a 60 W light bulb,which is two meters Most of these studies fit comfortably under one of two head- ings:stationary deployment [15],[161,[17],which focuses on optimizing the deployment of fixed chargers,or mobile S.Zhang,Z.Z.Qian,and S.L.Lu are with the State Key Laboratory for charging[10l,[11],[12l,[13],[14l,[181,[19],[20,which Novel Software Technology,Nanjing UIniversity,Nanjing 210023,China. E-mail:(sheng,qzz,sanglu@nju.edu.cn. focuses on optimizing charging sequence and/or duration. I.Wu is with the Department of Computer and Information Sciences, However,as we will explain in Section 3,existing methods Temple UIniversity,Philadelphia,PA 19122.E-mail:jiewu@temple.edu. may be insufficient and inflexible when the energy con- F.Y.Kong is with Ant Financial,China.E-mail:njukongfy@gmail.com. sumption of rechargeable devices fluctuates over time or Manuscript received 22 Apr.2016;revised 10 Nov.2016;accepted 12 Dec. when rechargeable devices are sparse. 2016.Date of publication 19 Dec.2016;date of current version 29 Aug.2017. For information on obtaining reprints of this article,please send e-mail to: We observed that in some applications(e.g.,underwater reprints@ieee.org,and reference the Digital Object Identifier below. monitoring and agricultural rain-fed farming),rechargeable Digital Object Identifier no.10.1109/TMC.2016.2641446 devices are deployed in environments that prohibit the 1s96g239726E5e8g722ePena6品b52b686m2c%恶RsanOptimizing Itinerary Selection and Charging Association for Mobile Chargers Sheng Zhang, Member, IEEE, Zhuzhong Qian, Member, IEEE, Jie Wu, Fellow, IEEE, Fanyu Kong, and Sanglu Lu, Member, IEEE Abstract—Wireless power transfer provides a promising way to extend the battery lifetime of our energy-hungry rechargeable devices. Previous studies have envisioned using mobile vehicles/robots/drones equipped with high capacity batteries as mobile chargers to replenish those devices, and they mainly focus on maximizing network lifetime, optimizing efficiency of charging scheduling, minimizing total charging delay, etc. However, existing methods may be insufficient and inflexible when the energy consumption of rechargeable devices fluctuates over time, or when rechargeable devices are sparse. In this paper, we consider how to efficiently provide flexible wireless charging using pre-planned charging itineraries. We present the Itinerary Selection and Charging Association (ISCA) problem: given a set of rechargeable devices and a set of candidate charging itineraries, how can we select itineraries and determine a corresponding charging association to minimize the amount of energy which is due to mobile chargers’ movement and wireless charging loss, so that every device gets its required energy. We prove that ISCA is NP-complete by reducing the set cover problem to it. We start solving this problem by first looking at the case in which an itinerary can only be used once, and we propose an algorithm with approximation ratio of Oðln MÞ and a practical heuristic algorithm, where M is the number of devices. For the general case in which an itinerary may be used multiple times, we propose an approximation algorithm of factor 10 using the Primal-Dual schema. Evaluations results from real field experiments and extensive simulations show that the proposed algorithms have near-optimal performance and PDA reduces the amount of wasted energy by up to 65 percent compared with a set cover-based algorithm. Index Terms—Wireless power transfer, approximation algorithm, Primal-Dual schema Ç 1 INTRODUCTION WIRELESS devices have greatly improved the overall quality of life over the past few years. Because they are battery-powered they remain operational only for a lim￾ited amount of time before connecting to wired chargers. To extend the lifetime of these energy-hungry devices, and thus enhance their usability, various approaches from dif￾ferent perspectives have been proposed, including energy harvesting [1], which extracts energy from the environment (e.g., solar, wind, and vibration), energy conservation [2], which focuses on slowing down the energy consumption rate and battery replacement [3]. However, energy harvest￾ing remains limited in practice due to its partial predictabil￾ity and the relatively large size of harvesting panels; energy conservation cannot compensate for depletion; battery replacement is costly and impractical. Recently, Kurs et al. [4] experimentally demonstrated that energy can be efficiently transmitted between magneti￾cally resonant objects without any interconnecting conduc￾tors, e.g., powering a 60 W light bulb, which is two meters away, with approximately 40 percent efficiency. Kang et al. [5] experimentally demonstrated that rechargeable lithium batteries can have high energy densities and high charge/discharge capabilities. These two technologies together provide a promising paradigm to extend the bat￾tery lifetimes of our daily-use devices and have led to the development of several commercial products. 30+ kinds of popular phones are beginning to embrace wireless charg￾ing [6], and even vehicles [7] and unmanned planes [8] are now supporting wireless charging. It is predicted that this market will be worth $13.78 billion by 2020 [9]. With these enabling technologies, existing studies [10], [11], [12], [13], [14], [15] proposed periodically employing static or mobile chargers to replenish rechargeable devices, such as RFID tags, sensors, smartphones, tablets, and cars, for the purpose of maximizing the lifetime of the underlying network [10], optimizing the efficiency of charging schedul￾ing [11], [12], minimizing total charging delay [13], etc. Most of these studies fit comfortably under one of two head￾ings: stationary deployment [15], [16], [17], which focuses on optimizing the deployment of fixed chargers, or mobile charging [10], [11], [12], [13], [14], [18], [19], [20], which focuses on optimizing charging sequence and/or duration. However, as we will explain in Section 3, existing methods may be insufficient and inflexible when the energy con￾sumption of rechargeable devices fluctuates over time or when rechargeable devices are sparse. We observed that in some applications (e.g., underwater monitoring and agricultural rain-fed farming), rechargeable devices are deployed in environments that prohibit the S. Zhang, Z.Z. Qian, and S.L. Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, Nanjing 210023, China. E-mail: {sheng, qzz, sanglu}@nju.edu.cn. J. Wu is with the Department of Computer and Information Sciences, Temple University, Philadelphia, PA 19122. E-mail: jiewu@temple.edu. F.Y. Kong is with Ant Financial, China. E-mail: njukongfy@gmail.com. Manuscript received 22 Apr. 2016; revised 10 Nov. 2016; accepted 12 Dec. 2016. Date of publication 19 Dec. 2016; date of current version 29 Aug. 2017. For information on obtaining reprints of this article, please send e-mail to: reprints@ieee.org, and reference the Digital Object Identifier below. Digital Object Identifier no. 10.1109/TMC.2016.2641446 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017 2833 1536-1233
2016 IEEE. Personal use is permitted, but republication/redistribution requires IEEE permission. See http://www.ieee.org/publications_standards/publications/rights/index.html for more information.