基于競爭粒子群算法的云計算資源調度策略

王鎮道，張一鳴?，石雪倩

（1.湖南大學 物理與微電子科學學院，湖南 長沙 410082；2.湘投云儲科技有限公司，湖南 長沙 410205）

云計算（Cloud Computing）是繼分布式計算（Distributed Computing）、并行處理（Parallel Computing）、網格計算（Grid Computing）等之后計算模式的最新發展[1].云計算通過將各種互聯的計算、存儲、數據、應用等資源進行有效整合來實現多層次的虛擬化與抽象，用戶只需要連接上網絡即可方便使用云計算強大的計算和存儲能力.虛擬化技術是云計算中的關鍵技術之一[2].通過虛擬化技術，單個服務器可以支持多個虛擬機運行多個操作系統和應用，從而大大提高服務器的利用率，通過虛擬化為應用提供了靈活多變、可擴展的平臺服務，用戶租賃滿足其需求的資源，并動態運行廣泛的應用程序，由此可以看出云計算的核心問題是資源管理[3].考慮到云計算環境的動態性、海量數據、異構性、任務規模大等問題，云計算分布式系統上的資源調度是NP-hard 問題.對于求解計算時間長、復雜度高的問題，求解的算法主要有群智能優化算法.例如模擬退火算法、遺傳算法、粒子群優化算法、蛙跳算法等[4-7]運用在資源調度問題中取得了較好的效果，由于群智能算法在解決調度問題上的優異表現，因此被日益重視，但這些算法普遍存在對參數依賴度高、尋優效果不理想或者穩定性差等問題，且當優化問題存在大量局部最優解或為高維時，容易出現過早收斂.這就導致隨著云計算調度任務規模的越來越大，這些算法在大規模任務調度問題上整體性能下降，極易陷入“維數災難”.

競爭粒子群算法（Competitive Particle Swarm Optimization，CSO）[8]通過引入成對的競爭機制實現粒子更新，不僅實現簡單，而其在解決高維問題方面性能優越，已經被應用于解決大規模優化問題.文獻[9]提出利用競爭粒子群算法進行電網調度，表現出了優于同類算法的性能；文獻[10]提出將二進制編碼與競爭粒子群算法結合來解決電動車充電樁的需求管理問題，改進后的算法展現了在解決大規模、負載電力系統調度問題方面的優越性能；文獻[11]通過對競爭粒子群優化算法的學習過程進行簡化，然后將其應用于解決燃料電池模型的參數辨識問題，結果證明該算法在精度、魯棒性、收斂性方面有很強競爭力.

本文在云計算資源調度中采用改進的競爭粒子群算法（Improved Competitive Particle Swarm Optimization，ICSO）對資源進行有效分配.首先通過對任務完成時間、系統負載均衡度、任務完成功耗建立約束函數以兼顧三個目標的優化.其次，在初始化操作中引入混沌映射，以改進收斂速度和尋優效率；引入自適應高斯變異操作對勝利粒子位置進行更新以提高算法搜索精度.仿真結果表明，本文算法在任務完成時間、任務執行功耗以及系統的負載均衡之間取得較好的平衡，提高了在大規模任務下的云計算資源的利用率.

1 云計算任務調度

當前云計算系統主要采用Map/Reduce 架構模式，通過對用戶任務進行分配來完成任務調度.具體來說，任務調度是指在云計算環境中根據任務和資源的實際情況，將任務分配或遷移到相應資源上執行的過程[12]，圖1 為云計算平臺中任務調度的一般過程.任務調度涉及了優先權、執行時間、完成時間、資源利用率、成本、能耗、網絡吞吐率以及公平性等優化參數和測評指標[13].任務調度策略不僅直接對任務執行時間和成本產生作用，還會影響到整個云計算平臺的性能.

圖1 資源調度模型Fig.1 Resource scheduling model

1.1 云計算任務調度數學模型

