计算机科学与技术（参考文献）Opportunistic Energy-Efficient Contact Probing in Delay-Tolerant Applications

1592 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 Opportunistic Energy-Efficient Contact Probing in Delay-Tolerant Applications Wei Wang,Member;IEEE,Mehul Motani,Member;IEEE,and Vikram Srinivasan,Member;IEEE Abstract-In many delay-tolerant applications,information is governed by the mobility of information carriers and their un- is opportunistically exchanged between mobile devices that en- derlying contact patterns. counter each other.In order to affect such information exchange, The notion of delay tolerance is useful in a variety of sce- mobile devices must have knowledge of other devices in their vicinity.We consider scenarios in which there is no infrastructure narios.One compelling application is providing connectivity and devices must probe their environment to discover other and network services during disasters and in rural environments. devices.This can be an extremely energy-consuming process where network infrastructure is minimal or nonexistent.An- and highlights the need for energy-conscious contact-probing other example comes from software developers who are devel- mechanisms.If devices probe very infrequently,they might miss oping dating applications for mobile phones.The profile of an many of their contacts.On the other hand,frequent contact ideal partner is entered into a Bluetooth-based mobile phone, probing might be energy inefficient.In this paper,we investigate which alerts the user whenever a matching profile is detected in the tradeoff between the probability of missing a contact and the contact-probing frequency.First,via theoretical analysis,we char. the vicinity (e.g.,www.bedd.com). acterize the tradeoff between the probability of a missed contact Current research and development efforts for delay-tolerant and the contact-probing interval for stationary processes.Next, applications fall broadly into two categories:delay-tolerant for time-varying contact arrival rates,we provide an optimization networking (DTN)[2]and delay-tolerant databases (DTD). framework to compute the optimal contact-probing interval as a For DTN applications,the goal is to enable communication function of the arrival rate.We characterize real-world contact between specific source-destination pairs in the network. patterns via Bluetooth phone contact-logging experiments and show that the contact arrival process is self-similar.We design Research in this area has involved studying algorithmic issues STAR,a contact-probing algorithm that adapts to the contact such as routing in networks [3],fundamental issues such as arrival process.Instead of using constant probing intervals, scaling laws [4],and performance bounds of routing algorithms STAR dynamically chooses the probing interval using both the [5]based on real-world contact patterns. short-term contact history and the long-term history based on DTD applications have been driven by the observation that time of day information.Via trace-driven simulations on our mobile devices are becoming increasingly powerful in terms experimental data,we demonstrate that STAR requires three of computation and storage and have multiple radio interfaces to five times less energy for device discovery than a constant such as Bluetooth,3G,WiFi,etc.[6].An effort is also being contact-probing interval scheme. made by phone manufacturers to embed sensors in these phones Index Terms-Bluetooth,delay-tolerant networking (DTN),en- to acquire and store personal information (health-related)and ergy efficiency. for environmental monitoring [7].As a consequence,these de- vices store large volumes of digital information such as songs, photographs,and sensory data and constitute a distributed ge- I.INTRODUCTION ographic database.The dating application stated earlier is an INCE its inception.the goal of networking research has example of a DTD application.The research community has in- been to provide instant,anytime,anywhere access to in- vestigated opportunistic query propagation and data aggregation formation.However,in recent times,research interest has been algorithms,based on device proximity.in [6]and [8]-10]. piqued by a new class of applications that are tolerant to delay. For both DTN and DTD applications,the common funda- In several of these applications,information is exchanged op- mental primitive is the opportunistic exchange of information portunistically between devices when they are within communi- between mobile devices when they are in communication range cation range of each other.In other words,information transport of each other.In order to enable such exchanges,devices will have to constantly probe the environment to discover other de- vices in the vicinity.Not surprisingly,device discovery!is an Manuscript received November 25.2007:revised August 12.2008;approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor B.Levine.First pub- extremely energy-consuming process.To understand this better, lished June 30,2009:current version published October 14,2009.Part of this we made measurements on a Nokia 6600 mobile phone.The work was presented at ACM MobiCom 2007,Montreal,QC,Canada. current drawn was:1)38.61 mA for Bluetooth device discovery; W.Wang was with the National University of Singapore,Singapore 119620. Singapore.He is now with Microsoft Research Asia,Beijing 100190,China 2)9.33 mA for enabling the device to be discoverable;3)51.47 (e-mail:wei.wang@microsoft.com:wangwei.ww@gmail.com) mA for Bluetooth data transfer;and 4)38.68 mA for making a M.Motani is with the Department of Electrical and Computer Engineering, phone call.In other words,the device discovery process is as National University of Singapore,Singapore 119620.Singapore (e-mail: energy-intensive as making a phone call. motani@nus.edu.sg). V.Srinivasan is with Bell Labs Research,Bangalore 560095,India (e-mail: Our measurements clearly motivate the need for energy-con- vikramsr@alcatel-lucent.com). scious device-discovery algorithms.Although the measure- Color versions of one or more of the figures in this paper are available online ments in this paper are based on Bluetooth devices,our at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TNET.2008.2008990 We use device discovery and contact probing interchangeably in this paper. 1063-6692/S26.00©2009EEE

