基于函數(shù)約束的云任務分配的研究

聶清彬，張莉萍，霍敏霞，曹耀欽

（1.重慶郵電大學移通學院，重慶401520；2.重慶郵電大學軟件工程學院，重慶400065）

基于函數(shù)約束的云任務分配的研究

聶清彬1，?，張莉萍2，霍敏霞1，曹耀欽1

（1.重慶郵電大學移通學院，重慶401520；2.重慶郵電大學軟件工程學院，重慶400065）

為了解決云環(huán)境下的資源調(diào)度問題，提出了一種改進的蟻群資源調(diào)度算法（RRLB?ACO），該算法在綜合參考各種云計算任務調(diào)度算法的基礎(chǔ)上，利用資源約束函數(shù)改進信息素的更新，并且通過負載均衡差函數(shù)來改進啟發(fā)信息，使虛擬機經(jīng)過算法多次迭代以后能夠處于一種負載均衡的狀態(tài)，利用CloudSim工具進行仿真測試，與標準的蟻群算法BACO、最新的ACOSA算法做仿真對比，實驗結(jié)果表明RRLB?ACO算法在任務的執(zhí)行時間、成本以及系統(tǒng)負載均衡方面均優(yōu)于BACO算法和ACOSA算法。

云計算；資源約束；蟻群算法；任務調(diào)度；負載均衡

0 引言

云計算是將計算資源進行統(tǒng)一管理與統(tǒng)一分配的新型計算模式，根據(jù)任務的需求分配相應的資源是云計算的核心技術(shù)，云計算是把具有可伸縮的、動態(tài)的、分散的資源進行虛擬化以后以付費的方式提供給用戶，用戶無需關(guān)心提供服務的服務器的具體位置和分布情況，只需要提交任務給云計算中心，云計算機中心就會分配相應的資源來完成這些任務，由于云計算中的任務量巨大，每時每刻都有海量的任務提交給云計算中心，因此對于云計算系統(tǒng)而言，如何采用有效的資源調(diào)度算法來合理地分配資源，降低任務執(zhí)行時間、成本，并且讓整個云計算資源得到充分利用，提高任務執(zhí)行效率成為研究的重點。

目前，云計算環(huán)境下中任務調(diào)度很多都采用Google提出的Map／Reduce的分布式編程模式，分成Map（映射）和Reduce（化簡）兩個階段，在Map階段，將用戶提交的任務劃分成一些小的子任務，然后分配到若干個虛擬機節(jié)點上并發(fā)地執(zhí)行，執(zhí)行結(jié)束并輸出結(jié)果，在Reduce階段，將Map階段輸出的結(jié)果進行匯總處理，并把最終的處理結(jié)果交付給用戶，在Map／Reduce計算編程模式下，如何對分割的子任務進行高效低成本的調(diào)度是算法的關(guān)鍵。

