Evaluating opportunistic routing protocols with large realistic contact traces

ABSTRACT

Traditional mobile ad hoc network (MANET) routing protocols assume that contemporaneous end-to-end communication paths exist between data senders and receivers. In some mobile ad hoc networks with a sparse node population, an end-to-end communication path may break frequently or may not exist at anytime. Many routing protocols have been proposed in the literature to address the problem, but few were evaluated in a realistic "opportunistic" network setting. We use simulation and contact traces (derived from logs in a production network) to evaluate and compare five existing protocols: direct-delivery, epidemic, random, PRoPHET, and Link-State, as well as our own proposed routing protocol. We show that the direct delivery and epidemic routing protocols suffer either low delivery ratio or high resource usage, and other protocols make tradeoffs between delivery ratio and resource usage.

REFERENCES

• 1: John Burgess, Brian Gallagher, David Jensen, and Brian Neil Levine. MaxProp: routing for vehicle-based disruption-tolerant networks. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006.
• 2: Scott Burleigh, Adrian Hooke, Leigh Torgerson, Kevin Fall, Vint Cerf, Bob Durst, Keith Scott, and Howard Weiss. Delay-tolerant networking: An approach to interplanetary Internet. IEEE Communications Magazine, 41(6):128--136, June 2003.
• 3: Tracy Camp, Jeff Boleng, and Vanessa Davies. A survey of mobility models for ad hoc network research. Wireless Communication & Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.
• 4: Andrew T. Campbell , Shane B. Eisenman , Nicholas D. Lane , Emiliano Miluzzo , Ronald A. Peterson, People-centric urban sensing, Proceedings of the 2nd annual international workshop on Wireless internet, p.18-es, August 02-05, 2006, Boston, Massachusetts [doi>10.1145/1234161.1234179]
• 5: Augustin Chaintreau, Pan Hui, Jon Crowcroft, Christophe Diot, Richard Gass, and James Scott. Impact of human mobility on the design of opportunistic forwarding algorithms. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006.
• 6: Kevin Fall, A delay-tolerant network architecture for challenged internets, Proceedings of the 2003 conference on Applications, technologies, architectures, and protocols for computer communications, August 25-29, 2003, Karlsruhe, Germany [doi>10.1145/863955.863960]
• 7: 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]
• 8: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 9: 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]
• 10: Sushant Jain , Michael Demmer , Rabin Patra , Kevin Fall, Using redundancy to cope with failures in a delay tolerant network, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 11: 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
• 12: David Kotz , Kobby Essien, Analysis of a campus-wide wireless network, Wireless Networks, v.11 n.1-2, p.115-133, January 2005 [doi>10.1007/s11276-004-4750-0]
• 13: David Kotz, Tristan Henderson, and Ilya Abyzov. CRAWDAD data set dartmouth/campus. http://crawdad.cs.dartmouth.edu/dartmouth/campus, December 2004.
• 14: Jason LeBrun, Chen-Nee Chuah, Dipak Ghosal, and Michael Zhang. Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks. In IEEE Vehicular Technology Conference, pages 2289--2293, May 2005.
• 15: Jeremie Leguay, Timur Friedman, and Vania Conan. Evaluating mobility pattern space routing for DTNs. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006.
• 16: Anders Lindgren, Avri Doria, and Olov Schelen. Probabilistic routing in intermittently connected networks. In Workshop on Service Assurance with Partial and Intermittent Resources (SAPIR), pages 239--254, 2004.
• 17: Mirco Musolesi , Stephen Hailes , Cecilia Mascolo, Adaptive Routing for Intermittently Connected Mobile Ad Hoc Networks, Proceedings of the Sixth IEEE International Symposium on World of Wireless Mobile and Multimedia Networks, p.183-189, June 13-16, 2005 [doi>10.1109/WOWMOM.2005.17]
• 18: OLPC. One laptop per child project. http://laptop.org.
• 19: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, ACM SIGCOMM Computer Communication Review, v.24 n.4, p.234-244, Oct. 1994
• 20: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 21: Libo Song , David Kotz , Ravi Jain , Xiaoning He, Evaluating Next-Cell Predictors with Extensive Wi-Fi Mobility Data, IEEE Transactions on Mobile Computing, v.5 n.12, p.1633-1649, December 2006 [doi>10.1109/TMC.2006.185]
• 22: Jing Su, Ashvin Goel, and Eyal de Lara. An empirical evaluation of the student-net delay tolerant network. In International Conference on Mobile and Ubiquitous Systems (MobiQuitous), July 2006.
• 23: Amin Vahdat and David Becker. Epidemic routing for partially-connected ad hoc networks. Technical Report CS-2000-06, Duke University, July 2000.
• 24: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.229-236, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080140]
• 25: Yu Wang and Hongyi Wu. DFT-MSN: the delay fault tolerant mobile sensor network for pervasive information gathering. In Proceedings of the 25th IEEE International Conference on Computer Communications (INFOCOM), April 2006.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.4 Distributed Systems

General Terms:
Design, Performance

Keywords:
oppotunistic networks, routing, simulation