林海濤,姜棟瀚

(海軍工程大學(xué) 電子工程學(xué)院，武漢 430033)

基于重建策略的云工作流調(diào)度算法優(yōu)化

林海濤,姜棟瀚

(海軍工程大學(xué) 電子工程學(xué)院，武漢 430033)

為了進一步提高算法性能，提出一種改進的蛙跳算法，并與調(diào)度方案相結(jié)合，以期為云工作流資源分配提供最優(yōu)調(diào)度。通過在蛙跳算法的局部搜索中加入重建策略，提高了數(shù)據(jù)隨機性，有效避免了局部最優(yōu)。研究了調(diào)度方案生成算法，與改進算法相結(jié)合得到接近最優(yōu)的調(diào)度。利用Java模擬器進行仿真試驗，并與粒子群優(yōu)化算法和傳統(tǒng)蛙跳算法作比較。實驗證明，提出的方法可以在滿足最長截止時間約束的情況下，使總執(zhí)行成本最小化。

蛙跳算法；資源調(diào)度；云工作流；重建策略

0 引 言

基礎(chǔ)設(shè)施即服務(wù)(IaaS)是云計算最基本的應(yīng)用形式[1]。當(dāng)用戶提出應(yīng)用請求后，IaaS通過管理中間件中的任務(wù)管理機制為任務(wù)分配虛擬化資源，其資源調(diào)度機制是影響云計算效能的關(guān)鍵。云計算中的按需配置和資源可用性使其成為執(zhí)行工作流應(yīng)用程序的理想選擇。然而，工作流調(diào)度是一個非確定性多項式(non-deterministic polynomial，NP)問題，云計算環(huán)境的異質(zhì)性和動態(tài)性又使問題進一步復(fù)雜化。資源調(diào)度高效算法是提升云工作流系統(tǒng)效能亟待解決的問題，也是云計算領(lǐng)域內(nèi)的研究熱點。

工作流是指將一組任務(wù)按照業(yè)務(wù)需求進行合理傳遞的工作流程。工作流中任務(wù)數(shù)量大小不等，但所有任務(wù)需要分配至不同的虛擬資源，并在合理的時間內(nèi)完成。而云計算環(huán)境下，服務(wù)器被虛擬化成可在同一處理器上運行的多個虛擬機(virtual machine,VM)，不同的虛擬機具有不同的CPU、內(nèi)存和帶寬等資源。資源調(diào)度算法就是確定任務(wù)和虛擬資源之間的映射，以便滿足一個或多個優(yōu)化目標(biāo)。

國內(nèi)外已經(jīng)提出了很多云計算環(huán)境下的資源調(diào)度方案，概括來說主要有2種：①基于最優(yōu)化理論對云計算資源調(diào)度問題建模，以實現(xiàn)整個系統(tǒng)的性能最佳。例如文獻[2]中通過動態(tài)箱包裝，最小化在包裝中使用的最大箱數(shù)，實現(xiàn)了云計算整體消耗的最小化；文獻[3]中提出的自適應(yīng)調(diào)度算法(adaptive scheduling algorithm，ASA)首先將任務(wù)從邏輯上分成若干類別，再根據(jù)不同資源的特點進行合理分配。上述算法在調(diào)度的過程中實現(xiàn)了整體效能的最優(yōu)，被廣泛應(yīng)用于小規(guī)模的虛擬機部署方案。但是，在分布式系統(tǒng)上進行資源調(diào)度是NP問題，該問題無法在多項式時間內(nèi)獲得最優(yōu)解。尤其在規(guī)模較大時，上述算法難以在有效時間內(nèi)得到最優(yōu)解。因此，另一種基于啟發(fā)式的次優(yōu)算法被提出。②基于啟發(fā)式的次優(yōu)算法，是指在可接受的范圍內(nèi)得到可行解來處理實際問題。例如文獻[4]中提出了模擬退火算法(simulated annealing algorithm，SAA)，模擬物理學(xué)中的冷卻過程通過內(nèi)外循環(huán)使其達到熱平衡狀態(tài)。即用更優(yōu)解替換原有解，經(jīng)過多次迭代找到較好的分配方案；文獻[5]中介紹了遺傳算法(genetic algorithm，GA)，通過初始化、交叉和變異算子，經(jīng)過多次迭代最終找到較優(yōu)解；文獻[6]提出的粒子群優(yōu)化(particle swarm optimization，PSO)算法通過在空間中找尋適應(yīng)度最優(yōu)的粒子，找到最佳位置，從而更好地進行資源調(diào)度；在蛙跳算法(shuffled frog leaping algorithm，SFLA)中，通過子種群群內(nèi)通信和群間通信，最差解不斷定向跳躍至最好解的位置，它作為一個有效的算法被應(yīng)用在各種資源調(diào)度中，如聚類、演化查詢、排序優(yōu)化、推薦系統(tǒng)等[7]。但是上述算法大多不具有約束能力，尤其在規(guī)模較大時，容易陷入局部最優(yōu)，難以得到全局最優(yōu)解。為了進一步提高算法性能，本文對SFLA進行了改進，以期為云計算資源調(diào)度建模提供思路。

