MotionCast: on the capacity and delay tradeoffs

ABSTRACT

In this paper, we define multicast for ad hoc network through nodes' mobility as MotionCast, and study the capacity and delay tradeoffs for it. Assuming nodes move according to an independently and identically distributed (i.i.d.) pattern and each desires to send packets to k distinctive destinations, we compare the capacity and delay in two transmission protocols: one uses 2-hop relay algorithm without redundancy, the other adopts the scheme of redundant packets transmissions to improve delay while at the expense of the capacity. In addition, we obtain the maximum capacity and the minimum delay under certain constraints. We find that the per-node capacity and delay for 2-hop algorithm without redundancy are Θ(1/k) and Θ(nlog k), respectively; and for 2-hop algorithm with redundancy they are Ω(1/(k√nlog k)) and Θ(√nlog k), respectively. The capacity of the 2-hop relay algorithm without redundancy is better than the multicast capacity of static networks developed in [3] as long as k is strictly less than n in an order sense; while when k=Θ(n), mobility does not increase capacity anymore. The ratio between delay and capacity satisfies delay/rate ≥ O(nklog k) for these two protocols, which is smaller than that of directly extending the fundamental tradeoff for unicast established in [1] to multicast, i.e., O(nk²).

REFERENCES

• 1: M.J. Neely, and E. Modiano, "Capaicty and delay tradeoffs for ad hoc mobile networks," IEEE Transactions on Information Theory, vol. 51, no. 6, pp. 1917--1937, Jun. 2005.
• 2: X. Lin and N. B. Shroff, "The fundamental capacity-delay tradeoff in large mobile wireless networks", Technical Report, 2004. Available at http://cobweb.ecn.purdue.edu/~linx/papers.html
• 3: Xiang-Yang Li , Shao-Jie Tang , Ophir Frieder, Multicast capacity for large scale wireless ad hoc networks, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287886]
• 4: P. Gupta and P. R. Kumar, "The capacity of wireless networks," IEEE Transactions on Information Theory, vol. 46, no. 2, pp. 388--404, Mar. 2000.
• 5: Alireza Keshavarz-Haddad , Vinay Ribeiro , Rudolf Riedi, Broadcast capacity in multihop wireless networks, Proceedings of the 12th annual international conference on Mobile computing and networking, September 23-29, 2006, Los Angeles, CA, USA [doi>10.1145/1161089.1161117]
• 6: Philippe Jacquet , Georgios Rodolakis, Multicast Scaling Properties in Massively Dense Ad Hoc Networks, Proceedings of the 11th International Conference on Parallel and Distributed Systems - Workshops, p.93-99, July 20-22, 2005
• 7: Srinivas Shakkottai , Xin Liu , R. Srikant, The multicast capacity of large multihop wireless networks, Proceedings of the 8th ACM international symposium on Mobile ad hoc networking and computing, September 09-14, 2007, Montreal, Quebec, Canada [doi>10.1145/1288107.1288141]
• 8: Matthias Grossglauser , David N. C. Tse, Mobility increases the capacity of ad hoc wireless networks, IEEE/ACM Transactions on Networking (TON), v.10 n.4, p.477-486, August 2002 [doi>10.1109/TNET.2002.801403]
• 9: A.E. Gamal, J. Mammen, B. Prabhakar, and D. Shah, "Throughput-delay trade-off in wireless networks," in Proceedings of IEEE INFOCOM, Mar. 2004.
• 10: Lei Ying, Sichao Yang and R. Srikant, "Optimal delay-throughput trade-offs in mobile ad hoc Networks," IEEE Transactions on Information Theory, vol. 54, no. 9, pp. 4119--4143, Sept. 2008.
• 11: S. Toumpis and A.J. Goldsmith, "Large wireless networks under fading, mobility, and delay constraints," in Proceedings of IEEE INFOCOM, Mar. 2004.
• 12: Mo Li , Yunhao Liu, Rendered path: range-free localization in anisotropic sensor networks with holes, Proceedings of the 13th annual ACM international conference on Mobile computing and networking, September 09-14, 2007, Montréal, Québec, Canada [doi>10.1145/1287853.1287861]
• 13: R.L. Cruz and A.V. Santhanam, "Hierarchical link scheduling and power control in multihop wireless networks," in Proceedings of the Annual Allerton Conference on communication, Control and Computing, Oct. 2002.
• 14: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Efficient routing in intermittently connected mobile networks: the multiple-copy case, IEEE/ACM Transactions on Networking (TON), v.16 n.1, p.77-90, February 2008 [doi>10.1109/TNET.2007.897964]
• 15: S.M. Ross, Stochastic processes. New York: John Wiley & Sons, 1996.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design

General Terms:
Algorithms, Theory

Keywords:
capacity, delay, mobility, multicast, scaling law