馬學(xué)森，許雪梅，蔣功輝，喬 焰，周天保

（1.合肥工業(yè)大學(xué) 計算機與信息學(xué)院，合肥 230601；2.安全關(guān)鍵工業(yè)測控技術(shù)教育部工程研究中心（合肥工業(yè)大學(xué)），合肥 230009）

0 引言

近年來，隨著互聯(lián)網(wǎng)和5G 快速發(fā)展，云服務(wù)模式不斷成熟，云計算在學(xué)術(shù)界、工業(yè)界和政府部門等場合得到了廣泛應(yīng)用，用戶應(yīng)用程序普遍從集群和網(wǎng)格大規(guī)模遷移到基礎(chǔ)設(shè)施及服務(wù)（Infrastructure as a Service，IaaS）云，云提供資源并向用戶定價收費［1］。應(yīng)用程序主要由一組數(shù)據(jù)相互依賴的任務(wù)組成，在云端形成有向無環(huán)圖（Directed Acyclic Graph，DAG）工作流［2］。具有截止期的工作流要求應(yīng)用程序都必須在有限的時間內(nèi)完成［3］。因此，如何在具有截止期約束的條件下進行工作流調(diào)度成為近年來研究的熱點之一。此外，云工作流調(diào)度的性能一方面影響用戶的響應(yīng)時間，另一方面關(guān)乎云提供商資源成本投入。用戶希望在截止期內(nèi)盡快完成應(yīng)用程序工作流，而云提供商希望以較低成本滿足用戶需求以獲得更高利潤。因此，研究如何合理調(diào)度DAG 工作流，保證工作流在截止期內(nèi)完成前提下，在用戶與供應(yīng)商之間權(quán)衡工作流完成時間和執(zhí)行成本有重要意義。

云計算中的任務(wù)調(diào)度已經(jīng)被證明是非確定性多項式（Non-deterministic Polynomial，NP）難問題［4］，尤其將工作流模型應(yīng)用于云任務(wù)調(diào)度中，使問題更加復(fù)雜。近年來，眾多學(xué)者提出了不同的工作流調(diào)度目標(biāo)模型和算法：李啟銳等［5］根據(jù)變化的用戶數(shù)量及資源采用不同的調(diào)度策略需求，建立了云作業(yè)調(diào)度系統(tǒng)模型，以此解決一種由傳輸時間、等待時間和執(zhí)行時間三部分構(gòu)成的多目標(biāo)優(yōu)化問題，所提算法有效降低作業(yè)的整體完工時間；Han 等［6］提出一種啟發(fā)式算法通過同時最小化工作流的完成時間和執(zhí)行成本來解決工作流調(diào)度問題；Alkayal 等［7］構(gòu)建了工作流完成時間、執(zhí)行成本以及系統(tǒng)吞吐量的多目標(biāo)模型，基于新的排序策略提出改進的多目標(biāo)粒子群算法，具有較好的效果；童釗等［8］提出一種基于強化學(xué)習(xí)的工作流調(diào)度算法，采用Q-learning 算法及線性加權(quán)法，優(yōu)化工作流的完成時間及執(zhí)行成本。上述研究主要以工作流完成時間、執(zhí)行成本等目標(biāo)優(yōu)化為主，具有較好的優(yōu)化效果，但是針對在滿足所有工作流截止期約束下，以優(yōu)化其完成時間及執(zhí)行成本為目標(biāo)的研究相對較少。

文獻［9-12］中考慮了工作流的截止期，建立了不同的工作流調(diào)度模型，提出了不同算法解決具有截止期工作流的調(diào)度問題，具有較好的效果；但上述文獻均以最小化工作流執(zhí)行成本為優(yōu)化目標(biāo)，解決的是在工作流完成時間的前提下，以最小化工作流執(zhí)行成本為目標(biāo)的單目標(biāo)問題。針對具有截止期的工作流，權(quán)衡工作流的完成時間與執(zhí)行成本的多目標(biāo)優(yōu)化問題亟須進一步研究。

此外，采用線性加權(quán)法求解多目標(biāo)優(yōu)化問題時，目標(biāo)的權(quán)重系數(shù)對優(yōu)化效果產(chǎn)生很大的影響，因此，大量研究者在權(quán)重系數(shù)的選擇上進行了研究。孫長亞等［13］將任務(wù)完成時間、執(zhí)行成本及負(fù)載均衡根據(jù)任務(wù)需求人為確定一組權(quán)重系數(shù)；方伯芃等［14］將工作流服務(wù)費用及執(zhí)行成本的權(quán)重系數(shù)人為確定三組依次做實驗。上述實驗權(quán)重系數(shù)的確定都具有一定的主觀性。雖然上述基于強化學(xué)習(xí)的工作流調(diào)度算法通過大量實驗可以得到一組多目標(biāo)的權(quán)重系數(shù)，具有一定的客觀性，但是其復(fù)雜度高，并且權(quán)重系數(shù)是個靜態(tài)值，無法動態(tài)調(diào)整優(yōu)化。因此，如何在工作流調(diào)度過程中，根據(jù)工作流的變化自適應(yīng)確定各個目標(biāo)的權(quán)重系數(shù)，將多目標(biāo)的值權(quán)衡最小化亟須進一步研究。

