基于改進(jìn)人工蜂群算法的云任務(wù)調(diào)度

吳 傲， 陳宏偉

(湖北工業(yè)大學(xué)計算機學(xué)院， 湖北 武漢 430068)

云計算技術(shù)作為一種全新的計算模式，對于用戶來講具有成本低廉，使用即時，操作簡單，計算高效等特點，因而受到業(yè)界的大量關(guān)注，目前已經(jīng)成為計算機領(lǐng)域熱門的研究方向。隨著越來越大的用戶需求，云環(huán)境下的資源分配問題成為一個急需考慮的問題，用戶日益增長的資源需求和云服務(wù)資源的高效分配之間的矛盾是目前云計算資源調(diào)度下最關(guān)鍵的問題。在云計算資源調(diào)度系統(tǒng)中，用戶可以采取租用的形式按需獲取供應(yīng)商提供的計算力、信息服務(wù)以及存儲空間[1]，由于在實際使用中，云計算資源調(diào)度系統(tǒng)面對的用戶群體十分巨大，而且任務(wù)類型極其復(fù)雜，在資源的調(diào)度過程中需要一個合理高效且低成本的分配方案。對于云計算任務(wù)調(diào)度。文獻(xiàn)[2]提出了一種基于改進(jìn)粒子群的云計算任務(wù)調(diào)度策略，從負(fù)載均衡的角度和任務(wù)完成的總時間的角度這兩個方面來對資源調(diào)度任務(wù)進(jìn)行優(yōu)化。

人工蜂群算法(artificial bee colony argorithm,ABC)于2005年由土耳其教授Karaboga基于蜜蜂種群采蜜機制而提出的一種蜂群算法[3-4]。由于BCO算法參數(shù)多，而ABC算法參數(shù)較少，易于實現(xiàn)，因此有關(guān)ABC算法的研究居多。

博弈論是數(shù)學(xué)基礎(chǔ)理論的一個分支方向，其包含博弈者本身、博弈者策略集合、信息、收益和納什均衡等五大因素。目前的研究已有將博弈論用于云環(huán)境下的資源調(diào)度問題中。Osorio等[5]簡要描述了當(dāng)前云資源分配策略，并且首次提出有關(guān)云資源分配框架。Hassan等[6]提出了用博弈論的方法來解決云環(huán)境下有關(guān)資源分配的管理問題，他們得出了合作博弈比非合作博弈的博弈模型更適合云環(huán)境的結(jié)論。

1 相關(guān)技術(shù)介紹

1.1 人工蜂群算法模型

在ABC算法中，蜂群包含3個小種群，分別為雇傭蜂(也稱為引領(lǐng)蜂)，跟隨蜂和偵察蜂[7]。算法原理是將蜜蜂種群尋找食物源的過程數(shù)學(xué)化為尋優(yōu)求解的過程。原ABC算法步驟如下：

1)：由式子(1)初始化種群，含有N個具有D維變量的解

Xi,j=Xmin,j+Rand(0,1)·(Xmax,j-Xmin,j)

(1)

式(1)中i=1,2，…，N，j=1,2,…,D。Xmax,j為搜索解空間的上限，Xmin,j為搜索解空間的下限。Rand(0,1)為區(qū)間[0,1]內(nèi)的隨機數(shù)。每個解Xi(i=1,2,…,N)用一個D維向量來表示，D是待優(yōu)化目標(biāo)問題參數(shù)個數(shù)。

2)引領(lǐng)蜂根據(jù)式(2)對食物源進(jìn)行鄰域搜索，并產(chǎn)生候選解，計算候選解的適應(yīng)度值。基于貪婪選擇原理挑選較好的食物源(解)，保留適應(yīng)度值最高的食物源。

Vi,j=Xi,j+ri,j(Xi,j-Xk,j)

(2)

其中，j=1,2,….,D，k=1,2,…,N，Xk,j，Xi,j為解空間內(nèi)的隨機解，且k≠j，ri,j為[-1,1]區(qū)間內(nèi)的一個隨機數(shù)，若Vi,j函數(shù)值優(yōu)于Xi,j，則前者取代后者。

3)跟隨蜂根據(jù)公式(3)計算食物源的適應(yīng)度值，根據(jù)公式(4)計算得出食物源位置被選擇的概率值。基于上述最優(yōu)食物源,根據(jù)式(2)展開二次鄰域搜索。再計算得出新解的適應(yīng)度值，根據(jù)貪婪選擇策略保留最優(yōu)解。

