王玲

摘 要：針對云計算環(huán)境下節(jié)點數(shù)量巨大，單個節(jié)點資源配置低，難以實現(xiàn)及時的資源調(diào)度有效性，為此提出了一種基于云計算環(huán)境下資源調(diào)度分配的改進(jìn)遺傳算法策略。通過在算法中添加查找表作為一個中間層，給不同的任務(wù)推薦匹配的節(jié)點，根據(jù)不同的節(jié)點類型或者成功率因子來進(jìn)行節(jié)點選擇，采用節(jié)點強度對任務(wù)查找進(jìn)行優(yōu)先級劃分，并根據(jù)概率參數(shù)來查看查找表信息。仿真結(jié)果表明：提出的算法相較于傳統(tǒng)的RR算法，顯著降低了任務(wù)執(zhí)行耗時，從而能然用戶任務(wù)更快的完成。

關(guān)鍵詞：云計算;資源分配;調(diào)度優(yōu)化;蟻群算法

Abstract：Because of the large scale of nodes in cloud computing environment and the low resource allocation of a single node， this paper proposes an improved genetic algorithm （GA） strategy based on resource scheduling and allocation in cloud computing environment. By adding the lookup table as an intermediate layer in the algorithm， the matching nodes are recommended to different tasks， and the nodes are selected according to different node types or success rate factors. The node strength is used to prioritize the task search， and the lookup table information is viewed according to the probability parameters. The simulation results show that the proposed algorithm is significantly lower than the traditional RR algorithm. The execution of the transaction is time-consuming so that the user task can be completed more quickly.

Key words：cloud computing;resource allocation;scheduling optimization;ant colony algorithm

0 引言

云計算采用服務(wù)方式為用戶提供虛擬化資源池，實現(xiàn)分布式資源的合理調(diào)度余分配，并根據(jù)需求進(jìn)行存儲空間、計算能力的提升[1-4]。當(dāng)前云計算資源管理方面主要以提高系統(tǒng)效率為目標(biāo)的資源管理和調(diào)度研究[5-8]。如文獻(xiàn)[9]基于遺傳算法來實現(xiàn)云計算任務(wù)調(diào)度的負(fù)載均衡，有效提升資源分配效率和計算穩(wěn)定性;文獻(xiàn)[10-13]中基于動態(tài)趨勢的蟻群算法，解決資源調(diào)度過程中空間占用率較多及響應(yīng)時間過程問題，提升響應(yīng)速度和計算精確度;文獻(xiàn)[14-16]中針對云計算環(huán)境下資源調(diào)度性能進(jìn)行策略優(yōu)化，通過引入一種雙適應(yīng)度動態(tài)遺傳策略來提升大規(guī)模數(shù)據(jù)響應(yīng)效率，并尋找到資源調(diào)度的最優(yōu)路徑。

綜上所述，本文在云計算資源調(diào)度方面，通過對傳統(tǒng)蟻群資源調(diào)度算法的改良來提升云計算資源調(diào)度效率，同時降低運算成本。

1 基于蟻群的云資源調(diào)度分析

蟻群算法（ACA）是一種通過模擬螞蟻行進(jìn)過程留下的信息素來進(jìn)行信息傳遞，通過信息素來尋找最優(yōu)路徑[17]。在云計算的資源調(diào)度中，設(shè)任務(wù)集合

T=（T1，T2，T3，…，Tm），整個任務(wù)集合中存在m個子任務(wù)，系統(tǒng)中布設(shè)了有n個處理機(jī)的虛擬機(jī)節(jié)點資源N=（N1，N2，N3，…，Nn）。通過資源的優(yōu)化調(diào)度即在最小的消耗時間下將m個任務(wù)集合快速有效的分配到n個處理機(jī)，從而改善系統(tǒng)運行效率。

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

2.1 查找表

云計算中存在不同類型、不同屬性的資源，對于某一種類型任務(wù)，只有連接到與之相匹配的計算機(jī)資源節(jié)點才能得到快速處理，而這個連接過程中，可通過建立相應(yīng)的查找表來實現(xiàn)[18]。查找表作為一個中間層，將任務(wù)和資源建立對接關(guān)系，實現(xiàn)任務(wù)推薦匹配到對應(yīng)的節(jié)點，并按照不同的節(jié)點強度對任務(wù)查找進(jìn)行優(yōu)先級劃分，強度高的節(jié)點能夠得到有效尋找。

