WANG etaL:OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1603 0.5 people have location preferences,which they visit periodically. STAR-LMMSE STARIMMS日 (true history) They then propose an empirical model to simulate user mobility STAR-MMSE 0.4 and validate it with WLAN data traces.The goal of this paper is modeling user mobility and contact patterns and not to derive contact-probing algorithms. 0.3 In [26],the authors again consider WLAN traces from the University of California,San Diego,and Dartmouth College, 0.2 Hanover,MA.They analyze the statistics of interpair contact time distribution,i.e.,the time between subsequent meetings ● of a specific pair of nodes.This metric is especially useful for 0.1 DTNs.They show that the interpair contact time distribution is self-similar.In our work,we consider traces of a different process,namely the set of contacts made as a user moves around. 0.0 A△ 0 100 200 300 400500 600 700 This contact process is significantly different from that obtained Probing Interval (seconds) from WLAN traces.In WLAN traces,contacts between users can be inferred only if two users associate with the same ac- Fig.13.STAR-LMMSE with true historical arrival rate cess point at the same time.Contacts between users at locations where there are no access points cannot be inferred.Also.we 0.4 characterize the intercontact time,i.e.,the time between the dis- covery of two new contacts.This metric is useful for both DTN and DTD applications. 0.3 Energy-efficient Bluetooth device discovery has been studied in [27]and [28].However,they focus on the Bluetooth protocol stack.Our algorithms are independent of the communication 902 protocol and adapt to user mobility to conserve energy for de- vice discovery,making them applicable to many communication systems. ◆—k=0.5 Stochastic-event capturing schemes are studied in wireless 0.1 一 k=0.7 ★ k=0.85 sensor networks [29].In [29],optimal visiting routes are de- -k=1.2 vised for mobile sensors to capture events that randomly happen ◆—k=1.5 in different points of interest.The event process is assumed to 0.0 1 100 200 300 400 500 be memoryless,and the parameters of the process are known Probing Interval (seconds) in advance.In our study,we investigate real-world contact pro- cesses that are more complicated than memoryless arrival and Fig.14.STAR-LMMSE with different k values. departure processes.The analysis in this paper can be applied to a general renewal process,and our algorithm can dynamically adapt to unknown parameters in the process. may not have the accurate value of k,which may also be time-varying.We use different k:values in the STAR-LMMSE VIII.REFLECTIONS to see whether it is sensitive to changes in the value of k. Fig.14 shows the performance of STAR-LMMSE running In this paper,we have identified that contact-probing mecha- with k changing from 0.5 to 1.5.Although our data has a k nisms play a critical role in certain mobile delay-tolerant appli- cations.In these applications,mobile devices periodically probe value of 0.846,changing the value of k used in the algorithm does not deteriorate the performance much.This shows that their environment for the presence of new contacts.We investi- the algorithm can work well with inaccurate or varying values gated the design of energy-conscious,adaptive contact-probing algorithms that trade off energy consumption and the probability of of missing a contact.Our key contributions were:1)a theoretical VII.RELATED WORK foundation that aids in the design of adaptive contact-probing User mobility has a profound impact on the performance of algorithms;2)real-world experiments and characterization of wireless networks.It has been shown that the capacity of wire- empirical contact patterns;and 3)design and validation of an less networks can be improved by random [4]or controlled [22] adaptive probing algorithm(called STAR)via trace-driven sim- mobility.The impact of user mobility in delay performance and ulations.We demonstrate that STAR-PTS is three times more forwarding algorithm design has also been widely studied in energy-efficient than a naive constant-probing algorithm.We DTNs that use Bluetooth or WLAN [5].[20].[23],[24].In this also show STAR-MMSE,an ideal MMSE estimator-based al- paper,we study how user mobility will effect energy efficiency gorithm,could further improve the energy efficiency by 50% in device discovery for delay-tolerant applications.Our protocol compared to STAR-PTS.We now reflect on what we have done. provides an energy-conscious device-discovery service,which can be used by many delay-tolerant applications. A.Exploiting Contact Bursts In [25],the authors observe that existing mobility models are Our empirical data show that the contact duration is Pareto- too simple and do not accurately reflect user mobility.Based distributed and the new contact arrivals are self-similar,meaning on WLAN traces from various universities,they observe that they are bursty.Not surprisingly,it is advantageous to exploitWANG et al.: OPPORTUNISTIC ENERGY-EFFICIENT CONTACT PROBING IN DELAY-TOLERANT APPLICATIONS 1603 Fig. 13. STAR-LMMSE with true historical arrival rate. Fig. 14. STAR-LMMSE with different values. may not have the accurate value of , which may also be time-varying. We use different values in the STAR-LMMSE to see whether it is sensitive to changes in the value of . Fig. 14 shows the performance of STAR-LMMSE running with changing from 0.5 to 1.5. Although our data has a value of 0.846, changing the value of used in the algorithm does not deteriorate the performance much. This shows that the algorithm can work well with inaccurate or varying values of . VII. RELATED WORK User mobility has a profound impact on the performance of wireless networks. It has been shown that the capacity of wire￾less networks can be improved by random [4] or controlled [22] mobility. The impact of user mobility in delay performance and forwarding algorithm design has also been widely studied in DTNs that use Bluetooth or WLAN [5], [20], [23], [24]. In this paper, we study how user mobility will effect energy efficiency in device discovery for delay-tolerant applications. Our protocol provides an energy-conscious device-discovery service, which can be used by many delay-tolerant applications. In [25], the authors observe that existing mobility models are too simple and do not accurately reflect user mobility. Based on WLAN traces from various universities, they observe that people have location preferences, which they visit periodically. They then propose an empirical model to simulate user mobility and validate it with WLAN data traces. The goal of this paper is modeling user mobility and contact patterns and not to derive contact-probing algorithms. In [26], the authors again consider WLAN traces from the University of California, San Diego, and Dartmouth College, Hanover, MA. They analyze the statistics of interpair contact time distribution, i.e., the time between subsequent meetings of a specific pair of nodes. This metric is especially useful for DTNs. They show that the interpair contact time distribution is self-similar. In our work, we consider traces of a different process, namely the set of contacts made as a user moves around. This contact process is significantly different from that obtained from WLAN traces. In WLAN traces, contacts between users can be inferred only if two users associate with the same ac￾cess point at the same time. Contacts between users at locations where there are no access points cannot be inferred. Also, we characterize the intercontact time, i.e., the time between the dis￾covery of two new contacts. This metric is useful for both DTN and DTD applications. Energy-efficient Bluetooth device discovery has been studied in [27] and [28]. However, they focus on the Bluetooth protocol stack. Our algorithms are independent of the communication protocol and adapt to user mobility to conserve energy for de￾vice discovery, making them applicable to many communication systems. Stochastic-event capturing schemes are studied in wireless sensor networks [29]. In [29], optimal visiting routes are de￾vised for mobile sensors to capture events that randomly happen in different points of interest. The event process is assumed to be memoryless, and the parameters of the process are known in advance. In our study, we investigate real-world contact pro￾cesses that are more complicated than memoryless arrival and departure processes. The analysis in this paper can be applied to a general renewal process, and our algorithm can dynamically adapt to unknown parameters in the process. VIII. REFLECTIONS In this paper, we have identified that contact-probing mecha￾nisms play a critical role in certain mobile delay-tolerant appli￾cations. In these applications, mobile devices periodically probe their environment for the presence of new contacts. We investi￾gated the design of energy-conscious, adaptive contact-probing algorithms that trade off energy consumption and the probability of missing a contact. Our key contributions were: 1) a theoretical foundation that aids in the design of adaptive contact-probing algorithms; 2) real-world experiments and characterization of empirical contact patterns; and 3) design and validation of an adaptive probing algorithm (called STAR) via trace-driven sim￾ulations. We demonstrate that STAR-PTS is three times more energy-efficient than a naive constant-probing algorithm. We also show STAR-MMSE, an ideal MMSE estimator-based al￾gorithm, could further improve the energy efficiency by 50% compared to STAR-PTS. We now reflect on what we have done. A. Exploiting Contact Bursts Our empirical data show that the contact duration is Pareto￾distributed and the new contact arrivals are self-similar, meaning they are bursty. Not surprisingly, it is advantageous to exploit