任金霞,何富江

（江西理工大學(xué)電氣工程與自動化學(xué)院，江西贛州341000）

快速降階匈牙利算法的云計算任務(wù)分配模型

任金霞,何富江

（江西理工大學(xué)電氣工程與自動化學(xué)院，江西贛州341000）

為了提高云計算任務(wù)分配效率，在標準匈牙利算法的基礎(chǔ)上，提出一種快速降階優(yōu)化算法的云計算任務(wù)分配模型.為實現(xiàn)快速求解全局任務(wù)分配問題，快速降階算法不斷排除已確定的分配方案對應(yīng)的代價矩陣元素，從而快速降低矩陣的階次.并可根據(jù)成本矩陣規(guī)模將矩陣分解成多個矩陣，使得該算法在任務(wù)和計算機不對等的情況下同樣適用.論文最后的仿真結(jié)果表明，快速降階匈牙利算法計算耗時遠遠小于匈牙利算法，并能有效提高計算機的利用率.

云計算；任務(wù)分配；降階；匈牙利算法

云計算[1]是由一個巨大的虛擬化[2]軟件資源庫組成，它只需通過網(wǎng)絡(luò)就能訪問和使用分散在各地的虛擬軟件和資源服務(wù)[3].

可以這樣總結(jié)云計算資源分配[4]的過程：設(shè)有m臺計算機要處理n個云計算任務(wù)，已知在任一計算機上運行任一的云計算任務(wù)所需的花費不同，任務(wù)分配的目的就是尋找到一個既能順利處理完所有任務(wù)又能使得成本最小的方案.

當(dāng)前任務(wù)分配方法[5]算法復(fù)雜，準確性低，且收斂速度會隨著程序運行時間的增加而降低.為了保證任務(wù)分配的效率，提出了基于匈牙利算法的快速降階云計算任務(wù)分配模型[6]，達到迅速收斂的目的.

1 匈牙利算法及其思想

匈牙利算法常用于標準的指派問題，例如：m個工件要在n臺車床上加工,每個工件在每臺車床上加工時成本不同，最優(yōu)任務(wù)分配問題就是指如何使得任務(wù)分配結(jié)果的總成本最低.

定理1如果從成本矩陣C=（cjk）n×n的每一行分別減去(加上)一個常數(shù)uj，從每一列分別減去(加上)一個常數(shù)vk,得到一個新的成本矩陣C*=（c*jk）n×n,若其中c*jk=cjk-uj-vk，則二者的最優(yōu)解等價.

定理2將矩陣C的所有元素劃為0和非0兩類，可得位于不同行和列的0元素最大個數(shù)等于經(jīng)過0元素最少的直線數(shù).

為了使新的代價矩陣中含有更多的0元素,在尋找最優(yōu)解的過程中，利用定理1不斷變換原代價矩陣.為了求解最小的總代價，矩陣（c*jk）n×n中找出n個目標函數(shù)中代價為z*=0的獨立的0元素，選中的獨立0元素對應(yīng)原來的（c*jk）n×n的元素組合為原分配問題最優(yōu)解.因此原分配問題最優(yōu)解為選中的獨立0元素相對應(yīng)的原代價矩陣（c*jk）n×n的元素的組合.

2 標準的匈牙利任務(wù)分配模型

標準的匈牙利算法是任務(wù)和計算機一對一的調(diào)度，即任務(wù)數(shù)量等于計算機數(shù)量，其任務(wù)分配問題模型是：如果n臺計算機要執(zhí)行n個任務(wù)，現(xiàn)假設(shè)已經(jīng)計算出第j個云計算任務(wù)在第k臺計算機執(zhí)行的成本，要求以最小的成本完成總的云計算任務(wù)，并且必須滿足一下條件：每個任務(wù)都會被執(zhí)行；且沒有空閑的計算機，即保證負載的均衡[7].

引入成本矩陣及任務(wù)分配矩陣,矩陣X=（xjk）n×n為任務(wù)分配問題的成本矩陣，cjk為任務(wù)分配結(jié)果：

因此云計算任務(wù)分配問題的數(shù)學(xué)模型可以描述為：

限制條件為：

式中,限制條件（4）要求每臺計算機至少運行一個云任務(wù)；限制條件（5）要求每個云任務(wù)都要運行；限制條件（6）要求分配結(jié)果元素值取0或1.且表示的含義如下：

匈牙利算法在化簡過程中對成本矩陣或分配矩陣進行多次迭代，達到行列縮減處理的目的，但效率卻不高，因為常常進行了新的一次迭代卻沒有增加有效的零位.因此在結(jié)合匈牙利算法的基礎(chǔ)上,提出了一種求解指派問題的快速優(yōu)化算法——降階優(yōu)化算法.

3 快速降階優(yōu)化算法

式中l(wèi)為

