云數(shù)據(jù)中心任務(wù)調(diào)度算法建模與仿真

摘要：隨著云計(jì)算技術(shù)的快速發(fā)展，云數(shù)據(jù)中心資源調(diào)度問題作為提高云資源利用率和優(yōu)化任務(wù)執(zhí)行時(shí)間的關(guān)鍵環(huán)節(jié)，受到廣泛關(guān)注。文章對(duì)云計(jì)算任務(wù)調(diào)度問題進(jìn)行建模，研究遺傳算法和蟻群算法兩種啟發(fā)式優(yōu)化算法，并在CloudSim環(huán)境下對(duì)兩種算法進(jìn)行實(shí)現(xiàn)和仿真。仿真過程中，以不同的任務(wù)數(shù)量和迭代次數(shù)為變量，對(duì)比兩種算法在時(shí)間效率上的表現(xiàn)。實(shí)驗(yàn)結(jié)果表明，遺傳算法和蟻群算法在特定條件下均能有效提升云計(jì)算任務(wù)調(diào)度的效率，且在文章仿真環(huán)境中，遺傳算法的表現(xiàn)優(yōu)于蟻群算法。

關(guān)鍵詞：任務(wù)調(diào)度；GA；ACO；Cloudsim

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2025）04-0088-04 開放科學(xué)（資源服務(wù)） 標(biāo)識(shí)碼（OSID） ：

0 引言

云計(jì)算[1]作為一種提供按需計(jì)算資源的新型服務(wù)模式，已經(jīng)成為信息技術(shù)領(lǐng)域的重要分支。在云計(jì)算環(huán)境中，任務(wù)調(diào)度是確保資源高效利用和快速響應(yīng)用戶需求的核心問題。任務(wù)調(diào)度模型的設(shè)計(jì)直接關(guān)系到云服務(wù)的性能和成本效益。因此，研究和開發(fā)高效的任務(wù)調(diào)度算法對(duì)于云數(shù)據(jù)中心的可持續(xù)發(fā)展至關(guān)重要。

傳統(tǒng)的任務(wù)調(diào)度算法，如先來先服務(wù)、時(shí)間片輪轉(zhuǎn)法等，在云數(shù)據(jù)中心的資源利用效率上存在明顯不足。近年來，智能調(diào)度算法被廣泛應(yīng)用于云數(shù)據(jù)中心任務(wù)調(diào)度過程中[2-5]，以提升數(shù)據(jù)中心資源利用率、縮短任務(wù)執(zhí)行時(shí)間，并實(shí)現(xiàn)更有效的負(fù)載均衡。然而，調(diào)度問題是一個(gè)NP完全（NP-complete） 問題，對(duì)于這類問題，不存在任何一種算法能夠在多項(xiàng)式時(shí)間內(nèi)找到問題的最優(yōu)解。遺傳算法（Genetic Algorithm，GA） [4]和蟻群算法（Ant Colony Optimization，ACO） [5]是兩種基于自然界現(xiàn)象的啟發(fā)式算法，它們?cè)诮鉀Q優(yōu)化問題方面顯示出了巨大的潛力。遺傳算法模擬了自然選擇和遺傳機(jī)制，而蟻群算法則模仿了螞蟻尋找食物的路徑選擇行為。這兩種算法在解決復(fù)雜問題時(shí)具有較好的全局搜索能力和魯棒性。本文利用CloudSim平臺(tái)，對(duì)遺傳算法和蟻群算法進(jìn)行了詳細(xì)的算法建模，并從時(shí)間效率和迭代次數(shù)兩個(gè)角度設(shè)計(jì)了仿真實(shí)驗(yàn)來評(píng)估這兩種算法在云計(jì)算任務(wù)調(diào)度中的性能。

1 云數(shù)據(jù)中心任務(wù)調(diào)度問題

