云計(jì)算下的蟻群優(yōu)化算法資源調(diào)度研究

楊愛華

云計(jì)算是由分布式等發(fā)展而來的，依托付費(fèi)方式為用戶提供相應(yīng)的服務(wù).云計(jì)算服務(wù)本質(zhì)在于運(yùn)用虛擬機(jī)計(jì)算及其存儲資源池進(jìn)行動態(tài)分配等一系列處理，并為用戶提供滿足QS各項(xiàng)要求的計(jì)算及其存儲服務(wù).云計(jì)算具備高可靠性、自治性等特點(diǎn)，已成為人們處理海量數(shù)據(jù)的主要技術(shù)［1］，它也在不斷地改變廣大居民對軟件的認(rèn)識及操作熟練性，人們不需要對軟件實(shí)施維護(hù)處理，利用付費(fèi)的方法就能在互聯(lián)網(wǎng)上獲得所需的保護(hù)服務(wù).云就是包含大規(guī)模的計(jì)算節(jié)點(diǎn)，而且這些節(jié)點(diǎn)受到計(jì)算、寬帶等能力的限制，需要分析云計(jì)算和蟻群優(yōu)化算法下的資源調(diào)度策略，減少用戶數(shù)量，找到最合理的虛擬機(jī)資源，并快速將用戶任務(wù)分配給相應(yīng)的虛擬機(jī)，以確保用戶在設(shè)定的時間內(nèi)順利完成任務(wù)［2-3］.本次研究中，提出ACO1、ACO2兩個資源調(diào)度策略，并將其運(yùn)用到雙向螞蟻機(jī)制中，期望依托前向和反向螞蟻之間展開直接交流，確保實(shí)際運(yùn)行中有效計(jì)算資源可以快速發(fā)掘出來，并在一定程度上提升使用算法收斂性，確保公司和用戶簽署服務(wù)等級協(xié)議SLA.

1 蟻群優(yōu)化算法的資源調(diào)度

1.1 蟻群優(yōu)化算法概述

蟻群算法（Ant Colony Optimization，ACO）又稱作螞蟻算法，是一種用于在圖內(nèi)找尋最優(yōu)路徑的幾率算法［4］.與其他啟發(fā)式算法相比，這種算法在信息交換積累上更容易進(jìn)行優(yōu)化，具有較高的效率.現(xiàn)階段，大多數(shù)蟻群算法中螞蟻主要由信息素進(jìn)行交流，而不同螞蟻間并沒有展開直接的交流，因此，算法的收斂性不佳.在考慮云計(jì)算與網(wǎng)絡(luò)環(huán)境存在明顯差異的前提下，本文提出兩個資源調(diào)度策略ACO1、ACO2.

在實(shí)際生活中，當(dāng)螞蟻尋找食物時，如果兩只螞蟻相遇，會利用觸角進(jìn)行交流，基于此，一只螞蟻會根據(jù)另外一只螞蟻提供的信息快速找到食物.螞蟻開展資源搜索過程中，會在一定程度上提升螞蟻相遇處理效率，用來提高算法的收斂性.在各節(jié)點(diǎn)預(yù)留出一定的存儲區(qū)，用來保存反向螞蟻攜帶的信息，并開啟相應(yīng)的定時器［5-6］.當(dāng)定時器開展歸零操作之前，前向螞蟻則會快速到達(dá)這個節(jié)點(diǎn)，判定前向和反向兩只螞蟻已相遇.實(shí)施歸零處理后，節(jié)點(diǎn)可以自動將各項(xiàng)信息進(jìn)行及時地消除.如果某一個節(jié)點(diǎn)在多個時刻會出現(xiàn)多數(shù)螞蟻經(jīng)過的情況，這些螞蟻會給出多個可利用的資源，下文采用兩種方式進(jìn)行解決.

