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 incurTherefore, 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 dic￾tated 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 movement￾energy 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 minimiza￾tion 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 Asso￾ciation 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 associa￾tion (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 loss￾energy, 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