【摘要】：隨著大數(shù)據(jù)時代的來臨,傳統(tǒng)的工作流計算平臺已經(jīng)無法滿足大量工作流應(yīng)用的計算要求.因此,工作流應(yīng)用開始由原有的基礎(chǔ)設(shè)施轉(zhuǎn)移到更加高效、可靠、廉價的云平臺上.針對現(xiàn)有的云工作流調(diào)度算法執(zhí)行時間最小化、作業(yè)最優(yōu)分配以及調(diào)度算法的收斂時間問題,提出一種基于多Agent系統(tǒng)的粒子群遺傳優(yōu)化云工作流調(diào)度算法.該算法首先利用粒子的自身歷史最優(yōu)位置和粒子群歷史最優(yōu)位置優(yōu)化全局最優(yōu)解的搜索過程,然后將系統(tǒng)中每個粒子作為一個Agent,多Agent間相互競爭和協(xié)調(diào),最后在多Agent系統(tǒng)中引入遺傳算法,通過Agent間的信息交互進行有目標(biāo)地交叉變異操作,不僅避免粒子群的盲目隨機化以及陷入局部最優(yōu)解,而且加速了搜索全局最優(yōu)解的收斂過程.使用真實工作流數(shù)據(jù)進行模擬實驗,實驗結(jié)果證明該算法的有效性.
【圖文】：

理大量業(yè)務(wù)．隨著云計算平臺與工作流系統(tǒng)的結(jié)合，云工作流系統(tǒng)將成為處理大規(guī)模復(fù)雜業(yè)務(wù)的有效工具．云工作流系統(tǒng)是建立在云計算平臺上的工作流系統(tǒng)，滿足云計算模式的功能需求．它的功能組件包括了一般工作流系統(tǒng)組件和與工作流系統(tǒng)相協(xié)調(diào)的云計算平臺．此外，由于云計算平臺的管理非常復(fù)雜和龐大，如何高效提高服務(wù)質(zhì)量ＱｏＳ（ＱｕａｌｉｔｙｏｆＳｅｒｉｖｉｃｅ）的管理和任務(wù)部署就成為一個極大的挑戰(zhàn)．為了在云環(huán)境中高效地調(diào)度任務(wù)及數(shù)據(jù)．本文提出了一個云工作流系統(tǒng)模型，如圖１所示．圖１云工作流系統(tǒng)模型Ｆｉｇ．１Ｃｌｏｕｄｗｏｒｋｆｌｏｗｓｙｓｔｅｍｍｏｄｅｌ３．２云工作流模型組件介紹（１）云工作流接口：云工作流通過這個接口導(dǎo)入到云工作流系統(tǒng)中，這個組件提供了對科學(xué)工作流、電子商務(wù)等的接口，以便后續(xù)組件根據(jù)其工作流的主要特點進行分類處理．（２）云工作流解析器：這個組件對工作流整體進行解析，生成工作流的任務(wù)集，任務(wù)之間的約束關(guān)系，以及任務(wù)之間的數(shù)據(jù)和傳輸路徑．（３）云工作流引擎：獲取云工作流解析器生成工作流任務(wù)集、任務(wù)之間的約束關(guān)系，以及任務(wù)之間的數(shù)據(jù)和傳輸路徑．云工作流引擎的主要作用在于根據(jù)任務(wù)間的約束關(guān)系，確保當(dāng)前任務(wù)在父任務(wù)成功完成或數(shù)據(jù)到達當(dāng)前任務(wù)時，當(dāng)前任務(wù)才可以執(zhí)行．這個組件只提交未處理的任務(wù)給云工作流調(diào)度器．（４）云工作流調(diào)度器：這個組件是整個系統(tǒng)的核心，主要的任務(wù)調(diào)度算法就是通過這個組件實現(xiàn)：首先云工作流調(diào)度器通過加載上一層組件生成的云工作流，生成一個全局隊列；其次在作業(yè)分配器中根據(jù)調(diào)度算法對任務(wù)進行分配，生成作業(yè)的調(diào)度的子隊列；然后從子隊列

次迭代時的速度，ω是慣性權(quán)重，取值非負，調(diào)節(jié)對解空間的搜索范圍ｃ．１和ｃ２是加速度常數(shù)（ｃ１也稱認知系數(shù)，ｃ２也稱社會系數(shù)），調(diào)節(jié)學(xué)習(xí)的最大步長．ｒ１和ｒ２是０到１之間的隨機數(shù)，以增加搜索隨機性，Ｘｋ＋１ｉ是粒子ｉ在第ｋ＋１次迭代時位置，Ｘｋｉ是粒子ｉ在第ｋ次迭代時的位置，是Ｐｂｅｓｔｉ第ｉ個粒子目前為止到達的最好位置，Ｇｂｅｓｔ是對整個種群而言最佳的粒子位置．粒子群優(yōu)化算法的流程圖如圖２所示．４．２云工作流環(huán)境下的粒子群算法云工作流調(diào)度算法的變量和規(guī)則描述如下：任務(wù)和虛擬機的映射關(guān)系：表示成一個二元組Ｘｉｊ：Ｘｉｊ＝Ｔｉ，Ｐｊ，ｉ∈［１，ｍ］，ｊ∈［１，ｎ］（３）其中，Ｔｉ表示第ｉ號任務(wù)，ｍ表示任務(wù)的數(shù)目，Ｐｊ表示第ｊ號虛擬機，，ｎ表示虛擬機的數(shù)目，這個二元組代表任務(wù)虛擬機的映射關(guān)系，即一個任務(wù)Ｔｉ分配到Ｐｊ虛擬機上．圖２粒子群優(yōu)化算法的流程圖Ｆｉｇ．２Ｐａｒｔｉｃｌｅｓｗａｒｍｏｐｔｉｍｉｚａｔｉｏｎａｌｇｏｒｉｔｈｍｆｌｏｗｃｈａｒｔ粒子的位置：代表云工作流調(diào)度問題的一個可行解，表示為一個二維矩陣Ｘ：Ｘ＝φ（Ｘ１１）φ（Ｘ１２）…φ（Ｘ１ｎ）φ（Ｘ２１）φ（Ｘ２２）…φ（Ｘ２ｎ）鐤鐤郪鐤φ（Ｘｍ１）φ（Ｘｍ２）…φ（Ｘｍｎ）p膒苝蘰危ǎ矗┢渲�，二维矩阵Ｘ代表一鸽hＷ擁奈恢茫卣竺扛鑫恢么娣諾娜撾瘢裕

本文編號：2564771