一種基于改進二進制粒子群的工作流云調度算法

熊聰聰，高 萌，趙 青，徐丹瀅

(天津科技大學人工智能學院，天津 300457)

隨著數據規模日漸龐大、計算日趨復雜，科學工作流已經不能滿足數據處理的需求，批處理科學工作流應運而生.批處理科學工作流較科學工作流運算更為復雜，數據處理能力更強，它是包含大量批處理任務組的科學工作流.批處理科學工作流廣泛應用于高能物理學、氣象學、生物信息學等不同領域，是建模和管理數據密集型數據的有效手段.

云計算為批處理科學工作流的處理提供了技術手段支持.云計算在 2006年由搜索引擎服務提供商Google率先提出[1].目前，云計算的用戶數量已經超過 40億.云計算是依靠虛擬技術進行使用，按需訪問是云計算的特點.數據密集型應用是云計算環境下最普遍的應用之一，數據通信往往是數據密集型應用的性能瓶頸.面對龐大的數據規模，怎樣對其進行合理的任務分配，使得云計算能夠高效完成任務和給出合理調度方案顯得尤為重要.

作為云計算的核心技術，任務調度是云計算處理任務過程中的重要環節之一，因此優化任務調度機制是提高云計算綜合性能的重要方法[2].在云環境中，任務調度是一個非確定性多項式問題(NP難題)的優化問題[3].任務調度可以合理地分配計算資源任務，并且對計算的任務進行高效率的調度，主要目標是將不同的用戶任務分配合適的資源，例如主機或虛擬機(VM)，并找出可以執行任務的適當順序在分配資源中執行.任務調度促進了云數據中心的可持續發展，高效率的任務調度策略是非常必要的.

近年來，隨著應用領域的不斷擴大，批處理科學工作流的調度問題引起了國內外學術界的重視，Cai等[4]提出的方法只考慮了批量任務組的整體同步調度，沒有考慮批處理數據組中任務的單獨調度問題.此后，Cai等[5]又對該方法進行改進，提出了一種基于多規則調度的算法，通過提高剩余時間間隙的利用率以最小化租賃成本，可以用于批處理數據組中單個任務的調度，考慮到了任務轉移、浪費預測，但沒有考慮任務間數據的傳輸成本增加的問題.本文希望考慮批處理工作量中子任務的調度問題以及數據密集型任務中最為關鍵的數據傳輸成本的變化，將采用元啟發式算法加以解決.這是因為元啟發式算法通常可以在有限的時間里高效、智能地探索搜索空間，以找到接近最佳的解決方案[6-7].而粒子群算法是近年來受到廣泛關注的一種元啟發式算法，具有效率高、收斂好的特點.

粒子群算法是美國的兩位學者 Eberhart和Kennedy源于對鳥群捕食行為的啟發提出的一種元啟發式算法，主要用來解決尋找最優解問題.Rodriguez等[8]提出基于粒子群算法的動態時間片資源分配方法，雖然為了避免調度失敗，采用了最大化任務執行時間假設的方法，但缺乏對任務間的數據依賴的考慮.馬亮等[9]提出一種改進的粒子群調度算法，以任務的完成時間為出發點進行考慮，對算法進行變異和修改，改進后的算法具有很好的性能，但著重考慮了任務的完成時間，未對其他影響因素進行考量.Saeedi等[10]提出一種改進的多目標粒子群優化算法求解工作流調度問題，該算法考慮了 4個影響因素，但未對粒子群算法的收斂性進行優化.

粒子群算法一般用于連續空間上的求解問題，而二進制粒子群算法更適合于求解 0/1離散空間上的求解問題，這與任務的調度模型非常相似.但已有研究成果顯示，二進制粒子群算法存在收斂性不好的問題[11-12]，所以本文對粒子的更新公式進行了修改.隨著速度的逐漸降低(趨近于 0)，發生跳轉的概率增大，改進的算法有效避免了這個問題.實驗結果表明，該算法提高了最優解的探測能力，所得最優解具有更好的實際調度時間和成本，提高了資源的利用率.在相同的條件設置下，該算法優于未經改進的二進制粒子群算法，當迭代次數增多時，其綜合調度性能優點明顯.

1 批處理科學工作流任務調度模型描述

工作流應用程序被建模為 DAG 圖，即 E＝{T，U}，其中 T = { t1,t2, … ,tn}表示所有任務的集，任務間的偏序關系集合表示為 U = { (vi, vj)| i ＜j} ，(vi, vj)表示先執行任務vi，然后再執行任務vj.圖1為批處理科學工作流DAG圖.

圖1 批處理科學工作流DAG圖Fig.1 DAG diagram of batch scientific workflow

