馬鈺，楊迪，王鵬

（長春理工大學 計算機科學技術學院，長春 130022）

云計算在一定程度上脫離了傳統(tǒng)意義上的計算概念，是一個基于Web2.0的計算型服務平臺，通過“云”端服務器將巨大的數(shù)據(jù)處理任務拆解、整合，通過特定的資源調度策略分配給系統(tǒng)內多個計算資源進行分析處理。其中資源調度算法對整個云計算平臺具有十分重要的意義，是影響用戶體驗最重要的環(huán)節(jié)。云計算資源調度目的在于如何將用戶的云任務請求在高服務質量、高響應速度的約束下，分配到云環(huán)境中的物理計算資源，其本質是一個NP完全問題，即多項式復雜性的不完全問題［1］。這一過程需要一系列執(zhí)行效率優(yōu)秀、結果穩(wěn)定的調度算法支撐。近二十年來，人們通過對自然界的認知，提出了一個又一個新型群智能算法，并不斷進行優(yōu)化改進。一些性能突出、實現(xiàn)簡單、執(zhí)行穩(wěn)定的算法，如遺傳算法（Genetic Algorithm，GA）［2］、蟻群算法（Ant Colony Optimization，ACO）［3］、粒子群算法（Particle Swarm optimization，PSO）［4］、菌群優(yōu)化算法（Bacterial Foraging Optimization，BFO）［5］、蛙跳算法（Shuffled Frog Leading Algorithm，SFLA）［6］、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）［7］等已經應用到實際中，在減少能源消耗方面做出巨大貢獻。其他新型和融合型算法也受到越來越多的關注。

上述算法中對粒子群算法的研究，重點集中在種群粒子的訓練方式，即通過不同適應度函數(shù)對粒子進行篩選，保留篩選結果更加優(yōu)秀的適應度函數(shù)，忽略了算法執(zhí)行過程中的關鍵參數(shù)，即學習因子和慣性權重對算法整體執(zhí)行效率的影響。

設定固定參數(shù)后，由于種群質量不同導致算法執(zhí)行效率不穩(wěn)定，部分種群在算法執(zhí)行后期存在著陷入局部最優(yōu)解的可能。針對上述不足，本文基于CloudSim平臺使用模擬退火、自適應權重策略對粒子群算法進行優(yōu)化改進，將算法的關鍵參數(shù)，即學習因子、慣性權重等交由上述策略進行實時控制，提高算法初期的全局搜索能力，加快算法后期篩選最優(yōu)解和收斂速度，從而提高算法平均執(zhí)行效率，在面對不同的云環(huán)境下能夠更好更快地執(zhí)行響應。

1 云計算資源調度算法

1.1 云計算資源調度模型

云計算的主要目標是將可用的云計算資源進行調度層面的優(yōu)化［8］。調度算法通常目的是將云計算任務分散到各個可用處理器上，并以最大效率利用它們，降低整體運行時間。云計算中任務調度主要包括兩方面：一是任務和虛擬資源間的調度關系，為云任務分配虛擬計算資源，二是虛擬計算資源和物理設施的調度關系，為虛擬計算資源提供物理設施支持［9］。

用戶將云計算任務提交到分配服務器中，服務器響應到任務后自動將任務分割為一系列最小、可獨立執(zhí)行的子任務，數(shù)據(jù)中心使用相應優(yōu)化調度算法，對收到的子任務合集進行合理分配，最終將處理結果展示給用戶。云計算資源調度系統(tǒng)模型如圖1所示。

圖1 云計算資源調度系統(tǒng)模型

云計算資源調度效率［10］直接影響總體執(zhí)行效率，直觀上反應為用戶提交云任務后的響應時間和結果顯示時間，對衡量服務質量起決定性作用。云計算中的調度本質上是一種映射關系，將客戶提交的任務分配到性能各異的虛擬資源上，隨后各個資源節(jié)點并行獨立計算已分配的子任務。

在數(shù)學角度，云計算資源調度問題可描述為：服務端將n個云任務分配到m個虛擬計算資源節(jié)點上運算（m＜n），F(xiàn)m表示云任務和資源節(jié)點之間的映射關系，任務和資源節(jié)點的映射關系如下：

