魏 勇，趙開新，張松青，王東署

（1.河南工學(xué)院，河南 新鄉(xiāng) 453003；2.鄭州大學(xué)電氣工程學(xué)院，鄭州 450001）

基于改進(jìn)蟻群算法的云計(jì)算任務(wù)調(diào)度研究*

魏 勇1，趙開新1，張松青1，王東署2

（1.河南工學(xué)院，河南 新鄉(xiāng) 453003；2.鄭州大學(xué)電氣工程學(xué)院，鄭州 450001）

把改進(jìn)的蟻群算法應(yīng)用到云計(jì)算任務(wù)調(diào)度中，通過將任務(wù)在虛擬機(jī)上的一次分配作為螞蟻的一次成功搜索，實(shí)現(xiàn)了虛擬機(jī)的負(fù)載均衡和調(diào)度時(shí)間的優(yōu)化，提高云計(jì)算資源分配的效率。通過在CloudSim平臺(tái)下進(jìn)行仿真測試，結(jié)果顯示，改進(jìn)蟻群算法在負(fù)載均衡性能和總的任務(wù)調(diào)度時(shí)間方面均優(yōu)于基本的蟻群算法。

基本蟻群算法，改進(jìn)蟻群算法，云計(jì)算，任務(wù)調(diào)度

0 引言

云計(jì)算是一種新興的計(jì)算模式，它是并行計(jì)算、分布式計(jì)算和網(wǎng)格計(jì)算的發(fā)展，它真正體現(xiàn)了按需服務(wù)的理念，它對(duì)存在于云計(jì)算環(huán)境中的海量數(shù)據(jù)、軟硬件資源進(jìn)行統(tǒng)一管理，并將這些資源進(jìn)行虛擬化，形成一個(gè)巨大的資源池，當(dāng)用戶需要這些資源時(shí)，就通過某種調(diào)度方式，從資源池中動(dòng)態(tài)獲取資源［1-2］。因此，如何對(duì)資源池中的資源進(jìn)行管理和分配，如何對(duì)任務(wù)進(jìn)行高效地調(diào)度成為云計(jì)算中所要解決的重要問題。

蟻群算法是一種智能算法，被應(yīng)用到云計(jì)算中，能縮短任務(wù)執(zhí)行時(shí)間，提高負(fù)載平衡度，較好地解決云計(jì)算中資源的管理和調(diào)度，以及虛擬機(jī)的負(fù)載均衡。但存在搜索最優(yōu)路徑所需迭代次數(shù)多、效率低以及容易陷入局部最優(yōu)路徑等缺陷［3-5］。本文通過對(duì)基本蟻群算法進(jìn)行改進(jìn)，提出了一種云環(huán)境下基于改進(jìn)蟻群算法的任務(wù)調(diào)度方案。

1 云計(jì)算任務(wù)調(diào)度

1.1 云計(jì)算體系結(jié)構(gòu)

在云計(jì)算中，通常將系統(tǒng)劃分為如下頁圖1所示的三層結(jié)構(gòu)，分別為應(yīng)用層、虛擬層和基礎(chǔ)設(shè)施層。云計(jì)算的分層模型很多，但所有分層模型都是基于這三層為基礎(chǔ)的，并且調(diào)度模型也是建立在這三層結(jié)構(gòu)之上。應(yīng)用層是云計(jì)算向用戶展示服務(wù)以及用戶向云計(jì)算申請(qǐng)服務(wù)的接口，主要負(fù)責(zé)向虛擬層提交任務(wù)、向用戶收集申請(qǐng)。虛擬層則是應(yīng)用層用戶能夠看到的自己獲得的全部資源，負(fù)責(zé)給用戶的具體申請(qǐng)來分配虛擬機(jī)資源，將滿足運(yùn)行條件的任務(wù)交給基礎(chǔ)設(shè)施層執(zhí)行?；A(chǔ)設(shè)施層則是實(shí)際的服務(wù)器集群［6-8］。

圖1 云計(jì)算體系結(jié)構(gòu)

1.2 問題的描述

