1602 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 0.8 information is less important than short-term human mobility 0.7 -Theory behavior in predicting contact arrival rates Fixed probing interval The performance of STAR-PTS and STAR-LMMSE is much 0.6 better.For a missing probability of 20%,the probing interval for STAR-PTS and STAR-LMMSE is about 300 s,which is 0.5 more than three times the probing interval of the constant 墨0.4 probing interval algorithm.In other words,STAR-PTS and STAR-LMMSE use only 1/3 the energy for contact probing 0.3 than constant probing interval schemes.Fig.12 also shows that the performances of STAR-PTS and STAR-LMMSE are nearly 02 the same.Compared to STAR-LMMSE,which estimates arrival 0.1 rates based on history of the past 12 time slots,STAR-PTS only uses the nearest time slot in the estimation.The similar 0.0十 0 306090120150180210240270300 performances of STAR-LMMSE and STAR-PTS suggest that it may be good enough to use a lesser amount of history in the Probing interval(seconds) arrival rate estimation.We take advantage of this to reduce the Fig.11.Comparing the missing probability of the Bluetooth log to theory re- complexity of STAR-MMSE. sults. The STAR-MMSE algorithm gives the best arrival rate esti- mation that can be achieved with perfect knowledge of historical 0.5 arrival rates and the statistics of the contact patterns.The per- Constant probing interval ▲-3TAR.T0D formance of STAR-MMSE is better than STAR-LMMSE when STAR-PTS ■-STAR-LMMSE STAR-MMSE -STAR-Genie the average probing interval is large.For a missing probability of 0.4 20%,the probing interval of STAR-MMSE is over 1.5 times that of STAR-LMMSE and five times that of the constant probing 0.3 scheme.However,the difference with STAR-LMMSE is negli- gible when the probing interval is small.This could have sev- eral explanations.First,STAR-LMMSE uses the detected ar- 0 0.2 rival rate,while the ideal STAR-MMSE uses the true arrival rates in the estimation.Second.STAR-LMMSE only has the 0.1 correlation of arrival rates,while STAR-MMSE has detailed in- formation on the conditional distribution of the arrival rates. Third,STAR-LMMSE uses the time-of-day information in a 0.0 heuristic weighted averaging manner,while STAR-MMSE uses 100 200 300 400 500 600 700 the time-of-day information directly in the conditional mean es- Probing Interval(seconds) timator. Fig.12.Improving energy efficiency by adapting to the contact arrival rate. To further compare STAR-LMMSE and STAR-MMSE,we use the true value of ii in the estimator of STAR-LMMSE The performance of STAR-LMMSE becomes better when the rithms.The energy consumption rate of the algorithms can be probing interval is large,as seen in Fig.13.This is because the calculated through ep/T,where ep is the energy used in each missing probability increases with the probing interval.When probe and T is the average probing interval.5 The curve for the missing probability is large,the detected arrival rate used STAR-Genie provides performance bounds for STAR-based in the estimation might be wrong.Consequently,the estimation adaptive contact-probing algorithms.STAR-Genie is a non- error will increase when wrong historical arrival rates are used causal algorithm that has accurate future contact arrival rates.In in estimation.Therefore,the performance of STAR-LMMSE other words,STAR-Genie shows the optimal tradeoff between can be greatly improved with accurate historical information energy and missing probability when there is no estimation when the probing interval is large.However,even with the ac- error.Comparing the performance of STAR-Genie to the results tual historical arrival rates,the performance of STAR-LMMSE in Fig.3,we see that the missing probability of STAR-Genie still cannot be as good as STAR-MMSE.This may due to the is lower.This can be explained by noting that human contact larger MSE of STAR-LMMSE.In our simulations,the MSE of processes have large variance (>10)in short-term contact STAR-LMMSE with accurate history is 2.2943,while the MSE arrival rates that can be exploited by STAR.Since STAR-Genie of STAR-MMSE is 1.1280.Although STAR-MMSE gives the is noncausal,an implementable contact-probing algorithm best performance,it requires much more storage and training needs to estimate the arrival rate. data than STAR-LMMSE and STAR-PTS.Therefore,STAR- STAR-TOD estimates the arrival rate based on the LMMSE and STAR-PTS may be more appropriate for use in time-of-day information.The performance of STAR-TOD mobile devices due to their simplicity is slightly better than constant probing interval algorithms and not as good as other estimation methods that use short-term D.Contact Duration Distribution arrival history.This observation suggests that the time-of-day In our analysis in Section III,we assumed that the contact SInour Bluetooth experiments,the value ofp is around 2.1 Jas the Bluetooth duration is distributed according to the Pareto distributions with device-discovery process takes 10-20 s. different k.In real contact processes,the probing algorithm1602 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 Fig. 11. Comparing the missing probability of the Bluetooth log to theory re￾sults. Fig. 12. Improving energy efficiency by adapting to the contact arrival rate. rithms. The energy consumption rate of the algorithms can be calculated through , where is the energy used in each probe and is the average probing interval.5 The curve for STAR-Genie provides performance bounds for STAR-based adaptive contact-probing algorithms. STAR-Genie is a non￾causal algorithm that has accurate future contact arrival rates. In other words, STAR-Genie shows the optimal tradeoff between energy and missing probability when there is no estimation error. Comparing the performance of STAR-Genie to the results in Fig. 3, we see that the missing probability of STAR-Genie is lower. This can be explained by noting that human contact processes have large variance ( ) in short-term contact arrival rates that can be exploited by STAR. Since STAR-Genie is noncausal, an implementable contact-probing algorithm needs to estimate the arrival rate. STAR-TOD estimates the arrival rate based on the time-of-day information. The performance of STAR-TOD is slightly better than constant probing interval algorithms and not as good as other estimation methods that use short-term arrival history. This observation suggests that the time-of-day 5In our Bluetooth experiments, the value of is around 2.1 J as the Bluetooth device-discovery process takes 10–20 s. information is less important than short-term human mobility behavior in predicting contact arrival rates. The performance of STAR-PTS and STAR-LMMSE is much better. For a missing probability of 20%, the probing interval for STAR-PTS and STAR-LMMSE is about 300 s, which is more than three times the probing interval of the constant probing interval algorithm. In other words, STAR-PTS and STAR-LMMSE use only 1/3 the energy for contact probing than constant probing interval schemes. Fig. 12 also shows that the performances of STAR-PTS and STAR-LMMSE are nearly the same. Compared to STAR-LMMSE, which estimates arrival rates based on history of the past 12 time slots, STAR-PTS only uses the nearest time slot in the estimation. The similar performances of STAR-LMMSE and STAR-PTS suggest that it may be good enough to use a lesser amount of history in the arrival rate estimation. We take advantage of this to reduce the complexity of STAR-MMSE. The STAR-MMSE algorithm gives the best arrival rate esti￾mation that can be achieved with perfect knowledge of historical arrival rates and the statistics of the contact patterns. The per￾formance of STAR-MMSE is better than STAR-LMMSE when the average probing interval is large. For a missing probability of 20%, the probing interval of STAR-MMSE is over 1.5 times that of STAR-LMMSE and five times that of the constant probing scheme. However, the difference with STAR-LMMSE is negli￾gible when the probing interval is small. This could have sev￾eral explanations. First, STAR-LMMSE uses the detected ar￾rival rate, while the ideal STAR-MMSE uses the true arrival rates in the estimation. Second, STAR-LMMSE only has the correlation of arrival rates, while STAR-MMSE has detailed in￾formation on the conditional distribution of the arrival rates. Third, STAR-LMMSE uses the time-of-day information in a heuristic weighted averaging manner, while STAR-MMSE uses the time-of-day information directly in the conditional mean es￾timator. To further compare STAR-LMMSE and STAR-MMSE, we use the true value of in the estimator of STAR-LMMSE. The performance of STAR-LMMSE becomes better when the probing interval is large, as seen in Fig. 13. This is because the missing probability increases with the probing interval. When the missing probability is large, the detected arrival rate used in the estimation might be wrong. Consequently, the estimation error will increase when wrong historical arrival rates are used in estimation. Therefore, the performance of STAR-LMMSE can be greatly improved with accurate historical information when the probing interval is large. However, even with the ac￾tual historical arrival rates, the performance of STAR-LMMSE still cannot be as good as STAR-MMSE. This may due to the larger MSE of STAR-LMMSE. In our simulations, the MSE of STAR-LMMSE with accurate history is 2.2943, while the MSE of STAR-MMSE is 1.1280. Although STAR-MMSE gives the best performance, it requires much more storage and training data than STAR-LMMSE and STAR-PTS. Therefore, STAR￾LMMSE and STAR-PTS may be more appropriate for use in mobile devices due to their simplicity. D. Contact Duration Distribution In our analysis in Section III, we assumed that the contact duration is distributed according to the Pareto distributions with different . In real contact processes, the probing algorithm