1 問題描述

1.1 問題說明

執(zhí)行一個大型工作流，首先將其分成多個小任務(wù)，并將其映射在虛擬資源上。云工作流的資源調(diào)度一般分為3個步驟：①提供可以用來分配給任務(wù)的可用資源；②將任務(wù)映射到滿足需求的資源上；③按照之前的映射方案將任務(wù)分配到相應(yīng)資源上運行。本文所提出的算法結(jié)合了資源提供和調(diào)度的問題，并將它們作為一個問題，使用改進的蛙跳算法加以解決。目的就是將工作流中的每個任務(wù)映射到更好的服務(wù)資源，使總執(zhí)行成本最小化，并將完成時間保持在最后期限內(nèi)。

工作流可以描述為有向無環(huán)圖(T,E,D)，其中，點集合T表示業(yè)務(wù)應(yīng)用的任務(wù)集合；E表示任務(wù)之間的依賴關(guān)系，即沿邊緣方向的權(quán)重值(邊緣權(quán)重)；最后期限D(zhuǎn)表示工作流應(yīng)該完成的最長執(zhí)行時間。虛擬機的處理能力根據(jù)每秒浮點運算次數(shù)來確定，并且可從云資源提供者處獲得?；谔摂M機的處理能力，可以計算給定虛擬機上任務(wù)的執(zhí)行時間。如果T1在任務(wù)圖中位于T2之前，即在T2任務(wù)開始執(zhí)行之前要完成T1任務(wù)，則從節(jié)點1到節(jié)點2存在有向邊。沒有傳入邊的節(jié)點表示進入任務(wù)，沒有傳出邊的節(jié)點表示退出任務(wù)。一種工作流示例如圖1所示。

圖1 一種工作流示例Fig.1 A workflow example

圖2描繪了與圖1任務(wù)圖相對應(yīng)的調(diào)度示例。

VM1T1T4T6VM2T2T5T9VM3T3T7T8

圖2調(diào)度示例
Fig.2 Example of scheduling

工作流中常見的優(yōu)化標(biāo)準(zhǔn)是任務(wù)完成時間的最小化、成本最小化、資源利用最大化、滿足目標(biāo)約束等。除此之外，還需要調(diào)度算法來協(xié)調(diào)工作流中的任務(wù)依賴性，即在某些情況下，只有當(dāng)工作流中的前一個任務(wù)已完成執(zhí)行時，才能執(zhí)行下一個任務(wù)。另外，云計算環(huán)境對于工作流更為有益，因為它使用戶能直接請求業(yè)務(wù)所需的資源，并且由用戶控制的調(diào)度器來調(diào)度任務(wù)[8]。這使得用戶能夠僅在需要時分配資源，并且一旦分配，該資源可以隨后用于執(zhí)行多種任務(wù)。因此，高效的資源調(diào)度是在云中實現(xiàn)高性能的主要挑戰(zhàn)[9]。假設(shè)各種類型的VM由IaaS提供商提供，用戶可以根據(jù)需求按需租用它們。本文提出的調(diào)度算法定義任務(wù)和資源之間的映射，并列出了應(yīng)租借的VM的數(shù)量以及應(yīng)租用的時間長度。目的是使總執(zhí)行成本最小化并將完成時間保持在期限內(nèi)。