很多學者提出了用改進的蟻群算法來更好地解決云環(huán)境下的任務調(diào)度，比如李建峰、彭艦［1］提出了一種帶有雙適應度的遺傳算法（DFGA），該算法能有效縮短任務的平均完成時間，與自適應算法（AGA）進行仿真對比，算法明顯優(yōu)于自適應算法；魏赟、陳元元［2］提出了一種能改善任務并行性和兼顧任務串行關(guān)系的DSFACO算法，算法將用戶提交的任務分成多個子任務，并根據(jù)執(zhí)行先后次序放到不同優(yōu)先級的調(diào)度隊列中，并對處于同一調(diào)度隊列中的子任務，利用最短任務的延遲時間來執(zhí)行調(diào)度，在提高任務執(zhí)行效率的同時，增強了調(diào)度公平性，最大程度地縮短了任務的延遲時間，實現(xiàn)了云環(huán)境下任務的最優(yōu)分配；張浩榮、陳平華、熊建斌［3］提出了融合模擬退火算法和蟻群算法的混合算法ACOSA，該算法以最小化調(diào)度時間為目標，引入了資源和任務的匹配因子以及負載均衡度，通過改進的蟻群算法計算出任務到資源的最優(yōu)解，并通過模擬退火算法對求出的解進行路徑的優(yōu)化以及信息素的更新，通過仿真實驗，算法在調(diào)度時間、負載均衡方面都取得了良好的效果；華夏渝、鄭駿、胡文心［6］提出了一種基于改進蟻群算法的計算資源分配算法，在資源調(diào)度之前，首先對可用節(jié)點的計算能力進行預測，分析線路質(zhì)量、帶寬的使用情況以及響應時間等因素對資源調(diào)度的影響，通過蟻群算法計算出最優(yōu)的資源，該算法在符合云計算環(huán)境配置的前提下，對比以往的網(wǎng)格分配算法，具有更優(yōu)的調(diào)度效果和更短的響應時間；史少鋒、劉宴兵［7］提出一種基于動態(tài)規(guī)劃模型的資源調(diào)度算法，將任務的執(zhí)行時間最短作為優(yōu)化目標，將虛擬機與任務的匹配看成是多階段決策的組合優(yōu)化，在一定的數(shù)量規(guī)模并且滿足用戶需求的前提下，減少了任務的完成時間，并且保持系統(tǒng)負載均衡。這些算法從不同方面優(yōu)化了云計算中資源調(diào)度的過程，但是都鮮有同時考慮到通過資源約束條件以及負載均衡差來實現(xiàn)資源的最優(yōu)調(diào)度，本文在已有的蟻群算法基礎(chǔ)之上提出建立資源約束函數(shù)，提高虛擬機負載均衡度的改進蟻群算法（Resource Restraint，Load Balancing Ant Colony Optimization，RRLB?ACO）來實現(xiàn)對任務的分配。

蟻群算法是1992年Marco Dorigo在博士論文里提出的一種在圖中尋找最優(yōu)路徑的算法，它模擬螞蟻群體搜尋食物的過程，尋覓食物過程中，在其經(jīng)過的每一條路經(jīng)上遺留下一種信息，叫信息素（pheromone），這些路徑上已經(jīng)留下的信息素的濃度大小對后續(xù)螞蟻選擇自己下一步走哪條路徑具有很大的影響。一般情況下，某一條路徑的信息濃度越高，后續(xù)螞蟻選擇其作為下一條路徑的概率也就越大，那么路徑上留下的信息素也就越多，這樣大量的螞蟻選擇該路徑的行為就體現(xiàn)出蟻群的整體運動機制。該算法求解精度高且易與其他方法結(jié)合，能在海量的解空間中最大限度地尋找全局最優(yōu)解，特別是解決組合優(yōu)化問題方面，根據(jù)狀態(tài)轉(zhuǎn)移概率來搜索解的空間，結(jié)合信息素的更新，找到最優(yōu)解。

1 資源約束負載均衡調(diào)度模型的建立

1.1 虛擬機的選擇

在云環(huán)境中，將n個分別獨立的子任務分配到m個虛擬機上并行執(zhí)行（m＜n），虛擬機表示為νm＝｛νm1，νm2，…，νmm｝，子任務表示為t＝｛t1，t2，…，tn｝，每個子任務只能在一個虛擬機上運行。結(jié)合蟻群算法公式（1）計算出任務ti被分配到虛擬機νmj的概率值

其中，τij（t）表示在t時刻路徑（i，j）上的信息素濃度，ηij（t）表示在t時刻路徑（i，j）上的啟發(fā)信息，α為期望啟發(fā)因子，表示螞蟻在任務調(diào)度過程中的啟發(fā)信息對任務選擇的相對重要程度；β為信息素啟發(fā)因子，表示路徑上的殘留信息素濃度對任務選擇的影響程度；tabuk（k＝1，2，…，n），記錄螞蟻已經(jīng)走過的城市，被訪問過的城市會加入禁忌表；allowedk表示第k只螞蟻允許訪問的下一個城市的節(jié)點，是禁忌表之外螞蟻還沒走過的城市，設(shè)置螞蟻的迭代次數(shù)為nc，最大迭代次數(shù)為ncmax。

1.2 資源約束函數(shù)

在對云計算機中資源選擇過程中，每個虛擬機完成任務的性能決定了被選擇的概率，當前資源與任務分配的方案用I表示。對任務選擇哪一個虛擬機來執(zhí)行的幾種因素主要考慮如下：