①如果一個節(jié)點(diǎn)存儲區(qū)域可以保存相應(yīng)反向螞蟻能夠提供的消息，當(dāng)后一螞蟻經(jīng)過相應(yīng)地點(diǎn)，會對原先的信息實(shí)施覆蓋，并將啟動器再次開啟.這種方法只是考慮一個可利用的資源，優(yōu)勢在于保存信息所用空間比較小，在求解下一跳轉(zhuǎn)節(jié)點(diǎn)概率過程中，所用計(jì)算量比較少，不足之處在于保存全部的可用資源信息［7］.②一個節(jié)點(diǎn)存儲區(qū)可以保存多數(shù)反向螞蟻提供的信息，若有反向螞蟻經(jīng)過，就會為其啟動與之對應(yīng)的定時器［8］.除此之外，如果包含兩個反向螞蟻來源于相同的可用資源，節(jié)點(diǎn)保存后一螞蟻提供的信息，這種方法的主要優(yōu)點(diǎn)是能夠把所有的可用資源均考慮其中，不足之處則是節(jié)點(diǎn)存儲空間大，且需要開展大量的計(jì)算.

與以上兩種方法對應(yīng)的算法分別是ACO1、ACO2資源調(diào)度算法.

1.2 信息素修改

在借鑒其他學(xué)者研究成果基礎(chǔ)上，通過虛擬機(jī)硬件資源對某個節(jié)點(diǎn)中的信息素實(shí)施判斷，主要通過CPU個數(shù)m、內(nèi)存（r）和外存容量（h）、帶寬（b）等指標(biāo)展開.根據(jù)下列公式為各參數(shù)設(shè)定閥值，如果大于這個閥值，則統(tǒng)一采用閥值計(jì)算.

先對節(jié)點(diǎn)的硬件信息素進(jìn)行初始化處理：

其中，節(jié)點(diǎn)i信息素就是上面各類信息素的帶權(quán)和，見公式（6）：

信息素實(shí)施修改主要由下列兩種組成，一種就是對有價(jià)值節(jié)點(diǎn)的信息素實(shí)施修改；另一種是指對反向螞蟻通過不同節(jié)點(diǎn)保存的信息進(jìn)行修改［9-10］.

如果存在新任務(wù)被分配至相對應(yīng)節(jié)點(diǎn)上，CPU利用率等指標(biāo)會明顯增大，這種條件下，信息素隨之減小.信息素通過以下公式展開更新處理：

上述式子中，λ代表調(diào)節(jié)因子；τi(t)代表處于t時刻需要進(jìn)行計(jì)算的節(jié)點(diǎn)信息素濃度；τi(t1)則表明有新任務(wù)為t1時刻到達(dá)i節(jié)點(diǎn)顯示的信息素濃度.

在任務(wù)處于t2時運(yùn)送完成或者失敗，系統(tǒng)的負(fù)載會明顯減輕.為確保節(jié)點(diǎn)上的負(fù)載平衡，這種情況下，信息素濃度求解公式為

此時，λ1表示調(diào)節(jié)因子；τi(t)代表t2時節(jié)點(diǎn)上（i）信息素濃度.

如果想要對順利完成任務(wù)的節(jié)點(diǎn)進(jìn)行獎勵，可以設(shè)法加大這一節(jié)點(diǎn)信息素濃度，保障更多前向螞蟻選取這個節(jié)點(diǎn)；當(dāng)遭遇任務(wù)失敗的節(jié)點(diǎn)，要接受一定的懲罰［11］.根據(jù)公式（8），對其添加相應(yīng)的新因子λ2，變成公式（9），該指標(biāo)用來表示增加或減少各節(jié)點(diǎn)狀態(tài)下的信息素濃度.

如果任務(wù)成功地運(yùn)行，則有0＜λ2＜1；反之，則為-1＜λ2＜0.

必須注意，隨著時間這個指標(biāo)逐漸推移，在有效節(jié)點(diǎn)上的任務(wù)數(shù)也會逐漸變少，承擔(dān)的負(fù)載更輕，其信息素明顯增多.這種狀況下，各節(jié)點(diǎn)存儲的有效節(jié)點(diǎn)信息素也隨之增加.此時，可以每隔一定的時間，通過下列公式求解相應(yīng)節(jié)點(diǎn)的信息素.

τe(t+1)代表在t+1時各節(jié)點(diǎn)開展修改處理后獲取有效節(jié)點(diǎn)（e）顯示的信息素濃度；λ3表明與之對應(yīng)的調(diào)節(jié)因子；τe(t)表明在t時各節(jié)點(diǎn)存儲的e信息素濃度.

1.3 修改任務(wù)預(yù)計(jì)執(zhí)行時間

