IIoT环境下基于蜣螂优化的雾工作流调度算法

doi:10.3778/j.issn.1002-8331.2402-0102

摘要/Abstract

摘要： 为了解决在工业物联网（industrial Internet of things，IIoT）环境下，现有的调度算法在调度工作流中对数据安全、响应时间有一定要求的任务所带来的完工时间上升、成本增加的问题，提出一种基于雾环境负载率而变化的任务调度策略，并使用改进的蜣螂优化算法对工作流调度问题进行求解。改进的算法使用HEFT（heterogeneous earliest finish time）算法对蜣螂种群进行初始化，降低了原始算法中随机性带来的影响。同时引入了镜面反射和反向学习思想，提高了算法的搜索性能。实验结果表明，该算法相比于其他一些传统的调度算法在完工时间与成本方面都有一定的性能提升。

关键词: 工作流调度, 蜣螂优化算法, HEFT算法, 反向学习, 调度算法, 雾计算, 工业物联网（IIoT）

Abstract: To solve the problem of increasing makespan and cost caused by existing scheduling algorithms for scheduling tasks in workflows with certain requirements on data security and response time in the IIoT (industrial Internet of things) environment, a task scheduling policy that changes based on the load rate of the fog environment is proposed, and the workflow scheduling problem is solved by using a dung beetle optimizer algorithm. The improved algorithm uses the HEFT (heterogeneous earliest finish time) algorithm to initialize the dung beetle population, which reduces the effect of randomness in the original algorithm. Meanwhile, the algorithm introduces the ideas of mirror reflection and opposition-based learning to improve the search performance of the algorithm. The experimental results show that the algorithm has some improvement in makespan and cost compared with some other traditional scheduling algorithms.

Key words: workflow scheduling, dung beetle optimizer algorithm, HEFT algorithm, opposition-based learning, scheduling algorithm, fog computing, industrial Internet of things (IIoT)

吴宏伟, 江凌云. IIoT环境下基于蜣螂优化的雾工作流调度算法[J]. 计算机工程与应用, 2025, 61(10): 341-349.

WU Hongwei, JIANG Lingyun. Fog Workflow Scheduling Algorithm Based on Dung Beetle Optimizer in IIoT Environment[J]. Computer Engineering and Applications, 2025, 61(10): 341-349.

参考文献