1）預計執(zhí)行時間νtij表示任務ti在虛擬機νmj預計執(zhí)行時間。

2）預計執(zhí)行成本νcij表示任務ti在虛擬機νmj預計執(zhí)行成本。

3）網(wǎng)絡帶寬νbij表示預計任務ti在虛擬機νmj執(zhí)行使用的網(wǎng)絡帶寬。

4）虛擬機νdij表示預計任務ti在虛擬機νmj執(zhí)行產(chǎn)生的延遲。

5）虛擬機νfij表示預計任務tj在虛擬機νmj執(zhí)行任務產(chǎn)生的故障概率。

則資源約束函數(shù)res（Iij）可表示為

其中，a，b，c，d，e為5個約束條件的權(quán)重，νtmax，vcmax，vdmax，vbmax，vfmax為其邊界條件，不同的云環(huán)境會有不同的取值。

1.3 負載均衡差函數(shù)

在實際云環(huán)境中，由于云計算資源存在動態(tài)性和異構(gòu)性，每個虛擬機的網(wǎng)絡帶寬、計算能力、內(nèi)存大小等差異較大，單位時間內(nèi)執(zhí)行任務的負載有較大差別，有的虛擬機性能較差，有的虛擬機性能明顯更好，這樣更容易造成大量任務聚集到一部分性能高的虛擬機上執(zhí)行，而且容易造成等待的任務增多，同時另外性能較差的虛擬機資源卻處于閑置的狀態(tài)，使得整個云計算中的虛擬機負載不均衡，資源利用率很低。為了解決這個問題，本文提出建立負載均衡差函數(shù)來改變虛擬機啟發(fā)信息，通過改進啟發(fā)信息可以讓閑置的虛擬機分配更多的任務，為分配過多任務的虛擬機減輕負載，使系統(tǒng)的負載始終保持均衡狀態(tài)。

在云計算實際環(huán)境中，影響負載的因素有虛擬機CPU的使用率r_cpu，內(nèi)存的使用率r_mem，網(wǎng)絡帶寬的利用率r_bw。因此虛擬機νmj的負載公式表示為

其中，w1＋w2＋w3＝1，w1，w2，w3分別表示CPU，內(nèi)存，帶寬的權(quán)值。則整個云計算系統(tǒng)的平均負載為

則整個云計算中心服務器負載均衡標準差Lij表示為

利用Lij結(jié)合公式（1）得到

根據(jù)公式（7）計算任務ti選擇虛擬機νmj并比較每種選擇方案所產(chǎn)生的Lij值。Lij值越小，說明任務ti選擇虛擬機νmj對系統(tǒng)所產(chǎn)生的負載使得整個云計算的平均負載率越均衡，虛擬機νmj被分配到任務的概率也就越大；反之，虛擬機νmj被分配到任務的概率也就越小。經(jīng)過算法多次迭代以后，改進后的算法最終能實現(xiàn)云計算中心虛擬機的負載平衡。

1.4 初始化信息素和啟發(fā)信息

在蟻群算法中，信息素τij（t）和啟發(fā)函數(shù)ηij（t）是最重要的參數(shù)，由于云計算的動態(tài)性和異構(gòu)性，本文通過虛擬機的計算能力、網(wǎng)絡帶寬、虛擬機內(nèi)存等對啟發(fā)函數(shù)和信息素進行初始化：

其中，νm_memj表示虛擬機內(nèi)存，νm_bwj表示虛擬機νmj網(wǎng)絡帶寬，νm_mipsj處理器運算速度，νm_numj表示虛擬機νmj的處理器數(shù)量。

通過輪盤賭算法計算任務選擇虛擬機的概率，首先利用概率轉(zhuǎn)移公式（1）計算得到任務ti選擇到虛擬機νmj上執(zhí)行的概率，最后用輪盤賭注法來確定某一個任務在哪一個虛擬機上執(zhí)行。每一個任務到虛擬機上的執(zhí)行概率就等同于賭盤上的每一個扇區(qū)，扇區(qū)面積越大，該扇區(qū)被指針選中的概率也就越大，任務分配到該虛擬機的概率值對應每個分區(qū)的大小，則任務分配到該虛擬機的轉(zhuǎn)移概率值越大，更有可能被選中來執(zhí)行下一個任務。在本文中選擇資源和路徑的過程就是尋找滿足式（3）以及最小res（Iij）和最小Lij的過程。

