Accelerating Convergence in Data Offloading Solutions: A Greedy-Assisted Genetic Algorithm Approach
(1) * Mulki Indana Zulfa Mail (Jenderal Soedirman University, Indonesia)
(2) Stephen Prasetya Chrismawan Mail (Jenderal Soedirman University, Indonesia)
(3) Adhwa Moyafi Hartoyo Mail (Jenderal Soedirman University, Indonesia)
(4) Wafdan Musa Nursakti Mail (Monster Technologies, Malaysia)
(5) Waleed Ali Ahmed Mail (King Abdulaziz University, Saudi Arabia)
*corresponding author

Abstract


Data offloading, a technique that distributes data across the network, is crucial for alleviating congestion and enhancing system performance. One challenge in this process is optimizing web caching, which can be modeled as a dynamic knapsack problem in edge networks. This study introduces a Greedy-Assisted Genetic Algorithm (GA-Greedy) to tackle this challenge, accelerating convergence and improving solution quality. The greedy heuristic is integrated into the GA at two stages: during initialization to create a superior starting population, and at the end of each iteration to refine solutions generated through genetic operations. The GA-Greedy’s effectiveness was evaluated using the IRcache dataset, focusing on hit ratio—an indicator of successful cache accesses that reduces network load and speeds up data retrieval. Results show that GA-Greedy outperforms traditional GA and standalone greedy algorithms, especially with smaller cache sizes. For instance, with a 3K cache size, the half-greedy GA achieved a hit ratio of 0.55, compared to 0.2 for the pure GA and 0.1 for the greedy algorithm. Similarly, the full-greedy GA reached a hit ratio of 0.45. By enhancing convergence and guiding the search, GA-Greedy enables more efficient data distribution in edge networks, reducing latency and improving user experience.

Keywords


Data Offloading; Genetic Algorithm; Greedy Algorithm; Dynamic Knapsack Problem; Edge Networks

   

DOI

https://doi.org/10.31763/ijrcs.v4i4.1652 		      

Article metrics

10.31763/ijrcs.v4i4.1652 Abstract views : 91 | PDF views : 30

   

Cite

How to cite item
   

Full Text

Download

References


[1] D. Clark, “The design philosophy of the DARPA internet protocols,” Symposium proceedings on Communications architectures and protocols, pp. 106-114, 1988, https://doi.org/10.1145/52324.52336.

[2] M. El Khadiri, W. C. Yeh, and H. Cancela, “An efficient factoring algorithm for the quickest path multi-state flow network reliability problem,” Computers & Industrial Engineering, vol. 179, p. 109221, 2023, https://doi.org/10.1016/j.cie.2023.109221.

[3] M. Candela, V. Luconi, and A. Vecchio, “A worldwide study on the geographic locality of Internet routes,” Computer Networks, vol. 201, p. 108555, 2021, https://doi.org/10.1016/j.comnet.2021.108555.

[4] T. Berners-Lee, R. Cailliau, J. F. Groff, and B. Pollermann, “World-wide web: The information universe,” Internet Research, vol. 2, no. 1, pp. 52-58, 1992, https://doi.org/10.1108/eb047254.

[5] Z. JinCheng and D. L. K. Chuen, “Chapter 28 - Understanding the Evolution of the Internet: Web 1.0 to Web3.0, Web3, and Web 3+∗,” Handbook of Digital Currency (Second Edition), pp. 553-581, 2024, https://doi.org/10.1016/B978-0-323-98973-2.00052-6.

[6] A. I. Díaz-Cano and A. Esplugues-Cebrián, “Web 2.0 as a new support for breastfeeding: Perception of mothers and professionals through a qualitative approach,” Enfermería Clínica (English Edition), vol. 34, no. 1, pp. 34-48, 2024, https://doi.org/10.1016/j.enfcle.2023.11.001.

[7] J. Zhu, F. Li, and J. Chen, “A Survey of Blockchain, Artificial Intelligence, and Edge Computing for Web 3.0,” Computer Science Review, vol. 54, p. 100667, 2023, https://doi.org/10.1016/j.cosrev.2024.100667.

