Abstract
Opportunistic communication is one of the key technologies for advertisement, information sharing, disaster evacuation guidance in delay-tolerant networks (DTNs), vehicular ad hoc networks (VANETs) and so on. The efficiency of message delivery in opportunistic communication is correlated to the routing protocols and the movement pattern of mobile entities. In this paper, we focus on message delivery based on opportunistic communication by pedestrians who move based on Lévy walk and Random walk movement patterns on the road network of a city. Moreover, we introduce roadside units located in the city, which play a role in the distributed message cache. So, we analyze the influence of roadside units, pedestrian walk patterns and the routing protocols of opportunistic communication on message delivery. We assume Random walk and Lévy walk as pedestrian mobility models and Epidemic, Spray and Wait and PRoPHET as the routing protocols. Our simulation results clarify the difference of routing protocols and show that the roadside units have a significant impact on message delivery with a small number of pedestrians.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Aleliunas, R., Karp, R.M., Lipton, R.J., Lovasz, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science (SFCS 1979), pp. 218–223 (1976)
Alzoubi, K.M., Wan, P.J., Frieder, O.: Message-optimal connected dominating sets in mobile ad hoc networks. In: Proceedings of the 3rd ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc 2002, pp. 157–164. ACM, New York (2002). https://doi.org/10.1145/513800.513820
Baldoni, R., Beraldi, R., Quema, V., Querzoni, L., Tucci-Piergiovanni, S.: Tera: Topic-based event routing for peer-to-peer architectures. In: Proceedings of the 2007 International Conference on Distributed Event-based Systems, pp. 2–13 (2007)
Birand, B., Zafer, M., Zussman, G., Lee, K.W.: Dynamic graph properties of mobile networks under levy walk mobility. In: Proceedings of the 2011 IEEE Eighth International Conference on Mobile Ad-Hoc and Sensor Systems, MASS 2011, pp. 292–301. IEEE Computer Society, Washington, DC (2011). https://doi.org/10.1109/MASS.2011.36
Bisnik, N., Abouzeid, A.A.: Optimizing random walk search algorithms in P2P networks. Comput. Netw. 51(6), 1499–1514 (2007). https://doi.org/10.1016/j.comnet.2006.08.004
Buldyrev, S.V., Goldberger, A.L., Havlin, S., Peng, C.K., Simons, M., Stanley, H.E.: Generalized lévy-walk model for dna nucleotide sequences. Phys. Rev. E 47(6), 4514–4523 (1993)
Desta, M.S., Hyytiä, E., Keränen, A., Kärkkäinen, T., Ott, J.: Evaluating (Geo) content sharing with the one simulator. In: Proceedings of the 14th ACM Symposium Modeling, Analysis and Simulation of Wireless and Mobile Systems (MSWiM) (2013)
Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mobi. Comput. 5(7), 893–905 (2006). https://doi.org/10.1109/TMC.2006.104
Draief, M., Ganesh, A.: A random walk model for infection on graphs: Spread of epidemics & rumours with mobile agents. Discrete Event Dyn. Syst. 21(1), 41–61 (2011). https://doi.org/10.1007/s10626-010-0092-5
Edwards, A.M., Phillips, R.A., Watkins, N.W., Freeman, M.P., Murphy, E.J., Afanasyev, V., Buldyrev, S.V., da Luz, M.G.E., Raposo, E.P., Stanley, H.E., Viswanathan, G.M.: Revisiting lévy flight search patterns of wandering albatrosses, bumblebees and deer. Nature 449, 1044–1048 (2007)
Fujihara, A., Miwa, H.: Homesick lévy walk and optimal forwarding criterion of utility-based routing under sequential encounters. In: 2013 Proceedings of the Internet of Things and Inter-cooperative Computational Technologies for Collective Intelligence 2013, pp. 207–231 (2013)
Grasic, S., Davies, E., Lindgren, A., Doria, A.: The evolution of a DTN routing protocol - PRoPHETv2. In: Proceedings of the 6th ACM Workshop on Challenged Networks, CHANTS 2011, pp. 27–30. ACM, New York (2011). https://doi.org/10.1145/2030652.2030661
Helgason, Ó., Kouyoumdjieva, S.T., Karlsson, G.: Opportunistic communication and human mobility. IEEE Trans. Mob. Comput. 13(7), 1597–1610 (2014)
Ikeda, S., Kubo, I., Yamashita, M.: The hitting and cover times of random walks on finite graphs using local degree information. Theor. Comput. Sci. 410(1), 94–100 (2009)
Kuhn, F., Wattenhofer, R.: Constant-time distributed dominating set approximation. In: Proceedings of the Twenty-second Annual Symposium on Principles of Distributed Computing, PODC 2003, pp. 25–32. ACM, New York (2003). https://doi.org/10.1145/872035.872040
Lévy, P.: Théorie de L’addition des Variables Aléatoires. Gauthier-Villars (1937)
Mizumoto, N., Abe, M.S., Dobata, S.: Optimizing mating encounters by sexually dimorphic movements. J. R. Soc. Interface 14(130), 20170086 (2017)
Nonaka, Y., Ono, H., Sadakane, K., Yamashita, M.: The hitting and cover times of metropolis walks. Theor. Comput. Sci. 411(16–18), 1889–1894 (2010)
Rhee, I., Shin, M., Hong, S., Lee, K., Kim, S.J., Chong, S.: On the levy-walk nature of human mobility. IEEE/ACM Trans. Netw. 19(3), 630–643 (2011). https://doi.org/10.1109/TNET.2011.2120618
Shinki, K., Hayashibara, N.: Resource exploration using lévy walk on unit disk graphs. In: The 32nd IEEE International Conference on Advanced Information Networking and Applications, AINA-2018. Krakow, Poland (2018)
Shinki, K., Nishida, M., Hayashibara, N.: Message dissemination using lévy flight on unit disk graphs. In: The 31st IEEE International Conference on Advanced Information Networking and Applications, AINA 2017, Taipei, Taiwan ROC (2017)
Spyropoulos, T., Psounis, K., Raghavendra, C.S.: Efficient routing in intermittently connected mobile networks: the multiple-copy case. IEEE/ACM Trans. Netw. 14, 77–90 (2008)
Sueda, T., Hayashibara, N.: Opportunistic communication by pedestrians with roadside units as message caches. In: Proceedings of the 22nd International Conference on Network-Based Information Systems, NBiS 2019, pp. 167–177 (2013)
Thejaswini, M., Rajalakshmi, P., Desai, U.B.: Novel sampling algorithm for human mobility-based mobile phone sensing. IEEE Internet Things J. 2(3), 210–220 (2015)
Vahdat, A., Becker, D.: Epidemic routing for partially-connected ad hoc networks. Technical report. CS-2000-06, Duke University (2000)
Valler, N.C., Prakash, B.A., Tong, H., Faloutsos, M., Faloutsos, C.: Epidemic spread in mobile ad hoc networks: determining the tipping point. In: Proceedings of the 10th International IFIP TC 6 Conference on Networking - volume Part I, NETWORKING 2011, pp. 266–280. Springer-Verlag, Heidelberg (2011). http://dl.acm.org/citation.cfm?id=2008780.20088
Viswanathan, G.M., Afanasyev, V., Buldyrev, S.V., Murphy, E.J., Prince, P.A., Stanley, H.E.: Lévy flight search patterns of wandering albatrosses. Nature 381, 413–415 (1996)
Yang, X.S.: Cuckoo search via Lévy flights. In: Proceedings of World Congress on Nature & Biologically Inspired Computing, NaBIC 2009, pp. 210–214 (2009)
Yang, X.S.: Firefly algorithm, lévy flights and global optimization. Research and Development in Intelligent Systems XXVI, pp. 209–218 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Sueda, T., Hayashibara, N. (2020). Human Mobility and Message Caching in Opportunistic Networks. In: Barolli, L., Okada, Y., Amato, F. (eds) Advances in Internet, Data and Web Technologies. EIDWT 2020. Lecture Notes on Data Engineering and Communications Technologies, vol 47. Springer, Cham. https://doi.org/10.1007/978-3-030-39746-3_41
Download citation
DOI: https://doi.org/10.1007/978-3-030-39746-3_41
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-39745-6
Online ISBN: 978-3-030-39746-3
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)