在云計算資源環境中，設資源節點共有n 個，用集合v={v1，v2，v3，v4，…，vn}表示，其中vj（1 ≤j ≤n）表示第j 個虛擬資源節點，將任務劃分成m 個子任務，子任務表示為T={t1，t2，t3，t4，…，tm}，其中第i 個任務表示為ti（1 ≤i ≤m）.每個子任務分配到一個虛擬資源節點運行，子任務分配到虛擬資源節點的情況可以用矩陣P 表示為：

式中：元素pji代表一個子任務ti和虛擬資源節點vj的對應關系.當子任務ti分配到vj時，pji=1，反之為0，即pji∈{0，1}.每個任務只能分配到某一個虛擬資源節點上執行，所以有：

考慮到云計算平臺資源的異構性，即不同的虛擬節點所具有的能力側重點不同，有些節點資源的運算能力較強而帶寬較小，而有些節點資源的內存較大而計算能力較弱等.基于以上特性，可以用（VC，VM，VB）表示虛擬機節點的資源能力，其中VC表示CPU 的運算能力（每秒處理百萬級指令的能力），VM表示內存的大小，VB表示帶寬大小，而子任務對處理節點的需求采用P（Ci，Mi，Bi）描述，表示執行任務Pi需要的CPU 處理能力、內存及網絡帶寬.

1.2 服務質量模型

服務質量是用來衡量云計算資源調度中任務的完成程度的指標.由于云計算的任務調度是一個多目標優化問題，綜合評價云計算任務調度的優良需要從多方面進行考慮，根據前面對任務調度性能指標的描述.首先給出3 個優化目標：任務完成總用時Tmax、任務完成功耗E、負載均衡度Bdegree.

對于虛擬機節點在處理任務時，它的單個任務耗時可以表示為：

式中：Li表示完成第i 個任務的長度；VCj為第j 個虛擬節點的CPU 處理能力.第j 個虛擬節點處理任務總耗時為：

則任務總用時Tmax為各虛擬機節點完成時間中的最大值，即

按照目前的研究表明，單位時間能耗和CPU 利用率是線性關系的[13]，結合能耗的計算公式E=P×T，任務從t0時刻到t1時刻所產生能耗可以表示為：

系統完成任務的總功耗為各節點功耗總和：

式中：VOCj為虛擬機節點j 的CPU 利用率；tji為虛擬機節點j 執行任務耗時；k 為乘法算子.CPU 利用率計算方法為：

式中：ci、vci分別表示任務對CPU 處理能力的需求以及虛擬機節點所能提供的CPU 運算能力.同理虛擬機資源j 中內存的利用率和帶寬利用率可以分別表示為：

在云計算執行任務過程中，虛擬機的負載主要是由其執行的任務量的大小和自身的計算能力所決定，虛擬機Vj負載情況表示為Vj={Mj，Cj，Bj}，其中Mj、Cj、Bj分別表示虛擬機Vj上的內存利用率、CPU利用率和帶寬利用率.則虛擬機資源j 的利用率為：

式中：k1、k2、k3分別為CPU、內存、帶寬的權值.整個系統的虛擬機資源平均利用率為：

以各個虛擬機節點利用率之間的標準差系數作為表示集合v={v1，v2，v3，v4，…，vn}中虛擬機負載情況，則系統的負載均衡度Bdegree可以表示為：

2 任務調度策略

2.1 競爭粒子群算法

粒子群優化算法（Particle Swarm Optimization，PSO）作為最經典的群智能算法之一，由于其簡單的實現和快速的收斂性，被廣泛應用于求解單目標優化問題（Single-ObjectiveOptimization Problem，SOP）.然而，當優化問題存在大量的局部最優解或為高維時，PSO 算法性能較差.競爭群優化算法是粒子群優化算法的一個變體，Cheng 和Jin[8]提出的CSO 算法模擬了生物學中的優勝劣汰的個體競爭機制.采用競爭機制的優化算法比原粒子群優化算法能夠更好地平衡收斂性和多樣性.而且在大規模優化問題上，該算法表現出良好的性能和可拓展性.該算法假設種群大小為M，在解空間內隨機地初始化種群.在每一次迭代過程中首先將種群隨機均分為2 組，兩組粒子兩兩進行競爭比較，根據適應值的大小分別為勝利者（Winner）與失敗者（Loser），勝利者將直接進入下一代，失敗者根據式（15）和式（16）向勝利者學習并更新自身位置和速度.