1.2 基于重建策略改進蛙跳算法

2003年，Eusuff和Lansey提出SFLA[10]，旨在模仿一群青蛙的行為，尋找隨機分布在池塘里的石頭上的食物。它匯集了基于遺傳進化的模因演算法(memetic algorithm，MA)以及基于社會行為的粒子群優(yōu)化(particle swarm optimization，PSO)算法，其已被用于解決諸如資源調(diào)度、車間作業(yè)生產(chǎn)調(diào)度等許多復(fù)雜的優(yōu)化問題。

在傳統(tǒng)的蛙跳算法中，初始種群由一組在池塘中尋找食物的青蛙組成。搜索食物包括2個交替的過程：①初始種群被分為若干個子種群，在子種群內(nèi)青蛙進行群內(nèi)通信；②子種群發(fā)展到一定階段，它們之間進行群間通信。這個過程中，只有最差解被定向跳躍至最好解的位置。然而，由于種群是隨機生成的，即使適應(yīng)度最好的青蛙也可能不具有真正的全局性，從而易導(dǎo)致局部最優(yōu)。越是食物密集的地方越容易陷入局部最優(yōu)，并且搜索食物的青蛙的跳躍動作取決于個體的慣性運動，因此，在最好解的周圍可能存在具有更多食物的位置。這可以通過更新最佳蛙的慣性矩來實現(xiàn)。

因此，我們設(shè)計了一種重建策略，重建策略流程如圖3所示。在得到的最好解周圍找隨機位置，進行適應(yīng)度比較。這種方法有助于最好解跳躍到其附近有更多食物的新位置。在每個模因中，對于每次迭代確定最佳和最差解。對于模因中的替代迭代，最好的青蛙試圖重新建立自我地位以增強他們的位置，而最壞的青蛙努力通過所有迭代中的信息交互來改善他們的位置。該策略可以用于解決任何種類的離散或連續(xù)優(yōu)化問題。對于任務(wù)調(diào)度，通過在最佳解決方案處搜索更好的位置來執(zhí)行重建。如果適應(yīng)度改進，則保留適配的解;否則，最好的青蛙保持在其原始位置。

圖3 重建策略流程圖Fig.3 Reconstruction strategy flow chart

圖3中，rand( )函數(shù)用來生成0到1之間的隨機數(shù)；Xqb為全局適應(yīng)度最好的青蛙，即全局最好解；Xjb為子種群中適應(yīng)度最好的青蛙，即局部最好解；Xw為子種群中適應(yīng)度最差的青蛙，即局部最差解；a是適合于該問題的常數(shù)值。

改進的蛙跳算法中的演變是沿著2個維度進行的：①通過在種群迭代進化期間恢復(fù)最好解的位置；②通過信息交換定期改善最差解的位置。因此，該算法已經(jīng)被修改為如下所示。步驟1到步驟5保持原算法不變。

步驟1將青蛙的大小設(shè)置為d；

步驟2用隨機位置初始化青蛙種群P，計算每只青蛙的適應(yīng)度；

步驟3按照其適應(yīng)度的降序?qū)ΨN群P進行排序；

步驟4確定全局最好解Xqb的適應(yīng)度為fqb；

步驟5將P分成m個子種群；

步驟6對于每個子種群

①確定局部最好解Xjb的適應(yīng)度為fjb，局部最差解Xw的適應(yīng)度為fw；

