翟青海, 謝曉蘭

(桂林理工大學(xué) a.信息科學(xué)與工程學(xué)院; b.廣西嵌入式技術(shù)與智能系統(tǒng)重點實驗室, 廣西 桂林 541006)

0 引 言

云計算技術(shù)有低成本、 配置靈活和資源利用率高的特點, 正在以極快的速度興起。云計算的計算中心由一系列的異構(gòu)網(wǎng)絡(luò)服務(wù)和計算資源組成[1]。在云計算領(lǐng)域中, 任務(wù)調(diào)度策略對用戶的任務(wù)執(zhí)行效率以及云環(huán)境下資源的使用效率有十分重要的作用。任務(wù)調(diào)度就是根據(jù)當(dāng)前的目標要求, 將不同的任務(wù)調(diào)度到合適的資源上, 建立適當(dāng)?shù)娜蝿?wù)執(zhí)行順序, 使得該調(diào)度策略盡可能滿足當(dāng)前目標要求。

混合云是一種將私有云資源和公有云資源結(jié)合起來使用的云計算環(huán)境[2]。但是由于安全性因素, 企業(yè)不希望將一些數(shù)據(jù)放至公有云上托管。而混合云模式則既可以提供私有云的安全性以達到對敏感數(shù)據(jù)的安全保證, 又可以利用公有云龐大的計算資源處理非關(guān)鍵任務(wù)和數(shù)據(jù)。因此， 研究混合云下的任務(wù)調(diào)度具有重要意義。

針對云計算環(huán)境下的工作流調(diào)度問題, 許多研究者將元啟發(fā)式算法引入到云任務(wù)調(diào)度中, 元啟發(fā)式優(yōu)化算法可以降低搜索空間的復(fù)雜性并且算法運行的時間也可以接受。羅智勇等[3]提出了一種面向云計算的花朵差分授粉工作流算法, 該算法將工作流任務(wù)和虛擬機建模成花粉, 將完整的調(diào)度序列建模成花朵, 再利用任務(wù)的偏序關(guān)系進行離散花朵授粉過程。Singh等[4]提出了基于蟻群算法的混合云工作流調(diào)度模型, 在滿足任務(wù)的最低期限的基礎(chǔ)上, 降低任務(wù)的執(zhí)行成本。徐俊等[5]提出了基于混合蛙跳算法的調(diào)度優(yōu)化策略, 該算法利用時間貪心算法來優(yōu)化初始種群以提高搜索效率, 同時增加對局部最優(yōu)個體的重建策略跳出局部最優(yōu), 增加全局搜索能力， 由于使用貪心算法提高了初始化種群質(zhì)量, 使得算法搜索耗時縮短。黃婷婷等[6]提出了基于模擬退火和遺傳算法結(jié)合的多目標優(yōu)化算法, 首先利用任務(wù)的影響程度生成合適的初始化種群; 再對交叉、 變異等遺傳操作產(chǎn)生的個體分別進行模擬退火操作, 避免引起早熟收斂問題； 最后在變異階段引入失敗率, 提高調(diào)度結(jié)果的可靠性。針對混合云環(huán)境下的任務(wù)調(diào)度問題, Sanaj等[7]提出了在混合云環(huán)境下保證服務(wù)完成時間的基礎(chǔ)上最大化私有云利潤的鯨魚優(yōu)化算法, 該算法相對人工蜂群和遺傳算法具有更高的效率。Zhou等[8]提出了兩種有效的混合云工作流調(diào)度方法, 既考慮了完成時間又考慮了完成成本: 單目標工作流調(diào)度優(yōu)化方法用于優(yōu)化截止期約束下的完成成本, 多目標工作流調(diào)度優(yōu)化方法用于同時優(yōu)化完成時間和完成成本。