用戶任務(wù)集合為：R={task1，task2，task3，…，taskn}，taski（i∈［1，n］）表示編號(hào)為i的任務(wù)，Q={taskit，taskic}，表示完成任務(wù)i所需的時(shí)間和對(duì)CPU的硬件需求。虛擬機(jī)的集合表示為V={v1，v2，v3，…，vm}，vi（i∈［1，n］）表示編號(hào)為i的虛擬機(jī)。預(yù)期完成時(shí)間（ETC，excepted time to completion）表示任務(wù)taski獨(dú)立在虛擬機(jī)vmj上的執(zhí)行時(shí)間為ETCij，所有ETCij元素組成ETC矩陣，式（1）是n個(gè)任務(wù)在m個(gè)虛擬機(jī)對(duì)應(yīng)的ETC矩陣。

本文針對(duì)資源調(diào)度模型作出如下假設(shè)：

假設(shè)1：各任務(wù)之間沒有依賴關(guān)系，虛擬機(jī)的性能能夠滿足任一任務(wù)的要求；

假設(shè)2：所有的任務(wù)可以被完全分配；

假設(shè)3：資源是被獨(dú)占的，非共享的，一個(gè)任務(wù)只能分配給一個(gè)虛擬機(jī)。

任務(wù)調(diào)度的目標(biāo)是建立任務(wù)與資源之間的映射，即R→V的映射。本文將改進(jìn)蟻群算法應(yīng)用到云計(jì)算的任務(wù)調(diào)度中，為任務(wù)尋找最優(yōu)的映射，使任務(wù)完成時(shí)間縮短，減少資源消耗，提高云計(jì)算的效率和性能。

1.3 云計(jì)算中蟻群算法的調(diào)度過程

算法的調(diào)度過程如圖2，當(dāng)有任務(wù)申請(qǐng)、結(jié)點(diǎn)失效和結(jié)點(diǎn)過載時(shí)會(huì)觸發(fā)蟻群算法調(diào)度。其中任務(wù)申請(qǐng)是有新任務(wù)時(shí)正常的任務(wù)提交，結(jié)點(diǎn)過載是當(dāng)有結(jié)點(diǎn)負(fù)載超過92%時(shí)發(fā)出的均衡負(fù)載申請(qǐng)，結(jié)點(diǎn)失效是當(dāng)正在執(zhí)行任務(wù)的結(jié)點(diǎn)Down機(jī)時(shí)發(fā)出的負(fù)載轉(zhuǎn)移申請(qǐng)。正常的任務(wù)申請(qǐng)是由虛擬機(jī)觸發(fā)的，而結(jié)點(diǎn)失效和結(jié)點(diǎn)過載也會(huì)觸發(fā)任務(wù)的申請(qǐng)。螞蟻尋找信息素值大的結(jié)點(diǎn)。每一次螞蟻遍歷的都是負(fù)載較低的結(jié)點(diǎn)，該結(jié)點(diǎn)會(huì)因獲得新的任務(wù)而負(fù)載上升，信息素值下降。而高負(fù)載結(jié)點(diǎn)由于獲得任務(wù)多，隨著先前任務(wù)的結(jié)束而負(fù)載下降，信息素值上升。這樣多次調(diào)度后，低負(fù)載結(jié)點(diǎn)負(fù)載會(huì)升高，而高負(fù)載結(jié)點(diǎn)負(fù)載會(huì)降低，真正實(shí)現(xiàn)負(fù)載均衡。

圖2 蟻群算法調(diào)度結(jié)構(gòu)圖

2 蟻群算法的改進(jìn)

在蟻群算法中信息素?fù)]發(fā)系數(shù)ρ的取值對(duì)算法的性能影響很大，為了提高算法的自適應(yīng)性，本文對(duì)基本蟻群算法信息素?fù)]發(fā)系數(shù)動(dòng)態(tài)進(jìn)行調(diào)整：

式中，ρmin和ρmax為揮發(fā)系數(shù)的最大和最小值，min和max為防止信息素最低或者最高的極限值。（t）為時(shí)變函數(shù)，值域介于ρmin和ρmax之間，其值變化趨勢如圖3。

圖3 （t）曲線變化圖

由于云計(jì)算任務(wù)的調(diào)度比較復(fù)雜，為了建立任務(wù)和資源的映射，改進(jìn)的蟻群算法信息素函數(shù)將對(duì)求解到的全局最優(yōu)路徑給予獎(jiǎng)勵(lì)，即對(duì)其所包含的路徑上的信息素濃度進(jìn)行加強(qiáng)，同時(shí)對(duì)求解到的局部迭代最差路徑給予懲罰，即對(duì)其所包含的路徑上的信息素濃度進(jìn)行減弱，這樣，最優(yōu)路徑和最差路徑信息濃度的差異會(huì)進(jìn)一步擴(kuò)大，從而達(dá)到使蟻群盡可能地在最優(yōu)路徑附近搜索的目的。

