聶清彬 蔡婷 曹耀欽

摘 要： 傳統(tǒng)的蟻群算法（ACO）在云計(jì)算資源調(diào)度的應(yīng)用中，存在一些資源節(jié)點(diǎn)無法滿足任務(wù)運(yùn)行所需的硬件配置條件，從而在任務(wù)調(diào)度算法中造成了大量的浪費(fèi)以及整體資源調(diào)度效率低下等問題。據(jù)此提出一種基于最小資源矩陣（ACO?MRM）的改進(jìn)蟻群算法，拋棄大量不滿足任務(wù)運(yùn)行條件的資源節(jié)點(diǎn)，減少大量對(duì)無效資源節(jié)點(diǎn)的計(jì)算，加速算法收斂。仿真實(shí)驗(yàn)表明，改進(jìn)的蟻群算法不僅能夠提高云計(jì)算調(diào)度的有效性，而且能縮短任務(wù)執(zhí)行時(shí)間和減少運(yùn)行成本來獲取全局最優(yōu)調(diào)度方案。

關(guān)鍵詞： 云計(jì)算； 蟻群算法； 任務(wù)調(diào)度； 最小資源矩陣

中圖分類號(hào)： TN911?34； TP393 文獻(xiàn)標(biāo)識(shí)碼： A 文章編號(hào)： 1004?373X（2016）05?0010?04

0 引 言

云計(jì)算機(jī)是由并行計(jì)算，網(wǎng)絡(luò)計(jì)算和分布式計(jì)算發(fā)展而來的一種新型計(jì)算模式。它把云計(jì)算中各種資源通過虛擬化技術(shù)進(jìn)行統(tǒng)一的分配和管理，并對(duì)外提供服務(wù)，形成以用戶為中心，實(shí)行“按需使用，按量付費(fèi)”的商業(yè)服務(wù)模式?；谠撋虡I(yè)模式，用戶必然關(guān)心任務(wù)的執(zhí)行成本以及所花的時(shí)間，因此必須要對(duì)云中的資源進(jìn)行合理的分配，最大化的提高資源利用率；用戶提交的任務(wù)執(zhí)行成本低，執(zhí)行的時(shí)間短同時(shí)讓整個(gè)系統(tǒng)的負(fù)載始終處于一個(gè)相對(duì)均衡的水平是需要解決的難題。

目前，基于云計(jì)算的資源調(diào)度算法很多，文獻(xiàn)[1]提出了基于改進(jìn)的TC_LABCO算法，優(yōu)化了任務(wù)執(zhí)行的時(shí)間和成本，在這些改進(jìn)的蟻群算法調(diào)度策略中，任務(wù)調(diào)度就是在資源和任務(wù)之間建立起一個(gè)映射關(guān)系的過程，讓任務(wù)合理地分配到資源上來達(dá)到優(yōu)化的目的；但是有一點(diǎn)因?yàn)槊總€(gè)任務(wù)運(yùn)行所要求的硬件資源不一致，并非每個(gè)資源都能滿足每個(gè)任務(wù)的要求，有的資源節(jié)點(diǎn)由于剩余的CPU處理能力不足，無法提供完成任務(wù)所需要的最低配置。然而以往的資源調(diào)度策略算法依然要對(duì)其預(yù)測(cè)計(jì)算，這樣就造成了大量的、無效和重復(fù)的搜素計(jì)算，浪費(fèi)了時(shí)間和資源，降低了整個(gè)系統(tǒng)的效率。因此本文以目前相對(duì)成熟并被廣泛應(yīng)用的蟻群算法作為基礎(chǔ)，結(jié)合資源矩陣特點(diǎn)，提出最小資源矩陣算法（ACO?MRM）對(duì)目前的蟻群算法進(jìn)行改進(jìn)。通過實(shí)驗(yàn)證明，改進(jìn)以后的蟻群算法不僅能節(jié)約大量的調(diào)度時(shí)間，同時(shí)降低了任務(wù)執(zhí)行的成本。

1 蟻群算法的基本原理

