大規模云計算網絡用戶短時需求任務調度優化算法

摘 "要： 設計一種大規模云計算網絡用戶短時需求任務調度優化算法，在較短的時間內處理大量的云計算任務，以滿足用戶短時需求。建立一個大規模云計算網絡任務調度模型，將大規模云計算網絡任務分配到各個虛擬機節點上，快速完成用戶的短時需求任務；再通過遺傳算法的個體編解碼、自適應函數和遺傳操作獲取最優任務調度結果；并引入模擬退火算法，在遺傳算法獲取最佳調度結果的基礎上進行局部搜索，直到迭代完成，輸出最終的大規模云計算網絡用戶短時需求任務調度的全局最優解。實驗結果表明：所設計算法能夠實時關注用戶任務執行狀態以及用戶任務執行時間；當用戶任務數量為220時，該算法的單節點最大執行時間約為0.27 s，可提升整個任務調度的性能和效率；且該算法獲取任務調度結果的收斂速度快、精度高。

關鍵詞： 云計算網絡； 用戶短時需求； 任務調度； 遺傳算法； 模擬退火算法； 收斂速度； 最大執行時間

中圖分類號： TN919?34； TP311 " " " " " " " " " 文獻標識碼： A " " " " " " " " " " "文章編號： 1004?373X（2024）06?0063?05

Short?term demand task scheduling optimization algorithm for large?scale cloud computing network users

YAN Junfeng， TANG Jingmin

（Faculty of Information Engineering and Automation， Kunming University of Science and Technology， Kunming 650500， China）

Abstract： A large?scale cloud computing network user short?term demand task scheduling optimization algorithm is designed to deal with a large number of cloud computing tasks in a short period of time， so as to meet the short?term demand of users. The large?scale cloud computing network task scheduling model is established， and the large?scale cloud computing network task is assigned to each virtual machine node to quickly complete the short?term tasks required by users. The optimal task scheduling results are obtained through individual encoding and decoding of genetic algorithm， establishment of adaptive function and genetic operation. The simulated annealing algorithm is introduced to perform local search on the basis of the optimal scheduling results obtained by means of the genetic algorithm until the iteration is completed， and the final global optimal solution of short?term demand task scheduling for large?scale cloud computing network users is output. The experimental results show that the algorithm can focus on the user task execution state and the user task execution time in real time. When the number of tasks is 220， the maximum execution time of a single node is 0.27 s， which can improve the performance and efficiency of the entire task scheduling. The algorithm has fast convergence speed and high precision in obtaining task scheduling results.

Keywords： cloud computing network; short term user needs; task scheduling; genetic algorithm; simulated annealing algorithm; convergence speed; maximum execution time

0 "引 "言

隨著電子信息技術的迅速發展，數據量也不斷增加，對電子設備的儲存能力要求也越來越高，一臺電子設備的運行模式已經無法滿足用戶的需求，因此，需要找到更有效的解決方式。云計算技術是結合分布式計算、網格計算和虛擬化等計算技術混合演進的算法[1?2]，該技術將大量數據利用網絡云計算分解為多個小程序，采用大量電子設備組成新系統，處理和分析小程序獲得的結果，再告知用戶。在云計算系統中，用戶任務的數量較大且非常復雜[3]，而任務調度的能力會影響云計算的處理效率[4?5]，因此，研究如何進行合理的云計算任務調度具有重要意義。

近年來，一些相關專家和學者對云計算任務調度的算法進行了研究，如賴兆林等人提出一種逆向學習行為粒子群算法的云計算任務調度算法[6]，將種群內的個體通過分群的方式進行分類，提升種群搜索的多樣性；再采用逆向學習和繁殖方式進行局部尋優，加快算法的收斂速度，實現云計算網絡用戶的任務調度。鄧斌濤等人提出一種基于生產函數的云計算QoS任務調度算法[7]，通過離散粒子群優化算法進行任務調度的搜索，采用生產函數建立任務調度的自適應函數，找到最優解，通過求解自適應函數實現云計算網絡用戶的任務調度。但是這兩種算法在開始搜索時速度較快，而在搜索快結束時收斂較慢，并且穩定性較差。

遺傳算法的快速全局搜索能力較強[8]，自適應性較高；模擬退火算法具有避免陷入局部最優解的能力[9]，并且操作簡單。本文結合遺傳算法和模擬退火算法，提出一種通過大規模云計算網絡用戶短時需求任務調度優化算法，通過合理地安排任務調度，提升用戶任務的執行效率，降低用戶任務的執行時間。

