Skip to main content
SpringerLink
Log in

A Cost Analysis of Routing Algorithms in Pedestrian-Based Delay Tolerant Networks

  • Conference paper
  • First Online:
Advances in Networked-Based Information Systems (NBiS 2020)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 1264))

Included in the following conference series:

  • 887 Accesses

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 model 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 models on the city’s road network. Moreover, we introduce roadside units located in the city, which play a role in the distributed message cache. We assume Random walk and Lévy walk as pedestrian mobility models and Epidemic, Spray and Wait, and PRoPHET as the routing protocols and analyze the influence of roadside units, pedestrian walk patterns, and the routing protocols of opportunistic communication on costs of message delivery. Our simulation results clarify the difference in routing protocols regarding network costs. We also discuss a trade-off between network cost and message delivery ratio according to the results.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 219.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 279.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. 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)

    Google Scholar 

  2. 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)

    Google Scholar 

  3. 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

    Article  MATH  Google Scholar 

  4. Broch, J., Maltz, D.A., Johnson, D.B., Hu, Y.C., Jetcheva, J.: A performance comparison of multi-hop wireless ad hoc network routing protocols. In: Proceedings of the 4th Annual ACM/IEEE International Conference on Mobile Computing and Networking, MobiCom 1998, p. 8597. Association for Computing Machinery, New York (1998). https://doi.org/10.1145/288235.288256

  5. 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)

    Article  Google Scholar 

  6. 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)

    Google Scholar 

  7. Dolev, S., Schiller, E., Welch, J.L.: Random walk for self-stabilizing group communication in ad hoc networks. IEEE Trans. Mobile Comput. 5(7), 893–905 (2006). https://doi.org/10.1109/TMC.2006.104

    Article  Google Scholar 

  8. 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

    Article  MathSciNet  MATH  Google Scholar 

  9. 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)

    Article  Google Scholar 

  10. 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

  11. Helgason, Ó., Kouyoumdjieva, S.T., Karlsson, G.: Opportunistic communication and human mobility. IEEE Trans. Mob. Comput. 13(7), 1597–1610 (2014)

    Article  Google Scholar 

  12. Hyytia, E., Lassila, P., Virtamo, J.: Spatial node distribution of the random waypoint mobility model with applications. IEEE Trans. Mob. Comput. 5(6), 680–694 (2006)

    Article  Google Scholar 

  13. Lévy, P.: Théorie de L’addition des Variables Aléatoires. Gauthier-Villars, Paris (1937)

    MATH  Google Scholar 

  14. 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

    Article  Google Scholar 

  15. 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)

    Google Scholar 

  16. 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)

    Google Scholar 

  17. Spaho, E., Bylykbashi, K., Barolli, L., Takizawa, M.: Routing in a DTN: performance evaluation for random waypoint and steady state random waypoint using NS3 simulator. In: Advances on P2P, Parallel, Grid, Cloud and Internet Computing, 3PGCIC 2018. Springer, Cham (2020)

    Google Scholar 

  18. 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)

    Article  Google Scholar 

  19. Sueda, T., Hayashibara, N.: Human mobility and message caching in opportunistic networks. In: Advances in Internet, Data and Web Technologies, EIDWT 2020. Springer, Kitakyushu (2020)

    Google Scholar 

  20. Vahdat, A., Becker, D.: Epidemic routing for partially-connected ad hoc networks. Technical report CS-2000-06, Duke University (2000)

    Google Scholar 

  21. 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.2008807

  22. 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)

    Article  Google Scholar 

  23. 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)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Graduate School of Frontier Informatics, Kyoto Sangyo University, Kyoto, Japan

    Tomoyuki Sueda

  2. Faculty of Computer Science and Engineering, Kyoto Sangyo University, Kyoto, Japan

    Naohiro Hayashibara

Authors
  1. Tomoyuki Sueda
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Naohiro Hayashibara
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Naohiro Hayashibara .

Editor information

Editors and Affiliations

  1. Department of Information and Communication Engineering, Faculty of Information Engineering, Fukuoka Institute of Technology, Fukuoka, Japan

    Leonard Barolli

  2. Department of Electrical and Computer Engineering, University of Victoria, Victoria, BC, Canada

    Kin Fun Li

  3. Faculty of Business Administration, Rissho University, Tokyo, Japan

    Tomoya Enokido

  4. Department of Advanced Sciences, Hosei University, Tokyo, Japan

    Makoto Takizawa

Rights and permissions

Reprints and permissions

Copyright information

© 2021 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Sueda, T., Hayashibara, N. (2021). A Cost Analysis of Routing Algorithms in Pedestrian-Based Delay Tolerant Networks. In: Barolli, L., Li, K., Enokido, T., Takizawa, M. (eds) Advances in Networked-Based Information Systems. NBiS 2020. Advances in Intelligent Systems and Computing, vol 1264. Springer, Cham. https://doi.org/10.1007/978-3-030-57811-4_8

Download citation

Publish with us

Policies and ethics

Search

Navigation