1592 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 Opportunistic Energy-Efficient Contact Probing in Delay-Tolerant Applications Wei Wang, Member, IEEE, Mehul Motani, Member, IEEE, and Vikram Srinivasan, Member, IEEE Abstract—In many delay-tolerant applications, information is opportunistically exchanged between mobile devices that en￾counter each other. In order to affect such information exchange, mobile devices must have knowledge of other devices in their vicinity. We consider scenarios in which there is no infrastructure and devices must probe their environment to discover other devices. This can be an extremely energy-consuming process and highlights the need for energy-conscious contact-probing mechanisms. If devices probe very infrequently, they might miss many of their contacts. On the other hand, frequent contact probing might be energy inefficient. In this paper, we investigate the tradeoff between the probability of missing a contact and the contact-probing frequency. First, via theoretical analysis, we char￾acterize the tradeoff between the probability of a missed contact and the contact-probing interval for stationary processes. Next, for time-varying contact arrival rates, we provide an optimization framework to compute the optimal contact-probing interval as a function of the arrival rate. We characterize real-world contact patterns via Bluetooth phone contact-logging experiments and show that the contact arrival process is self-similar. We design STAR, a contact-probing algorithm that adapts to the contact arrival process. Instead of using constant probing intervals, STAR dynamically chooses the probing interval using both the short-term contact history and the long-term history based on time of day information. Via trace-driven simulations on our experimental data, we demonstrate that STAR requires three to five times less energy for device discovery than a constant contact-probing interval scheme. Index Terms—Bluetooth, delay-tolerant networking (DTN), en￾ergy efficiency. I. INTRODUCTION SINCE its inception, the goal of networking research has been to provide instant, anytime, anywhere access to in￾formation. However, in recent times, research interest has been piqued by a new class of applications that are tolerant to delay. In several of these applications, information is exchanged op￾portunistically between devices when they are within communi￾cation range of each other. In other words, information transport Manuscript received November 25, 2007; revised August 12, 2008; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor B. Levine. First pub￾lished June 30, 2009; current version published October 14, 2009. Part of this work was presented at ACM MobiCom 2007, Montreal, QC, Canada. W. Wang was with the National University of Singapore, Singapore 119620, Singapore. He is now with Microsoft Research Asia, Beijing 100190, China (e-mail: wei.wang@microsoft.com; wangwei.ww@gmail.com). M. Motani is with the Department of Electrical and Computer Engineering, National University of Singapore, Singapore 119620, Singapore (e-mail: motani@nus.edu.sg). V. Srinivasan is with Bell Labs Research, Bangalore 560095, India (e-mail: vikramsr@alcatel-lucent.com). Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org. Digital Object Identifier 10.1109/TNET.2008.2008990 is governed by the mobility of information carriers and their un￾derlying contact patterns. The notion of delay tolerance is useful in a variety of sce￾narios. One compelling application is providing connectivity and network services during disasters and in rural environments, where network infrastructure is minimal or nonexistent. An￾other example comes from software developers who are devel￾oping dating applications for mobile phones. The profile of an ideal partner is entered into a Bluetooth-based mobile phone, which alerts the user whenever a matching profile is detected in the vicinity (e.g., www.bedd.com). Current research and development efforts for delay-tolerant applications fall broadly into two categories: delay-tolerant networking (DTN) [2] and delay-tolerant databases (DTD). For DTN applications, the goal is to enable communication between specific source–destination pairs in the network. Research in this area has involved studying algorithmic issues such as routing in networks [3], fundamental issues such as scaling laws [4], and performance bounds of routing algorithms [5] based on real-world contact patterns. DTD applications have been driven by the observation that mobile devices are becoming increasingly powerful in terms of computation and storage and have multiple radio interfaces such as Bluetooth, 3G, WiFi, etc. [6]. An effort is also being made by phone manufacturers to embed sensors in these phones to acquire and store personal information (health-related) and for environmental monitoring [7]. As a consequence, these de￾vices store large volumes of digital information such as songs, photographs, and sensory data and constitute a distributed ge￾ographic database. The dating application stated earlier is an example of a DTD application. The research community has in￾vestigated opportunistic query propagation and data aggregation algorithms, based on device proximity, in [6] and [8]–[10]. For both DTN and DTD applications, the common funda￾mental primitive is the opportunistic exchange of information between mobile devices when they are in communication range of each other. In order to enable such exchanges, devices will have to constantly probe the environment to discover other de￾vices in the vicinity. Not surprisingly, device discovery1 is an extremely energy-consuming process. To understand this better, we made measurements on a Nokia 6600 mobile phone. The current drawn was: 1) 38.61 mA for Bluetooth device discovery; 2) 9.33 mA for enabling the device to be discoverable; 3) 51.47 mA for Bluetooth data transfer; and 4) 38.68 mA for making a phone call. In other words, the device discovery process is as energy-intensive as making a phone call. Our measurements clearly motivate the need for energy-con￾scious device-discovery algorithms. Although the measure￾ments in this paper are based on Bluetooth devices, our 1We use device discovery and contact probing interchangeably in this paper. 1063-6692/$26.00 © 2009 IEEE

