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