1600 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 Assumptions and Methodology 800 In this section.we investigate the design of adaptive contact- -c=20 ●—G=50 probing algorithms that can achieve a good tradeoff between 600 ▲c=100 the probability of a missed contact and energy consumption. As described in Section II-A,the energy consumption rate is inversely proportional to the average probing interval;e.g.,a device with average probing interval of 30 s will consume two 400 times more energy than a device with average probing interval of 60 s. From our earlier analysis in Section III,we see that in order to 200- compute the optimal contact-probing interval,we require k,the power law exponent for the contact duration distribution and the arrival rate.We contend that variations in the contact duration distribution,if any,will occur over large time scales.It is reason- 10 15 able to hypothesize that contact duration distribution will always ,(contact/hour） follow a power law but with different decay coefficientsk over Fig.10. Relationship between optimal contact-probing interval and the arrival large time scales.This is validated by the fact that experiments rate. at widely differing geographical locations have all displayed a power-law contact duration distribution but with different decay coefficients [14],[12],[20].For the rest of this section,we as- STAR-TOD first collects the historical average arrival rate sume that the contact duration distribution is known and focus Ar at hour H (e.g.,A12 is the arrival rate averaged over dif- on the problem of adapting the contact-probing interval to vari- ferent days for the same time period of 1200-1259 h).Then, ations in arrival rate.This assumption will be further justified in STAR-TOD reads the current hour H from the system clock of Section VI. the device and sets As shown in Section III,we can find the optimal value of the contact-probing interval by solving (17)when the arrival rate 入=AH (20) is known.Since our contact duration is Pareto-distributed,we have In other words,STAR-TOD implicitly assumes the contact ar- rival rate is highly correlated to time of day,and the arrival rate 1-5 will not vary dramatically in different days. Ti=T( (1-+1 (19) 入kT 2)STAR-PTS:The STAR-previous time slot(STAR-PTS) scheme uses the detected arrival rate in the previous time slots where k:=0.85 and T=30 s for our logging data as shown as the estimation i.More specifically,it sets in Section IV.With a different energy cost of c,we can achieve 入 different tradeoff points between Pmiss and T.Fig.10 shows 入=-j (21) the optimal contact-probing interval for different arrival rates. We see that when the arrival rate is high,the optimal T*quickly where Ai is the nearest time slot with nonzero arrival rate.If the converges to T.This means we can tolerate a certain amount arrival rate in the last time slot Ai_1 is nonzero,(21)will set the of estimation error in A;when the contact arrival rate is high. estimate to入i=入i-l. However,when the contact rate is small,we need to estimate Note that the historical arrival rate Aj used in STAR-PTS it accurately so that we will not underestimate the rate and use comes from the arrival rate observed by the device.When T extremely long contact-probing intervals. is large,the missing probability will be quite high,andj could be inaccurate.To compensate this effect,we set Aj as A.Contact Arrival Rate Estimation 入=1-Dmis(Tj刀 (22) Based on our analysis,we propose a class of adaptive con- tact-probing schemes based on short-term arrival rate estima- tion (STAR).STAR updates the estimate of the contact arrival where n is the number of new contacts detected by the device rate Ai periodically using a time slot length of L.The estimation in time slot j. is based on information available to the probing devices,such STAR-PTS uses only the short-term history of the arrival as time of day,statistics of historical arrival rates,and observed process.This scheme may converge to certain nonoptimal op- arrival rates in previous time slots.STAR then sets the probing erating points for human contact process.For example,after a interval for next probing according to the optimal T*calculated night where no contacts arrive,the Ai will converge to zero,and from(l9)using the estimated arrival rate入： the T*could be very long.In the next morning,it will be difficult We will consider the following estimation methods for STAR to detect new contacts since the missing probability is high due and compare their performance in Section VI. to the large T*.Therefore,STAR-PTS will keep on assuming 1)STAR-TOD:The STAR-time of day(STAR-TOD)scheme Ai is zero until it detects some contact by chance.To reduce this is motivated by two facts.First,people are creatures of habit. long“wam-up time”'of STAR-PTS in the morning,we set入i Second,Fig.7 shows that the auto-correlation peaks at 24-h as lags.These suggest that it may be possible to estimate the arrival rate using the time-of-day information. 入= A5+(1-w)AH (23) 2-71600 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 Assumptions and Methodology In this section, we investigate the design of adaptive contact￾probing algorithms that can achieve a good tradeoff between the probability of a missed contact and energy consumption. As described in Section II-A, the energy consumption rate is inversely proportional to the average probing interval; e.g., a device with average probing interval of 30 s will consume two times more energy than a device with average probing interval of 60 s. From our earlier analysis in Section III, we see that in order to compute the optimal contact-probing interval, we require , the power law exponent for the contact duration distribution and the arrival rate. We contend that variations in the contact duration distribution, if any, will occur over large time scales. It is reason￾able to hypothesize that contact duration distribution will always follow a power law but with different decay coefficients over large time scales. This is validated by the fact that experiments at widely differing geographical locations have all displayed a power-law contact duration distribution but with different decay coefficients [14], [12], [20]. For the rest of this section, we as￾sume that the contact duration distribution is known and focus on the problem of adapting the contact-probing interval to vari￾ations in arrival rate. This assumption will be further justified in Section VI. As shown in Section III, we can find the optimal value of the contact-probing interval by solving (17) when the arrival rate is known. Since our contact duration is Pareto-distributed, we have (19) where and s for our logging data as shown in Section IV. With a different energy cost of , we can achieve different tradeoff points between and . Fig. 10 shows the optimal contact-probing interval for different arrival rates. We see that when the arrival rate is high, the optimal quickly converges to . This means we can tolerate a certain amount of estimation error in when the contact arrival rate is high. However, when the contact rate is small, we need to estimate it accurately so that we will not underestimate the rate and use extremely long contact-probing intervals. A. Contact Arrival Rate Estimation Based on our analysis, we propose a class of adaptive con￾tact-probing schemes based on short-term arrival rate estima￾tion (STAR). STAR updates the estimate of the contact arrival rate periodically using a time slot length of . The estimation is based on information available to the probing devices, such as time of day, statistics of historical arrival rates, and observed arrival rates in previous time slots. STAR then sets the probing interval for next probing according to the optimal calculated from (19) using the estimated arrival rate . We will consider the following estimation methods for STAR and compare their performance in Section VI. 1) STAR-TOD: The STAR-time of day (STAR-TOD) scheme is motivated by two facts. First, people are creatures of habit. Second, Fig. 7 shows that the auto-correlation peaks at 24-h lags. These suggest that it may be possible to estimate the arrival rate using the time-of-day information. Fig. 10. Relationship between optimal contact-probing interval and the arrival rate. STAR-TOD first collects the historical average arrival rate at hour (e.g., is the arrival rate averaged over dif￾ferent days for the same time period of 1200–1259 h). Then, STAR-TOD reads the current hour from the system clock of the device and sets (20) In other words, STAR-TOD implicitly assumes the contact ar￾rival rate is highly correlated to time of day, and the arrival rate will not vary dramatically in different days. 2) STAR-PTS: The STAR-previous time slot (STAR-PTS) scheme uses the detected arrival rate in the previous time slots as the estimation . More specifically, it sets (21) where is the nearest time slot with nonzero arrival rate. If the arrival rate in the last time slot is nonzero, (21) will set the estimate to . Note that the historical arrival rate used in STAR-PTS comes from the arrival rate observed by the device. When is large, the missing probability will be quite high, and could be inaccurate. To compensate this effect, we set as (22) where is the number of new contacts detected by the device in time slot . STAR-PTS uses only the short-term history of the arrival process. This scheme may converge to certain nonoptimal op￾erating points for human contact process. For example, after a night where no contacts arrive, the will converge to zero, and the could be very long. In the next morning, it will be difficult to detect new contacts since the missing probability is high due to the large . Therefore, STAR-PTS will keep on assuming is zero until it detects some contact by chance. To reduce this long “warm-up time” of STAR-PTS in the morning, we set as (23)