本文根據(jù)混合云環(huán)境下的工作流調(diào)度問題特點建立了相關(guān)問題模型, 借鑒黏菌算法(slime mould algorithm,SMA)和粒子群算法(particle swarm optimization,PSO)的思想對算法進行重新設(shè)計: 當(dāng)黏菌個體解的質(zhì)量較差時, 有較大概率保留全局最優(yōu)解的特征, 加快較差解的收斂速度; 當(dāng)解的質(zhì)量較好時, 則進行局部變異, 避免陷入局部最優(yōu); 同時, 加入了交叉算子解決當(dāng)任務(wù)調(diào)度問題中解空間較大時, 局部尋優(yōu)粒度不夠的問題。

1 混合云環(huán)境下工作流調(diào)度模型

1.1 混合云的相關(guān)定義

1)混合云模型: 目前, 越來越多的公有云廠商和私有云廠商向混合云轉(zhuǎn)型。如果企業(yè)和用戶最終需要同時訪問本地和云服務(wù)提供商提供的資源, 則使用混合云模型, 即選擇同時使用公共云和私有云。

私有云作為企業(yè)或個人所獨有的專有云平臺, 其規(guī)模相對公有云而言不會很大, 因此提供的各類資源一般比較有限。而公有云是由云服務(wù)提供商架設(shè)好大規(guī)模的IT基礎(chǔ)設(shè)施, 通過互聯(lián)網(wǎng)為企業(yè)提供服務(wù)器、 存儲、 應(yīng)用程序等租用服務(wù)。公有云通常是指可以同時提供大量的虛擬機實例供用戶使用的云平臺。因此, 本文假設(shè)公有云總有足夠的資源處理任務(wù), 并且每一個任務(wù)都在不同的虛擬機上執(zhí)行。

2)計費模型: 公有云資源由公有云提供商提供, 云服務(wù)提供商會根據(jù)其向用戶提供的資源收取一定的費用。2017年, 微軟、 亞馬遜和阿里云等服務(wù)商實現(xiàn)了按秒計費[9], 不需要將虛擬機的啟動時間和銷毀時間計算在內(nèi)。 而私有云為企業(yè)個體所有, 數(shù)量有限, 但是基本不需要考慮使用費用的問題。因此, 本文混合云的計費方法僅考慮公有云的收費, 計算方法為

(1)

其中:pricej表示公有云資源j的單位價格；Start_Timei表示任務(wù)i的運行開始時間;End_Timei表示任務(wù)i的運行結(jié)束時間。Start_Timei和End_Timei的計算方式如式(4)和式(5)。

1.2 工作流的相關(guān)定義

1)虛擬機模型: 服務(wù)商一般采用虛擬機進行抽象表示其計算資源, 用戶可以租用虛擬機執(zhí)行工作流任務(wù), 虛擬機可以用六元組M={id,ispublic,type,mip,costper,ram}表示。其中:id表示虛擬機的標識;ispublic表示該虛擬機是否屬于公有云;type表示虛擬機的型號; 同一型號的參數(shù)mip、costper、ram值相同,mip為虛擬機的運算能力,costper為租用虛擬機的單位時間費用,ram為虛擬機的內(nèi)存。

2)任務(wù)模型: 任務(wù)采用六元組表示N={id,task_length,size,depth,parent_task_list,child_task_list}。 其中,id表示任務(wù)的標識；task_length表示任務(wù)的操作指令數(shù)；size表示任務(wù)的存儲大??；depth表示任務(wù)在工作流當(dāng)中的深度層級, 如圖1所示, 任務(wù)之間的執(zhí)行順序可以用有向無環(huán)圖(DAG)表示, 圖中共有6個任務(wù), 并且任務(wù)1的深度為1, 任務(wù)2、 3、 4、 5的深度為2, 任務(wù)6的深度為3；parent_task_list表示當(dāng)前任務(wù)的上一個深度的任務(wù)集合；child_task_list表示當(dāng)前任務(wù)的下一個深度的任務(wù)集合。

圖1 任務(wù)深度

3)執(zhí)行時間Texe(ti,mj)表示工作流中任務(wù)ti在虛擬機mj上的執(zhí)行時間

Texe(ti,mj)=task_lengthti/mipmj,

(2)