在云計(jì)算的任務(wù)調(diào)度過程中，用戶的任務(wù)請(qǐng)求N 往往被劃分成n 個(gè)大小不等且相互獨(dú)立的子任務(wù)[6]，云計(jì)算資源的分配是將這n 個(gè)相互獨(dú)立的子任務(wù)分配給m個(gè)虛擬機(jī)（m＜n），圖1為云計(jì)算任務(wù)分配的模擬圖。

虛擬機(jī)VM的集合可以表示為V = { v1，v2，...vm }，任務(wù)Task的集合T = {n1，n2...nn }，中，vi（v=1，2，...m）表示第i個(gè)虛擬機(jī)資源，nj（j=1，2，...n）表示第j 個(gè)獨(dú)立的子任務(wù)。在調(diào)度過程中，虛擬機(jī)資源和子任務(wù)集合的映射關(guān)系可用布爾矩陣N 來表示，如式（1） 所示。

其中，當(dāng)元素Nij的值為1時(shí)，表示任務(wù)i 運(yùn)行在虛擬機(jī)j 上，根據(jù)不同的任務(wù)調(diào)度算法和不同的目標(biāo)函數(shù)，最后得到矩陣N 是不同的。

2 任務(wù)調(diào)度算法模型

2.1 遺傳算法

遺傳算法是由John Holland在20世紀(jì)70年代提出的一種模擬自然選擇和遺傳機(jī)制的優(yōu)化算法，常用于解決復(fù)雜的優(yōu)化問題，它通過模擬自然界的進(jìn)化過程來搜索問題的最優(yōu)解[7]。算法的流程如下。

2.1.1 選擇編碼策略

本文采用任務(wù)的直接實(shí)數(shù)編碼方式[8]，假設(shè)有m個(gè)虛擬機(jī)VM的集合為V = { v1，v2，...vm }，任務(wù)數(shù)量為n，任務(wù)Task的集合為T = { t1，t2...tn }，則遺傳算法編碼中染色體的基因串長(zhǎng)度為任務(wù)的總數(shù)n，染色體的基因值為虛擬機(jī)的編號(hào)i（1 ≤ i ≤ m），以下面的染色體序列為例：

{6，5，4，4，1，3，4，...，3，m - 3，m - 2，m }

該染色體序列表示第1個(gè)任務(wù)分配到第6個(gè)虛擬機(jī)資源上，第2個(gè)任務(wù)分配到第5個(gè)虛擬機(jī)資源上，第3、第4個(gè)任務(wù)分配到第4個(gè)資源上，第n-1個(gè)任務(wù)分配到第m-2個(gè)資源上，第n 個(gè)任務(wù)分配到第m 個(gè)資源上。這種編碼方式是遺傳算法應(yīng)用到CloudSim仿真中的最常用編碼方式，編碼簡(jiǎn)單，易于理解。

2.1.2 定義適應(yīng)度函數(shù)

從用戶的視角來看，任務(wù)的完成時(shí)間是首要考慮因素，因此將適應(yīng)度函數(shù)定義為用戶的等待時(shí)間（即任務(wù)運(yùn)行時(shí)間） ，以最小完成時(shí)間為適應(yīng)度函數(shù)。在本文中，任務(wù)的完成時(shí)間與任務(wù)運(yùn)行時(shí)間和任務(wù)的映射時(shí)間相關(guān)，具體而言，其大小與指令長(zhǎng)度以及虛擬機(jī)的帶寬和運(yùn)算速度相關(guān)，可由公式（2） 表示：

式中：Ti，j 表示任務(wù)i 在虛擬機(jī)資源j 上的執(zhí)行時(shí)間，tl和tf分別表示任務(wù)i 的指令長(zhǎng)度和文件大小，vm和vb表示虛擬機(jī)j 的帶寬和運(yùn)算速度。假設(shè)虛擬機(jī)j 上一共分配有n 個(gè)任務(wù)，則虛擬機(jī)j 完成這些任務(wù)的時(shí)間可以表示為：

