Intelligent Resource Allocation in Fog Computing: A Learning Automata Approach
الموضوعات :Alireza Enami 1 , Javad Akbari Torkestani 2
1 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
2 - Department of Computer Engineering, Arak Branch, Islamic Azad University, Arak, Iran
الکلمات المفتاحية: learning automata, Heuristic Algorithms, Fog Computing, Resource Allocation,
ملخص المقالة :
Fog computing is being seen as a bridge between smart IoT devices and large scale cloud computing. It is possible to develop cloud computing services to network edge devices using Fog computing. As one of the most important services of the system, the resource allocation should always be available to achieve the goals of Fog computing. Resource allocation is the process of distributing limited available resources among applications based on predefined rules. Because the problems raised in the resource management system are NP-hard, and due to the complexity of resource allocation, heuristic algorithms are promising methods for solving the resource allocation problem. In this paper, an algorithm is proposed based on learning automata to solve this problem, which uses two learning automata: a learning automata is related to applications (LAAPP) and the other is related to Fog nodes (LAN). In this method, an application is selected from the action set of LAAPP and then, a Fog node is selected from the action set of LAN. If the requirements of deadline, response time and resources are met, then the resource will be allocated to the application. The efficiency of the proposed algorithm is evaluated through conducting several simulation experiments under different Fog configurations. The obtained results are compared with several existing methods in terms of the makespan, average response time, load balancing and throughput.
[1] R. Huang, Y. Sun, C. Huang, G. Zhao, Y. Ma. A survey on fog computing. International Conference on Security, Privacy and Anonymity in Computation, Communication and Storage. Springer, 2019. p. 160-9.
[2] R. Mahmud, R. Kotagiri, R. Buyya. Fog computing: A taxonomy, survey and future directions. Internet of everything. Springer, 2018. p. 103-30.
[3] M. Ghobaei-Arani, A. Souri, A.A. Rahmanian. Resource management approaches in fog computing: a comprehensive review. Journal of Grid Computing. (2019) 1-42.
[4] F. Bonomi, R. Milito, J. Zhu, S. Addepalli. Fog computing and its role in the internet of things. Proceedings of the first edition of the MCC workshop on Mobile cloud computing, 2012. p. 13-6.
[5] M. Mukherjee, L. Shu, D. Wang. Survey of fog computing: Fundamental, network applications, and research challenges. IEEE Communications Surveys & Tutorials. 20 (2018) 1826-57.
[6] H. Ghorashi, and M. Mirabi, An Effective Task Scheduling Framework for Cloud Computing using NSGA-II. Journal of Advances in Computer Engineering and Technology, 2020. 6(3): p. 151-160.
[7] M. Bozorgi Elize, and A. KhademZadeh, A Genetic Based Resource Management Algorithm Considering Energy Efficiency in Cloud Computing Systems. Journal of Advances in Computer Engineering and Technology, 2017. 3(4): p. 203-212.
[8] M. Davarpanah, , A review of methods for resource allocation and operational framework in cloud computing. Journal of Advances in Computer Engineering and Technology, 2017. 3: p. 51-60.
[9] C.-H. Hong, B. Varghese. Resource management in fog/edge computing: a survey on architectures, infrastructure, and algorithms. ACM Computing Surveys (CSUR). 52 (2019) 1-37.
[10] F. Xhafa, A. Abraham. Computational models and heuristic methods for Grid scheduling problems. Future generation computer systems. 26 (2010) 608-21.
[11] K. Singh, A. Chhabra, A. GNDU. A Survey of Evolutionary Heuristic Algorithm for Job Scheduling in Grid Computing. International Journal of Computer Science and Mobile Computing. 4 (2015) 611-6.
[12] T. Remani, E. Jasmin, T.I. Ahamed. Residential load scheduling with renewable generation in the smart grid: A reinforcement learning approach. IEEE Systems Journal. (2018).
[13] M. Rezapoor Mirsaleh, M.R. Meybodi. Balancing exploration and exploitation in memetic algorithms: a learning automata approach. Computational Intelligence. 34 (2018) 282-309.
[14] A. Rezvanian, A.M. Saghiri, S.M. Vahidipour, M. Esnaashari, M.R. Meybodi. Recent advances in learning automata. Springer, 2018.
[15] M.M.D. Khomami, A. Rezvanian, M.R. Meybodi. A new cellular learning automata-based algorithm for community detection in complex social networks. Journal of computational science. 24 (2018) 413-26.
[16] H. Morshedlou, M.R. Meybodi. A new learning automata based approach for increasing utility of service providers. International Journal of Communication Systems. 31 (2018) e3459.
[17] M. Hasanzadeh-Mofrad, A. Rezvanian. Learning automata clustering. Journal of computational science. 24 (2018) 379-88.
[18] M. Ranjbari, J.A. Torkestani. A learning automata-based algorithm for energy and SLA efficient consolidation of virtual machines in cloud data centers. Journal of Parallel and Distributed Computing. 113 (2018) 55-62.
[19] S.M. Vahidipour, M. Esnaashari, A. Rezvanian, M.R. Meybodi. GAPN-LA: A framework for solving graph problems using Petri nets and learning automata. Engineering Applications of Artificial Intelligence. 77 (2019) 255-67.
[20] E. Susmitha, B.R. Devi. Pipelined Learning Automation for Energy Distribution in Smart Grid. International Conference on E-Business and Telecommunications. Springer, 2019. p. 732-42.
[21] A. Yazidi, X. Zhang, L. Jiao, B.J. Oommen. The hierarchical continuous pursuit learning automation: a novel scheme for environments with large numbers of actions. IEEE transactions on neural networks and learning systems. (2019).
[22] M. Jamshidi, M. Esnaashari, A.M. Darwesh, M.R. Meybodi. Detecting Sybil nodes in stationary wireless sensor networks using learning automaton and client puzzles. IET Communications. 13 (2019) 1988-97.
[23] A.M. Saghiri, M.D. Khomami, M.R. Meybodi. Random Walk Algorithms: Definitions, Weaknesses, and Learning Automata-Based Approach. Intelligent Random Walk: An Approach Based on Learning Automata. Springer, 2019. p. 1-7.
[24] A. Enami, J.A. Torkestani, A. Karimi. Resource selection in computational grids based on learning automata. Expert Systems with Applications. 125 (2019) 369-77.
[25] S. Bitam, S. Zeadally, A. Mellouk. Fog computing job scheduling optimization based on bees swarm. Enterprise Information Systems. 12 (2018) 373-97.
[26] E. Ghaffari. Providing a new scheduling method in fog network using the ant colony algorithm. Collection of Articles on Computer Science. (2019).
[27] S.B. Akintoye, A. Bagula. Improving quality-of-service in cloud/fog computing through efficient resource allocation. Sensors. 19 (2019) 1267.
[28] G. Li, Y. Liu, J. Wu, D. Lin, S. Zhao. Methods of resource scheduling based on optimized fuzzy clustering in fog computing. Sensors. 19 (2019) 2122.
[29] J. Wang, D. Li. Task scheduling based on a hybrid heuristic algorithm for smart production line with fog computing. Sensors. 19 (2019) 1023.
[30] W.-C. Yeh, C.-M. Lai, K.-C. Tseng. Fog computing task scheduling optimization based on multi-objective simplified swarm optimization. Journal of Physics: Conference Series. IOP Publishing, 2019. p. 012007.
[31] H. Wang, L. Wang, Z. Zhou, X. Tao, G. Pau, F. Arena. Blockchain-Based Resource Allocation Model in Fog Computing. Applied Sciences. 9 (2019) 5538.
[32] L. Yin, J. Luo, H. Luo. Tasks scheduling and resource allocation in fog computing based on containers for smart manufacturing. IEEE Transactions on Industrial Informatics. 14 (2018) 4712-21.
[33] H. Zhang, Y. Xiao, S. Bu, D. Niyato, F.R. Yu, Z. Han. Computing resource allocation in three-tier IoT fog networks: A joint optimization approach combining Stackelberg game and matching. IEEE Internet of Things Journal. 4 (2017) 1204-15.
[34] S. Jošilo, G. Dán. Decentralized algorithm for randomized task allocation in fog computing systems. IEEE/ACM Transactions on Networking. 27 (2018) 85-97.
[35] M. Mtshali, H. Kobo, S. Dlamini, M. Adigun, P. Mudali. Multi-Objective Optimization Approach for Task Scheduling in Fog Computing. 2019 International Conference on Advances in Big Data, Computing and Data Communication Systems (icABCD). IEEE, 2019. p. 1-6.
[36] X. Xu, S. Fu, Q. Cai, W. Tian, W. Liu, W. Dou, et al. Dynamic resource allocation for load balancing in fog environment. Wireless Communications and Mobile Computing. 2018 (2018).
[37] M. Thathachar, B.R. Harita. Learning automata with changing number of actions. IEEE Transactions on Systems, Man, and Cybernetics. 17 (1987) 1095-100.
[38] M. Thathachar, K. Narendra. Learning Automata: an Introduction, 1989.
[39] H. Gupta, A. Vahid Dastjerdi, S.K. Ghosh, R. Buyya. iFogSim: A toolkit for modeling and simulation of resource management techniques in the Internet of Things, Edge and Fog computing environments. Software: Practice and Experience. 47 (2017) 1275-96.