蟻群算法根據(jù)搜索方向的不同主要有前向螞蟻和后向螞蟻。根據(jù)查找表中建立的連接關(guān)系，前向螞蟻對節(jié)點進(jìn)行搜索查找，若節(jié)點不為空，則將尋找到的最大強度節(jié)點作為搜索的初節(jié)點，將該節(jié)點所攜帶的相關(guān)信息置入查找表中，同時節(jié)點強度加1。當(dāng)搜索到的節(jié)點為空，則前向螞蟻將隨

機(jī)選擇節(jié)點作為初始節(jié)點開始下一跳搜尋，并將查找表中次節(jié)點強度減1，直到0為止。后向螞蟻則將受到到的節(jié)點信息返回。查找表推介節(jié)點規(guī)模設(shè)為n，當(dāng)n=0時，查找失敗，當(dāng)n≥1，查找表發(fā)揮作用。

查找表不僅可放在資源、任務(wù)間，也可放在節(jié)點處，稱為節(jié)點查找表[19]。節(jié)點查找表存放在相鄰的兩個節(jié)點之間的下一跳節(jié)點。根據(jù)節(jié)點類型和成功率因子來選擇，并形成一個后向節(jié)點，后向節(jié)點攜帶該節(jié)點的信息沿著原路返回，并將節(jié)點信息置入路經(jīng)的節(jié)點，同時整個查找表得到更新。若查找表中未包含該節(jié)點，且存在強度為0節(jié)點，則刪除0節(jié)點，并將該節(jié)點加入表中，同時節(jié)點強度設(shè)置為1。若查找表中已包含該節(jié)點，則節(jié)點強度加1。為避免查找表不斷遞增而使得規(guī)模過大[20]，設(shè)置一個計時器

t0，當(dāng)t0逐漸降低到0時，則節(jié)點強度為0，刪除該節(jié)點信息。在選擇下一節(jié)點時，首先確定該節(jié)點信息是否已被刪除，同時設(shè)定一個查看查找表的概率參數(shù)p0（0

采用成功率因子來選擇節(jié)點查找表存放位置時，將成功率最高的2個節(jié)點放入查找表，后期選擇查找表放入節(jié)點時，有限選擇成功率因子最高的節(jié)點，在下一條時，根據(jù)概率優(yōu)先來選定查找表節(jié)點位置。

2.2 信息素定義

資源信息素主要包括資源處理能力、負(fù)載均衡能力、節(jié)點間通訊能力等直接影響到硬件資源的相關(guān)因子[21]。當(dāng)資源加入資源列表后，采集存儲容量、通信寬帶等信息，確定該節(jié)點的初始信息素τi（0），如式（1）所示。

其中τi（t1）為t1時刻節(jié)點信息素大小，λ0為調(diào)節(jié)因子，當(dāng)節(jié)點分配調(diào)節(jié)成功，則0<λ0≤1，當(dāng)分配調(diào)節(jié)失敗時，則存在有-1≤λ0<0。在Δt時間內(nèi)，當(dāng)該節(jié)點為有效值，則成功值加1，失敗減1。

定義成功率因子f，即Δt時間內(nèi)，若節(jié)點為有效節(jié)點，則成功值加1，否則減1。f則是Δt時間內(nèi)，節(jié)點成功值與被選中次數(shù)比值。若Δt時間內(nèi)節(jié)點選中的次數(shù)較多，則f上升。

2.3 下一跳選擇

設(shè)定螞蟻數(shù)量n，節(jié)點數(shù)量m。當(dāng)n只螞蟻隨機(jī)分配到m個節(jié)點，則定義節(jié)點i中第k只螞蟻在t時刻選擇下一節(jié)點j的概率，如式（4）所示。

2.4 算法步驟

構(gòu)建系統(tǒng)的整體查找表時來實現(xiàn)資源調(diào)度，如圖1所示。

（1） 首先初始化各節(jié)點信息素值，并進(jìn)行查找表的初始化，設(shè)定最大迭代N作為接受條件。

（2） 任務(wù)列表分類

（3） 采用螞蟻算法搜索查找表，當(dāng)不為空，則節(jié)點生成m個前向螞蟻，通過概率公式讓螞蟻繼續(xù)搜索下一節(jié)點j，并將搜素的j點置入禁忌表。若查找表位空，則前向螞蟻隨機(jī)選定一節(jié)點計算，并通過概率計算確定下一節(jié)點。

