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

關鍵詞： 云計算網(wǎng)絡； 用戶短時需求； 任務調(diào)度； 遺傳算法； 模擬退火算法； 收斂速度； 最大執(zhí)行時間

中圖分類號： 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 "引 "言

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

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

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

1 "云計算網(wǎng)絡用戶短時需求任務調(diào)度優(yōu)化算法

1.1 "大規(guī)模云計算網(wǎng)絡任務調(diào)度模型

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

N個用戶任務集合：

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

M個虛擬機資源節(jié)點：

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

M個虛擬機的計算速度：

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

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

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

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

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

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

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

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

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

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

1.2 "基于遺傳算法的云計算網(wǎng)絡任務調(diào)度

1.2.1 "個體編解碼

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

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

通過遺傳算法完成個體的編碼后，需要進行最優(yōu)個體的解碼，獲取大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度的方案，第[j]個用戶子任務在第[i]個虛擬機資源節(jié)點上執(zhí)行時間矩陣為[ET]，各虛擬機資源節(jié)點的所有執(zhí)行任務時間為：

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

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

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

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

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

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

式中[task]為用戶任務數(shù)目。

1.2.2 "適應度函數(shù)

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

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

1.2.3 "遺傳操作

1） 選擇操作

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

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

式中[k]為種群中的個體數(shù)目。

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]為任務調(diào)度的調(diào)整參數(shù)；[fmax]為適應度的最大值；[favg]為適應度的平均值；[f']為交叉的個體適應度為；[f]為變異的個體適應度。

1.3 "基于模擬退火算法的優(yōu)化算法

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

1.3.1 "領域函數(shù)與冷卻進度表

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

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

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

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

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

1.3.2 "Metropolis準則

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

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

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

1.3.3 "基于GASA算法的大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度流程

基于GASA算法的大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度的具體操作步驟如下：

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

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

3） 將每個個體視為任務調(diào)度的一個可行解，通過計算各個體的適應度，將適應度最大的個體作為最優(yōu)個體。

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

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

6） 將符合要求的最優(yōu)個體代替初始最優(yōu)解，繼續(xù)尋優(yōu)，再次迭代尋找本次迭代過程中的最優(yōu)解，將其視為最終的大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度結果，并進行記錄。

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

2 "實驗分析

2.1 "實驗環(huán)境和配置

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

2.2 "實驗結果分析

基于實驗環(huán)境和參數(shù)，將100件任務量分配給某公司的部分員工，通過本文算法獲取大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度結果，如圖1所示。

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

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

由圖2可以看出：隨著用戶任務數(shù)量的增加，三種算法的單節(jié)點最大執(zhí)行時間也隨之增加，生產(chǎn)函數(shù)算法進行大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度時，單節(jié)點最大執(zhí)行時間較長，并且執(zhí)行時間波動較大；通過逆向?qū)W習行為粒子群算法進行大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度，當任務數(shù)量較少時，其單節(jié)點最大執(zhí)行時間較少，而隨著用戶任務數(shù)量增多，其單節(jié)點最大執(zhí)行時間顯著增大；而本文算法的單節(jié)點最大執(zhí)行時間始終少于其他兩種算法，在用戶任務數(shù)量達到220時，本文算法的單節(jié)點最大執(zhí)行時間約為0.27 s。

由于收斂速度和精度是評價大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度有效性的重要指標，因此，在2.1節(jié)硬件環(huán)境的相關參數(shù)確定的基礎上，對比逆向?qū)W習行為粒子群算法、生產(chǎn)函數(shù)算法和本文算法的收斂速度和收斂精度，對比結果分別如圖3和表2所示。

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

3 "結 "論

本文針對大規(guī)模云計算網(wǎng)絡用戶任務調(diào)度的問題，結合遺傳算法和模擬退火算法的快速尋優(yōu)能力，實現(xiàn)大規(guī)模云計算網(wǎng)絡用戶短時需求任務調(diào)度。根據(jù)仿真軟件CloudSim得到的實驗結果能夠看出：在大規(guī)模任務下，本文算法能夠使用戶任務在短時間內(nèi)高效地完成；本文算法的單節(jié)點最大執(zhí)行時間、收斂速度和收斂精度均優(yōu)于其他算法。

參考文獻

[1] 李衛(wèi)星.基于改進共生優(yōu)化算法的云計算資源調(diào)度優(yōu)化[J].數(shù)學的實踐與認識，2020，50（17）：148?157.

[2] 謝劍.一種基于云計算任務神經(jīng)網(wǎng)絡調(diào)度算法[J].現(xiàn)代信息科技，2021，5（13）：31?33.

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

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

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

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

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

[8] 周峰.基于混合遺傳算法的通信網(wǎng)絡任務調(diào)度優(yōu)化方法[J].長江信息通信，2023，36（4）：174?176.

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

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

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

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

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

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

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