WANG etaL:OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1595 Putting all these into (3),we have 0.40 量一Exponential 0.35 -Uniform (瓜 ●-Pareto(k=2) FD()dx+(Ii-T)FD(T 0.30 0.25 +λIn+1FD(T) 80.20 0.15 F(c)+fD(T)(∑I-nT) i= 0.10 =Pmiss(T). (7) 0.05 0.00 681012141618202 D.Tradeoffs in Energy Efficiency and Pmiss Energy Consumption 1/(uT)) Having established that a constant contact-probing interval is Fig.2.Tradeoff between energy consumption and missing probability on dif- optimal under certain assumptions,we now explore the tradeoff ferent distributions. between energy efficiency and the missing probability.When contact durations are distributed according to a given distribu- tion,we can analytically determine the relationship between T interval should be around 7 to achieve a near-zero missing and Pniss(T)according to (1).Here,we demonstrate the rela- probability.In other words,for a constant arrival rate and a tionship between energy efficiency and missing probability for Pareto contact duration distribution,it is difficult to tradeoff several typical distributions.In Section IV,we will focus on dis- between Pmiss and T. tributions obtained from real-world Bluetooth contact logs. 1)Exponential Distribution:When the contact duration is E.Double Detection exponentially distributed,we have Fp()=1-e-u.Using As we stated earlier,a contact between device A and B is (1),we have missed only if neither device probes the environment during the mis(T）=I-1+e-r contact.Consider the case when two users A and B are inde- T (8)pendently probing the environment.Assume that both users are using the same constant contact-probing interval of T.Then, 2)Uniform Distribution:The uniform distribution is the probability that A does not discover B is Pniss(T).How- ever,the probability that neither A nor B discovers the other E<0 FD( 0≤x≤2u. (9) during a contact is much higher than PT),even though their contact-probing processes are independent.Suppose one x>2/4 user probes at times of T,2T,...,nT,and the other probes at Additionally,we have ,y+T,...,+(n-1)T.Without loss of generality,we can assume that y<T/2.Then,the probability that during a con- T<2 tact,neither user discovers the other is given by Pniss(T) T-1 T≥a (10) T-V mis(T,）= FD(c)dx+ FD(x)dx 3)Pareto Distribution:We have 0 T<T FD)=1-(er)*,x之r (11)When y T2.Piniss(T,y)has a minimum value of Pniss(T/2),and Pmiss(T,y)has maximum value of Pniss(T) In this case,we have 1/u.=kT/(:-1)when k>1.The mean when y=0.Since the two users are probing independently, is unbounded when<1.Using (1),we have y is uniformly distributed in [0,T/2],and the average missing probability is T Tk 乃msT)）=1+T1-府T(1-丙' T>T (12) 户niss(T) Fig.2 shows the tradeoff between energy consumption Fp(x)dx+ and missing probability for these distributions.The energy consumption is computed as where we set ep1 and normalize the energy consumption rate by the average contact Fp(x)drdy duration of u.We see that for exponential and uniform distribu- tions,the missing probability of 5%-10%is near the knee of the 2 curve that is a good tradeoff point between energy consump- Fp(x)dxdy+ Fp(x)dxdy tion and missing probability.This means the contact-probing [G interval should be around 1/6 to 1/3 of the average contact 2 duration.However,for Pareto distribution,the contact-probing Fp(c)dxdy. (13)WANG et al.: OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1595 Putting all these into (3), we have (7) D. Tradeoffs in Energy Efficiency and Having established that a constant contact-probing interval is optimal under certain assumptions, we now explore the tradeoff between energy efficiency and the missing probability. When contact durations are distributed according to a given distribu￾tion, we can analytically determine the relationship between and according to (1). Here, we demonstrate the rela￾tionship between energy efficiency and missing probability for several typical distributions. In Section IV, we will focus on dis￾tributions obtained from real-world Bluetooth contact logs. 1) Exponential Distribution: When the contact duration is exponentially distributed, we have . Using (1), we have (8) 2) Uniform Distribution: The uniform distribution is (9) Additionally, we have (10) 3) Pareto Distribution: We have (11) In this case, we have when . The mean is unbounded when . Using (1), we have (12) Fig. 2 shows the tradeoff between energy consumption and missing probability for these distributions. The energy consumption is computed as , where we set and normalize the energy consumption rate by the average contact duration of . We see that for exponential and uniform distribu￾tions, the missing probability of 5%–10% is near the knee of the curve that is a good tradeoff point between energy consump￾tion and missing probability. This means the contact-probing interval should be around 1/6 to 1/3 of the average contact duration. However, for Pareto distribution, the contact-probing Fig. 2. Tradeoff between energy consumption and missing probability on dif￾ferent distributions. interval should be around to achieve a near-zero missing probability. In other words, for a constant arrival rate and a Pareto contact duration distribution, it is difficult to tradeoff between and . E. Double Detection As we stated earlier, a contact between device A and B is missed only if neither device probes the environment during the contact. Consider the case when two users A and B are inde￾pendently probing the environment. Assume that both users are using the same constant contact-probing interval of . Then, the probability that A does not discover B is . How￾ever, the probability that neither A nor B discovers the other during a contact is much higher than , even though their contact-probing processes are independent. Suppose one user probes at times of , and the other probes at . Without loss of generality, we can assume that . Then, the probability that during a con￾tact, neither user discovers the other is given by When , has a minimum value of , and has maximum value of when . Since the two users are probing independently, is uniformly distributed in , and the average missing probability is (13)