Developing a Model to Optimize Maximum Coverage of Roadside Units Placement in Vehicular Ad–hoc Network for Intelligent Transportation System

Document Type : Original Article

Authors

1 Professor, Department of Industrial management, Faculty of management, University of Tehran.

2 Ph.D. Candidate, Department of Industrial management, Alborz Campus, University of Tehran.

3 Ph.D, Department of Industrial management, Faculty of management, University of Tehran.

Abstract

Roadside units are crucial elements of intelligent transportation systems that provide vehicle–vehicle and vehicle–equipment information communication. Due to the high cost of installation, the deployment of roadside units is the most critical. Aim of this study is developing a model to optimize of roadside units placement to achieve maximum coverage. A multi–objective mathematical model presented, based on the three main parameters. These parameters are traffic volume, incident rate and adjacency to important centers, which determine for alternative points. The maximum coverage problem is NP–hard. Consequently, conventional mathematical methods are not accurate for large scale problem. A meta–heuristic method based on the greedy algorithm was developed which conciders marking points as definitive–select or non–selectable. Result of the model were evaluated through testing of three scenarios, 200, 500 and 1000 meters coverage in District 5 of Tehran by using MATLAB and the best one, 1000 meters was chosen with 71% coverage. Observations showed the effect of various parameters such as equipment coverage radius, number of equipment and budget on the results of distribution. This algorithm makes it possible to solve the problem on a large scale by using the geolocation of the candidate points.

Keywords

Main Subjects

