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%恶Rsan
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ð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 limited 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 different 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 harvesting remains limited in practice due to its partial predictability 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 magnetically resonant objects without any interconnecting conductors, 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 battery 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 charging [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 scheduling [11], [12], minimizing total charging delay [13], etc. Most of these studies fit comfortably under one of two headings: 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 consumption 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.
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 replenishment or replacement [21]. Fig. 1 shows an example consisting 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, movementenergy, 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 itineraries, 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 Primal-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 NPcomplete. 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 algorithms to ISCA and ISCA-MP in Sections 4 and 5, respectively. 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 electromagnetic 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 network 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 maximize 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 durations 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 charging 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 heterogenous charging frequencies of sensors, scheduling multiple charging rounds to minimize total moving distance of mobile chargers is studied in [28]. Nikoletseas et al. [29] proposed 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
ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2835 Wang et al.[30]designed a hybrid framework which com-when a target area contains very few devices,we can bines solar energy harvesting for cluster heads and wireless arrange chargers less frequently. charging for normal sensor nodes.Chen et al.[31]investi- gated the problem of maximizing the number of nodes a 3.2 Charging Model and Itinerary path can charge within a given budget (e.g.,in terms of We consider a network composed of M stationary recharge- time,energy). able devices,denoted by the sets and distributed In contrast,we focus on employing mobile chargers with in a two-dimensional plane.The energy requirement of fixed candidate itineraries to periodically replenish each device is E,i.e.,when a mobile charger transfers rechargeable devices with the goal of minimizing unneces- energy to a device,the device must receive E units of sary energy wasted,i.e.,movement-energy and loss-energy. energy. The optimization techniques are inspired by two opti- In some applications,rechargeable devices are mization problems,e.g.,vehicle routing problem deployed in environments that prohibit the approach of (VRP)[32]and facility location problem(FLP)[33].Given mobile chargers.Mobile chargers can only travel along a road network,VRP is to find the optimal itineraries for existing infrastructures like bridges and roads.Besides,a multiple vehicles to traverse so that a given set of custom- charger could be integrated with a bus or some other ers are delivered.FLP is to find the optimal placement of moving tool,which travels along a fixed path,into a sin- facilities to minimize transportation costs.Although their gle entity,making it easy to deploy and install.Therefore, solutions greatly inspired us,ISCA differs from them in we assume that there is a set of N candidate charging two main aspects:(a)the cost of an itinerary in ISCA is itineraries,denoted by the setR Without caus determined by not only its length,but also by the devices ing confusion,we also use ri to denote the mobile charger that will be charged by the itinerary and(b)ISCA will that travels along itinerary ri. simultaneously select a subset of given itineraries and A mobile charger ri has a limited battery with capacity decide the association relationship between itineraries Bi.When a charger transfers energy to a device,the and devices. charger's transmission power is P.Thus,the charging capacity of ri,in terms of charging time,can be denoted by 3 MOTIVATION AND PROBLEM 3.1 Motivation Ti=Bi/P. (1) Wireless power transfer has been studied extensively We consider that the movement of each charger is sup- because of its wide use in recent years.It can be used to ported by petrol,and we assume the amount of move- periodically deliver energy to rechargeable wireless sensor ment-energy along itinerary ri,denoted by ci,is dictated by networks and can also facilitate the charging of our daily- the physical length of ri. use tools like electric toothbrushes and vacuum cleaner We assume an omnidirectional wireless power transfer robots.In these application scenarios,we may wish that we model in which the amount of received power at each can use wireless charging just like cellular networks.In fact, device is only dominated by the transmission power of the this can be achieved by deploying multiple fixed wireless charger and the distance between them.As indicated by the chargers to cover an area of interest.However,this method experiments in [16],the power pij received by device sj may be insufficient in the scenarios below: from charger ri can be quantified by an empirical model as follows: Bursty demands.The number of rechargeable devices and/or the energy consumption of these devices ap 4≤D, may fluctuate over time.If we place a number of j+b)2 (2) fixed chargers,they may be unable to satisfy the 0 dij>D. bursty demands for charging. Here,constants a and b are determined by environments Sparse devices.There may be not always many devi- and hardware of chargers and devices.dij is the physical ces within the area of interest.For areas with sparse distance between r;and sj.D is the maximum cover dis- devices,deploying fixed chargers may be not cost- efficient;instead,mobile chargers with carefully tance of each charger.2 planned itineraries could be appropriate. We use ti;to represent the time for charger ri to charge sj to its full requirement,i.e.,sj should obtain E units of Service decoupling.In the future,there may be many energy after being charged by ri.We have charging service providers that compete with each other.Each service provider will have several charg- EE(b+dij)2 ing itineraries passing through the area of interest. tii= (3) P衍 aP We may want to choose some of these itineraries to meet the charging demands while minimizing the wasted energy. 1.However,our formulation can be easily extended to the case in Therefore,we propose delivering energy to an area via which the movement of each charger is supported by battery:just replace B:in Eq.(1)by (B:-ci). mobile chargers which follow pre-defined itineraries.Our 2.In fact,when the transmission power P increases,D also tasks are to select a subset of these itineraries and to deter- increases.When a device is far away from a charger,the device may mine the association between selected itineraries and receive negligible power which is hard to be rectified to useful energy. rechargeable devices.This method is flexible:when there Denote the threshold of this negligible power by pu,then we have D=VaP/puh-b.However,since P is constant in our problem,we are bursty energy demands,we can arrange more chargers; assume D is also constant
Wang et al. [30] designed a hybrid framework which combines solar energy harvesting for cluster heads and wireless charging for normal sensor nodes. Chen et al. [31] investigated the problem of maximizing the number of nodes a path can charge within a given budget (e.g., in terms of time, energy). In contrast, we focus on employing mobile chargers with fixed candidate itineraries to periodically replenish rechargeable devices with the goal of minimizing unnecessary energy wasted, i.e., movement-energy and loss-energy. The optimization techniques are inspired by two optimization problems, e.g., vehicle routing problem (VRP) [32] and facility location problem (FLP) [33]. Given a road network, VRP is to find the optimal itineraries for multiple vehicles to traverse so that a given set of customers are delivered. FLP is to find the optimal placement of facilities to minimize transportation costs. Although their solutions greatly inspired us, ISCA differs from them in two main aspects: (a) the cost of an itinerary in ISCA is determined by not only its length, but also by the devices that will be charged by the itinerary and (b) ISCA will simultaneously select a subset of given itineraries and decide the association relationship between itineraries and devices. 3 MOTIVATION AND PROBLEM 3.1 Motivation Wireless power transfer has been studied extensively because of its wide use in recent years. It can be used to periodically deliver energy to rechargeable wireless sensor networks and can also facilitate the charging of our dailyuse tools like electric toothbrushes and vacuum cleaner robots. In these application scenarios, we may wish that we can use wireless charging just like cellular networks. In fact, this can be achieved by deploying multiple fixed wireless chargers to cover an area of interest. However, this method may be insufficient in the scenarios below: Bursty demands. The number of rechargeable devices and/or the energy consumption of these devices may fluctuate over time. If we place a number of fixed chargers, they may be unable to satisfy the bursty demands for charging. Sparse devices. There may be not always many devices within the area of interest. For areas with sparse devices, deploying fixed chargers may be not costefficient; instead, mobile chargers with carefully planned itineraries could be appropriate. Service decoupling. In the future, there may be many charging service providers that compete with each other. Each service provider will have several charging itineraries passing through the area of interest. We may want to choose some of these itineraries to meet the charging demands while minimizing the wasted energy. Therefore, we propose delivering energy to an area via mobile chargers which follow pre-defined itineraries. Our tasks are to select a subset of these itineraries and to determine the association between selected itineraries and rechargeable devices. This method is flexible: when there are bursty energy demands, we can arrange more chargers; when a target area contains very few devices, we can arrange chargers less frequently. 3.2 Charging Model and Itinerary We consider a network composed of M stationary rechargeable devices, denoted by the set S , fsigM i¼1 and distributed in a two-dimensional plane. The energy requirement of each device is E, i.e., when a mobile charger transfers energy to a device, the device must receive E units of energy. In some applications, rechargeable devices are deployed in environments that prohibit the approach of mobile chargers. Mobile chargers can only travel along existing infrastructures like bridges and roads. Besides, a charger could be integrated with a bus or some other moving tool, which travels along a fixed path, into a single entity, making it easy to deploy and install. Therefore, we assume that there is a set of N candidate charging itineraries, denoted by the set R , frigN i¼1. Without causing confusion, we also use ri to denote the mobile charger that travels along itinerary ri. A mobile charger ri has a limited battery with capacity Bi. When a charger transfers energy to a device, the charger’s transmission power is P. Thus, the charging capacity of ri, in terms of charging time, can be denoted by Ti ¼ Bi=P: (1) We consider that the movement of each charger is supported by petrol,1 and we assume the amount of movement-energy along itinerary ri, denoted by ci, is dictated by the physical length of ri. We assume an omnidirectional wireless power transfer model in which the amount of received power at each device is only dominated by the transmission power of the charger and the distance between them. As indicated by the experiments in [16], the power pij received by device sj from charger ri can be quantified by an empirical model as follows: pij ¼ aP ðdijþbÞ 2 dij D; 0 dij > D: ( (2) Here, constants a and b are determined by environments and hardware of chargers and devices. dij is the physical distance between ri and sj. D is the maximum cover distance of each charger.2 We use tij to represent the time for charger ri to charge sj to its full requirement, i.e., sj should obtain E units of energy after being charged by ri. We have tij ¼ E pij ¼ Eðb þ dijÞ 2 aP : (3) 1. However, our formulation can be easily extended to the case in which the movement of each charger is supported by battery: just replace Bi in Eq. (1) by ðBi ciÞ. 2. In fact, when the transmission power P increases, D also increases. When a device is far away from a charger, the device may receive negligible power which is hard to be rectified to useful energy. Denote the threshold of this negligible power by pth, then we have D ¼ ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi aP =pth p b. However, since P is constant in our problem, we assume D is also constant. ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2835
2836 EEE TRANSACTIONS ON MOBILE COMPUTING,VOL.16.NO.10,OCTOBER 2017 TABLE 1 Main Notations for Quick Reference Symbol Meaning the set of candidate itineraries Ss L the number of candidate itineraries P the transmission power of a charger B the battery capacity of a mobile charger ri S the set of stationary rechargeable devices M the number of stationary devices E the energy requirement of a device a candidate itinerary or a mobile charger the movement-energy of an itinerary ri the charging time capacity of an itinerary ra a rechargeable device Fig.2.Suppose that r2 is responsible for charging ss when it arrives at the minimum distance between ri and s; A.Although it could start transferring power to s:,to minimize loss- the time for ri to charge sj to its requirement energy,it will not begin transmitting power until it arrives at A:,and it will f the loss-energy during ri charges sj stop at As for a duration of tas to charge s3. Therefore,when r;charges s;to its full requirement,the Second,we must guarantee that only selected itineraries amount of loss-energy,denoted by fii,can be obtained as (i.e.,chargers)can deliver energy to devices,i.e., follows: i-r≥0，Hs5∈S,ri∈R ap =(P-P)t E6+42 We would like to mention that since ISCA is a minimiza- (d+b)2 aP tion problem,if no devices are charged by an itinerary ri, (4) (6+d)2 then yi must be 0;therefore,it is unnecessary to add other constraints to explicitly make sure that yi =0 if no devices are charged by ri. We see that when E is fixed,the loss-energy fij is dic- Third,no itinerary (i.e.,charger)can be overloaded,i.e., tated by dij.Therefore,to minimize loss-energy,a mobile charger transmits power to a device only when it arrives the T-∑≥0，∈R location that is closest to that device.For example,in Fig.2, jES suppose that r2 is responsible for charging s3 when it arrives We then have the Itinerary Selection and Charging Asso- at A30.Although it could start transferring power to s3,to ciation problem: minimize loss-energy,it would not begin transmitting power until it arrives at A3,and it would stop at A3 for a min ∑c班+∑∑ [ISCA] (5a) duration of t2s to charge ss. riE n∈R8ES To accomplish this,as proposed in [201,[301,mobile s.t. Ti=Bi/P r∈R (5b) chargers are equipped with positioning devices(e.g.,GPS, gyroscope,etc)to locate themselves so that they can easily E6+d2 ap si∈S,ri∈R (5c) recognize the location (e.g.,A3 in Fig.2)that is closest to each rechargeable device. (6+d)2 Table 1 provides a quick reference for main notations. s∈S,eR(5d) a 3.3 Problem Formulation 发 sj∈S (5e) We use yi to indicate whether itinerary ri is used,and zij to indicate whether ri is responsible for charging sj.Then,the 斯-写≥0， Vsi∈S,ri∈R (5f) total energy consumed in our problem can be classified into T-∑t≥0， Vr:∈R (5g） three types:the payload-energy E.M,the movement- S energy∑neRc9h,and the loss--energy∑neR∑es When the payload-energy is fixed,i.e.,ME,the objective of ∈{0,1} s∈S,ri∈R (5h) this paper is to minimize the sum of movement-energy and ∈{0,1}， r:∈R (5i) loss-energy,i.e., where Egs.(5h)and (5i)are integral constraints.Note min c+∑∑ that Eq.(5i)will be relaxed to yiz+in Section 5,for ∈R i€R8jeS which we design a constant-factor approximation algorithm. The following constraints must be satisfied.First,every Despite our focus on itinerary selection and charging device should be covered and charged,i.e., association,the generic optimization framework makes our analysis and solution applicable to a wide range of ISCA ∑x≥1，s∈S. variants such as stationary charger placement and associa- tion(in this case,setting up a stationary charger may incur
Therefore, when ri charges sj to its full requirement, the amount of loss-energy, denoted by fij, can be obtained as follows: fij ¼ ðP pijÞtij ¼ P aP ðdij þ bÞ 2 ! Eðb þ dijÞ 2 aP ¼ ðb þ dijÞ 2 a 1 !E: (4) We see that when E is fixed, the loss-energy fij is dictated by dij. Therefore, to minimize loss-energy, a mobile charger transmits power to a device only when it arrives the location that is closest to that device. For example, in Fig. 2, suppose that r2 is responsible for charging s3 when it arrives at A3a. Although it could start transferring power to s3, to minimize loss-energy, it would not begin transmitting power until it arrives at A3, and it would stop at A3 for a duration of t23 to charge s3. To accomplish this, as proposed in [20], [30], mobile chargers are equipped with positioning devices (e.g., GPS, gyroscope, etc) to locate themselves so that they can easily recognize the location (e.g., A3 in Fig. 2) that is closest to each rechargeable device. Table 1 provides a quick reference for main notations. 3.3 Problem Formulation We use yi to indicate whether itinerary ri is used, and xij to indicate whether ri is responsible for charging sj. Then, the total energy consumed in our problem can be classified into three types: the payload-energy E M, the movementenergy P ri2R ciyi, and the loss-energy P ri2R P sj2S fijxij. When the payload-energy is fixed, i.e., ME, the objective of this paper is to minimize the sum of movement-energy and loss-energy, i.e., min X ri2R ciyi þ X ri2R X sj2S fijxij: The following constraints must be satisfied. First, every device should be covered and charged, i.e., X i2R xij 1; 8sj 2 S: Second, we must guarantee that only selected itineraries (i.e., chargers) can deliver energy to devices, i.e., yi xij 0; 8sj 2 S; ri 2 R: We would like to mention that since ISCA is a minimization problem, if no devices are charged by an itinerary ri, then yi must be 0; therefore, it is unnecessary to add other constraints to explicitly make sure that yi ¼ 0 if no devices are charged by ri. Third, no itinerary (i.e., charger) can be overloaded, i.e., Tiyi X sj2S tijxij 0; 8ri 2 R: We then have the Itinerary Selection and Charging Association problem: min X ri2R ciyi þ X ri2R X sj2S fijxij [ISCA] (5a) s.t. Ti ¼ Bi=P 8ri 2 R (5b) tij ¼ Eðb þ dijÞ 2 aP 8sj 2 S; ri 2 R (5c) fij ¼ ðb þ dijÞ 2 a 1 !E 8sj 2 S; ri 2 R (5d) X i2R xij 1; 8sj 2 S (5e) yi xij 0; 8sj 2 S; ri 2 R (5f) Tiyi X sj2S tijxij 0; 8ri 2 R (5g) xij 2 f0; 1g; 8sj 2 S; ri 2 R (5h) yi 2 f0; 1g; 8ri 2 R (5i) where Eqs. (5h) and (5i) are integral constraints. Note that Eq. (5i) will be relaxed to yi 2 Zþ in Section 5, for which we design a constant-factor approximation algorithm. Despite our focus on itinerary selection and charging association, the generic optimization framework makes our analysis and solution applicable to a wide range of ISCA variants such as stationary charger placement and association (in this case, setting up a stationary charger may incur Fig. 2. Suppose that r2 is responsible for charging s3 when it arrives at A3a. Although it could start transferring power to s3, to minimize lossenergy, it will not begin transmitting power until it arrives at A3, and it will stop at A3 for a duration of t23 to charge s3. TABLE 1 Main Notations for Quick Reference Symbol Meaning R the set of candidate itineraries N the number of candidate itineraries P the transmission power of a charger Bi the battery capacity of a mobile charger ri S the set of stationary rechargeable devices M the number of stationary devices E the energy requirement of a device ri a candidate itinerary or a mobile charger ci the movement-energy of an itinerary ri Ti the charging time capacity of an itinerary ri sj a rechargeable device dij the minimum distance between ri and sj tij the time for ri to charge sj to its requirement fij the loss-energy during ri charges sj 2836 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017
ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2837 with cost no more than (K-(-1)Em),that covers all devices? S5 ● It is not hard to see that the construction can be finished in polynomial time.Thus,we reduce solving the NP-com- plete SC problem to solving a special case of ISCA,implying that ISCA is NP-hard.It is easy to verify that ISCA is in NP. The theorem follows immediately. We address three possible concerns.First,if Ti,tij,and fij are zeros in ISCA,is the ISCA problem exactly the SC prob- lem?(and thus prove its hardness result.)The answer is no. Fig.3.Reduction from SC to ISCA.By choosing proper ds,Ds,and Tis We note that the sets and their elements are pre-determined we can guarantee that ri can only cover the devices that belong to Vi. in the SC problem,while in ISCA,the "belong to"relation is dynamic,i.e.,a charging itinerary can cover any device if its a cost)and joint optimization of power allocation and data charging capacity is not violated.Therefore,simply letting collection.These problems have a common objective of min- Ti,tij,and fij be zeros in ISCA would produce a trivial SC imizing two types of costs:static cost (e.g.,movement- problem where each set (itinerary)contains all elements energy)and dynamic cost (e.g.,loss-energy). (devices),which is not NP-complete. 3.4 Problem Hardness Second,it is not the first time a mobile charging problem is Theorem 1.The decision version of ISCA is NP-complete. shown to be NP-complete.What are the differences between our proof and previous ones?The fundamental difference Proof.We prove this theorem by reduction from the Set originates from the difference between our problem and pre- Cover problem (SC)[22],which is NP-complete. Q vious ones.For example,Tong et al.[23]studied the problem Definition 1 (Set Cover).Given a universe u=fe1,e2,..., of determining the locations and transmission powers of sen- em}of m elements,a collection of subsets of u, sor nodes so as to minimize the total energy used by static chargers,and this problem is proven to be NP-complete by V=(V1,V2,...,Ve},the cost of v;is hi,and an integer K,does there exist a sub-collection of y,with no more than K cost,that reducing the 3-CNF SAT problem to it;Shu et al.[26]investi- covers all elements ofu? gated the problem of controlling velocities of multiple mobile chargers so as to maximize the network lifetime,and the prob- Given an instance of SC,we construct an instance of lem is shown to be NP-complete by reducing the multi-objec- ISCA as follows.The main idea is to carefully decide the dis- tive shortest path problem to it;Chen et al.[31]studied the tance dij between chargers and devices. problem of maximizing the number of mobile devices that We let N =k and M=m in ISCA,i.e.,each itinerary cor- can be charged by a mobile charger within a given budget, responds to a subset,and each device corresponds to an ele- and it is demonstrated to be NP-complete by reducing the Ori- ment.We line up all m devices at Q distance apart (see enteering problem to it.And we focus on minimizing the Fig.3).In doing so,we can arrange the itineraries as in amount of wasted energy by selecting charging itineraries Fig.3 to make sure that if ejE Vi,then the shortest distance and associations. dij between ri and sj is exactly d;otherwise,dij>Q.For Third,the ISCA problem has its own unique characteris- example,in Fig.3,if Vi=fe1,e2,e3}and V2=fe2,e3,e,e6}, tics;the values of fi;and tij depend on the physical distance we can arrange ri and r2 as in the figure. between a mobile charger and a device,and thus cannot be By choosing proper ds,Qs,and Tis,we can guarantee set arbitrarily.Therefore,ISCA with multipick admits con- that the charging capacity (i.e.,T)of r can cover only the stant approximations,but does not imply that the SC prob- devices that belong to Vi: lem also admits constant approximations.That would be impossible unless P=NP.These unique features will play =Ed) (6) key roles in developing a constant approximation algorithm ap for ISCA with multipick. and r;cannot charge any device that does not belong to Vi: 3.5 Roadmap In ISCA(Eq.(5)),each charging itinerary can be used once at E(b+Q)2/(aP)>TmarQ>VaPTmaz/E-b,(7) most (Eq.(5i)).However,there may be more than one char- where Tmmar is maxiTi. ger in the home station of each itinerary.Thus,we extend For all itineraries,we let c;=hi.Note that the objective of ISCA to the following general problem,ISCA-MP,where "MP"denotes multipick: ISCA is to minimize the sum of movement-energy and loss- energy (see Eq.(5a));since the shortest distance between ri min and each of the devices belonging to V;is d,the overall loss- ∑c班+∑∑f [ISCA-MP] energy,i.e.,(1)m,is fixed.The objective of ISCA ∈ r:∈R8ES (8) s.t. is then reduced to minimizing the movement-energy. Eqs.(5e),(5f,(5g),and(5h) Combining these,we get the following instance of 5∈2+，r:∈R ISCA.P and E could be of any reasonable value.N=k. ci=hi.Ti satisfies Eq.(6).B;=PTi.M=m.Q satisfies 3.Note that constraints (5b),(5c),and (5d)are equations,and thus Eq.(7).dii satisfies Fig.3.Does there exist a subset of R, are omitted here
a cost) and joint optimization of power allocation and data collection. These problems have a common objective of minimizing two types of costs: static cost (e.g., movementenergy) and dynamic cost (e.g., loss-energy). 3.4 Problem Hardness Theorem 1. The decision version of ISCA is NP-complete. Proof. We prove this theorem by reduction from the Set Cover problem (SC) [22], which is NP-complete. tu Definition 1 (Set Cover). Given a universe U¼fe1; e2; ... ; emg of m elements, a collection of subsets of U, V ¼ fV1; V2; ... ; Vkg, the cost of Vi is hi, and an integer K, does there exist a sub-collection of V, with no more than K cost, that covers all elements of U? Given an instance of SC, we construct an instance of ISCA as follows. The main idea is to carefully decide the distance dij between chargers and devices. We let N ¼ k and M ¼ m in ISCA, i.e., each itinerary corresponds to a subset, and each device corresponds to an element. We line up all m devices at Q distance apart (see Fig. 3). In doing so, we can arrange the itineraries as in Fig. 3 to make sure that if ej 2 Vi, then the shortest distance dij between ri and sj is exactly d; otherwise, dij > Q. For example, in Fig. 3, if V1 ¼ fe1; e2; e3g and V2 ¼ fe2; e3; e4; e6g, we can arrange r1 and r2 as in the figure. By choosing proper ds, Qs, and Tis, we can guarantee that the charging capacity (i.e., Ti) of ri can cover only the devices that belong to Vi: Ti ¼ Eðb þ dÞ 2 aP jVij; (6) and ri cannot charge any device that does not belong to Vi: Eðb þ QÞ 2 =ðaPÞ > Tmax , Q > ffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffiffi aPTmax=E p b; (7) where Tmax is maxiTi. For all itineraries, we let ci ¼ hi. Note that the objective of ISCA is to minimize the sum of movement-energy and lossenergy (see Eq. (5a)); since the shortest distance between ri and each of the devices belonging to Vi is d, the overall lossenergy, i.e., ð ðbþdÞ 2 a 1ÞE m, is fixed. The objective of ISCA is then reduced to minimizing the movement-energy. Combining these, we get the following instance of ISCA. P and E could be of any reasonable value. N ¼ k. ci ¼ hi. Ti satisfies Eq. (6). Bi ¼ PTi. M ¼ m. Q satisfies Eq. (7). dij satisfies Fig. 3. Does there exist a subset of R, with cost no more than ðK ððbþdÞ 2 a 1ÞEmÞ, that covers all devices? It is not hard to see that the construction can be finished in polynomial time. Thus, we reduce solving the NP-complete SC problem to solving a special case of ISCA, implying that ISCA is NP-hard. It is easy to verify that ISCA is in NP. The theorem follows immediately. We address three possible concerns. First, if Ti, tij, and fij are zeros in ISCA, is the ISCA problem exactly the SC problem? (and thus prove its hardness result.) The answer is no. We note that the sets and their elements are pre-determined in the SC problem, while in ISCA, the “belong to” relation is dynamic, i.e., a charging itinerary can cover any device if its charging capacity is not violated. Therefore, simply letting Ti, tij, and fij be zeros in ISCA would produce a trivial SC problem where each set (itinerary) contains all elements (devices), which is not NP-complete. Second, it is not the first time a mobile charging problem is shown to be NP-complete. What are the differences between our proof and previous ones? The fundamental difference originates from the difference between our problem and previous ones. For example, Tong et al. [23] studied the problem of determining the locations and transmission powers of sensor nodes so as to minimize the total energy used by static chargers, and this problem is proven to be NP-complete by reducing the 3-CNF SAT problem to it; Shu et al. [26] investigated the problem of controlling velocities of multiple mobile chargers so as to maximize the network lifetime, and the problem is shown to be NP-complete by reducing the multi-objective shortest path problem to it; Chen et al. [31] studied the problem of maximizing the number of mobile devices that can be charged by a mobile charger within a given budget, and it is demonstrated to be NP-complete by reducing the Orienteering problem to it. And we focus on minimizing the amount of wasted energy by selecting charging itineraries and associations. Third, the ISCA problem has its own unique characteristics; the values of fij and tij depend on the physical distance between a mobile charger and a device, and thus cannot be set arbitrarily. Therefore, ISCA with multipick admits constant approximations, but does not imply that the SC problem also admits constant approximations. That would be impossible unless P = NP. These unique features will play key roles in developing a constant approximation algorithm for ISCA with multipick. 3.5 Roadmap In ISCA (Eq. (5)), each charging itinerary can be used once at most (Eq. (5i)). However, there may be more than one charger in the home station of each itinerary. Thus, we extend ISCA to the following general problem, ISCA-MP, where “MP” denotes multipick:3 min X ri2R ciyi þ X ri2R X sj2S fijxij [ISCA-MP] s.t. Eqs. (5e), (5f), (5g), and (5h) yi 2 Zþ; 8ri 2 R (8) Fig. 3. Reduction from SC to ISCA. By choosing proper ds, Ds, and Tis, we can guarantee that ri can only cover the devices that belong to Vi. 3. Note that constraints (5b), (5c), and (5d) are equations, and thus are omitted here. ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2837