一種改進的蝙蝠算法QoS—BA

謝劍 王春霞

摘 要針對云計算環(huán)境下的任務調(diào)度問題，本文提出一種基于蝙蝠算法的QoS約束的調(diào)度算法QoS-BA，首先介紹了QoS-BA算法的模型，定義了基于用戶和運營商的目標函數(shù)，接著提出了任務調(diào)度的核心步驟，最后通過仿真驗證QoS-BA算法的有效性。

【關(guān)鍵詞】云計算 蝙蝠算法 QoS 任務調(diào)度

1 引言

隨著計算機技術(shù)的發(fā)展，云計算已經(jīng)成為研究的熱點問題。任務調(diào)度是云計算的核心技術(shù)之一，如何設(shè)計一種有效的任務調(diào)度方案是至關(guān)重要的。

針對上述問題，本文提出了基于蝙蝠算法的QoS約束的云計算任務調(diào)度算法，算法充分考慮了用戶成本和運營商成本的QoS約束，在兩者平衡中選取綜合評價最好的調(diào)度組合方式最為調(diào)度方案，初始化當前蝙蝠算法的初始蝙蝠種群覆蓋面選擇的問題，有利于當前蝙蝠算法針對當前解空間的全局搜索和控制算法本身的過早收斂等能力的提高，有效提高蝙蝠算法的計算速度。

2 基于QoS約束的云計算任務調(diào)度算法QoS-BA

2.1 多QoS約束雙邊評價體系

本文主要依據(jù)用戶及云資源提供商在云環(huán)境下最短時間內(nèi)用戶花費最小代價成本獲得計算結(jié)果，云資源提供商花費最小成本完成用戶提交的任務作為QoS的約束條件，因此QoS的目標約束函數(shù)為Minsize（Total_costuser）和Minsize（Total_costsupplier）。

云計算管理機制把用戶提交的任務分解為子任務并調(diào)度到云資源主機中執(zhí)行，子任務實際完成時間根據(jù)CloudSim模擬計算得出并賦值給ET執(zhí)行時間數(shù)值矩陣，之后通過對各種QoS指標按照權(quán)重進行計算，可以分別得到基于用戶和提供商的執(zhí)行成本。其中，定義用戶的成本如下：

定義提供商的成本如下：

Total_costsupplier

公式中成本的計算方式為：根據(jù)選定的調(diào)度方式M集合分別計算用戶和提供商的關(guān)心成本要素，計算方式為在不同的成本矩陣中根據(jù)M集合調(diào)度方式加權(quán)求和。本文為方便起見默認為平均加權(quán)求和。

其中：ETij為子任務集合T在對應云資源主機C集合中執(zhí)行時間的矩陣。

RCTij為子任務在云計算環(huán)境中云資源主機執(zhí)行消耗的評價指數(shù)集合。

SETij表示子任務對云資源主機的安全性評價數(shù)值矩陣。

PTi為當前云計算環(huán)境下總的任務序列中一個編號優(yōu)先執(zhí)行順位排序的一個集合。

STi表示子任務對云資源主機的適配性評價數(shù)值矩陣。

NSCIij為子任務完成后針對完成的結(jié)果需要傳回用戶或者匯總是需要網(wǎng)絡資源成本評價指數(shù)集合。

ATij表示子任務在云資源主機中執(zhí)行成功的概率數(shù)值矩陣。

2.2 基于蝙蝠算法的云計算調(diào)度

本文通過觀察云調(diào)度過程的特點以及調(diào)度方案數(shù)據(jù)結(jié)構(gòu)的特點，采用數(shù)據(jù)邊界初始化蝙蝠種群的方式，使得在多維約束條件下單一邊界內(nèi)都有新的蝙蝠在蝙蝠種群中，蝙蝠種群演變時能全面覆蓋解空間或者至少攜帶有一個或多個維度的最優(yōu)特性在當前蝙蝠種群的最優(yōu)結(jié)果中。

核心步驟如下：

步驟1：子任務在調(diào)度計算過程生成針對每一個云資源的QoS評價值，多個子任務針對多個云計算資源的評價值矩陣。

步驟2：找到子任務在云資源里面評價值最好的云資源，然后以此為基點構(gòu)造蝙蝠種群的一只蝙蝠。

步驟3：重復步驟2，直到所有的子任務或者云資源都有單一維度選擇最優(yōu)情況的蝙蝠產(chǎn)生，其他子任務和云資源隨機適配，然后以目前得到的蝙蝠種群作為算法啟動的初始化種群。

3 仿真實驗

3.1 實驗數(shù)據(jù)初始化設(shè)置

為了能夠針對本文采用的算法進行評估，將采用Cloudsim平臺對QoS-BA與PoS算法和BA算法進行對比實驗。

假定云環(huán)境擁有的主機種類有10種云計算主機資源，其主要性能如表1-3。