其中,mipmj表示虛擬機mj的處理能力。

4)傳輸時間Ttrans(ti,tk)表示任務(wù)ti和任務(wù)tk之間的數(shù)據(jù)傳輸時間, 可由式(3)計算得出。當(dāng)任務(wù)ti和任務(wù)tk處于同一個虛擬機時, 則傳輸時間為0。

(3)

其中:sizeti表示任務(wù)ti的傳出數(shù)據(jù)大小;Bwi和Bwk分別表示任務(wù)ti和任務(wù)tk所在虛擬機的帶寬。

5)任務(wù)ti的實際開始時間Start_Timei的計算方式如式(4)所示。當(dāng)該任務(wù)沒有父節(jié)點時, 則為起始節(jié)點, 開始時間為0； 否則， 需要等待該任務(wù)的所有父節(jié)點任務(wù)執(zhí)行完成并將數(shù)據(jù)傳輸至該任務(wù)所在的虛擬機上才能開始執(zhí)行。

(4)

6)任務(wù)ti的完成時間End_Timei表示任務(wù)ti在對應(yīng)虛擬機上的完成時間

End_Timei=Start_Timei+Texe(ti,mj)+Ttrans(ti,child)。

(5)

1.3 多目標模型

假設(shè)有n個任務(wù)Task={t1,t2, …,tn},m個虛擬機vm={vm1,vm2, …,vmm}, 則關(guān)于調(diào)度目標模型如下:

1)調(diào)度時間Tmakespan, 表示整個工作流的調(diào)度執(zhí)行時間, 即為最后一個任務(wù)計算完成的時間和第一個任務(wù)開始的時間差

Tmakespan=End_Timelast-Start_Timefirst。

(6)

2)執(zhí)行費用cost, 表示完成整個工作流任務(wù)所需要的執(zhí)行花費

(7)

costperj表示租用虛擬機j的費用。

3)多目標優(yōu)化, 適應(yīng)度是評價智能算法解優(yōu)劣程度的重要指標, 由于本模型的目標是使調(diào)度時間Tmakespan和執(zhí)行費用cost盡可能小, 因此適應(yīng)度函數(shù)可以由調(diào)度時間和完成成本計算

Fitness=w1Tmakespan+w2cost,

(8)

w1、w2分別為調(diào)度時間和執(zhí)行費用的權(quán)重, 且滿足w1+w2=1。在本文中, 適應(yīng)度值Fitness越小, 表示解的質(zhì)量越好。

1.4 編碼模型

參考文獻[2]的編碼方法解決混合云環(huán)境下的工作流調(diào)度編碼問題。一個可行解的調(diào)度方案如式(9)所示, 由3條染色體編碼組成

scheduler=(task_order,vm_order,vm_type),

(9)

3條染色體都由一個一維數(shù)組表示, 由于一個任務(wù)最多可放置在一個虛擬機上, 且本文定義公有云資源數(shù)量為無限多, 因此3個數(shù)組長度都相同, 長度為參與該次調(diào)度過程的任務(wù)數(shù)量。task_order表示任務(wù)的調(diào)度順序, 數(shù)組中每個值表示任務(wù)的id, 該數(shù)組表示具有依賴關(guān)系的調(diào)度順序；vm_order表示每個任務(wù)到虛擬機的映射關(guān)系, 數(shù)組中每個值表示虛擬機的id；vm_type表示每個虛擬機對應(yīng)的虛擬機型號。

2 算法流程

2.1 黏菌算法

黏菌算法是根據(jù)黏菌在尋找食物過程中的變化建立的智能搜索算法。主要模擬黏菌在覓食過程中的行為和形態(tài)變化, 通過權(quán)值指標模擬黏菌靜脈狀管的形態(tài)和收縮模式之間的3種相關(guān)性[10]。在黏菌覓食過程中, 根據(jù)空氣中的食物濃度接近食物, 食物濃度越高, 生物振蕩波越強, 細胞質(zhì)流動越快, 黏菌靜脈狀管越粗, 該區(qū)域會聚集更多黏菌; 當(dāng)該區(qū)域的食物濃度較低時, 黏菌會有較大概率探索其他區(qū)域。黏菌接近食物的表達式