蟻群算法（Ant Colony Optimization，ACO）是由Dorigo Macro在1992年在其發(fā)表的博士論文中提出的一種模擬螞蟻群體在通過尋找食物過程中去發(fā)現(xiàn)路徑行為的算法，螞蟻在覓食過程中，當(dāng)一只螞蟻找到食物后，就會(huì)在它經(jīng)過的路徑環(huán)境中釋放一些揮發(fā)性的分泌物，稱之為信息素，螞蟻在覓食過程中主要是根據(jù)所處的環(huán)境中的信息素決定其前進(jìn)的方向，那么在較短的路徑上的信息素的數(shù)量就會(huì)比較多，這樣螞蟻選擇的概率自然就更大，隨著最短路徑上的信息素的數(shù)量越來越多，最終螞蟻會(huì)選擇最短的路徑。常見的旅行商算法就是通過模擬蟻群算法來獲取全局最優(yōu)解的。

5 算法流程

（1） 初始化云資源中所有虛擬機(jī)的信息素的值。

（2） 將n個(gè)任務(wù)隨機(jī)地放在m個(gè)節(jié)點(diǎn)上，也就是把螞蟻隨機(jī)地分派到各個(gè)虛擬機(jī)上，構(gòu)造資源任務(wù)矩陣式（6），在該資源矩陣中，資源與任務(wù)形成映射關(guān)系，如果該對(duì)應(yīng)的虛擬機(jī)無法滿足對(duì)應(yīng)任務(wù)運(yùn)行最低要求如式（4），那么將矩陣中[xmn]的值賦給啟發(fā)因子[η=0，]則說明不會(huì)選中該虛擬機(jī)來執(zhí)行該任務(wù)；如果對(duì)某一個(gè)任務(wù)，虛擬機(jī)節(jié)點(diǎn)能夠滿足任務(wù)運(yùn)行的最低要求，如式（5），那么將[xmn]值賦給啟發(fā)因子[η=1]，通過該方式，可以為任務(wù)[Tj]挑選出那些有能力執(zhí)行的虛擬機(jī)。

（3） 每只螞蟻根據(jù)選擇下一跳的式（1）來為下一個(gè)子任務(wù)選擇全局最優(yōu)的資源節(jié)點(diǎn)。

（4） 當(dāng)某只螞蟻結(jié)束它的路徑遍歷任務(wù)后，通過文獻(xiàn)[1]中的TC_LABCO算法找到一種基于時(shí)間?成本最優(yōu)的資源節(jié)點(diǎn)后，所有資源節(jié)點(diǎn)按照式（9）進(jìn)行局部更新。

（5） 當(dāng)所有螞蟻都完成了路徑遍歷任務(wù)，執(zhí)行第（6）步，并且找出這次遍歷中的最優(yōu)路徑，然后對(duì)路徑上的所有資源節(jié)點(diǎn)進(jìn)行全局信息素更新，否則的話跳到第（3）步。

（6） 迭代次數(shù)[Nc]累加1，統(tǒng)計(jì)出最優(yōu)的方案，保存。

（7） 如果[Nc>Ncmax]（[Ncmax]為最大迭代次數(shù)）則算法停止優(yōu)化，并把結(jié)果輸出；否則，跳轉(zhuǎn)到步驟（2）繼續(xù)執(zhí)行，直到算法停止。

6 實(shí)驗(yàn)仿真以及結(jié)果分析

為了驗(yàn)證最小資源矩陣以及時(shí)間成本控制算法的有效性，通過云仿真工具CloudsSim進(jìn)行試驗(yàn)測(cè)試，在試驗(yàn)中，設(shè)置10個(gè)虛擬機(jī)，迭代次數(shù)設(shè)置為100，信息素初始值為1，設(shè)置任務(wù)數(shù)從50，100，150，200依次遞增，將本文改進(jìn)蟻群算法和傳統(tǒng)的CAO算法以及文獻(xiàn)[1]中提出的基于改進(jìn)的TC_LABCO算法策略進(jìn)行對(duì)比，如圖1，圖2所示。

