基于成本的云計算任務(wù)調(diào)度策略

摘 要：云計算服務(wù)的商用對用戶來說最關(guān)鍵的是成本問題。文章提出了基于粒子群算法的云計算任務(wù)調(diào)度策略。采用了間接編碼的方式，設(shè)置參數(shù)，考慮經(jīng)濟(jì)成本和時間成本因素，選取了適應(yīng)度函數(shù)，實驗結(jié)果表明，文章算法具有較強(qiáng)的尋優(yōu)能力，可以解決云計算任務(wù)調(diào)度問題。

關(guān)鍵詞：云計算；任務(wù)調(diào)度；成本粒子群算法

引言

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

1 任務(wù)調(diào)度問題描述

在云計算環(huán)境下，一個大規(guī)模的任務(wù)計算必須在邏輯上劃分成許多個子任務(wù)進(jìn)行，然后通過處理子任務(wù)來完成主任務(wù)。任務(wù)調(diào)度是將云計算中用戶提交的任務(wù)請求分配到多個資源的過程。在云計算的應(yīng)用中，大多數(shù)是商業(yè)的應(yīng)用，因此在云計算的任務(wù)調(diào)度更多的考慮成本指標(biāo)，同時滿足用戶的需求。成本由時間成本和經(jīng)濟(jì)成本等組成。

2 基于本文算法的云計算任務(wù)調(diào)度

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

2.1 粒子編碼方式

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

子任務(wù)的總數(shù)量：

其中，TNum（t）為第 t 個任務(wù)劃分子任務(wù)的個數(shù)。

對每個子任務(wù)的編碼方式為：

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

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

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

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

完成全部任務(wù)的總花費成本為：

2.2 粒子速度和位置的更新

標(biāo)準(zhǔn)粒子群算法的速度和位置更新公式為：

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

為了增加搜索過程中的種群的多樣性，優(yōu)化最優(yōu)解的搜索能力，本文提出自適應(yīng)的慣性權(quán)重，如下的更新公式

其中rand為0，1之間的隨機(jī)數(shù)

3 實驗仿真與結(jié)果

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

實驗結(jié)果如下圖：

由以上實驗結(jié)果可以看出，與傳統(tǒng)的PSO算法相比，本文算法尋優(yōu)能力更強(qiáng)，收斂速度較快。

4 結(jié)束語

本文研究了云計算任務(wù)調(diào)度模型，改進(jìn)了粒子群算法，并應(yīng)用到云計算任務(wù)調(diào)度上，主要考慮了時間成本和經(jīng)濟(jì)成本。仿真結(jié)果顯示本文算法具有較強(qiáng)的尋優(yōu)能力。

參考文獻(xiàn)

[1]封良良，張?zhí)?，賈振紅，等.云計算環(huán)境下基于改進(jìn)粒子群的任務(wù)調(diào)度算法[J].計算機(jī)工程，2013，39（5）：183-186.

[2]婁建峰，高岳林，李飛，等.基于改進(jìn)粒子群算法的云計算任務(wù)調(diào)度算法[J].微電子學(xué)與計算機(jī)，2016，33（8）：112-116.

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

作者簡介：常賀（1993-），男，碩士研究生，研究方向：計算機(jī)網(wǎng)絡(luò)與控制工程。