Delay-bounded routing in vehicular ad-hoc networks

ABSTRACT

Ad hoc networks formed by traveling vehicles are envisaged to become a common platform that will support a wide variety of applications, ranging from road safety to advertising and entertainment. The multitude of vehicular applications calls for routing schemes that satisfy user-defined delay requirements while at the same time maintaining a low level of channel utilization to allow their coexistence. This paper focuses on the development of carry-and-forward schemes that attempt to deliver data from vehicles to fixed infrastructure nodes in an urban setting. The proposed algorithms leverage local or global knowledge of traffic statistics to carefully alternate between the Data Muling and Multihop Forwarding strategies, in order to minimize communication overhead while adhering to delay constraints imposed by the application. We provide an extensive evaluation of our schemes using realistic vehicular traces on a real city map.

REFERENCES

• 1: http://www.openstreetmap.org.
• 2: J. Blum, A. Eskandarian, and L. Hoffman. Challenges of inter-vehicle ad hoc networks. In IEEE Transactions on Intelligent Transportation Systems, 5(4), pages 347--351, 2004.
• 3: Linda Briesemeister , Günter Hommel, Role-based multicast in highly mobile but sparsely connected ad hoc networks, Proceedings of the 1st ACM international symposium on Mobile ad hoc networking & computing, November 20, 2000, Boston, Massachusetts
• 4: T. Camp, J. Boleng, and V. Davies. A survey of mobility models for ad hoc network research. Wireless Communications and Mobile Computing (WCMC): Special issue on Mobile Ad Hoc Networking: Research, Trends and Applications, 2(5):483--502, 2002.
• 5: Paolo Costa , Davide Frey , Matteo Migliavacca , Luca Mottola, Towards lightweight information dissemination in inter-vehicular networks, Proceedings of the 3rd international workshop on Vehicular ad hoc networks, September 29-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161064.1161069]
• 6: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 7: A. Goel, K. G. Ramakrishnan, D. Kataria, and D. Logothetis. Efficient computation of delay-sensitive routes from one source to all destinations. In Conf. on Computer Communications (INFOCOM), pages 854--858, 2001.
• 8: N. Golmie , R. E. Van Dyck , A. Soltanian, Interference of bluetooth and IEEE 802.11: simulation modeling and performance evaluation, Proceedings of the 4th ACM international workshop on Modeling, analysis and simulation of wireless and mobile systems, p.11-18, July 2001, Rome, Italy [doi>10.1145/381591.381598]
• 9: J. LeBrun, C.-N. Chuah, D. Ghosal, and M. Zhang. Knowledge-based opportunistic forwarding in vehicular wireless ad hoc networks. In Vehicular Technology Conference, 2005. VTC 2005-Spring. 2005 IEEE 61st, volume 4, pages 2289--2293, May/June 2005.
• 10: Valery Naumov , Rainer Baumann , Thomas Gross, An evaluation of inter-vehicle ad hoc networks based on realistic vehicular traces, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132918]
• 11: E. Royer and C. Toh. A review of current routing protocols for ad-hoc mobile wireless networks. In IEEE Personal Communications, 1999.
• 12: J. Singh, N. Bambos, B. Srinivasan, and D. Clawin. Wireless lan performance under varied stress conditions in vehicular traffic scenarios. In IEEE VTC Fall 2002, volume 2, pages 743--747, 2002.
• 13: A. Vahdat and D. Becker. Epidemic routing for partially connected ad hoc networks.
• 14: 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]
• 15: B. Xu, A. Ouksel, and O. Wolfson. Opportunistic resource exchange in inter-vehicle ad-hoc networks. In IEEE International Conference on Mobile Data Management (MDM), 2004.
• 16: J. Zhao and G. Cao. Vadd: Vehicle-assisted data delivery in vehicular ad hoc networks. In Conf. on Computer Communications (INFOCOM), 2006.
• 17: 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]

INDEX TERMS

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

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

General Terms:
Algorithms, Performance

Keywords:
VANET, ad hoc network, delay, inter-vehicle communication, minimum cost forwarding, routing, vehicular network