目前，云工作流調(diào)度算法主要分為非啟發(fā)式算法與啟發(fā)式算法兩種。Max-Min 算法［15］等經(jīng)典的非啟發(fā)式算法屬于盡力服務(wù)類調(diào)度算法，目的是在更短時間內(nèi)找到工作流調(diào)度方案，而不是以工作流完成時間為優(yōu)化目標(biāo)。最早完成時間（Heterogeneous Earliest Finish Time，HEFT）算法［16］等傳統(tǒng)的啟發(fā)式算法主要以工作流完成時間最少為優(yōu)化目標(biāo)，未同時考慮資源代價問題，難以解決同時滿足用戶及云提供商需求的問題；且傳統(tǒng)啟發(fā)式算法效率低，而智能啟發(fā)式算法效率高，可在短時間內(nèi)找到問題的解決方案，而且還可以應(yīng)用于帶有約束條件的更為復(fù)雜的調(diào)度問題。最經(jīng)典的智能啟發(fā)式算法包括蟻群算法（Ant Colony Optimization，ACO）［17］、遺傳算法（Genetic Algorithm，GA）［18］和粒子群優(yōu)化（Particle Swarm Optimization，PSO）算法［19］等，其中：ACO 計算開銷較大，一般用來解決在圖上搜索路徑的問題。GA 通過選擇、交叉和變異保證問題解的多樣性進而獲得問題的最優(yōu)解。PSO 算法相較于ACO、GA 等全局優(yōu)化算法，其優(yōu)點是需要調(diào)整的參數(shù)較少、實現(xiàn)簡單、計算復(fù)雜度與問題規(guī)模呈多項式關(guān)系等，且可通過迭代尋找最優(yōu)解，在求解云工作流調(diào)度問題上具有天然的優(yōu)勢；但PSO 與其他智能啟發(fā)式算法相似，具有易陷入局部最優(yōu)、早熟收斂的缺點。因此，一些研究針對PSO 的缺點進行改進。張曉麗［20］引入混沌搜索對PSO 進行改進，提出了一種基于粒子群優(yōu)化的云工作流調(diào)度算法，實驗結(jié)果表明，比改進后的ACO 及改進后的GA 尋優(yōu)效果更好；李學(xué)俊等［21］提出了改進粒子群優(yōu)化算法（簡記為慣性權(quán)重粒子群算法（Weight Particle Swarm Optimization，WPSO）精準(zhǔn)調(diào)整粒子速度的自適應(yīng)權(quán)重，求解滿足時間約束時能耗最優(yōu)的調(diào)度問題，考慮了粒子易陷入局部最優(yōu)的問題，但忽略了對種群初始化方式進行改進可以提高收斂速度的問題。因此，對如何應(yīng)用PSO 實現(xiàn)工作流調(diào)度問題需要做進一步研究。

為解決以上問題，本文在考慮DAG 云工作流的截止期約束下，在用戶與供應(yīng)商之間權(quán)衡工作流的完成時間與執(zhí)行成本，提出一種混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法（Hybrid Adaptive Particle Swarm Optimization algorithm for workflow scheduling，HAPSO）。首先，從用戶及云提供商角度構(gòu)建了DAG 云工作流調(diào)度模型；其次，針對工作流完成時間與執(zhí)行成本的沖突問題，引入范數(shù)理想點方法，同時與自適應(yīng)權(quán)重結(jié)合，將DAG 調(diào)度模型轉(zhuǎn)化為權(quán)衡工作流完成時間與執(zhí)行成本優(yōu)化目標(biāo)的數(shù)學(xué)問題；最后，通過改進PSO，平衡粒子群的局部搜索與全局搜索能力，進而對DAG 完成時間與執(zhí)行成本的目標(biāo)優(yōu)化問題進行求解。通過實驗驗證了HAPSO 調(diào)度云工作流具有較好的優(yōu)越性。

1 DAG云工作流調(diào)度模型

1.1 模型描述

本文提出的DAG 云工作流調(diào)度模型如圖1 所示。DAG云工作流調(diào)度模型主要由用戶提交的工作流應(yīng)用程序、設(shè)計算法生成調(diào)度方案和云提供商提供資源完成工作流調(diào)度三部分組成。在該模型中，用戶提交應(yīng)用程序工作流，用DAG圖表示。工作流到達后，首先確定工作流調(diào)度的優(yōu)化目標(biāo)，本文調(diào)度目標(biāo)是在滿足工作流截止期的同時，權(quán)衡用戶與云提供商之間的需求最小化；然后通過本文設(shè)計的HAPSO 對用戶提交的工作流進行處理，找到目標(biāo)最優(yōu)的調(diào)度方案；最后云提供商根據(jù)調(diào)度方案將工作流中的任務(wù)分配到相應(yīng)的虛擬資源節(jié)點上，實現(xiàn)工作流的調(diào)度。

圖1 DAG云工作流調(diào)度模型的架構(gòu)Fig.1 Architecture of DAG cloud workflow scheduling model