[8] E. Demuro and L. Gurney, “Artificial intelligence and the ethnographic encounter: Transhuman language ontologies, or what it means ‘to write like a human, think like a machine,” Language & Communication, vol. 96, pp. 1-12, 2024, https://doi.org/10.1016/j.langcom.2024.02.002.

[9] D. Wang, X. An, X. Zhou, and X. Lü, “Data cache optimization model based on cyclic genetic ant colony algorithm in edge computing environment,” International Journal of Distributed Sensor Networks, vol. 15, no. 8, 2019, https://doi.org/10.1177/1550147719867864.

[10] M. I. Zulfa, R. Hartanto, and A. E. Permanasari, “Caching strategy for Web application – a systematic literature review,” International Journal of Web Information Systems, vol. 16, no. 5, pp. 545-569, 2020, https://doi.org/10.1108/IJWIS-06-2020-0032.

[11] S. Zhang, W. Sun and J. Liu, "Spatially Cooperative Caching and Optimization for Heterogeneous Network," IEEE Transactions on Vehicular Technology, vol. 68, no. 11, pp. 11260-11270, 2019, https://doi.org/10.1109/TVT.2019.2941115.

[12] M. I. Zulfa, R. Hartanto and A. E. Permanasari, "Performance Comparison of Swarm Intelligence Algorithms for Web Caching Strategy," 2021 IEEE International Conference on Communication, Networks and Satellite (COMNETSAT), pp. 45-51, 2021, https://doi.org/10.1109/COMNETSAT53002.2021.9530778.

[13] M. I. Zulfa, A. Fadli, A. E. Permanasari, and W. A. Ahmed, “Performance comparison of cache replacement algorithms onvarious internet traffic,” Jurnal INFOTEL, vol. 15, no. 1, pp. 1-7, 2023, https://doi.org/10.20895/infotel.v15i1.872.

[14] M. O. Okwu and L. K. Tartibu, “Metaheuristic Optimization: Nature-Inspired Algorithms Swarm and Computational Intelligence, Theory and Applications,” Studies in Computational Intelligence, vol. 927, 2021, https://doi.org/10.1007/978-3-030-61111-8.

[15] E. Rajapackiyam et al., “An efficient computation offloading in edge environment using genetic algorithm with directed search techniques for IoT applications,” Future Generation Computer Systems, vol. 158, pp. 378-390, 2024, https://doi.org/10.1016/j.future.2024.04.021.

[16] R. Paulavičius, L. Stripinis, S. Sutavičiūtė, D. Kočegarov, and E. Filatovas, “A novel greedy genetic algorithm-based personalized travel recommendation system,” Expert Systems with Applications, vol. 230, p. 120580, 2023, https://doi.org/10.1016/j.eswa.2023.120580.

[17] H. Qin, N. Li, T. Wang, G. Yang, and Y. Peng, “CDT: Cross-interface Data Transfer scheme for bandwidth-efficient LoRa communications in energy harvesting multi-hop wireless networks,” Journal of Network and Computer Applications, vol. 229, p. 103935, 2024, https://doi.org/10.1016/j.jnca.2024.103935.

[18] G. Huang, J. Liu, B. Zhang, and C. Li, “Quality-driven video streaming for ultra-dense OFDMA heterogeneous networks,” Computer Networks, vol. 218, p. 109398, 2022, https://doi.org/10.1016/j.comnet.2022.109398.

[19] J. Paul, M. Akbari, S. Mondal, S. Das, “Knowledge sharing leads to engagement during Covid-19 for online gamers,” Information & Management, vol. 61, no. 4, p. 103948, 2024, https://doi.org/10.1016/j.im.2024.103948.

[20] M. I. Bala and M. A. Chishti, “Survey of applications, challenges and opportunities in fog computing,” International Journal of Pervasive Computing and Communications, vol. 15, no. 2, pp. 80-96, 2019, https://doi.org/10.1108/IJPCC-06-2019-059.

[21] J. Tong et al., “Optimizing the path of seedling transplanting with multi-end effectors by using an improved greedy annealing algorithm,” Computers and Electronics in Agriculture, vol. 201, p. 107276, 2022, https://doi.org/10.1016/j.compag.2022.107276.