在云環境中進行任務調度，假設任務集合為T = { t1, t2, … ,tn}，虛擬機的集合為 V M = {v m1, v m2,… ,vmm}，有n個相互獨立的子任務將它們分配給m個虛擬機執行，其中m＜n.第 j個子任務用 tj=(j=1,2,…,n}表示，第i個虛擬機用 v mi(i = 1 ,2,… ,m)表示.每個任務只能由一個虛擬機運行.任務集合與虛擬機集合的調度關系用矩陣X表示為

參考給出的矩陣 X，每一列代表任務分配，每一行代表分配給虛擬機的任務.在每一列中，數值 1表示虛擬機被分配給一個任務時，每個任務只能由一個虛擬機來執行，數值 0表示沒有被分配任務.例如，表1為 3個虛擬機上有 5個任務的調度方案.與位置矩陣相似，每個粒子速度也以m×n矩陣的形式表示，其元素的范圍為[0，1].每行都只有一個 1，表示每個任務只能分配給一個虛擬機進行計算，但一個虛擬機可能不只計算一個任務.

表1 調度方案圖示例Tab.1 Sample scheduling scheme diagram

2 改進二進制粒子群的批處理科學工作流任務調度算法

2.1 生成初始種群

初始種群的生成關系到算法能否快速找到最優解，確定合理的初始種群對二進制粒子群算法至關重要.本文的初始種群采用計算機隨機生成，它的優點是具有充分的隨機性，分布比較均勻，同時也保證了粒子的豐富性.

2.2 適應度函數

處理優化問題的關鍵在于構造出合理的適應度函數，它是判斷一個解好壞的標準.適應度函數的選取對二進制粒子群算法的效率尤為重要.本文以時間和成本為優化目標.

當任務節點為y，虛擬機使用類型為i類時，j個虛擬機執行任務需要的時間為

其中：etcyi表示當虛擬機類型為i時，在第y個任務節點執行任務時所需的估測時間，tb為虛擬機啟動的時間與執行軟件安裝的時間之和.

任務調度總時間是在關鍵路徑進行任務調度時所需要的時間總和.

當任務節點為y，虛擬機使用類型為i類時，j個虛擬機執行任務需要的總費用為

其中：a為虛擬機的租用周期，ci為虛擬機使用類型為i類時單個租用周期的單價.

總費用Ctotal為每個任務節點的費用的累加之和.

由上所述，適應度函數fitness定義為

其中：w1+ w2=1，w1與w2為實數；Tdeadline為用戶所提供的調度該批任務所要求的截止時間與任務批開始進行調度的時間差值.Max代表取括號內的兩數中較大的數.

2.3 二進制粒子群算法及其改進

在粒子群算法中，每個優化問題的最優解可以通過搜索粒子的位置得到，由優化的函數決定它們的適應度函數值，粒子們依據當前的最優粒子狀態進行更新.標準粒子群算法根據式(6)進行解的迭代更新，在每一次迭代過程中，每個粒子根據兩個值更新它們的位置.其中一個值是粒子自身所找到的最優解，這個解稱為個體極值；另一個極值是整個群體找到的最優解，這個解稱為全局極值.

其中：w為慣性權重，rand()為均勻分布在(0，1)之間的隨機數，c1和 c2為學習因子.粒子的速度vi被最大速度vmax所限制，即若vi＞vmax，則令vi＝vmax，而若vi＜-vmax，也令vi＝vmax.為了處理離散型優化問題，需對公式進行修改，提出了二進制粒子群算法.它的速度公式保持不變，位置的迭代公式修正為

為了防止sigm函數飽和，通常給vi+1的取值規定一個區間范圍為{－4.0，4.0]，sigm函數與速度vi的關系如圖2所示.需指出的是：sigm函數值不表示某位變化的概率，而是表示某位取1的概率.

圖2 sigm函數與vi關系Fig.2 Relationship between sigm function and vi

根據式(7)，粒子改變是一種根據概率進行的改變.位為 1的概率為sigm(vid)，而位為 0的概率為1-sigm(vid).如果位已經是 0，則表示位發生變化的概率為sigm(vid)；如果位已經是 1，則表示位發生變化的概率為1-sigm(vid).在速度vid值已知的前提下，位發生改變的絕對概率為

結合式(8)和式(9)，得

式(7)表示位速度與位改變的絕對概率之間關系，其關系如圖3所示.由圖3可以看出，當位速度是 0時，位的絕對改變概率最大.經分析得出以下結論：當二進制粒子群算法的粒子速度是 0時，位最有可能發生改變，不利于全局最優解的搜索，此時的算法具有更強的隨機性，缺乏方向性.二進制粒子群算法隨著迭代次數的增多，其隨機性更強了，不能收斂到全局最優解.本文針對二進制粒子群算法的這種情況進行了改進.

圖3 位速度與位改變的絕對概率之間關系Fig.3 Relationship between bit velocity and bit change absolute probability