式中：xw（t）、xL（t）分別表示勝利者和失敗者的位置向量；vL（t+1）表示失敗者的速度向量；t 為迭代次數；r1（t）、r2（t）、r3（t）∈[0，1]D是3 個服從均勻分布的隨機向量，與解向量有相同的維數；φ 是一個參數，用于控制x（t）對失敗者位置更新的影響；x（t）有兩種含義，一種表示所有粒子的平均位置，具有全局性；另外一種表示領域內粒子的局部平均位置，具有局部性.在本文中使用全局平均位置.

2.2 改進的競爭粒子群算法

標準的CSO 算法具有操作簡單，所需參數較少，易于實現等優點，但由于CSO 算法在每次迭代過程中只更新失敗粒子的位置和速度信息，這使得種群多樣性不足，最終導致算法陷入局部最優解及“早熟”現象.因此，為了增強種群的多樣性，平衡種群的探索與開發，本文借鑒遺傳算法中的變異思想，在CSO 算法中引入自適應高斯變異，用來對勝利粒子的位置進行更新，同時引入混沌初始化策略對初始種群進行初始化.

2.2.1 混沌初始化策略

在標準CSO 算法中，種群的初始化是隨機產生的，初始位置的散布程度及其在搜索空間中的位置是否均勻，將直接影響整個搜索過程的收斂速度和算法的尋優效率[14-15].混沌是一種無規則的運動狀態，具有非常強烈的非線性特點，它有規律性、隨機性和遍歷性等特點，其基本思想是根據一定規則把變量從混沌空間映射到求解空間.本文利用混沌優化策略對粒子群進行初始化，Logistic 映射具有較均勻的遍歷性分布區間，能產生分布均勻的混沌序列，有效地保證了種群在解空間中的均勻分布，從而提高算法的搜索效率.本文選取Logistic 映射的方法產生初始混沌序列.該映射的表達式為：

式中：xn為混沌變量；參數μ∈（0，4]；n 為混沌變量序號，n=1，2，3，…，m.映射圖像如圖2 所示，當3.569 9<μ≤4 時，系統處于混沌狀態，在本文中μ 取值為4.

圖2 Logistic 映射Fig.2 Logistic map

本文利用混沌迭代生成初始化粒子群位置，具體步驟如下：

1）對于D 維空間中的n 個初始粒子位置，首先隨機產生一個D 維向量作為第一個混沌向量，即r1∈[0，1]D；

2）將r1的每一維利用式（17）進行n-1 次迭代，生成n-1 個混沌向量，r2、r3、…、rn；

3）將產生的n 個混沌向量按照式（18）映射到解的搜索空間.

式中：xmin、xmax分別為搜索空間的上下限；xi即為第i個混沌初始化粒子位置信息.

2.2.2 自適應高斯變異

由于變異算子在提升算法收斂性能和種群多樣性方面有著顯著表現，文獻[16]將高斯變異引入到PSO 算法中以改善粒子在求解過程中的多樣性，提出一種基于高斯變異的多目標粒子群優化算法.本文將高斯變異引入CSO 算法中對勝利粒子的位置進行更新，變異操作如下：

式中：c 為變異步長；γ 為服從高斯分布Gauss（0，1）的隨機變量；Pm為變異概率.同時考慮到迭代初期主要發揮競爭群算法自身的特點，采用較小的變異率，隨著迭代進行，種群多樣性逐漸降低，相應地增加了種群的變異概率，因此將變異概率設定為隨迭代次數線性遞增，使變異概率自適應變化.Pm的計算公式為：

式中：Pm，min為最小變異率；Pm，max為最大變異率；k 為當前迭代次數；N 為最大迭代次數.從更新公式可見，隨著迭代次數的增加，變異概率線性遞增.因此，引入自適應高斯變異后勝利者的更新如式（21）所示.

