基于改進(jìn)蟻群算法的QoS 約束云任務(wù)調(diào)度

丁 智

(揚(yáng)州職業(yè)大學(xué)，江蘇 揚(yáng)州 225009)

云環(huán)境下任務(wù)調(diào)度具有不同的目標(biāo)需求［1］，大多數(shù)調(diào)度算法集中在工作流調(diào)度和獨(dú)立任務(wù)調(diào)度，而以工作流任務(wù)和獨(dú)立任務(wù)混合的形式提交任務(wù)，稱之為部分相關(guān)任務(wù)。調(diào)度策略主要分為以性能、QoS 和效益為中心。云環(huán)境下任務(wù)調(diào)度是一大研究熱點(diǎn)，有人提出一種概率相關(guān)的優(yōu)先級(jí)算法，執(zhí)行獨(dú)立任務(wù)使用較少的計(jì)算資源［2］。也有人提出兩種用于私有云的任務(wù)調(diào)度算法，實(shí)現(xiàn)較少的完成時(shí)間［3］。還有一些啟發(fā)式算法也被用于基于QoS 的任務(wù)調(diào)度［4］。有文獻(xiàn)提出一種云環(huán)境下多QoS 約束的服務(wù)工作流調(diào)度方法［5］。此外，還有人提出了基于負(fù)載均衡的蟻群優(yōu)化算法用于云應(yīng)用調(diào)度［6］。然而，大多數(shù)研究沒有考慮QoS 約束的任務(wù)期限。為了有效地進(jìn)行部分相關(guān)任務(wù)調(diào)度，本文提出了一種滿足服務(wù)質(zhì)量(QoS)約束的調(diào)度模型，并將改進(jìn)的蟻群優(yōu)化算法(ACO +)用于云環(huán)境下部分相關(guān)任務(wù)調(diào)度。

1 云任務(wù)調(diào)度模型

由于云任務(wù)調(diào)度研究主要集中在獨(dú)立任務(wù)調(diào)度和工作流任務(wù)調(diào)度，缺乏對(duì)部分相關(guān)任務(wù)調(diào)度的研究。因此，在研究部分相關(guān)任務(wù)調(diào)度模型的基礎(chǔ)上，提出滿足QoS 約束的部分相關(guān)任務(wù)調(diào)度模型。部分相關(guān)任務(wù)模型通常被視為一個(gè)有向無環(huán)圖(DAG)，其中V={T1，T2，…，Tn}代表任務(wù)集合，E 代表任務(wù)之間的依賴關(guān)系，即若＜Tj，Tk＞∈E(j，k=1，2，…，P)，則Tj→Tk，Tj是Tk的先驅(qū)節(jié)點(diǎn)。圖1 是一個(gè)簡(jiǎn)單的工作流實(shí)例。

圖1 工作流

部分相關(guān)任務(wù)在一組計(jì)算資源VM ={VM1，VM2，…，VMnv}上執(zhí)行，ExeTimei為執(zhí)行時(shí)間，Lengthi為任務(wù)i 的長(zhǎng)度，Mipsj為虛擬機(jī)j 的單字長(zhǎng)定點(diǎn)指令平均執(zhí)行速度。TranTime 為通信時(shí)間，Comij為標(biāo)志位，maxTransfRate 為最大傳輸速率，Oputj為輸出信息量。

為了滿足服務(wù)質(zhì)量約束，F(xiàn)inishTimei需滿足式(4)，F(xiàn)inishTimei為任務(wù)Ti的完成時(shí)間，混合任務(wù)集中的每個(gè)任務(wù)Ti都必須滿足QoS 約束的截止時(shí)間，記為QoSi。

2 改進(jìn)ACO 的任務(wù)調(diào)度算法

蟻群算法是受自然界真實(shí)蟻群的集體覓食行為啟發(fā)用于解決各種組合優(yōu)化問題的隨機(jī)搜索方法。蟻群算法基于stigmergy 思想［7］，成員與群體之間通過環(huán)境的相互作用間接地溝通。

本文采用蟻群算法的思想將部分相關(guān)任務(wù)作為蟻群分配任務(wù)。為了得到更好的部分相關(guān)任務(wù)完成時(shí)間，把部分相關(guān)任務(wù)劃分成多個(gè)子群。AveMips 是對(duì)所有虛擬機(jī)的MIPSS 取平均值［8］。minTime 是工作流任務(wù)根節(jié)點(diǎn)的最小執(zhí)行時(shí)間，maxTime 是工作流任務(wù)輸出節(jié)點(diǎn)的最大執(zhí)行時(shí)間。

