2834 EEE TRANSACTIONS ON MOBILE COMPUTING,VOL.16.NO.10,OCTOBER 2017 Rechargeable Home device To the best of our knowledge,we are the first to propose mobile charging with candidate itineraries.We evaluate the proposed algorithms using both real field experiments and extensive simulations.We summarize our contributions Itinerary s.Ll Itinerary here as follows. We identify the itinerary selection and charging Itinerary 0s association problem and prove that it is NP. complete. Home Home We design approximation algorithms and efficient station of r station of ra heuristics for both ISCA and ISCA-MP. Physical roads Real field experiments and extensive simulations are Fig.1.Mobile charging with fixed candidate itineraries conducted to confirm our theoretical findings. The remainder of the paper is organized as follows.We approach of mobile chargers,i.e.,mobile chargers can only discuss related work in Section 2.We motivate our problem travel along existing infrastructures,e.g.,bridges and roads. and give its formulation in Section 3.We present the algo- This motivates us to propose a new charging paradigm: rithms to ISCA and ISCA-MP in Sections 4 and 5,respec- charging with fixed candidate itineraries.A charger could be tively.Field experiments and extensive simulations are integrated with a bus or some other moving tool that travels presented in Sections 6 and 7,respectively.We conclude the along a fixed path into a single entity,which would make it paper in Section 8. easy to deploy and install.Specifically,we want to provide wireless charging service in a two-dimensional(2-D)target 2 RELATED WORK area.Based on historical data analysis and investigation,we Since its inception,wireless power transfer has attracted can predict the locations of potential rechargeable devices, much attention.Existing studies can be classified into two and then preselect a number of candidate itineraries.These broad types:stationary and mobile chargers. itineraries are used by mobile chargers to deliver energy to For stationary chargers,He et al.[16]proposed point and rechargeable devices.Each mobile charger starts from the path provisioning for charger placement based on the Intel home station of an itinerary with a limited battery [11],[121, wireless identification and sensing platform.Tong et al.[23] travels along the itinerary,transfers energy to some devices, found that a charger can transfer energy to multiple devices and finally,returns to the home station for battery replen- simultaneously without significantly reducing the received ishment or replacement [21].Fig.1 shows an example con- energy at each device.Zhang et al.[15]considered charger sisting of three itineraries and six rechargeable devices. placement with adjustable power levels and power budget. Wireless power transfer is not perfect,i.e.,there is energy Dai et al.[17]studied how to obtain the maximum electro- loss when a mobile charger transfers energy to a device. magnetic radiation point under a given charger placement. Furthermore,the movement of each charger also costs Radiation safety and capacity restrictions are taken into energy.Therefore,the energy consumed in the system can account in [24],[25]. be classified into three types:loss-energy,which varies For mobile chargers,existing studies have considered depending on charging distance and duration,movement- various decision variables and objectives.To maximize net- energy,which is used by mobile chargers for moving,and work lifetime,charging sequence and packet routing are payload-energy,which is eventually received by rechargeable optimized in [101,[18],while Shu et al.[26]optimized the devices.Given a fixed payload-energy,the goal of this same objective under varying charger velocities.To maxi- paper is to minimize the sum of movement-energy and mize the ratio of the charger's vacation time(i.e.,time spent loss-energy.To achieve this,we must strategically select a at the home service station)over the cycle time,travelling subset of the candidate itineraries (i.e.,itinerary selection) path and stop schedules are optimized in [11],[121.Fu and determine which itinerary is responsible for charging et al.[13]optimized the charger stop locations and dura- each device (i.e.,charging association). tions for minimizing the total charging delay of all sensors. The Itinerary Selection and Charging Association (ISCA) Wang et al.[21]proposed NDN-based energy monitoring problem can be briefly stated as follows:Given a set of and reporting protocols with a special focus on scheduling rechargeable devices and a set of candidate charging itiner-mobile chargers for multiple concurrent emergencies. aries,we question how to find an itinerary selection and a Zhang et al.[14]utilized collaboration between mobile corresponding charging association solution to minimize chargers to improve the energy usage effectiveness.To the sum of movement-energy and loss-energy so that every simultaneously minimize charger travel distance and charg- device gets its required energy.In this paper,we prove that ing delay,He et al.[19]proposed synchronizing charging this problem is NP-complete by a reduction from the set sequences based on multiple nested tours,and Fu et al.[27] cover problem [221.For the case in which an itinerary can employed the same technique to simultaneously minimize only be used once,we propose an O(In M)-approximation charger travel distance and charging delay.Given the heter- algorithm and a practical heuristic algorithm,where M is ogenous charging frequencies of sensors,scheduling multi- the number of rechargeable devices;for the general case in ple charging rounds to minimize total moving distance of which an itinerary may be used multiple times,we propose mobile chargers is studied in [281.Nikoletseas et al.[29]pro- an approximation algorithm of factor 10 based on the Pri- posed the peer-to-peer interactive charging problem where mal-Dual schema. mobile entities are both energy transmitters and harvesters.approach of mobile chargers, i.e., mobile chargers can only travel along existing infrastructures, e.g., bridges and roads. This motivates us to propose a new charging paradigm: charging with fixed candidate itineraries. A charger could be integrated with a bus or some other moving tool that travels along a fixed path into a single entity, which would make it easy to deploy and install. Specifically, we want to provide wireless charging service in a two-dimensional (2-D) target area. Based on historical data analysis and investigation, we can predict the locations of potential rechargeable devices, and then preselect a number of candidate itineraries. These itineraries are used by mobile chargers to deliver energy to rechargeable devices. Each mobile charger starts from the home station of an itinerary with a limited battery [11], [12], travels along the itinerary, transfers energy to some devices, and finally, returns to the home station for battery replen￾ishment or replacement [21]. Fig. 1 shows an example con￾sisting of three itineraries and six rechargeable devices. Wireless power transfer is not perfect, i.e., there is energy loss when a mobile charger transfers energy to a device. Furthermore, the movement of each charger also costs energy. Therefore, the energy consumed in the system can be classified into three types: loss-energy, which varies depending on charging distance and duration, movement￾energy, which is used by mobile chargers for moving, and payload-energy, which is eventually received by rechargeable devices. Given a fixed payload-energy, the goal of this paper is to minimize the sum of movement-energy and loss-energy. To achieve this, we must strategically select a subset of the candidate itineraries (i.e., itinerary selection) and determine which itinerary is responsible for charging each device (i.e., charging association). The Itinerary Selection and Charging Association (ISCA) problem can be briefly stated as follows: Given a set of rechargeable devices and a set of candidate charging itiner￾aries, we question how to find an itinerary selection and a corresponding charging association solution to minimize the sum of movement-energy and loss-energy so that every device gets its required energy. In this paper, we prove that this problem is NP-complete by a reduction from the set cover problem [22]. For the case in which an itinerary can only be used once, we propose an Oðln MÞ-approximation algorithm and a practical heuristic algorithm, where M is the number of rechargeable devices; for the general case in which an itinerary may be used multiple times, we propose an approximation algorithm of factor 10 based on the Pri￾mal-Dual schema. To the best of our knowledge, we are the first to propose mobile charging with candidate itineraries. We evaluate the proposed algorithms using both real field experiments and extensive simulations. We summarize our contributions here as follows. We identify the itinerary selection and charging association problem and prove that it is NP￾complete. We design approximation algorithms and efficient heuristics for both ISCA and ISCA-MP. Real field experiments and extensive simulations are conducted to confirm our theoretical findings. The remainder of the paper is organized as follows. We discuss related work in Section 2. We motivate our problem and give its formulation in Section 3. We present the algo￾rithms to ISCA and ISCA-MP in Sections 4 and 5, respec￾tively. Field experiments and extensive simulations are presented in Sections 6 and 7, respectively. We conclude the paper in Section 8. 2 RELATED WORK Since its inception, wireless power transfer has attracted much attention. Existing studies can be classified into two broad types: stationary and mobile chargers. For stationary chargers, He et al. [16] proposed point and path provisioning for charger placement based on the Intel wireless identification and sensing platform. Tong et al. [23] found that a charger can transfer energy to multiple devices simultaneously without significantly reducing the received energy at each device. Zhang et al. [15] considered charger placement with adjustable power levels and power budget. Dai et al. [17] studied how to obtain the maximum electro￾magnetic radiation point under a given charger placement. Radiation safety and capacity restrictions are taken into account in [24], [25]. For mobile chargers, existing studies have considered various decision variables and objectives. To maximize net￾work lifetime, charging sequence and packet routing are optimized in [10], [18], while Shu et al. [26] optimized the same objective under varying charger velocities. To maxi￾mize the ratio of the charger’s vacation time (i.e., time spent at the home service station) over the cycle time, travelling path and stop schedules are optimized in [11], [12]. Fu et al. [13] optimized the charger stop locations and dura￾tions for minimizing the total charging delay of all sensors. Wang et al. [21] proposed NDN-based energy monitoring and reporting protocols with a special focus on scheduling mobile chargers for multiple concurrent emergencies. Zhang et al. [14] utilized collaboration between mobile chargers to improve the energy usage effectiveness. To simultaneously minimize charger travel distance and charg￾ing delay, He et al. [19] proposed synchronizing charging sequences based on multiple nested tours, and Fu et al. [27] employed the same technique to simultaneously minimize charger travel distance and charging delay. Given the heter￾ogenous charging frequencies of sensors, scheduling multi￾ple charging rounds to minimize total moving distance of mobile chargers is studied in [28]. Nikoletseas et al. [29] pro￾posed the peer-to-peer interactive charging problem where mobile entities are both energy transmitters and harvesters. Fig. 1. Mobile charging with fixed candidate itineraries. 2834 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017