李菁

(湖南電子科技職業(yè)學(xué)院 機(jī)械與電子工程分院， 長沙 410000)

0 引言

隨著各個領(lǐng)域每天都會出現(xiàn)大量的數(shù)據(jù)，目前已經(jīng)進(jìn)入了大數(shù)據(jù)時代，傳統(tǒng)單機(jī)數(shù)據(jù)處理技術(shù)已經(jīng)不能滿足人們對數(shù)據(jù)處理速度的要求，因此出現(xiàn)了云計算技術(shù)[1]。云計算技術(shù)將多種類型的設(shè)備如存儲器、網(wǎng)絡(luò)終端、大型打印機(jī)等進(jìn)行連接，通過“按需分配”、收費(fèi)方式提供給用戶使用，是一種大數(shù)據(jù)處理技術(shù)[2]。在云計算技術(shù)的實際應(yīng)用中，由于云計算資源不僅數(shù)量有限，而且十分寶貴，但是用戶的任務(wù)規(guī)模比較大，如何合理地將云計算資源分配給用戶任務(wù)、同時保證云計算資源負(fù)載均衡十分關(guān)鍵[3]。

針對云計算資源負(fù)載均衡問題，全世界各地的研究人員以及高校進(jìn)行了廣泛的研究，出現(xiàn)了許多類型的云計算資源負(fù)載均衡方法[4]。云計算資源負(fù)載均衡方法可以劃分為兩種類型，一類是傳統(tǒng)方法，一類是現(xiàn)代方法，傳統(tǒng)方法主要包括模糊聚類分析算法的云計算資源負(fù)載均衡方法、窮舉式搜索算法的云計算資源負(fù)載均衡方法，當(dāng)云計算資源負(fù)載規(guī)模比較少時，可以保證云計算資源負(fù)載均衡，用戶任務(wù)完成的效率高，但是隨著云計算資源負(fù)載數(shù)量增加，其計算復(fù)雜度會呈指數(shù)形式增長，難以滿足用戶任務(wù)的實時性要求[5,6]?，F(xiàn)代方法主要是引進(jìn)人工智能技術(shù)[7-9]對云計算資源負(fù)載均衡問題進(jìn)行求解，如：螢火蟲算法、禁忌搜索算法、蜂群優(yōu)化算法、社會力群智能優(yōu)化算法，它們首先建立云計算資源負(fù)載均衡問題的數(shù)學(xué)模型，然后采用螢火蟲算法、禁忌搜索算法、蜂群優(yōu)化算法、社會力群智能優(yōu)化算法進(jìn)行時求解，找到云計算資源負(fù)載最優(yōu)分配方案，求解速度高，時間短，成為當(dāng)前云計算資源負(fù)載均衡的主要研究方向[10,11]。但是在實際應(yīng)用中，現(xiàn)代云計算資源負(fù)載均衡方法也存在一些不足，如云計算資源的負(fù)載分配不均衡，有的資源負(fù)載多，有的資源長期處于空閑狀態(tài)，用戶無法分配得到最合理的云計算資源，使得云計算資源浪費(fèi)十分嚴(yán)重，影響了云計算資源利用率，用戶任務(wù)不能在規(guī)定時間完成[12]。

為了提高云計算資源利用率，保證云計算資源負(fù)載均衡，提出基于改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法，與其它方法進(jìn)行了云計算資源負(fù)載均衡仿真實驗結(jié)果表明，本文方法提高了云計算資源利用率，能夠保證各個云計算資源之間的負(fù)載均衡，相對于其它云計算資源負(fù)載均衡方法，本文方法具有十分明顯的優(yōu)越性。

1 云計算資源負(fù)載均衡問題描述

1.1 云計算系統(tǒng)

在一個云計算系統(tǒng)中，包括大量的云計算資源，每一種云計算資源的性能各異，因此具有典型的異構(gòu)特性，由于云計算系統(tǒng)主要針對大規(guī)模數(shù)據(jù)的處理，通常采用Map/Reduce的數(shù)據(jù)處理模式，首先服務(wù)器節(jié)點(diǎn)資源對一個大規(guī)模用戶任務(wù)進(jìn)行細(xì)化和分配，然后每一個云計算資源得到相應(yīng)的任務(wù)，并執(zhí)行任務(wù)，最后對每一個云計算資源任務(wù)完成結(jié)果進(jìn)行融合，得到大規(guī)模用戶任務(wù)執(zhí)行結(jié)果。在云計算系統(tǒng)工作過程中，要建立2個級別映射，具體為：

