面向云環境中任務負載的粒子群優化調度策略

胡志剛 常健 周舟

摘? ?要：隨著云環境中任務規模的不斷擴大，云計算中心高能耗問題變得日益突出.如何解決云環境中任務分配問題從而有效降低能耗，本文提出了一種改進的粒子群優化算法（Modified Particle Swarm Optimization， M-PSO）.首先構建出一個云計算能耗模型，同時考慮處理器的執行能耗和任務傳輸能耗.基于該模型，對任務分配問題進行定義描述，并采用粒子群優化算法對問題進行求解.此外，構建動態調整的慣性權重系數函數以克服標準PSO算法的局部最優和收斂速度慢的問題，有效提高系統性能.最后通過仿真實驗對該算法模型的性能進行了評估，結果表明M-PSO算法與其他算法相比能有效地降低系統總能耗.

關鍵詞：云計算;任務調度;慣性權重;粒子群優化

中圖分類號：TP338.8? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻標志碼：A

PSO Scheduling Strategy for Task Load in Cloud Computing

HU Zhigang1， CHANG Jian1， ZHOU Zhou2？覮

（1. School of Computer Science and Engineering，Central South University，Changsha 410075，China;

2. Department of Mathematics and Computer Science， Changsha University，Changsha 410022，China）

Abstract： As the scale of tasks in the cloud environment continues to expand， the problem of high energy consumption in cloud computing centers has become increasingly prominent. In order to solve the problem of task assignment in a cloud environment and to effectively reduce energy consumption， a Modified Particle Swarm Optimization algorithm （M-PSO） was proposed. First， a cloud computing energy consumption model， which takes into account the processor's execution energy consumption and task transmission energy consumption， was introduced. Based on the model， the task assignment problem was defined and described， and the particle swarm optimization algorithm was used to solve this problem. In addition， a dynamically adjusted inertia weight coefficient function was constructed to overcome the local optimization and slow convergence problem of the standard PSO algorithm， and the strategy can effectively improve the system performance. Finally， the performance of the introduced algorithm model was evaluated by simulation experiments. The results show that the M-PSO algorithm can effectively reduce the total energy consumption of the system compared with other algorithms.

Key words：cloud computing;task scheduling;inertia weight;Particle Swarm Optimization（PSO）

云計算提供了方便和按需的網絡訪問共享和可擴展的虛擬資源池，如服務器、存儲和應用服務[1].但是在配電和散熱方面，云計算數據中心會產生巨大的能源成本[2].對于像Google這樣的大公司來說，能源成本降低三分之一可以節約成本超過一百萬美元.與此同時，政府機構繼續推行節能計算[3].因此，降低能源消耗已經成為當今數據中心運營商關注的主要問題.

針對云計算數據中心的能耗問題，文獻[4-5]分別提出了一種精確度高的能耗模型來預測云計算數據中心單臺服務器的能耗狀況，從而實現對整個數據中心的能耗估測.如何在能耗與性能兩者間取得平衡，一種典型的思想就是不定期檢測系統中的空閑設備，然后將其關閉實現節約能耗的目標[6]. 但這種策略的主要問題在于：硬件設備從關閉狀態重新啟動達到運行狀態，這一過程期間會導致系統性能的下降.而云計算的主要支持技術是虛擬化，以經濟高效的方式將單個物理機器分割為多個虛擬機（Virtual Machine，VM），這種技術可以有效地將物理設備邏輯上分成若干子模塊，從而實現對物理設備的高利用率.文獻[7]基于蟻群算法，提出了一種有效的虛擬機放置策略.在同質和異構服務器的云環境中，將候選VM分組在一起，從全局優化的角度有效地減少了用于分配虛擬機的服務器數量，該策略適用于具有不同大小VM的各種分配問題.