[22] H. Cui, X. Li, and L. Gao, “An improved multi-population genetic algorithm with a greedy job insertion inter-factory neighborhood structure for distributed heterogeneous hybrid flow shop scheduling problem,” Expert Systems with Applications, vol. 222, p. 119805, 2023, https://doi.org/10.1016/j.eswa.2023.119805.

[23] S. Shukla and H. Banka, “Markov-based genetic algorithm with ϵ-greedy exploration for Indian classical music composition,” Expert Systems with Applications, vol. 211, p. 118561, 2023, https://doi.org/10.1016/j.eswa.2022.118561.

[24] S. Akila and S. Allin Christe, “A wrapper based binary bat algorithm with greedy crossover for attribute selection,” Expert Systems with Applications, vol. 187, p. 115828, 2022, https://doi.org/10.1016/j.eswa.2021.115828.

[25] T. Gangavarapu and N. Patil, “A novel filter–wrapper hybrid greedy ensemble approach optimized using the genetic algorithm to reduce the dimensionality of high-dimensional biomedical datasets,” Applied Soft Computing, vol. 81, p. 105538, 2019, https://doi.org/10.1016/j.asoc.2019.105538.

[26] A. Brum, R. Ruiz, and M. Ritt, “Automatic generation of iterated greedy algorithms for the non-permutation flow shop scheduling problem with total completion time minimization,” Computers & Industrial Engineering, vol. 163, 2022, https://doi.org/10.1016/j.cie.2021.107843.

[27] K. Rajwar, K. Deep, and S. Das, “An exhaustive review of the metaheuristic algorithms for search and optimization: taxonomy, applications, and open challenges,” Artificial Intelligence Review, vol. 56, no. 11, pp. 13187-13257, 2023, https://doi.org/10.1007/s10462-023-10470-y.

[28] S. R. Kumar and K. D. Singh, “Nature-Inspired Optimization Algorithms: Research Direction and Survey,” Neural and Evolutionary Computing, 2021, https://doi.org/10.48550/arXiv.2102.04013.

[29] F. Lin, “Solving the knapsack problem with imprecise weight coefficients using genetic algorithms,” European Journal of Operational Research, vol. 185, no. 1, pp. 133-145, 2008, https://doi.org/10.1016/j.ejor.2006.12.046.

[30] R. Vinayakumar, K. P. Soman and P. Poornachandran, "Secure shell (ssh) traffic analysis with flow based features using shallow and deep networks," 2017 International Conference on Advances in Computing, Communications and Informatics (ICACCI), pp. 2026-2032, 2017, https://doi.org/10.1109/ICACCI.2017.8126143.

[31] M. I. Zulfa, S. Maryani, Ardiansyah, T. Widiyaningtyas, W. Ali, “Application-Level Caching Approach Based on Enhanced Aging Factor and Pearson Correlation Coefficient,” International Journal on Informatics Visualization, vol. 8, no. 1, p. 31, 2024, https://doi.org/10.62527/joiv.8.1.2143.

[32] H. Ibrahim, W. Yasin, N. I. Udzir, and B. Process, “Intelligent cooperative web caching policies for media objects based on J48 decision tree and Naïve Bayes supervised machine learning algorithms in structured peer-to-peer systems,” Journal of Information and Communication Technology, vol. 15, no. 2, pp. 85-116, 2016, https://doi.org/10.32890/jict2016.15.2.5.

[33] X. Li, X. Wang, Z. Sheng, H. Zhou, and V. C. M. Leung, “Resource allocation for cache-enabled cloud- based small cell networks,” Computer Communications, vol. 127, pp. 20-29, 2018, https://doi.org/10.1016/j.comcom.2018.05.007.

[34] Q. Wang, S. Guo, J. Liu, C. Pan and L. Yang, "Profit Maximization Incentive Mechanism for Resource Providers in Mobile Edge Computing," IEEE Transactions on Services Computing, vol. 15, no. 1, pp. 138-149, 2022, https://doi.org/10.1109/TSC.2019.2924002.

