Capacity and Delay Tradeoffs for Ad Hoc Mobile Networks
Top Cited Papers
- 31 May 2005
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 51 (6) , 1917-1937
- https://doi.org/10.1109/tit.2005.847717
Abstract
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 redundant packets along multiple paths to the destination. Assuming the network has a cell partitioned structure and users move according to a simplified independent and identically distributed (i.i.d.) 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 two-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/spl ges/O(N). Two protocols that use redundancy and operate near the boundary of this curve are developed, with delays of O(/spl radic/N) and O(log(N)), respectively. Networks with non-i.i.d. mobility are also considered and shown through simulation to closely match the performance of i.i.d. systems in the O(/spl radic/N) delay regime.Keywords
This publication has 15 references indexed in Scilit:
- Capacity and delay tradeoffs for ad-hoc mobile networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Large wireless networks under fading, mobility, and delay constraintsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Throughput-delay trade-off in wireless networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Locating nodes with EASE: last encounter routing in ad hoc networks through mobility diffusionPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Exploiting data diversity and multiuser diversity in noncooperative mobile infostation networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2004
- Delay limited capacity of ad hoc networks: asymptotically optimal transmission and relaying strategyPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Mobility increases the capacity of ad-hoc wireless networksPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Replication strategies in unstructured peer-to-peer networksPublished by Association for Computing Machinery (ACM) ,2002
- Multipath routing in the presence of frequent topological changesIEEE Communications Magazine, 2001
- The capacity of wireless networksIEEE Transactions on Information Theory, 2000