OWL: Towards scalable routing in MANETs using depth-first search on demand

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 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, 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 based search (DFS) that does not rely on geographical or virtual coordinate information and is more efficient than mere random walks. Using the ordered walk search algorithm (OSA), we demonstrate the 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). The results show that OWL can achieve comparable these protocols while incurring up to ten times less overhead than AODV.