1 "云計算網絡用戶短時需求任務調度優化算法

1.1 "大規模云計算網絡任務調度模型

在云計算網絡中，包含了大量且復雜的信息資源和用戶，任務調度能夠將這些大規模信息資源分割成多個子任務[10]，分配到各個虛擬機節點上，保證快速地完成各項用戶的短時需求任務，降低完成任務時間，增強用戶服務質量。若將N個用戶短時需求任務分配到M個虛擬機節點，且[Mlt;N]，則可得到大規模云計算網絡任務調度模型的公式，如下：

N個用戶任務集合：

[T=T1，T2，…，TN] " " " " " " " " "（1）

M個虛擬機資源節點：

[V=V1，V2，…，VM] （2）

M個虛擬機的計算速度：

[MIPS=MIPS1，MIPS2，…，MIPSM] " " （3）

式中[MIPSi]為在一定時間內，虛擬機[Vi]的指令。

虛擬機資源節點和用戶任務之間的映射關系為：

[M=m11m12 "… "m1mm21m22 nbsp;… "m2m? " "? " ? " ?mn1mn2 "… "mnm] " " " " " " " （4）

如果用戶任務[Ti]分配到虛擬機節點[Vj]上，[M]中的元素[Mij=1]；反之，[Mij=0]。

第[j]個用戶子任務在第[i]個虛擬機資源節點上的執行時間矩陣為：

[ET=et11et12 "… "et1met21et22 "… "et2m? " "? " ? " ?etn1etn2 "… "etnm] " " " " " " "（5）

通過矩陣[ET]計算出各虛擬機[Vi]執行用戶子任務的時間，公式為：

[TotalTime（pi）=j=1NTime（i，j）， "i∈[1，M]] " （6）

式中： [N]為虛擬機[Vi]執行用戶子任務的總數目；[Time（i，j）]為虛擬機[Vi]的第[j]個用戶子任務的執行時間。

1.2 "基于遺傳算法的云計算網絡任務調度

1.2.1 "個體編解碼

采用遺傳算法對大規模云計算網絡用戶任務調度進行編碼[11]，隨機產生初始種群，使各個體和大規模云計算網絡用戶任務調度算法相互對應，假設用戶任務為[n]，虛擬機資源節點為[m]，得到個體的編碼長度可表示為：

[C=n+m] " " " " " " " " " " （7）

通過遺傳算法完成個體的編碼后，需要進行最優個體的解碼，獲取大規模云計算網絡用戶短時需求任務調度的方案，第[j]個用戶子任務在第[i]個虛擬機資源節點上執行時間矩陣為[ET]，各虛擬機資源節點的所有執行任務時間為：

[maxw=1workerj=1nworker（w，j）] " " " " " " " "（8）

第[t]個用戶任務的完成時間可表示為：

[tasktime（t）=maxj=1tasknumi=1kw（i，j）] " " " " " （9）

式中：[tasknum]為第[t]個用戶任務的子任務數目。

用戶任務的平均完成時間表示為：

[F（x）=t=1tasktasktime（t）task] （10）

式中[task]為用戶任務數目。

1.2.2 "適應度函數

在遺傳算法中，采用適應度函數評判問題求解的能力。針對大規模云計算網絡用戶短時需求任務調度問題[12?13]，為了達到滿意的任務調度完成時間，將用戶任務的最短完成時間作為個體的適應度函數，公式為：

[f（x）=t=1tasktasktime（t）task] " " " " "（11）

1.2.3 "遺傳操作

1） 選擇操作

適應度函數值影響了個體進入下一代種群的概率，得到的概率可用公式表示為：

[P（j）=1-f（j）i=1kf（i）] （12）

式中[k]為種群中的個體數目。

2） 交叉和變異操作

結合適應交叉概率[Pc]和變異概率[Pm]獲取新個體，公式為：

[Pc=k1（fmax-f'）fmax-favg， " " "f'≥favgk2， " " " " " " " " " " " " " f'lt;favg] （13）

[Pm=k3（fmax-f）fmax-favg， "f≥favgk4， " " " " " " " " " " " flt;favg] （14）

式中：[k1]、[k2]、[k3]、[k4]為任務調度的調整參數；[fmax]為適應度的最大值；[favg]為適應度的平均值；[f']為交叉的個體適應度為；[f]為變異的個體適應度。

1.3 "基于模擬退火算法的優化算法

結合遺傳算法（GA）和模擬退火算法（SAA）形成了大規模云計算網絡用戶短時需求任務調度算法（GASA）。利用遺傳算法獲取最優解后[14]，通過模擬退火算法在獲取的調度最優解附近進行局部搜索，獲取更優解；再用其代替之前的最優解，成為下次迭代過程中的最優解，再次進行迭代，記錄全部的最優解；在尋優結束后，找到大規模云計算網絡用戶短時需求任務調度最優解。利用1.2節遺傳算法的快速全局搜索能力，以及本小節模擬退火算法快速且準確的局部搜索能力，能夠高效地實現大規模云計算網絡用戶任務調度。

1.3.1 "領域函數與冷卻進度表

對1.2節中遺傳算法獲取的任務調度最優解進行局部搜索，獲取一個新的任務調度更優解。在局部搜索過程中，生成任務調度最優解的分布概率非常重要，因此，采用正態分布的方式形成最優解的候選解，最終將領域函數作為最優解的候選解。

在傳統的模擬退火算法中[15]，采用冷卻進度表控制溫度的降低幅度，若在[t]時的溫度為[T（t）]，則降溫函數可用公式表示為：

[T（t）=T0lg（1+t）] " " " " " " （15）

快速模擬退火算法的降溫函數可用公式表示為：

[T（t）=T01+t] " " " " " " " " （16）

1.3.2 "Metropolis準則

采用遺傳算法得到任務調度最優解[a]，再通過模擬退火算法產生新的最優解[b]，這些最優解被選中成為原始解的概率需遵循Metropolis準則：

令[Δf=Ffitness（（a）-Ffitness（b））]，如果[Δf≤0]，[b]將作為下一次迭代時的初始解；如果[exp（-ΔfT）]為[0，1]的一個數值，其中，目前的退火溫度為[T]，則下一次迭代過程中的初始解為[b]，否則[a]為下一次迭代過程中的最優解。

最后，在GASA算法中記錄每一次迭代過程的最優解，完成后對比全部最優解，選擇最合適的解作為大規模云計算網絡用戶短時需求任務調度輸出結果。

1.3.3 "基于GASA算法的大規模云計算網絡用戶短時需求任務調度流程

基于GASA算法的大規模云計算網絡用戶短時需求任務調度的具體操作步驟如下：

1） 確定GASA算法的種群規模、交叉和變異概率、模擬退火算法的最高迭代次數，以及模擬退火算法的初始溫度和結束時溫度。

2） 通過對個體進行編碼，生成十進制實數為種群個體，反復重復此過程直至種群規模符合要求后停止。

3） 將每個個體視為任務調度的一個可行解，通過計算各個體的適應度，將適應度最大的個體作為最優個體。

4） 將最優個體通過模擬退火算法進行操作后，使最優個體在一定溫度下處于平衡狀態。

5） 退火降溫后，判斷局部搜索后的最優個體是否符合要求，若符合要求進行下一步操作，否則，返回上一步操作。

6） 將符合要求的最優個體代替初始最優解，繼續尋優，再次迭代尋找本次迭代過程中的最優解，將其視為最終的大規模云計算網絡用戶短時需求任務調度結果，并進行記錄。

7） 判斷是否達到最大迭代次數，若已達到，結束算法，輸出大規模云計算網絡用戶短時需求任務調度結果；否則，對種群進行遺傳操作，返回步驟3）。

2 "實驗分析

2.1 "實驗環境和配置

實驗參數設置為：10～300個用戶任務，10～300個虛擬機資源節點，各用戶任務隨機分配給10～300個子任務，虛擬機資源節點用戶任務處理時間在[0，2]之間隨機表示，用戶任務需要使用虛擬機資源節點在[0，2]之間隨機表示，三種算法的參數如表1所示。

2.2 "實驗結果分析

基于實驗環境和參數，將100件任務量分配給某公司的部分員工，通過本文算法獲取大規模云計算網絡用戶短時需求任務調度結果，如圖1所示。

從圖1用戶任務調度中心的展示結果可以看出，通過本文算法對云計算網絡用戶進行任務調度，任務的執行狀態大多為成功，少數為進行中，并沒有出現任務執行失敗狀態；同時能夠清晰地看出每個任務的實際執行時間，大規模云計算網絡的任務處理效率和資源利用率有所提升，從而能夠滿足用戶的實際需求。

由于某個虛擬機資源節點在執行任務時花費的最長時間會影響到整個任務調度的性能和效率，為了進一步驗證本文算法的大規模云計算網絡用戶短時需求任務調度的有效性，將單節點最大執行時間作為評價指標，并將逆向學習行為粒子群算法、生產函數算法和本文算法進行對比，驗證三種方法的單節點最大執行時間，對比結果如圖2所示。

由圖2可以看出：隨著用戶任務數量的增加，三種算法的單節點最大執行時間也隨之增加，生產函數算法進行大規模云計算網絡用戶短時需求任務調度時，單節點最大執行時間較長，并且執行時間波動較大；通過逆向學習行為粒子群算法進行大規模云計算網絡用戶短時需求任務調度，當任務數量較少時，其單節點最大執行時間較少，而隨著用戶任務數量增多，其單節點最大執行時間顯著增大；而本文算法的單節點最大執行時間始終少于其他兩種算法，在用戶任務數量達到220時，本文算法的單節點最大執行時間約為0.27 s。

由于收斂速度和精度是評價大規模云計算網絡用戶短時需求任務調度有效性的重要指標，因此，在2.1節硬件環境的相關參數確定的基礎上，對比逆向學習行為粒子群算法、生產函數算法和本文算法的收斂速度和收斂精度，對比結果分別如圖3和表2所示。

在圖3中可以看出，生產函數算法在迭代次數為118次時停止迭代，逆向學習行為粒子群算法在迭代次數為97次時取得了最優個體，而本文算法在迭代次數為66次時就已完成迭代，獲取了本文算法的最優解，收斂速度較快。通過表2可以看出，本文算法得到的迭代最大值和迭代最小值均優于其他兩種算法，收斂精度比生產函數算法提升了19.31%，比逆向學習行為粒子群算法提升了5.4%。說明本文算法無論是收斂速度還是收斂精度均優于其他兩種算法，為大規模云計算網絡用戶短時需求任務調度提供了支持。

3 "結 "論

本文針對大規模云計算網絡用戶任務調度的問題，結合遺傳算法和模擬退火算法的快速尋優能力，實現大規模云計算網絡用戶短時需求任務調度。根據仿真軟件CloudSim得到的實驗結果能夠看出：在大規模任務下，本文算法能夠使用戶任務在短時間內高效地完成；本文算法的單節點最大執行時間、收斂速度和收斂精度均優于其他算法。

參考文獻

[1] 李衛星.基于改進共生優化算法的云計算資源調度優化[J].數學的實踐與認識，2020，50（17）：148?157.

[2] 謝劍.一種基于云計算任務神經網絡調度算法[J].現代信息科技，2021，5（13）：31?33.

[3] 楊毅，熊鷹.基于云計算平臺的多數據庫并行調度算法仿真[J].計算機仿真，2023，40（6）：459?462.

[4] 張金泉，徐壽偉，李信誠，等.基于正交自適應鯨魚優化的云計算任務調度[J].計算機應用，2022，42（5）：1516?1523.

[5] 陳孝如，曾碧卿.改進松鼠搜索算法的云計算多目標任務調度[J].計算機工程與設計，2022，43（7）：1990?1997.

[6] 賴兆林，馮翔，虞慧群.基于逆向學習行為粒子群算法的云計算大規模任務調度[J].華東理工大學學報（自然科學版），2020，46（2）：259?268.

[7] 鄧斌濤，徐勝超.基于生產函數的云計算QoS任務調度算法[J].吉林大學學報（信息科學版），2022，40（2）：295?300.

[8] 周峰.基于混合遺傳算法的通信網絡任務調度優化方法[J].長江信息通信，2023，36（4）：174?176.

[9] 黎陽，李新宇，牟健慧.基于改進模擬退火算法的大規模置換流水車間調度[J].計算機集成制造系統，2020，26（2）：366?375.

[10] 王昱，左利云.云計算中基于改進遺傳算法的多目標優化調度[J].廣東石油化工學院學報，2020，30（1）：35?39.

[11] 羅斯寧，王化龍，李弘宇，等.基于改進蟻群算法的云計算用戶任務調度算法[J].電信科學，2020，36（2）：95?100.

[12] 張銳，王隨園，張春霞，等.基于天牛須遺傳混合算法的大規模云任務調度[J].天津科技大學學報，2022，37（5）：44?49.

[13] 李文娟.改進粒子群優化算法的云計算任務調度策略[J].國外電子測量技術，2020，39（10）：55?59.

[14] 孟慶巖，王晶晶.基于混合螢火蟲遺傳算法的云計算中的任務調度優化[J].微型電腦應用，2021，37（5）：158?160.

[15] 王娟，唐秋華，毛永年.基于遺傳模擬退火算法的自動化制造單元周期調度[J].武漢科技大學學報，2020，43（4）：283?289.