References

  1. Abdulkadhim, F. G., Yi, Z., Onaizah, A. N., Rabee, F., & Al‑Muqarm, A. M. A. (2021). Optimizing the Roadside Unit Deployment Mechanism in VANET with Efficient Protocol to Prevent Data Loss. Wireless Personal Communications, 2021.
  2. Alam, M., Ara Shakil, K., & Khan, S. (2020). Internet of Things (IoT) Concepts and Applications. Springer Nature Switzerland AG.
  3. Assencio, D., (2017). The intersection area of two circles, available at: https://diego.assencio.com (accessed 25 March 2022).
  4. Azees, M., Vijayakumar, P., & Deboarh, L. J. (2017). EAAP: Efficient Anonymous Authentication with Conditional Privacy–Preserving Scheme for Vehicular Ad Hoc Networks. IEEE Transactions on Intelligent Transportation Systems, 18(9), 2467–2476.
  5. Chaabene, S. B., Yeferny, T., & Yahia, S. B. (2021). A roadside unit deployment framework for enhancing transportation services in Maghrebian cities. Concurrency and Computation: Practice and Experience, 33(1), 1–17.
  6. Chandu, P., D. (2015). Big Step Greedy Heuristic for Maximum Coverage Problem. International Journal of Computer Applications, 125(7), 19-24.
  7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. & Stein, C. (2003). Introduction to algorithms, 3rd edition, London, England, The MIT press.
  8. Danaiefard, H., Alvani, M., & Azar, A. (2019). Quantitative research methodology in management. Tehran: Saffar Publications (In Persian).
  9. Daneshvar, A., Homayounfar, M., Nahavandi, B., & Salahi, F. (2021). A Multi–objective Approach to the Problem of Subset Feature Selection Using Meta–heuristic Methods. The Journal of Industrial Management Journal, 13(2), 278– 299 (In Persian).
  10. Farsi, A., & Szczechowiak, P. (2014). Optimal deployment of Road Side Units in urban environments. 3rd International Conference on Connected Vehicles and Expo, ICCVE, Vienna, Australia, 2014, Nonember 3–7, 815–820.
  11. Fogue, M., Sanquesa, J. A., Martinez, F. J., & Marquez–Barja, J. M. (2018). Improving Roadside Unit Deployment in Vehicular Networks by Exploiting Genetic Algorithms, Applied Sciences, 8(1), 1–21.
  12. Fröhlich, N., Maier, A., & Hamacher, H. W. (2020). Covering edges in networks. Networks, 75(3), 278–290.
  13. Giuffrè, T., Trubia, S., Canale, A., & Severino, A. (2017). Automated Vehicle: a Review of Road Safety Implications as Driver of Change. 27th CARSP Conference, Toronto, Canada, 2017, June 18–21.
  14. Heo, J., Kang, B., Yang, J., Paek, J., & Bahk, S. (2019). Performance–Cost Tradeoff of Using Mobile Roadside Units for V2X Communication. IEEE Transactions on Vehicular Technology, 68(9), 9049–9059.
  15. Isaksson, J., Harjunkoski, I., & Sand, G. (2018). The impact of digitalization on the future of control and operations. Computers and Chemical Engineering, 114, 122–129.
  16. Jiang, L., Molnár, T. G., & Orosz, G. (2021). On the deployment of V2X roadside units for traffic prediction. Transportation Research Part C, 129, 1–14.
  17. Jo, Y., Jang, J., Park, S., & Oh, C. (2021). Connected vehicle–based road safety information system (CROSS): Framework and evaluation. Accident Analysis and Prevention, 151, 1–12.
  18. Kimura, T., Saito, H., & Honda, H. (2018). Optimal transmission range for V2I communications on congested highways. 28th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, PIMRC, Montreal, Canada, 2017, October 8–13, 1–7.
  19. Krasniqi, X., & Hajrizi, E. (2016). Use of IoT Technology to Drive the Automotive Industry from Connected to Full Autonomous Vehicles. IFAC–PapersOnLine, 49(29), 269–274.
  20. Lan, G., DePuy, G. W. & Whitehouse, G. E. (2007). Effective and simple heuristic for the set covering problem, European Journal of Operational Research, 176, 1387-1403.
  21. Li, S., Xu, L. Da, & Zhao, S. (2015). The internet of things: a survey. Information Systems Frontiers, 17, 243–259.
  22. Liang, Y., Wu, Z., & Hu, J. (2020). Road side unit location optimization for optimum link flow determination. ComputerAided Civil and Infrastructure Engineering, 35, 61–79.
  23. Makkawi, A., Daher, R., & Rizk, R. (2015). RSUs placement using cumulative weight based method for urban and rural roads. 7th International Workshop on Reliable Networks Design and Modeling, RNDM, Munich, Germany 2015, October 5–7, 307–313.
  24. Maria, E., Budiman, E., Haviluddin and Taruk, M. (2020), “Measure distance locating nearest public facilities using Haversine and Euclidean Methods”, Journal of Physics: Conference Series, 1450(1).
  25. Mohaghar, A., Ariaee, S. (2017). Locating using Geographical Information System and Weighted Maximal Covering Model. The Journal of Indusrtial Management Perspective, 7(2), 9-32 (In Persian).
  26. Mortazavi, S. & Seif Barghy, M. (2018). Two-Objective Modeling of Location-Allocation Problem in a Green Supply Chain Considering Transportation System and CO2 Emission. The Journal of Indusrtial Management Perspective, 8(1), 163-185. (In Persian)
  27. Naval S., S. (2019). Variation In Greedy Approach To Set Covering Problem. S. Thesis, University of Windsor, Ontario, Canada.
  28. Nikbakhsh, E., Zegordi, S.H. (2014). Hub Arc Covering Location Problem under Disruption. The Journal of Indusrtial Management Perspective, 4(1), 9-29. (In Persian)
  29. Outay, F., Kammoun, F., Kaisser, F., & Atiquzzaman, M. (2017). Towards safer roads through cooperative hazard awareness and avoidance in connected vehicles. Proceedings, 31st IEEE International Conference on Advanced Information Networking and Applications Workshops, WAINA, Taipei, Taiwan, 2017, March 27–29, 208–215.
  30. Peng, S., Pal, S., & Huang, L. (2020). Principles of Internet of Things (IoT) Ecosystem: Insight Paradigm. Springer Nature Switzerland AG.
  31. Pourkiani, M., Jabbehdari, S., & Khademzadeh, A. (2016). Vehicular Networks : A Survey on Architecture. Journal of Advances in Computer Engineering and Technology, 2(3), 43–53.
  32. Reis, A. B., Sargento, S. & Tonguz, O. K. (2018). Smarter Cities with Parked Cars as Roadside Units, IEEE Transactions on Intelligent Transportation Systems, 19(7), 2338–2352.
  33. Rios, M., Marianov, V., & Pérez, M. (2015). Locating fixed roadside units in a bus transport network for maximum communications probability, Transportation Research Part C, 53, 35–47.
  34. Salehikia, Z., & Salehinamad, M. (2017). Optimal Deployment of Roadside Units for Vehicular Networks Based on data exchange time reducing, 2nd National Conference on Intelligent Industrial Robots, Ahar, Iran, 2017, November 23. (In Persian).
  35. Sheikh, M. S., & Liang, J. (2019). A Comprehensive Survey on VANET Security Services in Traffic Management System. Wireless Communications and Mobile Computing, 2019, 1–23.
  36. Shi, Y., Lv, L., Yu, H., Yu, L., & Zhang, Z. (2020). A center–rule–based neighborhood search algorithm for roadside units deployment in emergency scenarios. Mathematics, 8(10), 1–27.
  37. Snyder, S. A., & Haight, R. G. (2016). Application of the Maximal Covering Location Problem to Habitat Reserve Site Selection: A Review. International Regional Science Review, 39(1),
  38. Trullols, O. Fiore, M. Casetti, C. Chiasserini, C.F. & Barcelo, O. J. M. (2010). Planning roadside infrastructure for information dissemination in intelligent transportation systems, Computer Communication. 33(4), 432–442.
  39. Xue, L., Yang, Y., & Dong, D. (2017). Roadside Infrastructure Planning Scheme for the Urban Vehicular Networks. Transportation Research Procedia, 25, 1380–1396.

Files

Share

How to cite

Statistics