(1)建立服務(wù)器與計算資源之間的映射關(guān)系。

(2)建立云計算資源和用戶任務(wù)之間的映射關(guān)系。

1.2 云計算資源負(fù)載均衡的數(shù)學(xué)模型

云計算資源負(fù)載均衡調(diào)度定義：根據(jù)一個云計算資源負(fù)載調(diào)度策略，結(jié)合云計算資源的能力，給每一個云計算資源分配一定數(shù)量的用戶任務(wù)，在滿足用戶任務(wù)完成要求的前提上，保證云計算資源之間負(fù)載分配均衡，使云計算資源利用率達(dá)到最大。設(shè)用戶任務(wù)集合為：T={t1,t2,…,tm}，其中m表示任務(wù)數(shù)量，云計算資源集合為：R={r1,r2,…,rk}，其中k表示云計算資源數(shù)量，而一個云計算資源主要包括CPU、內(nèi)存、網(wǎng)絡(luò)帶寬等具體物理設(shè)備，物理設(shè)備組成的集合為：D={d1,d2,…,dn}，這樣可以得到式(5)。

S={T,R,D,Mtr,Mrd}

(1)

式中，Mtr表示云計算法資源和用戶任務(wù)之間聯(lián)系；Mrd表示云計算資源和具體物理設(shè)備間的聯(lián)系。

設(shè)ti被分配到rj，rj使用dk執(zhí)行ti，任務(wù)ti在dk的執(zhí)行時間為ETC(ti,dk)，那么可以得到式(2)。

ETCkn=ETC(tiMtr,dj)

(2)

Start(dk)為物理設(shè)備dk開始執(zhí)行任務(wù)時間，ti完成時間的計算式為式(3)。

F(tiMtr,dk)=Start(dk)+ETC(tiMtr,dk)

(3)

物理設(shè)備dk上任務(wù)完成時間之和的計算式為式(4)。

(4)

式中，cik的取值方式如式(5)。

(5)

T={t1,t2,…,tm}完成總時間計算式為式(6)。

(6)

云計算資源負(fù)載均衡問題的求解實際上就是找到一個用戶任務(wù)完成時間最少的云計算資源分配方案，即式(7)。

(7)

2 改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法

2.1 云計算任務(wù)調(diào)度信息流的稀疏表示

當(dāng)前云計算任務(wù)調(diào)度信息流通常采用分塊細(xì)化方式進(jìn)行，這樣會使得數(shù)據(jù)之間存在一定的空余，影響云計算任務(wù)調(diào)度效率，云計算任務(wù)調(diào)度信息流模型可以表示為式(8)。

(8)

式中，p表示任務(wù)的階數(shù)；ai(t)表示分塊參數(shù)為式(9)。

ai(t)=-2m(t)cos(θ(t))

(9)

式中，m(t)表示正態(tài)隨機(jī)分布，θ(t)表示均勻分布。

采用改進(jìn)快速稀疏算法對云計算任務(wù)調(diào)度信息流進(jìn)行分解，得到不同大小的云計算任務(wù)，這樣便于分配最合理資源。

2.2 自適應(yīng)遺傳算法求解云計算資源負(fù)載均衡問題

由于當(dāng)前云計算資源負(fù)載均衡問題求解算法，如蜂群優(yōu)化算法，存在收斂速度慢，難以找到全局最優(yōu)的云計算資源負(fù)載均衡方案，因此本文引入自適應(yīng)遺傳算法對云計算資源負(fù)載均衡問題的數(shù)學(xué)模型進(jìn)行求解。自適應(yīng)遺傳算法主要通過交叉算子和變異算子不斷產(chǎn)生新的個體，以保證種群的多樣性，使種群搜索方向朝著問題的全局最優(yōu)解方向進(jìn)行搜索，進(jìn)化初期，交叉概率(Pc)的取值相對較小，變異概率(Pm)的取值相對較大，加快算法的搜索速度，具體方式為式(10)、式(11)。

