WANG etaL:OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1599 1.0 TABLE I CONTACT ARRIVAL RATE IN DIFFERENT TIME SCALES. Contact duration 0.8 -Number of new contacts Time slot Mean arrival rate Arrival rate Normalized ····Number of contacts size (contact/time slot) variance variance 5 minutes 0.2150 1.3350 28.8923 10 minutes 0.4299 4.4575 24.1172 0.6 30 minutes 1.2901 30.4295 18.2930 I hour 2.5973 113.8747 17.1142 0.4 12 600 (noy. Average contact 10 arrival rate 500 0.2 ■-Variance of contact arrival rate 0.0 风风A风AA风 400 72 96 120 144168192 216240 Hours 6 300 Fig.7.Normalized correlation of contact duration and contact number over 200 long time periods (=5 min). 2 100 1000 Linear fitting (slope=0.7636) ·-·slope0.5 0 0 9 12 H(time of day) 100 Fig.9.Contact arrival rate and its variance over time of day. the process,the variance increases faster than CL1/2 when the 10. time scale L increases.The normalized variance of the arrival rate is the variance divided by the mean arrival rate.As shown in Fig.3,a larger normalized variance of the arrival rate leads to potentially better performance.In our human contact process, the normalized variance of the contact process is larger than 10 100 1000 10000 when the time slot size L is smaller than I h.Therefore,adaptive L(minutes) contact probing should perform better than the lowest curve in Fig.8.The R/S statistic of the contact arrival process. Fig.3 when the arrival rate in the next hour is known. G.Contact Arrival Rate versus Time of Day and The contact arrival rate distribution varies with time of day. In Fig.9,we plot the average rate at which new contacts are seen at different times of the day.The contact arrival rate during the early morning is quite small.This implies that we can use longer S(t,L (X-X五)2，X,五 contact-probing intervals during the early morning to save en- L ergy as described in Section III.The variance of the contact ar- i=t+1 rival rate over different days is also plotted in Fig.9.We see If ER(L/S(L)}=CL,with Hurst parameter hE(0.5,1). that the variance is quite large.This shows the contact arrival then the process is self-similar [19].From Fig.8,we see that our rate at the same hour in different days may vary drastically.Al- process has a Hurst parameter close to 0.76. though the arrival rates exhibit some patterns in a 24-h period, This implies that the contact arrivals are not only long-range we cannot simply use the time of day to infer the arrival rate due dependent but also bursty.An intuitive model for this is that ar- to the large variance at the same time of day. rivals follow an ON-OFF process where the ON and OFF durations have memory.This can potentially be exploited to achieve en- V.ADAPTIVE PROBING ALGORITHMS ergy savings. In Section IV,we saw that human contact patterns have time- F.Mean and Variance of Contact Arrival Rate varying contact arrival rates when the time slot size L is smaller than 1 h.Also,the contact arrival rates have high short-term cor- As discussed in Section III,we can adapt the probing interval relation and exhibit a 24-h periodic pattern.These observations according to the contact arrival rate when the arrival rate is time- suggest that the human contact process is both time-varying and varying.Table I shows the mean and variance of the contact predictable.We exploit these characteristics to design an effi- arrival rates at different time scales.Due to the self-similarity of cient adaptive contact-probing scheme in this section.WANG et al.: OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1599 Fig. 7. Normalized correlation of contact duration and contact number over long time periods ( min). Fig. 8. The statistic of the contact arrival process. and If , with Hurst parameter , then the process is self-similar [19]. From Fig. 8, we see that our process has a Hurst parameter close to 0.76. This implies that the contact arrivals are not only long-range dependent but also bursty. An intuitive model for this is that ar￾rivals follow an ON–OFF process where the ON and OFF durations have memory. This can potentially be exploited to achieve en￾ergy savings. F. Mean and Variance of Contact Arrival Rate As discussed in Section III, we can adapt the probing interval according to the contact arrival rate when the arrival rate is time￾varying. Table I shows the mean and variance of the contact arrival rates at different time scales. Due to the self-similarity of TABLE I CONTACT ARRIVAL RATE IN DIFFERENT TIME SCALES. Fig. 9. Contact arrival rate and its variance over time of day. the process, the variance increases faster than when the time scale increases. The normalized variance of the arrival rate is the variance divided by the mean arrival rate. As shown in Fig. 3, a larger normalized variance of the arrival rate leads to potentially better performance. In our human contact process, the normalized variance of the contact process is larger than 10 when the time slot size is smaller than 1 h. Therefore, adaptive contact probing should perform better than the lowest curve in Fig. 3 when the arrival rate in the next hour is known. G. Contact Arrival Rate versus Time of Day The contact arrival rate distribution varies with time of day. In Fig. 9, we plot the average rate at which new contacts are seen at different times of the day. The contact arrival rate during the early morning is quite small. This implies that we can use longer contact-probing intervals during the early morning to save en￾ergy as described in Section III. The variance of the contact ar￾rival rate over different days is also plotted in Fig. 9. We see that the variance is quite large. This shows the contact arrival rate at the same hour in different days may vary drastically. Al￾though the arrival rates exhibit some patterns in a 24-h period, we cannot simply use the time of day to infer the arrival rate due to the large variance at the same time of day. V. ADAPTIVE PROBING ALGORITHMS In Section IV, we saw that human contact patterns have time￾varying contact arrival rates when the time slot size is smaller than 1 h. Also, the contact arrival rates have high short-term cor￾relation and exhibit a 24-h periodic pattern. These observations suggest that the human contact process is both time-varying and predictable. We exploit these characteristics to design an effi- cient adaptive contact-probing scheme in this section