改進(jìn)后的蟻群算法的全局信息素濃度更新方式為：

式中，Lbest是全局最優(yōu)路徑，Lworst為迭代最差路徑，σ為算法中引入的一個(gè)參數(shù)。

每只螞蟻完成對(duì)路徑的搜索后都要對(duì)其所走過的路徑進(jìn)行一次局部更新，該局部更新方法參照基本蟻群算法模型。局部更新的公式為：

式中ρ為信息揮發(fā)系數(shù)。

式中Lk表示第k只螞蟻求得的路徑距離，Q為算法中引入的一個(gè)參數(shù)。

3 改進(jìn)的蟻群算法在云計(jì)算中的調(diào)度方案

把改進(jìn)的蟻群算法應(yīng)用在云計(jì)算中，設(shè)計(jì)出組合優(yōu)化的模型，求得一個(gè)解s={X1，X2，…，Xm}的過程就是對(duì)其中每個(gè)決策變量Xi的求值過程，其中n是任務(wù)數(shù)，X的值域是元素（T，Vm）的集合，即n個(gè)任務(wù){(diào)task1，task2，task3，…，taskn}、m個(gè)虛擬化資源{v1，v2，v3，…，vm}的迪卡爾積。元組（T，Vm）任務(wù)到資源的一個(gè)分配，是將任務(wù)T分配到資源Vm上，可以用一只螞蟻在一張圖G上的爬行過程來模擬，圖上的每個(gè)頂點(diǎn)是一個(gè)分配，當(dāng)任務(wù)分配完后，螞蟻爬行結(jié)束，每個(gè)任務(wù)只能被分配一次，得到的解S的預(yù)期執(zhí)行時(shí)間是個(gè)合理的目標(biāo)函數(shù)，每個(gè)可能的決策（T，Vm）都有一個(gè)信息素P相對(duì)應(yīng)，在算法開始執(zhí)行時(shí)初始化信息素，并且信息素的值隨著算法的運(yùn)行而被更新。具體的調(diào)度過程如圖4。

圖4 改進(jìn)蟻群算法的云計(jì)算調(diào)度流程圖

4 實(shí)驗(yàn)與分析

本文采用CloudSim作為實(shí)驗(yàn)?zāi)M平臺(tái)來驗(yàn)證改進(jìn)蟻群算法在云計(jì)算中應(yīng)用的可行性和有效性，通過CloudSim中的DataCenter、VM等模擬計(jì)算機(jī)網(wǎng)絡(luò)的資源、任務(wù)以及虛擬機(jī)，構(gòu)建出云計(jì)算的仿真環(huán)境，在實(shí)驗(yàn)中設(shè)定任務(wù)數(shù)從20到100個(gè)，計(jì)算節(jié)點(diǎn)數(shù)為6個(gè)，虛擬機(jī)個(gè)數(shù)為10，螞蟻數(shù)為10到100，迭代次數(shù)為600。信息啟發(fā)算子α和期望啟發(fā)算子β分別為1、5，信息素殘留算子ρ=0.65?；鞠伻核惴ê透倪M(jìn)后的蟻群算法完成任務(wù)所需的時(shí)間如圖5，其中ACO表示基本蟻群算法，IACO表示改進(jìn)蟻群算法。

圖5 兩種算法執(zhí)行完任務(wù)所需時(shí)間

從圖5可以看到，當(dāng)任務(wù)量比較小時(shí)改進(jìn)的蟻群算法和基本蟻群算法執(zhí)行時(shí)間差別不大，但隨著任務(wù)量的增加，改進(jìn)后的蟻群算法明顯比基本蟻群算法執(zhí)行的時(shí)間減少，當(dāng)任務(wù)達(dá)到100時(shí)，兩種算法執(zhí)行時(shí)間相差將近2 s，由此可以看出，在一定范圍內(nèi)，隨著任務(wù)數(shù)的增加，這兩種算法分配資源并執(zhí)行的時(shí)間開銷相差越來越大，因此，改進(jìn)的蟻群算法在云計(jì)算中任務(wù)調(diào)度效率較高。

