On the Throughput-Delay Tradeoff in Georouting Networks

We study the scaling properties of a georouting scheme in a wireless multi-hop network of n mobile nodes. Our aim is to increase the network capacity quasi-linearly with n, while keeping the average delay bounded. In our model, we consider mobile nodes moving according to an independent identically distributed random walk with velocity v and transmitting packets to randomly chosen fixed and known destinations. The average packet delivery delay of our scheme is of order 1/v, and it achieves network capacity of order (n/log n log log n). This shows a practical throughput-delay tradeoff, in particular when compared with the seminal result of Gupta and Kumar, which shows network capacity of order (n/ log n)1/2 and negligible delay and the groundbreaking result of Grossglauser and Tse, which achieves network capacity of order n but with an average delay of order v n/v. The foundation of our improved capacity and delay tradeoff relies on the fact that we use a mobility model that contains straight-line segments, a model that we consider more realistic than classic Brownian motions. We confirm the generality of our analytical results using simulations under various interference models.