于淑香，周洪斌

（沙洲職業(yè)工學(xué)院 電子信息工程系，江蘇 張家港 215600）

引言

云計算是網(wǎng)格計算、并行計算和分布式計算等多種技術(shù)的融合[1]，其本質(zhì)是把各地的計算機(jī)資源及相關(guān)的終端設(shè)備等組織在網(wǎng)絡(luò)“云”中，為廣大用戶提供軟件、存儲、計算和大數(shù)據(jù)的訪問使用等服務(wù)。云計算系統(tǒng)是采用多種技術(shù)把“云”中各種資源進(jìn)行重組形成一個巨大的資源庫，方便隨用隨取，解決了當(dāng)前大數(shù)據(jù)時代，激增的數(shù)據(jù)量和計算機(jī)有限的硬件水平及處理能力的矛盾。云計算的使用類似居民用水電一樣“按需使用，按量付費(fèi)”，具有較高靈活性和可靠性。高效的任務(wù)調(diào)度和合理資源分配是提高云計算系統(tǒng)性能的重點(diǎn)和難點(diǎn)，這些技術(shù)的提高能使云計算系統(tǒng)更好地滿足客戶需求，降低能源消耗，提高企業(yè)效益。

資源調(diào)度模型的發(fā)展過程分為兩個階段，啟發(fā)式算法和傳統(tǒng)的資源調(diào)度算法。啟發(fā)式算法主要根據(jù)非線性理論和人工智能理論，模擬生物的自然行為尋找一些資源調(diào)度問題的最優(yōu)解[2]。而傳統(tǒng)的資源調(diào)度算法有先來先服務(wù)，貪心法、輪轉(zhuǎn)調(diào)度，最大最小等算法。很多專家和學(xué)者研究實(shí)驗(yàn)表明，在云計算任務(wù)調(diào)度中，使用啟發(fā)式算法明顯優(yōu)于傳統(tǒng)的資源調(diào)度算法，具有不可比擬的優(yōu)越性。

1 云計算任務(wù)調(diào)度模型

1.1 云計算的編程模型

云計算系統(tǒng)包含很多復(fù)雜和結(jié)構(gòu)迥異的資源，最優(yōu)的任務(wù)調(diào)度方案能保證快速完成用戶任務(wù)并且提高系統(tǒng)的效率和利用率。當(dāng)前的云計算系統(tǒng)大部分選用Map/Reduce思想的編程模型[3]，該模型特別適合應(yīng)用于云計算系統(tǒng)中大規(guī)模數(shù)據(jù)集的產(chǎn)生和處理。任務(wù)調(diào)度模型如圖1所示。

圖1任務(wù)調(diào)度模型

云計算系統(tǒng)中有巨大的用戶量和任務(wù)量，在用戶提交任務(wù)后，任務(wù)調(diào)度系統(tǒng)首先要進(jìn)行任務(wù)分布式化，即切分任務(wù)，把用戶提交的任務(wù)集切分成多個子任務(wù)；子任務(wù)提交給調(diào)度中心后，根據(jù)映射法則的算法，把每個子任務(wù)調(diào)度分配給虛擬資源節(jié)點(diǎn)。

1.2 任務(wù)調(diào)度的相關(guān)定義

按照相關(guān)的算法將N個用戶任務(wù)分配到M個虛擬資源節(jié)點(diǎn)上（M＜N），云計算環(huán)境下任務(wù)的數(shù)學(xué)模型表示如下：

⑴T={T1，T2，……Tn}表示N個待執(zhí)行獨(dú)立任務(wù)的集合。

⑵V={V1，V2，……Vm}表示M個虛擬機(jī)資源節(jié)點(diǎn)。

⑶MIPS={MIPSl，MIPS2，……，MIPSm}表示M個虛擬機(jī)的計算能力，即計算速度，MIPSi表示虛擬機(jī)Vi單位時間內(nèi)處理的指令數(shù)，以百萬/秒計。

⑷任務(wù)和虛擬機(jī)節(jié)點(diǎn)之間的映射關(guān)系如矩陣M表示，若任務(wù)Ti被分配到虛擬機(jī)Vj上執(zhí)行調(diào)度，則矩陣中的元素Mij=1，否則Mij=0。

⑸任務(wù)的期望執(zhí)行時間，即第j個子任務(wù)在第i個虛擬機(jī)上執(zhí)行時間。

由上述矩陣，可以計算出每個虛擬機(jī)Vi執(zhí)行子任務(wù)的時間，如公式（1）所示。

公式中n表示虛擬機(jī)Vi執(zhí)行的子任務(wù)數(shù)量，Time(i,j)表示虛擬機(jī)Vi上的第j個子任務(wù)執(zhí)行時間。

2 改進(jìn)蟻群優(yōu)化算法