3 基于ICSO 的云資源調度算法設計

3.1 粒子編碼與適應度函數設計

設任務數m，虛擬資源節點數n，本研究中每一個粒子代表一種任務分配方案，假設粒子所表示的解向量P={p1，p2，…，pn}，N 表示向量P 的維數，Ni表示向量P 第j 維的值，則Nj=i 表示任務j 分配到虛擬機i.

由于本文涉及到多個目標的優化過程，適應度函數與任務完成總用時Tmax、任務完成功耗E、負載均衡度Bdegree3 個目標相關聯，所以首先需要將多目標問題轉化為單目標問題.首先將各個優化目標參數歸一化，如式（22）所示：

式中：F 代表歸一化后的值；f（x）表示當前系統中某一個優化目標參數大?。籪（x）max、f（x）min分別表示該目標參數的最大值和最小值.通過對單個優化目標適應度值加權，將多目標優化問題轉化為單目標優化問題.適應度函數可以表示為：

式中：fi表示第i 個粒子的適應度值；w1、w2、w3分別表示任務完成總用時Tmax、任務完成功耗E、負載均衡度Bdegree3 個目標對應的權值，且w1+w2+w3=1.

3.2 改進競爭粒子群算法的任務調度

將本文提出的ICSO 算法應用于云計算資源調度問題中，調度算法的具體實現步驟為：

步驟1 將云計算任務調度方案與ICSO 算法中的粒子位置進行一一對應，粒子的最佳位置即為最佳任務調度方案；

步驟2 初始化參數.給出任務集數據、虛擬機參數，算法的最大迭代次數Maxcycle、種群規模m、變異步長；

步驟3 按照公式（17）（18）對粒子群初始位置進行混沌初始化；

步驟4 根據式（23）計算每個粒子的適應度值；

步驟5 將種群隨機進行兩兩競爭比較，根據適應度值的大小分為勝利者Winner 和失敗者Loser；

步驟6 根據式（15）（16），更新失敗粒子速度以及位置，根據式（19）更新勝利粒子的位置和速度.計算更新粒子的適應度值并更新全局最優值和最優解；

步驟7 達到最大迭代次數的時候，算法結束，轉到步驟8，否則繼續步驟5；

步驟8 得到最優粒子位置，即得到最優的任務調度方案.

4 試驗測試和結果分析

本文采用CloudSim 模擬云計算平臺的仿真環境對算法進行驗證[17-18]，具體的試驗環境為：Window10 操作系統，Intel?CoreTM i5-8250U，1.60 GHz CPU，16.00 GB 內存，CloudSim 4.0.將本文提出的改進的競爭群算法ICSO 與文獻[13]中的競爭群算法以及基本PSO 算法和GA 算法進行了比較.各算法試驗參數設置如表1 所示.

表1 算法參數表Tab.1 Algorithm parameter table

試驗中考慮了資源的處理速度和待處理任務的長度，設定兩個任務集T1、T2，分別設置任務數量為10～100 和1 000～5 000，代表小規模和大規模兩種任務規模情況.計算節點數為10，隨機設置虛擬節點的性能，設置虛擬節點能力為[1 000，2 000]mi/s，內存為 [512，2 048]MB，帶寬為[5 000，10 000]bit/s，在[500，9 000]間隨機設置任務長度，最大迭代次數為200 次，為排除偶然性，每種方法進行10 次獨立重復試驗，并取平均值作為最終的試驗結果.

為了驗證本文所提調度模型和算法的有效性，通過改變迭代次數、任務數來比較改進算法和對比算法在各個維度的差別.首先，分別在大規模和小規模兩個任務集中保證迭代次數相同的條件下，在任務完成時間、功耗、負載均衡度3 方面做出對比.試驗結果如圖3～圖8 所示.

圖3 小規模下任務完成時間對比圖Fig.3 Task completion time comparison chart in small－scale

圖4 大規模下任務完成時間對比圖Fig.4 Task completion time comparison chart in large－scale