[35] K. Cao, L. Li, Y. Cui, T. Wei and S. Hu, "Exploring Placement of Heterogeneous Edge Servers for Response Time Minimization in Mobile Edge-Cloud Computing," IEEE Transactions on Industrial Informatics, vol. 17, no. 1, pp. 494-503, 2021, https://doi.org/10.1109/TII.2020.2975897.

[36] B. Sun et al., “The Online Knapsack Problem with Departures,” Proceedings of the ACM on Measurement and Analysis of Computing Systems, vol. 6, no. 3, pp. 1-32, 2022, https://doi.org/10.1145/3570618.

[37] B. Abdollahzadeh, S. Barshandeh, H. Javadi, and N. Epicoco, “An enhanced binary slime mould algorithm for solving the 0–1 knapsack problem,” Engineering with Computers, vol. 38, pp. 3423-3444, 2022, https://doi.org/10.1007/s00366-021-01470-z.

[38] J. Reynolds, A. Bates, and M. Bailey, “Equivocal URLs: Understanding the Fragmented Space of URL Parser Implementations,” Computer Security–ESORICS 2022, pp. 166-185, 2022, https://doi.org/10.1007/978-3-031-17143-7_9.

[39] A. Laughter, S. Omari, P. Szczurek, and J. Perry, “Detection of Malicious HTTP Requests Using Header and URL Features,” Proceedings of the Future Technologies Conference (FTC) 2020, vol. 2, pp. 449-468, 2021, https://doi.org/10.1007/978-3-030-63089-8_29.

[40] N. Fukushi, T. Koide, D. Chiba, H. Nakano, and M. Akiyama, “Understanding Security Risks of Ad- based URL Shortening Services Caused by Users’ Behaviors,” Journal of Information Processing, vol. 30, pp. 865-877, 2022, https://doi.org/10.2197/ipsjjip.30.865.

[41] J. Mertz and I. Nunes, “Understanding Application-Level Caching in Web Applications,” ACM Computing Surveys (CSUR), vol. 50, no. 6, pp. 1-34, 2017, https://doi.org/10.1145/3145813.

[42] T. Chen, W. Shang, A. E. Hassan, M. Nasser, and P. Flora, “CacheOptimizer: Helping Developers Configure Caching Frameworks for Hibernate-Based Database-Centric Web Applications,” FSE 2016: Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pp. 666-677, 2016, https://doi.org/10.1145/2950290.2950303.

[43] Q. Chen and Y. Shao, “A Hybrid Genetic Algorithm to Solve Zero-One Knapsack Problem,” Applied Informatics and Communication, pp. 315-320, 2011, https://doi.org/10.1007/978-3-642-23214-5_42.

[44] Y. Feng, J. -H. Yi and G. -G. Wang, "Enhanced Moth Search Algorithm for the Set-Union Knapsack Problems," IEEE Access, vol. 7, pp. 173774-173785, 2019, https://doi.org/10.1109/ACCESS.2019.2956839.

[45] Y. Huang, P. Wang, J. Li, X. Chen and T. Li, "A Binary Multi-Scale Quantum Harmonic Oscillator Algorithm for 0–1 Knapsack Problem With Genetic Operator," IEEE Access, vol. 7, pp. 137251-137265, 2019, https://doi.org/10.1109/ACCESS.2019.2942340.

[46] S. Parvaze et al., “Optimization of Water Distribution Systems Using Genetic Algorithms: A Review,” Archives of Computational Methods in Engineering, vol. 30, no. 7, pp. 4209-4244, 2023, https://doi.org/10.1007/s11831-023-09944-7.

[47] M. Ahmed et al., "Vehicular Communication Network Enabled CAV Data Offloading: A Review," IEEE Transactions on Intelligent Transportation Systems, vol. 24, no. 8, pp. 7869-7897, 2023, https://doi.org/10.1109/TITS.2023.3263643.

[48] S. A. Oke, W. O. Adedeji, M. C. Ikedue, J. Rajan, “Exploiting Tournament Selection-Based Genetic Algorithm in Integrated AHP-Taguchi Analyses-GA Method for Wire Electrical Discharge Machining of AZ91 Magnesium Alloy,” Indonesian Journal of Industrial Engineering & Management, vol. 4, no. 1, pp. 1-17, 2023, https://doi.org/10.22441/ijiem.v4i1.17387.