本文提出的DAG 云工作流調(diào)度模型中的工作流用DAG表示。DAG 可以符號表示為G(T，E)，其中T為DAG 中的任務(wù)集合，T={t1，t2，…，tn}，ti(1 ≤i≤n)為DAG 的一個頂點，表示第i個任務(wù)。E為DAG 中任務(wù)之間的約束關(guān)系集合，E={(ti，tj)|ti，tj∈T}，其中任意一個有向邊eij（DAG 中的邊）代表依賴任務(wù)ti到tj之間的數(shù)據(jù)傳輸量。一般假設(shè)DAG 只有一個入口節(jié)點（無父節(jié)點）和一個出口節(jié)點（無子節(jié)點）。云提供商負(fù)責(zé)提供資源，主機p個，虛擬機m個，虛擬節(jié)點資源（虛擬機）表示為VM={v0，v1，…，vm-1}，其中vj(0 ≤j≤m-1)表示序號為j的虛擬機。每個任務(wù)分配到一個虛擬機運行，任務(wù)與虛擬機的分配映射關(guān)系用矩陣Z=(zij)表示。zij=0 表示任務(wù)ti不分配到虛擬機vj；zij=1表示任務(wù)ti分配到虛擬機vj。

DAG 云工作流調(diào)度模型解決的問題是：在保證工作流在截止期內(nèi)完成前提下，找到權(quán)衡工作流完成時間與工作流執(zhí)行成本最小化的DAG 云工作流調(diào)度方案，完成工作流調(diào)度。

1.2 調(diào)度目標(biāo)

本文提出的DAG 云工作流調(diào)度模型解決的問題是在工作流的截止期約束下，權(quán)衡工作流的完成時間Makespan和執(zhí)行成本Cost。在本節(jié)中，對調(diào)度優(yōu)化目標(biāo)進行相關(guān)定義。

定義1工作流完成時間Makespan。

DAG 工作流的完成時間Makespan為DAG 中的任務(wù)最大完成時間：

其中：任務(wù)ti完成時間FT(ti)包括響應(yīng)時間ST(ti)、執(zhí)行時間ET（ti）和傳輸時間TT(ti，ts)，滿足關(guān)系

其中：succ（ti）表示任務(wù)ti的所有直接后繼任務(wù)集合，任務(wù)ts為任務(wù)ti的直接后繼任務(wù)之一。

通過式（3）計算得到ST(ti)：

式（3）中：pred（ti）為任務(wù)ti的所有直接前驅(qū)任務(wù)，avai[vmti]表示虛擬機準(zhǔn)備執(zhí)行任務(wù)ti的最早時間。入口任務(wù)tentry可以立刻獲得資源，其響應(yīng)時間為0；非入口任務(wù)響應(yīng)時間取決于該任務(wù)所在虛擬機的開始執(zhí)行時間和該任務(wù)的所有前驅(qū)任務(wù)都完成的時間。

任務(wù)ti的執(zhí)行時間

其中：Tlengthi為任務(wù)ti的長度，vj為虛擬機j的CPU 速度，pej為虛擬機j的CPU 數(shù)目。

任務(wù)ti到其直接后繼任務(wù)ts的數(shù)據(jù)傳輸時間為：

其中：若任務(wù)ti與其直接后繼任務(wù)ts在不同虛擬機上執(zhí)行，則存在傳輸時間；否則，傳輸時間為0。vi是任務(wù)ti分配的虛擬機，vs是將要執(zhí)行任務(wù)ts的虛擬機，bw為虛擬機vi和vs的傳輸帶寬。本文假設(shè)虛擬機帶寬相同。

定義2工作流執(zhí)行成本Cost。

云工作流調(diào)度中，虛擬機按單位時間收費，Tunit表示IaaS云的單位時間。工作流執(zhí)行成本Cost為：

式（6）中，總執(zhí)行時間為：

總傳輸時間為：

其中：vm_costj表示虛擬機j單位時間執(zhí)行成本，bw_cost表示虛擬機單位時間傳輸成本。

定義3工作流的約束條件。

本文考慮工作流調(diào)度的三種約束：資源約束、任務(wù)間依賴約束以及截止期約束。

1）資源約束。

每個任務(wù)只能由一個虛擬機處理：

表示在分配矩陣Z的每一列中，只有一個元素的值為1，以保證每個任務(wù)只能分配到某一個虛擬機上執(zhí)行。n為任務(wù)的數(shù)目，m為虛擬機數(shù)目。

2）任務(wù)間依賴約束。

任務(wù)的執(zhí)行和傳輸?shù)钠鹗紩r間及結(jié)束時間滿足的條件為：

其中：Ts1、Ts2分別為任務(wù)的執(zhí)行起始時間和傳輸起始時間，Te1、Te2分別為任務(wù)的執(zhí)行結(jié)束時間和傳輸結(jié)束時間。

其中：1 ≤i≤n，1 ≤k≤n，0 ≤j≤m-1，i≠k。約束（12）表示，對于每個任務(wù)ti進行傳輸之前必須完成執(zhí)行；約束（13）和（14）保證被分配到同一虛擬機的任務(wù)順利執(zhí)行和傳輸。例如，兩個任務(wù)ti、tk被分配到同一虛擬機vi，任務(wù)tk在ti之后執(zhí)行。約束（13）表示任務(wù)ti執(zhí)行的結(jié)束時間在任務(wù)tk執(zhí)行時間之前；約束（14）表示任務(wù)ti傳輸?shù)慕Y(jié)束時間在任務(wù)tk執(zhí)行時間之前。

3）截止期約束。

為保證DAG 工作流在截止期內(nèi)完成，需滿足：

