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
2838 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 Intuitively,ISCA-MP is harder to solve than ISCA.To s2,...,sy.Inspired by the performance guarantee analysis help us gain some insights into the problem structure of for the SC problem,we have the following theorem: ISCA-MP,we first study ISCA in Section 4,and we introduce a factor O(In M)approximation algorithm and another sim- Theorem 2.GSA is a factor O(In M)approximation algorithm ple yet practical heuristic algorithm.We then design a factor for ISCA. 10 approximation algorithm for ISCA-MP in Section 5. Proof.We denote by OPT the optimal solution for ISCA and consider the iteration in which s;is covered by ri.At 4 SOLUTION FOR ISCA the beginning of this iteration,IS\S M-j+1;if we In this section,we present a factor O(In M)approximation use the optimal solution to cover remaining devices,the algorithm(Section 4.1)and a practical heuristic(Section 4.2). total energy cost is at most OPT,implying that there exists an unselected itinerary having cost-effectiveness of Alg.GSA(Greedy Selection Algorithm) at mostWe remember that GSA greedily selects the 1.R'-0:S-0 most cost-effective unselected itinerary,so we have 2.ii,x写-0：i,班←-0 3.Vhile S\S≠0do ec(s;)=cost-effectiveness of ri 4. If R R'=0,return failure OPT OPT 5 For each ri∈R\R 6. Compute a subset Si of S\S'by solving ≤5S\SSM-j+T (maxs,s.t∑s,es与≤T) It is obvious to see that the sum of movement-energy 7. '-arg min一 +∑ss and loss-energy used in the solution obtained by GSA is S■ 8. S'←-S'US,andj∈S,ry-1 ∑，esec(s).Since 9. R'-R'ui),and y-1 10.Output rijs and yis ec(s)≤1+ 4.1 Greedy Selection Algorithm ≤OlnM)OPT, The greedy selection algorithm (GSA)is inspired by the reduction from SC to ISCA.The main idea of GSA is to itera- the theorem follows immediately. 0 tively select the most cost-effective itinerary and remove the cov- GSA has at most N iterations.In each iteration,for each ered devices,until all devices are covered.Here,when we say a device is "covered",we mean there is an itinerary that is unselected itinerary,solving the(trivial)knapsack problem requires O(M log M)time,so the overall time complexity is responsible for charging it.""represents set minus.Alg. O(N2M log M). GSA shows the details. R'denotes the set of itineraries that have already been selected,and S'denotes the set of devices that have already 4.2 Modified GSA-A Practical Heuristic Algorithm been covered.Initially,both of them are empty sets.In each GSA has theoretic performance guarantee,but may perform iteration,we first compute the cost-effectiveness of all unse- poorly in practice.This section is devoted to improving lected itineraries and select the most cost-effective one.The GSA from the perspective of practice. cost-effectiveness can be computed as follows. In each iteration of GSA,the most cost-effective itiner- For eachrRR',we want to maximize the number of ary is selected regardless of the other itineraries,devices, uncovered devices that it can cover.Therefore,we have the fol- and their interrelationships.This is the key observation lowing trivialknapsack problem,where S,isasubset of s that helps us improve GSA.The Modified GSA is shown in Alg.MGSA.The difference compared with GSA is marked in blue (lines 6-9).The main idea of MGSA is as max S;l follows. s.t. ∑t场≤ (9) In each iteration,instead of selecting the most cost-effec- BjESi tive itinerary,MGSA selects the itinerary that costs a minimal energy to cover the devices that may take up more energy if they We would like to mention that Eq.(9)is a special case of the are otherwise covered by one of the other unselected itineraries. knapsack problem where the value of each item is 1.There-This intuition is captured by variable gij:for each fore,greedily picking the device with the smallest tij is riR\R'and each sjeS\S,gij is defined as the aver- already optimal and costs only O(Mlog M)time.The cost-age cost of sj if it is covered by the itineraries in effectiveness of r;is then defined as R\(R'U{i}),i.e, 9+∑si f ISil 弱=R1(RUeu We define the energy cost ec(sj)of sjas the cost-effective-Then,for each riR\R',we try to find a subset S;of ness of the itinerary that coverss Without loss of general-uncovered devices that maximizeThus,we have ity,we assume the order in which devices are covered is s1, the following knapsack problem:
Intuitively, ISCA-MP is harder to solve than ISCA. To help us gain some insights into the problem structure of ISCA-MP, we first study ISCA in Section 4, and we introduce a factor Oðln MÞ approximation algorithm and another simple yet practical heuristic algorithm. We then design a factor 10 approximation algorithm for ISCA-MP in Section 5. 4 SOLUTION FOR ISCA In this section, we present a factor Oðln MÞ approximation algorithm (Section 4.1) and a practical heuristic (Section 4.2). Alg. GSA (Greedy Selection Algorithm) 1. R0 ;; S0 ; 2. 8i; j, xij 0; 8i, yi 0 3. While SnS0 6¼ ; do 4. If RnR0 ¼ ;, return failure 5. For each ri 2RnR0 6. Compute a subset Si of SnS0 by solving ðmaxjSij, s.t. P sj2Si tij TiÞ 7. i 0 arg mini ciþ P sj2Si fij jSij 8. S0 S0 [ Si0 , and 8j 2 Si0 , xi0j 1 9. R0 R0 [ fi 0 g, and yi0 1 10. Output xijs and yis 4.1 Greedy Selection Algorithm The greedy selection algorithm (GSA) is inspired by the reduction from SC to ISCA. The main idea of GSA is to iteratively select the most cost-effective itinerary and remove the covered devices, until all devices are covered. Here, when we say a device is “covered”, we mean there is an itinerary that is responsible for charging it. “n” represents set minus. Alg. GSA shows the details. R0 denotes the set of itineraries that have already been selected, and S0 denotes the set of devices that have already been covered. Initially, both of them are empty sets. In each iteration, we first compute the cost-effectiveness of all unselected itineraries and select the most cost-effective one. The cost-effectiveness can be computed as follows. For each ri 2RnR0 , we want to maximize the number of uncovered devices that it can cover. Therefore, we have the following trivial knapsack problem, where Si is a subset of SnS0 : max jSij s.t. X sj2Si tij Ti: (9) We would like to mention that Eq. (9) is a special case of the knapsack problem where the value of each item is 1. Therefore, greedily picking the device with the smallest tij is already optimal and costs only OðM log MÞ time. The costeffectiveness of ri is then defined as ci þ P sj2Si fij jSij : We define the energy cost ecðsjÞ of sj as the cost-effectiveness of the itinerary that covers sj. Without loss of generality, we assume the order in which devices are covered is s1, s2,..., sM. Inspired by the performance guarantee analysis for the SC problem, we have the following theorem: Theorem 2. GSA is a factor Oðln MÞ approximation algorithm for ISCA. Proof. We denote by OPT the optimal solution for ISCA and consider the iteration in which sj is covered by ri. At the beginning of this iteration, jS n S0 j > M j þ 1; if we use the optimal solution to cover remaining devices, the total energy cost is at most OPT, implying that there exists an unselected itinerary having cost-effectiveness of at most OPT jSnS0 j . We remember that GSA greedily selects the most cost-effective unselected itinerary, so we have ecðsjÞ ¼ cost-effectiveness of ri OPT jS n S0 j OPT M j þ 1 : It is obvious to see that the sum of movement-energy and loss-energy used in the solution obtained by GSA is P sj2S ecðsjÞ. Since X sj2S ecðsjÞ 1 þ 1 2 þ ::: þ 1 M OPT Oðln MÞOPT; the theorem follows immediately. tu GSA has at most N iterations. In each iteration, for each unselected itinerary, solving the (trivial) knapsack problem requires OðM log MÞ time, so the overall time complexity is OðN2M log MÞ. 4.2 Modified GSA—A Practical Heuristic Algorithm GSA has theoretic performance guarantee, but may perform poorly in practice. This section is devoted to improving GSA from the perspective of practice. In each iteration of GSA, the most cost-effective itinerary is selected regardless of the other itineraries, devices, and their interrelationships. This is the key observation that helps us improve GSA. The Modified GSA is shown in Alg. MGSA. The difference compared with GSA is marked in blue (lines 6-9).The main idea of MGSA is as follows. In each iteration, instead of selecting the most cost-effective itinerary, MGSA selects the itinerary that costs a minimal energy to cover the devices that may take up more energy if they are otherwise covered by one of the other unselected itineraries. This intuition is captured by variable gij: for each ri 2RnR0 and each sj 2SnS0 , gij is defined as the average cost of sj if it is covered by the itineraries in R n ðR0 [ figÞ, i.e., gij ¼ 1 jR n ðR0 [ figÞj X rk2RnðR0 [figÞ fkj: Then, for each ri 2RnR0 , we try to find a subset Si of uncovered devices that maximize P sj2Si gij. Thus, we have the following knapsack problem: 2838 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017
ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2839 max 95 In the above formulation,"PL"refers to "primal".Intro- &jESi ducing variables as,Bs,and 0s corresponding to Eqs.(5e), (10) s.t. ∑场≤T (5f),and (5g),respectively,we have the following dual problem,where“DL"refers to“dual'": BjESi We then select the itinerary that minimizes the energy cost, max 〉a [ISCA-MP-DL] (12a) ie.fiand make some updates.Solving Eq.(10) through dynamic programming costs O(MT;)time.Thus, the overall complexity of MGSA is O(N2 MTmar). s.t. T8+∑B≤c, r:∈R (12b) BjES Alg.MGSA (Modified Greedy Selection Algorithm) aj-B-t8≤f s∈S,r:∈R (12c) 1.R'-0:S-0 2.i,i,写-0：i,5-0 4≥0， sj∈S (12d) 3.While S\S≠0do f20, s∈S,Ti∈R (12e) 4. If R R'=0,return failure 5. For each r:∈RR 0≥0， r:∈R (12f) 6. For each sj∈S\S 7. 断←(RU∑r∈R1(RU According to the weak duality theorem [33],the dual Compute a subset Si of S\S'by solving problem,i.e.,ISCA-MP-DL gives a lower bound on the opti- (max∑，s,9s.t∑，，≤T) mal value of the primal problem,i.e.,ISCA-MP-PL.We will 9. t-argmins(G+∑sesf) see shortly in Section 5.4 that this lower bound will be very useful in obtaining the approximation ratio. 10. S-SUS,andj∈S,x-1 11. '-RU{i},and班-1 5.2 Understanding Dual Variables 12.Output rijs and yis In this section,we use the complementary slackness condi- tions [33]to help readers better understand the dual prob- 4.3 Summary lem,i.e.,ISCA-MP-DL. In each iteration of MGSA,we think ahead by selecting an The primal complementary slackness conditions are as itinerary that,on average,consumes less loss-energy than follows: the remaining itineraries to cover a subset of uncovered devices.Though we cannot provide any theoretical perfor- (a)h>0→T8,+∑=G,r:∈R: mance guarantee for MGSA at this stage,it works better 8e8 than GSA in the evaluations presented in Section 7. (b)x6>0→g-B-t9=fi:s∈S,n∈R 5 SOLUTION FOR ISCA-MP The dual complementary slackness conditions are as fol- lows: In this section,we examine ISCA in a general setting by allowing an itinerary to be selected multiple times,i.e.,ISCA- (@)g>0→∑=1，eS MP.We first give the relaxed primal and dual problems of riER ISCA-MP (Section 5.1)and explain their slackness condi- (d)>0→5-x=0,Vs∈S,i∈R: tions (Section 5.2);then,we present the transformation (Section 5.3)and a constant-factor approximation algorithm (e)4>0→Th-∑t=0,:∈R. (Section 5.4).Finally,we show how to revert to the original S problem,i.e.,ISCA-MP (Section 5.5).We also provide a con- By condition (a),if an itinerary is selected,then crete example that may help illustrate the details (Section +B=cj.By condition (d),we suppose1.If 5.6) ij=1,then Bij 0;otherwise,Bij=0.By condition (b),if xij =1,then aj-Bij -tiji=fij. 5.1 Primal and Dual Problems Combining the conditions,we can take a;as the fotal price The LP-relaxation of ISCA-MP can be obtained by letting paid by device sj for the charging service,and aj can be parti- 0≤x≤1and0≤h≤1.Since ISCA-MP is a minimization tioned into three parts:Bi tiji,and fij.The first two parts problem,(1)s are redundant and thus,are discarded.The pay for the movement-energy cost of r;(by condition (a));if solution to this fractional CSRA-MP is a lower bound of we take 0;as the unit price of charging time,then,Bi;is a ISCA-MP.In fact,the solution to ISCA-MP also provides a fixed part,and tij;is a dynamic part depending on ti.The lower bound of ISCA last part of aj is fij,which pays for loss-energy when s;is being charged. min ∑G+∑∑f [ISCA-MP-PL] 5.3 Transformation s.t.Egs.(5e),(5f),and (5g) (11) There are three types of variables,a,B,and 0,in the ISCA- MP-DL problem.We want to eliminate one of them (say, ≥0，sj∈S,ri∈R and transform ISCA-MP-PL and ISCA-MP-DL into a new 班≥0，r∈R. pair of primal and dual programs that have only two
max X sj2Si gij s.t. X sj2Si tij Ti: (10) We then select the itinerary that minimizes the energy cost, i.e., ci þ P sj2Si fij, and make some updates. Solving Eq. (10) through dynamic programming costs OðMTiÞ time. Thus, the overall complexity of MGSA is OðN2MTmaxÞ. Alg. MGSA (Modified Greedy Selection Algorithm) 1. R0 ;; S0 ; 2. 8i; j, xij 0; 8i, yi 0 3. While SnS0 6¼ ; do 4. If RnR0 ¼ ;, return failure 5. For each ri 2RnR0 6. For each sj 2SnS0 7. gij 1 jRnðR0 [figÞj P rk2RnðR0 [figÞ fkj 8. Compute a subset Si of SnS0 by solving ðmaxP sj2Si gij, s.t. P sj2Si tij TiÞ 9. i 0 arg minSi6¼;ðci þ P sj2Si fijÞ 10. S0 S0 [ Si0 , and 8j 2 Si0 , xi0j 1 11. R0 R0 [ fi 0 g, and yi0 1 12. Output xijs and yis 4.3 Summary In each iteration of MGSA, we think ahead by selecting an itinerary that, on average, consumes less loss-energy than the remaining itineraries to cover a subset of uncovered devices. Though we cannot provide any theoretical performance guarantee for MGSA at this stage, it works better than GSA in the evaluations presented in Section 7. 5 SOLUTION FOR ISCA-MP In this section, we examine ISCA in a general setting by allowing an itinerary to be selected multiple times, i.e., ISCAMP. We first give the relaxed primal and dual problems of ISCA-MP (Section 5.1) and explain their slackness conditions (Section 5.2); then, we present the transformation (Section 5.3) and a constant-factor approximation algorithm (Section 5.4). Finally, we show how to revert to the original problem, i.e., ISCA-MP (Section 5.5). We also provide a concrete example that may help illustrate the details (Section 5.6). 5.1 Primal and Dual Problems The LP-relaxation of ISCA-MP can be obtained by letting 0 xij 1 and 0 yi 1. Since ISCA-MP is a minimization problem, ð 1Þs are redundant and thus, are discarded. The solution to this fractional CSRA-MP is a lower bound of ISCA-MP. In fact, the solution to ISCA-MP also provides a lower bound of ISCA min X ri2R ciyi þ X ri2R X sj2S fijxij [ISCA-MP-PL] s.t. Eqs. (5e), (5f), and (5g) xij 0; 8sj 2 S; ri 2 R yi 0; 8ri 2 R: (11) In the above formulation, “PL” refers to “primal”. Introducing variables as, bs, and us corresponding to Eqs. (5e), (5f), and (5g), respectively, we have the following dual problem, where “DL” refers to “dual”: max X sj2S aj [ISCA-MP-DL] (12a) s.t. Tiui þ X sj2S bij ci; 8ri 2 R (12b) aj bij tijui fij; 8sj 2 S; ri 2 R (12c) aj 0; 8sj 2 S (12d) bij 0; 8sj 2 S; ri 2 R (12e) ui 0; 8ri 2 R (12f) According to the weak duality theorem [33], the dual problem, i.e., ISCA-MP-DL gives a lower bound on the optimal value of the primal problem, i.e., ISCA-MP-PL. We will see shortly in Section 5.4 that this lower bound will be very useful in obtaining the approximation ratio. 5.2 Understanding Dual Variables In this section, we use the complementary slackness conditions [33] to help readers better understand the dual problem, i.e., ISCA-MP-DL. The primal complementary slackness conditions are as follows: (a) yi > 0 ) Tiui þ X sj2S bij ¼ cj; 8ri 2 R; (b) xij > 0 ) aj bij tijui ¼ fij; 8sj 2 S; ri 2 R: The dual complementary slackness conditions are as follows: (c) aj > 0 ) X ri2R xij ¼ 1; 8sj 2 S; (d) bij > 0 ) yi xij ¼ 0; 8sj 2 S; ri 2 R; (e) ui > 0 ) Tiyi X sj2S tijxij ¼ 0; 8ri 2 R: By condition (a), if an itinerary is selected, then Tiui þ P sj2S bij ¼ cj. By condition (d), we suppose yi ¼ 1. If xij ¼ 1, then bij > 0; otherwise, bij ¼ 0. By condition (b), if xij ¼ 1, then aj bij tijui ¼ fij. Combining the conditions, we can take aj as the total price paid by device sj for the charging service, and aj can be partitioned into three parts: bij, tijui, and fij. The first two parts pay for the movement-energy cost of ri (by condition (a)); if we take ui as the unit price of charging time, then, bij is a fixed part, and tijui is a dynamic part depending on tij. The last part of aj is fij, which pays for loss-energy when sj is being charged. 5.3 Transformation There are three types of variables, a, b, and u, in the ISCAMP-DL problem. We want to eliminate one of them (say, u) and transform ISCA-MP-PL and ISCA-MP-DL into a new pair of primal and dual programs that have only two ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2839
2840 EEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 variables.We want to solve them,and finally to revert to the PDA starts with a primal infeasible solution and a dual original integral problem. feasible solution.It iteratively improves the feasibility of the Let 0,=ISCA-MP-DL becomes primal solution and the optimality of the dual solution.It ensures that(i)the primal solution is always extended inte- max j ISCA-MP-DL-T] (13a) grally,and that (ii)the value of the dual solution is at least f 85S times as large as the value of the primal solution.Since the dual solution is a lower bound on the optimal value of the st.∑≤0 i r:∈R (13b) primal solution,the approximation ratio is then equal to f. 55 9citij Alg.PDA(Primal-Dual schema-Based Algorithm) 0-≤i+10 s∈S,rn∈R (13c Part II:Compute integral primal solution 21.i,i,x←-0：i,h-0,fselected-0 45≥0， ∀s,∈S (13d) 22.Ris-friltselectedi =1} ≥0， ∀s∈S,ri∈R (13e) 23.Construct a graph G with Ri as vertex set.For each pair of ri,riERs,there is an edge between them if and only if The integral dual of ISCA-MP-DL-T,i.e.,the transformed 3sj∈S,s.t.positive=positive为=1. ISCA-MP,is as follows: 24.Find a maximal independent vertex set in G with non-decreasing order of,say D. min iISCA-MP-T] 25.For each riE D,set yi -1,fselectedi-1. 10T 26.For each si do (14) 27. Ry-{rr:∈Rts,f>0} s.t. Egs.(5e),(5f),and (5h) 28.If,then RinD has only one element ri. 斯∈2+，r:eR 29. Setzij-1,sj is called closely covered. 30. Else if chosti ED,let rk-chosti Note that the constraint Eq.(5g)is discarded in Eq.(14); 31. Set kj -1,sj is called normally covered. therefore,in ISCA-MP-T,there is no constraint on the capac- 32. Otherwise,D must contain rh,such that ry and rh are ity of each itinerary. neighbors in G,and ch/Th ce/T 33. Setj-1,sj is called loosely covered. 5.4 Approximation Algorithm for ISCA-MP-T 34.xs and ys form an integral solution to ISCA-MP-T We now consider two problems:the primal problem,i.e., ISCA-MP-T,and the dual problem,i.e.,ISCA-MP-DL-T. PDA consists of two parts,which correspond to comput- There is a factor three approximation algorithm for the facil-ing dual and integral primal solutions,respectively.In the ity location problem in [33].Based on that algorithm and following,we first introduce these two parts and then pro- some special properties of ISCA-MP-T,we now propose a vide the analysis of the approximation ratio. factor nine approximation algorithm for ISCA-MP-T using the primal-dual schema,shown in Alg.PDA.The main intu- 5.4.1 Compute Dual Solution ition behind PDA is as follows. The objective of ISCA-MP-DL-T is to maximize The first part of PDA tries to increase asas much as possible Alg.PDA(Primal-Dual Schema-Based Algorithm) and maintains Eqs.(13b)and(13c). Part I:Compute dual solution All events are associated with a timestamp ts.When ts is 1.Vi,tselected;-0 zero,each itinerary is not temporarily selected(tselected); 2.j,&;←-0，covered;←-0，chost-0 each a is 0;each device is not covered(covered);the covering 3.ii,B-0,fullij←-0，positive6-0 host (chost)of each device is 0;each B is 0;the connection 4.Timestamp ts -0 between ri and sj is neither full nor positive. 5.While there is any uncovered device do PDA raises a by one for each uncovered device as ts 6. ts+ts+1 7.For each s;that satisfies covered;=0 do grows by one (line 8).For each ri that satisfies aj= +0,PDA runs as follows: 9c:t: 8. aj-aj+1 9. For eachrthat satisfiesdo the connection between itinerary ri and device sj 10. fullij-1 becomes full (line 10); 11. If tselected;1 and covered;=0 do if ri is temporarily selected and sj is not covered,we 12. covered←-1，chostj-r For eachthat satisfies>方+密do change sj into covered and its covering host is ri 13. ines11-12). 14. Bj-月+1，positiver-1 15. If∑，sA=年do And for each that satisfiesPDA runs as follows: 16. tselected←-l 17. For each se that satisfies covered:=0 .B;is increased by one and the corresponding con- and fullik =1 do nection is set to be positive (line 14),ensuring that 18. coveredk-1,chosts-ri Eq.(13 c)is not violated; 19.as and Bs form a dual solution to ISCA-MP-DL-T ·if∑s,esB=靠thenr,is marked as temporarily selected,all uncovered devices that have full
variables. We want to solve them, and finally to revert to the original integral problem. Let ui ¼ 9ci 10Ti . ISCA-MP-DL becomes max X sj2S aj [ISCA-MP-DL-T] (13a) s.t.X sj2S bij ci 10 ; 8ri 2 R (13b) aj bij fij þ 9citij 10Ti ; 8sj 2 S; ri 2 R (13c) aj 0; 8sj 2 S (13d) bij 0; 8sj 2 S; ri 2 R (13e) The integral dual of ISCA-MP-DL-T, i.e., the transformed ISCA-MP, is as follows: min X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij[ISCA-MP-T] s.t. Eqs. (5e), (5f), and (5h) yi 2 Zþ; 8ri 2 R (14) Note that the constraint Eq. (5g) is discarded in Eq. (14); therefore, in ISCA-MP-T, there is no constraint on the capacity of each itinerary. 5.4 Approximation Algorithm for ISCA-MP-T We now consider two problems: the primal problem, i.e., ISCA-MP-T, and the dual problem, i.e., ISCA-MP-DL-T. There is a factor three approximation algorithm for the facility location problem in [33]. Based on that algorithm and some special properties of ISCA-MP-T, we now propose a factor nine approximation algorithm for ISCA-MP-T using the primal-dual schema, shown in Alg. PDA. The main intuition behind PDA is as follows. Alg. PDA (Primal-Dual Schema-Based Algorithm) Part I: Compute dual solution 1. 8i, tselectedi 0 2. 8j, aj 0, coveredj 0, chostj 0 3. 8i; j, bij 0, fullij 0, positiveij 0 4. Timestamp ts 0 5. While there is any uncovered device do 6. ts ts þ 1 7. For each sj that satisfies coveredj ¼ 0 do 8. aj aj þ 1 9. For each ri that satisfies aj ¼ fij þ 9citij 10Ti do 10. fullij 1 11. If tselectedi ¼ 1 and coveredj ¼ 0 do 12. coveredj 1, chostj ri 13. For each ri that satisfies aj > fij þ 9citij 10Ti do 14. bij bij þ 1, positiveij 1 15. If P sj2S bij ¼ ci 10 do 16. tselectedi 1 17. For each sk that satisfies coveredk ¼ 0 and fullik ¼ 1 do 18. coveredk 1, chostk ri 19. as and bs form a dual solution to ISCA-MP-DL-T PDA starts with a primal infeasible solution and a dual feasible solution. It iteratively improves the feasibility of the primal solution and the optimality of the dual solution. It ensures that (i) the primal solution is always extended integrally, and that (ii) the value of the dual solution is at least f times as large as the value of the primal solution. Since the dual solution is a lower bound on the optimal value of the primal solution, the approximation ratio is then equal to f. Alg. PDA (Primal-Dual schema-Based Algorithm) Part II: Compute integral primal solution 21. 8i; j, xij 0; 8i, yi 0, fselectedi 0 22. Rts frijtselectedi ¼ 1g 23. Construct a graph G with Rts as vertex set. For each pair of ri; rk 2 Rts, there is an edge between them if and only if 9sj 2 S, s.t. positiveij ¼ positivekj ¼ 1. 24. Find a maximal independent vertex set in G with non-decreasing order of ci Ti , say D. 25. For each ri 2 D, set yi 1, fselectedi 1. 26. For each sj do 27. Rj frijri 2 Rts; bij > 0g 28. If Rj \ D 6¼ ;, then Rj \ D has only one element ri. 29. Set xij 1, sj is called closely covered. 30. Else if chostj 2 D, let rk chostj 31. Set xkj 1, sj is called normally covered. 32. Otherwise, D must contain rh, such that rk and rh are neighbors in G, and ch=Th ck=Tk 33. Set xhj 1, sj is called loosely covered. 34. xs and ys form an integral solution to ISCA-MP-T PDA consists of two parts, which correspond to computing dual and integral primal solutions, respectively. In the following, we first introduce these two parts and then provide the analysis of the approximation ratio. 5.4.1 Compute Dual Solution The objective of ISCA-MP-DL-T is to maximize P sj2S aj. The first part of PDA tries to increase as as much as possible and maintains Eqs. (13b) and (13c). All events are associated with a timestamp ts. When ts is zero, each itinerary is not temporarily selected (tselected); each a is 0; each device is not covered (covered); the covering host (chost) of each device is 0; each b is 0; the connection between ri and sj is neither full nor positive. PDA raises a by one for each uncovered device as ts grows by one (line 8). For each ri that satisfies aj ¼ fij þ 9citij 10Ti , PDA runs as follows: the connection between itinerary ri and device sj becomes full (line 10); if ri is temporarily selected and sj is not covered, we change sj into covered and its covering host is ri (lines 11-12). And for each ri that satisfies aj > fij þ 9citij 10Ti , PDA runs as follows: bij is increased by one and the corresponding connection is set to be positive (line 14), ensuring that Eq. (13 c) is not violated; if P sj2S bij ¼ ci 10, then ri is marked as temporarily selected, all uncovered devices that have full 2840 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017
ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2841 connections to r;are declared covered,and r;is the ▣ra ▣ covering host for each of them. When all devices become covered,the first half of PDA terminates. positive OSg 5.4.2 Compute Integral Primal Solution Closely covered Normally covered Loosely covered The second part of PDA computes an integral solution to Fig.4.Three types of being covered(See lines 26-33 of Alg.PDA).Note ISCA-MP-T.In fact,the as and Bs obtained from the first that a positive connection is also full,but a full connection may be not half of PDA give us some clues for finding an integral solu- positive. tion to ISCA-MP-T. 9citii Initially,each rij is 0;each yi is 0;each itinerary is not finally selected (fselected).Ris is the set of temporarily R10 +> ri∈R8eS 10店/， selected itineraries.In fact,Rts contains some unnecessary itineraries.In lines 23-25,we select a subset of Rt as the finally in terms of∑aj According to Alg.PDA,each device is covered by one of the selected itineraries.We first construct a graph G with Ris as three types (see lines 26-33):closely covered (ccovered),nor- vertex set.For each pair of ri,r&E Rts,there is an edge mally covered (ncovered),and loosely covered (lcovered).Fig.4 between them if and only if 3sj ES,s.t.positivej=positivekj gives an illustration,where squares represent itineraries. =1.Then we find a maximal independent vertex set in G,say For each ccovered device sj,we suppose that ri covers it in D,as the set of finally selected itineraries.D is obtained as fol- the final solution.Since the connection between ri and s;is lows:we sort the vertex set of G in non-decreasing order of positive, and then check whether each vertex(i.e.,itinerary)can be aj can be split into two parts:Bij and added into the maximal set.The itinerary selection part is (fij+9citi/(10T))(lines 9,and 13-14).It is trivial to see that done.The rest of the task is itinerary association. (15) For each sj,we denote Rj as the set of temporarily selected itineraries that have positive connections to s;(line 8 is ccovered,and r:∈D rex 10 27).There are three cases: and the second part of aj pays for the connection cost, If RinD0,since D is a maximal independent ver- 9citij tex set on G,RinD has only one element,say ri; -B= 10T: thus we set rij-1,and sj is called closely covered; sj is ccovered,andh∈D Ti∈R sj is ccovered ● Otherwise,the covering host of sj,say rk,is in D.We (16) setj-1,and sj is called normally covered; For each ncovered device sj,we suppose that rk covers it In the remaining case,D must contain rh such that r in the final solution.Since the connection between r and sj and rh are neighbors in G,and ch/Th ck/T is full,a;pays for the connection cost, (because D is a maximal independent set,again);we then set hj-1,and sj is called loosely covered. 9citij (17) 10T sj is ncovered,and r:ED 5.4.3 Dual Feasibility For lcovered devices,we have the following theorem: We have to check whether the obtained as and Bs satisfy the four constraints in Eq.(13).Constraints(13(e))and (13(d)) Theorem 3.For lcovered devices,we have are trivial.In lines 13-14,whenever a;is larger than .9y≥T 9citij fwe also increase by one,making sure con- 10T straint (13(c))is not violated.In lines 15-18,whenever (18) all uncovered devices that have full connec- Proof.For each lcovered device sj,we suppose that rh cov- tions to ri will be marked as covered,implying that those ers it in the final solution and that rk is its covering host Bi,s will not increase any more. (see Fig.4).According to line 23 of Alg.PDA,there must exist another sg that has positive connections with both rk 5.4.4 Primal Feasibility and rh.It is trivial to see that We check whether the obtained as and ys violate the four con- a;≥fs+9ckt/(10Tk), straints in Eq.(14).For Eq.(5 e),lines 26-33 of PDA guarantee that each s;is charged by one of the finally selected itineraries. a&g≥fg+9ctg/(10Tk), For Eg.(5f),lines 26-33 guarantee that devices can only be ag fhg +9chthg/(10Th). charged by the finally-selected itineraries.The rest is trivial. We denote by tsh and tsk the timestamps when rh and rk are marked as temporarily selected (line 16),respec- 5.4.5 Approximation Ratio Analysis tively.Since rk is the covering host of sj,we have We denote by OPT the optimal solution to ISCA-MP-T.Due aj tsk.Since the connection between sg and either rh or to the weak duality theorem [331is a lower bound rk is positive,we have agz min(tsh,tsk).Therefore, of OPT.We now try to find a upper bound of 0j20g
connections to ri are declared covered, and ri is the covering host for each of them. When all devices become covered, the first half of PDA terminates. 5.4.2 Compute Integral Primal Solution The second part of PDA computes an integral solution to ISCA-MP-T. In fact, the as and bs obtained from the first half of PDA give us some clues for finding an integral solution to ISCA-MP-T. Initially, each xij is 0; each yi is 0; each itinerary is not finally selected (fselected). Rts is the set of temporarily selected itineraries. In fact, Rts contains some unnecessary itineraries. In lines 23-25, we select a subset of Rts as the finally selected itineraries. We first construct a graph G with Rts as vertex set. For each pair of ri; rk 2 Rts, there is an edge between them if and only if 9sj 2 S, s.t. positiveij ¼ positivekj ¼ 1. Then we find a maximal independent vertex set in G, say D, as the set of finally selected itineraries. D is obtained as follows: we sort the vertex set of G in non-decreasing order of ci Ti and then check whether each vertex (i.e., itinerary) can be added into the maximal set. The itinerary selection part is done. The rest of the task is itinerary association. For each sj, we denote Rj as the set of temporarily selected itineraries that have positive connections to sj (line 27). There are three cases: If Rj \ D 6¼ ;, since D is a maximal independent vertex set on G, Rj \ D has only one element, say ri; thus we set xij 1, and sj is called closely covered; Otherwise, the covering host of sj, say rk, is in D. We set xkj 1, and sj is called normally covered; In the remaining case, D must contain rh such that rk and rh are neighbors in G, and ch=Th ck=Tk (because D is a maximal independent set, again); we then set xhj 1, and sj is called loosely covered. 5.4.3 Dual Feasibility We have to check whether the obtained as and bs satisfy the four constraints in Eq. (13). Constraints (13(e)) and (13(d)) are trivial. In lines 13-14, whenever aj is larger than fij þ 9citij 10Ti , we also increase bij by one, making sure constraint (13(c)) is not violated. In lines 15-18, whenever P sj2S bij ¼ ci 10, all uncovered devices that have full connections to ri will be marked as covered, implying that those bijs will not increase any more. 5.4.4 Primal Feasibility We check whether the obtained xs and ys violate the four constraints in Eq. (14). For Eq. (5 e), lines 26-33 of PDA guarantee that each sj is charged by one of the finally selected itineraries. For Eq. (5f), lines 26-33 guarantee that devices can only be charged by the finally-selected itineraries. The rest is trivial. 5.4.5 Approximation Ratio Analysis We denote by OPT the optimal solution to ISCA-MP-T. Due to the weak duality theorem [33], P sj2S aj is a lower bound of OPT. We now try to find a upper bound of X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij; in terms of P sj2S aj. According to Alg. PDA, each device is covered by one of the three types (see lines 26-33): closely covered (ccovered), normally covered (ncovered), and loosely covered (lcovered). Fig. 4 gives an illustration, where squares represent itineraries. For each ccovered device sj, we suppose that ri covers it in the final solution. Since the connection between ri and sj is positive, aj can be split into two parts: bij, and ðfij þ 9citij=ð10TiÞÞ (lines 9, and 13-14). It is trivial to see that X sj is ccovered; and ri2D bij ¼ X ri2R ciyi 10 ; (15) and the second part of aj pays for the connection cost, X sj is ccovered; and ri2D aj bij ¼ X ri2R X sj is ccovered fij þ 9citij 10Ti xij: (16) For each ncovered device sj, we suppose that rk covers it in the final solution. Since the connection between rk and sj is full, aj pays for the connection cost, X sj is ncovered; and ri2D aj ¼ X ri2R X sj is ncovered fij þ 9citij 10Ti xij: (17) For lcovered devices, we have the following theorem: Theorem 3. For lcovered devices, we have X sj is lcovered; and ri2D 9aj X ri2R X sj is lcovered fij þ 9citij 10Ti xij: (18) Proof. For each lcovered device sj, we suppose that rh covers it in the final solution and that rk is its covering host (see Fig. 4). According to line 23 of Alg. PDA, there must exist another sg that has positive connections with both rk and rh. It is trivial to see that aj fkj þ 9cktkj=ð10TkÞ; ag fkg þ 9cktkg=ð10TkÞ; ag fhg þ 9chthg=ð10ThÞ: We denote by tsh and tsk the timestamps when rh and rk are marked as temporarily selected (line 16), respectively. Since rk is the covering host of sj, we have aj tsk. Since the connection between sg and either rh or rk is positive, we have ag minðtsh; tskÞ. Therefore, aj ag. Fig. 4. Three types of being covered (See lines 26-33 of Alg. PDA). Note that a positive connection is also full, but a full connection may be not positive. ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2841
2842 IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL 16.NO.10,OCTOBER 2017 According to lines 24 and 32-33,we have ch/T c/Tk. To prove Eq.(18),it is sufficient to prove that /3 +器 2 4/3 10202040 1/2 6 9 12 4/3 -o+r-d+ 9Ecn(b+dhj) 10aPTh ,(Eqs.(3)and(4) 10 ≤b+dg+g+dsP-d 10 5 10 5 10 +9aE6+dg+g+d（rnt） 10aPTh (a)PDA inputs ≤盟o+4wP+b+dP+6+dgP-3a--2剑 6B66 686 +2TcnEl(b+dho)+(+da)+d) 10aPTi s3E[(0+dh)-a+(0+do)2-a+(+dj)2-a] ts=2 fs=4 l8=6 a full ---positive ◆tselected=1 △covered=1 27cnE(b+dng)27cnE(b+do 27cnE(+dx) (b)PDA in different timestamps 10aPT 10aPTh 10aPT Fig.5.Example of running PDA.Note that the a of a device will not ≤3(fng+fg+f)+3 (9cntng 9cht超 9cntki increase after being covered.The final solution is,s and s2 are closely 10Th covered by r and r1,respectively;ss and s are normally covered by r 10T6 10T and rs,respectively. ≤3(jg+fg+f)+3 (9chtng 9cktka 9cktkj 10Th 10T 10T Theorem 5.PDA plus Eq.(20)is a factor 10 approximation ≤3(ag+ag+a) algorithm for ISCA with multipick. ≤9ujr Proof..Notice that≤h+∑es where the third "<"is due to 8b2 2a,as a and b are T ,then we have know constants,and b is much bigger than a. Q ∑+∑∑ 防ER Combining the above analyses and Theorem 3,we have ri∈R8ES Theorem 4.PDA is a factor nine approximation algorithm for ∑+三 ISCA-MP-T. TiE riER BjES Proof.As previously mentioned,due to the weak duality ∑sr\ theorem, sjsaj is a lower bound of OPr. T +∑∑ 片∈R防S Eqs.(15),(16),(17),and (18),help us build a upper bound of∑，eR0+∑，eR∑ses+zy in terms of ∑jes4jnie ++器) ∑+∑∑（场+配） 09∑a S 10 ≤10∑a ≤9∑驰+∑∑+) 9citij 10 (19) ≤10.OPT ≤9∑g the theorem follows immediately. ◇ sjES Hereto,we have a constant-factor approximation for ISCA- ≤9.OPT MP,i.e.,charging with fixed itineraries in a general setting. Let L maxij(ci/10+fij+9citij/(10Ti)).In the first part the theorem follows immediately. of PDA,the maximal timestamp is at most L;in each itera- 5.5 Retransformation:Revert to ISCA-MP tion,PDA scans every connection between itineraries and uncovered devices.In the second part,constructing G In the previous sections,we have developed an approxima- requires O(MN)time;finding a maximal independent ver- tion algorithm of factor 9 for ISCA-MP-T.We now show tex set needs O(N2 log N)time.Therefore,the worst-case how to modify the results obtained by PDA for ISCA-MP. time complexity of PDA is O(LMN N2 log N). We denote by r's and ys the solution to ISCA-MP,and by rs and ys the solution generated by PDA for ISCA-MP-T. 5.6 Example of Running PDA In order to respect constraint(5g),we let We use an example to better illustrate the details of PDA. Fig.5a shows the inputs (i.e.,cis,Tis,tus,and fijs)of the =x,and (20) algorithm.There are 4 itineraries and 4 devices to cover. Fig.5b shows how PDA works in different timestamps
According to lines 24 and 32-33, we have ch=Th ck=Tk. To prove Eq. (18), it is sufficient to prove that fhj þ 9chthj 10Th ¼ E a ðb þ dhjÞ 2 a h i þ 9Echðb þ dhjÞ 2 10aPTh ðEqs. (3) and (4)Þ E a ðb þ dhg þ dkg þ dkjÞ 2 a h i þ 9chEðb þ dhg þ dkg þ dkjÞ 2 10aPTh ðtriangle inequalityÞ 3E a ðb þ dhgÞ 2 þ ðb þ dkgÞ 2 þ ðb þ dkjÞ 2 3a ð8b2 2aÞ h i þ 27chE½ðb þ dhgÞ 2 þ ðb þ dkgÞ 2 þ ðb þ dkjÞ 2 10aPTh 3E a ðb þ dhgÞ 2 a þ ðb þ dkgÞ 2 a þ ðb þ dkjÞ 2 a h i þ 27chEðb þ dhgÞ 2 10aPTh þ 27chEðb þ dkgÞ 2 10aPTh þ 27chEðb þ dkjÞ 2 10aPTh " # 3ðfhg þ fkg þ fkjÞ þ 3 9chthg 10Th þ 9chtkg 10Th þ 9chtkj 10Th 3ðfhg þ fkg þ fkjÞ þ 3 9chthg 10Th þ 9cktkg 10Tk þ 9cktkj 10Tk 3ðag þ ag þ ajÞ 9aj; where the third “” is due to 8b2 2a, as a and b are know constants, and b is much bigger than a. tu Combining the above analyses and Theorem 3, we have Theorem 4. PDA is a factor nine approximation algorithm for ISCA-MP-T. Proof. As previously mentioned, due to the weak duality theorem, P sj2S aj is a lower bound of OPT. Eqs. (15), (16), (17), and (18), help us build a upper bound of P ri2R ciyi 10 þ P ri2R P sj2Sðfij þ 9citij 10Ti Þxij P in terms of sj2S aj, i.e., X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij 9 X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij 9 X sj2S aj 9 OPT; (19) the theorem follows immediately. tu 5.5 Retransformation: Revert to ISCA-MP In the previous sections, we have developed an approximation algorithm of factor 9 for ISCA-MP-T. We now show how to modify the results obtained by PDA for ISCA-MP. We denote by x0 s and y0 s the solution to ISCA-MP, and by xs and ys the solution generated by PDA for ISCA-MP-T. In order to respect constraint (5g), we let x0 ij ¼ xij; and y0 i ¼ P sj2S tijxij Ti & ’: (20) Theorem 5. PDA plus Eq. (20) is a factor 10 approximation algorithm for ISCA with multipick. Proof. Notice that y0 i yi þ P sj2S tijxij Ti , then we have X ri2R ciy0 i þ X ri2R X sj2S fijx0 ij X ri2R ciy0 i þ 10 9 X ri2R X sj2S fijx0 ij 10 9 9 10 X ri2R ci yi þ P sj2S tijxij Ti þ X ri2R X sj2S fijx0 ij ¼ 10 9 9 X ri2R ciyi 10 þ X ri2R X sj2S fij þ 9citij 10Ti xij 10 9 9 X sj2S aj 10X sj2S aj 10 OPT; the theorem follows immediately. tu Hereto, we have a constant-factor approximation for ISCAMP, i.e., charging with fixed itineraries in a general setting. Let L ¼ maxi;jðci=10 þ fij þ 9citij=ð10TiÞÞ. In the first part of PDA, the maximal timestamp is at most L; in each iteration, PDA scans every connection between itineraries and uncovered devices. In the second part, constructing G requires OðMNÞ time; finding a maximal independent vertex set needs OðN2 log NÞ time. Therefore, the worst-case time complexity of PDA is OðLMN þ N2 log NÞ. 5.6 Example of Running PDA We use an example to better illustrate the details of PDA. Fig. 5a shows the inputs (i.e., cis, Tis, tijs, and fijs) of the algorithm. There are 4 itineraries and 4 devices to cover. Fig. 5b shows how PDA works in different timestamps. Fig. 5. Example of running PDA. Note that the a of a device will not increase after being covered. The final solution is, s1 and s2 are closely covered by r3 and r1, respectively; s3 and s4 are normally covered by r1 and r3, respectively. 2842 IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. 16, NO. 10, OCTOBER 2017