（4） 若j點為有效節(jié)點，則j點生產(chǎn)后向螞蟻，并攜帶信息返回，將信息保存在路過的各節(jié)點，按照式（2）和（3）更新信息素，若尋找到最優(yōu)解，填入查找表 。

（5） 后向螞蟻原路徑返回過程中的攜帶信息來更新查找表信息。

（6） 執(zhí)行最大迭代次數(shù)，設(shè)定最大迭代次數(shù)N，當(dāng)?shù)藭rn=N時，任務(wù)分配完成，進(jìn)入下個任務(wù)，否則轉(zhuǎn)至步驟（3），清空禁忌表。前向螞蟻以概率p0選擇查看節(jié)點查找表，并根據(jù)后向螞蟻的返回信息來更新節(jié)點查找表。

3 算法仿真分析

為驗證本文算法的有消息，采用CloudSim進(jìn)行算法仿真分析，采用MyEclipse算法工具。實驗過程中，設(shè)置初始條件值：α=0.5，β=0.5，資源重要度均為0.25，任務(wù)數(shù)由10-200范圍遞增，范圍在[5，20]隨機(jī)選擇，資源節(jié)點數(shù)5，為降低算法仿真誤差，設(shè)每個算法運行10次，取算法的平均值，圖中算法1為是在傳統(tǒng)蟻群算法下載資源列表和任務(wù)列表間插入了查找表，并考慮了成功率因子。算法2是在算法1基礎(chǔ)上插入了節(jié)點查找表。在相同條件下比較算法1、算法2和傳統(tǒng)RR算法的任務(wù)完成效率，資源參數(shù)表，如表1所示。

圖2中可以看出，在相同的任務(wù)數(shù)量下，算法1和算法2較傳統(tǒng)的RR算法任務(wù)用時短。同時，隨著任務(wù)數(shù)量的增加，這種任務(wù)執(zhí)行時間越短，即執(zhí)行效率進(jìn)一步提高。這主要是由于任務(wù)數(shù)的不斷上升，任務(wù)分配占用時間比例下降，有效提升了對資源的調(diào)度和任務(wù)的完成效率[23-24]。比較算法1和算法2的任務(wù)按時時間可以看出，算法2的平均完成時間更多，即采用節(jié)點查找表的方式相對于資源類表和任務(wù)列表能夠加快算法的收斂，具有更高的任務(wù)完成效率。

同時比較算法在相同任務(wù)數(shù)條件下的任務(wù)延遲時間對比，如圖3所示。

設(shè)調(diào)度任務(wù)為100時，比較三種算法的任務(wù)延遲時間可以看出，采用算法2的收斂速度較快，且任務(wù)任吃時間相較于RR算法少了40 ms，當(dāng)任務(wù)量增加到200時，兩種算法的任務(wù)延遲時間差距增加到210 ms，可以看出，隨著調(diào)度數(shù)量增加，采用本文設(shè)計的調(diào)查表插入法進(jìn)行任務(wù)調(diào)度具有更小的任務(wù)延時效果，能夠有效提升任務(wù)調(diào)度效率。

4 總結(jié)

本文提出了一種基于云計算環(huán)境下資源調(diào)度分配的改進(jìn)遺傳算法策略。通過在算法中添加查找表作為一個中間層，給不同的任務(wù)推薦匹配的節(jié)點，根據(jù)不同的節(jié)點類型或者成功率因子來進(jìn)行節(jié)點選擇，采用節(jié)點強度對任務(wù)查找進(jìn)行優(yōu)先級劃分，并根據(jù)概率參數(shù)來查看查找表信息。采用CludSim對算法進(jìn)行仿真表明，采用本文提供的算法降低了任務(wù)執(zhí)行耗時和任務(wù)延遲時間，提高了節(jié)點搜索效率。

參考文獻(xiàn)

[1] 楊建華，鄭杰.基于改進(jìn)蟻群算法的云計算任務(wù)調(diào)度方法研究[J].中國新通信，2019，21（6）：54-57.

[2] 楊蘇影，陳世平.基于包簇框架平衡蟻群算法的資源分配策略[J].軟件，2018，39（6）：4-8.

[3] 陳暄，徐見煒，龍丹.基于蟻群優(yōu)化-蛙跳算法的云計算資源調(diào)度算法[J].計算機(jī)應(yīng)用，2018，38（6）：1670-1674.

