Capacity, delay and mobility in wireless ad-hoc networks

Network throughput and packet delay are two important parameters in the design and the evaluation of routing protocols for ad-hoc networks. While mobility has been shown to increase the capacity of a network, it is not clear whether the delay can be kept low without trading off the throughput. We consider a theoretical framework and propose a routing algorithm which exploits the patterns in the mobility of nodes to provide guarantees on the delay. Moreover, the throughput achieved by the algorithm is only a poly-logarithmic factor off from the optimal. The algorithm itself is fairly simple. In order to analyze its feasibility and the performance guarantee, we used various techniques of probabilistic analysis of algorithms. The approach taken in this paper could be applied to the analyses of some other routing algorithms for mobile ad hoc networks proposed in the literature.