3.2 實驗結(jié)果分析及其展望

在蝙蝠算法中模擬成在所有的調(diào)度解空間中由蝙蝠種群進行搜索的過程，蝙蝠種群中的每一只蝙蝠為一種調(diào)度方案，蝙蝠種群在數(shù)次迭代中不斷根據(jù)解空間的位置進行自身的變異，最后通過計算最優(yōu)值找到解空間的最優(yōu)調(diào)度方案。在針對云計算任務調(diào)度相關(guān)參數(shù)的數(shù)據(jù)結(jié)構(gòu)的調(diào)整后，分別對云計算主機和云計算任務進行分別隨機抽取10個樣本構(gòu)成云計算主機集合和云計算任務集合，在相同條件下進行基礎(chǔ)蝙蝠算法、QoS蝙蝠算法和PoS算法對比，并且在蝙蝠算法的不同代數(shù)進行測試，并觀察比較三種不同算法的云計算調(diào)度方案的優(yōu)劣。

由于蝙蝠種群中每一只蝙蝠都是一種調(diào)度方案，為了便于比較，在做對比圖形的時候只記錄蝙蝠種群最優(yōu)和最差的調(diào)度方案。對比結(jié)果如圖1。

經(jīng)過100次的迭代運算后，運行結(jié)果趨向平穩(wěn)，預測的成本最優(yōu)值都比較接近，調(diào)度方案基本相同，達到了解空間中最優(yōu)調(diào)度方案或者比較接近。

從圖1中可以看出QoS-BA算法能在較短的時間和迭代次數(shù)下快速得到解空間中最優(yōu)解，并在后續(xù)迭代中保持平穩(wěn)。QoS-BA算法能適應在較大解空間中快速求解，滿足云任務調(diào)度的時間要求，對比BA算法，QoS-BA算法能更好的從客戶或者云資源提供商角度來控制成本，在采用了QoS-BA算法后成本會比BA算法低一些。

圖2中，用戶成本曲線是只考慮用戶使用成本，云調(diào)度成本隨著迭代次數(shù)增加的變化曲線。提供商成本曲線是在同樣環(huán)境下計算云資源提供者隨著迭代次數(shù)變化的成本變化曲線。綜合成本曲線是計算提供商和使用者綜合成本的計算結(jié)果。從圖中可以看出，當只考慮云資源使用者單邊效益時，對應的云資源提供者成本會產(chǎn)生變動，更有可能成本變大，只有考慮雙方共同利益的情況下整體效益才會最高，達到雙贏。隨著迭代次數(shù)的不斷增加，在保證用戶利益的前提下，可以在一定范圍內(nèi)降低云資源提供者的成本。

因此，QoS-BA算法在性能上介于PoS和BA之間，在降低云資源成本上有著顯著的效果，具有一定的有效性，并且由于QoS-BA收斂較快，在云任務調(diào)度的時間上具有一定優(yōu)勢。

4 結(jié)論

針對解決云環(huán)境下用戶和提供商的成本約束的任務調(diào)度優(yōu)化問題，建立了基于蝙蝠算法的調(diào)度算法QoS-BA，通過云仿真平臺CloudSim將QoS-BA算法與PoS算法、BA算法進行比較，仿真結(jié)果表明QoS-BA算法能夠使用戶和提供商的成本能得到基本的優(yōu)化，在一定約束條件范圍內(nèi)成本明顯降低，從而降低云資源運行的成本和資源消耗。但是，本文僅僅考慮了執(zhí)行的迭代的和總體成本的兩個優(yōu)化目標，下一步將考慮調(diào)度的時間限制和任務撤銷等多因素影響下云計算任務調(diào)度問題和成本問題。

參考文獻

[1]李枝勇，馬良，張惠珍.蝙蝠算法在多目標多選擇背包問題中的應用[J].計算機仿真，2013，30（10）：350-353.

[2]金偉健，王春枝.基于蝙蝠算法的云計算資源分配研究[J].計算機應用研究，2015，32（04）：1184-1187.

[3]許波，趙超，祝衍軍等.云計算中虛擬機資源調(diào)度多目標優(yōu)化[J].系統(tǒng)仿真學報，2014，26（03）：592-595.

[4]周蓮英.遺傳算法與蟻群算法相融合的云計算任務調(diào)度算法研究[J].蘇州大學，2013.

[5]張宇楠，劉付永.一種改進的變步長自適應蝙蝠算法及其應用[J].廣西民族大學學報（自然科學版），2013，19（02）：51-54.

作者簡介

謝劍（1986-），男，壯族，廣西壯族自治區(qū)柳州市人。碩士學位?？茊T，助理工程師。研究方向為網(wǎng)絡技術(shù)與安全。

作者單位

廣西科技大學網(wǎng)絡與現(xiàn)代教育技術(shù)中心 廣西壯族自治區(qū)柳州市 545006