[4] 王文東，劉繼梅.基于蟻群算法的云計算資源調(diào)度研究綜述[J].電腦知識與技術(shù)，2017，13（23）：161-163.

[5] 單好民.基于改進(jìn)蟻群算法和粒子群算法的云計算資源調(diào)度[J].計算機(jī)系統(tǒng)應(yīng)用，2017，26（6）：187-192.

[6] 徐浙君，陳善雄.基于膜計算和蟻群算法的融合算法在云計算資源調(diào)度中的研究[J].計算機(jī)測量與控制，2017，25（1）：127-130.

[7] 崔麗梅.云計算中的基于ACA-GA的資源調(diào)度的研究[J].科技通報，2016，32（9）：149-153.

[8] 李媛禎，楊群，賴尚琦，等.一種Hadoop Yarn的資源調(diào)度方法研究[J].電子學(xué)報，2016，44（5）：1017-1024.

[9] 姜棟瀚，林海濤.云計算環(huán)境下的資源分配關(guān)鍵技術(shù)研究綜述[J].中國電子科學(xué)研究院學(xué)報，2018，13（3）：308-314.

[10] 王巖，汪晉寬，宋欣.云計算資源納什均衡優(yōu)化分配方法改進(jìn)[J].計算機(jī)工程，2017，43（12）：17-24.

[11] 陳欽榮，劉順來，林錫彬.一種混合優(yōu)化的云計算資源調(diào)度算法[J].韓山師范學(xué)院學(xué)報，2016，37（6）：15-23+61.

[12] 王煜煒，劉敏，房秉毅，等.面向網(wǎng)絡(luò)性能優(yōu)化的虛擬計算資源調(diào)度機(jī)制研究[J].通信學(xué)報，2016，37（8）：105-118.

[13] 任瓊，常君明.基于任務(wù)分類思維的云計算海量資源改進(jìn)調(diào)度[J].科學(xué)技術(shù)與工程，2016，16（12）：101-105.

[14] 趙宏偉，申德榮，田力威.云計算環(huán)境下資源需求預(yù)測與調(diào)度方法的研究[J].小型微型計算機(jī)系統(tǒng)，2016，37（4）：659-663.

[15] 朱海，王洪峰，廖貅武.云環(huán)境下能耗優(yōu)化的任務(wù)調(diào)度模型及虛擬機(jī)部署算法[J].系統(tǒng)工程理論與實踐，2016，36（3）：768-778.

[16] 林偉偉，朱朝悅.面向大規(guī)模云資源調(diào)度的可擴(kuò)展分布式調(diào)度方法[J].計算機(jī)工程與科學(xué)，2015，37（11）：1997-2005.

[17] 趙宏偉，李圣普.基于粒子群算法和RBF神經(jīng)網(wǎng)絡(luò)的云計算資源調(diào)度方法研究[J].計算機(jī)科學(xué)，2016，43（3）：113-117+150.

[18] 王金海，黃傳河，王晶，等.異構(gòu)云計算體系結(jié)構(gòu)及其多資源聯(lián)合公平分配策略[J].計算機(jī)研究與發(fā)展，2015，52（6）：1288-1302.

[19] 張燕，顧才東.一種求解云計算資源優(yōu)化的改進(jìn)蝙蝠算法[J].科技通報，2014，30（11）：117-121.

[20] 劉運，程家興，林京.基于高斯變異的人工螢火蟲算法在云計算資源調(diào)度中的研究[J].計算機(jī)應(yīng)用研究，2015，32（3）：834-837.

[21] 李菁.改進(jìn)快速稀疏算法的云計算資源負(fù)載均衡[J].微型電腦應(yīng)用，2019，35（10）：36-38.

[22] 劉梓璇，周建濤.負(fù)載均衡的主導(dǎo)資源公平分配算法[J].計算機(jī)工程與科學(xué)，2019，41（9）：1574-1580.

[23] 趙莉.基于支持向量機(jī)的云計算資源負(fù)載預(yù)測模型[J].南京理工大學(xué)學(xué)報，2018，42（6）：687-692.

[24] 王虎，雷建軍，萬潤澤.基于改進(jìn)的粒子群優(yōu)化的云計算資源調(diào)度模型[J].華中師范大學(xué)學(xué)報（自然科學(xué)版），2018，52（6）：788-791.

（收稿日期：2019.09.12）