范 穎 沈建京

1(鄭州信息科技職業(yè)學(xué)院 河南 鄭州 450008) 2(中國人民解放軍戰(zhàn)略支援部隊(duì)信息工程大學(xué) 河南 鄭州450008)

0 引 言

云計(jì)算是一種可以提供靈活的按需基礎(chǔ)架構(gòu)的新興計(jì)算范例，它以平臺(tái)和軟件作為服務(wù)。通常有三種云模型：SaaS(軟件服務(wù))、PaaS(平臺(tái)服務(wù))和IaaS(基礎(chǔ)架構(gòu)服務(wù))[1]。云計(jì)算調(diào)度過程是決定各種可能的工作/任務(wù)之間資源分配的概念，根據(jù)資源的最佳分配和實(shí)現(xiàn)良好的服務(wù)質(zhì)量(Quality of Service，QoS)的需要，將這些任務(wù)分配給適當(dāng)?shù)馁Y源[2]，而最佳資源分配加入云計(jì)算配合后，能夠大幅提升QoS。在云計(jì)算中，不同的虛擬機(jī)(Virtual machines,VM)可以處理和調(diào)度來自不同用戶的獨(dú)立任務(wù)，以實(shí)現(xiàn)資源利用率的最大化。由于異構(gòu)資源的不同任務(wù)特征和動(dòng)態(tài)特性，任務(wù)調(diào)度被稱為NP完全問題[3]。在此過程中，任務(wù)調(diào)度程序從用戶接收任務(wù)并將其映射到可用資源，同時(shí)考慮任務(wù)的特征和資源的參數(shù)。因此，有效的最優(yōu)任務(wù)調(diào)度算法應(yīng)該通過實(shí)現(xiàn)資源的高效利用和最大利潤以及高性能計(jì)算來考慮系統(tǒng)負(fù)載平衡[4]。

已有的研究已經(jīng)應(yīng)用了幾種啟發(fā)式算法來應(yīng)對(duì)云計(jì)算中任務(wù)調(diào)度的挑戰(zhàn)。文獻(xiàn)[5]制定了任務(wù)調(diào)度模型，提出了一種基于小位置值規(guī)則的粒子群優(yōu)化算法，以最大限度地降低處理成本。通過將交叉和變異嵌入的PSO算法(Embedded crossing and variation PSO,ECV-PSO)與本地研究中的PSO算法與PSO算法進(jìn)行比較，結(jié)果表明PSO算法的大規(guī)模收斂速度更快，更適合云計(jì)算。文獻(xiàn)[6]提出了一種基于蟻群優(yōu)化算法的云任務(wù)調(diào)度策略，用于負(fù)載均衡，工作的主要貢獻(xiàn)是在嘗試最小化給定任務(wù)集的完成時(shí)間時(shí)平衡系統(tǒng)負(fù)載，并提出了與作業(yè)完成率相關(guān)的負(fù)載均衡因子，以提高負(fù)載均衡的能力。文獻(xiàn)[7]提出了一種用于云計(jì)算中工作負(fù)載調(diào)度的單目標(biāo)PSO算法。PSO算法與不同的慣性權(quán)重策略相結(jié)合，以最小化完成時(shí)間。結(jié)果表明，PSO結(jié)合線性降低的慣性重量(Linearly decreasing inertia weight,LDIW-PSO)可以獲得更好的性能并改善完成時(shí)間。文獻(xiàn)[8]為單用戶工作引入一種改進(jìn)的遺傳算法，其中開發(fā)適應(yīng)性以鼓勵(lì)形成解決方案以最小化執(zhí)行時(shí)間和執(zhí)行成本。實(shí)驗(yàn)結(jié)果表明，在重載下，該算法表現(xiàn)出良好的性能。文獻(xiàn)[9]提出了一種稱為正交貓群優(yōu)化算法(Orthogonal Taguchi based-cat swarm optimization,OTB-CSO)來最小化總?cè)蝿?wù)執(zhí)行時(shí)間，探索了Taguchi優(yōu)化方法的局部搜索能力，通過實(shí)現(xiàn)最小完成時(shí)間來提高收斂速度和解決方案的質(zhì)量。實(shí)驗(yàn)結(jié)果表明，OTB-CSO可有效優(yōu)化任務(wù)調(diào)度，提高整體云計(jì)算性能。以上研究已經(jīng)從各個(gè)方面為云計(jì)算中的調(diào)度問題提出了不同的方法和技術(shù)。然而，仍然迫切需要靈活的架構(gòu)和調(diào)度方法，其涵蓋可能對(duì)系統(tǒng)性能具有很大影響的重要要求。此外，一些工作不會(huì)動(dòng)態(tài)地考慮任務(wù)特征和資源屬性，任務(wù)等待時(shí)間這一重要績效指標(biāo)也需要得到進(jìn)一步重視與優(yōu)化。因此，提出了一種動(dòng)態(tài)調(diào)度隊(duì)列(Dynamic dispatch Queues,TSDQ)下入侵腫瘤生長優(yōu)化(Invasive Tumor Growth Optimization,ITGO)結(jié)合反向傳播神經(jīng)網(wǎng)絡(luò)(Back Propagation Neural Network,BPNN)的云計(jì)算任務(wù)調(diào)度新方法(TSDQ-ITGOBPNN)。其主要?jiǎng)?chuàng)新點(diǎn)如下：