1.5 信息素的更新

當螞蟻將任務分配到虛擬機上以后，隨著迭代次數(shù)的增加，原有的信息素就會隨之增加，如果不對路徑上殘留的信息素進行更新，算法將會陷入局部收斂的狀態(tài)，因此在每只螞蟻完成任務分配時，就利用式（10）進行信息素更新：

其中，ρ是信息揮發(fā)因子，表示信息素在單位時間內(nèi)的揮發(fā)程度，1－ρ表示信息素濃度殘留程度，ρ∈（0，1］，如果ρ越大，說明信息素揮發(fā)越快，則過去搜索過的路徑對現(xiàn)在的選擇影響也就越小，Δτij表示信息素濃度的增量，信息素增量Δτij用資源約束函數(shù)Δτij定義。改進的信息素更新由局部更新和全局更新組成。

1）當一只螞蟻通過路徑搜索時，也就是任務被分配到某一個虛擬機上，找到了相應的分配方案以后，路徑上所有的虛擬機都將進行一次局部信息素更新，此時Δτij定義如下：

其中，D1表示常量，res（Iki）表示第i只螞蟻在第k次迭代中為用戶搜索到的分配方案。

2）當所有螞蟻完成路徑搜索時，找到本次迭代中最優(yōu)的路徑，然后對路徑上的所有虛擬機進行全局信息素更新，此時Δτij定義如下：

其中，MIN（res（Iki））表示在第k次迭代中螞蟻為用戶搜索到的最優(yōu)的分配方案，D2為常量。

1.6 算法流程

第1步：初始化云計算機中所有虛擬機的信息素的值，信息素啟發(fā)因子α和揮發(fā)因子ρ，期望啟發(fā)因子β，螞蟻個數(shù)m，設(shè)置迭代次數(shù)nc以及最大迭代次數(shù)ncmax。

第2步：將螞蟻隨機地分配到虛擬機上。

第3步：計算任務到資源的負載均衡差Lij作為啟發(fā)信息，計算任務到資源的約束函數(shù)res（Iij），并根據(jù)公式（1）計算每個虛擬機被選中的概率，通過輪盤賭算法確定被最終執(zhí)行任務的虛擬機。

第4步：如果完成本次任務分配，根據(jù)公式（11）進行局部信息素的更新，否則跳轉(zhuǎn)到步驟2。

第5步：如果所有螞蟻完成了本次任務的分配，根據(jù)分配情況找出本次任務分配的最優(yōu)的分配方案，根據(jù)公式（12），通過本次的最優(yōu)解進行全局信息素更新。

第6步：判定當前迭代次數(shù)是否達到最大迭代次數(shù)，如果是，結(jié)束算法流程，如果沒有，跳轉(zhuǎn)到步驟2繼續(xù)執(zhí)行。

2 仿真實驗結(jié)果與分析

利用云計算仿真平臺CloudSim 3.0驗證算法RRLB?ACO的有效性與可行性，利用CloudSim里面的Cloudlet、DataCenter、VM等類來模擬云系統(tǒng)中真實環(huán)境和資源，創(chuàng)建虛擬機以及任務，并重寫Cloudlet，DataCenterBroker類來構(gòu)造RRLB?ACO算法，模擬云計算的真實環(huán)境，并在基于同樣配置和參數(shù)設(shè)置的條件下與標準的蟻群算法以及文獻［3］中的云計算中改進任務調(diào)度算法ACOSA進行對比。

在本實驗中，對CloudSim模擬器參數(shù)進行設(shè)置，設(shè)置數(shù)據(jù)中心為20個，每個數(shù)據(jù)中心設(shè)置10個虛擬機，虛擬機性能參數(shù)設(shè)置為500～2 000 MIPS，內(nèi)存為512～2 048 MB，帶寬為5 000～10 000 b／s，任務指令長度為300～3 600 MI（Million Instruction），任務數(shù)量為100～400個，虛擬機單位時間運行所消耗成本rcu（νmj）值為25，最大迭代次數(shù)ncmax為50次，在資源中心執(zhí)行時間共享和空間共享的策略，調(diào)度算法中的參數(shù)設(shè)置為：α＝1，β＝2，ρ＝0．01。

