The fundamental capacity-delay tradeoff in large mobile ad hoc networks

Abstract — There has been recent interest within the networking research community to understand how mobility can improve the capacity of mobile ad hoc networks. Of particular interest is the achievable capacity under delay constraints. In this paper, we establish the following upper bound on the optimal capacity-delay tradeoff in mobile ad hoc networks for an i.i.d. mobility model. For a mobile ad hoc network with n nodes, if the per-bit-averaged mean delay is bounded by ¯ D, then the per-node capacity λ is upper bounded by λ 3 ≤ O ( ¯ D n log3 n). By studying the condition under which the upper bound is tight, we are able to identify the optimal values of several key scheduling parameters. We then develop a new scheme that can achieve a capacity-delay tradeoff close to the upper bound up to a logarithmic factor. Our new scheme achieves a larger per-node capacity than the schemes reported in previous works. In particular, when the delay is bounded by a constant, our scheme achieves a per-node capacity of Θ(n −1/3 / log n). This indicates that, for the i.i.d. mobility model, mobility results in a larger capacity than that of static networks even with constant delays. Finally, the insight drawn from the upper bound allows us to identify limiting factors in existing schemes. These results present a relatively complete picture of the achievable capacity-delay tradeoffs under different settings. I