(1) 混合啟發(fā)式算法融合模擬退火算法與反向傳播神經(jīng)網(wǎng)絡(luò)算法特點(diǎn)，對(duì)平均等待時(shí)間進(jìn)行優(yōu)化并使系統(tǒng)中的任務(wù)等待隊(duì)列盡可能短；

(2) 提出的算法結(jié)合任務(wù)特性和資源能力，同時(shí)考慮搜索空間的動(dòng)態(tài)特性，加快了啟發(fā)算法的收斂速度并提高了解決方案的質(zhì)量；

(3) 混合啟發(fā)算法考慮云計(jì)算調(diào)度任務(wù)的復(fù)雜性，在兼顧云計(jì)算任務(wù)等待時(shí)間和隊(duì)列長度的前提下對(duì)其進(jìn)行隊(duì)列管理，克服了單個(gè)啟發(fā)式算法的固有局限性的同時(shí)增強(qiáng)了解決方案空間搜索的能力。

實(shí)驗(yàn)結(jié)果表明，所提動(dòng)態(tài)隊(duì)列下模擬退火結(jié)合反向傳播神經(jīng)網(wǎng)絡(luò)算法能有效減少任務(wù)調(diào)度等待時(shí)間，提高資源利用率并增強(qiáng)負(fù)載平衡度。

1 背景架構(gòu)

1.1 調(diào)度問題

現(xiàn)如今，由于云提供商要求與用戶服務(wù)質(zhì)量、用戶優(yōu)先級(jí)、服務(wù)成本等偏好之間存在巨大重疊，所以將任務(wù)調(diào)度作為云計(jì)算的一個(gè)重點(diǎn)方面進(jìn)行了大量研究。在安排任務(wù)時(shí)應(yīng)考慮用戶的滿意度、提供者的利潤優(yōu)化和其他因素。由于該過程是NP完全問題，因此，一種有效的方法不僅應(yīng)該優(yōu)化云用戶和提供商的某些目標(biāo)，還要考慮云計(jì)算環(huán)境的動(dòng)態(tài)特性。

云計(jì)算由包含多個(gè)物理機(jī)(Host)的大量數(shù)據(jù)中心組成。每個(gè)主機(jī)運(yùn)行多個(gè)虛擬機(jī)，負(fù)責(zé)執(zhí)行具有不同QoS的用戶任務(wù)。云計(jì)算環(huán)境中的調(diào)度過程，如圖1所示。假設(shè)N個(gè)用戶提交他們的任務(wù)T1,T2,…,TN，要安排到M臺(tái)虛擬機(jī)VM1,VM2,…,VMM上。本文假設(shè)任務(wù)是互相獨(dú)立的，即任務(wù)之間沒有優(yōu)先約束，它們不是先發(fā)制人的，也不能被打斷。此外，這些任務(wù)具有不同的特性，如長度、到達(dá)時(shí)間、突發(fā)時(shí)間、截止日期等。本文還假設(shè)VM在CPU速度、RAM、帶寬等方面是異構(gòu)的。

圖1 云調(diào)度環(huán)境