在云計(jì)算發(fā)展背景下，當(dāng)某個節(jié)點(diǎn)可能需要執(zhí)行多數(shù)任務(wù).但云計(jì)算會將不同的任務(wù)分配至高效率節(jié)點(diǎn)上，提升整個云計(jì)算性能.在此基礎(chǔ)上，構(gòu)建相應(yīng)的任務(wù)執(zhí)行時間預(yù)測模型，主要功能就是對新任務(wù)所用執(zhí)行時間展開預(yù)測，計(jì)算公式如下：

ET代表預(yù)計(jì)新任務(wù)Jpredict處于t2時刻估計(jì)在j這個節(jié)點(diǎn)上的執(zhí)行時間；此處，通過j運(yùn)行的任務(wù)數(shù)代表負(fù)載大??；npredict代表t2時刻j的負(fù)載表明t0時刻上某個已經(jīng)完成的任務(wù)Jprevious到j(luò)，且在j上預(yù)計(jì)執(zhí)行所需時間.nprevious代表上一個任務(wù)運(yùn)行狀態(tài)下的負(fù)載指出上一個處于t1對任務(wù)Jprevious完成實(shí)際所用的執(zhí)行時間.

因有效節(jié)點(diǎn)會跟隨運(yùn)行任務(wù)變化有所減少，在有效節(jié)點(diǎn)上預(yù)計(jì)任務(wù)順利完成時間也會明顯減少.基于此，每隔相應(yīng)的時間，可利用以下式子修改不同節(jié)點(diǎn)執(zhí)行任務(wù)使用的預(yù)計(jì)時間.

1.4 前向螞蟻選取下一跳節(jié)點(diǎn)

在前向和反向螞蟻并未相遇的背景下，根據(jù)公式（13）展開計(jì)算，挑選其中一個較大概率的節(jié)點(diǎn)作為下一跳節(jié)點(diǎn).

若某一節(jié)點(diǎn)僅保存一個反向螞蟻給出的消息，且該螞蟻i前一跳節(jié)點(diǎn)是k，對下一個跳節(jié)點(diǎn)進(jìn)行選取，依次求解Pij、Pik.在Pij內(nèi)，j則是i需要挑選的下一個跳節(jié)點(diǎn)，且j、k并非是同一個節(jié)點(diǎn).根據(jù)以下公式求解：

τe表示節(jié)點(diǎn)k存儲的有效節(jié)點(diǎn)e的信息素?cái)?shù)值；Ae代表k這一節(jié)點(diǎn)中存儲e預(yù)計(jì)執(zhí)行操作使用時間.依托比較Pij和Pik這兩個數(shù)值發(fā)現(xiàn)，前向螞蟻會將最大的一個概率節(jié)點(diǎn)當(dāng)作下一跳節(jié)點(diǎn).

當(dāng)一個節(jié)點(diǎn)中保存大量反向螞蟻給出的信息，需要將多數(shù)的有效節(jié)點(diǎn)考慮在內(nèi).依托定義B(K)、E(K)集合，B(K)則表明前向螞蟻會選取下個跳節(jié)點(diǎn)，這也成為反向螞蟻經(jīng)過節(jié)點(diǎn)總集合；E(K)表示大多數(shù)有效節(jié)點(diǎn)組合起來的集合.這種情況下，可以把下一跳節(jié)點(diǎn)j劃分為不同的類：第一類：j?Ns，且j?B(K)，求解式子如下：

第二類節(jié)點(diǎn)計(jì)算公式為

上述兩個式子中選取概率最大者作為下一跳節(jié)點(diǎn).

2 算法仿真實(shí)驗(yàn)

為有效驗(yàn)證所用蟻群優(yōu)化算法的效果，文中采用CloudSim平臺實(shí)施仿真實(shí)驗(yàn)，并將資源調(diào)度策略ACO1、ACO2、AS和基于蟻群系統(tǒng)ACS所有時間展開對比分析.

2.1 設(shè)計(jì)實(shí)驗(yàn)參數(shù)

