大規(guī)模云計算網(wǎng)絡(luò)用戶短時需求任務(wù)調(diào)度優(yōu)化算法

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

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

中圖分類號： TN919?34； TP311 " " " " " " " " " 文獻標(biāo)識碼： 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 "引 "言

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

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

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

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

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

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

N個用戶任務(wù)集合：

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

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

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

M個虛擬機的計算速度：

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

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

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

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

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

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

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

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

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

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

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

1.2.1 "個體編解碼

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

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

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

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

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

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

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

用戶任務(wù)的平均完成時間表示為：

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

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

1.2.2 "適應(yīng)度函數(shù)

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

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

1.2.3 "遺傳操作

1） 選擇操作

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

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

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

2） 交叉和變異操作

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

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

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

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

對1.2節(jié)中遺傳算法獲取的任務(wù)調(diào)度最優(yōu)解進行局部搜索，獲取一個新的任務(wù)調(diào)度更優(yōu)解。在局部搜索過程中，生成任務(wù)調(diào)度最優(yōu)解的分布概率非常重要，因此，采用正態(tài)分布的方式形成最優(yōu)解的候選解，最終將領(lǐng)域函數(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準(zhǔn)則

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

令[Δ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)絡(luò)用戶短時需求任務(wù)調(diào)度輸出結(jié)果。

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

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

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

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

3） 將每個個體視為任務(wù)調(diào)度的一個可行解，通過計算各個體的適應(yīng)度，將適應(yīng)度最大的個體作為最優(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)絡(luò)用戶短時需求任務(wù)調(diào)度結(jié)果，并進行記錄。

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

2 "實驗分析

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

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

2.2 "實驗結(jié)果分析

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

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

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

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

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

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

3 "結(jié) "論

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

參考文獻

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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