1st Annual Conference on Broadband Networks

Research Article

Capacity and delay tradeoffs for ad-hoc mobile networks

  • @INPROCEEDINGS{10.1109/BROADNETS.2004.21,
        author={Michael J. Neely and Eytan Modiano},
        title={Capacity and delay tradeoffs for ad-hoc mobile networks},
        proceedings={1st Annual Conference on Broadband Networks},
  • Michael J. Neely
    Eytan Modiano
    Year: 2004
    Capacity and delay tradeoffs for ad-hoc mobile networks
    DOI: 10.1109/BROADNETS.2004.21
Michael J. Neely1, Eytan Modiano2
  • 1: University of Southern California
  • 2: Massachusetts Inst. of Technology


We consider the throughput/delay tradeoffs for scheduling data transmissions in a mobile ad-hoc network. To reduce delays in the network, each user sends the redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified iid mobility model, we compute the exact network capacity and the exact end-to-end queueing delay when no redundancy is used. The capacity achieving algorithm is a modified version of the Grossglauser-Tse 2-hop relay algorithm and provides O(N) delay (where N is the number of users). We then show that redundancy cannot increase capacity, but can significantly improve delay. The following necessary tradeoff is established: delay/rate ≥ O(N). Two protocols which use redundancy and operate near the boundary of this curve are developed, with delays of O(√N) and O(log(N)), respectively. Networks with non-iid mobility are also considered and shown through simulation to closely match the performance of iid systems in the O(√N) delay regime.