由于不同的虛擬機(jī)上分配的任務(wù)數(shù)量不同，因此完成時(shí)間最長(zhǎng)的虛擬機(jī)所需的時(shí)間則表示在這種編碼方式下完成所有任務(wù)所需的最短時(shí)間，可以表示為：

Tmin = max（Tj ） （1≤j≤m） （4）

當(dāng)任務(wù)的執(zhí)行時(shí)間越小時(shí)，算法的適應(yīng)度越大，因此當(dāng)適應(yīng)度值越大時(shí)，此時(shí)遺傳算法染色體序列越好。適應(yīng)度函數(shù)的定義如公式（5） 所示：

F = 1 ／Tmin （5）

2.1.3 確定遺傳策略

本文所使用的遺傳算法在基礎(chǔ)遺傳算法的3種算子上做了適當(dāng)調(diào)整，將選擇和交叉兩種操作合并。這樣能夠在縮短迭代時(shí)間的同時(shí)保持種群的搜索范圍。選擇過程中采用輪盤賭法，根據(jù)染色體的適應(yīng)度進(jìn)行選擇，生成兩個(gè)臨時(shí)染色體S1 和S2。具體而言，首先計(jì)算總適應(yīng)度totalScore，然后隨機(jī)生成一個(gè)小于to?talScore的值slice，遍歷種群并累加染色體適應(yīng)度，當(dāng)累加值超過slice時(shí)，選擇當(dāng)前染色體。隨后對(duì)選中的染色體進(jìn)行交叉操作，通過隨機(jī)生成兩個(gè)交叉點(diǎn)a 和b，交換S1 與S2 在交叉區(qū)間內(nèi)的基因，從而生成具有新組合特征的子代染色體S3 和S4。此區(qū)間交叉操作的核心機(jī)制如圖2所示。

變異是通過對(duì)當(dāng)前種群的遍歷，根據(jù)變異率P 和變異步長(zhǎng)進(jìn)行隨機(jī)變異，以擴(kuò)大種群的搜索范圍。變異操作有助于增加種群的多樣性，防止算法過早收斂到局部最優(yōu)解。

2.1.4 初始化

規(guī)定種群大小為popSize，隨機(jī)初始化生成第一代種群P；計(jì)算種群P 中每個(gè)個(gè)體染色體的適應(yīng)度值；按照遺傳策略，運(yùn)用選擇（交叉） 和變異算子作用于群體，形成下一代群體；當(dāng)滿足迭代次數(shù)時(shí)，程序結(jié)束。

2.2 蟻群算法

蟻群算法（Ant Colony Optimization，ACO） 是由Marco Dorigo等人于1991年提出的一種啟發(fā)式算法[5]。蟻群的個(gè)體之間通過信息素進(jìn)行交流，通過簡(jiǎn)單個(gè)體組成群體完成復(fù)雜的工作，從而達(dá)到尋找最優(yōu)解的目的[9]。這種正反饋機(jī)制使得螞蟻能夠發(fā)現(xiàn)并利用最短的路徑到達(dá)食物源。以下是本文蟻群算法實(shí)現(xiàn)的參數(shù)設(shè)置和基本流程。

2.2.1 初始化

設(shè)置算法參數(shù)，包括信息素矩陣、螞蟻數(shù)量、參數(shù)α（信息素的重要程度） 、參數(shù)β（啟發(fā)式因子的重要程度） 、信息素蒸發(fā)率等，如表1所示。初始化各條路徑上的信息素濃度，隨機(jī)放置一定數(shù)量的螞蟻到問題的解空間中。

2.2.2 狀態(tài)轉(zhuǎn)移規(guī)則

每只螞蟻從當(dāng)前位置出發(fā)，采用輪盤法，根據(jù)信息素濃度和啟發(fā)式信息計(jì)算每個(gè)任務(wù)在不同虛擬機(jī)上運(yùn)行的概率，如式（6） 所示。根據(jù)輪盤賭策略選擇適應(yīng)度函數(shù)值較大的個(gè)體，作為下一個(gè)位置。這個(gè)過程將生成一個(gè)完整的路徑，即任務(wù)的調(diào)度方案。

