TABLE OF CONTENTS In this paper, we have studied the fundamental capacity-delay tradeoff in mobile wireless networks under the i.i.d. mobility model. Our contributions are three-fold. We have established the upper bound on the optimal capacity-delay tradeoff over all causal scheduling policies. The upper bound not only provides the fundamental limits of capacity and delay, but also helps to identify the optimal values of the key scheduling parameters in order to achieve the optimal capacity-delay tradeoff. Our second contribution is to develop a new scheduling scheme that can achieve a capacity-delay tradeoff that differs from the upper bound only by a logarithmic factor, which also implies that our upper bound is fairly tight. The capacity achievable by our new scheme is larger than that of the existing schemes in [3] and [4]. In particular, when the delay is bounded by a constant, our scheme achieves a per-node capacity of ?( n -1/3/ log n). This demonstrates that, under the i.i.d. mobility model, mobility increases the capacity even with constant delays. Our third contribution is to use the insight drawn from the upper bound to identify the limiting factors in the existing schemes. These results present a relatively complete picture of the achievable capacity-delay tradeoffs under different considerations.
In this paper, we have assumed an i.i.d. mobility model. For future work, we plan to study the optimal capacity-delay tradeoff for mobile wireless networks under other mobility models. Among the properties that we proved...
