基于模因優化和循環調度的多目標負載均衡技術

羅 寧 李 璐 唐 忠

1(廣西經貿職業技術學院網絡與現代教育技術中心 廣西 南寧 530021)2(廣西醫科大學信息與管理學院 廣西 南寧 530021)

0 引 言

云計算是目前計算機領域內技術發展的焦點之一，它是將傳統的分布式計算、并行計算、網格計算融為一體的數據服務系統[1]。由于云環境的動態特性，虛擬機(Virtual Machine，VM)會出現負載不平衡的問題[2]。因此，任務調度器需要通過將總負載分配給云系統中的所有可用節點來平衡負載。平衡負載的主要目標是最大限度地利用資源，提高服務質量。在云環境中，計算資源服務質量的好壞是衡量云計算效果的一個重要指標，因此，如何有效地降低云計算中的負載均衡、提升計算資源利用率是當前研究的熱點問題。

負載均衡的概念在2001年由Zomaya提出，是指將任務分攤到多個操作單元上執行的過程[3]，其避免產生系統瓶頸或者資源浪費。迄今為止，國內外研究學者已經開發出許多傳統算法、啟發式和元啟發式算法等用來解決任務負載優化問題。經典的Min-Min與Max-Min算法通過優先安排計算量過小或過大的任務方式縮短總任務完成時間，但是這類算法的負載均衡較差[4]。啟發式算法[5]包括蟻群算法、遺傳算法、粒子群算法和螢火蟲算法等算法以及相關的改進融合算法。這類方法具備操作簡單、魯棒性強和擴充性好的特點，能夠有效地縮短任務完成時間，解決資源負載均衡的問題。Tseng等[6]提出了一種動態預測云數據中心資源利用率和能耗的多目標遺傳算法，用于云數據中心的動態資源預測和任務分配。但是，在遇到用戶請求激增的突發情況時，負載平衡性能較差。Chou等[7]提出了基于粒子群優化算法的動態節能資源分配機制，利用最小二乘回歸方法對物理機資源利用率進行預測，實現動態節電資源分配，但是，該方法沒有考慮云環境中帶寬、內存等其他資源的利用率。Zuo等[8]提出了一種基于蟻群優化(mosaco)的面向任務的多目標調度方法，根據時間期限和成本約束，對混合云計算環境中公共和私有計算資源的有限池進行優化。Vakilinia[9]提出了基于時間負載感知的資源調度算法，通過服務器功耗、網絡通信和遷移成本的聯合優化，減少數據中心的資源使用成本，提高利用率。

針對現有多目標調度方法所需處理時間較長以及處理突發情況時性能降低的問題，提出一種基于模因優化和循環調度的多目標負載均衡技術。本文的主要創新之處在于在考慮云服務器多目標調度問題時，將工作狀態區分為兩種模式：若工作狀態為突發，選擇加權多目標模因優化循環調度算法；若工作負載狀態為正常，則采用閾值多目標模因優化技術調度任務。這樣可以通過選擇不同的負載平衡算法來提高任務調度效率，實現以更高的效率和最短的時間來平衡云中虛擬機之間的工作負載的目標。

1 模因算法

模因算法(Memetic Algorithm，MA)在1989年由Moscato提出[10]，靈感源于達爾文和拉馬克的基因遺傳理論。該算法是將遺傳算法和局部搜索策略相結合的智能算法，具有全局優化能力和局部優化能力。由于MA存在局部搜索機制，即使初始種群的個體與最優解相差很大，也能在單次迭代過程中達到個體局部最優，可行解在剔除適應度很差個體的同時，向最優解不斷逼近，從而顯示其較強的尋優效率及極高的容錯能力。

模因算法可以應用于單目標優化問題，也能夠在多目標優化問題中取得很好的效果。圖1給出了模因算法在單目標、多目標優化問題中的搜索過程。MA在最優解搜索過程中，全局搜索用于在特征空間內定位最優解的潛在區域，局部搜索是在潛在區域內進行精確定位。

(a) 單目標優化問題 (b) 多目標優化問題圖1 模因算法在單/多目標優化問題的搜索過程

