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

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

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

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

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

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

6、標(biāo)。這會(huì)造成云工作流無(wú)法滿足用戶在使用時(shí)的QoS需求。因此，如何在保證用戶QoS需求的同時(shí)，盡可能降低任務(wù)執(zhí)行能耗是一個(gè)急需解決的問(wèn)題。
　　目前云工作流系統(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)重通過(guò)更加精確的描述粒子位置狀態(tài)以增強(qiáng)在算法迭代過(guò)程中對(duì)慣性權(quán)重的調(diào)整精度

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

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

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

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