云代理查詢?cè)菩畔⒎?wù)(Cloud Information Ser-vice，CIS)提供有關(guān)執(zhí)行接收任務(wù)所需服務(wù)的信息，然后在發(fā)現(xiàn)的服務(wù)上安排任務(wù)。要服務(wù)任務(wù)的選擇取決于代理確保的多個(gè)因素和QoS要求。云信息數(shù)量龐大，給查詢帶來一定的困難。因此可以設(shè)計(jì)規(guī)模較小的云信息集，將同類信息進(jìn)行集合，實(shí)現(xiàn)云信息的全面覆蓋[10]。云代理是任務(wù)調(diào)度過程的主要組成部分，它調(diào)解用戶和提供者之間的協(xié)商，并且還負(fù)責(zé)對(duì)特定時(shí)間和特定資源進(jìn)行任務(wù)的調(diào)度決策，但是有些問題需要考慮在內(nèi)。

首先，用戶提交的任務(wù)加入系統(tǒng)中的第一個(gè)隊(duì)列，并且必須等待資源的使用。因此，這擴(kuò)展了系統(tǒng)的隊(duì)列長度并增加了等待時(shí)間。但是，必須使用有效的方法而不是先到先服務(wù)(First-come-first-served,FCFS)策略來管理此隊(duì)列。其次，當(dāng)提供者處理任務(wù)時(shí)，許多參數(shù)可以同時(shí)被視為單目標(biāo)優(yōu)化或多目標(biāo)，例如對(duì)資源利用有直接影響的完成時(shí)間。因此，應(yīng)該在云代理中設(shè)計(jì)和實(shí)現(xiàn)良好的任務(wù)調(diào)度方法，不僅要滿足云用戶強(qiáng)加的QoS約束，還要在虛擬機(jī)之間進(jìn)行良好的負(fù)載均衡，以提高資源利用率，最大化利潤。這種方法還應(yīng)具有根據(jù)云環(huán)境中動(dòng)態(tài)調(diào)度要求調(diào)整調(diào)度過程的適應(yīng)性?；谏鲜鰡栴}，本文提出的方法旨在優(yōu)化特定的性能指標(biāo)。特別是，本文的目標(biāo)是最小化完成時(shí)間、最小化等待時(shí)間、最大化資源利用率，實(shí)現(xiàn)更好的負(fù)載平衡并降低所需資源的成本。

1.2 有效性衡量標(biāo)準(zhǔn)

在任務(wù)調(diào)度過程中，可以將各種時(shí)間參數(shù)作為性能衡量指標(biāo)，包括所需時(shí)間(完成、等待、周轉(zhuǎn)、流程、延遲等)、吞吐量、負(fù)載平衡、資源利用率等[11]。本文選取Makespan、等待時(shí)間、不平衡程度、成本以及資源利用率作為性能評(píng)價(jià)指標(biāo)，具體定義如下：

(1) Makespan 該指標(biāo)表示執(zhí)行所有任務(wù)所花費(fèi)的時(shí)間(即上一個(gè)任務(wù)的結(jié)束時(shí)間)。該指標(biāo)可以按下式計(jì)算：

Makespan=maxi∈taskes{FTi}

(1)

式中：FTi表示任務(wù)i的結(jié)束時(shí)間。

(2) 等待時(shí)間 任務(wù)的等待時(shí)間是指在執(zhí)行之前在隊(duì)列中花費(fèi)的時(shí)間。等待時(shí)間的最小值表示可以最小化等待時(shí)間以及隊(duì)列長度的任務(wù)的正確/最佳順序。

(3) 不平衡程度(Degree of Imbalance，DI) 該指標(biāo)衡量各個(gè)虛擬機(jī)VM之間的不平衡。不平衡度量表示一個(gè)重要的QoS度量標(biāo)準(zhǔn)，用于顯示任務(wù)的分配效率和虛擬機(jī)之間的負(fù)載平衡。DI可以按下式：

(2)

式中：Tmax、Tmin、Tavg分別是所有VM的最大、最小和平均總執(zhí)行時(shí)間。

(4) 成本 成本指標(biāo)表示進(jìn)行任務(wù)調(diào)度過程中所花費(fèi)的時(shí)間及能耗綜合指標(biāo)，是評(píng)價(jià)調(diào)度算法的關(guān)鍵因素，該指標(biāo)可按下式計(jì)算：

Cost=∑ETij×CVMj

(3)

式中：ETij是VMj上任務(wù)i的執(zhí)行時(shí)間；CVMj是每單位時(shí)間VMj的成本。

(5) 資源利用率(Resource Utilization Rate，RU) 資源利用率是指在云計(jì)算任務(wù)調(diào)度過程中，調(diào)度任務(wù)對(duì)各個(gè)虛擬機(jī)算力使用以及資源分配是否合理的衡量指標(biāo)，可以按下式計(jì)算：