資源調度由資源調度策略、分配優(yōu)化目標、資源調度算法、調度系統(tǒng)、界定關系和約束關系六部分組成。其中資源調度策略決定了整個云計算平臺的總體性能，由服務商實際投入使用的物理資源配置決定；優(yōu)化目標指調度過程中以用戶特定需求、利潤率、執(zhí)行性能等作為目標進行對應的優(yōu)化；調度算法是指在成本、響應時間等維度上對目標函數(shù)進行優(yōu)化。

1.2 粒子群資源調度算法

粒子群算法是基于自然界中昆蟲、獸群、鳥群和魚群的動物群集智能行為，通過群體中個體之間的信息交流來尋找最優(yōu)解的智能型算法。這些群體按照一定規(guī)律合作尋找目標，群體中的每個成員通過繼承和學習其他成員的位置和速度信息不斷改變自己的搜索方式。

算法中每個粒子包含兩個屬性：速度vi和位置xi。假設存在一個n維m個粒子的樣本空間代表n個相互獨立的子任務和m個虛擬計算資源，第i個粒子的位置表示為：xi={xi1,xi2,…,xij}，其中j表示云任務編號，xij表示分配的虛擬資源編號；全局最優(yōu)解表示為：pg={pg1,pg2,...,pgd}。粒子的速度和位置的更新方法如下：

其中，ω表示慣性權重；c1和c2表示學習因子，c1和c2的大小決定了粒子識別能力的強弱和分享信息的效率［11］；r1和r2是［0，1］區(qū)間內均勻且相互獨立的隨機數(shù)。

在粒子群算法中，常用適應度來篩選不同的粒子，適應度的值通常通過目標函數(shù)計算得出。在云計算調度過程中，常用云任務的總完成時間來衡量粒子優(yōu)劣。云任務在虛擬計算資源上的執(zhí)行時間通常使用一個m×n階的矩陣表示。MATRIX(i,j)表示虛擬計算資源j執(zhí)行云任務i所用的時間。當MATRIX(i,j)=0時表示子任務i沒有進行分配。虛擬計算資源j上分配到的子任務運行時間如下：

其中，i∈ [1,n]；j∈ [1,m]；n表示分配到單個計算資源上的云任務數(shù)量；m表示云計算資源數(shù)量。各個虛擬資源都處于空閑狀態(tài)時，說明所有云任務均執(zhí)行完畢，得到完成總時間TotalTime，表達式如下：

粒子群算法的核心參數(shù)為慣性權重ω與加速系數(shù)。如果c1與之較大會導致隨機性過大，c2值較大會影響最優(yōu)值，ω值較大會讓粒子速度過大從而越過區(qū)域目標，影響算法穩(wěn)定性。在保證種群規(guī)模的情況下，適當提高迭代次數(shù)使結果更趨向于最優(yōu)解。

當粒子群中的某個個體尋找到最優(yōu)解或接近最優(yōu)解時，其他的粒子會自發(fā)的向其學習，快速向最優(yōu)方向搜索，大大提高了算法的效率。但粒子群算法依賴于初始種群的質量，如果設置不當會導致算法后期篩選最優(yōu)解的速度變慢與陷入局部最優(yōu)解等問題。

2 粒子群算法優(yōu)化改進

2.1 基于模擬退火的粒子群優(yōu)化算法（SAPSO）

粒子群算法前期由于參數(shù)設置的不同，導致全局尋優(yōu)能力不足，尋找到的局部最優(yōu)解數(shù)量較少，而模擬退火策略（Simulated Annealing，SA）在全局尋優(yōu)上有著天然的優(yōu)勢，該策略的核心是物理學中的固體降溫退火規(guī)律。該算法以一定概率接受劣質解，從而在一定程度跳出局部最優(yōu)解。本節(jié)在粒子群算法的基礎上引入模擬退火策略，采用雜交運算和帶高斯變異運算［12］，通過式（2）、式（3）計算出一代新的群體，獨立進行雜交和帶高斯變異運算。將得到的結果個體進行模擬退火處理，獲得最終可行解個體。

每輪計算中，雜交運算選擇一定數(shù)量的粒子進行雜交操作，產生新的子代。雜交公式如下：