WANG etaL:OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1593 device-discovery model can be used in other protocols.such C.Algorithm Design and Validation as 802.11 or UWB.As there are no centralized coordinators in DTNs,it is hard to synchronize devices in the network,and Finally,using insights gleaned from the theory and the data devices normally do not have information on which channel analysis,we investigate adaptive contact-probing algorithms. should be used in device discovery.In device-discovery proto- We design STAR,an algorithm that strives to estimate the ar- cols used in DTN,a mobile may need to send multiple packets rival rate and adapt the contact-probing interval based on this over a number of channels in order to scan for devices around estimate.We consider using several estimation methods in con- it.Therefore,the high probing energy consumption could be a junction with STAR and compare them using trace-driven simu- common problem in delay-tolerant networks. lations.We show that a simple weighted average of previous ar- One strategy to conserve energy is to increase the time be- rival rate estimates (STAR-PTS)works well and has 1/3 the en- tween subsequent device discoveries.The consequence of this ergy consumption of the constant nonadaptive contact-probing is that devices in the vicinity may go undiscovered,and opportu- algorithm for a missing probability of 0.2.The minimum mean nities to exchange data are lost.This points to a tradeoff between squared error estimator approach(STAR-MMSE)is even better energy and missed opportunities.For strategies that use a con- and has 1/5 the energy consumption of the nonadaptive scheme. stant device-discovery interval,the larger the probing interval, See Sections V and VI. the larger the missed opportunities and vice-versa.However,in stochastic environments,device discovery should be done adap- II.MODELING THE CONTACT PROCESS tively by choosing the probing interval based on the state of the environment.For example,late at night at home,device dis- covery can occur at large intervals without missing many con- A.System Model and Assumptions tacts,while on the subway to work,device discovery should be Assume that every device probes the environment governed done more frequently to catch the myriad of new contacts. In this paper,we investigate the design of energy-conscious, by some contact-probing algorithm.When a device A probes its environment,all devices that hear the probe respond to device adaptive contact-probing algorithms that trade off energy con- A with some information (e.g.,identity,services available,etc.). sumption and the probability of missing a contact.Specifically, Based on this information,A may choose to exchange data with we make the following contributions. some of its neighbors.We define two device,s A and B,to be in contact if they are within communication range of each other2. A.Theoretical framework The duration over which devices A and B are continuously in contact is called the contact duration for that contact.If neither We first develop a theoretical framework to characterize the device probes its environment during the contact duration,then tradeoff between the average contact-probing interval 7 and the we have a missed contact.We further assume,for the sake of contact missing probability Piss.We show that if the contact analysis,that each probe is an impulse and does not consume duration distribution is independent and identically distributed any time. (i.i.d.)and the contact arrival rate is constant,then for a given We assume that each probe consumes the same amount of missing probability constraint,the optimal contact-probing in- energy of ep.When the average contact-probing interval is T, terval is 1)constant and 2)depends only on contact duration dis-the energy consumption rate of the device will bep/T.With the tribution,independent of the contact arrival distribution.When same number of missed contacts,the algorithm that uses fewer the contact arrival rate is time varying,the optimal contact- probes (longer average probing interval)will be more energy probing interval is a function of the contact arrival rate.We pro- efficient. vide an optimization framework to compute the optimal con- For a given device,we assume that the contact durations tact-probing interval as a function of the contact arrival rate. tp()are i.i.d.random variables with cumulative distribution This theoretical base provides us with bounds on performance function (cdf)of Fp(t)and mean Eftp}=1/u. and also aids in the investigation and design of adaptive con- We assume that the contact arrival process is stationary.The tact-probing algorithms.See Sections II and III. contact arrival process is characterized by the intercontact time tc(i),defined as the time between the ith and (+1)-th contacts. B.Real-World Contact Pattern Experiments and Analysis The stationary assumption is that the sequence of intercontact times is a wide-sense stationary process;i.e.,the tc()have The theoretical development above depends on the contact a constant mean of Eftc}=1/A.We relax this assumption pattern statistics.To understand real-world contact patterns,we and deal with nonstationary contact arrival processes in the next conducted a large-scale data logging experiment [11].Nine vol- section. unteers were given Bluetooth devices equipped with a software See Fig.I for an illustration of contact duration tp(i)and program that probed for contacts every 30s and logged informa- intercontact time tc(). tion about other Bluetooth devices that came within range.Our database contains the largest number of unique devices discov- B.Missing Probability ered,compared to existing work [12]-[14].We conducted rig- orous analysis on the data.We confirmed that the contact dura- The missing probability Pmiss is the probability a contact that tion is Pareto-distributed.Moreover,our data analysis indicates occurs is not detected.For the following analysis,we assume weak correlations in contact patterns at 24-h time lags.Finally, we show that the contact process is self-similar with a Hurst pa- 2We do not assume a perfect communication region here.The imperfectness in communication is embedded in our contact data gathering process that uses rameter of 0.76.See Section IV. real devices

