動態隊列下入侵腫瘤生長優化和BPNN的云計算任務調度新方法

范 穎 沈建京

1(鄭州信息科技職業學院 河南 鄭州 450008) 2(中國人民解放軍戰略支援部隊信息工程大學 河南 鄭州450008)

0 引 言

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

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

(1) 混合啟發式算法融合模擬退火算法與反向傳播神經網絡算法特點，對平均等待時間進行優化并使系統中的任務等待隊列盡可能短；

(2) 提出的算法結合任務特性和資源能力，同時考慮搜索空間的動態特性，加快了啟發算法的收斂速度并提高了解決方案的質量；

(3) 混合啟發算法考慮云計算調度任務的復雜性，在兼顧云計算任務等待時間和隊列長度的前提下對其進行隊列管理，克服了單個啟發式算法的固有局限性的同時增強了解決方案空間搜索的能力。

實驗結果表明，所提動態隊列下模擬退火結合反向傳播神經網絡算法能有效減少任務調度等待時間，提高資源利用率并增強負載平衡度。

1 背景架構

1.1 調度問題

現如今，由于云提供商要求與用戶服務質量、用戶優先級、服務成本等偏好之間存在巨大重疊，所以將任務調度作為云計算的一個重點方面進行了大量研究。在安排任務時應考慮用戶的滿意度、提供者的利潤優化和其他因素。由于該過程是NP完全問題，因此，一種有效的方法不僅應該優化云用戶和提供商的某些目標，還要考慮云計算環境的動態特性。

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

圖1 云調度環境

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

首先，用戶提交的任務加入系統中的第一個隊列，并且必須等待資源的使用。因此，這擴展了系統的隊列長度并增加了等待時間。但是，必須使用有效的方法而不是先到先服務(First-come-first-served,FCFS)策略來管理此隊列。其次，當提供者處理任務時，許多參數可以同時被視為單目標優化或多目標，例如對資源利用有直接影響的完成時間。因此，應該在云代理中設計和實現良好的任務調度方法，不僅要滿足云用戶強加的QoS約束，還要在虛擬機之間進行良好的負載均衡，以提高資源利用率，最大化利潤。這種方法還應具有根據云環境中動態調度要求調整調度過程的適應性。基于上述問題，本文提出的方法旨在優化特定的性能指標。特別是，本文的目標是最小化完成時間、最小化等待時間、最大化資源利用率，實現更好的負載平衡并降低所需資源的成本。

1.2 有效性衡量標準

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

(1) Makespan 該指標表示執行所有任務所花費的時間(即上一個任務的結束時間)。該指標可以按下式計算：

Makespan=maxi∈taskes{FTi}

(1)

式中：FTi表示任務i的結束時間。

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

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

(2)

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

(4) 成本 成本指標表示進行任務調度過程中所花費的時間及能耗綜合指標，是評價調度算法的關鍵因素，該指標可按下式計算：

Cost=∑ETij×CVMj

(3)

式中：ETij是VMj上任務i的執行時間；CVMj是每單位時間VMj的成本。

(5) 資源利用率(Resource Utilization Rate，RU) 資源利用率是指在云計算任務調度過程中，調度任務對各個虛擬機算力使用以及資源分配是否合理的衡量指標，可以按下式計算：

(4)

式中：TVMi是VMi完成所有任務所花費的時間；N是資源的數量。

2 算法設計

2.1 前饋型神經網絡算法(BPNN)

前饋神經網絡包含的算法眾多，所提方法采用BP神經網絡，每層神經元的狀態只影響到下一層，且通過各神經元權值的不斷調整以降低誤差信號，直至找到最優狀態。

BP神經網絡的輸入層數據經隱層處理后轉向輸出層，如果輸出層實際輸出與期望輸出不相等，誤差信號將沿原通路返回，通過各神經元權值的不斷修改來降低誤差信號直至達到可接受范圍或指定學習次數為止[12]。

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

(5)

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

(6)

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

(7)

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

圖2 BPNN算法詳細流程

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

ITGO是一種基于群智能的啟發式優化算法，該算法通過模擬腫瘤細胞周圍的微環境，對所需問題進行求解和計算[14]。在細胞種群中，由外到內分別是入侵細胞、生長細胞、休眠細胞和死亡細胞。其中，當細胞種群陷入局部最優解時，可通過入侵細胞的Levy飛行，跳出局部最優解；當前范圍內搜索更優解由生長細胞負責。

