Merit: A unified framework for routing protocol assessment in mobile AD Hoc networks

ABSTRACT

MERIT is a framework to assess routing protocols in mobile Ad hoc networks (manets). It is based on the novel concept of a shortest mobile path (SMP) in a mobile qraph, generalizing the traditional shortest path concept for the mobile environment. As a standard measure for routing protocols in a manet, the MERIT framework proposes the mean ratio of the cost of the actually used route to the cost of the optimal mobile path, under the same history of link metrics in the changing network topology. The MERIT spectrum takes the MERIT ratio as a function of parameters of interest yielding a multi-faceted representation of protocol effectiveness. This Mean Real vs. Ideal cosT (MERIT) framework is unifying in that it provides a measure that allows a protocol to be assessed independently of other protocols, within its own environment. We show that there is an efficient algorithm to solve the underlying SMP problem for important cases, making the approach practically feasible. We also investigate generalizations of and extensions within the MERIT framework.

REFERENCES

• 1: 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]
• 2: M.S. Corson and J. Macker. Mobile Ad hoc Networking (manet): Routing Protocol Performance Issues and Evaluation Considerations. In Network Working Group, RFC 2501. January 1999. http://www.ieft.org/rfc/rfc2501.txt
• 3: The C++ Protocol Toolkit (CPT). Rooftop Communications Corp. (Now Nokia Rooftop.) http://www.rooftop.com
• 4: A. Farago and V.R. Syrotiuk. Transport Layer Routing Assessment in Mobile Ad Hoc Networks. Submitted to Symposium on Ad Hoc Wireless Networks, IEEE Global Communications Conference (Globecom'01).
• 5: András Faragó , Áron Szentesi , Balázs Szviatovszki, Inverse optimization in high-speed networks, Discrete Applied Mathematics, v.129 n.1, p.83-98, 15 June 2003 [doi>10.1016/S0166-218X(02)00235-4]
• 6: M.R. Garey and D.S. Johnson. Computers and Intractability. W.H. Freeman and Co., San Francisco, California, 1983.
• 7: GloMoSim: Global Mobile Information Systems Simulation Library. The University of California, Los Angeles. http://pcl.cs.ucla.edu/projects/glomosim/
• 8: D.B. Johnson. Routing in Ad Hoc Networks of Mobile Hosts, In IEEE Workshop on Mobile Computing Systems and Applications, pages 158-163. December 1994.
• 9: The Network Simulator - ns-2. The University of California, Berkeley. http://www.isi.edu/nsname/ns/
• 10: OPNET: Optimum Network Performance. OPNET Technologies, Inc. http://www.mil3.com
• 11: 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
• 12: Ad hoc networking, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 2001
• 13: C.E. Perkins and P. Bhagwat. DSDV Routing over a Multihop Wireless Network of Mobile Computers. In T. Imielinski and H.F. Korth, editors, Mobile Computing, pages 183-206. Kluwer Inc., 1996.
• 14: Charles E. Perkins , Elizabeth M. Royer, Ad-hoc On-Demand Distance Vector Routing, Proceedings of the Second IEEE Workshop on Mobile Computer Systems and Applications, p.90, February 25-26, 1999
• 15: E.M. Royer and C.-K. Toh. A Review of Current Routing Protocols for Ad Hoc Mobile Wireless Networks. In IEEE Personal Communications, pages 46-55. April 1999.
• 16: Zheng Wang, On the complexity of quality of service routing, Information Processing Letters, v.69 n.3, p.111-114, Feb. 12, 1999 [doi>10.1016/S0020-0190(98)00206-3]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features
          Subjects: Frameworks
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Network communication

General Terms:
Algorithms, Experimentation, Performance