WANG et al.: OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1593 device-discovery model can be used in other protocols, such as 802.11 or UWB. As there are no centralized coordinators in DTNs, it is hard to synchronize devices in the network, and devices normally do not have information on which channel should be used in device discovery. In device-discovery proto￾cols used in DTN, a mobile may need to send multiple packets over a number of channels in order to scan for devices around it. Therefore, the high probing energy consumption could be a common problem in delay-tolerant networks. One strategy to conserve energy is to increase the time be￾tween subsequent device discoveries. The consequence of this is that devices in the vicinity may go undiscovered, and opportu￾nities to exchange data are lost. This points to a tradeoff between energy and missed opportunities. For strategies that use a con￾stant device-discovery interval, the larger the probing interval, the larger the missed opportunities and vice-versa. However, in stochastic environments, device discovery should be done adap￾tively by choosing the probing interval based on the state of the environment. For example, late at night at home, device dis￾covery can occur at large intervals without missing many con￾tacts, while on the subway to work, device discovery should be done more frequently to catch the myriad of new contacts. In this paper, we investigate the design of energy-conscious, adaptive contact-probing algorithms that trade off energy con￾sumption and the probability of missing a contact. Specifically, we make the following contributions. A. Theoretical Framework We first develop a theoretical framework to characterize the tradeoff between the average contact-probing interval and the contact missing probability . We show that if the contact duration distribution is independent and identically distributed (i.i.d.) and the contact arrival rate is constant, then for a given missing probability constraint, the optimal contact-probing in￾terval is 1) constant and 2) depends only on contact duration dis￾tribution, independent of the contact arrival distribution. When the contact arrival rate is time varying, the optimal contact￾probing interval is a function of the contact arrival rate. We pro￾vide an optimization framework to compute the optimal con￾tact-probing interval as a function of the contact arrival rate. This theoretical base provides us with bounds on performance and also aids in the investigation and design of adaptive con￾tact-probing algorithms. See Sections II and III. B. Real-World Contact Pattern Experiments and Analysis The theoretical development above depends on the contact pattern statistics. To understand real-world contact patterns, we conducted a large-scale data logging experiment [11]. Nine vol￾unteers were given Bluetooth devices equipped with a software program that probed for contacts every 30 s and logged informa￾tion about other Bluetooth devices that came within range. Our database contains the largest number of unique devices discov￾ered, compared to existing work [12]–[14]. We conducted rig￾orous analysis on the data. We confirmed that the contact dura￾tion is Pareto-distributed. Moreover, our data analysis indicates weak correlations in contact patterns at 24-h time lags. Finally, we show that the contact process is self-similar with a Hurst pa￾rameter of 0.76. See Section IV. C. Algorithm Design and Validation Finally, using insights gleaned from the theory and the data analysis, we investigate adaptive contact-probing algorithms. We design STAR, an algorithm that strives to estimate the ar￾rival rate and adapt the contact-probing interval based on this estimate. We consider using several estimation methods in con￾junction with STAR and compare them using trace-driven simu￾lations. We show that a simple weighted average of previous ar￾rival rate estimates (STAR-PTS) works well and has 1/3 the en￾ergy consumption of the constant nonadaptive contact-probing algorithm for a missing probability of 0.2. The minimum mean squared error estimator approach (STAR-MMSE) is even better and has 1/5 the energy consumption of the nonadaptive scheme. See Sections V and VI. II. MODELING THE CONTACT PROCESS A. System Model and Assumptions Assume that every device probes the environment governed by some contact-probing algorithm. When a device A probes its environment, all devices that hear the probe respond to device A with some information (e.g., identity, services available, etc.). Based on this information, A may choose to exchange data with some of its neighbors. We define two device,s A and B, to be in contact if they are within communication range of each other2. The duration over which devices A and B are continuously in contact is called the contact duration for that contact. If neither device probes its environment during the contact duration, then we have a missed contact. We further assume, for the sake of analysis, that each probe is an impulse and does not consume any time. We assume that each probe consumes the same amount of energy of . When the average contact-probing interval is , the energy consumption rate of the device will be . With the same number of missed contacts, the algorithm that uses fewer probes (longer average probing interval) will be more energy efficient. For a given device, we assume that the contact durations are i.i.d. random variables with cumulative distribution function (cdf) of and mean . We assume that the contact arrival process is stationary. The contact arrival process is characterized by the intercontact time , defined as the time between the th and -th contacts. The stationary assumption is that the sequence of intercontact times is a wide-sense stationary process; i.e., the have a constant mean of . We relax this assumption and deal with nonstationary contact arrival processes in the next section. See Fig. 1 for an illustration of contact duration and intercontact time . B. Missing Probability The missing probability is the probability a contact that occurs is not detected. For the following analysis, we assume 2We do not assume a perfect communication region here. The imperfectness in communication is embedded in our contact data gathering process that uses real devices

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)

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)