蟻群算法是學(xué)者M(jìn)r.Dorigo等提出的，該算法受自然界中螞蟻的覓食行為過程啟發(fā)而提出。該算法具有啟發(fā)式、正反饋和分布式的搜索特點(diǎn)，在許多NP類問題的優(yōu)化求解過程中被普遍應(yīng)用，如模式識別、旅行商問題、車輛調(diào)度、多重背包等。隨著算法應(yīng)用演變發(fā)展，出現(xiàn)了更接近現(xiàn)實(shí)的模擬螞蟻覓食過程的算法，即蟻群優(yōu)化算法。

2.1 蟻群優(yōu)化算法原理

設(shè)螞蟻數(shù)量是n，在尋找食物經(jīng)過的路徑上，螞蟻會留下信息素，而后來的螞蟻會依據(jù)在此路徑上走過的螞蟻留下信息素濃度去選擇合適的路徑，即每只螞蟻會根據(jù)一定的概率轉(zhuǎn)移到下一個虛擬機(jī)資源節(jié)點(diǎn)，在t時刻，第k只螞蟻從虛擬機(jī)Vi訪問虛擬機(jī)Vj的概率計算如公式（2）所示。

其中:τij表示路徑(i,j)上的信息素濃度，α表示螞蟻對信息素的敏感度；β表示蟻群對信息素的敏感度，ηij表示節(jié)點(diǎn)j對節(jié)點(diǎn)i上螞蟻的吸引水平，即啟發(fā)因子，allowedk表示還沒有訪問的節(jié)點(diǎn)。

在不斷尋找食物的過程中,螞蟻在路徑上留下的初始信息素會陸續(xù)散發(fā)掉,同時又會在路徑上繼續(xù)釋放出新的信息素，所以為了有利于發(fā)現(xiàn)最優(yōu)的解，在蟻群優(yōu)化算法中，要更新路徑上的信息素，全局和局部的信息素更新如公式（3）所示。

其中:ρ ∈(0,1]表示信息素?fù)]發(fā)系數(shù)，Δτij(t)表示所有m只螞蟻釋放在路徑上的信息素總量(t)表示在路徑(i,j)上第k只螞蟻釋放信息素的增量，計算信息素增量如公式（4）所示。

其中，Q表示一次搜索結(jié)束后路徑上存留信息素的總量；Lk表示螞蟻k走過路徑總長度。

2.2 蟻群優(yōu)化算法的改進(jìn)

2.2.1 信息素初始化

在初始時刻，利用蟻群優(yōu)化算法原理將螞蟻（任務(wù)）隨機(jī)的放到云計算系統(tǒng)中的任意一個虛擬機(jī)上。此虛擬機(jī)處理器的數(shù)量為v_num。各處理器的處理能力v_pc，通信帶寬能力v_bw等參數(shù)。利用這些參數(shù)指標(biāo)，云計算系統(tǒng)可以初始化每個虛擬機(jī)的信息素值，計算如公式(5)所示。

其中虛擬機(jī)i的指標(biāo)如下：τi()0是信息素初始值，v_numi是處理器的數(shù)量，v_pci是處理器的處理能力（即MIPS），v_bwi是通信帶寬[4]。

2.2.2 選擇虛擬機(jī)概率

在改進(jìn)算法中，螞蟻（任務(wù)）從虛擬機(jī)Vi訪問虛擬機(jī)Vj的概率計算如公式（6）所示。

式中，q0∈(0，1)是給定的參數(shù)，q為(0，1)范圍內(nèi)的隨機(jī)數(shù)。當(dāng) q＜q0時，j取 MAX{allowedk}中的k，能夠得到使邊(i,k)距離i最短、信息素最高的節(jié)點(diǎn)作為下一節(jié)點(diǎn)[5]。

當(dāng)q＞q0時，啟發(fā)信息函數(shù)ηij表示任務(wù)i選擇虛擬機(jī)j的期望值。在此取ηij=propertyj*LLj,其中propertyj是固定值等于τi()0的值,其計算如公式（5）所示，LLj是虛擬機(jī)負(fù)載能力的衡量值，其值高低代表虛擬機(jī)當(dāng)前狀態(tài)下處理能力的高低，當(dāng)該值比較高時，被選擇的概率就更大。LLj的計算如公式（7）所示。

其中AVTime表示截止到前一次迭代結(jié)束時，在最優(yōu)路徑中的每個虛擬機(jī)Vi的平均執(zhí)行時間。

2.2.3 信息素更新

在螞蟻選中路徑(i,j)后，立即按公式（8）局部更新路徑(i,j)上的信息素。

式中，ρ是信息素的揮發(fā)因子，且ρ∈(0，1]，信息素的殘留濃度用1-ρ表示，ρ值越大，散發(fā)越快，則殘余濃度越低，所以曾探尋過的路徑對選擇當(dāng)前路徑的影響相對較小。信息素的增量用Δτij()t表示，第k只螞蟻在本次迭代中經(jīng)過路徑的長度用Lk表示[6]。

