Study of a bus-based disruption-tolerant network: mobility modeling and impact on routing

ABSTRACT

We study traces taken from UMass DieselNet, a Disruption-Tolerant Network consisting of WiFi nodes attached to buses. As buses travel their routes, they encounter other buses and in some cases are able to establish pair-wise connections and transfer data between them. We analyze the bus-to-bus contact traces to characterize the contact process between buses and its impact on DTN routing performance. We find that the all-bus-pairs aggregated inter-contact times show no discernible pattern. However, the inter-contact times aggregated at a route level exhibit periodic behavior.Based on analysis of the deterministic inter-meeting times for bus pairs running on route pairs, and consideration of the variability in bus movement and the random failures to establish connections, we construct generative route-level models that capture the above behavior. Through trace-driven simulations of epidemic routing, we find that the epidemic performance predicted by traces generated with this finer-grained route-level model is much closer to the actual performance that would be realized in the operational system than traces generated using the coarse-grained all-bus-pairs aggregated model. This suggests the importance in choosing the rightlevel of model granularity when modelingmobility-related measures such as inter-contact times in DTNs.

REFERENCES

• 1: UCSD Wireless Topology Discovery Project. http://sysnet.ucsd.edu/wtd/.
• 2: F. Bai, N. Sadagopan, B. Krishnamachari, and A. Helmy. Modeling Path Duration Distributions in MANETs and their Impact on Routing Performance. In IEEE Journal on Selected Areas of Communications, September 2004.
• 3: Aruna Balasubramanian , Brian Levine , Arun Venkataramani, DTN routing as a resource allocation problem, Proceedings of the 2007 conference on Applications, technologies, architectures, and protocols for computer communications, August 27-31, 2007, Kyoto, Japan
• 4: J. Bilmes. A Gentle Tutorial on the EM Algorithm and its Application to Parameter Estimation for Gaussian Mixture and Hidden Markov Models. Technical Report ICSI-TR-97-021, University of Berkeley, 1997.
• 5: J. Burgess, B. Gallagher, D. Jensen, and B. N. Levine. MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networks. In Proc. IEEE INFOCOM, 2006.
• 6: A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, R. Gass, and J. Scott. Impact of Human Mobility on the Design of Opportunitic Forwarding Algorithms. In Proc. IEEE INFOCOM, 2006.
• 7: L.-J. Chen, Y.-C. Chen, T. Sun, P. Sreedevi, K.-T. Chen, C.-H. Yu, and H. hua Chu. Finding Self-Similarities in Opportunistic People Networks. In Proc. IEEE INFOCOM Mini-Symposium, 2007.
• 8: M. Dunbabin, P. Corke, I. Vailescu, and D. Rus. Data Muling over Underwater Wireless Sensor Networks using an Autonomous Underwater vehicle. In Proc. Intl Conf on Robotics and Automation (ICRA). IEEE, May 2006.
• 9: Robin Groenevelt , Philippe Nain , Ger Koole, The message delay in mobile ad hoc networks, Performance Evaluation, v.62 n.1-4, p.210-228, October 2005 [doi>10.1016/j.peva.2005.07.018]
• 10: Tristan Henderson , David Kotz , Ilya Abyzov, The changing usage of a mature campus-wide wireless network, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023739]
• 11: W.-J. Hsu and A. Helmy. Encounter-based Message Broadcasting in Ad Hoc Networks with Intermittent Connectivity. In MobiHoc (poster), 2005.
• 12: W.-J. Hsu and A. Helmy. IMPACT: Investigation of Mobile-User Patterns Across University Campuses using WLAN Trace Analysis. Technical report, University of South California, 2005.
• 13: Ravi Jain , Dan Lelescu , Mahadevan Balakrishnan, Model T: an empirical model for user registration patterns in a campus wireless LAN, Proceedings of the 11th annual international conference on Mobile computing and networking, August 28-September 02, 2005, Cologne, Germany [doi>10.1145/1080829.1080848]
• 14: J. Jetcheva, Y.-C. Hu, S. PalChaudhuri, A. K. Saha, and D. B. Johnson. Design and Evaluation of a Metropolitan Area Multitier Wireless Ad Hoc Network Architecture. In Proc. Workshop on Mobile Computing Systems and Applications, 2003.
• 15: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 16: E. Kaplan and P. Meier. Nonparametric Estimation from Incomplete Observations. In Journal of the American Statistical Association, volume 53, June 1958.
• 17: M. Kim, D. Kotz, and S. Kim. Extracting a Mobility Model from Real User Traces. In Proc. IEEE INFOCOM, 2006.
• 18: Leonard Kleinrock, Theory, Volume 1, Queueing Systems, Wiley-Interscience, 1975
• 19: Amit Kumar Saha , David B. Johnson, Modeling mobility for vehicular ad-hoc networks, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023892]
• 20: A. Seth , D. Kroeker , M. Zaharia , S. Guo , S. Keshav, Low-cost communication for rural internet kiosks using mechanical backhaul, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161127]
• 21: Jing Su , Alvin Chin , Anna Popivanova , Ashvin Goel , Eyal de Lara, User Mobility for Opportunistic Ad-Hoc Networking, Proceedings of the Sixth IEEE Workshop on Mobile Computing Systems and Applications, p.41-50, December 02-03, 2004 [doi>10.1109/MCSA.2004.29]
• 22: J. Su, A. Goel, and E. d. Lara. An Empirical Evaluation of the Student-Net Delay Tolerant Network. In Proc. of the International Conference on Mobile and Ubiquitous Systems: Networks and Services (MOBIQUITOUS), 2006.
• 23: C. Tuduce and T. Gross. A Mobility Model Based on WLAN Traces and its Validation. In Proc. IEEE INFOCOM, 2005.
• 24: A. Vahdat and D. Becker. Epidemic Routing for Partially Connected Ad Hoc Networks. Technical Report CS-200006, Duke University, April 2000.
• 25: X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance Modeling of Epidemic Routing. Proc. IFIP Networking, 2006.
• 26: Xiaolan Zhang , Giovanni Neglia , Jim Kurose , Don Towsley, Performance modeling of epidemic routing, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.10, p.2867-2891, July, 2007 [doi>10.1016/j.comnet.2006.11.028]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Store and forward networks

General Terms:
Experimentation, Measurement, Performance, Verification

Keywords:
DTN, epidemic routing, mobility trace modeling