②通過替代迭代嘗試改善局部最好解的位置(即周期性n=2)；

③新的局部最好解Xn=重建Xjb；

④如果局部最好解Xn的適應(yīng)度提高，用新青蛙替換原來的青蛙；

⑤使用(1)式相對于局部最好解Xjb，改善局部最差解的位置。如果適應(yīng)度改善，更新局部最差解的位置。

跳躍步長為

Dd=rand×(Xjb-Xw)

(1)

新位置為

(2)

如果局部最差解的新位置改進，即適應(yīng)度更高，則其代替最差解；

⑥否則，使用方程(3)相對于全局最好解Xqb，改善局部最差解的位置。如果位置改善，更新局部最差解的位置；

跳躍步長為

Dd=rand×(Xqb-Xw)

(3)

新位置為

(4)

⑦否則，使用新的隨機生成的解決方案替換最差解；

步驟7將各進化后的子種群混合，按照其適應(yīng)度的降序?qū)ΨN群P進行重新排序；

步驟8檢查是否滿足收斂要求。是，則結(jié)束算法；否則，轉(zhuǎn)到步驟3。

在步驟6中，通過子種群內(nèi)的迭代，確定最好解和最差解。對于子種群中的迭代進化，局部最好解嘗試重建以增強他們的位置，而局部最差解努力通過所有迭代中的信息交換改善他們的位置。

2 資源調(diào)度方案

當(dāng)前用于資源調(diào)度的解決方案面臨成本效率比不高的問題，需要探索更好的解決方案。本文提出了一種基于改進蛙跳算法的方案，所述算法在最小化成本的同時，具有滿足最后期限約束的能力。

2.1 問題建模

下面將調(diào)度問題建模為改進蛙跳算法問題，假設(shè)將第k個工作流中的d個任務(wù)調(diào)度到r個資源上。工作流被表示為青蛙，每只青蛙攜帶一個由d個記憶模塊構(gòu)成的模因，對應(yīng)于任務(wù)工作流。第k個蛙F(k)表示為d個記憶值的向量。單元格的數(shù)量(即單元的維度)d，由工作流中的任務(wù)數(shù)量確定。青蛙的坐標(biāo)范圍和數(shù)量由資源的數(shù)量r決定。此外，可用資源的數(shù)量r表示搜索中允許青蛙移動的空間中的食物量。因此，坐標(biāo)的值在0和其可用的資源數(shù)r之間。青蛙的位置代表任務(wù)到資源的映射。例如，一個青蛙是10維的，則其位置由10個坐標(biāo)表示，因為它表示具有10個任務(wù)的工作流，坐標(biāo)值如表1所示。如果有4個資源可用，那么青蛙的每個坐標(biāo)可以具有在0～4的值。任務(wù)與資源的映射關(guān)系如表2所示，這里，第7坐標(biāo)的值1.9表示任務(wù)7已經(jīng)被映射到資源2。符號Mi指青蛙的第i個坐標(biāo)，并且對應(yīng)于工作流中的任務(wù)ti。

表1 坐標(biāo)值Tab.1 Coordinate values

表2 任務(wù)與資源映射關(guān)系表Tab.2 Task and resource mapping relationship table

2.2 調(diào)度方案生成算法

本文所提出的算法目標(biāo)是最小化工作流的總執(zhí)行成本，并且滿足用戶要求的截止時間。使用改進的SFLA獲得調(diào)度和資源供應(yīng)問題的解決方案包括以青蛙形式生成調(diào)度方案，隨后使用適應(yīng)度函數(shù)計算蛙的適應(yīng)度的值。適應(yīng)度函數(shù)是基于優(yōu)化問題的目標(biāo)，因此，我們評估每個調(diào)度計劃的總執(zhí)行成本，并將其用作適應(yīng)度函數(shù)。