MA的大致流程如算法1所示。

算法1模因算法

Begin

t=0；

種群初始化：隨機選擇初始種群P(t)；

評價種群P(t)中的每個個體；

while(中止條件) do

在種群P(t)中的全部/部分個體進行局部搜索；

評價種群P(t)中的每個個體；

復制種群P(t)得到臨時種群P′(t)；

對種群P′(t)使用重組、變異等隨機操作；

合并種群R(t)=P(t)∪P′(t)；

從R(t)中選擇個體產生下一代新種群P(t+1)；

t=t+1；

end while

end

目前，模因算法在單目標優化問題的搜索性能上表現優良，在多目標優化問題(Multi-Objective Optimization Problems，MOOP)中的應用還沒有被廣泛討論。MOOP需要在單目標優化問題的基礎上，解決局部搜索中最優解的排序問題。一般而言，處理這個問題存在兩種方式：采用聚合函數或Pareto排序。由于基于聚合函數的方法在優化效果方面明顯高于基于Pareto排序的方法，因此，大多數學者采用聚合函數求解MOOP問題。Chen等[11]給出了模因算法在局部搜索中采用不同聚合函數時多目標優化問題的解，該模型中的Pareto前沿具有良好收斂性和確定性，從而驗證了模因算法在MOOP問題上也具備很強的適應性。

2 算法設計

云數據中心由一系列連接到互聯網的服務器組成。因此，任務調度器需要安排調度云環境內的任務執行順序。一個優越的調度器使用較少的資源(如能耗、帶寬、內存和時間)來完成用戶任務。針對云資源管理的多目標問題，本文采用改進的模因算法和循環調度方法[12]，將用戶請求任務調度到資源最佳的虛擬機上，在最少的時間內實現負載均衡。

圖2給出了本文算法在云環境中平衡負載以獲得增強任務調度性能的整個過程。首先利用檢測器判斷用戶發送請求數量。如果在很短的時間內接收到大量的請求，會導致突發，并影響負載平衡性能。本文選擇不同的負載平衡算法來提高任務調度效率，當突發檢測器(Burst Detector，BD)發現工作負載狀態為突發時，選擇加權多目標模因優化循環調度算法，將用戶任務分配給云中資源最優的虛擬機；如果該工作負載狀態為正常，則采用閾值多目標模因優化技術調度任務，從而實現以更高的效率和最短的時間來平衡云中虛擬機之間的工作負載的目標。

圖2 本文算法的架構示意圖

2.1 突發檢測器

突發檢測器用于識別云環境服務器的工作負載變化，然后通過預設閾值來確定工作負載的狀態。當用戶請求到達云服務器時，BD將用戶請求的速率與閾值進行比較。如果用戶請求數量在短時間內激增，即任務到達時間t的速率大于閾值，則定義此時工作負載狀態為突發。否則，工作負荷狀態為正常。通過考慮突發檢測器的輸出結果，提出的技術選擇合適的負載平衡方法來調度用戶任務。

2.2 負載平衡算法

本文設計了兩種負載平衡算法，即閾值多目標模因優化算法和加權多目標模因優化循環調度算法，分別應用于正常和突發工作負載條件下的用戶任務調度。

2.2.1閾值多目標模因優化算法

閾值多目標模因優化算法是結合遺傳算法和局部搜索策略的智能算法，根據適應值與基于退火選擇、離散交叉和翻轉變異等進化運算原理來確定有效任務調度的最優虛擬機。閾值多目標模因優化算法的流程如圖3所示。算法首先從云服務器中的虛擬機數量填充種群開始。其次計算每個群體的模因適應值，以確定分配給用戶任務的最佳虛擬機。然后使用退火選擇從群體中挑取好的解決方案，接著將離散交叉應用于通過組合選定的解決方案來創建新的解決方案。交叉后，通過隨機改變解的方式對解進行翻轉突變。最后，采用局部搜索算法，獲得當前迭代中最佳的云負載平衡解決方案。通過設定迭代閾值后，輸出多次迭代的結果，并作為全局最優解。