[49] A. S. Hameed, H. M. B. Alrikabi, A. A. Abdul–Razaq, Z. H. Ahmed, H. K. Nasser, and M. L. Mutar, “Appling the Roulette Wheel Selection Approach to Address the Issues of Premature Convergence and Stagnation in the Discrete Differential Evolution Algorithm,” Applied Computational Intelligence and Soft Computing, vol. 2023, no. 1, pp. 1-16, 2023, https://doi.org/10.1155/2023/8892689.

[50] E. Tasci et al., “RadWise: A Rank-Based Hybrid Feature Weighting and Selection Method for Proteomic Categorization of Chemoirradiation in Patients with Glioblastoma,” Cancers, vol. 15, no. 10, p. 2672, 2023, https://doi.org/10.3390/cancers15102672.

[51] R. T. Bye, M. Gribbestad, R. Chandra, O. L. Osen, “A Comparison of GA Crossover and Mutation Methods for the Traveling Salesman Problem,” Innovations in Computational Intelligence and Computer Vision, pp. 529-542, 2021, https://doi.org/10.1007/978-981-15-6067-5_60.

[52] S. Rani, B. Suri, and R. Goyal, “On the Effectiveness of Using Elitist Genetic Algorithm in Mutation Testing,” Symmetry, vol. 11, no. 9, p. 1145, 2019, https://doi.org/10.3390/sym11091145.

[53] N. I. Senaratna, “Genetic Algorithms: The Crossover-Mutation Debate,” Neural and Evolutionary Computing, 2005, https://doi.org/10.48550/arXiv.2102.04013.

[54] F. Yu, Y. Peng, J. Li, G. Zhou, and L. Chen, “An Analysis of Optimization for Car PBS Scheduling Based on Greedy Strategy State Transition Algorithm,” Applied Science, vol. 13, no. 10, p. 6194, 2023, https://doi.org/10.3390/app13106194.

[55] T. Benecke and S. Mostaghim, "Effects of Optimal Genetic Material in the Initial Population of Evolutionary Algorithms," 2023 IEEE Symposium Series on Computational Intelligence (SSCI), pp. 1386-1391, 2023, https://doi.org/10.1109/SSCI52147.2023.10372037.

[56] R. M. Aziz, R. Mahto, K. Goel, A. Das, P. Kumar, and A. Saxena, “Modified Genetic Algorithm with Deep Learning for Fraud Transactions of Ethereum Smart Contract,” Applied Science, vol. 13, no. 2, p. 697, 2023, https://doi.org/10.3390/app13020697.

[57] L. Pintér, K. Krajczár, F. Őry, J. Szalma, and E. Lempel, “Effect of Intermediate Irrigation on Temperature Rise during Broken NiTi File Removal Using Ultrasonic Device,” Applied Science, vol. 13, no. 17, p. 9761, 2023, https://doi.org/10.3390/app13179761.

[58] S. Katoch, S. S. Chauhan, and V. Kumar, “A review on genetic algorithm: past, present, and future,” Multimedia Tools and Applications, vol. 80, no. 5, pp. 8091-8126, 2021, https://doi.org/10.1007/s11042-020-10139-6.


Refbacks

  • There are currently no refbacks.


Copyright (c) 2024 Mulki Indana Zulfa, Stephen Prasetya Chrismawan, Adhwa Moyafi Hartoyo, Wafdan Musa Nursakti, Waleed Ali Ahmed

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

 

About the JournalJournal PoliciesAuthor Information

International Journal of Robotics and Control Systems
e-ISSN: 2775-2658
Website: https://pubs2.ascee.org/index.php/IJRCS
Email: ijrcs@ascee.org
Organized by: Association for Scientific Computing Electronics and Engineering (ASCEE), Peneliti Teknologi Teknik Indonesia, Department of Electrical Engineering, Universitas Ahmad Dahlan and Kuliah Teknik Elektro
Published by: Association for Scientific Computing Electronics and Engineering (ASCEE)
Office: Jalan Janti, Karangjambe 130B, Banguntapan, Bantul, Daerah Istimewa Yogyakarta, Indonesia