基于蟻群算法的云任務調度研究

王云松，孫佳林，龔躍

（長春理工大學計算機科學與技術學院，長春 130022）

基于蟻群算法的云任務調度研究

王云松，孫佳林，龔躍

（長春理工大學計算機科學與技術學院，長春 130022）

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

蟻群算法；云計算；任務分配；cloudsim

任務分配是云計算［1-2］中的關鍵問題，近些年來人們也提出了很多種任務分配的方法。這些任務調度方法大致分為兩類：基于效率的調度算法和基于公平的調度算法。基于效率的調度算法有傳統的輪詢調度算法、啟發式遺傳算法［3］、蟻群算法［4-9］、混合啟發式算法［10］和模擬退火算法［11］等。基于公平調度的算法有回溯算法調度和改進的遺傳算法調度［12］等。科學家們通過研究螞蟻尋路的過程發現螞蟻經過的路徑上會留下一些信息素，螞蟻會優先選擇信息素濃度高的路徑行走，最終會形成一條從蟻穴到食物的最短路徑。本文將啟發式算法中的蟻群算法進行改進并應用于云計算的任務分配中。

1 蟻群任務分配算法設計

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

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

其中，timeij表示任務i分配給虛擬機j運行所要花費的時間，taski虛擬機j上已分配的任務i運行所需時間，runtimej表示虛擬機j上已經分配的t個任務所要運行的總時間。其中runtimej的計算公式如（3）式所示。當第k只螞蟻分配好所有任務后，需要用（4）（5）（6）式更新信息素矩陣。

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

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

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

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

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

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

圖1 第k只螞蟻的任務分配流程圖

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

（5）初始化螞蟻的數量是虛擬機數量的10倍以上。

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

（7）第k只螞蟻隨機在任務列表中隨機選擇一個任務i進行任務分配。

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

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

（10）隨機生成0到100以內的整數q，定義浮點數temp，讓temp=q*p［i］［j］（任務i分配給虛擬機j的概率），選擇所有從任務i到虛擬機j的路徑中temp值最大的虛擬機r，并將任務i分配給虛擬機r。標記任務i為已分配狀態，更新虛擬機r的運行時間為runtimer=runtimer+time［i］［r］（將任務i分配給虛擬機r的運行時間），并記錄任務i已分配給虛擬機r。

（11）跳到第（7）步，重新選擇一個沒有分配的任務i+1進行虛擬機的分配。

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

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

（14）根據公式（6）對螞蟻留下的信息素進行蒸發，避免算法過早收斂。ρ為蒸發系數。

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

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

（17）調用cloudsim仿真器的任務分配函數，按照bestArrange中記錄的方案進行任務分配。

2 仿真實驗設計與結果分析

CloudSim［15-17］是一款很好的云計算仿真平臺，它使用Java語言編寫，可以很容易的實現數據中心、物理機、虛擬機和網絡的創建。能夠很方便的對物理機和虛擬機進行配置，如CPU的處理能力、內存的大小、硬盤的大小和帶寬的大小進行配置。

圖2 CloudSim仿真流程圖

用CloudSim來進行仿真的流程如圖2所示。初始化CloudSim包，利用CloudSim所提供的方法來創建數據中心，給創建好的數據中心分配虛擬機并設置虛擬機的參數，然后CloudSim會進行參數的校驗，校驗成功后啟動仿真并輸出結果。

用CloudSim來進行任務調度仿真的步驟如下：

（1）初始化CloudSim的包。

（2）創建數據中心。

（3）創建物理機，設置物理機參數（如CPU、內存、硬盤、網卡信息等）并分配網絡帶寬。

（4）創建虛擬機，設置虛擬機的參數（如CPU、內存、硬盤、網卡信息等）并分配網絡帶寬。

（5）創建一系列任務并按照特定的任務調度算法將任務分配給虛擬機。

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

（7）仿真結束。

表1 不同任務數量下兩種調度策略的執行時間（ms）

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

圖3 兩種調度算法任務完成時間

分別使用輪詢調度算法（RR）和蟻群任務調度算法（ACO）進行仿真實驗，仿真結果如表1所示。

通過表1的仿真數據，輪轉調度算法和蟻群調度算法分別在分配了100到1000個任務后，通過CloudSim仿真平臺進行相應的任務調度，按照每批任務完成所用時間做折線圖。結果如圖3所示。

可以得出如下結論：改進的蟻群算法整體要好于輪詢調度算法，隨著任務數的增加，蟻群算法處理用時大大優于輪詢調度算法。

3 結論

通過將蟻群算法從TSP問題移植到云計算任務分配中來并進行相應的改進后，發現蟻群算法能夠較好的解決任務分配問題，使得任務的完成時間比傳統的輪詢調度算法完成時間短。蟻群算法是模擬自然界中螞蟻尋路的仿生學算法，在利用正反饋方式求解任務分配的過程中，得到了較為理想的仿真結果。

［1］王于丁，楊家海，徐聰，等.云計算訪問控制技術研究綜述［J］.軟件學報，2015，26（5）：1129-1150.

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

［3］張雨，李芳，周濤.云計算環境下基于遺傳蟻群算法的任務調度研究［J］.計算機工程與應用，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］.計算機工程與設計，2013，34（5）：1716-1719+ 1816.

［7］張春艷，劉清林，孟珂.基于蟻群優化算法的云計算任務分配［J］.計算機應用，2012，32（5）：1418-1420.

［8］黃俊，王慶鳳，劉志勤，等.基于資源狀態蟻群算法的云計算任務分配［J］.計算機工程與設計，2014，35（9）：3305-3309.

［9］趙飛，吳航，龔躍.蟻群算法解決網格環境下任務調度問題的研究［J］.長春理工大學學報：自然科學版，2013，36（Z1）：97-100.

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

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

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

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

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

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

［16］查英華，楊靜麗.云計算仿真平臺CloudSim在資源分配研究中的應用［J］.軟件導刊，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-），男，教授，博士生導師，E-mail：gongyue888878@sina.com