NSGAII-based task scheduling model for smart city applications in cloud-fog environment

Document Type : Persian Original Article

Authors

Department of Computer Engineering and Information Technology, University of Qom, Qom, Iran

Abstract

The advent of Internet of Things (IoT) technology has led to the concept of the smart city, in which smart devices are recognized as a necessity. The applications installed on these devices generate large volumes of data that often require real-time processing. However, these devices have limited capabilities and are not capable of processing large amounts of data. Moving all this data to cloud data centers results in higher bandwidth usage, latency, cost and energy consumption. Therefore, providing services to delay-sensitive smart city applications in the cloud is a challenging issue, and meeting the requirements of these applications requires the use of a hybrid cloud and fog paradigm. Fog computing as a complement to the cloud allows data to be processed near smart devices. However, the resources in the fog layer are heterogeneous and have different capabilities, hence, appropriate scheduling of these resources is of great importance. In this paper, the problem of task scheduling for the smart city applications in the cloud-fog environment has been addressed. To this purpose, the task scheduling problem has been modeled as a multi-objective optimization problem, which aims to minimize service delay and energy consumption of the system under deadline constraint. Then, in order to solve this problem and achieve an appropriate scheduling strategy, non-dominated sorting genetic algorithm II (NSGA-II) with customized operators has been applied. In addition, in order to improve the diversity of the population and the convergence speed of the proposed algorithm, a combination of chaotic map and opposition-based learning methods have been used to generate the initial population. Also, the approach based on the penalty function has been employed to penalize the solutions that do not meet the deadline constraint. The simulation results reveal that the proposed scheduling algorithm, compared to its best competitor, improves service response delay, waiting time, execution delay and system energy consumption by 1.49%, 1.70%, 2.7% and 1.86%, respectively. Furthermore, by properly assigning tasks to the computing nodes, compared to the best competitor, the percentage of missed-deadline tasks is reduced by 1.89%.

Keywords

References