其中：工作流的截止期［22］由工作流最快調(diào)度完成時間與截止期因子γ共同決定。由最早完成時間算法HEFT 得到的值作為，γ用來控制工作流截止期的緊急程度。

在工作流調(diào)度過程中，針對可能出現(xiàn)某些任務(wù)在隊列中等待時間過長導(dǎo)致工作流不能在截止期內(nèi)完成的情況，定義任務(wù)ti的最遲開始時間為：

其中：succ（ti）表示任務(wù)ti的所有直接后繼任務(wù)集合，任務(wù)ts為任務(wù)ti的直接后繼任務(wù)之一。沒有直接后繼任務(wù)的任務(wù)ti的最遲開始執(zhí)行時間為工作流的截止期與ti的最小執(zhí)行時間之差，有直接后繼任務(wù)ts的任務(wù)ti的最遲開始執(zhí)行時間為任務(wù)ts的最遲開始時間減去兩者的最小傳輸時間得到的值與任務(wù)ti的最小執(zhí)行時間之差。

定義4調(diào)度目標(biāo)優(yōu)化問題。

將DAG 云工作流調(diào)度模型轉(zhuǎn)化為目標(biāo)優(yōu)化數(shù)學(xué)問題，如式（18）所示，即本文需要解決的問題是找到最小值f。通過范數(shù)理想點將Makespan與Cost設(shè)置為同一量級，η1+η2=1，fT代表工作流完成時間，由HEFT 得到的值作為最快調(diào)度完成時間，fC代表工作流執(zhí)行成本，由貪心算法以執(zhí)行成本Cost為目標(biāo)調(diào)度得到的值作為最小工作流執(zhí)行成本，η1、η2分別為工作流完成時間與執(zhí)行成本部分的權(quán)重。

因此，本文DAG 工作流優(yōu)化目標(biāo)形式化定義為式（19）。Minf表示對Makespan和Cost的兩個沖突目標(biāo)在工作流截止期約束條件下進行協(xié)調(diào)折中處理，同時得到目標(biāo)函數(shù)最小值f。

定理1對于任意DAG 工作流，總存在一組系數(shù)使得f最小，即?DAG，?（η1，η2）使得f最小。

由定理證明可知，存在一組權(quán)重系數(shù)（η1，η2）使得f最小，且η1、η2值隨著fT、fC值自適應(yīng)改變，由證明過程可推導(dǎo)出：

混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法的調(diào)度目標(biāo)為最小化f，通過求出全局最優(yōu)解獲得滿足工作流截止期同時，權(quán)衡工作流完成時間與執(zhí)行成本最小值的工作流調(diào)度方案，實現(xiàn)工作流的最佳調(diào)度。

2 混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法

云工作流調(diào)度屬于離散優(yōu)化問題，將粒子群優(yōu)化（PSO）算法的解進行離散化編碼可以很好地解決云工作流調(diào)度問題；但是PSO 存在易陷入局部收斂的問題。針對此問題，本文提出混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法HAPSO，對PSO 進行4 個方面改進：1）引入螢火蟲算法（Firefly Algorithm，F(xiàn)A）［23］得到的調(diào)度方案來初始化HAPSO 粒子的初始位置，避免粒子初期由于搜索范圍大導(dǎo)致搜索時間長的問題；2）采用非線性遞減方法對慣性權(quán)重進行自適應(yīng)動態(tài)調(diào)整，結(jié)合伽馬隨機函數(shù)動態(tài)變化學(xué)習(xí)因子大小，跳出局部收斂狀態(tài)；3）引入花朵授粉算法的概率切換機制，自適應(yīng)調(diào)整局部搜索與全局搜索策略；4）對越界情況處理提出改進策略。

2.1 離散化編碼

HAPSO 采用最小位置原則（Smallest Position Value，SPV）［24］編碼方式將粒子位置映射到虛擬機資源上，每個粒子的位置代表一種調(diào)度策略，粒子的坐標(biāo)代表調(diào)度策略的映射方式，粒子的適應(yīng)度值代表調(diào)度策略的目標(biāo)值。所有可行的調(diào)度策略構(gòu)成了整個算法的解空間，每個粒子都在解空間中尋找最優(yōu)解。第i次迭代中每個粒子的位置構(gòu)成一個向量Xi（Xi=｛xi1，xi2，…，xin｝），n為構(gòu)成DAG 工作流的任務(wù)總數(shù)，xin∈Xi表示一個粒子在第i次迭代后每個任務(wù)被分配到虛擬機的編號。對向量Xi進行處理：

將第t次迭代后粒子位置按SPV 方式處理再進行求余，得到任務(wù)ti所對應(yīng)的虛擬機編號，實現(xiàn)任務(wù)到虛擬機資源的映射。m為虛擬機數(shù)目指的是第i次迭代的任務(wù)序號為d的位置。

假設(shè)調(diào)度一個由6 個任務(wù)構(gòu)成的DAG 工作流，虛擬機的個數(shù)為4。6 個任務(wù)分配到4 個虛擬機，虛擬機編號為｛0，1，2，3｝，若HAPSO 得到最優(yōu)解為｛2.4，7.1，5.3，6.7，3.5，4.2｝，經(jīng)編碼處理得到任務(wù)映射到虛擬機的結(jié)果如表1所示。

