基于資源組合預測的云計算任務調度算法

李園園武小年,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

基于資源組合預測的云計算任務調度算法

李園園1武小年1,2

（1.桂林電子科技大學信息與通信學院，廣西 桂林 541004；2.廣西無線寬帶通信與信號處理重點實驗室，廣西 桂林 541004）

云計算資源負荷狀態的動態變化，使得如何預測其變化情況，從而合理地實施任務調度，成為亟待解決的問題。針對該問題，提出一種基于資源組合預測的云計算任務調度算法。該模型采用偏最小二乘回歸從各種單一模型的預測結果中提取有效成分，建立組合預測模型；再依據對資源結點的資源預測結果和最小完成時間原則實施任務調度。仿真測試結果表明，該算法具有較好的性能與負載均衡性。

云計算；任務調度；組合預測；偏最小二乘回歸

1 引言

云平臺采用虛擬化技術將集群中的各種資源構成資源池[1]，接收用戶任務請求，并將任務調度到合適的資源上執行。云資源的動態變化，使得如何將用戶任務調度到合適的資源上執行，維護系統的時間跨度性能和負載均衡性能，成為亟待解決的問題。預測是指人們采用一定的技術方法，利用已經掌握的信息，對客觀事物的發展或趨勢做出科學分析[2]。使用預測技術對云資源負荷序列未來的運行狀態進行預測，基于預測結果進行任務調度，可以有效提高系統調度性能。

目前國內外學者提出了很多任務調度算法。文獻[3]基于QoS需求結合Min-Min算法實現任務調度。文獻[4]在研究蟻群算法、任務分配和資源調度的基礎上，提出了一種改進的蟻群資源調度算法，通過引入節點可信度機制在一定程度上增強了云計算資源的搜索能力和節點完成任務的成功率縮短了任務的執行時間。文獻[5]設計了一種基于 GM(1,1)預測和虛擬機遷移的負載均衡策略，有效地實現云計算中心虛擬機集群的負載均衡。

本文提出一種基于資源組合預測的云計算調度算法。該模型分別用趨勢外推模型[6]、時間序列ARIMA模型[7]、GM(1,1)灰色預測模型[8]對資源負荷序列進行預測；然后采用偏最小二乘回歸建立組合預測模型；再基于資源預測結果，以最小完成時間為原則實施任務調度，把任務分配到合適的資源上執行，避免了盲目調度。

2 資源組合預測模型

如何選擇合適的預測模型對云資源負荷序列進行準確預測，是人們一直在探究的問題。單一預測模型并不能符合資源負荷序列的所有特性，具有一定的局限性，其預測精確度有待提高。組合預測模型能夠克服單一預測模型的缺陷，形成優勢互補，最終得到精確度更高的預測結果。本文選取趨勢外推模型、ARIMA模型、GM(1,1)灰色預測模型三種具有不同特點的單一預測模型，采用偏最小二乘回歸建立組合預測模型，對云資源負荷序列進行預測。

偏最小二乘回歸分析是一種新型的多元統計數據分析方法，是多元線性回歸、典型相關分析和主成分分析的集成和發展[9]。在組合預測過程中，各個單一預測模型間可能存在相關性，使組合預測的輸入信息重疊，導致其預測的準確率降低[10]。用偏最小二乘回歸組合預測時提取的成分既能很好地概括自變量系統中的信息，又能最好地解釋因變量，能在樣本個數較少以及自變量存在嚴重多重相關性的條件下進行建模，且模型對實際情況的解釋力更強，提高了組合預測模型的預測精確度。

基于偏最小二乘回歸建立組合預測模型的過程如下：

（1）數據采集：采集n個樣本點數據。

（2）單一模型預測：假設選取 m個單一預測模型對 n個樣本點進行預測，得到的預測值為，Xij(i=1,2,…,n;j=1,2,…,m)這m個單一預測模型對應的預測值設為x1, x2,…, xi, …, xm，以xi作為自變量。設X=(x1, x2,…, xi, …, xm)n×m為自變量集，Y=(y)n×1為因變量集，其中y為n個樣本點實際值。針對上述預測值進行標準化處理，使預測值集合重心與坐標原點重合。令E0為X經標準化后的矩陣，F0為Y標準化后的矩陣。

（3）組合建型：從E0和F0中提取第一成分t1，t1應盡可能多地攜帶X數據變異信息，且t1對Y有最大的解釋能力，其相關程度能夠達到最大；在第一個成分被提取后，以偏最小二乘回歸實施E0對t1的回歸，如果回歸方程已經達到滿意的精度，則算法終止，否則將利用E0被t1解釋后的殘余信息進行第二輪的成分提取；如此往復，直到能達到一個較滿意的精度為止。假設最終對E0共提取了h個成分t1，t2，…, th，則F0對E0的回歸分析即轉化為F0對t1，t2，…, th的多元線性回歸分析，而成分t1，t2，…, th均可由E0線性表示，通過標準化的逆過程，最終得到y對x1, x2,…, xi, …, xm的回歸方程，即為本文的組合預測模型。

3 基于資源組合預測的任務調度算法

為實現有效的云計算環境下的任務調度策略，在任務調度實施之前先對云環境中的計算資源的使用狀況進行預測，根據預測結果為任務篩選滿足需求的資源，最后根據最小完成時間原則進行資源和任務的綁定，實施任務調度。

本文算法過程描述如下：

（1）基于上述建立的預測模型，對資源狀態進行預測，并將預測結果更新到資源集合列表中，用于任務調度時的依據；

（2）分別對任務集合和資源集合的相關屬性進行歸一化；

（3）初始化ETC和MCT矩陣；

（4）對任務 Ti，將所有滿足其需求的資源即，作為候選資源。按照任務所含符合其要求的資源個數的多少進行升序排列，即對于候選資源少的任務優先調度；