圖3 閾值多目標模因優化算法流程

云環境下的用戶i(i=1,2,…，n)發送請求到云服務器(Cloud Server，CS)，CS根據用戶請求到達的時間和數據中心中虛擬機利用率的詳細信息來向資源利用率較低的終端用戶提供不同的服務。考慮一個數據中心，具有n個虛擬機VM，通過計算能耗、任務完成時間、帶寬和內存消耗等多個目標來衡量虛擬機VMi的資源利用率。能耗指虛擬機在云環境中為用戶提供所需服務使用的能量，VM的能耗為：

EVM=pow(UR)×t

(1)

式中：EVM表示VM的能量消耗;pow(UR)表示為云用戶提供所需服務使用的能量；t表示服務時間。

虛擬機任務完成時間為：

TVM=ts-te

(2)

式中：ts和te分別表示處理任務的開始和結束時間。

VM的帶寬消耗通過可用帶寬ba和未使用帶寬bu之間的差異計算：

BVM=ba-bu

(3)

虛擬機處理用戶任務所需的存儲空間量可被定義為：

MVM=Ts-us

(4)

式中：MVM表示虛擬機的內存利用率；Ts和us分別表示總空間和未使用空間。

在閾值多目標模因優化算法中，首先利用VMi(i=1,2,…,n)初始化種群，根據下面的多目標問題計算所有VM的模因適應值FVM：

FVM={EVM,TVM,BVM,MVM}

(5)

利用退火選擇(Annealed Selection，AS)挑取具有模因適合度高的種群(即VM)用于下一代，進而找到用于云中任務調度和負載平衡的最佳VM。當種群生成出現變化時，每個種群的模因適合度值和選擇概率也會發生變化。種群選擇的概率在數學上被估計為：

(6)

式中：Fi表示種群的平均適合度；N表示種群數量。

離散交叉(Discrete Crossover，DC)是使用隨機實數來生成一個后代，隨機實數決定從哪個父母那里取出后代的模因。離散交叉過程如圖4所示，DC選擇P和Q作為父母，R是P和Q生成的后代，其模因可從父母中選擇。

圖4 離散交叉過程

翻轉突變(Flip Mutation，FM)如圖5所示，通過修改染色體中的0和1達到翻轉突變的目的。對于突變染色體中的1，父染色體中的后續位被翻轉來構建子染色體。

圖5 翻轉突變過程

在完成突變過程后，應用局部搜索，選擇具有較高適合度值的VM作為執行用戶任務的最佳虛擬機。局部搜索(Local Search，LS)在數學上定義為：

(7)

式中：FVM和FT分別表示VM和閾值的模因適度值。

通過使用式(7)，閾值多目標模因優化算法利用模因適度值的局部尋優，在多個VM之中找到最佳VM用于調度任務。閾值多目標模因優化算法適用于非突發條件下的云中VM工作負載平衡問題。

2.2.2加權多目標模因優化循環調度算法

加權多目標模因優化循環調度算法旨在優化突發工作負載情況下的具有不同處理能力的VM。該算法首先通過計算當前VM的能耗、帶寬、內存、任務完成時間，以及負載情況來確定模因適合度，然后根據適合度為每個VM分配權重，最后該算法根據權重系數安排完成用戶任務VM的順序及響應次數。例如，如果VM1和VM2的權重是3、5，則該算法采用循環調度的方式將3個用戶請求轉發到VM1上處理，將5個用戶請求轉發到VM2上。

在加權多目標模因優化循環調度算法中，同樣利用VMi(i=1,2,…，n)初始化種群，根據多目標問題計算所有VM的模因適應值FVM：

(8)

式中：LVM表示VM的當前負載。

(9)

式中：T表示VM的總容量；Nt表示在當前VM上運行的用戶任務的數量。

VM的權重系數為：

(10)