[1] Tang, B., Chen, Z., Hefferman, G., Pei, S., Wei, T., He, H. and Yang, Q., “Incorporating intelligence in fog computing for big data analysis in smart cities” IEEE Transactions on Industrial informatics, 13(5), pp.2140-2150, 2017.
[2] Dong, Y., Guo, S., Liu, J. and Yang, Y., “Energy-efficient fair cooperation fog computing in mobile edge networks for smart city” IEEE Internet of Things Journal, 6(5), pp.7543-7554, 2019.
[3] Fiandrino, C., Anjomshoa, F., Kantarci, B., Kliazovich, D., Bouvry, P. and Matthews, J.N., “Sociability-driven framework for data acquisition in mobile crowdsensing over fog computing platforms for smart cities” IEEE Transactions on Sustainable Computing, 2(4), pp.345-358, 2017.
[4] Liu, Q., Wei, Y., Leng, S. and Chen, Y., October. “Task scheduling in fog enabled Internet of Things for smart cities” In 2017 IEEE 17th International Conference on Communication Technology (ICCT) (pp. 975-980), IEEE, 2017.
[5] Desikan, K.S., Kotagi, V.J. and Murthy, C.S.R., September. “Smart at right price: A cost efficient topology construction for fog computing enabled iot networks in smart cities” In 2018 IEEE 29th Annual International Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC) (pp. 1-7), IEEE, 2018.
[6] Liao, S., Dong, M., Ota, K., Wu, J., Li, J. and Ye, T., December. “Vehicle mobility-based geographical migration of fog resource for satellite-enabled smart cities” In 2018 IEEE Global Communications Conference (GLOBECOM) (pp. 1-6). IEEE, 2018.
[7] Deng, R., Lu, R., Lai, C., Luan, T.H. and Liang, H. “Optimal workload allocation in fog-cloud computing toward balanced delay and power consumption” IEEE internet of things journal, 3(6), pp.1171-1181, 2016.
[8] Mahmud, R., Kotagiri, R. and Buyya, R., “Fog computing: A taxonomy, survey and future directions” In Internet of everything (pp. 103-130). Springer, Singapore, 2018.
[9] Yousefpour, A., Fung, C., Nguyen, T., Kadiyala, K., Jalali, F., Niakanlahiji, A., Kong, J. and Jue, J.P., “All one needs to know about fog computing and related edge computing paradigms: A complete survey” Journal of Systems Architecture, 98, pp.289-330, 2019.
[10] Stojmenovic, I. and Wen, S., “The fog computing paradigm: Scenarios and security issues” In 2014 federated conference on computer science and information systems (pp. 1-8). IEEE, 2014.
[11] Bittencourt, L.F., Diaz-Montes, J., Buyya, R., Rana, O.F. and Parashar, M., “Mobility-aware application scheduling in fog computing” IEEE Cloud Computing, 4(2), pp.26-35, 2017.
[12] Pham, X.Q. and Huh, E.N., “Towards task scheduling in a cloud-fog computing system” In 2016 18th Asia-Pacific network operations and management symposium (APNOMS) (pp. 1-4). IEEE, 2016.
[13] Jennings, B. and Stadler, R., “Resource management in clouds: Survey and research challenges” Journal of Network and Systems Management, 23(3), pp.567-619, 2015.
[14] Basu, S., Karuppiah, M., Selvakumar, K., Li, K.C., Islam, S.H., Hassan, M.M. and Bhuiyan, M.Z.A., “An intelligent/cognitive model of task scheduling for IoT applications in cloud computing environment” Future Generation Computer Systems, 88, pp.254-261, 2018.
[15] Aburukba, R.O., AliKarrar, M., Landolsi, T. and El-Fakih, K., “Scheduling Internet of Things requests to minimize latency in hybrid Fog–Cloud​ computing” Future Generation Computer Systems, 111, pp.539-551, 2020.
[16] Xu, J., Hao, Z., Zhang, R. and Sun, X., “A method based on the combination of laxity and ant colony system for cloud-fog task scheduling” IEEE Access, 7, pp.116218-116226, 2019.
[17] Zhan, Z.H., Liu, X.F., Gong, Y.J., Zhang, J., Chung, H.S.H. and Li, Y., “Cloud computing resource scheduling and a survey of its evolutionary approaches” ACM Computing Surveys (CSUR), 47(4), pp.1-33, 2015.
[18] Zhou, A., Qu, B.Y., Li, H., Zhao, S.Z., Suganthan, P.N. and Zhang, Q., “Multiobjective evolutionary algorithms: A survey of the state of the art” Swarm and Evolutionary Computation, 1(1), pp.32-49, 2011.
[19] Deb, K., Pratap, A., Agarwal, S. and Meyarivan, T.A.M.T., “A fast and elitist multiobjective genetic algorithm: NSGA-II” IEEE transactions on evolutionary computation, 6(2), pp.182-197, 2002.
[20] Xu, X., Liu, X., Xu, Z., Dai, F., Zhang, X. and Qi, L., “Trust-oriented IoT service placement for smart cities in edge computing” IEEE Internet of Things Journal, 7(5), pp.4084-4091, 2019.
[21] Xu, X., Huang, Q., Yin, X., Abbasi, M., Khosravi, M.R. and Qi, L., “Intelligent offloading for collaborative smart city services in edge computing” IEEE Internet of Things Journal, 7(9), pp.7919-7927, 2020.
[22] Naranjo, P.G.V., Pooranian, Z., Shojafar, M., Conti, M. and Buyya, R., “FOCAN: A Fog-supported smart city network architecture for management of applications in the Internet of Everything environments” Journal of Parallel and Distributed Computing, 132, pp.274-283, 2019.
[23] Tang, C., Wei, X., Zhu, C., Wang, Y. and Jia, W., “Mobile vehicles as fog nodes for latency optimization in smart cities” IEEE Transactions on Vehicular Technology, 69(9), pp.9364-9375, 2020.
[24] Hosseinioun, P., Kheirabadi, M., Tabbakh, S.R.K. and Ghaemi, R., “A new energy-aware tasks scheduling approach in fog computing using hybrid meta-heuristic algorithm” Journal of Parallel and Distributed Computing, 143, pp.88-96, 2020.
[25] Hosseinzadeh, M., Masdari, M., Rahmani, A.M., Mohammadi, M., Aldalwie, A.H.M., Majeed, M.K. and Karim, S.H.T., “Improved Butterfly Optimization Algorithm for Data Placement and Scheduling in Edge Computing Environments” Journal of Grid Computing, 19(2), pp.1-27, 2021.
[26] Tanha, M., Hosseini Shirvani, M. and Rahmani, A.M., 2021. A hybrid meta-heuristic task scheduling algorithm based on genetic and thermodynamic simulated annealing algorithms in cloud computing environments. Neural Computing and Applications, 33(24), pp.16951-16984.
[27] Ghanavati, S., Abawajy, J.H. and Izadi, D., “An Energy Aware Task Scheduling Model Using Ant-Mating Optimization in Fog Computing Environment” IEEE Transactions on Services Computing, 2020.
[28] Bitam, S., Zeadally, S. and Mellouk, A., “Fog computing job scheduling optimization based on bees swarm” Enterprise Information Systems, 12(4), pp.373-397, 2018.
[29] Kumar, A.S. and Venkatesan, M., “Multi-objective task scheduling using hybrid genetic-ant colony optimization algorithm in cloud environment” Wireless Personal Communications, 107(4), pp.1835-1848, 2019.
[30] Shahryari, O.K., Pedram, H., Khajehvand, V. and TakhtFooladi, M.D., “Energy and task completion time trade-off for task offloading in fog-enabled IoT networks” Pervasive and Mobile Computing, p.101395, 2021.
[31] Huang, T., Lin, W., Xiong, C., Pan, R. and Huang, J., 2020. An ant colony optimization-based multiobjective service replicas placement strategy for fog computing. IEEE Transactions on Cybernetics.
[32] Memari, P., Mohammadi, S.S., Jolai, F. and Tavakkoli-Moghaddam, R., 2022. A latency-aware task scheduling algorithm for allocating virtual machines in a cost-effective and time-sensitive fog-cloud architecture. The Journal of Supercomputing, 78(1), pp.93-122.
[33] Zade, B.M.H., Mansouri, N. and Javidi, M.M., 2021. SAEA: A security-aware and energy-aware task scheduling strategy by Parallel Squirrel Search Algorithm in cloud environment. Expert Systems with Applications, 176, p.114915.
[34] Dubey, K. and Sharma, S.C., 2021. A novel multi-objective CR-PSO task scheduling algorithm with deadline constraint in cloud computing. Sustainable Computing: Informatics and Systems, 32, p.100605.
[35] Abd Elaziz, M., Abualigah, L. and Attiya, I., 2021. Advanced optimization technique for scheduling IoT tasks in cloud-fog computing environments. Future Generation Computer Systems.
[36] Nguyen, B.M., Thi Thanh Binh, H. and Do Son, B., “Evolutionary algorithms to optimize task scheduling problem for the IoT based bag-of-tasks application in cloud–fog computing environment”, Applied Sciences, 9(9), p.1730, 2019.
[37] Ali, I.M., Sallam, K.M., Moustafa, N., Chakraborty, R., Ryan, M.J. and Choo, K.K.R., “An Automated Task Scheduling Model using Non-Dominated Sorting Genetic Algorithm II for Fog-Cloud Systems” IEEE Transactions on Cloud Computing, 2020.
[38] Tsegaye, A. and Assefa, B.G., 2021, November. HSSIW: Hybrid Squirrel Search and Invasive Weed Based Cost-Makespan Task Scheduling for Fog-Cloud Environment. In 2021 International Conference on Information and Communication Technology for Development for Africa (ICT4DA) (pp. 160-165). IEEE.
[39] Wang, Y., Lang, P., Tian, D., Zhou, J., Duan, X., Cao, Y. and Zhao, D., “A game-based computation offloading method in vehicular multiaccess edge computing networks” IEEE Internet of Things Journal, 7(6), pp.4987-4996, 2020.
[40] Han, S., Xu, X., Fang, S., Sun, Y., Cao, Y., Tao, X. and Zhang, P., “Energy efficient secure computation offloading in NOMA-based mMTC networks for IoT” IEEE Internet of Things Journal, 6(3), pp.5674-5690, 2019.
[41] Guerrero, C., Lera, I. and Juiz, C. Evaluation and efficiency comparison of evolutionary algorithms for service placement optimization in fog architectures. Future Generation Computer Systems, 97, pp.131-144, 2019.
[42] Li, Q., Liu, S.Y. and Yang, X.S. “Influence of initialization on the performance of metaheuristic optimizers”. Applied Soft Computing, 91, p.106193, 2020.
[43] Truong, Khoa H., et al. "A quasi-oppositional-chaotic symbiotic organisms search algorithm for global optimization problems." Applied Soft Computing 77,567-583, (2019).
[44] Salimi, R., Motameni, H. and Omranpour, H., “Task scheduling using NSGA II with fuzzy adaptive operators for computational grids” Journal of Parallel and Distributed Computing, 74(5), pp.2333-2350, 2014.
[45] Sivanandam, S.N. and Deepa, S.N., “Genetic algorithms” In Introduction to genetic algorithms (pp. 15-37). Springer, Berlin, Heidelberg, 2008.
[46] Du, K.L. and Swamy, M.N.S., “Particle swarm optimization” In Search and optimization by metaheuristics (pp. 153-173). Birkhäuser, Cham, 2016.
[47] Safe, M., Carballido, J., Ponzoni, I. and Brignole, N., September. “On stopping criteria for genetic algorithms” In Brazilian Symposium on Artificial Intelligence (pp. 405-413). Springer, Berlin, Heidelberg, 2004.
[48] T. SimPy, Simpy: Discrete event simulation for python, Tech. Rep. 9, 2017, URL https://simpy.readthedocs.io/en/latest/.
[49] Gazori, Pegah, Dadmehr Rahbari, and Mohsen Nickray. "Saving time and cost on the scheduling of fog-based IoT applications using deep reinforcement learning approach." Future Generation Computer Systems 110, pp.1098-1115, 2020.
[50] Rajput, I.S. and Gupta, D., “A priority based round robin CPU scheduling algorithm for real time systems” International Journal of Innovations in Engineering and Technology, 1(3), pp.1-11, 2012.
[51] Zhu, Q., Si, B., Yang, F. and Ma, Y., “Task offloading decision in fog computing system” China Communications, 14(11), pp.59-68, 2017.
[52] Wang, L., Fu, X., Mao, Y., Menhas, M.I. and Fei, M., 2012. A novel modified binary differential evolution algorithm and its applications. Neurocomputing, 98, pp.55-75.
Journal of Soft Computing and Information Technology
Volume 11, Issue 3 - Serial Number 37
Autumn
December 2023
Pages 64-82

Files

Share

How to cite

Statistics