(4)

式中：TVMi是VMi完成所有任務(wù)所花費(fèi)的時(shí)間；N是資源的數(shù)量。

2 算法設(shè)計(jì)

2.1 前饋型神經(jīng)網(wǎng)絡(luò)算法(BPNN)

前饋神經(jīng)網(wǎng)絡(luò)包含的算法眾多，所提方法采用BP神經(jīng)網(wǎng)絡(luò)，每層神經(jīng)元的狀態(tài)只影響到下一層，且通過各神經(jīng)元權(quán)值的不斷調(diào)整以降低誤差信號(hào)，直至找到最優(yōu)狀態(tài)。

BP神經(jīng)網(wǎng)絡(luò)的輸入層數(shù)據(jù)經(jīng)隱層處理后轉(zhuǎn)向輸出層，如果輸出層實(shí)際輸出與期望輸出不相等，誤差信號(hào)將沿原通路返回，通過各神經(jīng)元權(quán)值的不斷修改來降低誤差信號(hào)直至達(dá)到可接受范圍或指定學(xué)習(xí)次數(shù)為止[12]。

設(shè)訓(xùn)練樣本為Xk=[xk1,xk2,…,xkm],k=1,2,…,N，N為訓(xùn)練樣本數(shù),η為學(xué)習(xí)效率。隱層I和輸入層M間的權(quán)值向量WMI(n)第n次迭代時(shí)的關(guān)系式為：

(5)

隱層I與隱層J間的權(quán)值向量WIJ(n)第n次迭代時(shí)關(guān)系式為：

(6)

輸出層P與隱層J間的權(quán)值向量WJP(n)第n次迭代時(shí)關(guān)系式為：

(7)

迭代后的實(shí)際輸出為：Yk(n)=[yk1(n),yk2(n),…,ykp(n)]，期望輸出為：dk=[dk1,dk2,…,dkp]，k=1,2,…,N[13]。BPNN算法詳細(xì)流程如圖2所示。

圖2 BPNN算法詳細(xì)流程

2.2 入侵腫瘤生長優(yōu)化(ITGO)

ITGO是一種基于群智能的啟發(fā)式優(yōu)化算法，該算法通過模擬腫瘤細(xì)胞周圍的微環(huán)境，對(duì)所需問題進(jìn)行求解和計(jì)算[14]。在細(xì)胞種群中，由外到內(nèi)分別是入侵細(xì)胞、生長細(xì)胞、休眠細(xì)胞和死亡細(xì)胞。其中，當(dāng)細(xì)胞種群陷入局部最優(yōu)解時(shí)，可通過入侵細(xì)胞的Levy飛行，跳出局部最優(yōu)解；當(dāng)前范圍內(nèi)搜索更優(yōu)解由生長細(xì)胞負(fù)責(zé)。

4類細(xì)胞在解空間中的具體表現(xiàn)為：

(1) 入侵細(xì)胞。入侵細(xì)胞具有極強(qiáng)的搜索能力，能通過Levy飛行跳出局部最優(yōu)解[15]。當(dāng)細(xì)胞種群陷入局部最優(yōu)解時(shí)，可通過入侵細(xì)胞的Levy飛行，找到營養(yǎng)液濃度更高的位置，并引導(dǎo)種群向該濃度更高的地方移動(dòng)，從而跳出局部最優(yōu)解：

Icelli,j(t+1)=Icelli,j(t)+α·Levy(s)

(8)

(9)

Levy(s)～|s|-1-v1

(10)

(11)

(12)

(13)

式(11)-式(13)為基于蒙特卡羅的步長選擇。式(8)中：t為當(dāng)前迭代次數(shù)；Icelli,j(t+1)為當(dāng)前的入侵細(xì)胞；α是步長控制參數(shù)；Levy(s)是Levy飛行的步長分布。式(9)中T為算法最大迭代次數(shù)。

(2) 生長細(xì)胞。生長細(xì)胞位于入侵細(xì)胞內(nèi)層，休眠細(xì)胞外層，承擔(dān)了絕大部分的搜索工作，主要負(fù)責(zé)在當(dāng)前范圍內(nèi)搜索更優(yōu)解。

