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©2009EEE1592 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