通過使用式(10)來確定每個VM的權重值。然后加權多目標模因優化循環調度算法通過執行AS、DC、FM和LC在多個虛擬機中選取較高權重的VM，以便處理用戶請求的任務。當云計算中遇到突發性工作負載情況時，通過引入權重值，加權多目標模因優化循環調度算法在每輪中將用戶請求任務分配給已識別的最佳VM，以最小的資源利用率在云中平衡突發性工作負載。

2.3 帕累托前沿

多目標優化問題的解決方案在數學上以非支配點表示，即只有當解決方案在所有標準中具有優越性能時，解決方案才占優勢。如果解決方案不能被搜索空間中可用的任何其他解決方案所支配，則稱該解決方案是帕累托最優。所有帕累托最優解的集合被稱為帕累托集，其在客觀空間中的圖像稱為帕累托前沿[13]。

云中的工作流調度可以被視為多目標優化問題，其目標是找到一組良好的權衡解決方案，使用戶能夠在目標之間選擇所需的權衡。本文算法目的是從初始群體中找出帕累托最優集合以調度用戶請求的任務，即開始于一群隨機生成的候選解決方案，并在更多的生成或迭代次數上向更好的解決方案集(帕累托最優解決方案)發展。圖6給出了本文算法的帕累托前沿。其中：X軸表示種群初始化值(即不同數量的用戶請求任務)；Y軸表示用于平衡云中工作負荷的帕累托最優集(即為調度任務正確選擇的最佳VM的數量)。

圖6 本文算法的帕累托前沿

3 實驗結果與分析

為了評價本文算法的性能，使用Amazon EC2數據集通過CloudSim仿真器以Java語言進行測試實驗，它是一項基于Web的服務，允許用戶在Amazon Web Services(AWS)公共云中運行應用程序。為了對比性能，本文算法在相同條件下與多目標遺傳算法(MGA)[6]和動態節能資源分配(DPRA)[7]等現有的負載平衡方法的測試結果進行比較。

Amazon EC2數據集[14]為發送請求的用戶提供必需的服務。Amazon EC2數據集包含以下屬性：名稱、API名稱、內存、計算單位、核心、存儲、Arch、網絡性能、最大帶寬、最大IP、Linux成本和Windows成本。Amazon EC2數據集允許開發人員使用虛擬機VM，VM為與全球AWS數據中心一起運行的IT項目和云工作負載提供計算能力。測試數據考慮在25～250范圍內的不同數量的用戶請求任務來執行實驗評估。本文仿真實驗的運行環境為Windows10系統下Intel(R) Core(TM) i7-7700HQ處理器。

采用調度效率，調度時間和能耗三個性能評價指標來評估本文方法的性能。調度效率是計算正確調度到最佳VM的用戶請求任務數與用戶請求總數的比率：

(11)

式中：N表示用戶請求總數量；NURs表示正確調度到最佳VM的用戶請求的任務數。

調度時間是指將用戶請求任務調度到最佳VM所需的時間：

ST=N×t(SSUR)

(12)

式中：t(SSUR)表示調度單個用戶請求所用的時間。

能量消耗是估計虛擬機執行用戶請求任務時所需要的能量：

EC=N×E(SSP)

(13)

式中：E(SSP)指執行單個用戶請求任務所需的能量。

圖7-圖9給出了三種方法用于平衡云服務器中的工作負載時的調度效率、調度時間和能耗對比。可以看出，利用本文技術處理云中的突發和非突發工作負載時的調度效率都非常高，調度時間和能耗則是隨著用戶請求數量的增加而遞增。此外，本文算法在調度效率、調度時間和能耗方面的性能明顯優于其他算法。

圖7 不同用戶請求時的調度效率對比

圖8 不同用戶請求時的調度時間對比

圖9 不同用戶請求時的能耗對比

4 結 語

為了在正常和突發工作負載條件下提高云中用戶任務的調度效率，本文提出一種基于模因優化和循環調度的多目標負載均衡算法。通過設計閾值多目標模因優化算法和加權多目標模因優化循環調度算法來應對云計算中正常負載和突發負載時的用戶請求任務的調度工作。實驗結果表明，與其他算法相比，本文方法在調度效率、調度時間和能耗方面具有明顯的優勢。