A framework for reliable routing in mobile ad hoc networks

Abstract

Mobile ad hoc networks consist of nodes that are often vulnerable to failure. As such, it is important to provide redundancy in terms of providing multiple node- disjoint paths from a source to a destination. We first pro- pose a modified version of the popular AODV protocol that allows us to discover multiple node-disjoint paths from a source to a destination. We find that very few of such paths can be found. Furthermore, as distances between sources and destinations increase, bottlenecks inevitably occur and thus, the possibility of finding multiple paths is considerably reduced. We conclude that it is necessary to place what we call reliable nodes (in terms of both being robust to failure and being secure) in the network for efficient operations. We propose a deployment strategy that determines the po- sitions and the trajectories of these reliable nodes such that we can achieve a framework for reliably routing informa- tion. We define a notion of a reliable path which is made up of multiple segments, each of which either entirely con- sists of reliable nodes, or contains a preset number of mul- tiple paths between the end points of the segment. We show that the probability of establishing a reliable path between a random source and destination pair increases considerably even with a low percentage of reliable nodes when we con- trol their positions and trajectories in accordance with our algorithm.