【摘要】：由于云計算具有靈活性、高可擴展性和經(jīng)濟性等特性,許多組織將傳統(tǒng)工作流應用遷移到云計算環(huán)境中,形成了云工作流。云工作流調度指在云平臺上對用戶提交的工作流進行資源分配與任務執(zhí)行,調度過程要考慮用戶的服務質量(Quality-of-Service,QoS)需求,如執(zhí)行時間、費用等。針對QoS敏感的云工作流調度問題,本文提出兩種云工作流調度優(yōu)化方法,分別適用于云工作流調度的任務-資源映射階段和任務執(zhí)行階段的調度優(yōu)化。任務-資源映射階段,工作流中的各項任務需要預先被分配至最佳資源,分配過程要考慮滿足用戶的QoS約束。現(xiàn)有的調度算法要從時間和費用兩方面進行研究,很少考慮可靠性。但在實際系統(tǒng)中,資源和數(shù)據(jù)傳輸?shù)墓收隙紩䦟ぷ髁鞯某晒\行造成負面影響。論文考慮了時間、費用和可靠性三個重要QoS因素。針對時間和可靠性雙重約束下費用最小化的云工作流調度問題,提出了基于螢火蟲算法和動態(tài)優(yōu)先級的最優(yōu)調度方案搜索方法。特別地,結合云工作流調度問題的特點,重新定義了螢火蟲算法中的位置、距離以及位置更新方式,同時對于每一種調度方案,采取動態(tài)優(yōu)先級算法確定任務順序,以減少工作流完成時間。任務執(zhí)行階段依據(jù)任務-資源映射關系,將任務調度到相應的資源上執(zhí)行,調度過程中會產(chǎn)生調度開銷,從而影響到云工作流的QoS水平。任務聚類將細粒度任務合并成粗粒度任務,調度到同一資源上,減少調度開銷從而優(yōu)化流程執(zhí)行時間。不合理任務聚類過程會產(chǎn)生時間不均衡和依賴不均衡問題,這將導致任務執(zhí)行并行度降低。針對時間不均衡問題,本文提出了時間均衡聚類算法RBCA,該算法使用回溯法進行任務聚類,使得聚類后各類運行時間更加均衡。針對依賴不均衡問題,本文提出了依賴均衡聚類算法DBCA,定義了關聯(lián)度這一概念用來衡量任務之間依賴的相似程度,將關聯(lián)度高的任務聚為一類,從而解決依賴不均衡。本文在Workflow Sim云工作流仿真平臺上進行實驗仿真。實驗證實,基于螢火蟲算法和動態(tài)優(yōu)先級的多QoS云工作流調度方法在收斂速度和最優(yōu)值均優(yōu)于傳統(tǒng)螢火蟲算法,同時也優(yōu)于另外兩種云工作流調度算法GA和S-CLPSO�；诰饩垲惖脑乒ぷ髁髡{度優(yōu)化方法相比傳統(tǒng)的均衡聚類算法HRB、HIFB,聚類結果更為均衡,更能優(yōu)化流程的執(zhí)行時間。
[Abstract]:Because cloud computing has the characteristics of flexibility, high scalability, and economy, many organizations migrate traditional workflow applications into the cloud computing environment, forming a cloud workflow. The cloud workflow scheduling refers to the resource allocation and task execution of the workflow submitted by the user on the cloud platform, and the scheduling process takes into account the quality-of-service (QoS) requirements of the user, such as the execution time, the cost, and the like. In order to solve the problem of QoS-sensitive cloud workflow scheduling, two cloud workflow scheduling optimization methods are proposed, which are respectively applicable to the task-resource mapping stage and the scheduling optimization of the task execution stage of the cloud workflow scheduling. The task-resource mapping stage, the tasks in the workflow need to be allocated to the optimal resource in advance, and the allocation process takes into account the user's QoS constraints. The existing scheduling algorithm is to be studied in terms of time and cost, and the reliability is seldom considered. However, in the actual system, the failure of resources and data transmission will have a negative impact on the successful operation of the workflow. The paper takes into account three important QoS factors of time, cost and reliability. Aiming at the problem of cloud workflow scheduling under the double constraint of time and reliability, a search method of optimal scheduling scheme based on firefly and dynamic priority is proposed. In particular, in combination with the characteristics of the cloud workflow scheduling problem, the position, distance and location updating method in the firefly algorithm are redefined, and the task order is determined by adopting a dynamic priority algorithm for each scheduling scheme so as to reduce the completion time of the workflow. The task execution stage performs task scheduling to the corresponding resources according to the task-resource mapping relationship, and the scheduling cost is generated in the scheduling process, thereby affecting the QoS level of the cloud workflow. Task clustering combines fine-grained tasks into coarse-grained tasks, schedules to the same resource, reduces scheduling overhead, and optimizes process execution time. Unreasonable task clustering can produce time-imbalance and dependency-dependent problems, which will lead to a reduction in the parallelism of tasks. In view of the problem of time-imbalance, this paper presents a time-balanced clustering algorithm RBCA, which uses the backtracking method to carry out task clustering, so that the running time after clustering is more balanced. In order to solve the problem of dependency, this paper puts forward the DBCA which is dependent on the equilibrium clustering algorithm, and defines the degree of the degree of similarity between the task and the task, and the task of the high degree of association is gathered into a class, so that the problem of dependency is solved. In this paper, the experimental simulation is carried out on the workflow simulation platform of Workflow Sim. It is proved that the multi-QoS cloud workflow scheduling method based on the firefly algorithm and the dynamic priority is superior to the traditional firefly algorithm at the convergence speed and the optimal value, and is superior to the other two cloud workflow scheduling algorithms GA and S-CLPSO. Compared with the traditional balanced clustering algorithm HRB, HIFB, the clustering result is more balanced compared with the traditional balanced clustering algorithm HRB and HIFB, and the execution time of the process can be more optimized.
【學位授予單位】：杭州電子科技大學
【學位級別】：碩士
【學位授予年份】：2017
【分類號】：TP18;TP311.13

【參考文獻】

相關期刊論文 前8條

1 武岳;胡慶杰;李清朋;;基于改進螢火蟲算法的桿系結構拓撲優(yōu)化[J];建筑結構學報;2016年06期

2 曹斌;王小統(tǒng);熊麗榮;范菁;;時間約束云工作流調度的粒子群搜索方法[J];計算機集成制造系統(tǒng);2016年02期

3 李緒光;;WF工作流技術研究及在工程設計管理中的應用[J];通訊世界;2014年18期

4 楊玉麗;彭新光;黃名選;邊婧;;基于離散粒子群優(yōu)化的云工作流調度[J];計算機應用研究;2014年12期

5 閆歌;于炯;楊興耀;;基于可靠性的云工作流調度策略[J];計算機應用;2014年03期

6 劉亞秋;邢樂樂;景維鵬;;云計算環(huán)境下基于時間期限和預算的調度算法[J];計算機工程;2013年06期

7 程建軍;胡成松;;基于改進模擬退火任務調度算法研究[J];計算機仿真;2011年12期

8 葛新;陳華平;杜冰;李書鵬;;基于云計算集群擴展中的調度策略研究[J];計算機應用研究;2011年03期

相關碩士學位論文 前4條

1 李瑞青;改進的螢火蟲算法及應用[D];吉林大學;2015年

2 劉海濤;云環(huán)境下的工作流調度方法研究[D];北京理工大學;2015年

3 郭鳳羽;云環(huán)境下對資源聚類的工作流任務安全調度研究[D];新疆大學;2014年

4 熊磊;基于蟻群算法和DAG工作流的云計算任務調度研究[D];湖北工業(yè)大學;2014年

，

本文編號：2487829