Improving Backbone Routing for Transient Communication in Mobile Ad Hoc Networks

Multi-hop routing in mobile ad hoc networks is challenging due to node mobility, low power, constrained bandwidth and limited radio range. Previous work has shown that reactive flat algorithms outperform proactive algorithms under high mobility. Hybrid and hierarchical approaches further improve performance by reducing the range and frequency of broadcast route discovery messages. Current algorithms, however, perform poorly when dealing with spontaneous, transient communication. This traffic pattern generates route discoveries much more frequently than long-term communication and thus causes the reactive component of flat routing algorithms to flood the network, triggering broadcast storms that render the network temporally useless. Similarly, the increased number of route discoveries also makes the backbone a bottleneck for the hierarchical algorithms. This paper describes the design of a backbone routing scheme, called DCDS, that handles transient traffic well. Like other backbone routing algorithms, it uses proactive components to group nodes into clusters and construct a backbone; it then uses a reactive protocol to route packets over the backbone. The three key novel features of our algorithm are: (1) it uses piggybacking to prefetch multiple routes in response to a single request, (2) it timestamps cache entries to provide a heurstic for flushing out-of-date routes from caches and (3) it uses proactive, local information to adapt to and recovery from some failures without changing globally-cached routes or dropping packets. We evaluate DCDS using Glomosim to simulate it and three other algorithms, two variants of DSR and a model hierarchical algorithm, for comparison. Our results show that DCDS performs substantially better than these other algorithms for the workloads we studied.