本文采用改進(jìn)的蟻群算法解決云環(huán)境下的部分相關(guān)任務(wù)調(diào)度問題。算法中每只螞蟻代表可分配的虛擬機(jī)。啟發(fā)因子ηm，i，j表示任務(wù)Ti被分配給虛擬機(jī)VMj的期望程度，用式(7)表示，其中NV 代表虛擬機(jī)數(shù)量。Pm，i，j代表任務(wù)Ti被分配給虛擬機(jī)VMj處理的概率。

在不同的虛擬機(jī)分配策略下，任務(wù)Ti被分配給虛擬機(jī)VMj執(zhí)行同樣會(huì)增加該任務(wù)被分配給該虛擬機(jī)信息素，若仍然用τm，i，j來表示改進(jìn)蟻群算法中的信息素，則信息素的更新策略為:(1)當(dāng)子群中所有任務(wù)都在規(guī)定時(shí)間內(nèi)完成，則信息素根據(jù)式(9)進(jìn)行更新［9］;(2)當(dāng)子群中的任務(wù)沒有在規(guī)定時(shí)間內(nèi)完成，則信息素根據(jù)式(10)進(jìn)行更新;(3)當(dāng)所有的任務(wù)都在規(guī)定時(shí)間內(nèi)完成，信息素根據(jù)式(11)進(jìn)行更新。其中ρ(0 ＜ρ ＜1)是信息素的衰變參數(shù)，Δτm，i，j是選擇信息素的增量，見式(12)。

當(dāng)子群中所有的任務(wù)都在規(guī)定時(shí)間內(nèi)完成，則虛擬機(jī)處于空閑狀態(tài)，此時(shí)需要增加信息素增量Δτm，i，j來吸引其他任務(wù)在該虛擬機(jī)上執(zhí)行;而子群中的任務(wù)沒有在規(guī)定時(shí)間完成，則虛擬機(jī)處于忙的狀態(tài)，此時(shí)需要通過減少信息素來使其他任務(wù)選擇其他虛擬機(jī)執(zhí)行。

3 實(shí)驗(yàn)與分析

為了評(píng)估改進(jìn)蟻群算法在云環(huán)境下任務(wù)調(diào)度的性能，借助云仿真器CloudSim［10］中已有的算法對(duì)滿足QoS 約束的部分相關(guān)任務(wù)進(jìn)行調(diào)度，并比較分析。已知云仿真器中已有的算法已經(jīng)將任務(wù)流按特定順序排序，并對(duì)分配到相同虛擬機(jī)上的任務(wù)優(yōu)先執(zhí)行QoS 約束較弱的任務(wù)。

3.1 CloudSim 仿真流程

圖2 描述了CloudSim 的仿真流程，包括創(chuàng)建datacenter 資源，datacenter 向CIS 進(jìn)行注冊(cè)，當(dāng)有請(qǐng)求時(shí)，CIS 根據(jù)請(qǐng)求從列表中選擇合適的云服務(wù)提供商提返回用戶，然后由DatacenterBroker 負(fù)責(zé)信息交互的過程。

圖2 CloudSim 仿真流程

將改進(jìn)的蟻群算法和改進(jìn)的粒子群算法在CloudSim 仿真器上進(jìn)行試驗(yàn)，并應(yīng)用于求解PDTs任務(wù)調(diào)度模型。本實(shí)驗(yàn)采用計(jì)算機(jī)操作系統(tǒng)為Windows 7、CPU 2.66GHz、內(nèi)存2G，硬盤250GB。虛擬機(jī)所需設(shè)置的參數(shù)包括虛擬機(jī)ID、MIPS、存儲(chǔ)空間、帶寬、開銷等，微軟Windows Azure 平臺(tái)提供了5 種規(guī)格的虛擬機(jī)，選取前3 種，見表1。

表1 虛擬機(jī)參數(shù)表

3.2 實(shí)驗(yàn)數(shù)據(jù)

在云仿真器中，改進(jìn)的蟻群算法通過修改Datacenter Broker 類、Cloudlet 類以及Datacenter類來實(shí)現(xiàn)，表2 描述了PDTs 任務(wù)的參數(shù)設(shè)置。

表2 中Cloudlet0 -Cloudlet14 分別對(duì)應(yīng)任務(wù)T1到T15，并給出了滿足QoS 限制的獨(dú)立任務(wù)的截止時(shí)間和工作流任務(wù)集合的截止時(shí)間，則所有任務(wù)的截止時(shí)間集合Set1 ={510，78，420，1250，1250，1250，1250，1250，1250，1250，1250，1350，190，1350，1350}為QoS1。并對(duì)改進(jìn)的蟻群算法的相關(guān)參數(shù)設(shè)置如下:α=0.6，β=0.6，ρ=0.7。

表2 PDTs 任務(wù)參數(shù)表

3.3 實(shí)驗(yàn)結(jié)果分析

統(tǒng)計(jì)不同方法任務(wù)分配到虛擬機(jī)上執(zhí)行的完成時(shí)間，并對(duì)云仿真器中已有的分配算法和蟻群算法、滿足QoS 約束的任務(wù)相比較，任務(wù)完成時(shí)間見圖3。

