On the throughput-delay trade-off 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, mobile nodes move according to an i.i.d. random walk with velocity v and transmit packets to randomly chosen destinations. The average packet delivery delay of our scheme is of order 1/v and it achieves the network capacity of order n/(log n log log n). This shows a practical throughput-delay trade-off, in particular when compared with the seminal result of Gupta and Kumar which shows network capacity of order √(n/log n) 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 √n/v. The foundation of our improved capacity and delay trade-off relies on the fact that we use a mobility model that contains free space motion, 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.