王云松，孫佳林，龔躍

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130022）

基于蟻群算法的云任務(wù)調(diào)度研究

王云松，孫佳林，龔躍

（長(zhǎng)春理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，長(zhǎng)春 130022）

針對(duì)云計(jì)算中任務(wù)分配算法效率不高的問(wèn)題，提出了一種改進(jìn)的蟻群算法來(lái)解決云計(jì)算中的任務(wù)分配問(wèn)題。首先假定要分配的任務(wù)為螞蟻的起點(diǎn)，執(zhí)行任務(wù)的虛擬機(jī)為螞蟻的終點(diǎn)，任務(wù)分配的過(guò)程就是螞蟻從起點(diǎn)走到終點(diǎn)的過(guò)程。然后隨機(jī)選擇一個(gè)任務(wù)作為螞蟻的起點(diǎn)，用改進(jìn)的蟻群算法計(jì)算后把任務(wù)分配給相應(yīng)的虛擬機(jī)，直到所有任務(wù)都分配完成。最后當(dāng)所有螞蟻都把任務(wù)分配完成后，選擇代價(jià)最小的路徑作為本次任務(wù)分配的方案。通過(guò)使用cloudsim仿真器進(jìn)行仿真實(shí)驗(yàn)，證明了蟻群算法能夠有效的解決云計(jì)算中任務(wù)分配的問(wèn)題。

蟻群算法；云計(jì)算；任務(wù)分配；cloudsim

任務(wù)分配是云計(jì)算［1-2］中的關(guān)鍵問(wèn)題，近些年來(lái)人們也提出了很多種任務(wù)分配的方法。這些任務(wù)調(diào)度方法大致分為兩類(lèi)：基于效率的調(diào)度算法和基于公平的調(diào)度算法?；谛实恼{(diào)度算法有傳統(tǒng)的輪詢(xún)調(diào)度算法、啟發(fā)式遺傳算法［3］、蟻群算法［4-9］、混合啟發(fā)式算法［10］和模擬退火算法［11］等。基于公平調(diào)度的算法有回溯算法調(diào)度和改進(jìn)的遺傳算法調(diào)度［12］等?？茖W(xué)家們通過(guò)研究螞蟻尋路的過(guò)程發(fā)現(xiàn)螞蟻經(jīng)過(guò)的路徑上會(huì)留下一些信息素，螞蟻會(huì)優(yōu)先選擇信息素濃度高的路徑行走，最終會(huì)形成一條從蟻穴到食物的最短路徑。本文將啟發(fā)式算法中的蟻群算法進(jìn)行改進(jìn)并應(yīng)用于云計(jì)算的任務(wù)分配中。

1 蟻群任務(wù)分配算法設(shè)計(jì)

通過(guò)分析蟻群算法解決TSP問(wèn)題的過(guò)程［13-14］，下面將蟻群算法應(yīng)用于解決任務(wù)分配的問(wèn)題上。隨機(jī)生成p個(gè)螞蟻，其中第k只螞蟻隨機(jī)選擇任務(wù)i，并計(jì)算從任務(wù)i到每一個(gè)虛擬機(jī)的概率。第k只螞蟻將任務(wù)i分配到虛擬機(jī)j上運(yùn)行的概率計(jì)算公式如（1）式所示。由（1）式可以看出任務(wù)i在虛擬機(jī)j上運(yùn)行的時(shí)間越短，其概率值Pij(k)就越大，這就意味著第k只螞蟻選中這條路徑的概率就越大。

其中，i∈［1，n］代表要分配的任務(wù)，j∈［1，m］代表處理任務(wù)的虛擬機(jī)，timeij表示任務(wù)i在虛擬機(jī)j上運(yùn)行的時(shí)間，α是任務(wù)運(yùn)行時(shí)間的權(quán)重因子，β是信息素矩陣的權(quán)重因子，ηij表示任務(wù)i到虛擬機(jī)j路徑上的信息素矩陣，τij表示將任務(wù)i分配給虛擬機(jī)j運(yùn)行的獎(jiǎng)懲因子，τij的計(jì)算公式如（2）式所示。如果虛擬機(jī)j上沒(méi)有任務(wù)執(zhí)行，則τij=1不進(jìn)行懲罰，否則根據(jù)虛擬機(jī)上任務(wù)運(yùn)行時(shí)間的長(zhǎng)短進(jìn)行懲罰。

其中，timeij表示任務(wù)i分配給虛擬機(jī)j運(yùn)行所要花費(fèi)的時(shí)間，taski虛擬機(jī)j上已分配的任務(wù)i運(yùn)行所需時(shí)間，runtimej表示虛擬機(jī)j上已經(jīng)分配的t個(gè)任務(wù)所要運(yùn)行的總時(shí)間。其中runtimej的計(jì)算公式如（3）式所示。當(dāng)?shù)趉只螞蟻分配好所有任務(wù)后，需要用（4）（5）（6）式更新信息素矩陣。