圖3 各算法的任務(wù)完成時(shí)間

從圖3 中可以看出，蟻群算法大部分任務(wù)都無法滿足QoS 約束;仿真器中已有的算法對(duì)任務(wù)進(jìn)行調(diào)度時(shí)，任務(wù)號(hào)1 和任務(wù)號(hào)12 也不能很好地滿足QoS 約束。

而采用改進(jìn)的蟻群算法對(duì)部分相關(guān)任務(wù)調(diào)度模型進(jìn)行調(diào)度時(shí)，將得到的完成時(shí)間與QoS 約束相比較，混合任務(wù)流中的所有任務(wù)都能滿足QoS約束，見圖4。從圖3 和圖4 可知，本文提出的改進(jìn)蟻群算法與仿真器中已有的算法以及原有的蟻群算法相比能有效地滿足QoS 約束。

圖4 ACO+算法任務(wù)完成時(shí)間

為了測(cè)試數(shù)據(jù)的有效性，本文在QoS 約束集Set1 的基礎(chǔ)上，進(jìn)行另一組QoS 約束實(shí)驗(yàn)，QoS 約束條件的截止時(shí)間集Set2 = {1350，1350，68，1250，1250，1250，1250，1250，1250，1250，1250，1350，320，650，850}，即QoS2，完成時(shí)間見圖5。

圖5 ACO+算法任務(wù)完成時(shí)間

從圖4 和圖5 可以看出改進(jìn)的蟻群算法能夠很好地解決云環(huán)境下混合任務(wù)模型部分相關(guān)任務(wù)的調(diào)度問題，并保證任務(wù)的QoS 約束。

4 結(jié)論

根據(jù)改進(jìn)的蟻群算法將部分相關(guān)任務(wù)分配給虛擬機(jī)，并根據(jù)不同的參數(shù)測(cè)試改進(jìn)蟻群算法性能。實(shí)驗(yàn)結(jié)果表明改進(jìn)的蟻群算法具有較高的收斂性和尋優(yōu)能力，適用于云環(huán)境下任務(wù)調(diào)度。本文對(duì)混合任務(wù)模型分析時(shí)只設(shè)置了一個(gè)輸入和一個(gè)輸出，任務(wù)調(diào)度的輸入輸出過程相對(duì)簡(jiǎn)單，在處理獨(dú)立任務(wù)和工作流任務(wù)的過程中，考慮了每個(gè)獨(dú)立任務(wù)的截止時(shí)間，沒考慮整個(gè)工作流中間過程的截止時(shí)間。

［1］ ZHANG Z，ZHANG X. A load balancing mechanism based on ant colony and complex network theory in open cloud computing federation［C］//Proceedings of the 2nd International Conference on Industrial Mechatronics and Automation. Piscataway:IEEE，2010.

［2］ ZHU L，LI Q，HE L. Study on cloud computing resource scheduling strategy based on the ant colony optimization algorithm［J］. IJCSI International Journal of Computer Science Issues，2012，9(5):54 -58.

［3］ NISHANT K，SHARMA P，KRISHNA V，et al. Load balancing of nodes in cloud using ant colony optimization［C］//Computer Modelling and Simulation，2012 UKSim 14th International Conference on. IEEE，2012.

［4］ YAN HUA Z，LEI F，ZHI Y. Optimization of cloud database route scheduling based on combination of genetic algorithm and ant colony algorithm［J］. Procedia Engineering，2011(15):3341 -3345.

［5］ MISHRA R，JAISWAL A. Ant colony optimization:A solution of load balancing in cloud［J］. International Journal of Web ＆ Semantic Technology，2012，3(2):33 -50.

［6］ LIU X，CHEN J，WU Z，et al. Handling recoverable temporal violations in scientific workflow systems:a workflow rescheduling based strategy［C］//Proceedings of the 2010 10th IEEE/ACM International Conference on Cluster，Cloud and Grid Computing. IEEE Computer Society，2010.

［7］ LIU H，XU D，Miao H K. Ant colony optimization based service flow scheduling with various QoS requirements in cloud computing［C］//Software and Network Engineering，2011 First ACIS International Symposium on. IEEE，2011.

［8］ CHIMAKURTHI L. Power efficient resource allocation for clouds using ant colony framework［J/OL］. arXiv preprint arXiv:1102.2608，2011.

［9］ ENDO P T，DE ALMEIDA PALHARES A V，PEREIRA N N，et al. Resource allocation for distributed cloud:concepts and research challenges［J］. IEEE，2011，25(4):42 -46.

［10］CALHEIROS R N，RANJAN R，BELOGLAZOV A，et al. CloudSim:a toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］. Software:Practice and Experience，2011，41(1):23 -50.