Contention-aware analysis of routing schemes for mobile opportunistic networks

ABSTRACT

A large body of work has theoretically analyzed the performance of routing schemes for mobile opportunistic networks. But a vast majority of these prior studies have ignored wireless contention. Recent papers have shown through simulations that ignoring contention leads to inaccurate and misleading results, even when studying sparse networks. In this paper, we analyze the performance of routing schemes under contention. To model contention we use our recently-proposed analytical framework which is applicable to any multi-hop wireless network. Then, we take into consideration the special characteristics of mobile opportunistic networks and compute the delays for four representative routing schemes for these networks. Finally, we use these delay expressions to answer practical questions in the context of designing more efficient routing schemes for mobile opportunistic networks.

REFERENCES

• 1: Disruption tolerant networking. http://www.darpa.mil/ato/solicit/DTN/
• 2: Daniel Aguayo , John Bicket , Sanjit Biswas , Glenn Judd , Robert Morris, Link-level measurements from an 802.11b mesh network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 3: S. Burleigh, A. Hooke, L. Torgerson, K. Fall, V. Cerf, B. Durst, and K. Scott. Delay-tolerant networking:an approach to interplanetary internet. IEEE Communications Magazine 41, 2003.
• 4: A. Doria, M. Udn, and D. P. Pandey. Providing connectivity to the Saami nomadic community. In Proc. 2nd Int. Conf. on Open Collaborative Design for Sustainable Innovation Dec. 2002.
• 5: 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]
• 6: Sushant Jain , Kevin Fall , Rabin Patra, Routing in a delay tolerant network, Proceedings of the 2004 conference on Applications, technologies, architectures, and protocols for computer communications, August 30-September 03, 2004, Portland, Oregon, USA
• 7: A. Jindal and K. Psounis. Optimizing multi-copy routing schemes for resource constrained intermittently connected mobile networks. In Proceedings of IEEE Asilomar Conference on Signals, Systems and Computers 2006.
• 8: Apoorva Jindal , Konstantinos Psounis, Performance analysis of epidemic routing under contention, Proceedings of the 2006 international conference on Wireless communications and mobile computing, July 03-06, 2006, Vancouver, British Columbia, Canada [doi>10.1145/1143549.1143657]
• 9: Apoorva Jindal , Konstantinos Psounis, Fundamental Mobility Properties for Realistic Performance Analysis of Intermittently Connected Mobile Networks, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.59-64, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.52]
• 10: A. Jindal and K. Psounis. Wireless contention in mobile multi-hop networks. Technical Report CENG-2007-4, USC, 2007.
• 11: Evan P. C. Jones , Lily Li , Paul A. S. Ward, Practical routing in delay-tolerant networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.237-243, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080141]
• 12: 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
• 13: Anders Lindgren , Avri Doria , Olov Schelén, Probabilistic routing in intermittently connected networks, ACM SIGMOBILE Mobile Computing and Communications Review, v.7 n.3, July 2003 [doi>10.1145/961268.961272]
• 14: Giovanni Neglia , Xiaolan Zhang, Optimal delay-power tradeoff in sparse delay tolerant networks: a preliminary study, Proceedings of the 2006 SIGCOMM workshop on Challenged networks, p.237-244, September 11-15, 2006, Pisa, Italy [doi>10.1145/1162654.1162661]
• 15: Richard Draves , Jitendra Padhye , Brian Zill, Routing in multi-radio, multi-hop wireless mesh networks, Proceedings of the 10th annual international conference on Mobile computing and networking, September 26-October 01, 2004, Philadelphia, PA, USA [doi>10.1145/1023720.1023732]
• 16: Tara Small , Zygmunt J. Haas, Resource and performance tradeoffs in delay-tolerant wireless networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.260-267, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080144]
• 17: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and wait: an efficient routing scheme for intermittently connected mobile networks, Proceeding of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.252-259, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080143]
• 18: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]
• 19: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Efficient routing in intermittently connected mobile networks: The multi-copy case. to appear in IEEE Transactions on Networking 2007.
• 20: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Efficient routing in intermittently connected mobile networks: The single-copy case. to appear in IEEE Transactions on Networking 2007.
• 21: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Spray and Focus: Efficient Mobility-Assisted Routing for Heterogeneous and Correlated Mobility, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications Workshops, p.79-85, March 19-23, 2007 [doi>10.1109/PERCOMW.2007.108]
• 22: Yu-Chee Tseng , Sze-Yao Ni , Yuh-Shyan Chen , Jang-Ping Sheu, The broadcast storm problem in a mobile ad hoc network, Wireless Networks, v.8 n.2/3, p.153-167, March-May 2002 [doi>10.1023/A:1013763825347]
• 23: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr. 2000.
• 24: Yong Wang , Sushant Jain , Margaret Martonosi , Kevin Fall, Erasure-coding based routing for opportunistic networks, Proceeding 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: A. F. Winfield. Distributed sensing and data collection via broken ad hoc wireless connected networks of mobile robots. Distributed Autonomous Robotic Systems pages 273--282, 2000.
• 26: Hao Wu , Richard Fujimoto , Randall Guensler , Michael Hunter, MDDV: a mobility-centric data dissemination algorithm for vehicular networks, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023884]
• 27: X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. In Networking 2005.
• 28: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 29: M. Zuniga and B. Krishnamachari. Analyzing the transitional region in low power wireless links. In Proceedings of IEEE SECON 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols
          Subjects: Routing protocols

General Terms:
Performance

Keywords:
delay tolerant networks, performance analysis, wireless contention