(10)

p=tanh|S(i)-DF|;

(11)

a=arctanh(-t/tmax)+1)。

(12)

(13)

式中:r為[0, 1]間的隨機數(shù);bF表示在當(dāng)前迭代過程中最佳的適應(yīng)度;S(i)表示當(dāng)前個體適應(yīng)度值;wF表示在當(dāng)前迭代過程中最差的適應(yīng)度值;i=C表示種群中適應(yīng)度值最好的前一半個體;i=O表示其余個體;Sort(i)按照適應(yīng)度值排序的氣味指數(shù)。

當(dāng)黏菌找到了更好的食物, 仍然會分離出部分個體探索其他區(qū)域進行全局尋優(yōu), 黏菌種群更新位置的計算方法為

(14)

rand是[0, 1]間的隨機數(shù),LB與UB表示解空間的上下邊界,z是進行全局尋優(yōu)的閾值。

2.2 本文算法設(shè)計

由于傳統(tǒng)的黏菌算法和粒子群算法都是用于連續(xù)的數(shù)值優(yōu)化, 進行迭代計算的都是實數(shù), 但是工作流調(diào)度問題都是組合優(yōu)化問題, 解由3組整數(shù)序列組成, 因此， 本文對算法進行重新設(shè)計。本文工作流調(diào)度算法的基本思想如下: 首先隨機初始化符合工作流執(zhí)行序列的初始種群, 計算種群中個體的適應(yīng)度值, 并確定最佳的適應(yīng)度值, 之后采用交叉算子對每個個體進行計算, 計算個體的適應(yīng)度值判斷是否進行粒子群優(yōu)化全局尋優(yōu)或局部變異， 最后標識出當(dāng)前種群中的最優(yōu)個體Gbest。算法的主要符號說明如表1, 具體步驟如下。

表1 主要符號說明

步驟1:按照算法1初始化種群, 并計算每個個體的適應(yīng)度值和當(dāng)前最優(yōu)個體Gbest。

算法1 種群初始化算法INPUT: 工作流任務(wù)集合G, 種群規(guī)模NPOUTPUT: 相應(yīng)規(guī)模的個體種群pop1.init i=02.while i

步驟2:按照文獻[2]的做法更新任務(wù)調(diào)度順序task_order。

步驟3:每個個體的vm_type根據(jù)算法2進行交叉計算, 其中v和b的計算方法為

v=|-b+(2·b)·r|;

(15)

b=0.25-iter/(max_iter·4)。

(16)

其中:r表示區(qū)間[0, 1]內(nèi)的隨機值;iter表示當(dāng)前迭代次數(shù);max_iter表示最大迭代次數(shù)；v表示交叉的位點個數(shù), 隨著迭代次數(shù)的增加而逐漸變小, 細化局部尋優(yōu)的粒度進而增加算法的局部尋優(yōu)能力。

算法2 交叉算法INPUT: 交叉?zhèn)€體X, 較優(yōu)個體XbOUTPUT: 交叉?zhèn)€體X’1.按照式(15)計算交叉位點個數(shù)num2.init start=random(0, T_length-num)3.init end=start+num4.while start

步驟4:按照式(17)判斷個體的vm_type迭代方式, 其中r表示區(qū)間[0, 1]內(nèi)的隨機值, 當(dāng)解的質(zhì)量較差時, 則有較大概率按照算法3進行迭代, 這樣可以在前期加快全局尋優(yōu)的速度。p值的計算方法為式(18), 在算法3中個體的速度值Vel按照式(19)和式(20)進行計算。由于個體位置vm_type的值為離散型變量, 采用相減的計算方法意義不大, 因此， 本文采用與運算處理離散型變量加快解的收斂速度。

(17)

p=tanh|best_fitness-fitness(X(j))|;

(18)

(19)

(20)