整個算法時間復(fù)雜度為O(k(m+n)，該式子中，k代表作業(yè)個數(shù)；O(n)表示將作業(yè)置于虛擬機(jī)資源上的時間復(fù)雜度；O(m)則表示前向螞蟻找尋資源時間的復(fù)雜程度；本算法主要功能在于使前向螞蟻找尋虛擬機(jī)資源使用時間盡量地縮小，確保分配虛擬機(jī)整體時間也明顯減少.

算法內(nèi)a～d這四個字母依次代表虛擬機(jī)CPU、內(nèi)存、外存及其帶寬的重要性.由于任務(wù)分配實(shí)施或受到處理器的影響，因此，可以將這四個字母設(shè)置為4、2、2、2.a、β依次代表信息素，對需要執(zhí)行的不同項(xiàng)任務(wù)使用時間重要程度展開預(yù)計(jì).n主要作用就是用于評估存在多數(shù)螞蟻更合適.通過與之對應(yīng)的實(shí)驗(yàn)，得到最優(yōu)a、β、n組合.調(diào)節(jié)因子λ、λ1、λ3都設(shè)定為0.2；λ2就是當(dāng)任務(wù)成功或者失敗條件下依次取值0.2、-0.2.ρ、ρ1依次取0.4、0.2.Master定時器設(shè)定為5 s；虛擬機(jī)節(jié)點(diǎn)設(shè)置200個.在任務(wù)大小是500 M，虛擬機(jī)處理能力處于200～400 MIPS范圍之內(nèi)，帶寬、外存容量依次為1～2 M/s、10～20 G范圍中；內(nèi)存容量設(shè)定512 M～1 G.

2.2 統(tǒng)計(jì)與分析實(shí)驗(yàn)結(jié)果

先要提交2 500 M的作業(yè)，這個作業(yè)反復(fù)提交次數(shù)為10次，最終得出相應(yīng)的結(jié)果，存在7次在a=1，β、n分別是2、2.5條件下，進(jìn)行作業(yè)調(diào)度有效節(jié)點(diǎn)時采用的時間最少.隨后，挑選多種作業(yè)量重復(fù)上述環(huán)節(jié)，從而得出60%時，在a=1，β=2，n=2.5條件下，是作業(yè)所用時間最少的任務(wù)調(diào)度有效節(jié)點(diǎn)，這也說明，這種情況下是最優(yōu)的組合.表1代表作業(yè)大小為2 500 M，a、β、n選取不同數(shù)值時，資源調(diào)度時間發(fā)生改變.

表1 資源調(diào)度時間變化情況

表2表示在作業(yè)大小為2 500 M，設(shè)定a=1，β=2，n=2.5的條件下，比較ACO1、ACO2及其與螞蟻系統(tǒng)AS、蟻群系統(tǒng)ACS對資源調(diào)度中使用的時間.

表2 對比不同算法下資源調(diào)度時間

根據(jù)表2數(shù)據(jù)可知，ACO1和ACO2資源調(diào)度所用時間顯著少于ACS、AS這兩種算法，分析其原因可知，由于前向螞蟻對虛擬機(jī)資源找尋過程中使用的時間有所減少，導(dǎo)致分配虛擬機(jī)整體所用時間縮短.當(dāng)前向螞蟻對虛擬機(jī)實(shí)施尋找時，會在一定程度上加大螞蟻相遇過程中的交流，在前向與反向螞蟻相遇這個前提下，前向螞蟻會依據(jù)后向螞蟻提供的重要節(jié)點(diǎn)信息，在上述信息內(nèi)作出選擇，及時找出達(dá)到執(zhí)行作業(yè)任務(wù)要求的節(jié)點(diǎn).與ACO1算法相比，ACO2算法所用的時間更少，分析發(fā)現(xiàn)，是因ACO2這種算法中節(jié)點(diǎn)內(nèi)保存多數(shù)有效的節(jié)點(diǎn)信息，前向螞蟻會從以上有效節(jié)點(diǎn)中選取最大的發(fā)生概率，說明這種方法使用調(diào)度時間是最少的.

3 結(jié)論

本研究對云計(jì)算下資源調(diào)度問題展開分析，并介紹一些研究成果.依托螞蟻算法提出雙向螞蟻機(jī)制的資源調(diào)度策略ACO1、ACO2，這兩種策略可以滿足云計(jì)算環(huán)境下的要求，促使用戶可以快速找到理想的虛擬機(jī)資源，并對任務(wù)實(shí)施合理的分配，保障用戶能順利完成作業(yè)任務(wù).