其中，Δηij是信息素的增量，totaltimek是第k只螞蟻分配完所有任務(wù)后，最慢完成所分配任務(wù)的虛擬機(jī)的運(yùn)行時(shí)間。用上面（4）式計(jì)算第k只螞蟻分配完成所有任務(wù)后在其所經(jīng)過(guò)路徑上留下的信息素增量。用（5）式更新信息素矩陣后，用（6）式蒸發(fā)所有路徑上信息素的濃度，以避免因某條路徑上信息素濃度過(guò)高影響其它螞蟻對(duì)解空間的探索，使得算法過(guò)早收斂。ρ是蒸發(fā)因子，其取值范圍在［0～1］之間。

第k只螞蟻周游一圈的流程圖如圖1所示。第k只螞蟻從任務(wù)列表中隨機(jī)選擇一個(gè)任務(wù)i，令虛擬機(jī)j=1，判斷j＜m（虛擬機(jī)的數(shù)量）是否成立，如果成立則根據(jù)公式（2）進(jìn)行獎(jiǎng)懲因子的計(jì)算，根據(jù)公式（1）計(jì)算把任務(wù)i分配給虛擬機(jī)j的概率，然后讓j++，選擇下一個(gè)虛擬機(jī)。同樣計(jì)算獎(jiǎng)懲因子和概率，直到計(jì)算完成任務(wù)i分配給所有虛擬機(jī)的概率Pij，用random（）函數(shù)生成1到100的隨機(jī)整數(shù)，然后把任務(wù)i分配給使得Pij*random（）最大的虛擬機(jī)。如果任務(wù)沒(méi)有分配完成則繼續(xù)分配，否則根據(jù)任務(wù)分配情況，更新信息素矩陣并開(kāi)始第k+1只螞蟻的游歷。

用蟻群算法求解任務(wù)分配的步驟是：

（1）定義信息素矩陣ηij用來(lái)存儲(chǔ)螞蟻k從任務(wù)i走到虛擬機(jī)j所經(jīng)過(guò)路徑上信息素的濃度，其中ηij∈［0，1）。

（2）定義timeij矩陣來(lái)存儲(chǔ)任務(wù)i在虛擬機(jī)j上運(yùn)行的時(shí)間，其中timeij=任務(wù)i中所有要執(zhí)行指令的長(zhǎng)度/虛擬機(jī)j每秒鐘執(zhí)行的指令數(shù)。

（3）定義最短完成時(shí)間minTime和任務(wù)的分配方式bestArrange，初始化minTime為整型的最大值。

圖1 第k只螞蟻的任務(wù)分配流程圖

（4）初始化信息素矩陣的所有值為0.1，根據(jù)任務(wù)的長(zhǎng)度和虛擬機(jī)每秒執(zhí)行指令數(shù)初始化timeij矩陣。

（5）初始化螞蟻的數(shù)量是虛擬機(jī)數(shù)量的10倍以上。

（6）讓第k只螞蟻開(kāi)始探索解空間。

（7）第k只螞蟻隨機(jī)在任務(wù)列表中隨機(jī)選擇一個(gè)任務(wù)i進(jìn)行任務(wù)分配。

