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 com￾bines solar energy harvesting for cluster heads and wireless charging for normal sensor nodes. Chen et al. [31] investi￾gated 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 unneces￾sary energy wasted, i.e., movement-energy and loss-energy. The optimization techniques are inspired by two opti￾mization 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 custom￾ers 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 daily￾use 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 devi￾ces within the area of interest. For areas with sparse devices, deploying fixed chargers may be not cost￾efficient; 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 charg￾ing 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 deter￾mine 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 recharge￾able 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 sin￾gle 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 caus￾ing 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 sup￾ported by petrol,1 and we assume the amount of move￾ment-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 dis￾tance 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