(3)

(4)

式(4)中：Pi表示為第i個食物源由跟隨蜂選取的概率fiti為其對應(yīng)的適應(yīng)度值。fi為該解的目標(biāo)函值，等同于待優(yōu)化問題的函數(shù)值。

4)若某個解Xi在有限次循環(huán)(定義為Limit_time)之后并沒有得到提高，引領(lǐng)蜂必須放棄該較差的食物源，且引領(lǐng)蜂更改職責(zé)稱為偵察蜂，按照式(5)產(chǎn)生隨機新解。若多次循環(huán)后食物源沒有被放棄，則該食物源為最佳蜜源(即該解為問題最優(yōu)解)。

Xi,j=Xmin,j+Rand(0,1)·(Xmax,j-Xmin,j)

(5)

其中，Xmin,j為目前得到的第j維最小值；Xmax,j為得到的第j維最大值。Rand(0,1)為[0,1]區(qū)間內(nèi)的隨機數(shù)。通過以上種群內(nèi)互相協(xié)作結(jié)合的方式，蜜源會不斷地優(yōu)于上一代，在經(jīng)過多次迭代后，達(dá)到算法所預(yù)設(shè)的次數(shù)或者達(dá)到精度范圍內(nèi)的所需解。以此達(dá)到求最優(yōu)解的過程。

1.2 基于博弈論的云計算資源調(diào)度模型

在資源調(diào)度系統(tǒng)中，首要保證系統(tǒng)資源高效利用和用戶最小等待，此時就需要采用資源調(diào)度算法將任務(wù)合理的分配給不同的服務(wù)器節(jié)點，提升處理效率和用戶滿意度[11]。用戶任務(wù)用Ti表示，則m個任務(wù)可表示為T={T1,T2,…,Tm}。系統(tǒng)中的服務(wù)器節(jié)點為VMi，則n個服務(wù)器節(jié)點可表示為V={VM1,VM2,…,VMn}，對于任意的節(jié)點VMj。

采用如下定義描述該模型，調(diào)度任務(wù)定義如下：

Ti={Lenth,Filesize,Cost}

式中:Lenth為任務(wù)長度；Filesize為任務(wù)文件大小；Cost為任務(wù)花費。

節(jié)點模型如下：

VMj={CPU，Memory，Bandwidth，Cost}

虛擬節(jié)點考慮因素分別為CPU、內(nèi)存大小、網(wǎng)絡(luò)帶寬以及調(diào)度收益成本。云計算資源調(diào)度拓?fù)浣Y(jié)構(gòu)見圖1。

圖 1 云計算資源調(diào)度結(jié)構(gòu)圖

結(jié)合非合作博弈理論，構(gòu)建基于非合作博弈的調(diào)度模型，博弈模型可以用一個五元組表示，模型定義如下

G={Time,ω,C,(Sp(t)),(P(t)p)}

下面給出非合作博弈模型和相關(guān)的表達(dá)式[8]。

1)資源調(diào)度時間耗費 在資源調(diào)度系統(tǒng)中，Ti表示第i個任務(wù)，VMj表示第j個節(jié)點，因此任務(wù)Ti在節(jié)點上VMj會對應(yīng)一個時間耗費，用Time(Ti→VMj)來表示。那么對于一個完整的執(zhí)行序列K必然對應(yīng)一個總時間耗費Time，如

(6)

式中，m表示任務(wù)數(shù)量，n表示服務(wù)器節(jié)點數(shù)量。

2)資源調(diào)度節(jié)點負(fù)載均衡 節(jié)點負(fù)載均衡同樣是納入考慮的重要因素，用ω表示,即

(7)

式中，VMlj表示節(jié)點VMj負(fù)載，aVMlj表示節(jié)點的平均負(fù)載，ω值越小說明系統(tǒng)負(fù)載均衡度越好，此時效率越高。

3)資源調(diào)度中用戶任務(wù)需求花費 另一個重要因素是任務(wù)花費，用C表示用戶支付費用，如

式中：Ccpuj,Cramj,Cbwj為悉尼節(jié)點的特征量。分別代表節(jié)點cpu花費成本，內(nèi)存花費成本，網(wǎng)絡(luò)帶寬花費成本。該式體現(xiàn)了資源調(diào)度服務(wù)按需付費的原則，合理地將任務(wù)分配到不同的計算節(jié)點上，使用戶以最低的成本來達(dá)到目的。