[1] AAZAM M, ZEADALLY S, HARRAS K A. Deploying fog computing in industrial Internet of things and industry 4.0[J]. IEEE Transactions on Industrial Informatics, 2018, 14(10): 4674-4682.
[2] QIU T, CHI J C, ZHOU X B, et al. Edge computing in industrial Internet of things: architecture, advances and challenges[J]. IEEE Communications Surveys & Tutorials, 2020, 22(4): 2462-2488.
[3] MUKHERJEE M, SHU L, WANG D. Survey of fog computing: fundamental, network applications, and research challenges[J]. IEEE Communications Surveys & Tutorials, 2018, 20(3): 1826-1857.
[4] HU W, LI X P, LI X. Hybrid cloud workflow scheduling method with privacy data[J]. IEEE Access, 2020, 8: 211540-211552.
[5] SHISHIDO H Y, ESTRELLA J C, TOLEDO C F M, et al. Optimizing security and cost of workflow execution using task annotation and genetic-based algorithm[J]. Computing, 2021, 103(6): 1281-1303.
[6] ABAZARI F, ANALOUI M, TAKABI H, et al. MOWS: multi-objective workflow scheduling in cloud computing based on heuristic algorithm[J]. Simulation Modelling Practice and Theory, 2019, 93: 119-132.
[7] MOHAMMADZADEH A, MASDARI M, GHAREHCHOPOGH F S, et al. A hybrid multi-objective metaheuristic optimization algorithm for scientific workflow scheduling[J]. Cluster Computing, 2021, 24(2): 1479-1503.
[8] AHMED O H, LU J, AHMED A M, et al. Scheduling of scientific workflows in multi-fog environments using Markov models and a hybrid salp swarm algorithm[J]. IEEE Access, 2020, 8: 189404-189422.
[9] MOKNI M, YASSA S, HAJLAOUI J E, et al. Cooperative agents-based approach for workflow scheduling on fog-cloud computing[J]. Journal of Ambient Intelligence and Humanized Computing, 2022, 13(10): 4719-4738.
[10] AHMED O H, LU J, XU Q, et al. Using differential evolution and moth-flame optimization for scientific workflow scheduling in fog computing[J]. Applied Soft Computing, 2021, 112: 107744.
[11] LIU M T, YU F R, TENG Y L, et al. Performance optimization for blockchain-enabled industrial Internet of things (IIoT) systems: a deep reinforcement learning approach[J]. IEEE Transactions on Industrial Informatics, 2019, 15(6): 3559-3570.
[12] WAN J F, LI J P, IMRAN M, et al. A blockchain-based solution for enhancing security and privacy in smart factory[J]. IEEE Transactions on Industrial Informatics, 2019, 15(6): 3652-3660.
[13] DAI Y Y, ZHANG K, MAHARJAN S, et al. Deep reinforcement learning for stochastic computation offloading in digital twin networks[J]. IEEE Transactions on Industrial Informatics, 2021, 17(7): 4968-4977.
[14] SREE T R. Role of fog-assisted industrial Internet of things: a systematic review[J]. Transactions on Emerging Telecommunications Technologies, 2022, 33(12): e4611.
[15] 田倬璟, 黄震春, 张益农. 云计算环境任务调度方法研究综述[J]. 计算机工程与应用, 2021, 57(2): 1-11.
TIAN Z J, HUANG Z C, ZHANG Y N. Review of task scheduling methods in cloud computing environment[J]. Computer Engineering and Applications, 2021, 57(2): 1-11.
[16] LAKHAN A, MASTOI Q U A, ALI DOOTIO M, et al. Hybrid workload enabled and secure healthcare monitoring sensing framework in distributed fog-cloud network[J]. Electronics, 2021, 10(16): 1974.
[17] 刘洋睿, 江凌云. 基于动态资源选择策略的微服务工作流调度算法[J]. 计算机工程与设计, 2023, 44(5): 1313-1319.
LIU Y R, JIANG L Y. Microservice workflow scheduling algorithm based on dynamic resource selection strategy[J]. Computer Engineering and Design, 2023, 44(5): 1313-1319.
[18] 王子健, 卢政昊, 潘纪奎, 等. 最后期限动态分配的三步云工作流调度算法[J]. 小型微型计算机系统, 2023, 44(2): 248-255.
WANG Z J, LU Z H, PAN J K, et al. Three-step cloud workflow scheduling algorithm based on dynamic deadline distribution[J]. Journal of Chinese Computer Systems, 2023, 44(2): 248-255.
[19] 杨乾龙, 江凌云. 基于机器学习的微服务负载均衡算法研究[J]. 计算机科学, 2023, 50(5): 313-321.
YANG Q L, JIANG L Y. Study on load balancing algorithm of microservices based on machine learning[J]. Computer Science, 2023, 50(5): 313-321.
[20] KHOSO F H, KEHAR A. Proposing a novel IoT framework by identifying security and privacy issues in fog cloud services network[J]. International Journal of Emerging Trends in Engineering Research, 2021, 9(5): 592-596.
[21] XUE J K, SHEN B. Dung beetle optimizer: a new meta-heuristic algorithm for global optimization[J]. The Journal of Supercomputing, 2023, 79(7): 7305-7336.
[22] HAI T, ZHOU J C, JAWAWI D, et al. Task scheduling in cloud environment: optimization, security prioritization and processor selection schemes[J]. Journal of Cloud Computing, 2023, 12(1): 15.
[23] MAHDAVI S, RAHNAMAYAN S, DEB K. Opposition based learning: a literature review[J]. Swarm and Evolutionary Computation, 2018, 39: 1-23.
[24] RANI R, GARG R. Power and temperature-aware workflow scheduling considering deadline constraint in cloud[J]. Arabian Journal for Science and Engineering, 2020, 45(12): 10775-10791.
[25] LIU X, FAN L M, XU J, et al. FogWorkflowSim: an automated simulation toolkit for workflow performance evaluation in fog computing[C]//Proceedings of the 2019 34th IEEE/ACM International Conference on Automated Software Engineering. Piscataway: IEEE, 2019: 1114-1117.
[26] HALMAN N, KOVALYOV M Y, QUILLIOT A. Max-max, max-min, min-max and min-min knapsack problems with a parametric constraint[J]. 4OR: A Quarterly Journal of Operations Research, 2023, 21(2): 235-246.
[27] TOOR W T, SEO J B, JIN H. Practical splitting algorithm for multi-channel slotted random access systems[J]. IEEE Transactions on Mobile Computing, 2020, 19(12): 2863-2873.
[28] ABED-ALGUNI B H, ALAWAD N A. Distributed grey wolf optimizer for scheduling of workflow applications in cloud environments[J]. Applied Soft Computing, 2021, 102: 107113.