(3) 休眠細(xì)胞。休眠細(xì)胞位于生長細(xì)胞內(nèi)層，死亡細(xì)胞外層。休眠細(xì)胞搜索能力極低，當(dāng)周圍的營養(yǎng)液濃度過低時(shí)，部分細(xì)胞會(huì)由于營養(yǎng)成分不足而進(jìn)入休眠狀態(tài)，直到周圍的營養(yǎng)液濃度再次發(fā)生變化。

(4) 死亡細(xì)胞。在優(yōu)化過程中，不執(zhí)行任何檢索操作，不占據(jù)任何計(jì)算資源，當(dāng)達(dá)到一定的細(xì)胞周期之后，將釋放占據(jù)的計(jì)算空間。

2.3 任務(wù)調(diào)度

云計(jì)算環(huán)境的增長速度非常迅速，任務(wù)調(diào)度被認(rèn)為是必須解決的挑戰(zhàn)之一。由于任務(wù)的特征、云提供商的要求、用戶的偏好以及要解決的優(yōu)化問題的類型多樣，有效的任務(wù)調(diào)度方法是一個(gè)長期存在的問題。

各混合算法間的主要區(qū)別在于調(diào)整任務(wù)權(quán)重的方法和適應(yīng)度計(jì)算模型。所提方法的主要目的是使用WTO-PSO算法以增強(qiáng)BPNN的收斂性能，并提高搜索能力和方案質(zhì)量，其中采用SA算法來優(yōu)化慣性權(quán)重這一影響B(tài)PNN性能的關(guān)鍵參數(shù)，動(dòng)態(tài)調(diào)整該參數(shù)，可提高BPNN的搜索能力。此外，在分析問題的動(dòng)態(tài)特征基礎(chǔ)上，所提方案包括任務(wù)特征和資源容量。

因此，本文使用基于BPNN算法的有效算法來優(yōu)化平均等待時(shí)間并使系統(tǒng)中的任務(wù)等待隊(duì)列盡可能短。如圖3所示，在任務(wù)等待隊(duì)列中，任務(wù)根據(jù)其到達(dá)時(shí)間排隊(duì)。通過計(jì)算所有可能的任務(wù)序列等待時(shí)間以獲得時(shí)間的最佳序列，選取其中的最小值并返回，即可以獲得最小等待時(shí)間和減少隊(duì)列長度的任務(wù)的正確順序?？s小等待時(shí)間和減少隊(duì)列任務(wù)可以有效降低分?jǐn)偟矫總€(gè)任務(wù)隊(duì)列的壓力，有利于實(shí)現(xiàn)負(fù)載均衡，負(fù)載均衡又可以提高對(duì)動(dòng)態(tài)特征的分析和處理[16]。

圖3 本文提出的方法模型

為了優(yōu)化等待時(shí)間，定義式(12)為該問題的目標(biāo)函數(shù)。因此，給出了用于計(jì)算PSO算法中每個(gè)粒子的解的適應(yīng)度函數(shù)，并且在式(15)和式(16)中檢驗(yàn)了解決方案以找到所考慮問題的最優(yōu)解。

objectivefunction=minimize{WT}

(14)

Fitness=minTWi

(15)

任務(wù)TWT的總等待時(shí)間可以表示如下：

(16)

式中：WTTaski是任務(wù)TWT的等待時(shí)間；n是隊(duì)列中的任務(wù)數(shù)。

該算法從初始化部分開始，該部分包括生成具有隨機(jī)位置和速度的群。然后在每次迭代中連續(xù)更新速度、位置、局部最佳和全局最佳解。當(dāng)滿足終止標(biāo)準(zhǔn)時(shí)，該過程結(jié)束：超過迭代次數(shù)或獲得最佳解決方案。本文使用SA算法來優(yōu)化慣性權(quán)重，以加速BPNN向最優(yōu)解的收斂。模擬退火方法的偽代碼如下：

Pseudo-code of Simulated Annealing(SA)

1. S0=Generate_initial_solution()

2. Sbest=S0

3. Temperature=Initialize_Temp()

4. repeat

5. repeat

6. Temperature=calculate_temperature()

7. Snew=Create_neighbor_solution(S0)