假定最初v為應(yīng)用程序租用虛擬機的數(shù)量，即在工作流中并行執(zhí)行任務(wù)的數(shù)量。假設(shè)工作流中的任務(wù)集由數(shù)組T給出。用文獻[11]中的方法計算每個資源上的任務(wù)ti所花費的時間，可以在初始虛擬機組集合(initial virtual machine，IVM)中計算。時間由n×v矩陣ETM表示，其中，n是工作流中的任務(wù)數(shù)量，v是IVM中虛擬機的數(shù)量。此外，工作流中的任務(wù)可以依賴于工作流中用于其輸出的其他任務(wù)。因此，我們通過n×n矩陣DM表示工作流的依賴性，如果任務(wù)ti取決于任務(wù)tj(任務(wù)tj是子任務(wù))，則DM[i][j]=1，否則為0。將任務(wù)的輸出傳送到其子任務(wù)所花費的時間存儲在n×n矩陣TTM中。

通過遍歷青蛙的每個記憶類型來評估青蛙的適應(yīng)度，的維度對應(yīng)于任務(wù)ti，并且其值對應(yīng)于由IVM給出的虛擬機。任務(wù)開始的時間取決于它所依賴任務(wù)的完成時間和虛擬機可用的時間。算法使用的符號說明如表3所示。

表3 符號說明Tab.3 Symbol description

算法偽代碼如下。

輸入：用戶提交的工作流應(yīng)用，設(shè)置初始虛擬機組。

輸出：總執(zhí)行成本和總執(zhí)行時間。

1. 初始化參數(shù)TEC=0, TST=0, LVM=Φ: flag=0；

2. 計算時間ETM，TTM；

3. 添加依賴關(guān)系DM；

4. For 0 < id-1

i.初始化任務(wù)和虛擬機，令ti=T[i]，VM(i)= IVM[Mi]，flag=0

ii.for 0 < jd-1；//定義任務(wù)ti的開始時間

IfDM[i][j]==1,{flag=1; STi=max(STi,CTj,CTVM (VM(i))}

If flag==0 STi=CTVM(VM(i))

iii.在資源上執(zhí)行任務(wù)所用時間exe_time=ETM(ti, VM(i))；

iv. for 0 < jd-1；//定義傳送時間

IfDM[j][i]==1 and VM(j)< >VM(i)

Trans_time+=Trans_time+TTM[i][j]

v.任務(wù)在虛擬機上的總運行時間Tot_time (i, VM(i))=exe_time+trans_time

vi. CT(i, VM(i))=STi+ Tot_time (i, VM(i))；//任務(wù)的完成時間

vii. If VM(i)LVM, add it, STVM (VM(i))=STi；//租用VM的開始時間

viii. CTVM (VM(i))= Tot_time (i, VM(i))+STi；//虛擬機的租期完成時間

5. 計算每個VM的總執(zhí)行成本和總執(zhí)行時間，令cLVM；

i. TEC=TEC+((CTVM[c]-STVM[c])*Cost[c])

ii. if(CTVM[c]>TST)

該算法提供了需要為工作流租用的VM的數(shù)量。每個任務(wù)ti與一個虛擬機VM(i)相關(guān)聯(lián)，VM(i)的開始和完成時間分別被給定為STVM和CTVM。此后，算法計算當(dāng)前解決方案的總執(zhí)行成本(TEC)和總執(zhí)行時間(TST)。因此，對應(yīng)于特定青蛙的調(diào)度方案由任務(wù)到VM的映射以及VM的開始和結(jié)束時間給出。

2.3 資源調(diào)度算法整體步驟

改進的SFLA和調(diào)度方案生成算法被組合以得到接近最優(yōu)的調(diào)度。在改進的SFLA中，根據(jù)總執(zhí)行成本來計算蛙的適應(yīng)度，其通過使用上面給出的調(diào)度方案生成算法生成調(diào)度方案來評估。如果對應(yīng)青蛙的調(diào)度時間超過最后期限，改進的SFLA用新的隨機生成解替換該青蛙。以這種方式，改進的SFLA僅保留滿足期限約束的調(diào)度方案。

步驟1利用調(diào)度方案生成算法產(chǎn)生工作流的原始調(diào)度；

步驟2通過改進的SFLA，保留滿足期限約束的調(diào)度方案。

3 仿真分析

本文使用JAVA模擬器和3個不同大小的工作流來評估性能。每個模擬仿真進行25次，并且在SFLA和PSO算法中實現(xiàn)以作比較。控制參數(shù)如表4所示。

表4 控制參數(shù)Tab.4 Control parameters

假定從一個資源到另一個資源具有不同的任務(wù)執(zhí)行時間[12]。工作流的最后期限是由對每個工作流執(zhí)行的最小和最大執(zhí)行時間的平均值得出。計算最大執(zhí)行時間的方法是，租用最少時間的單個虛擬機，并在其上執(zhí)行所有工作流任務(wù)[13-14]。通過對每個工作流任務(wù)使用一個最快類型的虛擬機來計算最小執(zhí)行時間。

1)周期性參數(shù)“n”控制執(zhí)行重建策略的頻率，也就是最佳青蛙試圖改善其位置的次數(shù)。n=1的值意味著最佳青蛙嘗試在每次迭代中重新定位。本文進行了具有不同參數(shù)設(shè)置的一系列實驗，最終確定了最佳參數(shù)組合。改進的蛙跳算法中，周期參數(shù)的取值為n=2，迭代次數(shù)定為50。

