1594 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 te(1): te(2) The overall missing probability Pmiss can be derived in a similar way(see the Appendix).Similar to the reliable probes case,the Contact 3 missing probability for unreliable probes is also independent of Contact 2 to(3) the intercontact time distribution.In the rest of this paper,we to(2) Contact 1 only consider cases where all contact probes are reliable. tp(1) C.Optimal Contact-Probing Scheme We will now prove the following theorem about the constant contact-probing scheme described earlier. Fig.1.Illustrating the contacts for a specific user probing at a constant in- terval T. Theorem 1:Consider a contact process for which the con- tact durations are i.i.d and the distribution of intercontact times is stationary,with an expected intercontact time of Consider the class of contact-probing strategies that do not exploit knowl- that for a device A.a contact B is missed if B is not discovered by A's probes.We will relax this later to compute the missing edge of the contact process.Then,among all contact-probing probability when neither A nor B's probes discover each other. strategies with the same average contact-probing interval,the Let us first consider the simplest possible contact strategy,where strategy that probes at constant intervals achieves the minimum each device probes for contacts at constant intervals of T(see missing probability. Fig.1). Proof:Consider a large interval of time L.Let us con- sider all strategies that probe the environment n times in this We first consider the case when contact probes are reliable; i.e.,every probe can successfully detect all contacts around the interval.As shown previously,for the strategy that probes at device.If tp T,the contact will never be missed.Consider a constant intervalsT the missing probability over dura- contact i that is initiated at time nT-x,nT-+dr],where tion L is Piss(T)=FD()dz.Assume that an arbi- d is an arbitrarily small value so that the time interval can be trary scheme probes n times at t1,t2,...,tn.Define to =0 treated as a time point.This contact will not be detected by the and tn+1 =nT.Then,we have n+1 intervals of I1=t- mobile at time nT if tp(i)<t,which happens with prob- to:12=t2-t1,...,In+1 =tn+1-tn.Since the scheme se- ability of Fp(t).By Blackwell's Theorem in renewal theory lects probe time ti without knowledge of the contact process,the [15],when the contact process is a general renewal process with expected number of missed contacts in an interval ofti1,ti a nonlattice distribution function,we can calculate the long-term isFp()dr,for1.All the contacts that occur in average missing probability given the probing interval of T as [tn,nT will be missed.The expected missing probability is ims(四= Fp(x)dx. (1) Fp(t)dr+Xn+ (3) Note that we do not need to restrict the intercontact time distri- since the expected number of contacts arriving in duration L is bution to be memoryless to perform the averaging procedure in λL.For Ii≥T,we have (1). Consider the mean value of tp given that tp T,which is E(tpltp <T}o [1-Fp()/Fp(T)ldr.Then, Pmiss(T)can be expressed as Pnis(1)=T-E(tpltp<Tx E(T). FD(T)d (2) =1 p(x)dx+(Ii-T)FD(T).(4) For a constant contact-probing interval of T,any contact with duration larger than T will always be detected.Equation Similarly,when Ii<T we have (2)shows that for a contact with duration shorter than T, the expected probability that the contact will be missed is T-EftpltT.Therefore,only contacts with duration smaller than T will be missed.If all the contacts with tp T have 入 zero contact duration,then Pniss(T)will be exactly Fp(T). The key observation here is that for a constant probing rT scheme,if the contact durations are i.i.d.and the intercontact ≥入F()dc-入 Fp(T)dc times are stationary,then the missing probability depends only on the distribution of the contact duration and the con- Fp(E)dx+(Ii-T)Fp(T).(5) tact-probing interval T.It is independent of the intercontact time distribution. We also have In real networks,contact probes are unreliable due to the nondeterministic nature of wireless channel.Consider the case where a probe can miss a present contact with probability of K. 入Ln+1≥λIn+1FD(T). (6)1594 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 Fig. 1. Illustrating the contacts for a specific user probing at a constant in￾terval . that for a device A, a contact B is missed if B is not discovered by A’s probes. We will relax this later to compute the missing probability when neither A nor B’s probes discover each other. Let us first consider the simplest possible contact strategy, where each device probes for contacts at constant intervals of (see Fig. 1). We first consider the case when contact probes are reliable; i.e., every probe can successfully detect all contacts around the device. If , the contact will never be missed. Consider a contact that is initiated at time , where is an arbitrarily small value so that the time interval can be treated as a time point. This contact will not be detected by the mobile at time if , which happens with prob￾ability of . By Blackwell’s Theorem in renewal theory [15], when the contact process is a general renewal process with a nonlattice distribution function, we can calculate the long-term average missing probability given the probing interval of as (1) Note that we do not need to restrict the intercontact time distri￾bution to be memoryless to perform the averaging procedure in (1). Consider the mean value of given that , which is . Then, can be expressed as (2) For a constant contact-probing interval of , any contact with duration larger than will always be detected. Equation (2) shows that for a contact with duration shorter than , the expected probability that the contact will be missed is . Therefore, only contacts with duration smaller than will be missed. If all the contacts with have zero contact duration, then will be exactly . The key observation here is that for a constant probing scheme, if the contact durations are i.i.d. and the intercontact times are stationary, then the missing probability depends only on the distribution of the contact duration and the con￾tact-probing interval . It is independent of the intercontact time distribution. In real networks, contact probes are unreliable due to the nondeterministic nature of wireless channel. Consider the case where a probe can miss a present contact with probability of . The overall missing probability can be derived in a similar way (see the Appendix). Similar to the reliable probes case, the missing probability for unreliable probes is also independent of the intercontact time distribution. In the rest of this paper, we only consider cases where all contact probes are reliable. C. Optimal Contact-Probing Scheme We will now prove the following theorem about the constant contact-probing scheme described earlier. Theorem 1: Consider a contact process for which the con￾tact durations are i.i.d and the distribution of intercontact times is stationary, with an expected intercontact time of . Consider the class of contact-probing strategies that do not exploit knowl￾edge of the contact process. Then, among all contact-probing strategies with the same average contact-probing interval, the strategy that probes at constant intervals achieves the minimum missing probability. Proof: Consider a large interval of time . Let us con￾sider all strategies that probe the environment times in this interval. As shown previously, for the strategy that probes at constant intervals , the missing probability over dura￾tion is . Assume that an arbi￾trary scheme probes times at . Define and . Then, we have intervals of . Since the scheme se￾lects probe time without knowledge of the contact process, the expected number of missed contacts in an interval of is , for . All the contacts that occur in will be missed. The expected missing probability is (3) since the expected number of contacts arriving in duration is . For , we have (4) Similarly, when we have (5) We also have (6)