David A. Maltz

On-Demand Routing in Multi-hop Wireless Mobile Ad Hoc Networks Degree Type: Ph.D. in Computer Science
Advisor(s): David Johnson
Graduated: May 2001

Abstract:

An ad hoc network is a collection of wireless mobile nodes dynamically forming a temporary network without the use of any preexisting network infrastructure or centralized administration. Routing protocols used in ad hoc networks must automatically adjust to environments that can vary between the extremes of high mobility with low bandwidth, and low mobility with high bandwidth. This thesis argues that such protocols must operate in an on-demand fashion and that they must carefully limit the number of nodes required to react to a given topology change in the network. I have embodied these two principles in a routing protocol called Dynamic Source Routing (DSR). As a result of its unique design, the protocol adapts quickly to routing changes when node movement is frequent, yet requires little or no overhead during periods in which nodes move less frequently. By presenting a detailed analysis of DSR s behavior in a variety of situations, this thesis generalizes the lessons learned from DSR so that they can be applied to the many other new routing protocols that have adopted the basic DSR framework. The thesis proves the practicality of the DSR protocol through performance results collected from a full-scale 8 node testbed, and it demonstrates several methodologies for experimenting with protocols and applications in an ad hoc network environment, including the emulation of ad hoc networks.

Thesis Committee:
David B. Johnson (Chair)
M. Satyanarayanan
Hui Zhang
Martha Steenstrup (Stow Research L.L.C.)

Randy Bryant, Head, Computer Science Department
James Morris, Dean, School of Computer Science

Keywords:
Ad hoc networks, mobile networking, on-demand reactive routine protocols, network performance analysis, network emulation, Dynamic Source Routing Protocol

CMU-CS-01-130.pdf (1.38 MB) ( 192 pages)
Copyright Notice