考慮到云服務中計算成本、任務執行截止期限、服務質量（Quality of Service，QoS）、高吞吐量等約束條件，有效的任務調度策略成為云計算中一個重要的研究領域.為了解決云環境中的任務調度和資源分配問題，Yang等人[8]提出了一種基于PSO的算法，將每個子任務分配給適當的資源，并對資源上的子任務進行排序以實現此方案的目標.Verma 等[9]提出基于雙準則優先的粒子群算法（Bi-Criteria Priority based Particle Swarm Optimization， BPSO），在可用的云資源上調度工作流任務，并在約束下的執行時間最大限度地降低執行成本. Pandey等人[10]提出了另一種基于PSO的啟發式方案，該方案基于PSO給出的解決方案優化了任務-資源映射的成本，兼顧了計算成本和數據傳輸成本.針對數據密集型工作流的高能耗問題，肖鵬等人[11]提出通過引入“虛擬數據訪問節點”的方法來量化評估工作流任務的數據訪問能耗開銷，并在此基礎上設計了一種“最小能耗路徑”的啟發式策略.這些方法從不同方面對云計算中任務分配問題提出相應的優化方案，從而達到降低能耗開銷、提高系統能效.

目前用于解決云計算中任務分配問題的方法各種各樣，其中任務分配旨在將適當的任務或作業映射到最合適的可用資源上，可將其抽象歸納為與云計算硬件設施效率有關的組合優化問題之一[12].多處理器調度是一個非常難的問題，為了解決這些問題，粒子群算法被廣泛采用，各種應用研究的成果不斷涌現.Rodriguez等[13]提出了一種基于元啟發式優化技術的粒子群優化算法（Particle Swarm Optimization，PSO），該算法的目的是在滿足期限約束條件的同時最小化總體工作流執行成本.文獻[12]提出了一個云環境的多目標任務調度方案，盡量減少任務執行時間、任務傳輸時間、任務執行成本和提高QoS. 文獻[14]提出了一個改進的云環境任務調度算法，結合了模擬退火（Simulated Annealing，SA）算法和粒子群算法（PSO）來提高資源利用率. Patel等人[15]提出了一種基于群體智能算法的混合蟻群優化（Ant Colony Optimization，ACO）/ PSO）技術來優化多播樹.有一些研究者對文獻[16]中提出的基于粒子群優化（PSO）的任務和工作流調度方案進行了深入的分析，提出動態自適應粒子群優化算法（Dynamic Adaptive Particle Swarm Optimization，DAPSO）來增強基本PSO算法的性能，通過最小化特定任務集的完成時間來優化任務運行時間，同時最大化資源利用率[17].這些文獻考慮到PSO算法沒有交叉和變異運算，結構簡單，相比其他算法簡單易實現的特點.但缺乏對算法中慣性權重的動態調節，這會使系統易陷入局部最優，導致收斂精度低和不易收斂問題.

PSO算法的搜索過程是一個通過迭代使搜索空間不斷縮小的過程，其中全局搜索能力和局部搜索能力的平衡對算法的效率起著至關重要的作用[18].本文針對PSO收斂速度慢，易陷入局部最優的問題，提出一種改進的優化調度策略.考慮到粒子群算法中的慣性權重是影響搜索結果和收斂速度的關鍵因素[19]，本文提出了一種適用于云計算資源調度的M-PSO算法，來提高收斂速度以及搜索的良好適應性，從而減少系統開銷.

1? ?系統模型

1.1? 能耗模型

任務分配問題就是將應用程序的一系列任務合理分配到分布式計算系統中相應的可用資源上，以達到計算資源的負載均衡[20]，減少任務執行的等待時間并提高系統輸出效率.用戶對調度結果的評價依據有很多，文中主要研究如何減少任務的完成

時間.

本文在任務分配問題中，考慮任務的執行能耗和任務間交互能耗.結合能耗的計算公式E = P × T，任務從進入云計算系統的時刻t0到執行完畢時刻? t1所產生的能耗可表示為：

定義.云計算系統中任務間的交互關系可定義為任務交互圖（Task Interaction Graph， TIG） ，其中? 代表一個程序的任務，并且T = {1，2，…，m}代表這些任務之間的交互.邊權重eij = （Ti，Tj）表示在節點? ?i和j之間的任務信息交互大小;節點權重wi對應于任務本身大小. 圖1表示了一個任務交互圖（TIG）的實例.

同樣，計算系統可由處理器交互圖（Processor Interaction Graph， PIG）表示為G（P，E）， 其中P = {1，2，…，n}表示系統中的處理器集合和邊權重djk在任何兩個節點之間j和k表示相應處理器之間的路徑長度. 分配問題可以正式表示如下：

