面向云環(huán)境中任務(wù)負載的粒子群優(yōu)化調(diào)度策略

胡志剛 常健 周舟

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

關(guān)鍵詞：云計算;任務(wù)調(diào)度;慣性權(quán)重;粒子群優(yōu)化

中圖分類號：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）

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

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

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

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

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

1? ?系統(tǒng)模型

1.1? 能耗模型

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

時間.

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

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

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

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

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

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

1.2? ?任務(wù)分配模型

在云環(huán)境中，大量的云用戶在不了解系統(tǒng)基礎(chǔ)結(jié)構(gòu)的情況下向云服務(wù)提供商提交獨立任務(wù)并從云訪問服務(wù).從任務(wù)的長度和任務(wù)的資源需求來看，任務(wù)可視為是異構(gòu)的[21].

3.2.1? ?加速因子對適應(yīng)度的影響

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

3.2.2? ?迭代次數(shù)對保證率的影響

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

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

3.2.3? ?任務(wù)負載對系統(tǒng)能耗的影響

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

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

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

4? ?結(jié)? ?論

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

參考文獻

[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]? 束柬，梁昌勇，徐健. 基于信任的云服務(wù)系統(tǒng)多目標任務(wù)分配模型[J]. 計算機研究與發(fā)展，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.