Protocol for dynamic ad-hoc networks using distributed spanning trees

A dynamic ad-hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based a hold-and-forward or shuttling mechanisms. We introduce the notion of connectivity-through-time and the parameter holding-time as new fundamental concepts that can be used by ad-hoc routing algorithms. For various network connectivity scenarios we evaluate the impact of these concepts on the performance of ad-hoc routing algorithms. Using simulation, we study the throughput, reachability and message-reachability ratio of the proposed schemes under various connection/disconnection rates and holding times.