基于成本的云計算任務調度策略

摘 要：云計算服務的商用對用戶來說最關鍵的是成本問題。文章提出了基于粒子群算法的云計算任務調度策略。采用了間接編碼的方式，設置參數，考慮經濟成本和時間成本因素，選取了適應度函數，實驗結果表明，文章算法具有較強的尋優能力，可以解決云計算任務調度問題。

關鍵詞：云計算；任務調度；成本粒子群算法

引言

在這大數據的時代，云計算已是學術界、商界的新貴。雖然云計算技術在商業中應用的比較廣泛，但是就云計算技術，還有許多需要完善和改進的。云計算是一種商業計算模型，它將計算任務分布在大量計算機構成的資源池上，是各種應用系統能夠根據需要獲取計算力、存儲空間和信息服務。

1 任務調度問題描述

在云計算環境下，一個大規模的任務計算必須在邏輯上劃分成許多個子任務進行，然后通過處理子任務來完成主任務。任務調度是將云計算中用戶提交的任務請求分配到多個資源的過程。在云計算的應用中，大多數是商業的應用，因此在云計算的任務調度更多的考慮成本指標，同時滿足用戶的需求。成本由時間成本和經濟成本等組成。

2 基于本文算法的云計算任務調度

粒 子 群 優 化 算 法（Particle Swarm Optimization，簡稱PSO）是由美國的J.Kennedy 博士和 R.C.Eberhart受鳥群覓食行為的啟發提出的一種基于群體智能的優化算法。因算法程序結構簡單、需要調節的參數較少、高效等特點，被廣泛應于到科學研究。

2.1 粒子編碼方式

本文采用間接編碼方式，采用離散數值編碼，編碼長度等于子任務數量。設有M個任務，N個資源，每個任務又劃分為多個子任務。

子任務的總數量：

其中，TNum（t）為第 t 個任務劃分子任務的個數。

對每個子任務的編碼方式為：

采用自然數編碼，即按任務自然數順序進行編碼。第i個任務中的第 j 個子任務的序號是 R[i，j]。

文中使用ETC 矩陣[1]表示任務的運行時間，ETC（i，j）表示子任務i在第j個資源上執行的時間。其中，ETC（i，j）表示子任務i在云資源j上執行的時間，ETC（i，j）=0表示子任務i不在資源j上執行。用RUC數組表示計算資源單位時間內任務執行的成本[3]，根據粒子解碼結果和ETC矩陣[2]，可看出資源j運行完被分配到本資源的全部子任務的時間Time（j）：

所有資源上的子任務全部執行完后，表示全部任務運行完畢，則任務的總完成時間FTime：

第r個資源運行本資源上的全部子任務所花費的總時間為：

完成全部任務的總花費成本為：

2.2 粒子速度和位置的更新

標準粒子群算法的速度和位置更新公式為：

其中[2]，ω代表慣性權重，v表示第i個粒子在第k+1次迭代時在j維的速度，c1、c2表示粒子個體的學習因子和粒子群體的學習因子，r1，r2為0到1之間均勻分布的隨機數，x表示第i個粒子在第k+1次迭代時在j維的位置，pbest表示第i個粒子在第k次迭代時個體歷史最優位置，gbest表示第k次迭代時的全局最優位置。其次為了防止粒子飛出最大解空間，通常限制vij∈（-vmax，vmax）。

為了增加搜索過程中的種群的多樣性，優化最優解的搜索能力，本文提出自適應的慣性權重，如下的更新公式

其中rand為0，1之間的隨機數

3 實驗仿真與結果

本文實驗使用Matlab生成ETC矩陣和RCU數組。運用CloudSim-3.0對傳統粒子群算法和本文算法進行云環境下的仿真實驗，實驗在任務數相同、任務大小相同、計算資源的計算能力相同的情況下進行。實驗測試執行200次，采用200次實驗的實驗結果的平均值作為作圖的數據。實驗參數設置：種群規模P為50個，計算資源數N為10個，任務數M為20個，慣性權重ωstart、ωend為0.95、0.4，學習因子c1、c2為2、2，最大迭代次數為1000次。

實驗結果如下圖：

由以上實驗結果可以看出，與傳統的PSO算法相比，本文算法尋優能力更強，收斂速度較快。

4 結束語

本文研究了云計算任務調度模型，改進了粒子群算法，并應用到云計算任務調度上，主要考慮了時間成本和經濟成本。仿真結果顯示本文算法具有較強的尋優能力。

參考文獻

[1]封良良，張陶，賈振紅，等.云計算環境下基于改進粒子群的任務調度算法[J].計算機工程，2013，39（5）：183-186.

[2]婁建峰，高岳林，李飛，等.基于改進粒子群算法的云計算任務調度算法[J].微電子學與計算機，2016，33（8）：112-116.

[3]封良良，夏曉燕，賈振紅，等.實驗基于資源預先分類的云計算任務調度算法[J].計算機仿真，2013，30（10）：363-367.

作者簡介：常賀（1993-），男，碩士研究生，研究方向：計算機網絡與控制工程。