4類細胞在解空間中的具體表現為：

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

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

(8)

(9)

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

(10)

(11)

(12)

(13)

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

(2) 生長細胞。生長細胞位于入侵細胞內層，休眠細胞外層，承擔了絕大部分的搜索工作，主要負責在當前范圍內搜索更優解。

(3) 休眠細胞。休眠細胞位于生長細胞內層，死亡細胞外層。休眠細胞搜索能力極低，當周圍的營養液濃度過低時，部分細胞會由于營養成分不足而進入休眠狀態，直到周圍的營養液濃度再次發生變化。

(4) 死亡細胞。在優化過程中，不執行任何檢索操作，不占據任何計算資源，當達到一定的細胞周期之后，將釋放占據的計算空間。

2.3 任務調度

云計算環境的增長速度非常迅速，任務調度被認為是必須解決的挑戰之一。由于任務的特征、云提供商的要求、用戶的偏好以及要解決的優化問題的類型多樣，有效的任務調度方法是一個長期存在的問題。

各混合算法間的主要區別在于調整任務權重的方法和適應度計算模型。所提方法的主要目的是使用WTO-PSO算法以增強BPNN的收斂性能，并提高搜索能力和方案質量，其中采用SA算法來優化慣性權重這一影響BPNN性能的關鍵參數，動態調整該參數，可提高BPNN的搜索能力。此外，在分析問題的動態特征基礎上，所提方案包括任務特征和資源容量。

因此，本文使用基于BPNN算法的有效算法來優化平均等待時間并使系統中的任務等待隊列盡可能短。如圖3所示，在任務等待隊列中，任務根據其到達時間排隊。通過計算所有可能的任務序列等待時間以獲得時間的最佳序列，選取其中的最小值并返回，即可以獲得最小等待時間和減少隊列長度的任務的正確順序。縮小等待時間和減少隊列任務可以有效降低分攤到每個任務隊列的壓力，有利于實現負載均衡，負載均衡又可以提高對動態特征的分析和處理[16]。

圖3 本文提出的方法模型

為了優化等待時間，定義式(12)為該問題的目標函數。因此，給出了用于計算PSO算法中每個粒子的解的適應度函數，并且在式(15)和式(16)中檢驗了解決方案以找到所考慮問題的最優解。

objectivefunction=minimize{WT}

(14)

Fitness=minTWi

(15)

任務TWT的總等待時間可以表示如下：

(16)

式中：WTTaski是任務TWT的等待時間；n是隊列中的任務數。

該算法從初始化部分開始，該部分包括生成具有隨機位置和速度的群。然后在每次迭代中連續更新速度、位置、局部最佳和全局最佳解。當滿足終止標準時，該過程結束：超過迭代次數或獲得最佳解決方案。本文使用SA算法來優化慣性權重，以加速BPNN向最優解的收斂。模擬退火方法的偽代碼如下：

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并將溫度設置為初始溫度。在滿足某個停止標準之前執行迭代。在每個步驟中，SA考慮當前解S0的一些相鄰解Snew，并且以一定的概率決定在移動到Snew或保持在S0之間。如果新解決方案(Snew)與當前解決方案(S0)相比具有更好的適應性，則將被接受。但是，如果新解決方案比當前解決方案更差，則以一定的概率駁回。一旦達到熱平衡，就根據退火時間表降低溫度。模擬退火算法的主要優點是其強大的局部搜索能力，避免陷入局部最優解。

3 實驗及分析

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

3.1 模擬環境及參數設置

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

表1 資源參數

3.2 平均等待與完成時間對比

此模擬的目的是在任務等待隊列中找到最佳的最小等待時間序列。為了說明這種情況，本文提供了一個簡單的例子。本文假設用戶提交了3個獨立的任務，由提供者處理，并且最初存儲在等待時間隊列中。在該模擬中，進行了6次實驗，其中在這些實驗中每個任務的突發時間已經改變。

圖4所示為所提算法與ECV-PSO、LDIW-PSO、OTB-CSO算法的對比結果。可以看出所提算法可以有效地克服OTB-CSO的缺點并提供優化的解決方案，通過最小化在隊列中花費的任務等待時間，減少隊列長度并使其盡可能短，提高了管理任務等待隊列的速度和效率。

