Bus*: An efficient algorithm for finding Moving K-Nearest Neighbors (MKNNs) with capacity constraints

Authors

  • Saad Aljubayrin Shaqra University, Saudi Arabia

DOI:

https://doi.org/10.12928/commicast.v5i1.9955

Keywords:

A* , Alogarithm , Bus Path , Moving k-Nearest , Neighbor , Optimization

Abstract

The large-scale and increasing use of transportation systems in various applications is expected to become an important component of communications networks beyond 5G and 6G in the next decade. To effectively support the massive deployment of transportation systems, reliable, secure, and cost-effective wireless connectivity is required. Communication networks are very important for vehicles that act as mobile user equipment. Although communications networks offer a promising way for cars to stay connected, it isn't easy to make transportation work well. This paper aims to present a new and interesting problem: the finding of the moving K-nearest neighbors (MKNNs), where each neighbor has a capacity limit. Specifically, considering a set of moving objects with different capacity constraints distributed in the road network, query objects with a certain load, find the optimal set of neighbors where the total available capacity is equal to or greater than the load of the query object, and the total travel time of the optimal set to reach the query object is minimized. This problem has significant applications in our lives. For example, it can help bus operating companies find other optimal bus trains in operation to move to the location of the damaged bus and transport its passengers to their destinations. In contrast, the total travel time of the optimal train is minimized. This paper uses previous research methods with a qualitative descriptive approach from sources that researchers found. The results of this research serve as material for proposing new algorithms that are effective for solving problems in real-time when using real data sets

References

Ahmed, M., Khan, W. U., Ihsan, A., Li, X., Li, J., & Tsiftsis, T. A. (2022). Backscatter Sensors Communication for 6G Low-Powered NOMA-Enabled IoT Networks Under Imperfect SIC. IEEE Systems Journal, 16(4), 5883–5893. https://doi.org/10.1109/JSYST.2022.3194705

Ahmed, M., Raza, S., Mirza, M. A., Aziz, A., Khan, M. A., Khan, W. U., Li, J., & Han, Z. (2022). A survey on vehicular task offloading: Classification, issues, and challenges. Journal of King Saud University - Computer and Information Sciences, 34(7), 4135–4162. https://doi.org/10.1016/j.jksuci.2022.05.016

Ali, Z., Farooq, W., Khan, W. U., Qureshi, M., & Sidhu, G. A. S. (2021). Artificial intelligence techniques for rate maximization in interference channels. Physical Communication, 47. https://doi.org/10.1016/j.phycom.2021.101294

Ali, Z., Khan, W. U., Ihsan, A., Waqar, O., Sidhu, G. A. S., & Kumar, N. (2021). Optimizing Resource Allocation for 6G NOMA-Enabled Cooperative Vehicular Networks. IEEE Open Journal of Intelligent Transportation Systems, 2, 269–281. https://doi.org/10.1109/OJITS.2021.3107347

Ali, Z., Khan, W. U., Sardar Sidhu, G. A., K, N., Li, X., Kwak, K. S., & Bilal, M. (2022). Fair power allocation in cooperative cognitive systems under NOMA transmission for future IoT networks. Alexandria Engineering Journal, 61(1), 575–583. https://doi.org/10.1016/j.aej.2021.04.107

Aljubayrin, S., He, Z., & Zhang, R. (2015). Skyline trips of multiple POIs categories. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 9050, 189–206. https://doi.org/10.1007/978-3-319-18123-3_12

Aljubayrin, S., Qi, J., Jensen, C. S., Zhang, R., He, Z., & Wen, Z. (2015). The safest path via safe zones. Proceedings - International Conference on Data Engineering, 2015-May, 531–542. https://doi.org/10.1109/ICDE.2015.7113312

Asif, M., Ihsan, A., Khan, W. U., Ranjha, A., Zhang, S., & Wu, S. X. (2023). Energy-Efficient Beamforming and Resource Optimization for AmBSC-Assisted Cooperative NOMA IoT Networks. IEEE Internet of Things Journal, 10(14), 12434–12448. https://doi.org/10.1109/JIOT.2023.3247021

Assegaff, S. B., & Pranoto, S. O. (2020). Price Determines Customer Loyalty in Ride-Hailing Services. American Journal of Humanities and Social Sciences Research, 3.

Athitsos, V., Alon, J., & Sclaroff, S. (2005). Efficient nearest neighbor classification using a cascade of approximate similarity measures. Proceedings - 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, CVPR 2005, I, 486–493. https://doi.org/10.1109/CVPR.2005.141

