Simulation-based performance evaluation of routing protocols for mobile ad hoc networks

ABSTRACT

In this paper we evaluate several routing protocols for mobile, wireless, ad hoc networks via packet‐level simulations. The ad hoc networks are multi‐hop wireless networks with dynamically changing network connectivity owing to mobility. The protocol suite includes several routing protocols specifically designed for ad hoc routing, as well as more traditional protocols, such as link state and distance vector, used for dynamic networks. Performance is evaluated with respect to fraction of packets delivered, end‐to‐end delay, and routing load for a given traffic and mobility model. Both small (30 nodes) and medium sized (60 nodes) networks are used. It is observed that the new generation of on‐demand routing protocols use much lower routing load, especially with small number of peer‐to‐peer conversations. However, the traditional link state and distance vector protocols provide, in general, better packet delivery and end‐to‐end delay performance.

REFERENCES

• 1: C. Alaettinoglu, A.U. Shankar, K. Dussa-Zieger and I. Matta, De-sign and implementation of MaRS: A routing testbed, Journal of Internetworking: Research and Experience 5(1) (1994) 17-41.
• 2: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 3: Josh Broch , David A. Maltz , David B. Johnson , Yih-Chun Hu , Jorjeta Jetcheva, A performance comparison of multi-hop wireless ad hoc network routing protocols, Proceedings of the 4th annual ACM/IEEE international conference on Mobile computing and networking, p.85-97, October 25-30, 1998, Dallas, Texas, United States [doi>10.1145/288235.288256]
• 4: C. Cheng , R. Riley , S. P. R. Kumar , J. J. Garcia-Luna-Aceves, A loop-free extended Bellman-Ford routing protocol without bouncing effect, Symposium proceedings on Communications architectures & protocols, p.224-236, September 25-27, 1989, Austin, Texas, United States
• 5: M.S. Corson, S. Batsell and J. Macker, Architectural con-siderations for mobile mesh networking (May 1996) Request for comments draft; http://tonnant.itd.nrl.navy.mil/ mmnet/mmnetRFC.txt.
• 6: M. Scott Corson , Anthony Ephremides, A distributed routing algorithm for mobile wireless networks, Wireless Networks, v.1 n.1, p.61-81, Feb. 1995 [doi>10.1007/BF01196259]
• 7: S. Corson, S. Papademetriou, P. Papadopoulos, V. Park and A. Qayyum, An Internet MANET Encapsulation Protocol (IMEP) specification, Internet Draft (1998), http://www.ietf.org/ internet-drafts/draft-ietf-manet-imep-spec-01. txt.
• 8: E.W. Dijkstra, A note on two problems in connection with graphs, Numerical Mathematics 1 (1959) 269-271.
• 9: E. Gafni and D. Bertsekas, Distributed algorithms for generating loop-free routes in networks with frequently changing topology, IEEE Transactions on Communication 29(1) (1981) 11-18.
• 10: J. J. Garcia-Luna-Aceves, A unified approach to loop-free routing using distance vectors or link states, Symposium proceedings on Communications architectures & protocols, p.212-223, September 25-27, 1989, Austin, Texas, United States
• 11: Mario Gerla , Jack Tzu-Chieh Tsai, Multicluster, mobile, multimedia radio network, Wireless Networks, v.1 n.3, p.255-265, 1995 [doi>10.1007/BF01200845]
• 12: Z. Haas, A new routing protocol for the reconfigurable wireless net-works, in: Proc. of the IEEE Internat. Conf. on Universal Personal Communications (October 1997).
• 13: Z.J. Haas and M.R. Pearlman, The Zone Routing Protocol (ZRP) for ad hoc networks, IETF Internet draft (1997), http:// www.ietf.org/internet-drafts/draft-ietf-manet-zonezrp-00.txt.
• 14: Zygmunt J. Haas , Marc R. Pearlman, The performance of query control schemes for the zone routing protocol, Proceedings of the ACM SIGCOMM '98 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-177, August 31-September 04, 1998, Vancouver, British Columbia, Canada
• 15: C. Hedrick, Routing information protocol, RFC 1058 (June 1988).
• 16: B. Ireisleben and R. Jansen, Analysis of routing protocols for ad hoc networks of mobile computers, in: Proc. of the 15th IASTED Internat. Conf. on Applied Informatics, Innsbruck, Austria (IASTED-Acta Press, 1997) pp. 33-136.
• 17: D. Johnson and D. Maltz, Dynamic source routing in ad hoc wire-less networks, in: Mobile Computing (Kluwer Academic, Dordrecht, 1996).
• 18: J. Jubin and J.D. Tornow, The DARPA packet radio network proto-cols, Proceedings of the IEEE 75(1) (1987) 21-32.
• 19: S. Keshav, An engineering approach to computer networking: ATM networks, the Internet, and the telephone network, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 20: A. Khanna , J. Zinky, The revised ARPANET routing metric, Symposium proceedings on Communications architectures & protocols, p.45-56, September 25-27, 1989, Austin, Texas, United States
• 21: P. Krishna , N. H. Vaidya , M. Chatterjee , D. K. Pradhan, A cluster-based approach for routing in dynamic networks, ACM SIGCOMM Computer Communication Review, v.27 n.2, p.49-64, Apr. 1997 [doi>10.1145/263876.263885]
• 22: J. Macker and S. Corson, Mobile Ad hoc Networks (MANET), IETF Working Group Charter (1997), http://www.ietf.org/ html.charters/manet-charter.html.
• 23: J. Moy, OSPF Version 2. RFC 1247 (July 1991).
• 24: Shree Murthy , J. J. Garcia-Luna-Aceves, An efficient routing protocol for wireless networks, Mobile Networks and Applications, v.1 n.2, p.183-197, Oct. 1996 [doi>10.1007/BF01193336]
• 25: V. Park and S. Corson, A performance comparison of TORA and ideal link state routing, in: Proc. of IEEE Symposium of Computers and Communication (June 1998).
• 26: V. Park and S. Corson, Temporally Ordered Routing Algo-rithm (TORA) Version 1, Functional specification IETF Internet draft (1998), http://www.ietf.org/internet-drafts/ draft-ietf-manet-tora-spec-01.txt.
• 27: Vincent D. Park , M. Scott Corson, A Highly Adaptive Distributed Routing Algorithm for Mobile Wireless Networks, Proceedings of the INFOCOM '97. Sixteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Driving the Information Revolution, p.1405, April 09-11, 1997
• 28: C. Perkins, Ad hoc On demand Distance Vector (AODV) rout-ing, IETF Internet draft (1997), http://www.ietf.org/ internet-drafts/draft-ietf-manet-aodv-00.txt.
• 29: Charles E. Perkins , Pravin Bhagwat, Highly dynamic Destination-Sequenced Distance-Vector routing (DSDV) for mobile computers, Proceedings of the conference on Communications architectures, protocols and applications, p.234-244, August 31-September 02, 1994, London, United Kingdom
• 30: Y. Rekhter and T. Li, A border gateway protocol-4, RFC 827 (March 1995).
• 31: N. Schacham and J. Westcott, Future directions in packet radio archi-tectures and protocols, Proceedings of the IEEE 75(1) (1987) 83-99.
• 32: A. Udaya Shankar , Cengiz Alaettinoğlu , Ibrahim Matta , Klaudia Dussa-Zieger, Performance comparison of routing protocols using MaRS: distance-vector versus link-state, Proceedings of the 1992 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.181-192, June 01-05, 1992, Newport, Rhode Island, United States
• 33: Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications, IEEE Standard 802.11-1997, IEEE Standards Department (1997).

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.1 Network Architecture and Design
          Subjects: Wireless communication

General Terms:
Design