1596 IEEE/ACM TRANSACTIONS ON NETWORKING.VOL.17.NO.5.OCTOBER 2009 For example,when the contact duration is uniformly dis-It can be verified that U(ti)is always a concave and increasing tributed as shown n(9,we have户nmis(T）='=景rmis(T), function for the three distributions we discussed above.Using which is smaller than the single user missing probability only by the Karush-Kuhn-Tucker (KKT)conditions [16],we have a constant factor. U()=c (16) III.NONSTATIONARY INTERCONTACT TIMES Until now,we have made the simplifying assumption that the for all nonzero optimal solutions 4.Note that =0 when intercontact times are stationary.This assumption is clearly not c.The energy cost cis a constant that can be obtained true.For example,one would expect the intercontact time pat- by solving the dual of(15).The optimal T*can then be solved terns late at night to differ significantly from the intercontact from time distribution during lunch hours or peak traffic hours.This implies that the optimal contact-probing interval will vary with )=关 (17) time.In the following sections,we study the contact arrival pro- cesses where the average contact arrival rate varies with time.In for a given Ai.In practice,we can set the parameter c instead this case,we assume that the contact arrival rate is constant over of N to achieve a certain tradeoff point between energy and some short time period of duration L.As before,we assume the missing probability.A larger value of c means energy is more contact durations are i.i.d..This assumption will be justified in precious(smaller N)and less energy will be used in the M time Section VI. slots.Consequently,the overall contact-missing probability will be larger.Once the parameter c is set,we can use(17)to calcu- A.Problem Formulation late the optimal T*based on the estimate of Ai for a time slot i. This solution minimizes the missing probability over all time, We divide the time to slots with equal duration of L.We de- subject to energy constraints,which are determined by the en- note the average contact arrival rate in the ith time slot as Ai. ergy cost c. We proved in Theorem 1 that using a constant con- Example /Let the contact duration distribution be uniform. tact-probing interval of T is optimal during the ith time L=1 h,and N is the number of times the device can probe slot.In this case,the expected number of contacts captured in 24 h.Then,the optimal contact-probing interval T*for the during time period i will be Ai(1-Pniss(T).However,to arrival rate.入zis minimize the overall contact-missing probability,the optimal probing intervals Ti could be different for different time slots AC that have a different arrival rate of Ai.Intuitively,more energy (18) u入 should be spent in time slots with high arrival rates to capture more contacts so that the overall contact missing probability by(I7).If the:are all equal,.then clearlyT=装，∀i.There- can be minimized. Consider the problem of maximizing the number of contacts ore,c=学（装）2 and Pi(T)=裴when T≤a captured over M time slots,given a constraint on the total en- ergy used in the M time slots.This problem is equivalent to min- B.Discussion imizing the contact-missing probability over the M time slots. In Section II,we show that a constant probing rate is optimal As each probe consumes equal energy,the constraint on total for stationary processes,and the optimal tradeoff points can energy consumption can be converted to a constraint of total be derived from (1).In this section,we show that the average number of probes used in the M time slots.Assume that the de- vice can take N probes during the M time slots.We can then missing probability can be further reduced when the contact arrival rate is time-varying.When the contact arrival ratesAi formulate the following optimization problem to find the op- are different in different time slots,we can use adaptive contact timal probing interval T for each time slot: probing to redistribute the limited probing energy according to the contact arrival rate.For a time slot with high contact Maximize 入(1-Pmis(T) arrival rate,we can increase the probing rate and reduce the missing probability so that most contacts arriving in this time i=1 M slot can be captured.When the contact arrival rate is low,the ≤N T≥0 i. (14) contact-probing rate can be reduced since the number of missed s.t i=1 contacts入：LPmiss(T)will be small for a small入i,even if Pisquite high.In this way.the overall missing probability Defining variable ti as 1/Ti and Ui(i)=Ai(1-Pmiss(1/i)), (can be minimized.However,the missing the optimization in(14)can be recast as M AL probability for time slots with low arrival rates could be very M high in this case. Maximize Ui(xi) We now make two observations regarding the the optimiza- =1 tion in (14).First,when the contact arrival rates are equal for all M time slots,it is not necessary to use different probing intervals S.t Lx≤N x≥0 Vi. (15) in different time slots,and a constant probing rate is optimal. In this scenario.the solution to (14)reduces to the solution for

1596 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 17, NO. 5, OCTOBER 2009 For example, when the contact duration is uniformly dis￾tributed as shown in (9), we have , which is smaller than the single user missing probability only by a constant factor. III. NONSTATIONARY INTERCONTACT TIMES Until now, we have made the simplifying assumption that the intercontact times are stationary. This assumption is clearly not true. For example, one would expect the intercontact time pat￾terns late at night to differ significantly from the intercontact time distribution during lunch hours or peak traffic hours. This implies that the optimal contact-probing interval will vary with time. In the following sections, we study the contact arrival pro￾cesses where the average contact arrival rate varies with time. In this case, we assume that the contact arrival rate is constant over some short time period of duration . As before, we assume the contact durations are i.i.d.. This assumption will be justified in Section VI. A. Problem Formulation We divide the time to slots with equal duration of . We de￾note the average contact arrival rate in the th time slot as . We proved in Theorem 1 that using a constant con￾tact-probing interval of is optimal during the th time slot. In this case, the expected number of contacts captured during time period will be . However, to minimize the overall contact-missing probability, the optimal probing intervals could be different for different time slots that have a different arrival rate of . Intuitively, more energy should be spent in time slots with high arrival rates to capture more contacts so that the overall contact missing probability can be minimized. Consider the problem of maximizing the number of contacts captured over time slots, given a constraint on the total en￾ergy used in the time slots. This problem is equivalent to min￾imizing the contact-missing probability over the time slots. As each probe consumes equal energy, the constraint on total energy consumption can be converted to a constraint of total number of probes used in the time slots. Assume that the de￾vice can take probes during the time slots. We can then formulate the following optimization problem to find the op￾timal probing interval for each time slot: (14) Defining variable as and , the optimization in (14) can be recast as (15) It can be verified that is always a concave and increasing function for the three distributions we discussed above. Using the Karush–Kuhn–Tucker (KKT) conditions [16], we have (16) for all nonzero optimal solutions . Note that when . The energy cost is a constant that can be obtained by solving the dual of (15). The optimal can then be solved from (17) for a given . In practice, we can set the parameter instead of to achieve a certain tradeoff point between energy and missing probability. A larger value of means energy is more precious (smaller ) and less energy will be used in the time slots. Consequently, the overall contact-missing probability will be larger. Once the parameter is set, we can use (17) to calcu￾late the optimal based on the estimate of for a time slot . This solution minimizes the missing probability over all time, subject to energy constraints, which are determined by the en￾ergy cost . Example 1: Let the contact duration distribution be uniform, h, and is the number of times the device can probe in 24 h. Then, the optimal contact-probing interval for the arrival rate is (18) by (17). If the are all equal, then clearly . There￾fore, and when . B. Discussion In Section II, we show that a constant probing rate is optimal for stationary processes, and the optimal tradeoff points can be derived from (1). In this section, we show that the average missing probability can be further reduced when the contact arrival rate is time-varying. When the contact arrival rates are different in different time slots, we can use adaptive contact probing to redistribute the limited probing energy according to the contact arrival rate. For a time slot with high contact arrival rate, we can increase the probing rate and reduce the missing probability so that most contacts arriving in this time slot can be captured. When the contact arrival rate is low, the contact-probing rate can be reduced since the number of missed contacts will be small for a small , even if is quite high. In this way, the overall missing probability can be minimized. However, the missing probability for time slots with low arrival rates could be very high in this case. We now make two observations regarding the the optimiza￾tion in (14). First, when the contact arrival rates are equal for all time slots, it is not necessary to use different probing intervals in different time slots, and a constant probing rate is optimal. In this scenario, the solution to (14) reduces to the solution for