其中，x代表位置向量，而childk(x)和parentk(x)中的k=1，2對應子代、父代空間位置；p代表隨機空間向量。子代粒子的速度計算公式如下：

其中，v代表速度向量；而childk(x)和parentk(x)中的k=1，2對應子代速度和父代速度。變異運算選取定量的粒子進行高斯變異，淘汰變異前的粒子，公式如下：

首先通過進化產生一個適應度較高的優(yōu)良群體，然后以一定概率進行雜交、變異生成一個多樣性群體，最后通過模擬退火策略對群體進行降溫優(yōu)化。具體算法流程如下：

（1）初始化參數(shù)：交叉概率Pc，變異概率Pm，學習因子c1和c2，溫度冷卻參數(shù)C，初始溫度T。

（2）隨機產生規(guī)模為N的粒子種群。

（3）采用式（2）、式（3）對種群中的粒子進行更新操作。

（4）對步驟（3）產生的種群以交叉概率Pc篩選符合條件的粒子形成新的子種群。從子種群中隨機選取兩個個體xj,xk，按照式（6）、式（7）進行交叉操作，產生兩個新個體x′j,x′k。

計算適應函數(shù)值f(xj)，f(xk)，f(x′j)，f(x′k)，若min{1,exp(-f(x′j)-f(xj)/T)} ＞R，則把x′j作為新的粒子個體，若 min{1,exp(-f(x′k)-f(xk)/T)} ＞R，則把x′k作為新粒子個體。其中R∈ [0,1]。

（5）對交叉操作后產生的新種群以概率Pm篩選出符合條件的粒子形。從新的種群中隨機選取粒子個體xj，按式（10）進行高斯變異操作，產生一個新粒子個體x′j，計算目標函數(shù)值f(xj)和f(x′j)，若 min{1,exp(-f(x′j)-f(xj)/T)} ＞R，則 把x′j作為新粒子個體。

（6）當經過篩選后的個體滿足預定最優(yōu)解條件時，即為全局最優(yōu)解，算法結束。

（7）若迭代次數(shù)不足，則進行退火降溫操作，令T→CT，回到步驟（3）。

基于模擬退火的粒子群算法流程圖如圖2所示。

圖2 基于模擬退火的粒子群算法程圖

2.2 基于自適應權重的粒子群優(yōu)化算法（SAWPSO）

粒子群算法在隨機搜索中存在易陷入局部最優(yōu)解的問題，慣性權重的取值對算法的前期和后期都起著決定性作用，較大的慣性權重會加強算法前期搜索全部可行解的能力，較小的慣性權重會加快算法后期篩選最優(yōu)解的速度。因此可以通過自適應權重策略控制慣性權重來達到全局搜索能力和局部搜索能力的平衡，加快算法的執(zhí)行速度。

本節(jié)中采用的自適應慣性權重（Self-Adaptive Weight）［13］系數(shù)的表達式如下：

其中，ωmax和ωmin分別表示ω的最大值和最小值；f表示粒子目標函數(shù)即適應度的值；favg和fmin表示當前粒子的平均目標值和最小目標值。式中的ω使用自適應權重策略進行實施更改。算法具體步驟如下：

（1）將一個云任務和一個虛擬資源的對應分配關系視為一個粒子解，初始化粒子群中的相關參數(shù)。

（2）計算每個粒子的適應度的值，并從中篩選適應度最優(yōu)的粒子作為一個局部最優(yōu)解。

（3）比較當前粒子的適應度與均值適應度，根據(jù)結果更改公式（11）的慣性權重系數(shù)。

（4）開始進一步迭代，根據(jù)自適應權重方程來調整最優(yōu)粒子的速度和位置，計算方法如下：

（5）粒子位置更新后再次調用目標函數(shù)，并取得最新的適應度與整個算法流程中最好位置gbest比較，如果適應度提升，則將最佳位置更新。

（6）若未滿足預定的收斂條件則返回步驟（1），若滿足條件則算法終止，求得最優(yōu)解。

基于自適應權重的粒子群優(yōu)化算法流程圖如圖3所示。

圖3 自適應權重粒子群算法程圖

3 實驗結果與分析

3.1 實驗環(huán)境及參數(shù)設置