表1 粒子編碼Tab.1 Particle coding

由解可知，任務(wù)6 分配到虛擬機0，任務(wù)3 分配到虛擬機1，任務(wù)1 和4 分配到虛擬機2，任務(wù)2 和5 分配到虛擬機3。被分配到同一虛擬機上的任務(wù)則按照依賴順序先后執(zhí)行，被分配到不同虛擬機上的任務(wù)但具有依賴順序關(guān)系的則父任務(wù)執(zhí)行完之后再進行數(shù)據(jù)傳輸，子任務(wù)才能執(zhí)行。

2.2 種群初始化

螢火蟲算法具有參數(shù)少、易實現(xiàn)等優(yōu)點，采用多個位置并行的全局隨機搜索策略，在求解本文優(yōu)化目標(biāo)問題時，能夠同時獲得每個任務(wù)被分配的虛擬機資源。因此，為了改進粒子群初始種群的質(zhì)量，將螢火蟲算法得到的工作流調(diào)度方案X=｛x1，x2，…，xn｝作為HAPSO 粒子i第一次迭代時的個體最優(yōu)值與全局最優(yōu)值初 始值。n為 構(gòu)成DAG 工作流的任務(wù)數(shù)。HAPSO 中每個粒子先隨機初始化速度，再根據(jù)個體最優(yōu)值以及全局最優(yōu)值更新自身的速度以及位置。圖2 展示了HAPSO 中粒子更新位置的具體過程。

圖2 粒子位置更新示意圖Fig.2 Schematic diagram of updating particle position

式（22）計算粒子i第t+1 次迭代時的速度：

其中：w為慣性權(quán)重，c1和c2為學(xué)習(xí)因子，r1和r2是［0，1］內(nèi)隨機數(shù)分別為第t次迭代時個體最優(yōu)解和全局最優(yōu)解為第t次迭代時粒子i飛行的速度為第t次迭代時粒子i的位置。

式（23）計算第t+1 次迭代時粒子i的位置

在初始化HAPSO 時，F(xiàn)A 得到的最優(yōu)工作流調(diào)度方案X=｛x1，x2，…，xn｝映射到HAPSO 各粒子位置X1=｛x11，x12，…，x1n｝作為第一次迭代時的個體最優(yōu)值以及全局最優(yōu)值。在后續(xù)粒子迭代過程中，每個粒子根據(jù)HAPSO 的位置更新公式不斷調(diào)整該初始值，在解空間尋找最優(yōu)的調(diào)度策略，直到找到最優(yōu)解或者達到迭代次數(shù)。種群初始化算法表述如算法1。

算法1 種群初始化算法。

輸入 任務(wù)列表Cloudlets，虛擬機列表Vms；

輸出 初始化種群Swarm。

2.3 自適應(yīng)動態(tài)優(yōu)化參數(shù)

由圖2 可知，慣性權(quán)重w代表當(dāng)前迭代粒子速度對下一次迭代時粒子速度的影響程度。學(xué)習(xí)因子c1、c2分別代表當(dāng)前迭代個體最優(yōu)值與全局最優(yōu)值對下一次迭代粒子速度的影響程度，r1和r2是［0，1］內(nèi)隨機數(shù)。因此，針對粒子在對虛擬機資源分配給任務(wù)時易陷入局部最優(yōu)的問題，對慣性因子、學(xué)習(xí)因子進行改進，根據(jù)粒子迭代次數(shù)自適應(yīng)動態(tài)改變參數(shù)值，提高粒子的搜索效率。

1）慣性權(quán)重自適應(yīng)。

由式（22）可知：w>1 時，粒子速度會越來越大，最終粒子處于發(fā)散狀態(tài)。w∈(0，1]時，w越大，對下一次迭代速度影響越大，增大種群多樣性，有利于算法前期探索搜索空間；w越小，對下一次迭代速度影響越小，有利于算法后期局部開發(fā)能力。胡堂清等［25］采用非線性遞減函數(shù)對慣性權(quán)重w處理，實驗證明采用非線性處理得到的收斂效果優(yōu)于線性處理。因此，本文采用非線性遞減方式對慣性權(quán)重處理，如式（24）所示：

其中：wmax=0.9，wmin=0.4［25］，t為當(dāng)前迭代次數(shù)，T0為算法的總迭代次數(shù)。慣性權(quán)重w隨著粒子迭代非線性減小，實現(xiàn)自適應(yīng)的動態(tài)改變。

2）學(xué)習(xí)因子自適應(yīng)。

由式（22）可知，學(xué)習(xí)因子較大代表個體最優(yōu)值及全局最優(yōu)值對下一次迭代速度的影響程度越大。針對工作流調(diào)度中尋找目標(biāo)最優(yōu)值的問題，HAPSO 前期注重自我學(xué)習(xí)，c1較大，c2較小；HAPSO 后期注重向群內(nèi)學(xué)習(xí)，c1較小，c2較大。針對算法中學(xué)習(xí)因子一般取值2.0［26］，造成易陷入局部最優(yōu)的問題，本文結(jié)合伽馬隨機函數(shù)，動態(tài)改變學(xué)習(xí)因子，跳出局部收斂局面。本文對學(xué)習(xí)因子的改進，具體描述如式（25）（26）所示：