Basu, S., Karki, M., Ganguly, S., DiBiano, R., Mukhopadhyay, S., & Nemani, R. (2015). Learning sparse feature representations using probabilistic quadtrees and Deep Belief Nets. 23rd European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, ESANN 2015 - Proceedings, 367–372. https://www.scopus.com/inward/record.uri?eid=2-s2.0-84961832113&partnerID=40&md5=7d6cf0813cb5c9ea539809d7428b1907

Dijkstra, E. W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1), 269–271. https://doi.org/10.1007/BF01386390

Duch, A., & Martinez, C. (2005). Improving the Performance of Multidimensional Search Using Fingers. ACM Journal of Experimental Algorithmics, 10, 2.4. https://doi.org/10.1145/1064546.1180615

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100–107. https://doi.org/10.1109/TSSC.1968.300136

Hasan, T., Malik, J., Bibi, I., Khan, W. U., Al-Wesabi, F. N., Dev, K., & Huang, G. (2023). Securing Industrial Internet of Things Against Botnet Attacks Using Hybrid Deep Learning Approach. IEEE Transactions on Network Science and Engineering, 10(5), 2952–2963. https://doi.org/10.1109/TNSE.2022.3168533

Hautamäki, V., Kärkkäinen, I., & Fränti, P. (2004). Outlier detection using k-nearest neighbour graph. Proceedings - International Conference on Pattern Recognition, 3, 430–433. https://doi.org/10.1109/ICPR.2004.1334558

Huang, X., Jensen, C. S., Lu, H., & Šaltenis, S. (2007). S-GRID: A versatile approach to efficient query processing in spatial networks. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 4605 LNCS, 93–111. https://doi.org/10.1007/978-3-540-73540-3_6

Ihsan, A., Chen, W., Asif, M., Khan, W. U., Wu, Q., & Li, J. (2022). Energy-Efficient IRS-Aided NOMA Beamforming for 6G Wireless Communications. IEEE Transactions on Green Communications and Networking, 6(4), 1945–1956. https://doi.org/10.1109/TGCN.2022.3209617

Ihsan, A., Chen, W., Khan, W. U., Wu, Q., & Wang, K. (2023). Energy-Efficient Backscatter Aided Uplink NOMA Roadside Sensor Communications Under Channel Estimation Errors. IEEE Transactions on Intelligent Transportation Systems, 24(5), 4962–4974. https://doi.org/10.1109/TITS.2023.3240159

Jameel, F., Khan, W. U., Shah, S. T., & Ristaniemi, T. (2019). Towards intelligent IoT networks: Reinforcement learning for reliable backscatter communications. 2019 IEEE Globecom Workshops, GC Wkshps 2019 - Proceedings. https://doi.org/10.1109/GCWkshps45667.2019.9024401

Jan, M., Soomro, S. A., & Ahmad, N. (2017). Impact of Social Media on Self-Esteem. European Scientific Journal, ESJ, 13(23). https://doi.org/10.19044/esj.2017.v13n23p329

Jensen, C. S., Kolář, J., Pedersen, T. B., & Timko, I. (2003). Nearest neighbor queries in road networks. GIS: Proceedings of the ACM International Symposium on Advances in Geographic Information Systems, 1–8. https://doi.org/10.1145/956676.956677

Khan, A. U., Abbas, G., Abbas, Z. H., Bilal, M., Shah, S. C., & Song, H. (2022). Reliability Analysis of Cognitive Radio Networks with Reserved Spectrum for 6G-IoT. IEEE Transactions on Network and Service Management, 19(3), 2726–2737. https://doi.org/10.1109/TNSM.2022.3168669

Khan, A. U., Tanveer, M., Khan, W. U., Nebhen, J., Li, X., Zeng, M., & Dobre, O. A. (2021). An enhanced spectrum reservation framework for heterogeneous users in CR-Enabled IoT Networks. IEEE Wireless Communications Letters, 10(11), 2504–2508. https://doi.org/10.1109/LWC.2021.3105728

Khan, W. U. (2019). Maximizing physical layer security in relay-assisted multicarrier nonorthogonal multiple access transmission. Internet Technology Letters, 2(2). https://doi.org/10.1002/itl2.76

