1604 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 the bursty nature to find a good tradeoff between missing prob- consume considerable energy in periodic listening.Therefore, ability and energy.This is what STAR implicitly does. there is a tradeoff between the listening frequency and energy consumption of sending probing messages [31].Second,the B.Other Heuristics energy used in information exchange after the contact has been It is also possible to use other heuristics in adaptive con- detected should also be considered.In this case,the device may tact-probing algorithms.For example,we can use the additive need to use additional information-such as the importance increase/multiplicative decrease (AIMD)algorithm in the adap- of the contact,expected amount of information exchange,and tive contact-probing scheme.The AIMD algorithm additively residual energy-to decide whether to take the contact or not. increases the probing interval when no new contacts are discov- ered and decreases the probing interval by half when new con- APPENDIX tacts are detected.Although AIMD changes the probing interval CONTACT MISSING PROBABILITY according to the arrival rate as in STAR algorithm,the perfor- WHEN PROBES ARE UNRELIABLE mance of AIMD is not as good as STAR-PTS,as shown in [1]. Consider the case that a probe can fail to detect a present contact with probability K.We also assume that the failure C.Unknown Contact Duration Distribution probabilities of consequent probes are independent.For con- In contact processes other than human contacts,the intercon- tacts with tD E0,T],they will either not be probed at all or tact times could be stationary while the contact duration distri- only be probed once during their contact duration.As shown bution could change.In such processes,it is hard to calculate in Section II,the probability that these contacts will not be Piss from the observations of the device since we do not have probed isT Therefore,the probability that these the information on contact duration distribution.It is shown in contacts can be probed once isE.As probes can [1]that we can use the percentage of short contacts,which are fail with probability of K,the missing probability given that contacts that are only detected by the device in one probing and tD∈[0，T]is leave in the next probing,to bound the missing probability and adapt to the unknown contact duration distribution. Pmiss(Tl0≤tD<T) D.Maintaining Short-Term Pmiss T-E(tpltp<TE(tpltp<T).(31) T T Even though STAR maintains a low missing probability Similarly,for contacts with tp e nT,(n+1)T,they can be over large time scales,it can miss a relatively large fraction probed by n times or n+1 times during their contact dura- of contacts in the short term.This is because we have so far tion.If a contact has been probed for n times,the probability assumed that when a device is not probing,it has no way of knowing if new contacts have arrived even if those new contacts of missing that contact is for independent probes.Define are probing.However,if devices are cognizant of the fact that En EftplnT<tD<(n+1)T}-nT.We have they have been probed,this information can clearly be used to better adapt the probing interval and thereby reduce the Pis(InT≤t切<(n+1T)=T-E++1E T T short term contact missing probability.We point out that our (32) analysis and simulations were motivated by current Bluetooth Therefore implementations,which do not expose the fact that a device has Pmiss(T) been probed,to the application.However,this constraint is not 00 fundamental and can easily be taken into account. Pmi(TlmT≤tD<(n+1)T)(Fo(m+1)T)-Fo(nT) n=0 E.Synthetic Contact Models Our empirical data set for contact patterns is much larger than FD((n+1)T)-FD(nT)) any comparable data set.We have learned quite a bit about mo- bile device contact patterns and are certain that there is much more that can be gleaned.In addition,we believe that our data Note that Pmiss only depends on FD()and in this case. set and analysis can be used to develop synthetic models for real-world contact patterns,as done in [30](for modeling In- ACKNOWLEDGMENT ternet traffic)and [25](for modeling association with WiFi ac- The authors wish to thank F.Kohwaja for the implementation cess points). on mobile phones. F.Energy Consumption During Contact Process REFERENCES We only consider energy used for sending out probing [1]W.Wang,V.Srinivasan,and M.Motani,"Adaptive contact probing messages in this paper.Energy used in other parts of the mechanisms for delay tolerant applications,"in Proc.ACM MobiCom, contact process should also be considered when designing 2007,Pp.230-241. [2]K.Fall,"A delay-tolerant network architecture for challenged inter- the contact protocols.First,a device needs to periodically nets,"in Proc.ACM SIGCOMM,2003.pp.27-34. listen to the channel in order to be probed.Increasing the [3]S.Jain,K.Fall,and R.Patra,"Routing in a delay tolerant network," listening frequency can reduce the time duration of device SIGCOMM Comput.Commun.Rev.,vol.34,no.4,pp.145-158,2004. discovery.Thus,energy used in each probe for the probing [4]M.Grossglauser and D.Tse."Mobility increases the capacity of ad hoc wireless networks,"IEEE/ACM Trans.Netw.,vol.10,no.4,pp device can be reduced.However,the device to be probed will 477486.Aug.2002.1604 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 the bursty nature to find a good tradeoff between missing prob￾ability and energy. This is what STAR implicitly does. B. Other Heuristics It is also possible to use other heuristics in adaptive con￾tact-probing algorithms. For example, we can use the additive increase/multiplicative decrease (AIMD) algorithm in the adap￾tive contact-probing scheme. The AIMD algorithm additively increases the probing interval when no new contacts are discov￾ered and decreases the probing interval by half when new con￾tacts are detected. Although AIMD changes the probing interval according to the arrival rate as in STAR algorithm, the perfor￾mance of AIMD is not as good as STAR-PTS, as shown in [1]. C. Unknown Contact Duration Distribution In contact processes other than human contacts, the intercon￾tact times could be stationary while the contact duration distri￾bution could change. In such processes, it is hard to calculate from the observations of the device since we do not have the information on contact duration distribution. It is shown in [1] that we can use the percentage of short contacts, which are contacts that are only detected by the device in one probing and leave in the next probing, to bound the missing probability and adapt to the unknown contact duration distribution. D. Maintaining Short-Term Even though STAR maintains a low missing probability over large time scales, it can miss a relatively large fraction of contacts in the short term. This is because we have so far assumed that when a device is not probing, it has no way of knowing if new contacts have arrived even if those new contacts are probing. However, if devices are cognizant of the fact that they have been probed, this information can clearly be used to better adapt the probing interval and thereby reduce the short term contact missing probability. We point out that our analysis and simulations were motivated by current Bluetooth implementations, which do not expose the fact that a device has been probed, to the application. However, this constraint is not fundamental and can easily be taken into account. E. Synthetic Contact Models Our empirical data set for contact patterns is much larger than any comparable data set. We have learned quite a bit about mo￾bile device contact patterns and are certain that there is much more that can be gleaned. In addition, we believe that our data set and analysis can be used to develop synthetic models for real-world contact patterns, as done in [30] (for modeling In￾ternet traffic) and [25] (for modeling association with WiFi ac￾cess points). F. Energy Consumption During Contact Process We only consider energy used for sending out probing messages in this paper. Energy used in other parts of the contact process should also be considered when designing the contact protocols. First, a device needs to periodically listen to the channel in order to be probed. Increasing the listening frequency can reduce the time duration of device discovery. Thus, energy used in each probe for the probing device can be reduced. However, the device to be probed will consume considerable energy in periodic listening. Therefore, there is a tradeoff between the listening frequency and energy consumption of sending probing messages [31]. Second, the energy used in information exchange after the contact has been detected should also be considered. In this case, the device may need to use additional information—such as the importance of the contact, expected amount of information exchange, and residual energy—to decide whether to take the contact or not. APPENDIX CONTACT MISSING PROBABILITY WHEN PROBES ARE UNRELIABLE Consider the case that a probe can fail to detect a present contact with probability . We also assume that the failure probabilities of consequent probes are independent. For con￾tacts with , they will either not be probed at all or only be probed once during their contact duration. As shown in Section II, the probability that these contacts will not be probed is . Therefore, the probability that these contacts can be probed once is . As probes can fail with probability of , the missing probability given that is (31) Similarly, for contacts with , they can be probed by times or times during their contact dura￾tion. If a contact has been probed for times, the probability of missing that contact is for independent probes. Define . We have (32) Therefore Note that only depends on and in this case. ACKNOWLEDGMENT The authors wish to thank F. Kohwaja for the implementation on mobile phones. REFERENCES [1] W. Wang, V. Srinivasan, and M. Motani, “Adaptive contact probing mechanisms for delay tolerant applications,” in Proc. ACM MobiCom, 2007, pp. 230–241. [2] K. Fall, “A delay-tolerant network architecture for challenged inter￾nets,” in Proc. ACM SIGCOMM, 2003, pp. 27–34. [3] S. Jain, K. Fall, and R. Patra, “Routing in a delay tolerant network,” SIGCOMM Comput. Commun. Rev., vol. 34, no. 4, pp. 145–158, 2004. [4] M. Grossglauser and D. Tse, “Mobility increases the capacity of ad hoc wireless networks,” IEEE/ACM Trans. Netw., vol. 10, no. 4, pp. 477–486, Aug. 2002