On optimal TTL sequence-based route discovery in MANETs

In on-demand multi-hop routing protocols for MANETs such as DSR and AODV, a fundamental requirement for peer-to-peer connectivity is to discover routes to a remote node via flooding of route request messages. Historically, such floodings of requests have used a TTL (time-to-live) large enough to reach all nodes in the network to ensure successful route discovery in one round of flooding. Recently (N. Chang et al., 2004), it was shown that the generic minimal cost flooding search problem can be solved via a sequence of floodings with an optimally chosen set of TTLs. The theoretical result, when applied to DSR route discovery, does not take into account optimizations such as route caching and overhearing, which can significantly reduce the frequency and the propagation range of route discovery operations. Equally importantly, the impact of using a sequence of floodings on the packet delivery delay is not clear. In this paper, we study the impact of using the optimal TTL sequence-based route discovery on DSR routing performance. Our results show when caching and overhearing are considered, the route discovery enhanced by an optimal TTL sequence has very similar overhead but higher delay than the basic route discovery mechanism.