ارائه‌ی یک مدل زمان‌بندی وظایف مبتنی بر الگوریتم ژنتیک چند هدفه با مرتب‌سازی نامغلوب برای برنامه‌های کاربردی شهر هوشمند در محیط ابر-مه

نوع مقاله : مقاله پژوهشی فارسی

نویسندگان

1 دانشکده مهندسی کامپیوتر و فناوری اطلاعات، دانشگاه قم، قم، ایران

2 دانشکده مهندسی کامپیوتر و فن آوری اطلاعات، دانشگاه قم، قم، ایران

چکیده

ظهور تکنولوژی اینترنت اشیا مفهوم شهر هوشمند را ایجاد کرده که در این پارادایم، دستگاه‌های هوشمند به عنوان یک ضرورت شناخته می‌شوند. برنامه‌های کاربردی نصب‌شده بر روی این دستگاه‌ها باعث تولید حجم زیادی داده می‌شوند که اغلب نیازمند پردازش بلادرنگ می‌باشند. بااین‌حال، این دستگاه‌ها دارای قابلیت‌های محدودی هستند و قادر به پردازش حجم زیاد داده‌ها نمی‌باشند. انتقال همه‌ی این داده‌ها به مراکز داده‌ی ابری منجر به استفاده از پهنای باند، تاخیر، هزینه و مصرف انرژی بیشتر می‌شود. ازاین‌رو، ارائه‌ خدمات به برنامه‌های کاربردی شهر هوشمند حساس به تاخیر در ابر یک موضوع چالش برانگیز است و پاسخگویی به نیازمندی‌های این برنامه‌ها، مستلزم استفاده از پارادایم ترکیبی ابر و مه می‌باشد. رایانش مه به عنوان مکملی برای ابر امکان می‌دهد تا داده‌ها در نزدیکی دستگاه‌های هوشمند پردازش شوند. بااین‌حال، منابع موجود در لایه‌ی مه ناهمگن و دارای قابلیت‌های متفاوتی می‌باشند، بنابراین زمان‌بندی مناسب این منابع از اهمیت زیادی برخوردار است. در این مقاله، به مسأله‌ی زمان‌بندی وظایف برای برنامه‌های کاربردی شهر هوشمند در محیط ابر-مه پرداخته شده‌است. به این منظور، مسأله‌ی زمان‌بندی وظیفه به صورت یک مسأله‌ی بهینه‌سازی چند هدفه مدل شده‌است که اهداف آن، کاهش تاخیر ارائه‌ی خدمات و مصرف انرژی سیستم با در نظر گرفتن قید مهلت زمانی می‌باشد. سپس به منظور حل این مسأله و دستیابی به استراتژی زمان‌بندی مناسب، الگوریتم ژنتیک چند هدفه با مرتب‌سازی نامغلوب با اپراتورهای سفارشی به کار گرفته شده‌است. علاوه‌براین، به منظور بهبود تنوع جمعیت و سرعت همگرایی الگوریتم پیشنهادی، برای تولید جمعیت اولیه از ترکیب روش‌های نگاشت بی‌نظمی و یادگیری مبتنی بر تضاد استفاده ‌شده‌است. همچنین رویکرد مبتنی بر تابع جریمه برای راه‌حل‌هایی که قید مهلت زمانی را برآورده نمی‌کنند، به کار گرفته شده‌است. نتایج شبیه‌سازی‌ها نشان می‌دهد که الگوریتم زمان‌بندی پیشنهادی، در مقایسه با بهترین رقیب خود، تاخیر ارائه‌ی خدمات، زمان انتظار، تاخیر اجرای وظیفه و مصرف انرژی سیستم را به ترتیب 1/49، 1/70، 2/7 و 1/86 درصد بهبود می‌دهد. علاوه‌براین، با تخصیص مناسب وظایف به گره‌های محاسباتی در مقایسه با بهترین رقیب، درصد وظایفی که مهلت زمانیشان را از دست می‌دهند به میزان 1/89 درصد کاهش می‌دهد.

کلیدواژه‌ها


[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.