（8）根據(jù)公式（2）計(jì)算出將任務(wù)i分配給每一個(gè)虛擬機(jī)的獎(jiǎng)懲因子，已經(jīng)分配任務(wù)的虛擬機(jī)runtime時(shí)間越長(zhǎng)其懲罰越嚴(yán)重，當(dāng)沒(méi)有任務(wù)運(yùn)行時(shí)runtime=0，τ的值為1，表示不進(jìn)行懲罰。

（9）根據(jù)公式（1）計(jì)算出將任務(wù)i分配給每一個(gè)虛擬機(jī)的概率值，其中任務(wù)i在虛擬機(jī)j上運(yùn)行時(shí)間越短，其概率值越高。由于引入獎(jiǎng)懲因子，所有沒(méi)有分配任務(wù)的虛擬機(jī)比已分配任務(wù)的虛擬機(jī)被選中的概率要高。

（10）隨機(jī)生成0到100以?xún)?nèi)的整數(shù)q，定義浮點(diǎn)數(shù)temp，讓temp=q*p［i］［j］（任務(wù)i分配給虛擬機(jī)j的概率），選擇所有從任務(wù)i到虛擬機(jī)j的路徑中temp值最大的虛擬機(jī)r，并將任務(wù)i分配給虛擬機(jī)r。標(biāo)記任務(wù)i為已分配狀態(tài)，更新虛擬機(jī)r的運(yùn)行時(shí)間為runtimer=runtimer+time［i］［r］（將任務(wù)i分配給虛擬機(jī)r的運(yùn)行時(shí)間），并記錄任務(wù)i已分配給虛擬機(jī)r。

（11）跳到第（7）步，重新選擇一個(gè)沒(méi)有分配的任務(wù)i+1進(jìn)行虛擬機(jī)的分配。

（12）當(dāng)?shù)趉只螞蟻分配完所有任務(wù)后，記錄第k只螞蟻在這種分配方式下的任務(wù)完成時(shí)間finish-Time（finishTime是所有虛擬機(jī)運(yùn)行時(shí)間（runtime）的最大值），如果finishTime小于minTime則讓minTime=finishTime，并且用bestArrange記錄第k只螞蟻的分配方式。

（13）根據(jù)公式（5）更新信息素矩陣。

（14）根據(jù)公式（6）對(duì)螞蟻留下的信息素進(jìn)行蒸發(fā)，避免算法過(guò)早收斂。ρ為蒸發(fā)系數(shù)。

（15）跳到第（6）步，讓第k+1只螞蟻開(kāi)始探索解空間。

（16）當(dāng)所有螞蟻都走完后，bestArrange中記錄的就是最佳的分配方案。

（17）調(diào)用cloudsim仿真器的任務(wù)分配函數(shù)，按照bestArrange中記錄的方案進(jìn)行任務(wù)分配。

2 仿真實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

CloudSim［15-17］是一款很好的云計(jì)算仿真平臺(tái)，它使用Java語(yǔ)言編寫(xiě)，可以很容易的實(shí)現(xiàn)數(shù)據(jù)中心、物理機(jī)、虛擬機(jī)和網(wǎng)絡(luò)的創(chuàng)建。能夠很方便的對(duì)物理機(jī)和虛擬機(jī)進(jìn)行配置，如CPU的處理能力、內(nèi)存的大小、硬盤(pán)的大小和帶寬的大小進(jìn)行配置。

圖2 CloudSim仿真流程圖

用CloudSim來(lái)進(jìn)行仿真的流程如圖2所示。初始化CloudSim包，利用CloudSim所提供的方法來(lái)創(chuàng)建數(shù)據(jù)中心，給創(chuàng)建好的數(shù)據(jù)中心分配虛擬機(jī)并設(shè)置虛擬機(jī)的參數(shù)，然后CloudSim會(huì)進(jìn)行參數(shù)的校驗(yàn)，校驗(yàn)成功后啟動(dòng)仿真并輸出結(jié)果。

用CloudSim來(lái)進(jìn)行任務(wù)調(diào)度仿真的步驟如下：

（1）初始化CloudSim的包。

（2）創(chuàng)建數(shù)據(jù)中心。