其中：c1和c2分別表示全局最優(yōu)解和個體最優(yōu)解的權(quán)重;best_fitness表示全局最優(yōu)解的適應(yīng)度值;fitness(X(j))表示當(dāng)前個體j的適應(yīng)度值;xg和xb分別表示全局最優(yōu)解的vm_type和個體中最優(yōu)解的vm_type。

算法3 全局尋優(yōu)算法INPUT: 全局尋優(yōu)個體X, 全局最優(yōu)個體Xg, 個體最優(yōu)XbOUTPUT: 全局尋優(yōu)個體X’1. init j=02. while j

在算法4變異算法中,v和b的計算方式如式(15)和式(16)。由于解空間很大, 因此算法4并沒有對所有位點進行變異,而是基于較優(yōu)的個體選擇局部位點進行變異。

算法4 局部變異算法INPUT: 局部變異個體XOUTPUT: 局部變異個體X’1.按照式(15)計算交叉?zhèn)€數(shù)num2.init j=0, x=[num]3.while j

步驟5:按照式(8)計算每個個體的適應(yīng)度。

步驟6:更新當(dāng)前迭代全局最優(yōu)解和個體在迭代中的最優(yōu)解,并判斷是否達到最大迭代次數(shù),若未達到,則繼續(xù)從步驟2開始執(zhí)行；若達到最大迭代次數(shù),則停止搜索, 當(dāng)前的全局最優(yōu)解即為最終結(jié)果。

3 實驗與結(jié)果分析

為驗證本文設(shè)計算法在處理混合云環(huán)境下考慮工作流任務(wù)調(diào)度問題的有效性和可行性, 使用WorkflowSim作為仿真平臺, 在同樣的條件和環(huán)境下實驗, 并和經(jīng)典的粒子群算法、 遺傳算法以及文獻[11]的算法進行對比。設(shè)置10種虛擬機類型,虛擬機配置參考亞馬遜的類型[12](表2),帶寬速度設(shè)置為0.02 GB/s,存儲費用為0.000 1 ＄/(GB·h)。實驗設(shè)置迭代次數(shù)為1 000次,w1、w2為0.5, 種群個體數(shù)為60, 私有云虛擬機數(shù)占總虛擬機數(shù)的1/5。實驗采用4種科學(xué)工作流模型, 即模型Epigenomic、

表2 虛擬機配置

Inspiral、 Montage和 Sipht。將這4種工作流的數(shù)據(jù)集進行優(yōu)化調(diào)度, 各類算法在不同數(shù)據(jù)集和不同任務(wù)數(shù)量的完成時間和完成成本如圖2—4所示。隨著任務(wù)數(shù)量的增加, 由于遺傳算法的全局尋優(yōu)能力較低, 因此性能普遍較低, 而文獻[11]的改進算法相對于遺傳算法和粒子群算法這兩種算法效果都要好。但是在任務(wù)數(shù)量較多時, 由于本文的算法有更細粒度的局部尋優(yōu)能力, 因此在4種數(shù)據(jù)集上的整體表現(xiàn)都優(yōu)于其他3種算法。

圖2 50個任務(wù)完成時間(a)和完成成本(b)

圖3 100個任務(wù)完成時間(a)和完成成本(b)

圖4 1 000個任務(wù)完成時間(a)和完成成本(b)

4 結(jié)束語

本文以黏菌算法為基本的研究思路, 在算法前期借鑒了粒子群算法的思想, 加快全局尋優(yōu)速度, 同時增加了交叉算子提高局部尋優(yōu)的粒度, 在算法迭代后期通過變異算子, 避免陷入局部最優(yōu)。從實驗仿真結(jié)果看, 隨著任務(wù)數(shù)量的增加, 本文算法的尋優(yōu)能力比其他算法更優(yōu)。但是, 本文算法依然存在有待改進的地方, 如當(dāng)某一個任務(wù)的屬性值和其他任務(wù)有明顯差異時, 該任務(wù)的分配結(jié)果會顯著影響算法尋優(yōu), 后續(xù)將針對該問題進行研究。