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

王云松，孫佳林，龔躍

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

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

王云松，孫佳林，龔躍

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（10）隨機(jī)生成0到100以內(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)行時間為runtimer=runtimer+time［i］［r］（將任務(wù)i分配給虛擬機(jī)r的運(yùn)行時間），并記錄任務(wù)i已分配給虛擬機(jī)r。

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

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

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

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

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

（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ì)算仿真平臺，它使用Java語言編寫，可以很容易的實(shí)現(xiàn)數(shù)據(jù)中心、物理機(jī)、虛擬機(jī)和網(wǎng)絡(luò)的創(chuàng)建。能夠很方便的對物理機(jī)和虛擬機(jī)進(jìn)行配置，如CPU的處理能力、內(nèi)存的大小、硬盤的大小和帶寬的大小進(jìn)行配置。

圖2 CloudSim仿真流程圖

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

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

（1）初始化CloudSim的包。

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

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)論

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

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

［2］王繼，程志華，彭林，等.云計(jì)算綜述及電力應(yīng)用展望［J］.中國電力，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)度問題的研究［J］.長春理工大學(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)的遺傳算法求解旅行商問題［J］.控制與決策，2014，29（8）：1483-1488.

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

［14］韓成，趙斌，白寶興，等.基于集群的蟻群算法在TSP中的應(yīng)用研究［J］.長春理工大學(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ì)算仿真平臺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