CloudSim仿真步驟如下：

1）初始化CloudSim包。

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

3）創(chuàng)建數(shù)據(jù)代理中心。

4）創(chuàng)建虛擬機。

5）創(chuàng)建云任務。

6）調(diào)用任務調(diào)度策略，分配任務到虛擬機。

7）啟動仿真。

8）仿真結(jié)束后分析結(jié)果。

實驗中在同等條件下將標準的蟻群算法BACO、文獻［3］中的ACOSA算法和本文的RRLB?ACO算法進行試驗仿真，對比任務的執(zhí)行時間、成本以及虛擬機的負載率狀況，具體實驗數(shù)據(jù)如圖1～3所示，圖中任務執(zhí)行成本單位為美元（），執(zhí)行時間單位為秒。實驗結(jié)果分析如下：

從圖1可以看出，在任務數(shù)量在100左右的時候，三者算法執(zhí)行任務時間差別不大，隨著任務數(shù)量的增加，BACO和ACOSA算法對比，ACOSA算法執(zhí)行時間比BACO算法短。同等條件下，RRLB?ACO算法使任務執(zhí)行時間最短。任務在選擇虛擬機的過程中，算法中的資源約束函數(shù)總是通過算法對比選擇出執(zhí)行當前任務時間相對較短的虛擬機，有更好地發(fā)現(xiàn)解的能力，提高資源利用率，對縮短任務執(zhí)行時間發(fā)揮有效作用。

圖1 任務執(zhí)行時間比較Fig.1 Comparison of task execution time

從圖2可以看出，當任務量在200以內(nèi)時，3個算法執(zhí)行成本差別不大，隨著任務數(shù)量的增加，執(zhí)行同樣多數(shù)量的任務，BACO算法執(zhí)行費用最高，ACOSA算法執(zhí)行成本比BACO降低了一些，RRLB?ACO算法的執(zhí)行成本比ACOSA降低35%左右，說明通過資源約束函數(shù)res（Iij）中的成本約束、網(wǎng)絡帶寬約束、執(zhí)行時間約束等函數(shù)，算法總能在目前可選的虛擬機中選擇出與當前任務匹配并且執(zhí)行成本相對較低的虛擬機來執(zhí)行任務，從而達到降低任務執(zhí)行成本的目的。

圖2 任務執(zhí)行成本比較Fig.2 Comparison of task execution costing

圖3反映了虛擬機的負載均衡度的對比，從圖中可以看出，標準的蟻群算法BACO負載均衡度是最低的，說明負載極不平衡，ACOSA算法負載有所改進，RRLB?ACO算法相比前面兩種算法將負載均衡度提高了0.3左右，使云計算資源系統(tǒng)負載一直維持在一個相對均衡的狀態(tài)，說明通過成本函數(shù)改進以后的蟻群算法通過多次迭代以后，使得整個系統(tǒng)的負載均衡度提高，再與圖1、圖2的任務執(zhí)行時間、成本對比分析，RRLB?ACO算法所產(chǎn)生的任務執(zhí)行時間短，負載均衡度高，充分說明了云系統(tǒng)的負載均衡度越高，虛擬機的利用率就越高，以后用戶提交的任務的執(zhí)行時間也就越短。

圖3 負載均衡率比較Fig.3 Comparison of load balancing rate

3 結(jié)束語

本文提出了基于資源的約束函數(shù)，負載均衡差的改進蟻群優(yōu)化算法RRLB?ACO，用來改進云計算中的資源調(diào)度，實驗結(jié)果表明，RRLB?ACO算法性能明顯優(yōu)于ACOSA和BACO，有效優(yōu)化了資源的調(diào)度，降低執(zhí)行時間和成本，提高了系統(tǒng)執(zhí)行任務效率，讓云計算系統(tǒng)始終保持在一個負載均衡的狀態(tài)。

［1］李建峰，彭艦.云計算環(huán)境下基于改進遺傳算法的任務調(diào)度算法［J］.計算機應用，2011，31（1）：184?187.

