一種加權歐氏距離負載均衡云任務調度算法

李 英，李 亞，劉廣亮

(南陽師范學院軟件學院，河南 南陽473061)

0 引言

云計算是在并行計算、分布式計算、集群計算、網格計算的基礎上發展起來的一種新興計算模式[1］，其基本思想是通過構建數據中心，并采用成熟的虛擬化技術給用戶提供服務[2］。然而，不同的用戶對服務的需求是不同的，這就要求云計算平臺能夠通過任務調度為不同的用戶提供不同類型的服務，并保證用戶能夠獲得較好的服務質量。

任務調度是云計算的關鍵技術之一。云任務調度的目的就是按照某種策略，將任務合理地分配到處理單元，以達到完成時間最短、成本最小以及提高系統利用率等目的[3］。

目前，云計算的任務調度算法具有較好的完成時間，但是并不符合云計算按需分配的特性，不能滿足用戶的需求。為此，本文提出了基于加權歐氏距離的負載平衡的云計算任務調度算法(簡稱EDW-LB算法)。EDW-LB算法針對云計算平臺中任務執行時的動態特征，提出使用加權歐式距離來計算任務和資源的相關程度，使云計算任務能夠分配到合適的資源中，更好的滿足用戶對完成時間以及帶寬等多方面的需求。通過仿真和分析，表明該算法是可行的，并將本算法與目前比較常用的最優時間調度算法進行對比，證明了在用戶滿意度和資源利用率方面取得了較好的效果。

1 問題描述

云環境中使用成熟的虛擬機技術，將物理層上的硬件映射到虛擬機層上，用戶的任務是通過虛擬機來執行的[4］。任務調度相應于完成把n個任務通過某種策略合理的分配到虛擬機上執行。

服務質量(QoS)是衡量用戶使用云計算服務滿意度的標準。QoS衡量參數大致可以分為:完成時間、費用、帶寬和可靠性[4］。本文通過QoS參數對任務進行劃分。

1.1 任務描述

云任務集合用T={T1，T2，…，Tn}表示，每個任務的屬性集合表示為:

其中，IDi為云任務的編號;TYPEi為云任務的類型;Li為任務的總長度;INi為任務的輸入大小;OUTi為任務的輸出大小;Ei為用戶對任務的期待值;Ji為用戶對任務的滿意度。

任務的類型是根據QoS參數對進行劃分，每一類任務都對資源有著不同的需求指標。例如，計算型任務要求任務完成時間較短，而有些任務對帶寬有著較高的要求。文獻[2］提出給每類任務設定一般期待向量:

設第i類任務的一般期待向量為[2］:

其中，ei1、ei2、ei3、ei4、ei5分別表示對虛擬機的CPU數量、內存大小、帶寬、任務執行的費用以及虛擬機的故障率的期待值。

1.2 資源描述

虛擬機集合用V={V1，V2，…，Vm}表示，每個虛擬機的性能參數集合表示為:

其中，IDi為虛擬機的編號;PENi為虛擬機中包含的處理機或者CPU個數;RAM為虛擬機的內存;BWi為虛擬機的帶寬;FRi為虛擬機的故障率;PPUi為虛擬機單位時間內的使用價格。

2 WED_GA_LB任務調度算法

2.1 相關計算

2.1.1 歸一化

將虛擬機的 5 個性能參數進行歸一化，令集合Xij={X1j，X2j，…，Xij}，i∈[1，m］，j∈[1，5］，Xij表示第i個虛擬機的第j個屬性(不包括虛擬機ID)，歸一化值為:

其中，GXij為第i個虛擬機的第j個性能參數歸一化后的值;curXij、minXij、maxXij分別為性能當前值、最小值和最大值。

2.1.2 歐氏距離的計算

任務的一般期待向量可以體現每種不同類別任務對資源性能的不同需求，因此，可以通過計算任務的一般期待向量與歸一化后的資源性能參數的歐氏距離，獲得最適合用戶需求的資源。假設某任務的一般期待向量為[e1，e2，e3，e4，e5］，某虛擬機性能參數歸一化后為[GXi1，GXi2，GXi3，GXi4，GXi5］，則該云任務與第i個虛擬機的歐式距離表示為[5-6］:

式(4)在計算任務與虛擬機的距離時，將各個性能所起的作用看成是一樣的，然而對于不同類別的任務對虛擬機性能的要求是不一樣的，所以這樣顯然是不合理的。文中提出加權的歐式距離，使計算距離時根據任務分類不同，虛擬機性能參數所起的作用也不同。加權歐式距離定義如下:

2.1.3 虛擬機負載計算

本文通過對虛擬機的性能參數歸一化后的值GXij來計算虛擬機的負載能力，具體操作為:首先，計算每個虛擬機的綜合性能指標為第i個虛擬機的第j個性能參數歸一化后的值。再將GSi/min(GSi)，得到虛擬機負載能力向量 gs= [gs1，gs2，gs3，gs4，gs5］。

定義1 虛擬機當前負載狀態[7］指在當前分配到該虛擬機上的所有任務的長度之和(長度單位為字節)。第i個虛擬機的當前負載狀態表示為:

其中，m為虛擬機的個數。

通過以上描述可知:第i個虛擬機的當前負載狀態Loadi＞gsi×SLoad時，則該虛擬機負載較重。此時，需要將任務轉移到其他虛擬機上。文中采用的轉移方法是根據歐氏距離來轉移。

2.1.4 任務的滿意度J值

任務執行完后，需要計算任務的滿意度J的值。任務i的滿意度可以表示為:

其中，m為當前分配到該節點的任務數;Lk為第k個任務的長度(長度單位為字節)。

由式(6)可得當前系統中總負載量SLoad為:

其中，Texpt為任務的期待執行時間;Tact為任務實際的執行時間;BWact為任務實際獲得的帶寬;BWexpt任務期待的帶寬;COSTexpt為任務期待的成本;COSTact為任務實際成本;Psucces為任務期待的可靠完成率;P為機器的故障率。

Ji=0說明該任務獲得的資源與期待的資源一致;Ji＞0表示該任務獲得的資源的性能高于期待的資源;Ji＜0表示該任務獲得的資源沒有達到期待值。

2.2 EDW-LB算法流程

根據前面的描述得知任務與資源之間的歐式距離越小，資源的性能也就越符合任務的期待值。這里需要考慮一個問題，同一類型的任務很有可能會被分配到同一個資源上，這樣就會造成某個或某些資源的負載過重，從而導致任務的完成時間過長。因此，本文提出的EDW-LB算法不僅考慮歐氏距離，而且還需要考慮資源的負載情況。該算法的偽代碼如下:

EDW-LB-bindCloudletToVM(cloudletList，vmList)

Foreach t in T

//計算任務t與各個資源加權歐式距離

eucliddis[］=ComputeWEuclidDis(vmList，t)

//根據加權歐式距離的值對資源進行排序(升序)，

并記錄資源的編號

vmOS[］=SortVmByED(eucliddis[］)

Foreach i in vmOS[］

//暫時第i個任務分配給歐式距離最小的資源

Allocate t to vmOS[i］

//考察編號為vmOS[i］資源的狀態

If(LoadvmOS[i］＞ gsvmOS[i］*SLoad)

//如果該資源負載較重，

根據歐式距離將任務分配給下一個資源

Allocate t to vmOS[i+1］

EndIF

EndFor

endFor

3 仿真實驗

使用云計算仿真平臺Cloudsim[8-10］來驗證提出的基于加權歐式距離的負載均衡任務調度算法的可行性與算法性能，并與順序任務調度算法、最優完成時間調度算法進行了仿真比較。

3.1 實驗設置

[2］將所有任務分成兩類，第1類屬于計算型任務，對完成時間要求較高;第2類對帶寬要求較高。這兩類的任務的一般期待向量分別為[0.6，0.1，0.3］，[0.3，0.2，0.5］。

模擬的云環境包括4個虛擬機，虛擬機的性能參數如表1所示，10個任務(其中5個為第1類，5個為第2類)。仿真實驗主要考察的3個方面是用戶任務的完成時間，用戶滿意度和各個資源的負載情況。

表1 虛擬機列表

3.2 實驗結果及分析

圖1為任務完成時間對比圖，從圖1中可以看出順序調度、最優完成時間以及EDW-LB這3種算法的對比情況，對于完成時間有較高要求的任務(任務1～5)而言，文中提出的EDW-LB算法的完成時間比順序調度算法以及最優完成時間算法要短，而對于要求帶寬的任務(任務6～10)，EDW-LB算法的完成時間卻不是最短的，這是因為EDW-LB算法需要在滿足任務的帶寬需求的情況下，對任務進行調度。

圖2體現了3種算法的用戶滿意度對比情況，由圖2可以看出:EDW-LB調度算法的用戶滿意度比順序調度算法以及最優完成時間算法優越，也就是說EDW-LB調度算法可以使任務獲得符合其需求的資源。

圖1 任務完成時間對比圖

圖2 用戶滿意度對比圖

考察虛擬機的負載狀態，隨機生成長度在區間[10 000，50 000］的100個任務，虛擬機性能參數如表1所示，進行仿真實驗。

表2是采用3種不同算法時虛擬機的負載狀態，從表2中很容易看出采用順序調度算法各個虛擬機的負載情況，3號虛擬機上的任務長度(指令數)大于1、2、4號虛擬機，然而實驗中所創建的虛擬機綜合性能1號＞2號＞3號＞4號。也就是說，1號虛擬機的性能最好，負載的指令數卻并不是很多。WED-LB調度算法能夠根據虛擬機的性能，控制虛擬機的負載情況。

表2 虛擬機負載情況 byte

4 結論

針對云環境下的任務調度提出了基于加權歐氏距離負載均衡的任務調度算法，該算法使用加權歐氏距離來計算用戶任務和虛擬機之間的相關程度，能夠滿足不同需求的用戶，在得到良好的用戶滿意度同時，通過資源的負載平衡策略提高資源的利用率，盡可能的縮短任務的完成時間。

參考文獻:

[1]吳煜祺，曾國蓀，曾媛.云計算環境下調度算法的趨勢分析[J］.微電子學與計算機，2012，29(9):103-108.

[2]楊麗，武小年，商可旻.一種基于聚類的云計算任務調度算法[J］.大眾科技，2012，14(5):37-39.

[3]趙春燕.云環境下作業調度算法研究與實現[D］.北京:北京交通大學，2009.

[4]朱健琛，徐潔，魯珂.一種類歐氏距離-負載平衡的云任務調度算法[J］.計算機仿真，2012，29(6):159-162.

[5]董旭，魏振軍.一種加權歐氏距離聚類方法[J］.信息工程大學學報，2005，6(1):23-25.

[6]劉瑞元.加權歐氏距離及其應用[J］.數理統計與管理，2002，21(5):17-19.

[7]韓云，于炯，張偉，等.基于負載均衡的任務調度改進算法[J］.微電子學與計算機，2010，27(8):201-204.

[8]丁陽，顏惠琴.基于改進粒子群算法的云計算任務調度策略[J］.無錫職業技術學院學報，2012，11(3):66-68.

[9]李坤.云環境下的任務調度算法研究與實現[D］.長春:吉林大學，2012.

[10]申麗君，劉麗，陸銳，等.基于改進免疫進化算法的云計算任務調度[J］.計算機工程，2012，38(9):208-210.