A mobility model for pedestrian content distribution

ABSTRACT

Mobile communication devices may be used for spreading multimedia data without support of an infrastructure. Such a scheme, where the data is carried by people walking around and relayed from device to device by means of short range radio, could potentially form a public content distribution system that spans vast urban areas. The transport mechanism is the flow of people and it can be studied but not engineered. The question addressed in this paper is how well pedestrian content distribution may work. We answer this question by modeling the mobility of people moving around in a city, constrained by a given topology. Our contributions are both the queuing analytic model that captures the flow of people and the results on the feasibility of pedestrian content distribution. Furthermore, we discuss possible extensions to the mobility model to capture speed-distance relations that emerge in dense crowds.

REFERENCES

• 1: M. Izal, G. Urvoy-Keller, E. Biersack, P. Felber, A. A. Hamra, and L. Garćes-Erice, "Dissecting BitTorrent: Five Months in a Torrent's Lifetime," Proc. Passive and Active Measurements Conference, Antibes Juan-les-Pins, France, 2004.
• 2: S. M. Hedetniemi, S. T. Hedetniemi and A. Liestman, "A Survey of Gossiping and Broadcasting in Communication Networks," Networks, vol. 18, no. 4, pp. 319--349, 1988.
• 3: Delay Tolerant Networking Research Group. {Online}. Available: http://www.dtnrg.org/wiki. {Accessed Jan. 20, 2009}.
• 4: A. Vahdat and D. Becker, "Epidemic Routing for Partially Connected Ad Hoc Networks," Tech. rep. CS-200006, Duke University, NC, 2000.
• 5: Maria Papadopouli , Henning Schulzrinne, Effects of power conservation, wireless coverage and cooperation on data dissemination among mobile devices, Proceedings of the 2nd ACM international symposium on Mobile ad hoc networking & computing, October 04-05, 2001, Long Beach, CA, USA [doi>10.1145/501431.501433]
• 6: Julian Chesterfield , Pablo Rodriguez, DeltaCast: efficient file reconciliation in wireless broadcast systems, Proceedings of the 3rd international conference on Mobile systems, applications, and services, June 06-08, 2005, Seattle, Washington [doi>10.1145/1067170.1067181]
• 7: A. El Fawal, J.-Y. Le Boudec, K. Salamatian, "Self-Limiting Epidemic Forwarding," Tech. rep. LCA-REPORT-2006-126, EPFL, Switzerland, 2006.
• 8: Wenrui Zhao , Mostafa Ammar , Ellen Zegura, Multicasting in delay tolerant networks: semantic models and routing algorithms, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.268-275, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080145]
• 9: Sewook Jung , Uichin Lee , Alexander Chang , Dae-Ki Cho , Mario Gerla, BlueTorrent: Cooperative Content Sharing for Bluetooth Users, Proceedings of the Fifth IEEE International Conference on Pervasive Computing and Communications, p.47-56, March 19-23, 2007 [doi>10.1109/PERCOM.2007.11]
• 10: G. Karlsson, V. Lenders, and M. May, "Delay-Tolerant Broadcasting," IEEE Trans. Broadcasting, vol. 53, no. 2, pp. 369--381, 2007.
• 11: T. Camp, J. Boleng, and V. Davies, "A Survey of Mobility Models for Ad Hoc Network Research," Wireless Communications and Mobile Computing, vol. 2, no. 5, pp. 483--502, 2002.
• 12: Esa Hyytia , Pasi Lassila , Jorma Virtamo, Spatial Node Distribution of the Random Waypoint Mobility Model with Applications, IEEE Transactions on Mobile Computing, v.5 n.6, p.680-694, June 2006 [doi>10.1109/TMC.2006.86]
• 13: J.-Y. Le Boudec and M. Vojnovic, "Perfect Simulation and Stationarity of a Class of Mobility Models," Proc. IEEE INFOCOM, Miami, FL, 2005.
• 14: Thrasyvoulos Spyropoulos , Konstantinos Psounis , Cauligi S. Raghavendra, Performance analysis of mobility-assisted routing, Proceedings of the 7th ACM international symposium on Mobile ad hoc networking and computing, May 22-25, 2006, Florence, Italy [doi>10.1145/1132905.1132912]
• 15: F. Bai, N. Sadagopan, B. Krishnamachari, and Ahmed Helmy, "Modeling Path Duration Distributions in MANETs and their Impact on Reactive Routing Protocols," IEEE Journal on Selected Areas of Comm. (JSAC), vol. 22, no. 7, pp. 1357--1373, 2004.
• 16: K. K. Leung, W. A. Massey and W. Whitt, "Traffic Models for Wireless Communication Networks," IEEE Journal on Selected Areas in Communication, vol. 12, No. 8, pp. 1353--1364, 1994.
• 17: R. Groenevelt , E. Altman , P. Nain, Relaying in mobile ad hoc networks: the Brownian motion mobility model, Wireless Networks, v.12 n.5, p.561-571, September 2006 [doi>10.1007/s11276-006-6535-0]
• 18: Denizhan N. Alparslan , Khosrow Sohraby, A generalized random mobility model for wireless ad hoc networks and its analysis: one-dimensional case, IEEE/ACM Transactions on Networking (TON), v.15 n.3, p.602-615, June 2007 [doi>10.1109/TNET.2007.893235]
• 19: Wing Ho Yuen , Roy D. Yates , Chi Wan Sung, Effect of node mobility on highway mobile infostation networks, Proceedings of the 6th ACM international workshop on Modeling analysis and simulation of wireless and mobile systems, September 19-19, 2003, San Diego, CA, USA [doi>10.1145/940991.941006]
• 20: CRAWDAD: A Community Resource for Archiving Wireless Data at Dartmouth. {Online}. Available: http://crawdad.cs.dartmouth.edu. {Accessed Jan. 20, 2009}.
• 21: MobiLib: Community-Wide Library of Mobility and Wireless Networks Measurements. {Online}. Accessed: http://nile.usc.edu/MobiLib. {Accessed Jan. 20, 2009}.
• 22: M. Kim, D. Kotz, and S. Kim, "Extracting a Mobility Model from Real User Traces," Proc. IEEE INFOCOM, Barcelona, Spain, 2006.
• 23: Thomas Karagiannis , Jean-Yves Le Boudec , Milan Vojnović, Power law and exponential decay of inter contact times between mobile devices, 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.1287875]
• 24: Pan Hui , Augustin Chaintreau , James Scott , Richard Gass , Jon Crowcroft , Christophe Diot, Pocket switched networks and human mobility in conference environments, Proceedings of the 2005 ACM SIGCOMM workshop on Delay-tolerant networking, p.244-251, August 26-26, 2005, Philadelphia, Pennsylvania, USA [doi>10.1145/1080139.1080142]
• 25: A. Chaintreau, P. Hui, J. Crowcroft, C. Diot, Richard Gass and James Scott, "Impact of Human Mobility on the Design of Opportunistic Forwarding Algorithms," Proc. IEEE INFOCOM, Barcelona, Spain, 2006.
• 26: W. Hsu, T. Spyropoulos, K. Psounis, and A. Helmy, "Modeling Time-Variant User Mobility in Wireless Mobile Networks," Proc. IEEE INFOCOM, Anchorage, AL, 2007.
• 27: Liam McNamara , Cecilia Mascolo , Licia Capra, Media sharing based on colocation prediction in urban transport, Proceedings of the 14th ACM international conference on Mobile computing and networking, September 14-19, 2008, San Francisco, California, USA [doi>10.1145/1409944.1409953]
• 28: Kumiko Maeda , Kazuki Sato , Kazuki Konishi , Akiko Yamasaki , Akira Uchiyama , Hirozumi Yamaguchi , Keiichi Yasumoto , Teruo Higashino, Getting urban pedestrian flow from simple observation: realistic mobility generation in wireless network simulation, Proceedings of the 8th ACM international symposium on Modeling, analysis and simulation of wireless and mobile systems, October 10-13, 2005, Montréal, Quebec, Canada [doi>10.1145/1089444.1089471]
• 29: V. Vukadinovic, O. R. Helgason, and G. Karlsson, "On the performance of pedestrian content distribution," Tech. rep. TRITA-EE 2008:035, Royal Institute of Technology, Stockholm, Sweden.
• 30: A. Varga, "The OMNeT++ Discrete Event Simulation System," Proc. European Simulation Multiconference, Prague, Czech Republic, 2001.
• 31: D. Helbing and P. Molnar, "Social Force Model for Pedestrian Dynamics," Physical Review E, vol. 51, no. 5, pp. 4282--4286, 1995.
• 32: D. Helbing, M. Treiber, and A. Kesting, "Understanding Interarrival and Interdeparture Time Statistics from Interactions in Queuing Systems," Physica A, vol. 363, no. 1, pp. 62--72, 2006.

INDEX TERMS

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

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.2 Network Protocols

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
broadcast, content distribution, delay-tolerant networks, mobility modeling, multicast, queuing analysis