云工作流系統(tǒng)中基于粒子群算法的任務(wù)調(diào)度優(yōu)化研究.pdf

1、云計算是一種大型計算資源共享模型。云計算平臺在充分利用海量異構(gòu)分布式資源的同時，可以向用戶提供無處不在、方便、按需的網(wǎng)絡(luò)計算資源服務(wù)。云計算的關(guān)鍵特征在于按需服務(wù)、超大規(guī)模、虛擬化、高可伸縮性和通用性。工作流是一種部分或完全由計算機(jī)自動執(zhí)行的業(yè)務(wù)流程。工作流管理系統(tǒng)從用戶處接收任務(wù)且根據(jù)用戶的需求和任務(wù)限制條件為每個任務(wù)分配合適的資源。由于云計算的目標(biāo)是為用戶提供執(zhí)行效率更好且成本更低的資源，并且隨著在云環(huán)境中大規(guī)模電子商務(wù)以及科學(xué)計算

2、等應(yīng)用的不斷發(fā)展，使得對云環(huán)境中任務(wù)自動分配和執(zhí)行的QoS(Quality of Service)目標(biāo)的要求不斷提升。因此，如何使得云環(huán)境中的任務(wù)調(diào)度和資源分配方案更加合理是一個重要的研究方向。
　　云工作流系統(tǒng)是一種將云計算海量的資源配置與工作流的自主資源分配方法相結(jié)合的產(chǎn)物，云工作流管理系統(tǒng)根據(jù)工作流任務(wù)之間的依賴關(guān)系以及任務(wù)之間的優(yōu)先級將云計算中的各種可用資源分配給相應(yīng)的工作流任務(wù)。由于在云環(huán)境中資源的使用是有償?shù)?，如果無法

3、以一種合理的方式為這些任務(wù)分配合適的資源，那么將會增加云服務(wù)提供商的成本，同時也會使云環(huán)境中的各類資源無法得到充分利用。因此，如何通過云工作流系統(tǒng)為用戶所提交的任務(wù)分配合適的資源是一項(xiàng)十分重要的問題。
　　針對這一問題，可以在云工作流系統(tǒng)中通過任務(wù)調(diào)度算法為不同任務(wù)分配合適的資源，早期的云環(huán)境由于規(guī)模不大，云服務(wù)提供商所最為關(guān)注的是任務(wù)執(zhí)行的費(fèi)用問題，因此早期云環(huán)境中的任務(wù)調(diào)度算法優(yōu)化目標(biāo)為降低任務(wù)執(zhí)行費(fèi)用。隨著云計算的不斷發(fā)展，

4、用戶對任務(wù)執(zhí)行完成時間的要求越來越高，云服務(wù)提供商也同時需要較高的資源利用率，此時調(diào)度算法的優(yōu)化目標(biāo)又轉(zhuǎn)移至降低任務(wù)執(zhí)行時間。近年來隨著云計算領(lǐng)域針對QoS優(yōu)化目標(biāo)的研究不斷興起，使得云工作流任務(wù)調(diào)度算法需要同時針對任務(wù)執(zhí)行的時間與費(fèi)用目標(biāo)進(jìn)行優(yōu)化。因此，如何將任務(wù)執(zhí)行時間與費(fèi)用兩個目標(biāo)有效的結(jié)合，進(jìn)而形成合適的QoS優(yōu)化目標(biāo)又成為了當(dāng)下研究的熱點(diǎn)。
　　但是隨著近幾年來云計算行業(yè)的蓬勃發(fā)展以及巨型云數(shù)據(jù)中心的不斷出現(xiàn)，云服務(wù)所帶

5、來的巨額能耗成本在總運(yùn)營成本中所占比重越來越大，如何優(yōu)化與管理大型云數(shù)據(jù)中心的能源消耗是一個巨大的挑戰(zhàn)，通過云工作流管理系統(tǒng)可以管理和優(yōu)化云環(huán)境中的任務(wù)調(diào)度，降低服務(wù)器運(yùn)行能耗。然而，現(xiàn)有的云工作流管理系統(tǒng)針對能耗目標(biāo)優(yōu)化的研究較少，導(dǎo)致任務(wù)調(diào)度算法無法充分提高服務(wù)器資源利用率，降低任務(wù)執(zhí)行能耗。同時現(xiàn)有基于能耗的任務(wù)調(diào)度算法僅對任務(wù)執(zhí)行時的QoS需求或能耗目標(biāo)單獨(dú)進(jìn)行優(yōu)化。導(dǎo)致調(diào)度策略在優(yōu)化了服務(wù)器能耗的同時，降低了云工作流服務(wù)性能指