在螞蟻確定選擇某一路徑后應(yīng)減少該條路徑上的信息素，同時增加其余路徑邊被選擇的概率，當(dāng)所有螞蟻都走完一次循環(huán)之后，根據(jù)式（9）全局更新信息素，進(jìn)而使最佳路徑的搜索概率更大[5]。

公式中，Lgbest是此刻得到的最優(yōu)路徑。

2.3 算法描述

⑴算法參數(shù)初始化，包括云計算虛擬機(jī)節(jié)點(diǎn)數(shù)，任務(wù)數(shù)，信息素和迭代次數(shù)等各參數(shù)。

⑵將X只螞蟻隨機(jī)放置在虛擬機(jī)節(jié)點(diǎn)上。

⑶計算出螞蟻個體轉(zhuǎn)移到下一虛擬機(jī)節(jié)點(diǎn)的概率，并根據(jù)計算結(jié)果進(jìn)行移動。

⑷局部更新螞蟻?zhàn)哌^路徑上的信息素值，并修改相應(yīng)的禁忌表。

⑸重復(fù)步驟2)～4)，直到蟻群中的每個螞蟻個體找到一條可行的路徑截止。

⑹全局更新所有路徑的信息素。

⑺增加迭代次數(shù)，如其值已達(dá)預(yù)設(shè)的最大迭代次數(shù)，則停止搜索，獲得云計算任務(wù)調(diào)度的最優(yōu)解。

3 仿真實(shí)驗(yàn)及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

為了驗(yàn)證改進(jìn)蟻群算法在云計算系統(tǒng)中任務(wù)調(diào)度分配優(yōu)化效果，本文選用澳大利亞墨爾本大學(xué)和Gridbus項目共同提出的云仿真軟件CloudSim平臺進(jìn)行測試實(shí)驗(yàn)[7]，實(shí)驗(yàn)的硬件環(huán)境為2.66GHz的CPU，8G的內(nèi)存，500G硬盤作為硬件環(huán)境，Windows10操作系統(tǒng)和JDK8.0的基礎(chǔ)環(huán)境及Antl.9.7的編譯工具。在CloudSim平臺中對比測試本文改進(jìn)蟻群優(yōu)化任務(wù)調(diào)度算法、標(biāo)準(zhǔn)蟻群算法和MAX-MIN算法在任務(wù)調(diào)度分配執(zhí)行方面的效率。通過初始化CloudSim，創(chuàng)建數(shù)據(jù)中心及DataCenterBroker,創(chuàng)建虛擬機(jī)、云任務(wù)集等一系列的操作后開始仿真實(shí)驗(yàn)。

3.2 結(jié)果分析

仿真實(shí)驗(yàn)主要測試在任務(wù)數(shù)量增加的情況下，本文算法的任務(wù)平均完成時間，并與其他比較算法進(jìn)行對比，公平起見所有測試的算法都進(jìn)行10次實(shí)驗(yàn)，統(tǒng)計平均，橫坐標(biāo)為申請任務(wù)數(shù)量，縱坐標(biāo)為各算法分別完成任務(wù)處理所需時間。在實(shí)驗(yàn)軟硬件環(huán)境相同，資源節(jié)點(diǎn)相同的情況下，幾種算法的任務(wù)完成時間對比如圖2所示。

圖2各算法任務(wù)執(zhí)行時間對比

在文件任務(wù)量不大情況下，各算法完成任務(wù)分配執(zhí)行所用時間差別不大，但從整體上來看，任務(wù)量相同時本文改進(jìn)蟻群優(yōu)化算法執(zhí)行任務(wù)用時比較短。而隨著任務(wù)數(shù)量的增加，本文算法完成任務(wù)時間增幅度不大，相反另外兩種比較算法的執(zhí)行時間增加幅度非常大。同時在實(shí)驗(yàn)中發(fā)現(xiàn)本文算法的迭代次數(shù)少于其他比較算法，這是因?yàn)楸疚乃惴ǔ晒Φ乇苊饬藗鹘y(tǒng)蟻群優(yōu)化算法容易陷入局部最優(yōu)解的缺點(diǎn)，這樣可以使用戶提交的任務(wù)在相應(yīng)的資源節(jié)點(diǎn)最快分配執(zhí)行完成，提高云計算系統(tǒng)的工作效率，取得了比較理想的資源任務(wù)調(diào)度效果。

4 結(jié)語

本文提出了基于改進(jìn)蟻群優(yōu)化算法的云計算任務(wù)調(diào)度算法。首先介紹了云計算系統(tǒng)的編程模型和任務(wù)調(diào)度相關(guān)定義，然后針對傳統(tǒng)蟻群優(yōu)化算法進(jìn)行改進(jìn)，并在CloudSim平臺測試該算法在云計算系統(tǒng)任務(wù)調(diào)度中的性能。仿真實(shí)驗(yàn)結(jié)果表明，該算法在云計算系統(tǒng)任務(wù)調(diào)度方面有較好的性能，提高了資源的利用率。