圖5 小規模下負載均衡度對比圖Fig.5 Comparison chart of load balance degree in small－scale

圖6 大規模下負載均衡度對比圖Fig.6 Comparison chart of load balance degree in large－scale

圖7 小規模下任務完成功耗對比圖Fig.7 Task completion power consumption comparison chart in small－scale

圖8 大規模下任務完成功耗對比圖Fig.8 Task completion power consumption comparison chart in large-scale

圖9 迭代次數與適應度值的關系Fig.9 Relationship between iterations and fitness

1）圖3 和圖4 分別為ICSO 算法、CSO 算法、GA算法和PSO 算法在小規模和大規模任務數量下的任務完成時間結果對比圖.可以看出，當任務數量較少時，ICSO 算法與試驗對比算法任務完成時間相差不大.隨著任務數量的增多，CSO 和ICSO 算法在大規模任務下具有明顯的優勢，ICSO 和CSO 算法的任務完成時間明顯優于PSO 和GA 算法，ICSO 算法的任務完成時間又優于基本的CSO 算法，說明本文改進的ICSO 算法在減少任務完成時間方面有所提升.

2）圖5 和圖6 分別為2 種任務集下4 種算法的負載均衡度對比圖.隨著任務數量的增多，4 種算法的任務調度策略的負載均衡度都在上升，但ICSO 和CSO 算法任務調度策略下負載均衡度上升速率明顯小于PSO 調度策略和GA 調度策略；在整個過程中，ICSO 調度算法下的負載均衡度始終低于另外2 種算法.這主要是因為ICSO 算法中引入的變異算子提升了種群的多樣性，很好地避免了局部最優，使得最后的結果更好.

3）圖7 和圖8 為2 種任務集下的4 種調度策略的任務完成功耗對比圖.從圖中可以看出，在任務數量較少時，ICSO、CSO 算法和PSO 算法以及GA 算法完成的云計算資源調度在任務完成功耗上差別不大，但隨著任務數量的增多，CSO 和ICSO 算法在大規模任務下的優越性得到了體現，PSO 算法下的調度策略功耗明顯高于CSO 和ICSO 算法下的調度策略，而ICSO 算法的功耗又略低于CSO 算法的功耗，這說明改進的算法在降低任務完成功耗方面也有所提升.

從迭代次數的角度進行對比，將任務數設置為3 000，比較迭代次數對最優適應度值的影響.結果如圖9 所示.

由圖9 可知，在初始階段CSO 算法和改進的ICSO 算法收斂速度要高于PSO 算法和GA 算法，在迭代40 次前，各算法所得適應度值差別并不明顯，這時CSO 算法略優于其他3 種對比算法；隨著迭代次數增至60 以上，CSO 算法和ICSO 算法所求結果明顯好于PSO 算法和GA 算法，且兩種算法在80 次開始逐漸趨于穩定，而PSO 算法在120 次以后才開始趨于穩定.在收斂速度方面，CSO 算法略微好于ICSO 算法，這主要是由于引入的變異操作在一定程度上降低了算法的收斂速度；從求解精度上可以看到，ICSO 算法能夠跳出局部最優解，實現更好的求解精度，算法結果表現更加優秀.

5 結論

針對大規模云計算資源調度中算法求解精度不高，易陷入局部最優等問題，本文提出改進的競爭粒子群優化算法來求解云計算資源調度問題.相較于標準的競爭粒子群算法，該算法利用混沌理論產生初始化種群，使得初始化粒子在解空間中均勻分布；在粒子搜索過程中引入自適應變異概率的高斯變異來進行勝利粒子的更新，提升了種群多樣性和算法的全局搜索能力.在CloudSim 仿真環境下，分別從不同任務規模下的求解精度與相同任務規模下的收斂速度兩方面進行試驗.仿真結果表明，本文提出的多目標綜合評價模型兼顧了云計算任務的完成時間、功耗以及負載均衡度，能搜索到最佳調度方案，可很好地應用于大規模云計算環境下的資源調度問題.