X1的0元素不再進行優(yōu)化分配.此時E1已轉(zhuǎn)化為求解（n-1）個計算機對（n-1）個任務(wù)的分配問題,分配矩陣降為（n-1）階,稱之快速降階.

同理

上式的l為

X2的0元素不再進行優(yōu)化分配,E2也轉(zhuǎn)化為求解（n-1）臺計算機對（n-1）個任務(wù)的分配問題，即：E1和E2是2個低一階分配問題的最優(yōu)解,對應(yīng)的成本矩陣為X1和X2.

若要使得最終分即：已確定降為（n-1）階后對應(yīng)分配方案的值，

有

反之，若想得到最大成本分配方案，則選擇式（8）中clt=1為分配方案的部分解，并剔除其對應(yīng)的行列，成本矩陣降低一階.重復(fù)上述步驟，成本矩陣規(guī)模不斷減小，僅有一個元素時得到最優(yōu)分配方案.

針對匈牙利算法只能求解標準一對一分配問題的不足，在任務(wù)和資源不對等的情況下做了一些改進，再按照已設(shè)計的降階優(yōu)化方法進行成本最小的任務(wù)分配，具體流程如圖1.

圖1 快速降階匈牙利算法流程圖

從流程圖可以看出，針對計算機和任務(wù)不匹配的情況，將矩陣拆分，且循環(huán)n-1次就能得到n階矩陣分配問題的最優(yōu)解.

其中矩陣的降階操作為算法的核心部分，首先將矩陣每一個元素代入公式（8）找出最大值所在行l(wèi)，將已確定l的值代入公式（7）得到xlm，并將xlm所在行列其他元素置0，而后依次代入式（9）、式（10）、式（11）、式（12），此時矩陣降為（n-1），降階過程結(jié)束.

4 算法舉例

現(xiàn)假設(shè)有3臺計算機p1、p2、p3,16個云仿真任務(wù)R1、R2、R3、R4、R5、R6、R7、R8、R9、R10、R11、R12、R13、R14、R15、R16，他們完成各個任務(wù)的成本已經(jīng)給出如表1.

表1 不同計算機對應(yīng)不同任務(wù)的成本

將表1轉(zhuǎn)化為成本矩陣，并將其分解為矩陣A、B、C、D、E、F,即：

由于矩陣F是3×1的矩陣，現(xiàn)以虛擬任務(wù)(添0)補足，即：

對矩陣A進行降階優(yōu)化操作

對矩陣B進行降階優(yōu)化操作

對矩陣C進行降階優(yōu)化操作

對矩陣D進行降階優(yōu)化操作

對矩陣E進行降階優(yōu)化操作

對矩陣F進行降階優(yōu)化操作

最終任務(wù)分配結(jié)果為：

即：任務(wù)R2、R6、R9、R10、R14在計算機P1執(zhí)行；任務(wù)R1、R5、R7、R11、R15、R16在計算機P2執(zhí)行；任務(wù)R3、R4、R8、R12、R13在計算機P3執(zhí)行.

5 仿真實驗與分析

5.1 算法耗時比較

算法通過M atlab程序，對降階優(yōu)化算法與經(jīng)典的匈牙利算法的效率進行對比和分析.

在實驗中，采用Rand函數(shù),自動生成隨機矩陣,然后應(yīng)用兩種算法計算n×n的隨機矩陣,并記錄每次所消耗的時間，為了減少誤差,重復(fù)多次取平均值,用縱軸表示時間，橫軸表示矩陣維數(shù)，如圖2.

圖2 兩種算法運行時間比較

通過比較圖2兩種算法，得出以下結(jié)論：快速降階優(yōu)化算法在耗時上遠低于標準匈牙利算法，特別是處理50×50階內(nèi)任務(wù)分配問題時，在50×50階之后，兩種算法耗時都在顯著增加，但快速降解算法由于需要行內(nèi)元素互減計算量加大，斜率明顯變大.兩種算法耗時如表2.

表2 算法耗時比較/s

通過以上分析，可知快速降階匈牙利算法相對于匈牙利算法所節(jié)省的時間主要源于以下兩個方面:

（1）快速降解的匈牙利算法每運行一次，矩陣規(guī)模便降一階，每降一階便減少了n×（n-1）次運算，而匈牙利算法則需要多次循環(huán)比較之后才能對矩陣行列進行刪劃.

（2）匈牙利算法在對矩陣行列進行刪劃之后，還要進行多次迭代，以期出現(xiàn)跟多零位,但是零位往往沒有增加，而快速降階算法有效避免了無法出現(xiàn)更多零位的循環(huán)迭代.

5.2 算法負載率的比較

綜合云計算系統(tǒng)的結(jié)構(gòu)特征，將系統(tǒng)負載率作為衡量資源利用率的重要指標，資計算機的負載率計算公式如下：