8. if(Fitness(Snew)

9. Sbest=Snew

10. else if(rand()

11. S0=Snew

12. end if

13. until thermal equilibrium is reached

14. decrease Temperature according with the annealing schedule;

15. until stopping criterion is met

16. return Sbest

在此過程中，生成初始S0并將溫度設(shè)置為初始溫度。在滿足某個(gè)停止標(biāo)準(zhǔn)之前執(zhí)行迭代。在每個(gè)步驟中，SA考慮當(dāng)前解S0的一些相鄰解Snew，并且以一定的概率決定在移動(dòng)到Snew或保持在S0之間。如果新解決方案(Snew)與當(dāng)前解決方案(S0)相比具有更好的適應(yīng)性，則將被接受。但是，如果新解決方案比當(dāng)前解決方案更差，則以一定的概率駁回。一旦達(dá)到熱平衡，就根據(jù)退火時(shí)間表降低溫度。模擬退火算法的主要優(yōu)點(diǎn)是其強(qiáng)大的局部搜索能力，避免陷入局部最優(yōu)解。

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

本文進(jìn)行了幾個(gè)不同參數(shù)設(shè)置的實(shí)驗(yàn)，以評(píng)估本文的工作效率。因此，為了客觀地評(píng)估所提算法的性能，本文將提出的算法TSDQ-ITGOBPNN與文獻(xiàn)[5-6,9]中提出的ECV-PSO、LDIW-PSO以及OTB-CSO算法進(jìn)行了比較。評(píng)估使用來自并行工作負(fù)載存檔(PWA)[7]中可用實(shí)際系統(tǒng)生成的工作負(fù)載數(shù)據(jù)的合成和實(shí)際數(shù)據(jù)集完成的。主要對(duì)比在完成時(shí)間、不平衡程度、資源利用率和成本等方面的性能。

3.1 模擬環(huán)境及參數(shù)設(shè)置

為了評(píng)估所提方法TSDQ-ITGOBPNN的有效性，在CloudSim上實(shí)現(xiàn)了性能評(píng)估和與其他算法的比較。該模擬器允許建模和模擬可擴(kuò)展云，并在受控環(huán)境中測試開發(fā)的應(yīng)用程序服務(wù)的性能。CloudSim工具包支持云系統(tǒng)組件的建模，例如:云數(shù)據(jù)中心、用戶、虛擬機(jī)和資源配置策略。Cloudsim提供了多種功能，例如使用不同的方案生成不同的工作負(fù)載，并根據(jù)自定義配置執(zhí)行穩(wěn)健的測試。資源參數(shù)如表1所示。

表1 資源參數(shù)

3.2 平均等待與完成時(shí)間對(duì)比

此模擬的目的是在任務(wù)等待隊(duì)列中找到最佳的最小等待時(shí)間序列。為了說明這種情況，本文提供了一個(gè)簡單的例子。本文假設(shè)用戶提交了3個(gè)獨(dú)立的任務(wù)，由提供者處理，并且最初存儲(chǔ)在等待時(shí)間隊(duì)列中。在該模擬中，進(jìn)行了6次實(shí)驗(yàn)，其中在這些實(shí)驗(yàn)中每個(gè)任務(wù)的突發(fā)時(shí)間已經(jīng)改變。

圖4所示為所提算法與ECV-PSO、LDIW-PSO、OTB-CSO算法的對(duì)比結(jié)果?？梢钥闯鏊崴惴梢杂行У乜朔﨩TB-CSO的缺點(diǎn)并提供優(yōu)化的解決方案，通過最小化在隊(duì)列中花費(fèi)的任務(wù)等待時(shí)間，減少隊(duì)列長度并使其盡可能短，提高了管理任務(wù)等待隊(duì)列的速度和效率。

圖4 不同算法平均等待時(shí)間對(duì)比

在這種模擬中，高性能計(jì)算中心北部的標(biāo)準(zhǔn)格式化工作負(fù)載稱為日志，用于生成不同的工作負(fù)載。圖5中，對(duì)于不同數(shù)量的任務(wù)，在平均完成時(shí)間方面對(duì)性能進(jìn)行了比較。得到的結(jié)果表明，所提算法TSDQ-ITGOBPNN的完成時(shí)間比其他算法更好，增長更慢?？梢钥闯?，所提算法在執(zhí)行所有任務(wù)上花費(fèi)的時(shí)間更少，并且在解決方案的質(zhì)量和收斂速度方面優(yōu)于LDIW-PSO和RIW-PSO；當(dāng)搜索空間擴(kuò)大時(shí)，LDIW-PSO和RIW-PSO都顯示出更高的穩(wěn)定性。但在LDIW-PSO和RIW-PSO算法的情況下，找到改進(jìn)的最優(yōu)解的可能性變得更大。TSDQ-ITGOBPNN算法顯示出良好的收斂特性，特別是當(dāng)任務(wù)數(shù)量增加時(shí)，完成時(shí)間顯著減少。這是因?yàn)榛趦蓚€(gè)階段的動(dòng)態(tài)隊(duì)列和模糊邏輯，TSDQ-ITGOBPNN算法通過考慮任務(wù)長度和VM能力(如CPU速度、占用率、RAM和帶寬)將任務(wù)分配給最合適的資源，有助于在更短的時(shí)間內(nèi)找到最佳的映射和完成任務(wù)。此外，在搜索最優(yōu)值的每次迭代中，算法評(píng)估返回的解決方案以選擇最優(yōu)解。由于虛擬機(jī)狀態(tài)或虛擬機(jī)的占用率是所提算法的輸入?yún)?shù)之一，所有這些都使得TSDQ-ITGOBPNN不僅能夠做出最佳決策，而且還能夠?yàn)槠浞峙渥詈线m的資源。即使收到任務(wù)，也要盡可能保持資源的繁忙，這樣才能通過增加任務(wù)執(zhí)行時(shí)間的方式有效地減少完成時(shí)間。

