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

謝劍 王春霞

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

【關鍵詞】云計算 蝙蝠算法 QoS 任務調度

1 引言

隨著計算機技術的發展，云計算已經成為研究的熱點問題。任務調度是云計算的核心技術之一，如何設計一種有效的任務調度方案是至關重要的。

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

2 基于QoS約束的云計算任務調度算法QoS-BA

2.1 多QoS約束雙邊評價體系

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

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

定義提供商的成本如下：

Total_costsupplier

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

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

RCTij為子任務在云計算環境中云資源主機執行消耗的評價指數集合。

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

PTi為當前云計算環境下總的任務序列中一個編號優先執行順位排序的一個集合。

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

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

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

2.2 基于蝙蝠算法的云計算調度

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

核心步驟如下：

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

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

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

3 仿真實驗

3.1 實驗數據初始化設置

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

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

3.2 實驗結果分析及其展望

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

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

經過100次的迭代運算后，運行結果趨向平穩，預測的成本最優值都比較接近，調度方案基本相同，達到了解空間中最優調度方案或者比較接近。

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

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

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

4 結論

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

參考文獻

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

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

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

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

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

作者簡介

謝劍（1986-），男，壯族，廣西壯族自治區柳州市人。碩士學位。科員，助理工程師。研究方向為網絡技術與安全。

作者單位

廣西科技大學網絡與現代教育技術中心 廣西壯族自治區柳州市 545006