（5）將任務列表中排序最靠前的任務Ti分配到其候選資源中使其完成時間最小的資源上，建立任務-資源映射列表；

（6）刪除任務Ti，更新MCT矩陣；

（7）反復執行(5)-(6)，直到任務列表或MCT矩陣為空為止；

（8）任務調度。按照任務-資源映射關系，完成任務調度。

4 仿真實驗及結果分析

4.1實驗設置

本文在實驗室計算資源節點上采集CPU使用率和內存使用率數據并進行預測，資源組合預測模型基于MATLAB 7.8.0軟件平臺實現。依據資源預測結果，以最小完成時間為原則在CloudSim仿真平臺下進行任務調度。在仿真實驗中，測試了本文算法進行任務調度的時間跨度和負載均衡，并與Min-Min算法進行了對比。

4.2實驗結果與分析

（1）實驗一：完成時間跨度測試。

完成時間跨度（Makespan）指用戶提交的所有任務都執行完畢的時間。Makespan值越小，表示任務完成的速度越快，系統的調度性能越好。該值作為調度算法評價指標之一，具有很強的參考性。

對Min-Min算法和本文算法在40個虛擬機上針對400、800、1200和1600個任務進行完成時間跨度性能測試，測試結果如圖1所示。

圖1　完成時間跨度測試結果

從圖1可以看出，當任務數在400到1600之間變化時，本文算法在時間跨度性能上均優于Min-Min算法。

（2）實驗二：負載均衡測試。

負載均衡（Load balances）：虛擬機負載情況使用相對標準差（Relative Standard Deviation,RSD）表示。，其中是樣本標準偏差，表示樣本參數的離散程度。是樣本均值。使用相對標準差能較好的說明一組數據的分散程度，反應出所有虛擬機的負載均衡情況。

對Min-Min算法和本文算法在40個虛擬機上針對400、800、1200和1600個任務進行負載均衡性能測試，測試結果如圖2所示。

圖2　負載均衡測試結果

從圖2可以看出，當任務數在400到1600之間變化時，本文算法在負載均衡性能上均優于Min-Min算法。隨著任務數的增加，本文算法的負載均衡性能相對趨于穩定，而Min-Min算法則隨著任務數的增加其負載均衡性能表現出降低的趨勢。以上分析可知，本文算法具有較優的負載均衡性能。

5 結束語

本文提出一種基于資源組合預測的云計算調度算法。該算法先分別用ARIMA模型、趨勢外推法、灰色預測GM(1,1)模型進行云資源預測；然后采用偏最小二乘回歸建立組合預測模型，偏最小二乘回歸能夠有效消除各個模型多重相關性在組合建模時的不良作用，提高預測精確度；最后基于資源預測結果，以最小完成時間為原則實施任務調度。該任務算法通過資源預測，把任務分配到合適的資源上執行，避免了盲目調度。實驗測試結果表明，該算法具有更好的性能和負載均衡性。

[1] Buyya R, Yeo C,Venugopal S.Market-oriented Cloud Computing: Vision, Hype, and Reality for Delivering It Services as Computing Utilities[J].High Performance Computing and Communications,2008: 25-27.

[2] (美)Shmueli,G.時間序列預測[M].北京:清華大學出版社,2012.

[3] XiaoShan He,Xianhe Sun and Gregor von Laszewski. QoS guided Min-Min heuristic for grid task scheduling[J]. Journal of Computer Science and Technology, 2003,18(4): 442-451.

[4] 余星,胡德敏,黃超.云計算資源調度算法的研究與實現[J].信息技術,2013,(11):29-32.

[5] 王志勃,畢艷茹.基于 GM (1,1)預測和虛擬機遷移的云計算負載均衡策略設計[J].計算機測量與控制,2014,(11): 089.

[6] Boel B,Michael P V, Anders H.Prediction of glaucoma-tous visual field loss by extrapolation of linear trends[J]. Archives of Ophthalmology,2009,127(12):1610-1615.

[7] 潘迪夫,劉輝,李燕飛.風電場風速短期多步預測改進算法[J].中國電機工程學報,2008,28(26): 87-91.

[8] 謝乃明,劉思峰.離散GM(1,1)模型與灰色預測模型建模機理[J].系統工程理論與實踐,2005,(25):93-98.

[9] 王文圣,丁晶,趙玉龍,等.基于偏最小二乘回歸的年用電量預測研究[J].中國電機工程學報,2003,23(10): 17-21.

[10] Yang Y H. Combining forecasting procedures:some theoretical results[J]. Econometric Theory, 2004, 20(1):176-222.

The task scheduling algorithm based on resources combination forecast in cloud computing

Due to the dynamic changes of cloud resources load conditions, it has been an urgent problem how to predict its changes and execute task scheduling reasonably. Aiming at the problem, this paper proposes a task scheduling algorithm based on resources combination forecast in cloud computing. Using the partial least square regression method, the model is set up by extracting the active components from the predicted results of single forecast models. Then, according to the predicted results of the resources node and the principle of minimum completion time task scheduling is completed. The simulation tested results demonstrate that the performance of this algorithm is good, and the load balancing performance is stable.

Cloud computing; task scheduling; combination forecast; partial least square regression

TP393

A

1008-1151(2015)04-0027-03

2015-02-13

廣西自然科學基金(2012GXNSFAA053224)；廣西無線寬帶通信與信號處理重點實驗室開放基金項(GXKL0614110)。

李園園（1989-）女，廣西桂林人，桂林電子科技大學信息與通信學院碩士研究生，研究方向為信息安全；武小年（1972-）男，湖北監利人，桂林電子科技大學副教授，碩士，研究方向為信息安全和分布式計算。