WANG etaL:OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1601 where w is the weight for different estimations.In(23),the amount of memory to store the A;corresponding to different time-of-day information is combined with estimation from combinations of H and Ai-i's.Also,it needs a large amount short-term history to prevent the algorithm from getting stuck of training data for calculating the conditional mean.Therefore, at the nonoptimal operating point.This approach combines it has a much higher complexity compared to STAR-LMMSE both the long-term history of TOD and the short-term history. and STAR-PTS.Though it may not be optimal in terms of min- The long-term history can serve as a baseline of the everyday imizing missing probability,STAR-MMSE can serve as a per- routine of the user.The short-term history will track dynamic formance benchmark for estimation-based contact-probing al- changes in user behavior. gorithms. 3)STAR-LMMSE:STAR linear minimum mean-squared 5)STAR-Genie:STAR-Genie is a noncausal algorithm that error estimation(STAR-LMMSE)uses more short-term corre- assumes that we know the actual arrival rate in the next time lation information than STAR-PTS.It sets the estimation of the slot.It serves as a lower bound for the missing probability of all arrival rate in the next time slot to STAR-based algorithms. 入i-j (24) VI.SIMULATIONS A.Simulation Models Suppose the auto-correlation of arrival rates is We now compare the performance of different adaptive con- tact-probing algorithms by running trace-driven simulations on An= 入i入i+n (25) the data that we have collected. When calculating the missing probability,we use the Blue- tooth contact logs,which are based on a 30-s contact-probing We define interval as the baseline.We apply different adaptive contact- Ao A1 A2 Ag-11 probing algorithms to filter the contact log data.Assume that A0 A1 1-2 a device D has been logged in our experiments from time t to (26) t+T.Then,for a specific adaptive contact-probing algorithm, we say that the contact has been missed if the algorithm does not 40 initiate any probe in the intervalt,t+.The contact missing probability is computed as the ratio of the number of contacts and missed by the adaptive contact-probing algorithm to the total V=[A1 A2...A]. number of contacts made in our data logging experiments. (27) Then setting B.Verification of Analysis First,we verify that the relationship between Tand Pmiss de- [a1a2,...,ad]=V(A-1) (28) rived in(12)is correct for a constant contact-probing interval T. From our logging data,we have computed the decay exponent will minimize the MSE of the linear estimator [21],and the cor- of the contact distribution =0.85.Since the granularity of responding MSE is given by [21] our logging experiments is over 30-s intervals,we setT=30. The comparison between the trace-driven simulations and the E{(-A)2}=A0- (29) analytical results are shown in Fig.11.We see that the results of the simulation are quite close to the theoretical results.Since the constant contact-probing interval algorithm does not adapt Note that STAR-LMMSE only uses short-term history and to the changes in the contact arrival rate,we will use this as the may have the same"warm-up"problem as STAR-PTS.In this lower bound for the average contact-probing interval to achieve case,we can use the same weighted average method as dis- a given missing probability. cussed in STAR-PTS. 4)STAR-MMSE:We can also use the general nonlinear C.Performance Comparison MMSE scheme to estimate the arrival rate by setting [21] We use data-driven simulations to compare the performance 入=E{λlH,入-1，，入i-g} (30)of different adaptive probing algorithms.In the simulation,we use a time slot size of 10 min based on the correlation of human where H is the time of day as in STAR-TOD.In (30).H and contacts shown in Fig.6.Since the correlation drops below 0.1 Acan only take integer values.Therefore.the algorithm after 2 h,we use the arrival rate in the previous 2 h(i.e..g=12) needs to store the Ai corresponding to different combinations to estimate A;in STAR-LMMSE.For STAR-MMSE,we use of H and Ai-js.As we can see from Fig.10,the curve becomes g =4 due to the large storage space and training data size re- flat when Ai is large.Therefore,the algorithm can tolerate large quired by the algorithm.Additionally,we assume STAR-MMSE estimation errors when A:is large.In practice,we can"quan-has perfect knowledge of the arrival rates in the previous time tize"large values of A's so that the number of combinations slots.In this sense,it is a lower bound to the performance of the of H and Ai-i's can be reduced. algorithm that uses the detected arrivals only. The STAR-MMSE algorithm uses both the short-term his- Fig.12 shows the relationship between missing probability tory and time-of-day information.However,it requires a large and the long-term average probing interval for different algo-WANG et al.: OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1601 where is the weight for different estimations. In (23), the time-of-day information is combined with estimation from short-term history to prevent the algorithm from getting stuck at the nonoptimal operating point. This approach combines both the long-term history of TOD and the short-term history. The long-term history can serve as a baseline of the everyday routine of the user. The short-term history will track dynamic changes in user behavior. 3) STAR-LMMSE: STAR linear minimum mean-squared error estimation (STAR-LMMSE) uses more short-term corre￾lation information than STAR-PTS. It sets the estimation of the arrival rate in the next time slot to (24) Suppose the auto-correlation of arrival rates is (25) We define . . . ... ... ... . . . (26) and (27) Then setting (28) will minimize the MSE of the linear estimator [21], and the cor￾responding MSE is given by [21] (29) Note that STAR-LMMSE only uses short-term history and may have the same “warm-up” problem as STAR-PTS. In this case, we can use the same weighted average method as dis￾cussed in STAR-PTS. 4) STAR-MMSE: We can also use the general nonlinear MMSE scheme to estimate the arrival rate by setting [21] (30) where is the time of day as in STAR-TOD. In (30), and can only take integer values. Therefore, the algorithm needs to store the corresponding to different combinations of and s. As we can see from Fig. 10, the curve becomes flat when is large. Therefore, the algorithm can tolerate large estimation errors when is large. In practice, we can “quan￾tize” large values of ’s so that the number of combinations of and ’s can be reduced. The STAR-MMSE algorithm uses both the short-term his￾tory and time-of-day information. However, it requires a large amount of memory to store the corresponding to different combinations of and ’s. Also, it needs a large amount of training data for calculating the conditional mean. Therefore, it has a much higher complexity compared to STAR-LMMSE and STAR-PTS. Though it may not be optimal in terms of min￾imizing missing probability, STAR-MMSE can serve as a per￾formance benchmark for estimation-based contact-probing al￾gorithms. 5) STAR-Genie: STAR-Genie is a noncausal algorithm that assumes that we know the actual arrival rate in the next time slot. It serves as a lower bound for the missing probability of all STAR-based algorithms. VI. SIMULATIONS A. Simulation Models We now compare the performance of different adaptive con￾tact-probing algorithms by running trace-driven simulations on the data that we have collected. When calculating the missing probability, we use the Blue￾tooth contact logs, which are based on a 30-s contact-probing interval as the baseline. We apply different adaptive contact￾probing algorithms to filter the contact log data. Assume that a device D has been logged in our experiments from time to . Then, for a specific adaptive contact-probing algorithm, we say that the contact has been missed if the algorithm does not initiate any probe in the interval . The contact missing probability is computed as the ratio of the number of contacts missed by the adaptive contact-probing algorithm to the total number of contacts made in our data logging experiments. B. Verification of Analysis First, we verify that the relationship between and de￾rived in (12) is correct for a constant contact-probing interval . From our logging data, we have computed the decay exponent of the contact distribution . Since the granularity of our logging experiments is over 30-s intervals, we set . The comparison between the trace-driven simulations and the analytical results are shown in Fig. 11. We see that the results of the simulation are quite close to the theoretical results. Since the constant contact-probing interval algorithm does not adapt to the changes in the contact arrival rate, we will use this as the lower bound for the average contact-probing interval to achieve a given missing probability. C. Performance Comparison We use data-driven simulations to compare the performance of different adaptive probing algorithms. In the simulation, we use a time slot size of 10 min based on the correlation of human contacts shown in Fig. 6. Since the correlation drops below 0.1 after 2 h, we use the arrival rate in the previous 2 h (i.e., ) to estimate in STAR-LMMSE. For STAR-MMSE, we use due to the large storage space and training data size re￾quired by the algorithm. Additionally, we assume STAR-MMSE has perfect knowledge of the arrival rates in the previous time slots. In this sense, it is a lower bound to the performance of the algorithm that uses the detected arrivals only. Fig. 12 shows the relationship between missing probability and the long-term average probing interval for different algo-