（3）創(chuàng)建物理機(jī)，設(shè)置物理機(jī)參數(shù)（如CPU、內(nèi)存、硬盤(pán)、網(wǎng)卡信息等）并分配網(wǎng)絡(luò)帶寬。

（4）創(chuàng)建虛擬機(jī)，設(shè)置虛擬機(jī)的參數(shù)（如CPU、內(nèi)存、硬盤(pán)、網(wǎng)卡信息等）并分配網(wǎng)絡(luò)帶寬。

（5）創(chuàng)建一系列任務(wù)并按照特定的任務(wù)調(diào)度算法將任務(wù)分配給虛擬機(jī)。

（6）啟動(dòng)仿真并記錄輸出的結(jié)果。

（7）仿真結(jié)束。

表1 不同任務(wù)數(shù)量下兩種調(diào)度策略的執(zhí)行時(shí)間（ms）

創(chuàng)建50臺(tái)虛擬機(jī)，設(shè)置每臺(tái)虛擬機(jī)的計(jì)算能力參數(shù)mips（每秒鐘執(zhí)行百萬(wàn)條指令）是在10～100內(nèi)隨機(jī)生成的一個(gè)整數(shù)值，即mips∈［10，100］，這能體現(xiàn)出每臺(tái)虛擬機(jī)的計(jì)算能力都是不同的。創(chuàng)建10個(gè)測(cè)試組，每個(gè)測(cè)試組包含100，200，300，……1000個(gè)任務(wù)，其中每個(gè)任務(wù)的長(zhǎng)度是在10000～100000（該任務(wù)包含多少百萬(wàn)條指令）內(nèi)隨機(jī)生成的一個(gè)整數(shù)，表示每個(gè)任務(wù)的長(zhǎng)度不同。其中蟻群任務(wù)調(diào)度算法的初始化參數(shù)為：α=1、β=1、ρ=0.5、AntNum= vmNum*10、AntGen（蟻群的代數(shù)）=2。

圖3 兩種調(diào)度算法任務(wù)完成時(shí)間

分別使用輪詢(xún)調(diào)度算法（RR）和蟻群任務(wù)調(diào)度算法（ACO）進(jìn)行仿真實(shí)驗(yàn)，仿真結(jié)果如表1所示。

通過(guò)表1的仿真數(shù)據(jù)，輪轉(zhuǎn)調(diào)度算法和蟻群調(diào)度算法分別在分配了100到1000個(gè)任務(wù)后，通過(guò)CloudSim仿真平臺(tái)進(jìn)行相應(yīng)的任務(wù)調(diào)度，按照每批任務(wù)完成所用時(shí)間做折線(xiàn)圖。結(jié)果如圖3所示。

可以得出如下結(jié)論：改進(jìn)的蟻群算法整體要好于輪詢(xún)調(diào)度算法，隨著任務(wù)數(shù)的增加，蟻群算法處理用時(shí)大大優(yōu)于輪詢(xún)調(diào)度算法。

3 結(jié)論

通過(guò)將蟻群算法從TSP問(wèn)題移植到云計(jì)算任務(wù)分配中來(lái)并進(jìn)行相應(yīng)的改進(jìn)后，發(fā)現(xiàn)蟻群算法能夠較好的解決任務(wù)分配問(wèn)題，使得任務(wù)的完成時(shí)間比傳統(tǒng)的輪詢(xún)調(diào)度算法完成時(shí)間短。蟻群算法是模擬自然界中螞蟻尋路的仿生學(xué)算法，在利用正反饋方式求解任務(wù)分配的過(guò)程中，得到了較為理想的仿真結(jié)果。

［1］王于丁，楊家海，徐聰，等.云計(jì)算訪(fǎng)問(wèn)控制技術(shù)研究綜述［J］.軟件學(xué)報(bào)，2015，26（5）：1129-1150.

［2］王繼，程志華，彭林，等.云計(jì)算綜述及電力應(yīng)用展望［J］.中國(guó)電力，2014，47（7）：108-112+127.

