Author(s):
|
Stephen Dabideen, University of California,Santa Cruz, USA ; JJ Garcia-Luna-Aceves, University of California at Santa Cruz, USA
|
Abstract:
|
Most routing protocols designed for MANETs to date employ breadth-first search (BFS), usually in the form of flooding of route requests or updates, to establish and maintain routes between in source-destination pairs. This usually incurs significant overhead, which degrades the performance of the network. In this paper we present a new paradigm for routing protocols operating in MANETs, and such that flooding is not required and paths from sources to destinations can be established on demand with time complexity comparable to that of flooding but with significantly less overhead. We introduce the concept of ordered walk as a depth-first search (DFS) based search that does not rely on geographical or virtual coordinate information and is more efficient than mere random walks. Using this algorithm,we demonstrate the great potential of using DFS as the building block of the signaling of MANET routing protocols. We introduce the OWL protocol (ordered walk with learning) as an example of efficient DFS-based routing in MANETs, and use simulation experiments to compare its performance against that of three well-known MANET routing protocols based on BFS (OLSR, DSR and AODV).
|