從圖1可以看出，相比較而言，隨著任務(wù)數(shù)的增加，加入最小資源矩陣算法以后的蟻群算法收斂速度明顯比傳統(tǒng)的蟻群算法更快，改進(jìn)以后的蟻群算法在同等條件下執(zhí)行同樣的任務(wù)執(zhí)行時(shí)間更短。從圖2可以看出，在同等條件下，改進(jìn)算法執(zhí)行的費(fèi)用更低。實(shí)驗(yàn)表明，在原始的蟻群算法中，存在大量的無效搜素，導(dǎo)致搜索任務(wù)的時(shí)間更短，而經(jīng)過最小資源矩陣改進(jìn)以后的蟻群算法適應(yīng)度最小。

7 結(jié) 語

本文主要研究了基于蟻群算法在云計(jì)算資源調(diào)度中的運(yùn)用，發(fā)現(xiàn)以往的蟻群調(diào)度算法在資源搜索過程中存在大量的不能滿足任務(wù)運(yùn)行的無效資源，從而浪費(fèi)了大量的時(shí)間和成本，使得在云計(jì)算環(huán)境中任務(wù)調(diào)度算法效率不高，因此提出了最小資源矩陣算法（ACO?MRM），該算法在適應(yīng)云計(jì)算資源調(diào)度算法的前提下，排除了不能滿足任務(wù)運(yùn)行的無效資源，使得能夠參與運(yùn)算的都是有效資源，這樣的結(jié)果使得迭代次數(shù)更優(yōu)，同時(shí)具有收斂更快的優(yōu)勢(shì)，并使用仿真軟件驗(yàn)證了最小資源矩陣算法的有效性。實(shí)踐證明通過加入該算法，可以使得執(zhí)行的時(shí)間縮短，成本降低以及資源節(jié)點(diǎn)負(fù)載更均衡，在未來的研究中，還將進(jìn)一步挖掘加強(qiáng)螞蟻之間的交流，同時(shí)考慮用戶的QoS需求，最大限度地提高云計(jì)算機(jī)中資源調(diào)度的合理性和高效性。

參考文獻(xiàn)

[1] 李坤.云環(huán)境下的任務(wù)調(diào)度算法研究與實(shí)現(xiàn)[D].長春：吉林大學(xué)，2012.

[2] 劉萬軍，張孟華，郭文越.基于MPSO算法的云計(jì)算資源調(diào)度策略[J].計(jì)算機(jī)工程，2011，37（11）：43?44.

[3] 張春艷，劉清林，孟珂.基于蟻群優(yōu)化算法的云計(jì)算任務(wù)分配[J].計(jì)算機(jī)應(yīng)用，2012，32（5）：1418?1420.

[4] 王登科.云計(jì)算任務(wù)調(diào)度算法的研究與實(shí)現(xiàn)[D].蘭州：西北師范大學(xué)，2013.

[5] 姜華杰.基于QoS的云計(jì)算資源分配算法[D].太原：太原理工大學(xué)，2012.

[6] 王娟，李飛，張路橋.限制解空間的PSO云存儲(chǔ)任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用研究，2013，30（1）：127?130.

[7] DORIGO M， CARO G D. The ant colony optimization meta?heuristic [J]. New ideas in optimization， 1999， 28（3）： 11?32.

[8] KUN Li， XU Gaochao， ZHAO Guangyu， et al. Cloud task scheduling based on load balancing ant colony optimization [C]// Proceedings of 2011 Sixth China Grid Conference on Annual. Liaoning： IEEE， 2011： 3?9.

[9] DORIGO M. Optimization， learning and natural algorithms [D]. Milano： Politecnico Di Milano， 1992.

[10] 王永貴，韓瑞蓮.基于改進(jìn)蟻群算法的云環(huán)境任務(wù)調(diào)度研究[J].計(jì)算機(jī)測(cè)量與控制，2011，19（5）：1203?1211.

[11] 吳慶洪，張紀(jì)會(huì)，徐心和.具有變異特征的蟻群算法[J].計(jì)算機(jī)研究與發(fā)展，1999，36（10）：1240?1245.

[12] 李建峰，彭艦.云計(jì)算環(huán)境下基于改進(jìn)遺傳算法的任務(wù)調(diào)度算法[J].計(jì)算機(jī)應(yīng)用，2011，31（1）：184?186.