Khan, W. U., Ali, Z., Lagunas, E., Mahmood, A., Asif, M., Ihsan, A., Chatzinotas, S., Ottersten, B., & Dobre, O. A. (2023). Rate Splitting Multiple Access for Next Generation Cognitive Radio Enabled LEO Satellite Networks. IEEE Transactions on Wireless Communications, 22(11), 8423–8435. https://doi.org/10.1109/TWC.2023.3263116

Khan, W. U., Ali, Z., Waqas, M., & Sidhu, G. A. S. (2019). Efficient power allocation with individual QoS guarantees in future small-cell networks. AEU - International Journal of Electronics and Communications, 105, 36–41. https://doi.org/10.1016/j.aeue.2019.03.016

Khan, W. U., Ihsan, A., Nguyen, T. N., Ali, Z., & Javed, M. A. (2022). NOMA-Enabled Backscatter Communications for Green Transportation in Automotive-Industry 5.0. IEEE Transactions on Industrial Informatics, 18(11), 7862–7874. https://doi.org/10.1109/TII.2022.3161029

Khan, W. U., Imtiaz, N., & Ullah, I. (2021). Joint optimization of NOMA-enabled backscatter communications for beyond 5G IoT networks. Internet Technology Letters, 4(2). https://doi.org/10.1002/itl2.265

Khan, W. U., Jameel, F., Li, X., Bilal, M., & Tsiftsis, T. A. (2021). Joint Spectrum and Energy Optimization of NOMA-Enabled Small-Cell Networks with QoS Guarantee. IEEE Transactions on Vehicular Technology, 70(8), 8337–8342. https://doi.org/10.1109/TVT.2021.3095955

Khan, W. U., Jameel, F., Sidhu, G. A. S., Ahmed, M., Li, X., & Jantti, R. (2020). Multiobjective Optimization of Uplink NOMA-Enabled Vehicle-to-Infrastructure Communication. IEEE Access, 8, 84467–84478. https://doi.org/10.1109/ACCESS.2020.2991197

Khan, W. U., Jamshed, M. A., Lagunas, E., Chatzinotas, S., Li, X., & Ottersten, B. (2023). Energy Efficiency Optimization for Backscatter Enhanced NOMA Cooperative V2X Communications Under Imperfect CSI. IEEE Transactions on Intelligent Transportation Systems, 24(11), 12961–12972. https://doi.org/10.1109/TITS.2022.3187567

Khan, W. U., Jamshed, M. A., Mahmood, A., Lagunas, E., Chatzinotas, S., & Ottersten, B. (2022). Backscatter-Aided NOMA V2X Communication under Channel Estimation Errors. IEEE Vehicular Technology Conference, 2022-June. https://doi.org/10.1109/VTC2022-Spring54318.2022.9860382

Khan, W. U., Lagunas, E., Ali, Z., Javed, M. A., Ahmed, M., Chatzinotas, S., Ottersten, B., & Popovski, P. (2022). Opportunities for Physical Layer Security in UAV Communication Enhanced with Intelligent Reflective Surfaces. IEEE Wireless Communications, 29(6), 22–28. https://doi.org/10.1109/MWC.001.2200125

Khan, W. U., Lagunas, E., Mahmood, A., Ali, Z., Chatzinotas, S., Ottersten, B., & Dobre, O. A. (2022). Integration of Backscatter Communication with Multi-cell NOMA: A Spectral Efficiency Optimization under Imperfect SIC. IEEE International Workshop on Computer Aided Modeling and Design of Communication Links and Networks, CAMAD, 2022-Novem, 147–152. https://doi.org/10.1109/CAMAD55695.2022.9966913

Khan, W. U., Lagunas, E., Mahmood, A., Elhalawany, B. M., Chatzinotas, S., & Ottersten, B. (2022). When RIS Meets GEO Satellite Communications: A New Sustainable Optimization Framework in 6G. IEEE Vehicular Technology Conference, 2022-June. https://doi.org/10.1109/VTC2022-Spring54318.2022.9860805

Khan, W. U., Li, X., Ihsan, A., Ali, Z., Elhalawany, B. M., & Sidhu, G. A. S. (2021). Energy efficiency maximization for beyond 5G NOMA-enabled heterogeneous networks. Peer-to-Peer Networking and Applications, 14(5), 3250–3264. https://doi.org/10.1007/s12083-021-01176-5