其中：cmax=2.5，cmin=0.5［27］，λ=0.1［28］，t為當(dāng)前迭代次數(shù)，T0為算法的總迭代次數(shù)。

2.4 獲取個體最優(yōu)值與全局最優(yōu)值

2.5 位置更新

由于PSO 不能很好地平衡局部搜索與全局搜索能力，HAPSO 引入花朵授粉算法的概率切換機制，對粒子迭代過程中全局搜索與局部搜索進行處理。設(shè)計隨機切換概率p值，p∈[0，1]。實驗［29］證明：p值過大，算法注重于全局授粉，收斂速度慢；p值過小，算法注重于局部授粉，易陷入局部最優(yōu)解；當(dāng)p=0.8 時，算法性能最好。因此，將p值設(shè)定在0.8附近波動，如式（29）所示，實現(xiàn)自適應(yīng)切換局部搜索與全局搜索。若隨機生成［0，1］值rand≤p，則粒子進行局部搜索，位置按式（23）更新；若rand>p，則粒子進行全局搜索，位置按式（30）更新。

式中：vpbest表示個體最優(yōu)速度，vgbest表示全局最優(yōu)速度，表示粒子i在第t+1 次迭代時的速度分別為粒子i在第t次及第t+1 次迭代時的位置，L(λ)是花朵授粉算法的Levy 飛行函數(shù)；rand、ε是［0，1］的隨機數(shù)。

2.6 越界處理

針對粒子容易出現(xiàn)越界情況，一般以邊界作為粒子位置［29］，這樣處理方式簡單，但由于絕大多數(shù)邊界值并不是全局最優(yōu)解，導(dǎo)致算法收斂效果不好。因此，HAPSO 采用beta分布函數(shù)對邊界問題進行處理，將越界粒子均勻分布到具有可行解的搜索范圍內(nèi)，對粒子越過上界及下界按式（31）處理，重新初始化越界粒子的位置，a=b=0.8［28］，效果較好。

2.7 算法流程

設(shè)計混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法HAPSO 的偽代碼如算法2 所示。

若任務(wù)數(shù)為n，HAPSO 中粒子種群規(guī)模為m1，迭代次數(shù)為t1。FA 中螢火蟲數(shù)量為m2，迭代次數(shù)為t2，則算法FA 時間復(fù)雜度為O(m22×t2)，由于初期使用FA 對HAPSO 各粒子位置初始化，本文設(shè)置t2遠(yuǎn)小于t1，m2較小，本文分別對慣性因子、學(xué)習(xí)因子，以及局部搜索與全局搜索的切換，邊界問題處理都是簡單的操作，可以在每次迭代中完成，復(fù)雜度O(1)，因此，總的算法時間復(fù)雜度為O(n×m1×t1)。

算法2 HAPSO 算法。

輸入 DAG 工作流，最大迭代次數(shù)T0；

輸出Makespan與Cost權(quán)衡最小值f。

3 算例仿真

3.1 仿真環(huán)境

將CloudSim［30］作為本文工作流調(diào)度實驗的仿真器，通過在Datacenter Broker 類中添加調(diào)度算法HAPSO 完成仿真。為了模擬真實的隨機復(fù)雜環(huán)境，本文隨機生成DAG 工作流，通過任務(wù)的數(shù)量不同來改變DAG 的規(guī)模。設(shè)置云仿真參數(shù)如表2 所示。

表2 云仿真器參數(shù)設(shè)置Tab.2 Parameter setting of cloud simulator

將HAPSO 與PSO［19］、WPSO［21］、ACO［17］進行對比，其中，WPSO 是基于PSO 改進的算法，ACO 是與PSO 完全不同的算法。通過這些對比算法來驗證本文提出的HAPSO 在工作流調(diào)度方面的性能。設(shè)置四種算法的各參數(shù)如表3 所示，其中，種群大小設(shè)置為30，迭代次數(shù)為500。將每次隨機生成的DAG 工作流保存為文件，四種算法從同一文件中讀取DAG 進行工作流調(diào)度實驗。

表3 算法參數(shù)設(shè)置Tab.3 Parameter setting of algorithms

3.2 算法收斂性分析

為驗證本文HAPSO 具有較好的收斂性，將PSO［19］、WPSO［21］和ACO［17］在解決求同一函數(shù)最小值問題方面進行比較，分別計算出四種算法對同一函數(shù)求最小值的收斂性結(jié)果，如表4 所示。

表4 算法收斂性對比Tab.4 Comparison of convergence among algorithms

圖3 展示了四種算法在迭代過程中的適應(yīng)度值的具體變化。

圖3 四種算法的迭代效果對比Fig.3 Comparison of iterative effects of four algorithms

算法的收斂性指標(biāo)為收斂速度與收斂精度。本實驗中，收斂速度通過收斂迭代次數(shù)衡量，收斂精度通過尋優(yōu)結(jié)果最小值衡量。由表4 可知，ACO 比PSO 收斂速度快，收斂精度高。WPSO 提高了收斂速度，但是收斂精度低于ACO。本文提出的HAPSO 極大地提升收斂速度的同時，也提高了收斂精度，HAPSO 的收斂性優(yōu)于ACO。