式中：pk ij （t）為t時(shí)刻第k只螞蟻選擇任務(wù)i在虛擬機(jī)j 上運(yùn)行的概率大小；τij （t） 是任務(wù)i 在虛擬機(jī)j 上運(yùn)行的信息素濃度大小，其值由信息素濃度矩陣得到；α和β 作為信息素和啟發(fā)因子的影響程度，可根據(jù)實(shí)際情況調(diào)整，本文視兩者影響程度相同，取相等的值；Dij （t）作為概率p的第二個(gè)影響因子（即啟發(fā)式影響因子） ，代表t 時(shí)刻任務(wù)i 在虛擬機(jī)j 上運(yùn)行所需的時(shí)間代價(jià)，其計(jì)算方式為虛擬機(jī)j 上所有任務(wù)的執(zhí)行時(shí)間與任務(wù)i 映射在虛擬機(jī)j 上的時(shí)間之和，可由公式（7） 表示：

式中：vm和vb表示編號(hào)為j 的虛擬機(jī)的帶寬和運(yùn)算速度，tif和tl 表示任務(wù)i 的文件大小和指令長(zhǎng)度，T 表示在t 時(shí)刻虛擬機(jī)j 上的所有任務(wù)的指令長(zhǎng)度之和。假設(shè)在t 時(shí)刻虛擬j 上任務(wù)數(shù)量為n，則T 的表示為：

2.2.3 更新禁忌列表（Tabu List）

為了增加搜索的多樣性，為每個(gè)螞蟻設(shè)置禁忌列表tabu，tabuk（k=1，2，...，m）為第k 只螞蟻的禁忌列表[10]，將已經(jīng)選擇的路徑（虛擬機(jī)資源） 加入禁忌列表中，避免螞蟻在接下來的迭代中選擇重復(fù)的任務(wù)。

2.2.4 計(jì)算解的質(zhì)量

根據(jù)問題的目標(biāo)函數(shù)計(jì)算螞蟻所構(gòu)建路徑的質(zhì)量。通過計(jì)算每一代螞蟻所通過路徑的時(shí)間，判斷螞蟻是否找到更優(yōu)的解。任務(wù)的完成時(shí)間與遺傳算法的計(jì)算方式一致，均與任務(wù)執(zhí)行時(shí)間和任務(wù)的映射時(shí)間相關(guān)，如遺傳算法中公式（2） 所示。

2.2.5 更新信息素

根據(jù)t 時(shí)刻螞蟻所找到的解的質(zhì)量，計(jì)算每只螞蟻新發(fā)出的信息素濃度并求和。同時(shí)，應(yīng)用信息素的揮發(fā)機(jī)制，減少所有路徑上的信息素濃度，以避免算法過早收斂，更新方式如公式（9） 所示。

τij （t + 1） = （1 - ρ）τij + Δτij （t） （9）

式中：τij （t + 1）為更新后的信息素濃度矩陣，1-ρ是信息素的殘留系數(shù)，Δτij （t）用來計(jì)算所有螞蟻個(gè)體更新的信息素之和，其計(jì)算方式為：

Δτk ij （t）表示在t 時(shí)刻第k 只螞蟻的信息素變化量，由下式計(jì)算得到：

式中：tourk ij （t） 為t 時(shí)刻第k 只螞蟻在這一次迭代過程中走的路徑所用的總時(shí)間。

3 性能對(duì)比

