基于云計算資源分配與調度優化的改進蟻群算法研究

王玲

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

關鍵詞：云計算;資源分配;調度優化;蟻群算法

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 引言

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

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

1 基于蟻群的云資源調度分析

蟻群算法（ACA）是一種通過模擬螞蟻行進過程留下的信息素來進行信息傳遞，通過信息素來尋找最優路徑[17]。在云計算的資源調度中，設任務集合

T=（T1，T2，T3，…，Tm），整個任務集合中存在m個子任務，系統中布設了有n個處理機的虛擬機節點資源N=（N1，N2，N3，…，Nn）。通過資源的優化調度即在最小的消耗時間下將m個任務集合快速有效的分配到n個處理機，從而改善系統運行效率。

2 改進的蟻群算法

2.1 查找表

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

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

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

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

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

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

2.2 信息素定義

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

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

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

2.3 下一跳選擇

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

2.4 算法步驟

構建系統的整體查找表時來實現資源調度，如圖1所示。

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

（2） 任務列表分類

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

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

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

（6） 執行最大迭代次數，設定最大迭代次數N，當迭代此時n=N時，任務分配完成，進入下個任務，否則轉至步驟（3），清空禁忌表。前向螞蟻以概率p0選擇查看節點查找表，并根據后向螞蟻的返回信息來更新節點查找表。

3 算法仿真分析

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

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

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

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

4 總結

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

參考文獻

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

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

[3] 陳暄，徐見煒，龍丹.基于蟻群優化-蛙跳算法的云計算資源調度算法[J].計算機應用，2018，38（6）：1670-1674.

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

[5] 單好民.基于改進蟻群算法和粒子群算法的云計算資源調度[J].計算機系統應用，2017，26（6）：187-192.

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

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

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

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

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

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

[12] 王煜煒，劉敏，房秉毅，等.面向網絡性能優化的虛擬計算資源調度機制研究[J].通信學報，2016，37（8）：105-118.

[13] 任瓊，常君明.基于任務分類思維的云計算海量資源改進調度[J].科學技術與工程，2016，16（12）：101-105.

[14] 趙宏偉，申德榮，田力威.云計算環境下資源需求預測與調度方法的研究[J].小型微型計算機系統，2016，37（4）：659-663.

[15] 朱海，王洪峰，廖貅武.云環境下能耗優化的任務調度模型及虛擬機部署算法[J].系統工程理論與實踐，2016，36（3）：768-778.

[16] 林偉偉，朱朝悅.面向大規模云資源調度的可擴展分布式調度方法[J].計算機工程與科學，2015，37（11）：1997-2005.

[17] 趙宏偉，李圣普.基于粒子群算法和RBF神經網絡的云計算資源調度方法研究[J].計算機科學，2016，43（3）：113-117+150.

[18] 王金海，黃傳河，王晶，等.異構云計算體系結構及其多資源聯合公平分配策略[J].計算機研究與發展，2015，52（6）：1288-1302.

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

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

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

[22] 劉梓璇，周建濤.負載均衡的主導資源公平分配算法[J].計算機工程與科學，2019，41（9）：1574-1580.

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

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

（收稿日期：2019.09.12）