其中：this.MI為計算機的利用率，n為計算機總數(shù)，systhis.MI為系統(tǒng)總的利用率.

求解云計算任務(wù)分配問題的算法的算法有許多，通過蟻群算法[5，9-11]，F(xiàn)IFO（先入先出）與快速降階算法進行對比，結(jié)果如圖3.

圖3 三種算法負載率對比

由圖3可知，F(xiàn)IFO算法對計算機的負載率最大，其次是蟻群算法[9，12-13]，快速降階優(yōu)化算法負載率最小.

原因分析：快速降階算法求解分配問題的計算過程中，每次循環(huán)都在獲解局部最優(yōu)解，并逐步縮小可行范圍，最終求得全局最優(yōu)解；而蟻群算法由于自組織性、正反饋性、分布式計算的特性，容易陷入局部最優(yōu)解；FIFO算法則沒有考慮到任務(wù)量以及和計算機的匹配程度，導(dǎo)致負載率高.

6 結(jié)論

結(jié)合云計算的特征，根據(jù)資源分配和匈牙利算法特點，提出了快速降階云計算任務(wù)分配策略，在求解全局最優(yōu)解的同時能夠快速收斂，對算法進行了相應(yīng)的仿真，可達到縮短求解時間、降低負載率、提高計算機利用率的效果.

[1]劉鵬.云計算[M].2版.北京:電子工業(yè)出版社,2011.

[2]肖斐.虛擬化云計算中資源管理的研究與實現(xiàn)[D].西安：西安電子科技大學(xué),2010.

[3]Beloglzov A,Buyya R.Adaptive threshold based approach for energy-efficient consoli dation of virtual machines in cloud data centers[C]//Proceedings of the 8th International Workshop on Middleware for Grids,Clouds and eScience,New York：USA ACM Press,2010.

[4]AMMBRUST M,FOX A,GRIFFITH R,et al.A view of cloud computing[J].Communications of the ACM,2010,53(4):50-58.

[5]邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計算方法[M].北京:清華大學(xué)出版社, 2003.

[6]陳艷金.Mapreduce模型在Hadoop實現(xiàn)中的性能分析及改進優(yōu)化[D].成都:電子科技大學(xué),2010.

[7]田浪軍,陳衛(wèi)衛(wèi),陳衛(wèi)東，等.云存儲系統(tǒng)中動態(tài)負載均衡算法研究[J].計算機工程,2013,39(10):19-23.

[8]Ge Yujia,Wei Guiyi.GA-based Task Scheduler for the Cloud Computing Systems[C]//Proc.of 2010 International Conference on Web Information Systems and Mining.Sanya,China:[s.n.],2010: 181-186.

[9]范杰,彭艦,黎紅友.基于蟻群算法的云計算需求彈性算法[J].計算機應(yīng)用,2011,31(1):1-7.

[10]雷葆華,饒少陽,江峰,等.云計算機解碼:技術(shù)架構(gòu)和產(chǎn)業(yè)運營[M].北京:電子工業(yè)出版社,2011.

[11]段海濱,張祥銀,徐春芳.仿生智能計算[M].北京：科學(xué)出版社, 2011.

[12]Calheiros R N,Ranjan R,Beloglazov A,et al.CloudSim:A Tookit for Modeling and Simulation of Cloud Computing Environments and Evaluation of Resource Provisioning Algorithms[J].Software: Practice and Expericence,2011,41(1):23-50.

[13]陳真.改進蟻群算法在云環(huán)境下路徑優(yōu)化設(shè)計[J].江西理工大學(xué)學(xué)報,2012,33(3):66-70.

Task assignment model in cloud computing based on Hungary algorithm of faster reduced order

REN Jin-xia,HE Fu-jiang

（School of Electrical Engineering and Automation,Jiangxi University of Science and Technology,Ganzhou 341000,China）

In order to improve the efficiency of task allocation in cloud computing,on the basis of standard Hungary algorithm,this paper puts forward a task allocation model in cloud computing using fastreduced order optimization algorithm.To solve all task allocation problem fast,the algorithm constantly rules out corresponding matrix elements in the allocation plan,and thus the order of the matrix is quickly reduced.And the matrix is decomposed into multiple matrixes according to the size of cost matrix,which makes the algorithm also applicable in the uncoordinated case of tasks and computer.The final simulated results ofthe paper show that Hungary algorithm in the fast reduced order costs far less time than that of Hungarian algorithm,and the former improves the utilization of the computer.

cloud computing;task assignment;reduced order;Hungary algorithm

TP393

A

2095-3046（2014）03-0063-05

10.13265/j.cnki.jxlgdxxb.2014.03.012

2014-05-23

國家自然科學(xué)基金資助項目(61262013)

任金霞（1970-），女，副教授，主要從事智能優(yōu)化算法及應(yīng)用等方面的研究；E-mail：6201424@qq.com.