［3］張雨，李芳，周濤.云計(jì)算環(huán)境下基于遺傳蟻群算法的任務(wù)調(diào)度研究［J］.計(jì)算機(jī)工程與應(yīng)用，2014，50（6）：51-55.

［4］GanRongwei，GuoQingshun，ChangHuiyou，Yi Yang.Improvedantcolonyoptimizationalgorithm for the traveling salesman problems［J］.Journal of Systems Engineering and Electronics，2010，21（2）：329-333.

［5］MaurizioMarchese.Anantcolonyoptimization method for generalized TSP problem［J］.Progress in Natural Science，2008，18（2008）：1417-1422.

［6］查英華，楊靜麗.改進(jìn)蟻群算法在云計(jì)算任務(wù)調(diào)度中的應(yīng)用［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34（5）：1716-1719+ 1816.

［7］張春艷，劉清林，孟珂.基于蟻群優(yōu)化算法的云計(jì)算任務(wù)分配［J］.計(jì)算機(jī)應(yīng)用，2012，32（5）：1418-1420.

［8］黃俊，王慶鳳，劉志勤，等.基于資源狀態(tài)蟻群算法的云計(jì)算任務(wù)分配［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2014，35（9）：3305-3309.

［9］趙飛，吳航，龔躍.蟻群算法解決網(wǎng)格環(huán)境下任務(wù)調(diào)度問(wèn)題的研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，36（Z1）：97-100.

［10］孔令夷.面向有約束TSP的一種混合啟發(fā)式算法［J］.西安郵電大學(xué)學(xué)報(bào)，2013，18（1）：86-89.

［11］羅晨，李淵，劉勇，等.基于模擬退火遺傳算法的多agent系統(tǒng)任務(wù)分配［J］.計(jì)算機(jī)應(yīng)用研究，2012，29（6）：2114-2116.

［12］于瑩瑩，陳燕，李桃迎.改進(jìn)的遺傳算法求解旅行商問(wèn)題［J］.控制與決策，2014，29（8）：1483-1488.

［13］劉少偉，王潔.一種改進(jìn)的蟻群算法在TSP問(wèn)題中的應(yīng)用研究［J］.計(jì)算機(jī)仿真，2007，24（9）：155-157+ 186.

［14］韓成，趙斌，白寶興，等.基于集群的蟻群算法在TSP中的應(yīng)用研究［J］.長(zhǎng)春理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2008，31（4）：109-112..

［15］王霞俊.CloudSim云計(jì)算仿真工具研究及應(yīng)用［J］.微型電腦應(yīng)用，2013，29（8）：59-61.

［16］查英華，楊靜麗.云計(jì)算仿真平臺(tái)CloudSim在資源分配研究中的應(yīng)用［J］.軟件導(dǎo)刊，2012，11（11）：57-59.

［17］王燕妮，吳文輝.Cloudsim3.0仿真流程分析［J］.軟件，2014，35（4）：63-64.

Research of Cloud Task Scheduling Based on Ant Colony Algorithm

WANG Yunsong，SUN Jialin，GONG Yue

（School of Computer Science and Technology，Changchun University Of Science and Technology，Changchun 130022）

In order to solve the problem of low efficiency of task allocation，an improved ant colony algorithm was proposed to solve the problem of task allocation in cloud computing.Firstly，It was assumed that the task was the starting point of the ants，the virtual machine to perform the task was the end of the ants，the process of task allocation was the process of ants from the beginning to the end.Secondly，one task was selected as the starting point of the ants randomly.The improved ant colony algorithm was used to assign the task to the corresponding virtual machine.Until the end of the task assignment was completed.Finally，the path of the minimum cost was chosen as the solution of this task when all the ants were assigned to the tasks.By using the cloudsim simulator，it is proved that ant colony algorithm can effectively solve the problem of task allocation in cloud computing.

Ant Colony Optimization，cloud computing，task allocation，cloudsim

TP399

A

1672-9870（2017）01-0133-04

2016-09-05

王云松（1987-），男，碩士研究生，E-mail：wang_yun_song@163.com

龔躍（1960-），男，教授，博士生導(dǎo)師，E-mail：gongyue888878@sina.com