An approach based on fog nodes collaboration and lottery algorithm for deadline-aware task placement and scheduling in fog computing

Document Type : Persian Original Article

Authors

1 University of Sistan and Baluchestan

2 Information Technology Department, Faculty of Electrical and Computer Engineering, University of Sistan and Baluchestan, Zahedan, Iran.

3 Department of Information Technology Engineering, Faculty of Electrical and Computer Engineering, University of Sistan & Baluchestan, Zahedan, Iran

Abstract

Fog computing is a distributed computing paradigm that extends the cloud services to the edge of the network to support real-time and delay-sensitive applications. One of the main issues in fog computing is how to effectively and fairly allocate the restricted resources of fog nodes to users' requests. The limited number of resources, the different requirements of user requests, and latency requirement of delay-sensitive applications have made resource allocation and scheduling challenging. This paper proposes an efficient approach for the placement and scheduling of deadline-aware tasks in fog computing. In the proposed approach, task placement is done with the collaboration of fog nodes and based on the estimation of the completion time of a request in different fog nodes. The lottery algorithm is also used for task scheduling, and the requests are prioritized based on their deadlines. The experimental results show that the combination of fog nodes collaboration for task placement and the lottery algorithm for scheduling reduces the response time and increases the acceptance ratio of user requests. According to the simulation results, the acceptance ratio and the response time of the proposed approach improved by 12.72% and 37.97 ms, respectively, compared to the baseline method that uses the FCFS algorithm for task scheduling. Also, in comparison with the existing approaches which use a central controller for fog nodes collaboration, the proposed approach increased the acceptance ratio by 2.57%, and decreased the response time by 20.42 ms.

Keywords

References

[1] O. Skarlat, M. Nardelli, S. Schulte, M. Borkowski and P. Leitner, "Optimized IoT service placement in the fog," Service Oriented Computing and Applications, Vol. 11, No. 4, pp. 427-443, 2017.
[2] O. Skarlat and S. Schulte, "FogFrame: a framework for IoT application execution in the fog," PeerJ Computer Science, Vol. 7, pp. e588, 2021.
[3] J. Nie, J. Luo and L. Yin, "Energy-aware Multi-dimensional Resource Allocation Algorithm in Cloud Data Center", Ksii Transactions on Internet & Information Systems, Vol. 11, No. 9, 2017.
[4] EH. Houssein, AG. Gad, YM. Wazery PN.and Suganthan, "Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends," Swarm and Evolutionary Computation, Vol. 62, pp.100841, 2021.
[5] PK. Bal, SK. Mohapatra, TK. Das, K. Srinivasan and YC. Hu, "A Joint Resource Allocation, Security with Efficient Task Scheduling in Cloud Computing Using Hybrid Machine Learning Techniques," Sensors, Vol. 22, No. 3, pp. 1242, 2022.
[6] AM. Yadav, KN. Tripathi and SC Sharma, "An enhanced multi-objective fireworks algorithm for task scheduling in fog computing environment," Cluster Computing, Vol. 25, No. 2, pp. 983-98, 2022.
[7] J. Gu, J. Mo, B. Li, Y. Zhang and W. Wang, "A multi-objective fog computing task scheduling strategy based on ant colony algorithm," In 2021 IEEE 4th International Conference on Information Systems and Computer Aided Education (ICISCAE), pp. 12-16, 2021.
[8] N. Potu, C. Jatoth, and P. Parvataneni, "Optimizing resource scheduling based on extended particle swarm optimization in fog computing environments,"Concurrency and Computation: Practice and Experience, Vol. 33, No. 23, pp. e6163, 2021.
[9] K.P.N. Jayasena and B.S. Thisarasinghe, “Optimized task scheduling on fog computing environment using meta heuristic algorithms,” In 2019 IEEE International Conference on Smart Cloud (SmartCloud), pp. 53-58, 2019.
[10] M. Abd Elaziz, L. Abualigah and I. Attiya, “Advanced optimization technique for scheduling IoT tasks in cloud-fog computing environments,” Future Generation Computer Systems, 2021.
[11] M. Verma, N. Bhardwaj and A.K. Yadav, "Real Time Efficient Scheduling Algorithm for Load Balancing in Fog Computing Environment," I.J. Information Technology and Computer Science," Vol. 8, No. 4, pp. 1-10, 2016.
[12] T. Choudhari, M. Moh and T.S. Moh, “Prioritized task scheduling in fog computing,” In Proceedings of the ACMSE 2018 Conference, pp. 1-8, 2018.
[13] Y. Xiao and  M. Krunz, "QoE and power efficiency tradeoff for fog computing networks with fog node cooperation," IEEE INFOCOM 2017-IEEE Conference on Computer Communications, pp. 1-9, 2017.
[14] S. Azizi, F. Khosroabadi and M. Shojafar, "A priority-based service placement policy for fog-cloud computing systems," Computational Methods for Differential Equations, No. 4 (Special Issue), pp. 521-34, 2019.
[15] C. Guerrero, I. Lera, C. Juiz, "On the influence of fog colonies partitioning in fog application  makespan," In IEEE International Conference on Future Internet of Things and Cloud (FiCloud), pp. 377-384, 2018.
[16] P. Maiti, B. Sahoo, A.K. Turuk, A. Kumar and B.J. Choi, “Internet of Things applications placement to minimize latency in multi-tier fog computing framework,” ICT Express, 2021.
[17] S. Wang, T. Zhao and S. Pang, “Task scheduling algorithm based on improved firework algorithm in fog computing,” IEEE Access, 8, pp. 32385-32394, 2020.
[18] O. Consortium, "OpenFog reference architecture for fog computing," Architecture Working Group, pp. 1-162, 2017.
[19] RN. Calheiros, R. Ranjan, A. Beloglazov, CA. De Rose and R. Buyya, "CloudSim: a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms," Software: Practice and experience, Vol. 41, No. 1, pp. 23-50, 2011.
[20] H.E. Refaat and M.A. Mead, "DLBS: Decentralize Load-Balance Scheduling Algorithm for Real-Time IoT Services in Mist Computing," Editorial Preface from the Desk of Managing Editor, Vol. 10, No. 9, 2019.
[21] A. Khalid and M. Shahbaz, "Service Architecture Models For Fog Computing: A Remedy for Latency Issues in Data Access from Clouds," TIIS, Vol. 11, No. 5, pp. 2310-2345, 2017.
Journal of Soft Computing and Information Technology
Volume 11, Issue 2 - Serial Number 36
Summer
September 2022
Pages 64-75

Files

Share

How to cite

Statistics