| With the advent of the Internet of Everything era,more and more workflows contain a large number of real-time IoT data processing tasks,such as workflow applications in smart cities,intelligent transportation and other application scenarios.In order to improve the execution efficiency of workflow and make full use of computing resources,it is inevitable to use cloud-edge collaboration to schedule and execute workflow.However,in the cloud-edge collaborative environment,the scheduling and execution of IoT workflows will face many challenges.For example,IoT data is always expressed as continuous stream data,so IoT workflows need to be repeatedly executed;at the same time,the dynamic nature of IoT data will also affect the workload of workflow tasks.Long-term use of the static scheduling algorithm will bring greater cost and time delay.In this case,applying the online scheduling algorithm becomes an effective way to reduce the influence of the workload dynamics and to schedule workflows more efficiently.As far as the existing dynamic scheduling and online scheduling algorithms,most of them focus on the fluctuation of computing resources in the scheduling process,while ignoring the dynamic characteristics of streaming workflow load.The fluctuation of task load will affect the task execution time and communication cost,and even lead to partial data loss.If the scheduling scheme cannot be adjusted according to the load change in time,it will bring unpredictable cost to the entire workflow execution.Aiming at the scheduling uncertainty in the continuous scheduling process of workflow,which is caused by the dynamic changes of the IoT data,this paper proposes a load-sensitive online workflow scheduling algorithm,which is named LAPT(Load Aware Plan Tuning).Compared with the existing scheduling strategies,the LAPT strategy has the following advantages:1)Introducing the task migration cost into the optimization objective.By this operation,the change of the task execution position in the two consecutive scheduling can be limited as much as possible,so as to ensure the stability of the plan and reduce the deployment cost.2)The scheduling strategy adopts a two-stage method,which combines genetic algorithm and local search algorithm.First,the genetic algorithm is used to find the approximate optimal solution,and then when the change of the data generation rate of the workflow data source is greater than 20%,the local search algorithm is used to update the scheduling plan.The scheduling strategy reduces the scheduling time and meets the real-time requirements of workflow scheduling.In order to further improve the quality of the local optimal solution in the second stage of the LAPT strategy,we propose an improved P-LAPT algorithm(Predictivebased Load Aware Plan Tuning).From the perspective of big data,we use a large number of workflow instances and the corresponding optimal scheduling plans(which are obtained based optimization algorithms,such as GA,NSGA and etc.)to train Seq2Seq model,we obtain a model that can predict the scheduling plan.In the second stage of the LAPT strategy,the predicted optimal solution is added to the continuous scheduling,and the local search is changed to multi-neighborhood local search.By expanding the search space in a targeted manner,the quality of the scheduling plan is optimized.In this paper,we carry out the experiments on the improved WorkflowSim,and a large number of workflows that generated by the DAG generation algorithm are used for the experimental verification.By embedding different algorithms in the predictivebased method,the quality of the predictive solution is evaluated.At the same time,compared with several existing scheduling methods,it is found that the method proposed in this paper can adapt to IoT data rate changes,and quickly generate a less expensive scheduling plan.These two methods achieve overall better performance in execution time,cost and processing speed.The optimal effect meets the low-latency requirement of IoT workflow scheduling. |
PDF Full Text Request