圖4 不同算法平均等待時間對比

在這種模擬中，高性能計算中心北部的標準格式化工作負載稱為日志，用于生成不同的工作負載。圖5中，對于不同數量的任務，在平均完成時間方面對性能進行了比較。得到的結果表明，所提算法TSDQ-ITGOBPNN的完成時間比其他算法更好，增長更慢。可以看出，所提算法在執行所有任務上花費的時間更少，并且在解決方案的質量和收斂速度方面優于LDIW-PSO和RIW-PSO；當搜索空間擴大時，LDIW-PSO和RIW-PSO都顯示出更高的穩定性。但在LDIW-PSO和RIW-PSO算法的情況下，找到改進的最優解的可能性變得更大。TSDQ-ITGOBPNN算法顯示出良好的收斂特性，特別是當任務數量增加時，完成時間顯著減少。這是因為基于兩個階段的動態隊列和模糊邏輯，TSDQ-ITGOBPNN算法通過考慮任務長度和VM能力(如CPU速度、占用率、RAM和帶寬)將任務分配給最合適的資源，有助于在更短的時間內找到最佳的映射和完成任務。此外，在搜索最優值的每次迭代中，算法評估返回的解決方案以選擇最優解。由于虛擬機狀態或虛擬機的占用率是所提算法的輸入參數之一，所有這些都使得TSDQ-ITGOBPNN不僅能夠做出最佳決策，而且還能夠為其分配最合適的資源。即使收到任務，也要盡可能保持資源的繁忙，這樣才能通過增加任務執行時間的方式有效地減少完成時間。

圖5 具有不同任務數的平均完成時間對比

3.3 平均執行成本對比

圖6給出了在相同條件下各種任務調度算法的平均完成時間和執行成本，可以看出本文算法的平均執行成本最小。結果同時表明，所提出的算法不僅優化了完成時間而且優化了執行成本，并解決了兩個相互沖突的目標。在所提算法中，以任務執行花費最少時間并且不忽略諸如資源利用和執行成本的其他度量的方式來選擇資源。因為目標是在更好的執行時間和低成本之間找到折衷方案，可以盡可能多地使用具有較低處理器容量的資源，同時獲得較好的解決方案。所提算法具有動態優化資源分配、縮短執行時間和降低執行成本的靈活性。

圖6 對比不同算法的平均執行成本

3.4 不平衡程度對比

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

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

3.5 平均資源利用率與不同任務數成本對比

圖8顯示了所提算法與ECV-PSO、LDIW-PSO、OTB-CSO的平均資源利用率。資源利用率是一項重要的性能指標，因為它不僅代表資源的利用率，而且顯示資源在執行任務時忙于哪個級別。結果表明TSDQ-ITGOBPNN的資源利用率保持在較高水平，與ECV-PSO、LDIW-PSO以及OTB-CSO相比，它具有最佳的資源利用率。提出的算法和這些算法之間的差異是顯著的，并證明了基于動態調度隊列的算法的有效性。因此，TSDQ-ITGOBPNN可以靈活地分析、探索和調度存儲在動態隊列中的任務集，以執行更智能的調度決策。此外，TSDQ-ITGOBPNN還可以在調度任務的過程中實現資源的良好利用，保持較高的資源占用率。實際上，TSDQ-ITGOBPNN算法使資源盡可能繁忙并使用所有可能的資源能力。資源利用率指標正在顯著增長，因為服務提供商希望通過租用有限數量的資源來獲得最大利潤。

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

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

圖9 具有不同任務數的成本對比

實驗表明，所提算法的特性不僅適用于合成任務，也適用于實際任務。它是一種智能體系結構，可以獲得最優解，并在所考慮的性能指標方面實現更好的全局收斂能力。

4 結 語

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

實驗結果證明了本文提出的算法的有效性，與其他現有的調度算法相比，特別是在高維問題中，具有更優異的性能。下一步可以通過整合其他優化算法和技術來增強所提算法的穩健性，并考慮更多的QoS參數如任務的優先級，允許在隊列之間遷移任務，考慮能量消費和虛擬機遷移的概念等。