下頁表1顯示了基本的蟻群算法和改進(jìn)的蟻群算法，每個(gè)節(jié)點(diǎn)上所分配的任務(wù)數(shù)，其中ACO表示基本蟻群算法，IACO表示改進(jìn)蟻群算法，從表中可以看出采用改進(jìn)蟻群算法執(zhí)行任務(wù)時(shí)節(jié)點(diǎn)的負(fù)載均衡度較高。為了更直觀地顯示兩種算法的差別，求解出兩種算法任務(wù)分配結(jié)構(gòu)的相對(duì)標(biāo)準(zhǔn)偏差，如圖6所示。

表1 各節(jié)點(diǎn)上任務(wù)分配結(jié)果

圖6 任務(wù)分配結(jié)果相對(duì)偏差

5 結(jié)論

在云計(jì)算環(huán)境中，資源的合理分配與管理、任務(wù)的調(diào)度是保證云計(jì)算服務(wù)質(zhì)量的關(guān)鍵，為了在云計(jì)算環(huán)境中進(jìn)行合理的任務(wù)調(diào)度，縮短完成總?cè)蝿?wù)的時(shí)間，各節(jié)點(diǎn)盡可能達(dá)到負(fù)載均衡，把改進(jìn)的蟻群算法應(yīng)用到云計(jì)算任務(wù)調(diào)度中，通過仿真測試表明，隨著任務(wù)量的增加，和基本蟻群算法相比，任務(wù)執(zhí)行的時(shí)間明顯減少，節(jié)點(diǎn)的負(fù)載均衡度有了明顯提高。

［1］劉漳輝，王曉莉.云計(jì)算虛擬機(jī)群中帶遺傳算法的負(fù)載均衡算法［J］.福州大學(xué)學(xué)報(bào)，2012，40（4）：453-458.

［2］楊慶芳，梅朵，韓振波，等.基于云計(jì)算的蟻群算法求解城市路網(wǎng)最短路徑［J］.吉林大學(xué)學(xué)報(bào)，2013，43（5）：1210-1214.

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

［4］張?zhí)?基于改進(jìn)粒子群算法的云計(jì)算任務(wù)調(diào)度算法［J］.計(jì)算機(jī)工程與應(yīng)用，2013，49（19）：68-72.

［5］劉衛(wèi)寧.基于改進(jìn)量子遺傳算法的云計(jì)算資源調(diào)度［J］.計(jì)算機(jī)應(yīng)用，2013，33（8）：2151-2153.

［6］YAGMAHAN B，YENISEY M M，A multi-objective ant colony system algorithm for flow shop scheduling problem［J］. Expert Systems with Applications，2010，37（2）：1361-1368.

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

［8］劉新華，張旭堂，劉文劍.基于改進(jìn)最大-最小螞蟻系統(tǒng)的多工藝線路決策方法［J］.計(jì)算機(jī)集成制造系統(tǒng)，2008，14（12）：2414-2420.

Cloud Computing Task Scheduling Based on Improved Ant Colony Algorithm

WEI Yong1，ZHAO Kai-xin1，ZHANG Song-qing1，WANG Dong-shu2
（1.Henan Institute of Technology，Xinxiang 453003，China；2.Electrical Engineering School of Zhengzhou University，Zhengzhou 450001，China）

The improved ant colony algorithm is applied to the cloud computing task scheduling，realize load balancing and scheduling time optimization of virtual machine，improve the efficiency of resource allocation in cloud computing is improved.Through task in a virtual machine a distribution as ants to a successful search，the simulation test under the CloudSim platform，the results show that the improved ant colony algorithm is better than the basic ant colony algorithm in the load balancing performance and the total task scheduling time.

ant colony algorithm，improved ant colony algorithm，cloud computing，task scheduling

TP309.2

A

1002-0640（2017）05-0130-04

2016-03-18

2016-05-17

國家自然科學(xué)基金（61174085）；河南省高等學(xué)校重點(diǎn)科研基金（16A520084）；河南省高等學(xué)校教學(xué)工程基金（豫教高2012［1099］號(hào)）；河南省高等學(xué)校教學(xué)工程基金資助項(xiàng)目（豫教高2012［1185］號(hào)）

魏 勇（1982- ），男，河南衛(wèi)輝人，碩士，講師。研究方向：云計(jì)算、計(jì)算機(jī)網(wǎng)絡(luò)。