1. Introduction

Since the seminal paper by Gupta and Kumar [1], there has been tremendous interest in the networking research community to understand the fundamental achievable capacity in wireless networks. For a static network (where nodes do not move), Gupta and Kumar show that the per-node capacity decreases as O(1 / ) ^[1] as the number of nodes n increases [1]. The capacity of wireless networks can be improved when mobility is taken into account. When the nodes are mobile, Grossglauser and Tse show that per-node capacity of ?(1) is achievable [2], which is much better than that of static networks. This capacity improvement is achieved at the cost of excessive packet delays. In fact, it has been pointed out in [2] that the packet delay of the proposed scheme could be unbounded.

There have been several recent studies that attempt to address the relationship between the achievable capacity and the packet delay in mobile wireless networks. In the work by Neely and Modiano [3], it was shown that the maximum achievable per-node capacity of a mobile wireless network is bounded by O(1). Under an i.i.d. mobility model, the authors of [3] present a scheme that can achieve ?(1) per-node capacity and incur ?( n) delay, provided that the load is strictly less than the capacity. Further, they show that it is possible to reduce packet delay if one is willing to sacrifice capacity. In [3], the authors formulate and...