實(shí)驗(yàn)采用CloudSim 5.0模擬云計(jì)算環(huán)境。Cloud?Sim是由墨爾本大學(xué)的Buyya教授帶領(lǐng)研究團(tuán)隊(duì)推出的一款云計(jì)算仿真工具[11]。通過重寫DatacenterBro?ker類中的bindCloudletToVm方法，根據(jù)不同算法最后得到的虛擬機(jī)與子任務(wù)的映射序列，將各個(gè)子任務(wù)分配給其對(duì)應(yīng)的虛擬機(jī)，隨后開始仿真。仿真環(huán)境中虛擬機(jī)和任務(wù)的參數(shù)設(shè)置如表2所示。

實(shí)驗(yàn)一在相同虛擬機(jī)數(shù)量下對(duì)GA、ACO和FCFS 算法的任務(wù)完成時(shí)間進(jìn)行比較分析。實(shí)驗(yàn)中虛擬機(jī)數(shù)量固定為5個(gè)，GA和ACO算法的迭代次數(shù)設(shè)定為100次，任務(wù)的指令數(shù)和長(zhǎng)度按照表2所給的任務(wù)參數(shù)范圍進(jìn)行限定。實(shí)驗(yàn)隨機(jī)生成10、25、50、100、200 和400個(gè)任務(wù)，為防止出現(xiàn)偶然誤差，在每個(gè)任務(wù)量下進(jìn)行100次實(shí)驗(yàn)并取平均值，得到其平均完成時(shí)間。實(shí)驗(yàn)結(jié)果匯總于表3，任務(wù)完成時(shí)間如圖3所示。

由實(shí)驗(yàn)一可以看出，傳統(tǒng)的FCFS調(diào)度策略在大任務(wù)量的情況下耗時(shí)較大。兩種智能算法在迭代100 次的情況下且任務(wù)量少于100時(shí)，任務(wù)的完成時(shí)間相差不大；在任務(wù)量超過100時(shí)，本文中的遺傳算法的尋優(yōu)能力略優(yōu)于蟻群算法，體現(xiàn)出一種任務(wù)量越多，遺傳算法的性能越好的趨勢(shì)。通過對(duì)表3實(shí)驗(yàn)數(shù)據(jù)的分析，發(fā)現(xiàn)遺傳算法的最優(yōu)解和最差解的區(qū)間比蟻群算法小，蟻群算法的波動(dòng)較大。這是因?yàn)檫z傳算法利用種群和遺傳操作（如交叉、變異） 來探索解空間，通常能保持較為穩(wěn)定的進(jìn)化過程，從而使最優(yōu)解和最差解的區(qū)間較小。相反，蟻群算法通過模擬螞蟻的行為和信息素更新來進(jìn)行搜索，雖然在局部搜索中具有較高的靈活性和適應(yīng)性，但其信息素的隨機(jī)性和更新機(jī)制可能導(dǎo)致解的波動(dòng)較大。信息素的分布不均和更新策略可能導(dǎo)致算法在不同迭代中經(jīng)歷較大的變化，從而使最優(yōu)解和最差解的區(qū)間出現(xiàn)較大的波動(dòng)。

實(shí)驗(yàn)二在虛擬機(jī)環(huán)境下，任務(wù)數(shù)量固定為1000 個(gè)，通過調(diào)整迭代次數(shù)來評(píng)估兩種算法的收斂性。每種迭代設(shè)置下進(jìn)行了100次獨(dú)立實(shí)驗(yàn)，并取其平均值，實(shí)驗(yàn)結(jié)果如圖4所示。

通過實(shí)驗(yàn)二可以看出，在完成大規(guī)模任務(wù)的情況下，文中描述的算法在迭代初期，蟻群算法的效率較高，這是因?yàn)橄伻核惴ǖ亩鄠€(gè)螞蟻一開始就可以搜索多條路徑。隨著迭代次數(shù)的增加，遺傳算法的效率逐漸提高，在迭代次數(shù)較少的情況下即可找到較好的解，說明在復(fù)雜的大任務(wù)優(yōu)化問題中，遺傳算法的尋優(yōu)能力優(yōu)于蟻群算法。GA的全局搜索能力可以幫助更快地找到較優(yōu)解，而ACO在信息素機(jī)制不當(dāng)?shù)那闆r下容易陷入局部最優(yōu)。

