The Medium Time Metric: High Throughput Route Selection in Multi-rate Ad Hoc Wireless Networks

Modern wireless devices, such as those that implement the 802.11abg standards, utilize multiple transmission rates in order to accommodate a wide range of channel conditions. The use of multiple rates presents a significantly more complex challenge to ad hoc routing protocols than the traditional single rate model. The hop count routing metric, which is traditionally used in single rate networks, is sub-optimal in multi-rate networks as it tends to select short paths composed of maximum length links. In a multi-rate network, these long distance links operate at the slowest available rate, thus achieving low effective throughput and reduced reliability due to the low signal levels. In this work we explore the lower level medium access control and physical phenomena that affect routing decisions in multi-rate ad hoc networks. We provide simulation results which illustrate the impact of these phenomena on effective throughput and show how the traditional minimum hop routing strategy is inappropriate for multi-rate networks. As an alternative, we present the Medium Time Metric (MTM) which avoids using the long range links often selected by shortest path routing in favor of shorter, higher throughput, more reliable links. Our experimental results with 802.11 g radios show that the Medium Time Metric achieves significantly higher throughput then alternative metrics. We observed up to 17 times more end-to-end TCP throughput than when the Min Hop or ETX metrics were used. Baruch Awerbuch is currently a professor at the Computer Science Dept. at Johns Hopkins University. His current Research interests include: Security, Online Algorithms, Distributed and Peer-to-Peer Systems, Recommendation Systems, and Wireless Networks. Baruch Awerbuch has published more than 100 papers in journals and refereed conferences in the general area of design and analysis of online algorithms, combinatorial and network optimization, distributed algorithms, learning, fault tolerance, network architecture, and others. Baruch Awerbuch is a co-director of the JHU Center for Networks and distributed systems http://www.cnds.jhu.edu. He is supervising the Archipelago project http://www.cnds.jhu.edu/archipelago whose goal is developing WiFi (IEEE 802.11 based) multi-hop wireless network based on novel rerouting algorithms. Dr. Awerbuch served as a member of the Editorial Board for Journal of Algorithms, Wireless Networks and Interconnection Networks. He was a program chair of the 1995 ACM Conference on Wireless Computing & Communication and a member of the program committees of the 2004 ACM Mobihoc, as well as PC member ACM PODC Principles of Distributed Computing (PODC) Conference in 1989 and of the Annual ACM STOC (Symposium on Theory of Computing) Conference in 1990 and 1991. Web: http://www.cs.jhu.edu/~baruch David Holmer received his B.S. in electrical engineering and MSE in computer science from the Johns Hopkins University in 2001 and 2002. He is now a Ph.D. candidate in the Department of Computer Science at Johns Hopkins University, and a research assistant in the Wireless Communication Group. The theme of his research is the development of deployable high performance ad hoc networking technology. As a result, his interests span many aspects of wireless networking including: routing, medium access control, physical layer properties and simulation, security, and energy efficiency. Herbert Rubens is a Ph.D. candidate in the Computer Science Department at the Johns Hopkins University (JHU) in Baltimore, Maryland. He is a member of the Wireless Communication Group, and specializes in multi-hop ad hoc protocol design. He has designed innovative mechanisms allowing power efficiency, high scalability, and efficient resource allocation in wireless networks. He obtained his B.Sc. and Masters Degree in computer science from Johns Hopkins University in 2001 and 2002 respectively. His research interests include ad hoc routing, medium access control, network security, and distributed algorithms.