Khan, W. U., Liu, J., Jameel, F., Khan, M. T. R., Ahmed, S. H., & Jantti, R. (2020). Secure backscatter communications in multi-cell NOMA Networks: Enabling link security for massive IoT networks. IEEE INFOCOM 2020 - IEEE Conference on Computer Communications Workshops, INFOCOM WKSHPS 2020, 213–218. https://doi.org/10.1109/INFOCOMWKSHPS50562.2020.9162938

Khowaja, S. A., Khuwaja, P., Dev, K., Lee, I. H., Khan, W. U., Wang, W., Qureshi, N. M. F., & Magarini, M. (2023). A Secure Data Sharing Scheme in Community Segmented Vehicular Social Networks for 6G. IEEE Transactions on Industrial Informatics, 19(1), 890–899. https://doi.org/10.1109/TII.2022.3188963

Li, J., Fang, H. Y., Ma, Y. R., & Yang, H. B. (2014). Research on point cloud data management based on spatial index and database. Advanced Materials Research, 850–851, 685–688. https://doi.org/10.4028/www.scientific.net/AMR.850-851.685

Lopac, V., Brant, S., & Paar, V. (1986). Level density fluctuations and characterization of chaos in the realistic model spectra for odd-odd nuclei. Zeitschrift Für Physik A Hadrons and Nuclei, 356(2), 113–118. https://doi.org/10.1007/s002180050156

Mahmood, A., Ahmed, A., Naeem, M., Amirzada, M. R., & Al-Dweik, A. (2022). Weighted utility aware computational overhead minimization of wireless power mobile edge cloud. Computer Communications, 190, 178–189. https://doi.org/10.1016/j.comcom.2022.04.017

Mahmood, A., Ahmed, A., Naeem, M., & Hong, Y. (2020). Partial offloading in energy harvested mobile edge computing: A direct search approach. IEEE Access, 8, 36757–36763. https://doi.org/10.1109/ACCESS.2020.2974809

Mahmood, A., Hong, Y., Ehsan, M. K., & Mumtaz, S. (2021). Optimal Resource Allocation and Task Segmentation in IoT Enabled Mobile Edge Cloud. IEEE Transactions on Vehicular Technology, 70(12), 13294–13303. https://doi.org/10.1109/TVT.2021.3121146

Mahmood, A., Vu, T. X., Khan, W. U., Chatzinotas, S., & Ottersten, B. (2022). Optimizing Computational and Communication Resources for MEC Network Empowered UAV-RIS Communication. 2022 IEEE GLOBECOM Workshops, GC Wkshps 2022 - Proceedings, 974–979. https://doi.org/10.1109/GCWkshps56602.2022.10008627

Matke, M., Saurabh, K., & Singh, U. (2023). An Empirical Evaluation of Machine Learning Algorithms for Intrusion Detection in IIoT Networks. 2023 IEEE 20th India Council International Conference, INDICON 2023, 1353–1358. https://doi.org/10.1109/INDICON59947.2023.10440779

Nutanong, S., Zhang, R., Tanin, E., & Kulik, L. (2009). V*-kNN: An efficient algorithm for moving k nearest neighbor queries. Proceedings - International Conference on Data Engineering, 1519–1522. https://doi.org/10.1109/ICDE.2009.63

Petrescu-Mag, R. M., Vermeir, I., Petrescu, D. C., Crista, F. L., & Banatean-Dunea, I. (2020). Traditional foods at the click of a button: The preference for the online purchase of romanian traditional foods during the COVID-19 pandemic. Sustainability (Switzerland), 12(23). https://doi.org/10.3390/su12239956

Rasheed, I., Asif, M., Ihsan, A., Khan, W. U., Ahmed, M., & Rabie, K. M. (2023). LSTM-Based Distributed Conditional Generative Adversarial Network for Data-Driven 5G-Enabled Maritime UAV Communications. IEEE Transactions on Intelligent Transportation Systems, 24(2), 2431–2446. https://doi.org/10.1109/TITS.2022.3187941

Raza, S., Wang, S., Ahmed, M., Anwar, M. R., Mirza, M. A., & Khan, W. U. (2022). Task Offloading and Resource Allocation for IoV Using 5G NR-V2X Communication. IEEE Internet of Things Journal, 9(13), 10397–10410. https://doi.org/10.1109/JIOT.2021.3121796

Shahabi, C., Kolahdouzan, M. R., & Sharifzadeh, M. (2002). A road network embedding technique for K-Nearest Neighbor search in moving object databases. Proceedings of the ACM Workshop on Advances in Geographic Information Systems, 94–100. https://doi.org/10.1145/585147.585167