4 結(jié)束語(yǔ)

本文對(duì)數(shù)據(jù)中心云計(jì)算任務(wù)調(diào)度模型進(jìn)行了建模，完成了蟻群算法和遺傳算法這兩種啟發(fā)式算法在CloudSim中的實(shí)現(xiàn)與仿真。這兩種算法的可變參數(shù)較多，通過合理地改變這些參數(shù)的大小，可以在不同情況下發(fā)揮出不同的效率。通過實(shí)驗(yàn)驗(yàn)證，在本文仿真環(huán)境中，遺傳算法的時(shí)間效率和迭代效率均優(yōu)于蟻群算法。下一步研究工作是對(duì)遺傳算法進(jìn)行進(jìn)一步改進(jìn)，利用粒子群算法的全局搜索能力，在遺傳算法迭代一次之后，對(duì)遺傳算法選擇的部分解進(jìn)行一定概率的粒子群算法優(yōu)化，從而使搜索范圍進(jìn)一步擴(kuò)大，期望能夠更快地找到更優(yōu)的解，以縮短云數(shù)據(jù)中心任務(wù)的執(zhí)行時(shí)間并提高資源利用率。

參考文獻(xiàn)：

[1] 劉陳偉，孫鑒，雷冰冰，等.基于改進(jìn)粒子群算法的云數(shù)據(jù)中心能耗優(yōu)化任務(wù)調(diào)度策略[J].計(jì)算機(jī)科學(xué)，2023，50（7）：246-253.

[2] LI K，XU G，ZHAO G，et al.Cloud task scheduling based on loadbalancing ant colony optimization[C]//Proceedings of the 2011Sixth Annual ChinaGrid Conference.Dalian：IEEE Press，2011：3-9.

[3] GEORGE N，CHANDRASEKARAN K，BINU A.Optimizationawarescheduling in cloud computing[C]//Proceedings of theSecond International Conference on Information and Communi?cation Technology for Competitive Strategies.New York：ACMPress，2016：1-6.

[4] HOLLAND J H.Adaptation in natural and artificial systems：anintroductory analysis with applications to biology，control，and ar?tificial intelligence[M].Cambridge：MIT Press，1992.

[5] DORIGO M，DI CARO G.Ant colony optimization：a new metaheuristic[C]//Proceedings of the 1999 Congress on EvolutionaryComputation-CEC99.Washington，DC：IEEE Press，1999：1470-1477.

[6] 王登科，李忠.基于粒子群優(yōu)化與蟻群優(yōu)化的云計(jì)算任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用與軟件，2013，30（1）：290-293.

[7] 鄧德康.基于啟發(fā)式算法的任務(wù)調(diào)度研究[D].南寧：廣西大學(xué)，2023.

[8] 楊博，劉樹東，魯維佳，等.改進(jìn)遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用[J].現(xiàn)代制造工程，2022（6）：9-16.

[9] 朱嘉豪，鄭巍，楊豐玉，等.基于蟻群算法優(yōu)化反向傳播神經(jīng)網(wǎng)絡(luò)的軟件質(zhì)量預(yù)測(cè)[J].計(jì)算機(jī)應(yīng)用，2023，43（11）：3568-3573.

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

[11] 孫鳳杰，王克儉，何振學(xué)，等.基于煙花算法的云計(jì)算任務(wù)調(diào)度研究[J].計(jì)算機(jī)仿真，2022，39（3）：340-343，443.

【通聯(lián)編輯：謝媛媛】

基金項(xiàng)目：甘肅省教育廳創(chuàng)新基金（項(xiàng)目編號(hào)：2021B-197） ；天水師范學(xué)院2023 年創(chuàng)新基金專項(xiàng)項(xiàng)目（項(xiàng)目編號(hào)：CXJ2023-11）