在粒子群算法尋優的過程中用vi表示速度，能夠對粒子的位置和方向有一定影響，使算法在指定的搜索范圍內進行搜索.假設算法的進化迭代視為一個自適應過程，則不斷的會有新粒子替代粒子xi的位置，并且根據vi進行自我調節.在進行每一次迭代時，群體經驗的最優解是粒子移動的方向，粒子群算法是有目的的尋找最優解.而二進制粒子群算法中，vi表示一種可能的概率性，粒子的每維分量的位置取值可能以 s igm(vi+1)的概率取 1，或者以 1 -sigm(vi+1)的概率取0，其位發生變化概率為

分析得出，當速度越趨近于 0時，其位發生改變的概率越高.粒子在尋找最優解的過程中，粒子越來越靠近最優粒子，即速度在不斷趨近于 0時，此時位發生改變的概率應該越小，而二進制粒子群算法反而越來越大，如此必然影響算法的尋優能力.

本文提出的算法基于二進制粒子群算法的尋找最優解模式進行改進，粒子速度作為粒子位置的修正項，應當充分考慮粒子之間的此種導向作用，所以在對二進制粒子群算法進行改進中，速度迭代公式維持不變，速度歸一化公式sigm函數以及位置迭代公式改進為

改進后的新sigm函數與vi關系如圖4所示，當速度的絕對值越來越大時，位改變的概率也越來越大；反之，當速度趨近于 0時，位改變的概率越來越小.由此得出，改進后的函數遵循二進制粒子群算法的尋優模式，更有利于全局最優解的搜索.

圖4 新sigm函數與vi的關系Fig.4 New relationship between sigm function and vi

3 仿真實驗

為了驗證本文所提模型以及算法的有效性，選擇開源的云仿真CloudSim平臺對優化算法進行仿真驗證.采用 Montage和 CyberShake作為測試用例.軟件安裝時間為 10s，帶寬 B為 10MB/s，虛擬機的加載時間為 30s，采用 Amazon EC2提供的虛擬機價格，它是基于按小時計費原則.本文提出的改進二進制粒子群算法與基本二進制粒子群算法分別進行任務完成時間和花費兩方面的比較與分析.

Montage 100測試用例隨迭代次數增加完成時間的變化趨勢測試結果如圖5所示.測試用例為 100時，與未經改進的算法相比，改進的二進制粒子群算法的趨勢平緩，時間變化比較穩定，且所用時間相對少.當迭代次數為90次時，開始收斂.

圖5 Montage測試用例任務數為100時算法的完成時間Fig.5 Algorithm completion time for the Montage test case with 100 tasks

Montage 100測試用例隨迭代次數增加所需費用的變化趨勢測試結果如圖6所示.當任務數為 100時，與未經改進的算法相比，改進的二進制粒子群算法的趨勢較平緩，且費用相對少.

圖6 Montage測試用例任務數為100時算法所需費用Fig.6 Algorithm completion cost for the Montage test case with 100 tasks

CyberShake 100測試用例隨迭代次數增加完成時間的變化趨勢和隨迭代次數增加所需費用的變化趨勢測試結果如圖7和圖8所示.與未經改進的算法相比，改進的二進制粒子群算法所需的完成時間和費用都優于未改進的算法.

圖7 CyberShake測試用例任務數為 100時算法的完成時間Fig.7 Algorithm completion time for the CyberShake test case with 100 tasks

圖8 CyberShake測試用例任務數為100時算法所需費用Fig.8 Algorithm completion cost for the CyberShake test case with 100 tasks

綜合分析，本算法對不同的工作流具有普適性，在不同的工作流上都體現了優化作用.本算法對租賃成本的優化效果更為明顯，而對于完成時間的優化略微不明顯.分析原因是由于本算法對租賃成本的優化是越低越好，而對完成時間的優化是盡量小于截止時間.

Montage 100測試用例在迭代次數相同且任務數不同時，時間和費用的變化趨勢如圖9和圖10所示.當迭代次數相同時，改進的二進制粒子群算法隨著任務數量的增加，完成時間和費用都優于未經改進的二進制粒子群算法.

圖9 不同任務數對應的完成時間Fig.9 Completion time for different tasks

圖10 不同任務數對應的所需費用Fig.10 Costs of different tasks

4 結 語

針對二進制粒子群算法不能收斂于粒子的全局最優位置的問題，本文對粒子的更新公式進行了修改，提出了一種基于改進的二進制粒子群的任務調度算法.實驗結果表明，經過改進的二進制粒子群算法能得到很好的收斂，具有普適性，所得最優解具有更低的調度時間和費用，提高了資源利用率.在相同的條件設置下，該算法優于傳統的二進制粒子群算法.

致謝：本研究獲得天津教委項目(2017KJ035，2018KJ105)資助.