Capacity scaling in delay tolerant networks with heterogeneous mobile nodes

ABSTRACT

We provide a general framework for the analysis of the capacity scaling properties in mobile ad-hoc networks with heterogeneous nodes and spatial inhomogeneities. Existing analytical studies strongly rely on the assumption that nodes are identical and uniformly visit the entire network space. Experimental data, however, have shown that the mobility pattern of individual nodes is typically restricted over the area, while the overall node density is often largely inhomogeneous, due to prevailing clustering behavior resulting from hot-spots. Such ubiquitous features of realistic mobility processes demand to reconsider the scaling laws for the per-user throughput achievable by the store-carry-forward communication paradigm which provides the foundation of many promising applications of delay tolerant networking. We show how the analysis of the asymptotic capacity of dense mobile ad-hoc networks can be transformed, under mild assumptions, into a Maximum Concurrent Flow (MCF) problem over anassociated Generalized Random Geometric Graph (GRGG). Our methodology allows to identify the scaling laws for a general class of mobile wireless networks, and to precisely determine under which conditions the mobility of nodes can indeed be exploited to increase the per-node throughput. At last we propose a simple, asymptotically optimal, scheduling and routing scheme that achieves the maximum transport capacity of the network.

REFERENCES

• 1: P. Gupta, P.R. Kumar, "The capacity of wireless networks", IEEE Trans. on Information Theory, vol. 46, n.2, pp. 388--404, Mar. 2000
• 2: 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]
• 3: Delay Tolerant Network Research Group: www.dtnrg.org
• 4: A. Chaintreau, P.Hui, J. Crowcroft, C.Diot, R.Gass, J. Scott, "Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms", in Proc. IEEE INFOCOM '06, Barcelona, Spain, April 2006.
• 5: J. Burgess, B.Gallagher, D. Jensen, B.N. Levine, "MaxProp: Routing for Vehicle-Based Disruption-Tolerant Networking", in Proc. IEEE INFOCOM 2006, Barcelona, Spain, April 2006.
• 6: N. Sarafijanovic-Djukic, M. Piorkowski, and M. Grossglauser, "Island Hopping: Efficient Mobility-Assisted Forwarding in Partitioned Networks", IEEE SECON 2006, Reston, VA, Sep. 2006.
• 7: Philo Juang , Hidekazu Oki , Yong Wang , Margaret Martonosi , Li Shiuan Peh , Daniel Rubenstein, Energy-efficient computing for wildlife tracking: design tradeoffs and early experiences with ZebraNet, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 8: W. Zhao , M. Ammar , E. Zegura, A message ferrying approach for data delivery in sparse mobile ad hoc networks, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989483]
• 9: Alex (Sandy) Pentland , Richard Fletcher , Amir Hasson, DakNet: Rethinking Connectivity in Developing Nations, Computer, v.37 n.1, p.78-83, January 2004 [doi>10.1109/MC.2004.1260729]
• 10: S. Toumpis and A.Goldsmith, "Large wireless networks under fading, mobility, and delay constraints", IEEE INFOCOM, Hong Kong, China, Mar. 2004
• 11: A. El Gamal, J.Mammen, B. Prabhakar, and D. Shah, "Throughput-Delay Trade-off in Wireless Networks", IEEE INFOCOM, Hong Kong, China, Mar. 2004
• 12: G. Sharma, R. R.Mazumdar and N. B. Shroff, "Delay and Capacity Trade-offs in Mobile Ad Hoc Networks: A Global Perspective" IEEE INFOCOM, Barcelona, Spain, Apr. 2006
• 13: W.-J.Hsu and A.Helmy, "On Nodal Encounter Patterns in Wireless LAN Traces", in Proc. WiNMee '06, Boston, MA, 2006.
• 14: J. Leguay, T. Friedman, V. Conan, "Evaluating Mobility Pattern Space Routing for DTNs", in Proc. IEEE INFOCOM '06, Barcelona, Spain, April 2006.
• 15: Magdalena Balazinska , Paul Castro, Characterizing mobility and network usage in a corporate wireless local-area network, Proceedings of the 1st international conference on Mobile systems, applications and services, p.303-316, May 05-08, 2003, San Francisco, California [doi>10.1145/1066116.1066127]
• 16: Jong Hee Kang , William Welbourne , Benjamin Stewart , Gaetano Borriello, Extracting places from traces of locations, ACM SIGMOBILE Mobile Computing and Communications Review, v.9 n.3, July 2005 [doi>10.1145/1094549.1094558]
• 17: M.Kim, D.Kotz, S.Kim, "Extracting a mobility model from real user traces", in Proc. IEEE INFOCOM '06, Barcelona, Spain, April 2006.
• 18: S.N. Diggavi, M. Grossglauser, D.N.C. Tse, "Even one-dimensional mobility increases ad hoc wireless capacity", IEEE Trans. on Information Theory, vol. 51, n. 11, pp. 3947--3954, Nov. 2005
• 19: R.M.Moraes, H. R. Sadjadpour and J. J.Garcia-Luna Aceves, "Mobility-Capacity-Delay Trade-off in Wireless Ad Hoc Networks," Elsevier Journal on ad hoc networks, July 2005
• 20: M. Garetto, P. Giaccone, E. Leonardi, "On the Capacity of Ad Hoc Wireless Networks Under General Node Mobility", IEEE Infocom 2007, Anchorage, AK, May 2007
• 21: S. R. Kulkarni, P.Viswanath, "A Deterministic Approach to Throughput Scaling in Wireless Networks," IEEE Trans. on Infornation Theory, vol. 50, no. 6 , pp. 1041--1049, June 2004
• 22: Stavros Toumpis, Capacity bounds for three classes of wireless networks: asymmetric, cluster, and hybrid, Proceedings of the 5th ACM international symposium on Mobile ad hoc networking and computing, May 24-26, 2004, Roppongi Hills, Tokyo, Japan [doi>10.1145/989459.989477]
• 23: Christina Peraki , Sergio D. Servetto, On the maximum stable throughput problem in random networks with directional antennas, Proceedings of the 4th ACM international symposium on Mobile ad hoc networking & computing, June 01-03, 2003, Annapolis, Maryland, USA [doi>10.1145/778415.778426]
• 24: Ulaş C. Kozat , Leandros Tassiulas, Throughput capacity of random ad hoc networks with infrastructure support, Proceedings of the 9th annual international conference on Mobile computing and networking, September 14-19, 2003, San Diego, CA, USA [doi>10.1145/938985.938992]
• 25: Ashish Agarwal , P. R. Kumar, Capacity bounds for ad hoc and hybrid wireless networks, ACM SIGCOMM Computer Communication Review, v.34 n.3, July 2004 [doi>10.1145/1031134.1031143]
• 26: B. Liu, Z. Liu, and D. Towsley, "On the capacity of hybrid wireless networks", IEEE INFOCOM, vol. 2, pp. 1543--1552, San Francisco, CA, Apr. 2003
• 27: M. Penrose, Random Geometric Graphs, Oxford University Press, 2003.
• 28: Yonatan Aumann , Yuval Rabani, An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm, SIAM Journal on Computing, v.27 n.1, p.291-301, Feb. 1998 [doi>10.1137/S0097539794285983]
• 29: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995

INDEX TERMS

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

General Terms:
Design, Performance, Theory

Keywords:
delay tolerant networking, network capacity, routing