M：T→P其中M是任務集合T映射到處理器集合的函數.該問題可以描述為：找到一個任務處理器映射實例M;使得在估計使用每個計算資源所引起的總成本P時，所有計算資源中的最大成本被最小化. Eex（M）k是分配給計算資源k的所有任務的總開銷. Etr（M）i是任務i與其他未分配在相同處理器上的任務之間的總交互開銷.在一個給定的任務分配映射中，系統總開銷E（M）是執行開銷和交互開銷的總和：

在估計所有資源的總開銷時，任務分配問題的目標是找到一個任務分配映射M，對于給定的PIG和TIG上具有最小的開銷：

Minimize（E（M）? ? ？坌M）? ? （3）

1.2? ?任務分配模型

在云環境中，大量的云用戶在不了解系統基礎結構的情況下向云服務提供商提交獨立任務并從云訪問服務.從任務的長度和任務的資源需求來看，任務可視為是異構的[21].

3.2.1? ?加速因子對適應度的影響

圖4（a）表示在任務量300、迭代次數100時，加速因子變量值從1逐漸遞增到2的過程中對算法適應度值的影響.由圖可以看出，適應度值變化的整體趨勢為先增加再遞減，但變化過程中并非嚴格遞增和遞減，其中存在輕微波動.當加速因子值為1.5時，對應的適應度值達到最大，此時為算法的最優狀態.圖4（b）表示將任務量增加至800，算法迭代次數增加到200的情況下，加速因子對適應度值的影響.從圖可以看出，適應度值的變化趨勢和圖4（a）相似，同樣呈現出先增后減的趨勢，并當加速因子取值在1.4至1.6之間達到峰值.由此可以分析出，在不同任務量和迭代次數下，選取加速因子值為1.5時，算法可以有較好的性能表現，故在后面的對比實驗中，將其取值為1.5作為系統參數值.

3.2.2? ?迭代次數對保證率的影響

圖5（a）和5（b）分別表示在加速因子變量取值為1.5、任務量為300和1 000的條件下，迭代次數對完成任務分配的保證率的影響.圖5（a）中，任務量較少時，保證率隨迭代次數的增加變化明顯，且曲線的變化較為平滑.初期當迭代次數取值在20至150之間時，保證率上升速度快，說明此時算法對迭代次數要求比較高，適當增加迭代次數對系統有較高的保證率.但當迭代次數逐漸增加至200時，保證率曲線逐漸出現收斂現象，達到250時變化不明顯. 圖

5（b）中，相應增加任務量，此時IPSO和PSO-ACO算法的保證率曲線變化十分相似，迭代次數在50至200區間時對應的保證率幾乎一致，后期到達收斂時，IPSO算法的保證率略微高于PSO-ACO算法.從圖5（a）和圖5（b）中可以看出，M-PSO算法的保證率始終高于IPSO和PSO-ACO兩種算法，并且三種算法在200次迭代以后保證率的變化都逐漸開始收斂，此時迭代次數對算法的影響較小.但隨著任務量的增加，各算法本身的保證率也會隨著略微降低.

3.2.3? ?任務負載對系統能耗的影響

圖6表示在加速因子取值為1.5、 迭代次數取值為200的條件下，不同的任務數所產生的系統開銷.由圖可以看出，在任務量為200時，算法ACO的系統開銷處于最低，而ACO-PSO和M-PSO算法其次，IPSO算法最高.其原因主要在于，與其他啟發式算法相比，蟻群算法具有較強的魯棒性和較好的求解性能. 同時，在工作任務量較小的情況下，算法的迭代次數對基于PSO的各種改進算法影響不明顯.當執行任務量為400時，算法M-PSO和PSO-ACO的開銷較低，IPSO算法和ACO算法次之，其原因主要為：當主機負載增加時，基于PSO的算法逐漸體現出其在調度方面的優勢.PSO-ACO將ACO的局部搜索和變異操作同時混合到PSO算法中，通過適當調整各自的優勢，從而使得PSO-ACO提高了全局優化的能力. 當負載的任務量進一步增大時，M-PSO算法的優化比率很明顯.與IPSO，PSO-ACO 和ACO相比，在600個任務和200次迭代的情況下，所提出的算法M-PSO分別降低了總開銷的8.5%，7.1%和9.7%，而PSO-ACO與IPSO和ACO相比只降低了2.9%和5.7%的開銷.