6、標(biāo)。這會造成云工作流無法滿足用戶在使用時的QoS需求。因此，如何在保證用戶QoS需求的同時，盡可能降低任務(wù)執(zhí)行能耗是一個急需解決的問題。
　　目前云工作流系統(tǒng)常用的任務(wù)調(diào)度優(yōu)化算法為粒子群算法，然而傳統(tǒng)慣性權(quán)重的粒子群算法存在易陷入局部最優(yōu)，迭代收斂速度緩慢的缺點(diǎn)。由此導(dǎo)致任務(wù)調(diào)度方案的費(fèi)用與能耗較高。因此，本文首先改進(jìn)了傳統(tǒng)自適應(yīng)慣性權(quán)重，新的自適應(yīng)慣性權(quán)重通過更加精確的描述粒子位置狀態(tài)以增強(qiáng)在算法迭代過程中對慣性權(quán)重的調(diào)整精度

7、。接著提出了一種精細(xì)搜索的自適應(yīng)慣性權(quán)重粒子群算法(Fine Adaptive Inertia Weight-basedParticle Swarm Optimization, FAIWPSO)，然后將該算法分別針對云工作流系統(tǒng)任務(wù)調(diào)度方案的執(zhí)行費(fèi)用與能耗兩個目標(biāo)分別進(jìn)行優(yōu)化。提出了兩種任務(wù)調(diào)度算法:費(fèi)用優(yōu)化的粒子群任務(wù)調(diào)度算法與能耗感知的粒子群任務(wù)調(diào)度算法。
　　本文的主要工作和創(chuàng)新點(diǎn)具體如下:
　　1.針對傳統(tǒng)自適應(yīng)慣性

8、權(quán)重的粒子群算法易陷入早熟與局部收斂的缺點(diǎn)，對傳統(tǒng)自適應(yīng)慣性權(quán)重的成功值計算方法進(jìn)行改進(jìn)，提出了一種精細(xì)搜索的自適應(yīng)慣性權(quán)重策略的粒子群算法。之后使用該算法對于云工作流任務(wù)調(diào)度執(zhí)行費(fèi)用與能耗目標(biāo)分別進(jìn)行了優(yōu)化研究。
　　2.首先針對任務(wù)執(zhí)行的費(fèi)用目標(biāo)進(jìn)行研究。將精細(xì)搜索的自適應(yīng)慣性權(quán)重粒子群算法與云工作流任務(wù)層調(diào)度的費(fèi)用模型相結(jié)合提出了一種費(fèi)用優(yōu)化的自適應(yīng)慣性權(quán)重粒子群任務(wù)調(diào)度算法，對云工作流任務(wù)執(zhí)行費(fèi)用進(jìn)行優(yōu)化。通過將費(fèi)用優(yōu)化的

9、自適應(yīng)慣性權(quán)重粒子群任務(wù)調(diào)度算法與其他五種不同慣性權(quán)重的粒子群算法實(shí)驗(yàn)對比，結(jié)果表明費(fèi)用優(yōu)化的自適應(yīng)慣性權(quán)重粒子群任務(wù)調(diào)度算法在算法收斂性、適應(yīng)度和任務(wù)執(zhí)行費(fèi)用三方面均優(yōu)于其余算法。
　　3.接著針對任務(wù)執(zhí)行的能耗目標(biāo)進(jìn)行優(yōu)化研究。根據(jù)任務(wù)執(zhí)行能耗計算模型設(shè)計了適于評價任務(wù)調(diào)度方案執(zhí)行能耗的適應(yīng)度計算方法。之后結(jié)合精細(xì)搜索的自適應(yīng)粒子群任務(wù)調(diào)度算法提出了針對任務(wù)執(zhí)行能耗進(jìn)行優(yōu)化的能耗感知自適應(yīng)粒子群任務(wù)調(diào)度算法。通過與其他幾種慣性

10、權(quán)重的粒子群算法進(jìn)行實(shí)驗(yàn)對比。結(jié)果表明，能耗感知自適應(yīng)粒子群任務(wù)調(diào)度算法不但收斂穩(wěn)定而且調(diào)度方案的執(zhí)行能耗最低。
　　本文基于當(dāng)前針對云工作流任務(wù)調(diào)度的費(fèi)用與能耗問題進(jìn)行了深入的研究。提出了一種精細(xì)搜索的自適應(yīng)慣性權(quán)重粒子群算法，分別針對當(dāng)前任務(wù)調(diào)度優(yōu)化目標(biāo)中兩個較為重要的目標(biāo)費(fèi)用與能耗分別進(jìn)行研究，提出了針對不同優(yōu)化目標(biāo)的兩種粒子群任務(wù)調(diào)度算法。最終通過實(shí)驗(yàn)證明了兩種算法不僅優(yōu)化了云工作流環(huán)境中的任務(wù)執(zhí)行費(fèi)用與能耗，而且在算法收