4)效用函數(shù) 在博弈中，對于某個特定的策略序列，該序列下的單位調(diào)度成本的倒數(shù)為效用函數(shù)，用于衡量該調(diào)度的效用：

5)目標(biāo)函數(shù) 資源調(diào)度系統(tǒng)的最大目的為保持各個節(jié)點之間公平均衡調(diào)度的前提下實現(xiàn)系統(tǒng)最低調(diào)度成本和最大化總效用。定義表述目標(biāo)函數(shù)如：

1.3 基于Nash均衡算法求解

Nash均衡點在非合作博弈下具有以下幾個特點，任何博弈參與者在單獨改變行動策略的前提下都不會增加效用函數(shù)，因此利用Nash均衡求解能得到云計算資源調(diào)度的最優(yōu)調(diào)度序列[8-9]。

定理1：在任務(wù)m的需求非合作博弈中，假如不同的任務(wù)最佳反應(yīng)函數(shù)Oi(S-i)滿足如下條件：

1)對于任務(wù)q的調(diào)度策略Sq(?q≠i)，Oi(S-i)是Sq的可微函數(shù)；

則此次任務(wù)Ti的非合作博弈必定存在Nash均衡點。

此外，?S=(s1，s2，…，sm)，根據(jù)文中定義可知S為策略空間，定義Ks=(O1(S-1)，O2(S-2)，…，Om(S-m))，于是有

由拉式中值定理可知：

2 仿真實驗結(jié)果分析

實驗環(huán)境：Inter i7-8086k CPU 4.0GHZ；系統(tǒng)平臺為Windows7操作系統(tǒng)；軟件為MATLAB2018，Cloudsim3.0仿真平臺。本文實驗使用谷歌Cluster trance數(shù)據(jù)作為參考。表1收集了谷歌集群5天內(nèi)的各項參數(shù)變化。

表1 節(jié)點中心部分參數(shù)

本實驗將經(jīng)典的群智能優(yōu)化算法的ACO算法(蟻群優(yōu)化算法)，PSO算法(粒子群優(yōu)化算法)和本文結(jié)合博弈論的改進(jìn)ABC算法(后文統(tǒng)一用BG-ABC算法作描述)做對比，并從多個角度比較分析兩個算法在實際運用中的不同點。實驗結(jié)果見圖2、圖3。

圖 2 任務(wù)完成總時間對比圖

圖 3 節(jié)點間負(fù)載均衡值ω對比圖

由圖2可知，對于資源調(diào)度任務(wù)完成總時間，BG-ABC算法較PSO算法和ACO算法具有更高的速度，PSO算法和ACO算法相差不大。由圖3可知，采用BG-ABC算法的云計算資源調(diào)度系統(tǒng)，其系統(tǒng)的負(fù)載均衡度值相較于PSO和ACO算法更小，說明其系統(tǒng)負(fù)載均衡度更好，相關(guān)公式參見式(2-7)。

為進(jìn)一步驗證改進(jìn)算法的高效性，這里增加實驗，使用Schaffer測試函數(shù)來驗證，理論上最優(yōu)解為0，即當(dāng)實驗結(jié)果越接近0表示越精確。Schaffer函數(shù)具體表達(dá)式如下：

實驗對比見圖4。實驗結(jié)果表明，BG-ABC算法在測試函數(shù)求最優(yōu)值上具有高效性和精準(zhǔn)性，精確度高于ACO算法和ABC算法。

圖 4 Schaffer函數(shù)尋優(yōu)結(jié)果對比

3 結(jié)束語

本文提出了基于博弈論的云計算資源調(diào)度優(yōu)化模型，并以人工蜂群算法為前提。該模型考慮了調(diào)度時間，節(jié)點間負(fù)載均衡度，資源調(diào)度花費，效用函數(shù)和目標(biāo)函數(shù)。將改進(jìn)后的GB-ABC和傳統(tǒng)PSO算法、ACO算法同時運用在資源調(diào)度下，并對實驗結(jié)果進(jìn)行對比，同時利用測試函數(shù)進(jìn)一步證明BG-ABC算法的有效性。結(jié)果表明，BG-ABC算法較同類型的其他算法效果更佳。