后期任務量繼續增加時，M-PSO算法依然保持著較低開銷的優勢.由于ACO算法是一種典型的概率算法，算法中設置的參數通常由實驗方法經驗確定，導致性能的優化與人的經驗密切相關，所以很難做到在不同任務量的情況下一直處于最佳的執行效果. 而混合算法PSO-ACO的收斂速度較慢，隨著任務量的不斷增大算法容易陷入局部最優，導致算法需要較長的搜索時間，其復雜度可以反映出這一點.IPSO算法最主要的問題在于容易過早收斂，這導致其喪失了搜索空間中的種群多樣性，進行全局搜索的優化能力較差.

綜合以上實驗分析，隨著負載任務量的不斷增大，各算法的性能表現也有所變化.粒子群算法在處理大任務量時具有明顯優勢，并且加速因子、慣性系數和迭代次數對粒子群算法的性能表現具有較大影響.這意味著基于PSO算法的M-PSO算法通過對慣性權重系數的改進，克服算法收斂和局部最優問題能夠實現以相對較低的系統開銷執行較大的任務負載量.因此，在云計算環境中分配較大規模任務負載應用時，采用M-PSO算法具有更大的優勢.

4? ?結? ?論

本文提出了一種基于任務調度的改進粒子群優化算法（M-PSO），實驗結果表明：1）在總開銷方面， M-PSO算法在處理任務負載量較大時的性能優于負載量較小的;2）隨著任務量和迭代次數的增加，所提出的M-PSO任務調度算法在降低總開銷方面比其他3種算法（IPSO，PSO-ACO和ACO算法）更有效. 該算法有望應用于實際的云平臺，旨在提高能效，降低任務調度的總開銷.

參考文獻

[1]? ? ZENG L， VEERAVALLI B， ZOMAYA A Y. An integrated task computation and data management scheduling strategy for workflow applications in cloud environments[J]. Journal of Network & Computer Applications，2015，50（C）：39—48.

[2]? ? SINGH S，SWAROOP A，KUMAR A，et al. A survey on techniques to achieve energy efficiency in cloud computing[C]// International Conference on Computing，Communication and Automation. IEEE，2017：1281—1285.

[15]? PATEL M K，KABAT M R，TRIPATHY C R. A hybrid ACO/PSO based algorithm for QoS multicast routing problem[J]. Ain Shams Engineering Journal，2014，5（1）：113—120.

[16]? MASDARI M，SALEHI F，JALALI M，et al. A survey of PSO-based scheduling algorithms in cloud computing [J]. Journal of Network & Systems Management，2017，25（1）：122—158.

[17]? Al-MAAMARI A，OMARA F A. Task scheduling using PSO algorithm in cloud computing environments [J]. International Journal of Grid and Distributed Computing，2015，8（5）： 245—256.

[18]? ROSTAMI A，LASHKARI M. Extended PSO algorithm for improvement problems K-means clustering algorithm [J]. International Journal of Managing Information Technology，2014，6（3）：17—29.

[19] BOROWSKA B. Exponential inertia weight in particle swarm optimization [C]// Information Systems Architecture and Technology： Proceedings of 37th International Conference on Information Systems Architecture and Technology C ISAT 2016 C Part IV. Springer International Publishing，2017：265—275.

[20]? BHARATHI P D，PRAKASH P，KIRAN M V K. Energy efficient strategy for task allocation and VM placement in cloud environment[C]// Power and Advanced Computing Technologies. IEEE，2018：1—6.

[21]? MISHRA S K，PUTHAL D，SAHOO B，et al. An adaptive task allocation technique for green cloud computing [J]. Journal of Supercomputing，2018，74（1）：1—16.

[22]? 束柬，梁昌勇，徐健. 基于信任的云服務系統多目標任務分配模型[J]. 計算機研究與發展，2018，55（6）：1167—1179.

SHU J，LIANG C Y，XU J. Trust-based multi-objectives task assignment model in cloud service system[J]. Journal of Computer Research and Development， 2018， 55（6）： 1167—1179.（In Chinese）

[23]? JU J H，BAO W Z，WANG Z Y，et al. Research for the task scheduling algorithm optimization based on hybrid PSO and ACO for cloud computing[J]. International Journal of Grid & Distributed Computing，2014，7（25）：217—218.