(10)

(11)

進(jìn)化后期，Pc的取值相對較大，Pm的取值相對較小，提高算法的搜索精度，具體為式(12)、式(13)。

(12)

(13)

式中，fmax和favg為最大適應(yīng)度值和適應(yīng)度平均值，Pc0和Pm0分別表示交叉概率和變異概率的初值。

3 改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法工作步驟

(1)建立云計算系統(tǒng)，確定各種云計算資源的數(shù)量以及各種云計算資源的處理能力。

(2)收集用戶任務(wù)，并采用改進(jìn)快速稀疏算法對云計算任務(wù)調(diào)度信息流進(jìn)行分解，得到不同大小對云計算任務(wù)。

(3)根據(jù)云計算任務(wù)、云計算資源以及物理設(shè)備之間的關(guān)系，以任務(wù)完成時間最少為目標(biāo)建立云計算資源負(fù)載均衡問題的求解數(shù)學(xué)模型。

(4)設(shè)置自適應(yīng)遺傳算法，如種群中的個體數(shù)量等。

(5)初始種群，種群中每一個個體與云計算資源負(fù)載均衡問題的一個解相對應(yīng)，并根據(jù)適應(yīng)度函數(shù)值對個體進(jìn)行排序，確定當(dāng)前最優(yōu)個體。

(6)通過選擇、交叉、變異操作產(chǎn)生新的種群，并根據(jù)適應(yīng)度函數(shù)值對新種群個體進(jìn)行評價，并采用當(dāng)前最優(yōu)個體替代歷史最優(yōu)個體。

(7)進(jìn)化代數(shù)增加。

(8)如果當(dāng)前進(jìn)化代數(shù)等于最大進(jìn)化代數(shù)，那么，根據(jù)當(dāng)前最優(yōu)個體得到云計算資源負(fù)載均衡問題的最優(yōu)解，不然繼續(xù)執(zhí)行步驟(6)～(7)。

4 云計算資源負(fù)載均衡方法的性能驗證

為了分析改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法的性能，選擇文獻(xiàn)[10]和文獻(xiàn)[11]的云計算資源負(fù)載均衡方法進(jìn)行對比實驗。

3種云計算資源負(fù)載均衡方法的任務(wù)完成時間如圖1所示。

圖1 云計算資源負(fù)載均衡方法的任務(wù)完成時間

對圖1的云計算資源負(fù)載均衡方法的任務(wù)完成時間進(jìn)行分析可以知道，改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法的任務(wù)完成時間最短，其次為文獻(xiàn)[11]的云計算資源負(fù)載均衡方法，任務(wù)完成時間最長的是文獻(xiàn)[10]的云計算資源負(fù)載均衡方法，這表明改進(jìn)快速稀疏算法可以為用戶任務(wù)分配到更優(yōu)的云計算資源，提升了用戶任務(wù)完成的速度。

3種云計算資源負(fù)載均衡方法的資源負(fù)載分配結(jié)果如圖2所示。

圖2 云計算資源負(fù)載的分布結(jié)果對比

對圖2云計算資源負(fù)載均衡方法的資源負(fù)載分配結(jié)果進(jìn)行對比和分析可知，改進(jìn)快速稀疏算法的云計算資源負(fù)載十分均衡，沒有出“過負(fù)載”或者“空負(fù)載”現(xiàn)象，而文獻(xiàn)[10]和文獻(xiàn)[11]的云計算資源負(fù)載均衡方法均出現(xiàn)了“過負(fù)載”或者“空負(fù)載”現(xiàn)象，這表明改進(jìn)快速稀疏算法提高了云計算資源利用率，每一個云計算資源都可以分配得到了最合理數(shù)量用戶任務(wù)，提高了云計算系統(tǒng)的處理能力。

5 總結(jié)

為了解決當(dāng)前云計算資源負(fù)載分配不均衡、資源利用率低等難題，提出基于改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡方法。仿真實驗結(jié)果表明，與其它云計算資源負(fù)載均衡方法相比，改進(jìn)快速稀疏算法可以提高云計算資源的利用率，使得云計算資源負(fù)載分配更加均衡，加快了云計算任務(wù)完成的速度，具有十分廣泛的應(yīng)用前景。