Performance analysis of epidemic routing under contention

ABSTRACT

Epidemic routing has been proposed as a robust transmission scheme for sparse mobile ad hoc networks. Under the assumption of no contention, epidemic routing has the minimum end-to-end delay amongst all the routing schemes proposed for such networks. The assumption of no contention was justified by arguing that since the network is sparse, there will be very few simultaneous transmissions. Some recent papers have shown through simulations that this argument is not correct and that contention cannot be ignored while analyzing the performance of routing schemes, even in sparse networks.Incorporating contention in the analysis has always been a hard problem and hence its effect has been studied mostly through simulations only. In this paper, we find analytical expressions for the delay performance of epidemic routing with contention. We include all the three main manifestations of contention, namely (i) the finite bandwidth of the link which limits the number of packets two nodes can exchange, (ii) the scheduling of transmissions between nearby nodes which is needed to avoid excessive interference, and (iii) the interference from transmissions outside the scheduling area. The accuracy of the analysis is verified via simulations.

REFERENCES

• 1: Disruption tolerant networking. http://www.darpa.mil/ato/solicit/DTN/.
• 2: Torus hitting times and green's functions. http://www.math.tamu.edu/~rellis/comb/torus/torus.html.
• 3: 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
• 4: D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. (monograph in preparation.). http://stat-www.berkeley.edu/users/aldous/RWG/book.html.
• 5: 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.
• 6: A. Doria, M. Udén, 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.
• 7: R. Groenevelt, P. Nain, and G. Koole. The message delay in mobile ad hoc networks. In Performance, 2005.
• 8: A. Jindal and K. Psounis. Perfomance analysis of epidemic routing under contention. Technical Report CENG-2006-2, USC, 2006.
• 9: 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
• 10: S. Kandukuri and S. Boyd. Optimal power control in interference-limited fading wireless channels with outage-probability specifications. IEEE Transactions on Wireless Communications, 1, Jan. 2002.
• 11: 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]
• 12: S. Ross. Introduction to Probability Models. Academic Press, 8 edition, 2002.
• 13: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Multiple-copy routing in intermittently connected mobile networks. Technical Report CENG-2004-12, USC, 2004.
• 14: T. Spyropoulos, K. Psounis, and C. S. Raghavendra. Single-copy routing in intermittently connected mobile networks. In Proceedings of IEEE SECON, 2004.
• 15: 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]
• 16: 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]
• 17: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks. Technical Report CS-200006, Duke University, Apr. 2000.
• 18: 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.
• 19: X. Zhang, G. Neglia, J. Kurose, and D. Towsley. Performance modeling of epidemic routing. Technical Report CMPSCI 05-44, Umass, 2005.
• 20: 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

Additional Classification:
  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Performance

Keywords:
ad-hoc networks, contention, delay tolerant networks, epidemic routing