從圖3 可直觀看出，首先，算法開始迭代時，HAPSO 初始解優(yōu)于其他三種對比算法，說明引入FA 初始化HAPSO 具有很好的效果。HAPSO 在后期迭代時每個粒子根據(jù)FA 得到的最優(yōu)值進行位置更新，粒子的搜索范圍大幅度減小，有效避免隨機初始化粒子位置導(dǎo)致生成的初始值可能不落在可行域的問題，這極大地提高了種群搜索最優(yōu)值的速度，減少了迭代次數(shù)，從而提高了收斂速度。

然后，通過對慣性權(quán)重w，學(xué)習(xí)因子c1、c2的改進，使它們隨著迭代次數(shù)增加而自適應(yīng)變化，以實現(xiàn)種群從收斂較快的全局搜索到收斂較慢的局部搜索。同時引入花朵授粉算法的概率切換機制，平衡局部搜索與全局搜索的能力，防止種群因陷入局部搜索導(dǎo)致收斂結(jié)果較差。采用beta 分布函數(shù)對越界粒子重新設(shè)置初始位置，將越界粒子位置重新初始化到具有可行解的搜索范圍內(nèi)，大幅提高了粒子的搜索效率，從而提高HAPSO 的收斂精度。

3.3 DAG調(diào)度實驗分析

本文DAG 工作流調(diào)度實驗分為三個部分：工作流完成時間與執(zhí)行成本權(quán)衡最小化對比實驗、完成時間對比實驗和執(zhí)行成本對比實驗。在完成時間與執(zhí)行成本權(quán)衡最小化對比實驗中，實現(xiàn)本文1.5 節(jié)提出的優(yōu)化目標(biāo)函數(shù)f，驗證本文提出的HAPSO 性能。同時，為了驗證HAPSO 的普適性，分別對工作流的完成時間和執(zhí)行成本進行實驗。

3.3.1 完成時間與執(zhí)行成本權(quán)衡最小化對比實驗

本實驗在具有10 個虛擬機資源下，對具有不同數(shù)量的任務(wù)（30，60，100，200，300）構(gòu)成的具有截止期的DAG 工作流，以工作流的完成時間與執(zhí)行成本權(quán)衡最小化為目標(biāo)進行調(diào)度。針對本文1.4 節(jié)提出的工作流截止期約束條件，本實驗截止期因子取0.2 以表示DAG 工作流的緊急程度。實驗得到的目標(biāo)值f如圖4 所示。

圖4 四種算法的權(quán)衡最小值f對比Fig.4 Comparison of trade-off minimum values f of four algorithms

圖4 的實驗表明，相對于WPSO、PSO 和ACO 三種對比算法，HAPSO 實現(xiàn)的工作流調(diào)度方案得到的目標(biāo)值f最小。說明HAPSO 在權(quán)衡工作流的完成時間與執(zhí)行成本最小化方面具有較好的優(yōu)越性。

同時，為了進一步證明本文所提算法HAPSO 在完成工作流調(diào)度時，工作流的完成時間是否滿足截止期的要求，本文將本實驗得到的工作流完成時間與該工作流的截止期進行對比。將不同DAG 工作流的完成時間以相應(yīng)截止期為基線1 進行數(shù)據(jù)標(biāo)準(zhǔn)化，實驗結(jié)果如圖5 所示。

從圖5 可以看出，對比四種算法在調(diào)度不同的DAG 工作流時，HAPSO 對應(yīng)的工作流完成時間Makespan小于1，說明HAPSO 實現(xiàn)的工作流調(diào)度滿足工作流截止期約束條件。

圖5 四種算法在不同工作流上的完成時間和截止期對比Fig.5 Comparison of makespans and deadlines for different workflows of four algorithms

本文HAPSO 在實現(xiàn)工作流調(diào)度時，根據(jù)自適應(yīng)權(quán)重系數(shù)權(quán)衡工作流的完成時間和執(zhí)行成本兩個沖突目標(biāo)，有效協(xié)調(diào)折中了用戶與云提供商的需求。通過f可知，HAPSO 在工作流完成時間與執(zhí)行成本的多目標(biāo)優(yōu)化結(jié)果上，比PSO 降低了50.4%～81.1%，比WPSO 降低了40.9%～67.5%，比ACO 降低了45.3%～77.1%。PSO 性能低于ACO，但本文對PSO 進行改進，實驗表明，改進后的HAPSO 比ACO 性能提高77.1%（以調(diào)度由300 個任務(wù)構(gòu)成的DAG 云工作流為例），由此可說明本文所提的HAPSO 很大程度提高了PSO 性能。

在對粒子群改進過程中，采用FA 得到最初的調(diào)度方案，粒子根據(jù)最初調(diào)度方案按照慣性權(quán)重及學(xué)習(xí)因子的自適應(yīng)動態(tài)變化進行迭代，調(diào)整DAG 工作流調(diào)度方案。同時利用花朵授粉的切換概率機制平衡粒子在尋找最優(yōu)調(diào)度方案時的局部搜索與全局搜索能力，防止粒子在尋找虛擬機資源時易陷入局部最優(yōu)狀態(tài)，當(dāng)粒子位置處于邊界時，對其按式（31）進行處理，將粒子轉(zhuǎn)移到可行解當(dāng)中，避免任務(wù)因等待時間太長導(dǎo)致工作流超過截止期的問題。在保證工作流在截止期內(nèi)完成前提下，確定自適應(yīng)工作流完成時間與執(zhí)行成本的權(quán)重系數(shù)，找到最小值f，實現(xiàn)DAG 工作流調(diào)度，將任務(wù)分配到合適的虛擬資源節(jié)點。

