ZHANG ET AL.:OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2843 S30 「3 (2 ○S2 S6O Rechargeable sensor S4 51 S5O HyperTerminal OS8 S100 零年果年季年 Mobile charger AP 28.51m (a)Hardware (b)An example of sensor node placement Fig.6.Our testbed consists of 4 TX91501 power transmitters produced by Powercast [34].10 rechargeable sensor nodes,and an AP In the first part of PDA,when ts=2,since a1=2=f31+assume that the amount of energy required by each sensor 9c3t31/(10T3),the connection between r3 and s1 becomes node is 10 ml. ful.When ts=4,since∑，Bj=Ba1=2=c/10,r The transmitting power of TX91501 is 3 W.We combine a becomes temporarily selected,and all devices (here,only TX91501 with a mobile robot to obtain a mobile charger.The s)that have full connections with ra are declared as being movement of the charger is supported by the battery and a covered.Later,when a changes to 4,the connection charger consumes roughly 4J per meter.The battery capac- between s4 and r3 becomes full,that is,sa is covered and its ity of each transmitter is 1,300 J.We choose four candidate covering host is r3.a and a will not increase any more itineraries,as shown in Fig.6.The physical lengths of these hereafter.When ts =6,it is not hard to verify that ri is tem- itineraries are 99.79,71.28,66.52,and 59.09 m,respectively porarily selected and covers s2 and s3. The charging area of a TX91501 transmitter is roughly a sec- In the second part of PDA,R={r,r3}.Since there is tor with with an angle of 60,therefore,when a mobile char- not any device that has positive connections with both of ger approaches a sensor node,we may need to manually them,the maximal independent set D is (r,rs),too.In the adjust the orientation of the TX91501 transmitter to make final solution,s and s2 are closely covered by rs and r,sure that the sensor node to be charged is within the charg- respectively;ss and sa are normally covered by ri and r3,ing area of the charger. respectively.The energy cost of this solution is 38(see Eq.(5 In our testbed,the AP connecting to a laptop is responsi- a)),while the optimal solution is to select r twice,yielding ble for collecting the received power information (along a cost of 31.Note that though the approximation factor of with temperature,light,and humidity information)of each PDA is 10,on average,it works much better than the bound.rechargeable sensor node and sending it the HyperTerminal on the laptop,as shown in Fig.6. 5.7 Summary We present PDA for ISCA-MP in this section.We first relax 6.2 Experimental Results integral variables to get ISCA-MP-PL and its dual ISCA-MP- We are interested in comparing four algorithms,including DL.We then fix one variable in ISCA-MP-DL to get ISCA- OPT,PDA,GSA,and RAN.We use the optimal fractional MP-DL-T and its corresponding transformed primal integral solution by solving the LP-relaxation of Egs.(5)and (8) problem ISCA-MP-T.We design an algorithm,PDA,for using the Python PuLP package [35]to replace the optimal ISCA-MP-T with an approximation ratio of 9.Finally we re- integral solution OPT,as the former is a lower bound of the transform ISCA-MP-T to ISCA-MP and prove that PDA is a latter.The random solution RAN is obtained by first ran- factor 10 approximation algorithm for ISCA-MP. domly selecting itineraries and then randomly determining charging association,under the capacity constraints.We fix 6 FIELD EXPERIMENTS four candidate itineraries and run four algorithms on ten different placements of rechargeable sensor nodes.The To better validate the proposed algorithms,we conduct real average,maximum,and minimum results among the ten field experiments in this section. runs are shown in Figs.7,9,and 10. Fig.7 shows the comparison results.Generally speaking, 6.1 Experimental Setup PDA performs better than GSA,and GSA outperforms We develop a testbed that consists of 4 TX91501 power RAN.PDA allows each itinerary to be selected more than transmitters produced by Powercast [341,10 rechargeable once,thus,there are more opportunities for PDA to improve sensor nodes,and an AP,as shown in Fig.6.All devices are the results than GSA.The gap between PDA and OPT is at deployed within a square of 26.14 x 28.51 m.Rechargeable most 23 percent of OPT,which is consistent with our theo- sensor nodes are randomly placed within this area.We retic analysis.When rechargeable sensor nodes are placedIn the first part of PDA, when ts ¼ 2, since a1 ¼ 2 ¼ f31þ 9c3t31=ð10T3Þ, the connection between r3 and s1 becomes full. When ts ¼ 4, since P sj b3j ¼ b31 ¼ 2 ¼ c3=10, r3 becomes temporarily selected, and all devices (here, only s1) that have full connections with r3 are declared as being covered. Later, when a4 changes to 4, the connection between s4 and r3 becomes full, that is, s4 is covered and its covering host is r3. a1 and a4 will not increase any more hereafter. When ts ¼ 6, it is not hard to verify that r1 is tem￾porarily selected and covers s2 and s3. In the second part of PDA, Rts ¼ fr1; r3g. Since there is not any device that has positive connections with both of them, the maximal independent set D is fr1; r3g, too. In the final solution, s1 and s2 are closely covered by r3 and r1, respectively; s3 and s4 are normally covered by r1 and r3, respectively. The energy cost of this solution is 38 (see Eq. (5 a)), while the optimal solution is to select r1 twice, yielding a cost of 31. Note that though the approximation factor of PDA is 10, on average, it works much better than the bound. 5.7 Summary We present PDA for ISCA-MP in this section. We first relax integral variables to get ISCA-MP-PL and its dual ISCA-MP￾DL. We then fix one variable in ISCA-MP-DL to get ISCA￾MP-DL-T and its corresponding transformed primal integral problem ISCA-MP-T. We design an algorithm, PDA, for ISCA-MP-T with an approximation ratio of 9. Finally we re￾transform ISCA-MP-T to ISCA-MP and prove that PDA is a factor 10 approximation algorithm for ISCA-MP. 6 FIELD EXPERIMENTS To better validate the proposed algorithms, we conduct real field experiments in this section. 6.1 Experimental Setup We develop a testbed that consists of 4 TX91501 power transmitters produced by Powercast [34], 10 rechargeable sensor nodes , and an AP, as shown in Fig. 6. All devices are deployed within a square of 26.14  28.51 m. Rechargeable sensor nodes are randomly placed within this area. We assume that the amount of energy required by each sensor node is 10 mJ. The transmitting power of TX91501 is 3 W. We combine a TX91501 with a mobile robot to obtain a mobile charger. The movement of the charger is supported by the battery and a charger consumes roughly 4J per meter. The battery capac￾ity of each transmitter is 1,300 J. We choose four candidate itineraries, as shown in Fig. 6. The physical lengths of these itineraries are 99.79, 71.28, 66.52, and 59.09 m, respectively. The charging area of a TX91501 transmitter is roughly a sec￾tor with with an angle of 60 , therefore, when a mobile char￾ger approaches a sensor node, we may need to manually adjust the orientation of the TX91501 transmitter to make sure that the sensor node to be charged is within the charg￾ing area of the charger. In our testbed, the AP connecting to a laptop is responsi￾ble for collecting the received power information (along with temperature, light, and humidity information) of each rechargeable sensor node and sending it the HyperTerminal on the laptop, as shown in Fig. 6. 6.2 Experimental Results We are interested in comparing four algorithms, including OPT, PDA, GSA, and RAN. We use the optimal fractional solution by solving the LP-relaxation of Eqs. (5) and (8) using the Python PuLP package [35] to replace the optimal integral solution OPT, as the former is a lower bound of the latter. The random solution RAN is obtained by first ran￾domly selecting itineraries and then randomly determining charging association, under the capacity constraints. We fix four candidate itineraries and run four algorithms on ten different placements of rechargeable sensor nodes. The average, maximum, and minimum results among the ten runs are shown in Figs. 7, 9, and 10. Fig. 7 shows the comparison results. Generally speaking, PDA performs better than GSA, and GSA outperforms RAN. PDA allows each itinerary to be selected more than once, thus, there are more opportunities for PDA to improve the results than GSA. The gap between PDA and OPT is at most 23 percent of OPT, which is consistent with our theo￾retic analysis. When rechargeable sensor nodes are placed Fig. 6. Our testbed consists of 4 TX91501 power transmitters produced by Powercast [34], 10 rechargeable sensor nodes, and an AP. ZHANG ET AL.: OPTIMIZING ITINERARY SELECTION AND CHARGING ASSOCIATION FOR MOBILE CHARGERS 2843