圖5 具有不同任務(wù)數(shù)的平均完成時(shí)間對(duì)比

3.3 平均執(zhí)行成本對(duì)比

圖6給出了在相同條件下各種任務(wù)調(diào)度算法的平均完成時(shí)間和執(zhí)行成本，可以看出本文算法的平均執(zhí)行成本最小。結(jié)果同時(shí)表明，所提出的算法不僅優(yōu)化了完成時(shí)間而且優(yōu)化了執(zhí)行成本，并解決了兩個(gè)相互沖突的目標(biāo)。在所提算法中，以任務(wù)執(zhí)行花費(fèi)最少時(shí)間并且不忽略諸如資源利用和執(zhí)行成本的其他度量的方式來選擇資源。因?yàn)槟繕?biāo)是在更好的執(zhí)行時(shí)間和低成本之間找到折衷方案，可以盡可能多地使用具有較低處理器容量的資源，同時(shí)獲得較好的解決方案。所提算法具有動(dòng)態(tài)優(yōu)化資源分配、縮短執(zhí)行時(shí)間和降低執(zhí)行成本的靈活性。

圖6 對(duì)比不同算法的平均執(zhí)行成本

3.4 不平衡程度對(duì)比

圖7繪制了所提算法與ECV-PSO、LDIW-PSO、OTB-CSO在平均不平衡程度與任務(wù)數(shù)量方面的比較。實(shí)驗(yàn)結(jié)果表明，基于動(dòng)態(tài)隊(duì)列的兩種任務(wù)調(diào)度算法具有明顯的效率優(yōu)勢，并且對(duì)所有數(shù)據(jù)集表現(xiàn)出近似相同的性能。TSDQ-ITGOBPNN顯示出極好的能力來確定資源之間的最佳負(fù)載平衡，從而防止完成時(shí)間變得過大并避免VM的不平衡工作負(fù)載。這意味著資源具有最佳負(fù)載量；任一負(fù)載不至于繁忙，且其他負(fù)載在任何特定時(shí)間閑置或不使用。因此，最佳和良好的負(fù)載平衡可以得到最高的資源利用率。

圖7 對(duì)比不同算法的平均失衡度(DI)

3.5 平均資源利用率與不同任務(wù)數(shù)成本對(duì)比

圖8顯示了所提算法與ECV-PSO、LDIW-PSO、OTB-CSO的平均資源利用率。資源利用率是一項(xiàng)重要的性能指標(biāo)，因?yàn)樗粌H代表資源的利用率，而且顯示資源在執(zhí)行任務(wù)時(shí)忙于哪個(gè)級(jí)別。結(jié)果表明TSDQ-ITGOBPNN的資源利用率保持在較高水平，與ECV-PSO、LDIW-PSO以及OTB-CSO相比，它具有最佳的資源利用率。提出的算法和這些算法之間的差異是顯著的，并證明了基于動(dòng)態(tài)調(diào)度隊(duì)列的算法的有效性。因此，TSDQ-ITGOBPNN可以靈活地分析、探索和調(diào)度存儲(chǔ)在動(dòng)態(tài)隊(duì)列中的任務(wù)集，以執(zhí)行更智能的調(diào)度決策。此外，TSDQ-ITGOBPNN還可以在調(diào)度任務(wù)的過程中實(shí)現(xiàn)資源的良好利用，保持較高的資源占用率。實(shí)際上，TSDQ-ITGOBPNN算法使資源盡可能繁忙并使用所有可能的資源能力。資源利用率指標(biāo)正在顯著增長，因?yàn)榉?wù)提供商希望通過租用有限數(shù)量的資源來獲得最大利潤。