2)任務(wù)流的大小對總執(zhí)行成本的影響。本研究在3種不同工作流程上進行：工作流1為Montage，工作流2為LIGO，工作流3為Cyber Shake。所有這些工作流具有不同的結(jié)構(gòu)、不同的數(shù)據(jù)和計算特性。Montage工作流程是一個天文學(xué)應(yīng)用程序，用于根據(jù)一組輸入圖像生成天空的自定義馬賽克。大多數(shù)任務(wù)是I / O密集型，不需要高CPU處理能力。LIGO工作流程來自物理學(xué)領(lǐng)域，目的是檢測引力波。此工作流主要是CPU密集型任務(wù)，需要大量內(nèi)存。Cyber Shake用于通過生成合成地震圖來區(qū)分地震危害，并且是具有高CPU和內(nèi)存要求的數(shù)據(jù)密集型工作流。除了給出的3個應(yīng)用工作流，再隨機生成其他2個工作流：①具有少量任務(wù)(任務(wù)= 8)；②具有大量任務(wù)(任務(wù)= 150)。我們在仿真中設(shè)定云資源的時間為10，20和30單位，處理器統(tǒng)一設(shè)為4，使用的其他參數(shù)列于表5中。

表5 仿真參數(shù)Tab.5 Simulation parameters

圖4描述了由PSO，SFLA和改進的SFLA獲得的總執(zhí)行成本。從結(jié)果中可以觀察到，與PSO相比，SFLA能夠?qū)⒖倛?zhí)行成本平均降低約42%，改進的蛙跳算法平均降低約48%。

圖4 總執(zhí)行成本vs不同任務(wù)數(shù)的工作流Fig.4 Total execution costs vs workflow with different tasks

3)處理器數(shù)量對總執(zhí)行成本的影響。本文進行了嚴格仿真來研究不同數(shù)量的資源對不同大小工作流程的影響。對于每個工作流，處理器的數(shù)量在1～10內(nèi)選定；任務(wù)量的大小分別為100，200，300；處理器數(shù)量分別為 2， 4，6，8，10；最大迭代次數(shù)為50。仿真結(jié)果如圖5所示。

圖5 總執(zhí)行成本vs所使用的處理器的數(shù)量Fig.5 Total execution costs vs the number of processors used