Shen, B., Zhao, Y., Li, G., Zheng, W., Qin, Y., Yuan, B., & Rao, Y. (2017). V-Tree: Efficient KNN search on moving objects with road-network constraints. Proceedings - International Conference on Data Engineering, 609–620. https://doi.org/10.1109/ICDE.2017.115

Sparrow, B. H. (2004). Projections of Power: Framing News, Public Opinion, and U.S. Foreign Policy. Perspectives on Politics. https://doi.org/10.1017/s1537592704350589

Tianyang, D., Lulu, Y., Qiang, C., Bin, C., & Jing, F. (2019). Direction-aware KNN queries for moving objects in a road network. World Wide Web, 22(4), 1765–1797. https://doi.org/10.1007/s11280-019-00657-1

Wang, S., Gao, S., Feng, X., Murray, A. T., & Zeng, Y. (2018). A context-based geoprocessing framework for optimizing meetup location of multiple moving objects along road networks. International Journal of Geographical Information Science, 32(7), 1368–1390. https://doi.org/10.1080/13658816.2018.1431838

Yu, S., Khan, W. U., Zhang, X., & Liu, J. (2021). Optimal power allocation for NOMA-enabled D2D communication with imperfect SIC decoding. Physical Communication, 46. https://doi.org/10.1016/j.phycom.2021.101296

Zhao, X., Yu, J., Ge, X., & Hao, R. (2024). Towards efficient Secure Boolean Range Query over encrypted spatial data. Computers and Security, 136. https://doi.org/10.1016/j.cose.2023.103544

Zheng, Z., & Su, D. (2014). Short-term traffic volume forecasting: A k-nearest neighbor approach enhanced by constrained linearly sewing principle component algorithm. Transportation Research Part C: Emerging Technologies, 43, 143–157. https://doi.org/10.1016/j.trc.2014.02.009

Downloads

Published

2024-03-31

How to Cite

aljubayrin, saad. (2024). Bus*: An efficient algorithm for finding Moving K-Nearest Neighbors (MKNNs) with capacity constraints. COMMICAST, 5(1), 43–62. https://doi.org/10.12928/commicast.v5i1.9955

Issue

Vol. 5 No. 1 (2024): March

Section

Articles

License

Copyright (c) 2024 Saad Aljubayrin

Creative Commons License

This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

License and Copyright Agreement

In submitting the manuscript to the journal, the authors certify that:

  • They are authorized by their co-authors to enter into these arrangements.
  • The work described has not been formally published before, except in the form of an abstract or as part of a published lecture, review, thesis, or overlay journal. Please also carefully read Commicast's Posting Your Article Policy at http://journal2.uad.ac.id/index.php/commicast/about/editorialPolicies#custom-5
  • That it is not under consideration for publication elsewhere,
  • That its publication has been approved by all the author(s) and by the responsible authorities – tacitly or explicitly – of the institutes where the work has been carried out.
  • They secure the right to reproduce any material that has already been published or copyrighted elsewhere.
  • They agree to the following license and copyright agreement.

Copyright

Authors who publish with Commicast agree to the following terms:

  1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License (CC BY-SA 4.0) that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this journal. 
  2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial publication in this journal.
  3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.

Licensing for Data Publication

Commicast use a variety of waivers and licenses, that are specifically designed for and appropriate for the treatment of data:

Other data publishing licenses may be allowed as exceptions (subject to approval by the editor on a case-by-case basis) and should be justified with a written statement from the author, which will be published with the article.

Open Data and Software Publishing and Sharing

The journal strives to maximize the replicability of the research published in it. Authors are thus required to share all data, code or protocols underlying the research reported in their articles. Exceptions are permitted but have to be justified in a written public statement accompanying the article.

Datasets and software should be deposited and permanently archived inappropriate, trusted, general, or domain-specific repositories (please consult http://service.re3data.org and/or software repositories such as GitHub, GitLab, Bioinformatics.org, or equivalent). The associated persistent identifiers (e.g. DOI, or others) of the dataset(s) must be included in the data or software resources section of the article. Reference(s) to datasets and software should also be included in the reference list of the article with DOIs (where available). Where no domain-specific data repository exists, authors should deposit their datasets in a general repository such as ZENODO, Dryad, Dataverse, or others.

Small data may also be published as data files or packages supplementary to a research article, however, the authors should prefer in all cases a deposition in data repositories.