本文基于CloudSim平臺進行仿真模擬實驗，通過虛擬化技術將實例對象模擬為實際的物理資源，提供雙向分配操作，完成物理主機、虛擬機、云任務之間的相互映射。其中軟硬件環(huán)境具體配置如表1和表2所示。

表1 硬件環(huán)境

表2 軟件環(huán)境

CloudSim平臺虛擬機、算法參數(shù)如表3所示。

表3 虛擬機、算法參數(shù)設置

3.2 實驗結果對比分析

實驗中虛擬機和云任務均采用空間共享策略，即運行在同一個虛擬機的任務需要排隊按順序完成。

本文通過以下兩個實驗對改進前后的粒子群算法進行比對，每組實驗結果為運行10次取平均值。

實驗1：粒子群算法優(yōu)化前后的執(zhí)行效率比對傳統(tǒng)粒子群算法（PSO）與基于模擬退火策略（SAPSO）和自適應權重策略（SAWPSO）的優(yōu)化算法在同等條件下進行測試，測試結果如圖4所示。

圖4 粒子群算法優(yōu)化結果

圖4中展示了粒子群算法優(yōu)化前后的執(zhí)行效率對比結果，從實驗結果來看，云任務數(shù)量相同時，基于自適應權重的粒子群優(yōu)化算法所需執(zhí)行時間更短。

實驗2：不同資源調度算法的負載均衡性能比對云環(huán)境中隨著云任務數(shù)量急劇增加，良好的調度算法可以更加高效地處理這些計算任務。本文采用虛擬機負載不均衡率D來衡量每個虛擬資源上分配到的云任務數(shù)量情況。由于用戶提交的云任務往往在數(shù)量上存在很大差異，所以不能以傳統(tǒng)的虛擬機-云任務數(shù)量對應關系評估，而是選用更加均衡的虛擬機占用時間來衡量，衡量方式如下：

而每個虛擬機占用的時間T如下：

實驗過程中將遺傳算法（GA）、蟻群算法（ACO）、粒子群算法（PSO）、基于模擬退火的粒子群算法（SAPSO）、基于自適應權重的粒子群算法（SAWPSO）處于不同云任務數(shù)量下時虛擬機的負載情況進行比較，實驗結果如圖5所示。

圖5 任務數(shù)不同時負載均衡情況對比

通過實驗1與實驗2得出，基于自適應權重的粒子群優(yōu)化算法相對于其他調度算法的負載均衡性能更好，執(zhí)行效率更高，資源利用率更大。優(yōu)化前粒子群算法存在著固有缺陷，如全局搜索能力不足，后期收斂能力緩慢。模擬退火策略提高全局搜索能力，提高可行解數(shù)量，對算法執(zhí)行效率有一定改進，而自適應權重則側重于提高算法后期收斂速度，故自適應權重策略對粒子群算法的執(zhí)行效率提高效果更加突出。

隨著任務規(guī)模的增加，系統(tǒng)資源利用率逐步提升，由于時間限制，本文采用的虛擬機數(shù)量較少，加之群智能算法本身子代的隨機性屬性，會導致個別虛擬機分配不到任務而造成空閑的情況。但當問題規(guī)模足夠大時，使用群智能算法進行優(yōu)化后，資源利用率得到了較大的提升。

4 結論

結合現(xiàn)有的群智能算法和CloudSim云計算平臺技術等研究場景，本文的論述重點在于如何最大限度提高資源調度的效率，如何將現(xiàn)有的算法與其他調度策略相融合，應用這些策略后又該如何調節(jié)參數(shù)來最大化這些優(yōu)化。基于模擬退火算法和自適應權重的粒子群優(yōu)化算法在性能上有了一定的提升，但仍有許多地方需要改進。例如針對單個高處理量云任務或碎片化云任務時，算法的執(zhí)行時間仍不是穩(wěn)定的，算法的隨機性過大，在實際云環(huán)境下可能增大云服務器在分配任務過程中的負擔，造成不必要的消耗；針對目前的群智能算法發(fā)展，不僅要考慮到算法的執(zhí)行效率，還要考慮到算法在不同環(huán)境下的穩(wěn)定性以及在整個調度過程中的分配任務時間的占比情況，這也將是云計算資源調度等相關領域發(fā)展的重點。