圖8 不同算法的平均資源利用率對(duì)比

圖9為TSDQ-ITGOBPNN與ECV-PSO、LDIW-PSO、OTB-CSO不同任務(wù)數(shù)之間的成本比較。此度量標(biāo)準(zhǔn)顯示用戶需要向服務(wù)提供商支付的資源利用總量。例如，在此模擬中，本文假設(shè)資源的5 000 MIPS計(jì)算能力的成本是每單位時(shí)間10美元。仿真結(jié)果表明，當(dāng)任務(wù)數(shù)量增加時(shí)，TSDQ-ITGOBPNN表現(xiàn)更好，成本更低。基于所提出的調(diào)度策略，TSDQ-ITGOBPNN顯示出了將傳入請(qǐng)求分發(fā)到異構(gòu)VM的更好的靈活性，例如，它能夠確定執(zhí)行每個(gè)任務(wù)的最合適的VM，以便在考慮其他QoS要求的同時(shí)最小化成本。TSDQ-ITGOBPNN算法基于Mamdani推理系統(tǒng)和定義的規(guī)則動(dòng)態(tài)地考慮任務(wù)長度和資源處理器容量。當(dāng)所提算法計(jì)算函數(shù)適應(yīng)度時(shí)，它考慮任務(wù)和資源屬性，例如：資源的任務(wù)長度和CPU功率。因此，最佳適應(yīng)性意味著TSDQ-ITGOBPNN算法選擇并使用具有較高計(jì)算能力的VM，如果具有較低計(jì)算能力的VM不能為任務(wù)提供良好結(jié)果或給出非最佳解決方案，那么將影響結(jié)果的準(zhǔn)確性。綜上，TSDQ-ITGOBPNN算法可以在成本方面有效地實(shí)現(xiàn)良好的性能。

圖9 具有不同任務(wù)數(shù)的成本對(duì)比

實(shí)驗(yàn)表明，所提算法的特性不僅適用于合成任務(wù)，也適用于實(shí)際任務(wù)。它是一種智能體系結(jié)構(gòu)，可以獲得最優(yōu)解，并在所考慮的性能指標(biāo)方面實(shí)現(xiàn)更好的全局收斂能力。

4 結(jié) 語

任務(wù)調(diào)度是云計(jì)算中最具挑戰(zhàn)性的問題之一，在整個(gè)云計(jì)算設(shè)施的效率中起著重要作用。任務(wù)調(diào)度的目標(biāo)是通過優(yōu)化執(zhí)行時(shí)間、成本、資源利用率、負(fù)載平衡度等指標(biāo)將任務(wù)映射到要執(zhí)行的最合適資源。提出的動(dòng)態(tài)調(diào)度隊(duì)列和混合啟發(fā)式算法的任務(wù)調(diào)度優(yōu)化方法能快速有效確定不同情況下的最佳調(diào)度方案，以保證較高的調(diào)度效率與最佳的穩(wěn)定性。通過使用CloudSim仿真器和來自Parallel Workload Archive(PWA)的實(shí)際系統(tǒng)的合成和實(shí)際數(shù)據(jù)集的大量實(shí)驗(yàn)，驗(yàn)證了所提出工作的優(yōu)越性。TSDQ-ITGOBPNN在最小化等待時(shí)間和隊(duì)列長度、減少完成時(shí)間、最大化資源利用率、最小化執(zhí)行成本和改善負(fù)載平衡方面取得了良好的性能。

實(shí)驗(yàn)結(jié)果證明了本文提出的算法的有效性，與其他現(xiàn)有的調(diào)度算法相比，特別是在高維問題中，具有更優(yōu)異的性能。下一步可以通過整合其他優(yōu)化算法和技術(shù)來增強(qiáng)所提算法的穩(wěn)健性，并考慮更多的QoS參數(shù)如任務(wù)的優(yōu)先級(jí)，允許在隊(duì)列之間遷移任務(wù)，考慮能量消費(fèi)和虛擬機(jī)遷移的概念等。