［2］魏赟，陳元元.基于改進蟻群算法的云計算任務調(diào)度模型［J］.計算機工程，2015，41（1）：12?16.

［3］張浩榮，陳平華，熊建斌.基于蟻群模擬退火算法云環(huán)境任務調(diào)度［J］.廣東工業(yè)大學學報，2014，31（3）：77?82.

［4］張煥青，張學平，等.基于負載均衡蟻群優(yōu)化算法的云計算任務調(diào)度［J］.微電子學與計算機，2015，5（5）：31?40.

［5］左利云，左利鋒.云計算中基于預先分類的調(diào)度優(yōu)化算法［J］.計算機工程與設(shè)計，2012，33（4）：1357?1361.

［6］華夏渝，鄭駿，胡文心.基于云計算環(huán)境的蟻群優(yōu)化計算資源分配算法［J］.華東師范大學學報（自然科學版），2010，2（1）：127?134.

［7］史少鋒，劉宴兵.基于動態(tài)規(guī)劃的云計算任務調(diào)度研究［J］.重慶郵電大學學報（自然科學版），2012，6（1）：687?692.

［8］林偉偉，齊德昱.云計算資源調(diào)度研究綜述［J］.計算機科學，2012，39（10）：1?6.

［9］張水平，鄔海艷.基于細胞自動機遺傳算法的云資源調(diào)度［J］.計算機工程，2012，38（6）：11?13.

［10］劉衛(wèi)寧，靳洪兵，劉波.基于改進量子遺傳算法的云計算資源調(diào)度［J］.計算機應用，2013，33（8）：2151?2153.

［11］卓濤，詹穎.改進人工蜂群算法的云計算資源調(diào)度模型［J］.微電子與計算機，2014，31（7）：147?150.

［12］Dinh H T，Lee C，Niyato D，et al.A survey of mobile cloud compu?ting：architecture，applications，and approaches［J］.Wireless Com?munications and Mobile Computing，2013，13（18）：1587?1611.

［13］Garg S K，Versteeg S，Buyya R.A framework for ranking of cloud computing services［J］.Future Generation Computer Systems，2013，29（4）：1012?1023.

［14］Venkata Krishna P.Honey bee behavior inspired load balancing of tasks in cloud computing environments ［J］.Applied Soft Computing，2013，13（5）：2292?2303.

［15］Yuan H，Li C，Du M.Optimal virtual machine resources scheduling based on improved particle swarm optimization in cloud computing［J］.Journal of Software，2014，9（3）：705?708.

［16］Armbrust M，F(xiàn)ox A，Griffith R，et al.A view of cloud computing［J］.Communication of the ACM，2010，53（4）：50?58.

Research on cloud task allocation based on constraint of function

NIE Qing?bin1，ZHANG Li?ping2，HUO Min?xia1，CAO Yao?qin1
（1.College of Mobile Communication，Chongqing University of Posts and Telecommunications，Chongqing 401520，China；2.College of Software Engineering，Chongqing University of Posts and Telecommunications，Chongqing 400065，China）

In order to solve the problem of resource scheduling in cloud environment，an improved ant colony resource scheduling optimization algorithm（RRLB?ACO）is proposed.Based on a variety of cloud computing task scheduling algorithms，a resource con?straint function is used to improve the update of information elements in this algorithm，and the heuristic information is improved by load balancing function，which enable the virtual machine to be in a state of load balance after many iterations of algorithm.The sim?ulation test is carried out using the CloudSim tool，and compared with the standard BACO algorithm and the latest ACOSA algo?rithm.The results show that the RRLB?ACO algorithm performs better in task execution time，cost and system load balancing.

cloud computing；resource restraint；ant colony optimization；task scheduling；load balancing

TP393

A

10．3969／j．issn．1007?791X．2015．05．012

1007?791X（2015）05?0453?05

2015?07?15 基金項目：重慶市前沿與應用基礎(chǔ)研究計劃一般資助項目（cstc2014jcyjA40049，cstc2015jcyjA30001）；重慶市教委科學技術(shù)研究資助項目（KJ130527）

?聶清彬（1982?），男，四川資中人，碩士，講師，主要研究方向為云計算與物聯(lián)網(wǎng)，Email：270104318＠qq.com。