從結(jié)果可以觀察到，執(zhí)行的時間隨著用于工作流的資源數(shù)量的增加而增加。另外，可以看出，在某些情況下，PSO的性能優(yōu)于SFLA，在其他情況下趨勢逆轉(zhuǎn)。然而，改進的蛙跳算法一直優(yōu)于PSO和SFLA。在仿真期間，隨著較高數(shù)量的資源被用于執(zhí)行，總執(zhí)行時間減少。這些結(jié)果沒有列入，因為所有的時間規(guī)劃都符合截止日期的限制。

4)算法的可擴展性評估。我們使用極大工作流的來驗證算法的可擴展性，采用100個處理器，用于執(zhí)行大小變化為300，500和1 000的隨機工作流。極大工作流下的總執(zhí)行成本比較如圖6所示。

圖6 極大工作流下的總執(zhí)行成本比較Fig.6 Comparison of total execution costs under maximum workflow

從圖6可以看出，隨著工作流大小的增加，PSO和SFLA給出可比的性能。與PSO和SFLA相比，改進的SFLA將總執(zhí)行成本平均降低了約78%，顯示其巨大的性能優(yōu)勢。因此，本文所提算法是高度可擴展的，適于在IaaS云中執(zhí)行較大的工作流應(yīng)用。

5)不同算法的吞吐量比較。進行了仿真來研究不同數(shù)量的資源節(jié)點對吞吐量的影響。對于每個工作流，處理器的數(shù)量在1～10內(nèi)選定，仿真結(jié)果如圖7所示。

從圖7中觀察到，雖然處理器數(shù)目較少時，三類算法吞吐量相差不大。但是，隨著處理器數(shù)目的增多，本文算法的優(yōu)勢體現(xiàn)出來，并且不斷增強。這更適合于大數(shù)據(jù)時代的挑戰(zhàn)，長遠來看，本文算法的吞吐量更高。

6)關(guān)于魯棒性和開銷的推斷。所提出的算法的魯棒性可以從這樣的事實推斷，本文算法能夠較好地滿足具有不同數(shù)量的任務(wù)工作流的期限約束。此外，與PSO和SFLA相比，改進的SFLA能夠?qū)⒖倛?zhí)行成本降低高達78%，顯示其良好的魯棒性。另外，成本的減少會增加執(zhí)行時間的開銷，但是本文的算法對最小化執(zhí)行成本是主要關(guān)注點，故而主要適用于優(yōu)先考慮執(zhí)行成本的情況。

圖7 不同算法的吞吐量比較Fig.7 Comparison of throughput of different algorithms

4 結(jié) 論

本文提出一種改進的蛙跳算法，用于云環(huán)境下的資源調(diào)度和調(diào)度。在滿足指定目標(biāo)約束的同時，優(yōu)化工作流的總執(zhí)行成本。對各種工作流進行了仿真，并且與SFLA和PSO算法的性能比較，仿真分析表明，改進的蛙跳算法在降低的工作流總體執(zhí)行時間方面優(yōu)于其他算法。

[1] ZOU D, XIANG Y, MIN G. Privacy preserving in cloud computing environment[J].Security & Communication Networks, 2016, 9(15):2752-2753.

[2] LI Y, TANG X, CAI W. Dynamic Bin Packing for On-Demand Cloud Resource Allocation[J]. IEEE Transactions on Parallel & Distributed Systems, 2016, 27(1):157-170.

[3] MA J, LI W, FU T, et al. A Novel Dynamic Task Scheduling Algorithm Based on Improved Genetic Algorithm in Cloud Computing[M].Berlin：Springer-Verlag , 2016:184-186.

[4] YOUNG L, MCGOUGH S, NEWHOUSE S, et al. Scheduling Architecture and Algorithms within the ICENI Grid Middleware[C]//RR Holman.UK e-science all hands meeting.Nottingham：Pergamon Press Ltd，2003:5-12.

[5] 賁可榮,張彥鐸.人工智能[M].2版.北京：清華大學(xué)出版社, 2013：134-142.

