【摘要】：由于云計算具有靈活性、高可擴(kuò)展性和經(jīng)濟(jì)性等特性,許多組織將傳統(tǒng)工作流應(yīng)用遷移到云計算環(huán)境中,形成了云工作流。云工作流調(diào)度指在云平臺上對用戶提交的工作流進(jìn)行資源分配與任務(wù)執(zhí)行,調(diào)度過程要考慮用戶的服務(wù)質(zhì)量(Quality-of-Service,QoS)需求,如執(zhí)行時間、費用等。針對QoS敏感的云工作流調(diào)度問題,本文提出兩種云工作流調(diào)度優(yōu)化方法,分別適用于云工作流調(diào)度的任務(wù)-資源映射階段和任務(wù)執(zhí)行階段的調(diào)度優(yōu)化。任務(wù)-資源映射階段,工作流中的各項任務(wù)需要預(yù)先被分配至最佳資源,分配過程要考慮滿足用戶的QoS約束�，F(xiàn)有的調(diào)度算法要從時間和費用兩方面進(jìn)行研究,很少考慮可靠性。但在實際系統(tǒng)中,資源和數(shù)據(jù)傳輸?shù)墓收隙紩䦟ぷ髁鞯某晒\行造成負(fù)面影響。論文考慮了時間、費用和可靠性三個重要QoS因素。針對時間和可靠性雙重約束下費用最小化的云工作流調(diào)度問題,提出了基于螢火蟲算法和動態(tài)優(yōu)先級的最優(yōu)調(diào)度方案搜索方法。特別地,結(jié)合云工作流調(diào)度問題的特點,重新定義了螢火蟲算法中的位置、距離以及位置更新方式,同時對于每一種調(diào)度方案,采取動態(tài)優(yōu)先級算法確定任務(wù)順序,以減少工作流完成時間。任務(wù)執(zhí)行階段依據(jù)任務(wù)-資源映射關(guān)系,將任務(wù)調(diào)度到相應(yīng)的資源上執(zhí)行,調(diào)度過程中會產(chǎn)生調(diào)度開銷,從而影響到云工作流的QoS水平。任務(wù)聚類將細(xì)粒度任務(wù)合并成粗粒度任務(wù),調(diào)度到同一資源上,減少調(diào)度開銷從而優(yōu)化流程執(zhí)行時間。不合理任務(wù)聚類過程會產(chǎn)生時間不均衡和依賴不均衡問題,這將導(dǎo)致任務(wù)執(zhí)行并行度降低。針對時間不均衡問題,本文提出了時間均衡聚類算法RBCA,該算法使用回溯法進(jìn)行任務(wù)聚類,使得聚類后各類運行時間更加均衡。針對依賴不均衡問題,本文提出了依賴均衡聚類算法DBCA,定義了關(guān)聯(lián)度這一概念用來衡量任務(wù)之間依賴的相似程度,將關(guān)聯(lián)度高的任務(wù)聚為一類,從而解決依賴不均衡。本文在Workflow Sim云工作流仿真平臺上進(jìn)行實驗仿真。實驗證實,基于螢火蟲算法和動態(tài)優(yōu)先級的多QoS云工作流調(diào)度方法在收斂速度和最優(yōu)值均優(yōu)于傳統(tǒng)螢火蟲算法,同時也優(yōu)于另外兩種云工作流調(diào)度算法GA和S-CLPSO。基于均衡聚類的云工作流調(diào)度優(yōu)化方法相比傳統(tǒng)的均衡聚類算法HRB、HIFB,聚類結(jié)果更為均衡,更能優(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.
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：TP18;TP311.13

【參考文獻(xiàn)】

相關(guān)期刊論文 前8條

1 武岳;胡慶杰;李清朋;;基于改進(jìn)螢火蟲算法的桿系結(jié)構(gòu)拓?fù)鋬?yōu)化[J];建筑結(jié)構(gòu)學(xué)報;2016年06期

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

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

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

5 閆歌;于炯;楊興耀;;基于可靠性的云工作流調(diào)度策略[J];計算機(jī)應(yīng)用;2014年03期

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

7 程建軍;胡成松;;基于改進(jìn)模擬退火任務(wù)調(diào)度算法研究[J];計算機(jī)仿真;2011年12期

8 葛新;陳華平;杜冰;李書鵬;;基于云計算集群擴(kuò)展中的調(diào)度策略研究[J];計算機(jī)應(yīng)用研究;2011年03期

相關(guān)碩士學(xué)位論文 前4條

1 李瑞青;改進(jìn)的螢火蟲算法及應(yīng)用[D];吉林大學(xué);2015年

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

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

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

，

本文編號：2487829