Analysis of multi-hop emergency message propagation in vehicular ad hoc networks

ABSTRACT

Vehicular Ad Hoc Networks (VANETs) are attracting the attention of researchers, industry, and governments for their potential of significantly increasing the safety level on the road. In order to understand whether VANETs can actually realize this goal, in this paper we analyze the dynamics of multi-hop emergency message dissemination in VANETs. Under a probabilistic wireless channel model that accounts for interference, we derive lower bounds on the probability that a car at distance d from the source ofthe emergency message correctly receives the message within time t. Besides d and t, this probability depends also on 1-hop channel reliability, which we model as a probability value p, and on the message dissemination strategy. Our bounds are derived for an idealized dissemination strategy which ignores interference, and for two provably near-optimal dissemination strategies under protocol interference. The bounds derived in the first part of the paper are used to carefully analyze the tradeoff between the safety level on the road (modeled by parameters d and t), and the value of 1-hop message reliability p. The analysis of this tradeoff discloses several interesting insights that can be very useful in the design of practical emergency message dissemination strategies.

REFERENCES

• 1: Maen M. Artimy , William Robertson , William J. Phillips, Assignment of dynamic transmission range based on estimation of vehicle density, Proceedings of the 2nd ACM international workshop on Vehicular ad hoc networks, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080754.1080761]
• 2: S. Bana, P. Varaiya, "Space Division Multiple Access (SDMA) for Robust Ad Hoc Vehicle Communication Networks", Proc. IEEE ITS Conference, pp. 962--967, 2001.
• 3: L. Briesemeister, L. Schafers, G. Hommel, "Disseminating Messages among Highly Mobile Hosts Based on Inter-Vehicle Communication", Proc. IEEE Intelligent Vehicles Symposium, pp. 522--527, 2000.
• 4: F. Chung, L. Lu, Complex Graphs and Networks, to appear. Sample chapters of the book are available online at http://www.math.ucsd.edu/fan/complex.
• 5: Dedicated Short Range Communications (DSRC) home, http://www.leearmstrong.com/DSRC/DSRCHomeset.htm.
• 6: "Task 3: Identifying Intelligent Vehicle Safety Applications Enabled by DSRC - Interim Report", Vehicle Safety Communications Consortium, Jan. 2003.
• 7: P. Gupta and P.R. Kumar, "The Capacity of Wireless Networks," IEEE Trans. Info. Theory, Vol. 46, No. 2, pp. 388--404, 2000.
• 8: Gökhan Korkmaz , Eylem Ekici , Füsun Özgüner , Ümit Özgüner, Urban multi-hop broadcast protocol for inter-vehicle communication systems, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023887]
• 9: Maxim Raya , Jean-Pierre Hubaux, The security of vehicular ad hoc networks, Proceedings of the 3rd ACM workshop on Security of ad hoc and sensor networks, November 07-07, 2005, Alexandria, VA, USA [doi>10.1145/1102219.1102223]
• 10: G. Resta, P. Santi, J. Simon, "Analysis of Multi-Hop Emergency Message Propagation in Vehicular Ad Hoc Networks", Tech. Rep. IIT-TR-08/2007, Istituto di Informatica e Telematica, Pisa - Italy, June 2007.
• 11: M. Sun, W. Feng, T. Lai, K. Yamada, H. Okada, K. Fujimura, "GPS-Based Message Broadcast for Adaptive Inter-Vehicle Communications", Proc. IEEE Vehicular Technology Conference, pp. 2685--2692, 2000.
• 12: Marc Torrent-Moreno , Daniel Jiang , Hannes Hartenstein, Broadcast reception rates and effects of priority access in 802.11-based 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.1023878]
• 13: Marc Torrent-Moreno , Paolo Santi , Hannes Hartenstein, Fair sharing of bandwidth in VANETs, Proceedings of the 2nd ACM international workshop on Vehicular ad hoc networks, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080754.1080762]
• 14: M. Torrent-Moreno, P. Santi, H. Hartenstein, "Distributed Fair Transmit Power Adjustment for Vehicular Ad Hoc Networks", Proc. IEEE SECON, 2006.
• 15: Qing Xu , Tony Mak , Jeff Ko , Raja Sengupta, Vehicle-to-vehicle safety messaging in DSRC, Proceedings of the 1st ACM international workshop on Vehicular ad hoc networks, October 01-01, 2004, Philadelphia, PA, USA [doi>10.1145/1023875.1023879]
• 16: Ravi M. Yadumurthy , Adithya C. H. , Mohan Sadashivaiah , Ranga Makanaboyina, Reliable MAC broadcast protocol in directional and omni-directional transmissions for vehicular ad hoc networks, Proceedings of the 2nd ACM international workshop on Vehicular ad hoc networks, September 02-02, 2005, Cologne, Germany [doi>10.1145/1080754.1080757]
• 17: X. Yang, J. Liu, F. Zhao, N. Vaidya, "A Vehicle-to-Vehicle Communication Protocol for Cooperative Collision Warning", Proc. MobiQuitous, pp. 114--123, 2004.
• 18: Jijun Yin , Tamer ElBatt , Gavin Yeung , Bo Ryu , Stephen Habermas , Hariharan Krishnan , Timothy Talty, Performance evaluation of safety applications over DSRC 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.1023877]

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Algorithms, Performance, Theory

Keywords:
active safety, dissemination strategies, emergency messaging, vehicular ad hoc networks