BEN Kerong, ZHANG Yanduo. Artificial Intelligence. Second Edition[M].2nd.Beijing:Tsinghua University Press, 2013：134-142.

[6] ALRASHIDI M R, ELHAWARY M E. A survey of particle swarm optimization applications in electric power systems[J]. Evolutionary Computation, IEEE Transactions on, 2009, 13(4): 913-918.

[7] ZHU G Y, ZHANG W B. An improved Shuffled Frog-leaping Algorithm to optimize component pick-and-place sequencing optimization problem[J]. Expert Systems with Applications, 2014, 41(15):6818-6829.

[8] BOTTA A, DE DONATO W, PERSICO V, et al. Integration of Cloud computing and Internet of Things[J].Future Generation Computer Systems, 2016, 56(C):684-700.

[9] ZHANG Q, YU G U, YING X U, et al. Feature selection for SAR images using the hybrid intelligent optimization algorithm[J]. Journal of Remote Sensing, 2016，38(18)：110-119.

[10] EUSUFF M M, LANSEY K E. LANSEY, K. Optimization of Water Distribution Network Design Using the Shuffled Frog Leaping Algorithm. Journal of Water Resources Planning and Management[J].Journal of Water Resources Planning & Management, 2003, 129(3):210-225.

[11] JUVE G, CHERVENAK A, DEELMAN E, et al. Characterizing and profiling scientific workflows[J]. Future Generation Computer Systems, 2013, 29(3):682-692.

[12] KOZERA R, OKULICKADF, NOAKES L. Integrated Parallel 2D-Leap-Frog Algorithm for Noisy Three Image Photometric Stereo[C]//PR Jones.PSIVT 2015 Workshops. Berlin：Springer-Verlag，2016：73-87.

[13] 黃婷婷,梁意文.云工作流任務(wù)調(diào)度的模擬退火遺傳改進算法[J].微電子學(xué)與計算機, 2016, 33(1):42-46.

HUANG Tingting, LIANG Yiwen.Improved Anomalous Improvement Algorithm for Task Scheduling of Cloud Workflow[J]. Microelectronics and Computer, 2016, 33(1): 42-46.

[14] FU X, YELIANG C, ZHU L, et al. Deadline based scheduling for data-intensive applications in clouds[J]. Journal of China Universities of Posts & Telecommunications, 2016, 23(6):8-15.

The National Natural Science Foundation of China(61302099)

Optimizationofcloudworkflowschedulingalgorithmbasedonreconstructionstrategy

LIN Haitao, JIANG Donghan

School of Electronic Engineering, Naval University of Engineering, Wuhan 430033, P.R. China)

In order to further improve the performance of the algorithm, this paper proposes an improved leapfrog algorithm, which is combined with the scheduling scheme to provide optimal scheduling for cloud workflow resource allocation. First of all, by means of joining the reconstruction strategy to improve the randomness of data the local search in the frog leaking algorithm the local optimal is effectively prevented. Secondly, we study the scheduling scheme generation algorithm, and get the optimal scheduling with the improved algorithm. Finally, the simulation experiment is carried out using Java simulator, and compared with the particle swarm optimization algorithm and the traditional frog leap algorithm. It is found that the proposed method can minimize the total execution cost while satisfying the longest deadline constraint.

frog leaping algorithm; resource scheduling; cloud workflow; reconstruction strategy

10.3979/j.issn.1673-825X.2017.06.017

2017-02-15

2017-06-05

姜棟瀚 457176001@qq.com

國家自然科學(xué)基金(61302099)

TN93

A

1673-825X(2017)06-0822-08

林海濤(1974 -)，男，山東濰坊人，副教授，博士，主要研究方向為網(wǎng)絡(luò)規(guī)劃與管理。E-mail：1174756267@qq.com。

姜棟瀚(1992 -)，男，山東煙臺人，碩士研究生，主要研究方向為通信技術(shù)與網(wǎng)絡(luò)。E-mail：457176001@qq.com。

(編輯：王敏琦)