3.3.2 完成時間對比實驗

實驗中以工作流完成時間為目標(biāo)，對由不同數(shù)量任務(wù)構(gòu)成的DAG 工作流進行調(diào)度，得到了不同DAG 工作流完成時間。首先，對10～90 個任務(wù)構(gòu)成的DAG 工作流在5 個虛擬機資源下調(diào)度得到的完成時間如圖6 所示。接著增加構(gòu)成DAG 工作流的任務(wù)個數(shù)至210～290，增加虛擬機的個數(shù)至15，得到工作流的完成時間如圖7 所示。

圖6 DAG完成時間對比（10～90任務(wù)數(shù)）Fig.6 Comparison of DAG makespan（10～90 tasks）

圖7 DAG完成時間對比（210～290任務(wù)數(shù)）Fig.7 Comparison of DAG makespan（210～290 tasks）

由圖6 和圖7 的實驗結(jié)果可看出，隨著DAG 工作流的任務(wù)數(shù)增加，DAG 工作流的完成時間也相應(yīng)增加。對相同DAG 工作流在相同的虛擬機資源下，HAPSO 的完成時間優(yōu)化結(jié)果均優(yōu)于其他三種算法，比PSO 減少了15.6%～69.4%，比WPSO 減少了2.5%～48.5%，比ACO 減少了0.8%～53.3%。在虛擬機資源不變的情況下，在任務(wù)數(shù)較少時，四種算法得到的時間值相差不大。這是由于在相同的DAG 工作流模型下，虛擬機數(shù)量與任務(wù)數(shù)相差不大，HAPSO 的優(yōu)越性沒有得到很好的體現(xiàn)。隨著任務(wù)數(shù)增多，大量的任務(wù)根據(jù)四種算法得到的調(diào)度方案分配到固定數(shù)量的虛擬機資源，結(jié)果表明，HAPSO 性能優(yōu)于其他三種算法。由此可知，HAPSO 也能很好地解決以工作流最小化完成時間Makespan為目標(biāo)的問題。

3.3.3 執(zhí)行成本對比實驗

實驗中以工作流執(zhí)行成本為目標(biāo)，對由不同數(shù)量任務(wù)構(gòu)成的DAG 工作流進行調(diào)度，得到了不同DAG 工作流的執(zhí)行成本。首先，對于10～90 個任務(wù)構(gòu)成的DAG 工作流在5 個虛擬機資源下調(diào)度得到的執(zhí)行成本如圖8 所示。

圖8 DAG執(zhí)行成本對比（10～90任務(wù)數(shù)）Fig.8 Comparison of DAG execution cost（10～90 tasks）

接著增加構(gòu)成DAG 工作流的任務(wù)數(shù)至210～290，增加虛擬機的個數(shù)至15，得到工作流執(zhí)行成本如圖9 所示。

由圖8 和圖9 的實驗結(jié)果可看出，隨著DAG 工作流的任務(wù)數(shù)增加，完成工作流所需的執(zhí)行成本相應(yīng)增加，四種算法對相同工作流在具有相同虛擬機資源下進行調(diào)度，HAPSO完成的執(zhí)行成本最小，比PSO 降低了14.9%～48.0%，比WPSO 降低了2.5%～23.8%，比ACO 降低了11.7%～33.3%。在任務(wù)數(shù)較少時，四種算法的調(diào)度策略完成工作流的執(zhí)行成本并沒有明顯差距，與工作流的完成時間對比實驗結(jié)果類似，由于任務(wù)數(shù)較少，調(diào)度策略的結(jié)果很難顯示出較大差距。隨著任務(wù)數(shù)增多，可選擇的調(diào)度策略增多，HAPSO 通過FA初始化來提高收斂速度，通過平衡全局搜索與局部搜索能力，避免粒子陷入局部收斂的狀態(tài)，提高HAPSO 的收斂精度，HAPSO 的尋優(yōu)能力得到增強。因此，所提算法也能很好地適用于解決最小化工作流執(zhí)行成本Cost的目標(biāo)優(yōu)化問題。

圖9 DAG執(zhí)行成本對比（210～290任務(wù)數(shù)）Fig.9 Comparison of DAG execution cost（210～290 tasks）

4 結(jié)語

本文針對云工作流完成時間與執(zhí)行成本的沖突問題，提出了一種混合自適應(yīng)粒子群工作流調(diào)度優(yōu)化算法HAPSO。該算法能夠保證DAG 工作流在截止期內(nèi)完成前提下，有效權(quán)衡云工作流完成時間與執(zhí)行成本。同時，在優(yōu)化云工作流完成時間或執(zhí)行成本的單目標(biāo)上，HAPSO 都優(yōu)于WPSO、PSO 和ACO。因此，HAPSO 在優(yōu)化云工作流調(diào)度目標(biāo)上具有較好的普適性。但是本文用戶需求僅考慮了云工作流的完成時間，云提供商的需求只考慮了云工作流的執(zhí)行成本。因此，本文考慮的因素較少，在未來的研究工作中，將考慮工作流應(yīng)用程序的可靠性、能耗和安全性等因素對DAG 云工作流調(diào)度的影響。