胡志剛 常健 周舟

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

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

中圖分類號(hào)：TP338.8? ? ? ? ? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)志碼：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）

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

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

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

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

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

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

1.1? 能耗模型

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

時(shí)間.

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

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

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

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

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

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

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

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

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

圖4（a）表示在任務(wù)量300、迭代次數(shù)100時(shí)，加速因子變量值從1逐漸遞增到2的過程中對算法適應(yīng)度值的影響.由圖可以看出，適應(yīng)度值變化的整體趨勢為先增加再遞減，但變化過程中并非嚴(yán)格遞增和遞減，其中存在輕微波動(dòng).當(dāng)加速因子值為1.5時(shí)，對應(yīng)的適應(yīng)度值達(dá)到最大，此時(shí)為算法的最優(yōu)狀態(tài).圖4（b）表示將任務(wù)量增加至800，算法迭代次數(shù)增加到200的情況下，加速因子對適應(yīng)度值的影響.從圖可以看出，適應(yīng)度值的變化趨勢和圖4（a）相似，同樣呈現(xiàn)出先增后減的趨勢，并當(dāng)加速因子取值在1.4至1.6之間達(dá)到峰值.由此可以分析出，在不同任務(wù)量和迭代次數(shù)下，選取加速因子值為1.5時(shí)，算法可以有較好的性能表現(xiàn)，故在后面的對比實(shí)驗(yà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ù)的增加變化明顯，且曲線的變化較為平滑.初期當(dāng)?shù)螖?shù)取值在20至150之間時(shí)，保證率上升速度快，說明此時(shí)算法對迭代次數(shù)要求比較高，適當(dāng)增加迭代次數(shù)對系統(tǒng)有較高的保證率.但當(dāng)?shù)螖?shù)逐漸增加至200時(shí)，保證率曲線逐漸出現(xiàn)收斂現(xiàn)象，達(dá)到250時(shí)變化不明顯. 圖

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

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

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

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

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

4? ?結(jié)? ?論

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

參考文獻(xiàn)

[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)多目標(biāo)任務(wù)分配模型[J]. 計(jì)算機(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.