云環(huán)境下改進SOS的多目標任務調(diào)度算法

陳 藝，江芝蒙，張 渝

(1.四川文理學院 智能制造學院，四川 達州 635000；2.四川文理學院 信息化建設與服務中心， 四川 達州 635000；3.西南大學 計算機與信息科學學院，重慶 400715)

0 引 言

分布式計算是當前信息技術(shù)領域最具影響力的發(fā)展方向，將并行的思想和技術(shù)連接起來，為個人計算機和其它機器提供資源、設備、軟件和數(shù)據(jù)等內(nèi)容的實時共享[1]。但云計算普遍都面臨安全問題，在云設置中存在巨大挑戰(zhàn)，盡管該領域已有部分研究，但任務規(guī)劃仍然有較大改善空間[2]。

任務規(guī)劃算法效率的提高有助于提升系統(tǒng)的整體效率，以便提供更好的服務質(zhì)量。任務規(guī)劃應側(cè)重于在適當?shù)目蚣苤袑τ嬎闳蝿者M行合理的規(guī)劃，使計算資源最大化利用的情況下完成計算任務[3]。多目標任務調(diào)度優(yōu)化旨在構(gòu)建出一個用于指導任務分配的分配表[4]。近年來，在操作系統(tǒng)進程與線程之間、流水作業(yè)之間和工業(yè)生產(chǎn)環(huán)境之間或者是在分布式計算系統(tǒng)中的任務調(diào)度中多目標調(diào)度技術(shù)都是值得進行探究的方向[5,6]。因此，數(shù)值計算對于確定最優(yōu)解來規(guī)劃云計算中各種功能而言至關(guān)重要。

在云計算模型中大規(guī)模問題實例帶來的巨大搜索空間，現(xiàn)有多目標任務調(diào)度方法容易陷入局部最優(yōu)解，無法快速有效地獲得全局最優(yōu)解[7]。因此，提出了一種云環(huán)境下基于改進SOS的多目標任務調(diào)度算法。首先對目前云環(huán)境下多目標任務調(diào)度算法的研究現(xiàn)狀進行了分析，然后提出多目標任務調(diào)度算法整體架構(gòu)，分析了調(diào)度算法框架和目標函數(shù)；再者介紹共生生物搜索算法的各個階段，對于任務調(diào)度給出了相應的改進方案，最后進行實驗分析，論證所提算法的可行性。

1 相關(guān)研究

對于云環(huán)境下多任務流多目標優(yōu)化調(diào)度，一般的啟發(fā)式算法、元啟發(fā)式算法、博弈論調(diào)度以及帕累托優(yōu)化等方法都是被廣泛使用的優(yōu)化算法，并且在相關(guān)研究中已取得了一定的進展[8]。

由于啟發(fā)式方法依賴于一個特定問題域的信息學習的特性，通常被用來制定針對特定類型問題的解決方案[9]。通過對啟發(fā)式算法進行改進后，生成了一種新的算法稱為元啟發(fā)式算法，該算法也將局部搜索算法和隨機算法進行了融合。其中蟻群優(yōu)化、遺傳算法以及粒子群優(yōu)化算法等都屬于典型元啟發(fā)式算法[10]。在任務調(diào)度問題領域，通常包括獨立任務調(diào)度、列表調(diào)度以及基于集群和復制的調(diào)度3種啟發(fā)式算法。文獻[11]提出了一種基于元啟發(fā)式的任務調(diào)度方法，以優(yōu)化異構(gòu)MPSoC的壽命可靠性、性能和功耗。壽命可靠性受幾種具有不同行為的故障機制的影響，這些機制主要取決于溫度及其變化模式。為了提高多處理器系統(tǒng)的生命周期可靠性，需要在優(yōu)化過程中考慮所有潛在故障的影響。實驗結(jié)果表明，所提方法可靠性和功耗平均分別提高30%和3.6%。因此，它可以用于云計算問題的研究和實踐應用，以優(yōu)化工作計劃。文獻[12]提出了一種空間任務調(diào)度和資源優(yōu)化(spatial task scheduling and resource optimization，STSRO)方法，通過經(jīng)濟高效地調(diào)度異構(gòu)應用程序的所有到達任務來滿足任務的延遲約束，從而最小化其提供者的總成本。STSRO很好地利用了分布式綠云數(shù)據(jù)中心(distributed green cloud data centers，DGCDC)中的空間多樣性。在每個時隙中，將DGCDC的成本最小化問題表述為約束優(yōu)化之一，并通過提出的基于模擬退火的蝙蝠算法(SBA)加以解決[13]。實驗結(jié)果表明，與兩種典型的調(diào)度方法相比，STSRO實現(xiàn)了更低的總成本和更高的吞吐量。

文獻[14]提出了一種負載均衡資源集群(LB-RC)負載均衡機制。應用元啟發(fā)式蝙蝠算法來獲得最佳資源聚類及其聚類中心，以實現(xiàn)更快的收斂。采用新的動態(tài)任務分配策略，以在給定的限制內(nèi)實現(xiàn)最小的制造時間和執(zhí)行成本。在各種綜合數(shù)據(jù)集和性能矩陣上的實驗結(jié)果表明，該方法在計算資源利用率和計算成本方面有一定改進，但還有可提升的空間。文獻[15]提出了使用兩個禁忌列表的禁忌元啟發(fā)式算法，將機器分為兩組，以減少生成的鄰居數(shù)量，然后通過保持相同質(zhì)量的解決方案來最大程度地減少計算時間。禁忌搜索與最佳啟發(fā)式方法的比較結(jié)果表明，禁忌搜索調(diào)度方案在計算時間方面具有更好的表現(xiàn)。

對于博弈算法而言，為使分布式計算的整體性能更佳，因此側(cè)重于對系統(tǒng)級的負載均衡以及資源分配方面進行深入的探究[16]。文獻[17]通過運用演化博弈論研究了3種策略的分工演化。根據(jù)回報矩陣中的參數(shù)設置所出現(xiàn)4種特定情況，通過計算提供平衡點的相應穩(wěn)定性。數(shù)值計算結(jié)果直觀描述了策略的演變狀態(tài)。結(jié)果表明，更大的協(xié)同收益有助于系統(tǒng)中的有效分工，從而為多主體系統(tǒng)提供高收益。在實際應用中，由于高時間復雜度，該算法的可行性是還有待進一步驗證。

針對多目標優(yōu)化問題的解決方法，帕累托優(yōu)化方法是被廣泛使用的一種方法，同時它還能對多個目標之間進行合理的權(quán)衡，因此當多個目標間有沖突時該方法的效果更佳[18,19]。滿足帕累托優(yōu)化準則的通常存在多個解，一般將該多個解集合稱為帕累托邊際。

盡管上述調(diào)度方法都是有效的，但部分方法在實際應用中的可行性較差，且任務調(diào)度優(yōu)化結(jié)果還有進一步提升的可能。為了處理多目標問題，調(diào)度計劃所需的時間會大幅度增加。因此，文獻[20]側(cè)重提出一種混沌共生生物搜索(chaos symbiosis search，CSOS)算法，用于任務調(diào)度問題中降低搜索的代價和時間跨度。結(jié)果表明，CSOS在任務規(guī)劃中對成本降低和時間限制方面有著顯著的改進，但對于數(shù)據(jù)量大、任務復雜度高的云環(huán)境下的可行性還有待驗證。

針對上述問題，例如不適用于多目標任務優(yōu)化、搜索時間長、計算復雜、易陷入局部最優(yōu)等，提出了一種云環(huán)境下基于改進SOS的多目標任務調(diào)度算法。所提算法的創(chuàng)新點總結(jié)如下：

(1)為了更合理地實現(xiàn)多目標任務調(diào)度，所提算法設計了相應的調(diào)度框架，其中包括云平臺、數(shù)據(jù)中心、處理單元和任務管理器等，并且提出了與之對應的目標函數(shù)與約束條件。

(2)由于傳統(tǒng)的共生生物搜索(symbiotic organisms search，SOS)算法收斂速度慢，易陷入局部最優(yōu)，所提算法對其進行改進，即利用準反射學習構(gòu)建初始種群，在偏利共生階段中加入擾動項，并且在寄生階段中加入自適應變異率，以提高全局搜索能力。

(3)為了將改進SOS算法應用于多目標任務調(diào)度問題，所提算法將生物坐標轉(zhuǎn)換為任務時間表，通過設定坐標即可實現(xiàn)任務分配，縮短了完成時間且提高了算法各方面的性能。

2 多目標任務調(diào)度算法整體架構(gòu)

2.1 問題描述

多目標任務調(diào)度是通過調(diào)度算法將接收到的任務分配到合適的執(zhí)行虛擬機(virtual machines，VM)列表中，在滿足多目標約束下實現(xiàn)任務完成時間最短。單目標調(diào)度算法存在一個問題，例如，具有高優(yōu)先級的任務擁有優(yōu)先分配的機會，如果高優(yōu)先級任務未分配完成，低優(yōu)先級任務將無法分配，如此便降低了系統(tǒng)處理任務的效率。因此需要一個有效的調(diào)度算法，在各種情況下均能提供最佳效率。在調(diào)度器中充分應用調(diào)度算法，在不破壞服務層契約的情況下提高信息中心的效率。

此外，任務提交和VM會影響完成工作的時間，相應的成本效益也會受到服務供應商規(guī)劃的影響，因此，在此情況下，應有效地對任務進行調(diào)度，以減少執(zhí)行成本和時間。

2.2 調(diào)度算法框架

在整個任務執(zhí)行過程中，如果調(diào)度方案降低了工作效率，并且影響了客戶的活動，那么客戶可以通過任務調(diào)度器進行任務數(shù)據(jù)管理。任務調(diào)度器具有接受和管理任務信息的功能，將滿足預算、成本、存儲限制的任務數(shù)據(jù)上傳至調(diào)度中心，然后由調(diào)度中心根據(jù)成本、時間等約束完成任務分配。所提的多目標任務調(diào)度算法框架如圖1所示。

圖1 云環(huán)境下的任務調(diào)度框架

其中，云平臺由多個數(shù)據(jù)中心組成，這些數(shù)據(jù)中心可以通過使用各地的互聯(lián)網(wǎng)進行訪問，具備計算、存儲等數(shù)據(jù)處理功能，并且調(diào)度中心利用改進的SOS算法來解決云模式中任務調(diào)度的問題。在每個服務器集群中，處理單元(processing elements，PE)通過高帶寬連接網(wǎng)絡[21]，因此需要考慮通信延遲。在任務調(diào)度模塊中，有效地將用戶任務分配給各種可用的PE，以優(yōu)化用電量和時間。

在調(diào)度過程中，用戶任務將分配給數(shù)據(jù)中心C(C1,C2,…,Cm)， 每個數(shù)據(jù)中心都配備了多個處理單元 {PE1,PE2,…,PEm} 來執(zhí)行用戶任務。數(shù)據(jù)中心之間會通過一組信息 〈v,p〉 來相互交流，其中v、p分別表示處理單元的執(zhí)行速率和功耗。用戶的任務流可以建模為一個有向無環(huán)圖(directed acyclic graph，DAG)，記為Gr(N,H)。

節(jié)點集N={T1,…,Tn}， 在任務對 {Ti,Tj}∈H中，父任務稱為Ti， 子任務稱為Tj。Tj使用Ti生成的信息，子任務在其所有父任務完成之前被假定為無法執(zhí)行。在某個任務圖表中，沒有父任務的任務稱為進入任務，而沒有子任務的任務稱為退出任務。該模型只考慮一個輸入輸出任務節(jié)點。因此，在DAG開始和結(jié)束時，添加了兩個假任務Tet和Tex， 運行時間為零。DAG中每N個頂點上都有長度為l的任務。由于所有PE都是有順序的且標準化的，但調(diào)度是隨時發(fā)生的，因此不利于任務的快速的處理。所提算法通過使用改進的SOS為云環(huán)境中提供了任務調(diào)度和資源使用方案。

2.3 多目標調(diào)度的目標函數(shù)

所提模型中將云接口視為在復雜計算任務中使用云資源執(zhí)行的一組用戶功能。根據(jù)任務、資源、成本的定義以及規(guī)劃優(yōu)化模型的表示，云計算的效率會有所不同。在N個任務T的調(diào)度問題中，存在兩個目標函數(shù)和各種限制。目標一為在vmj分配中減少任務i的預期任務往返時間 (RTij)； 目標二為降低vmj中的總預期成本 (ECij)。 利用加權(quán)和策略構(gòu)建兩個目標函數(shù)的加權(quán)集合，以解決向量顯著減少的多目標問題。其中預期往返時間RTij包括傳輸、確認和執(zhí)行操作在內(nèi)的整個過程的完整時間

RTij=(Si/bi)+di+(ki/nj)+di

(1)

式中：Si為任務i的大小，b為帶寬，d為延遲，ki為執(zhí)行任務i所需的指令數(shù)目，nj為每秒執(zhí)行的指令數(shù)

ECij=(li/nj)*RC+(fi/bj)*C/bjRC=R*(C/m)+S*C/st

(2)

式中：RC為資源成本，fi為文件大小，C為執(zhí)行任務i的成本，R為虛擬機的RAM，S為虛擬機的大小，st為存儲量。

對于一個虛擬機來說，其容量小于或等于數(shù)據(jù)中心的數(shù)據(jù)量。因此多目標任務調(diào)度的優(yōu)化目標為

(3)

Subject to

(4)

式中：zij是在vmj中分配任務i的決策變量，cj是分配給vmj的CPU，mj是分配給vmj的內(nèi)存，tc是數(shù)據(jù)中心的總CPU，tm是數(shù)據(jù)中心的總內(nèi)存，ξ1、ξ2為權(quán)重因子。適應度值為

fitness=minP

(5)

3 提出的改進共生生物搜索算法

對于云環(huán)境下多目標任務優(yōu)化調(diào)度，通常使用的算法包括元啟發(fā)式算法、博弈論調(diào)度以及帕累托優(yōu)化等，其中元啟發(fā)算法中的SOS算法潛在的解由一組經(jīng)過連續(xù)迭代進化而來的生物表示，每個生物代表一個優(yōu)化問題的解，并且通過互利、共棲和寄生3個階段進行解決方案優(yōu)化[22]。相比于其它搜索算法，SOS算法的全局搜索能力更強，得到的優(yōu)化結(jié)果更加合理有效。

3.1 共生生物搜索算法

SOS算法的互利階段是兩種不同生物之間的一種關(guān)系，兩種生物都從這種相互作用中受益。在共棲關(guān)系中，一個生物從相互作用中受益，而另一個生物不受傷害。在寄生關(guān)系中，一個生物引發(fā)一種有益于自身的關(guān)系，而另一個生物則受到傷害[23]。

在SOS算法進化中，適者生物被允許進入下一代潛在解，而不適者生物被丟棄。在二維搜索空間中創(chuàng)建生物種群，并根據(jù)SOS的3個階段(互利、共棲和寄生)的模型改變每個生物的位置。假設第i個生物在解決方案搜索空間中的位置為

Xi=(Xi1,Xi2,Xi3,…,Xig)

(6)

式中：Xip∈[Lp,Up]，p∈[1,g]， 搜索空間第p維數(shù)的上下界分別由Lp和Up進行表示。并且每次進行迭代的過程中，生物的位置都會根據(jù)生物的3個階段進行更新。

3.1.1 互利階段

假設Xi是生態(tài)系統(tǒng)的第i個成員。在此階段，從生物群中隨機選擇一個生物個體Xj， 與另一個個體Xi(i≠j) 相互作用，以實現(xiàn)互利。這種相互作用的實質(zhì)是提高生態(tài)系統(tǒng)中Xi和Xj的生存程度。根據(jù)下式得到了Xi和Xj的新候選解，而這些候選解的質(zhì)量受互惠互利因素的影響

(7)

式中：Co為Xi和Xj之間的相互關(guān)系向量，Xbest為具有最佳適應值的生物，β1和β2代表生物Xi和Xj之間的利益因子，U(0,1) 是0和1之間均勻分布的隨機數(shù)向量；i=1,2,3,…,ecosize；j∈{1,2,3,…,ecosize|j≠i}， 其中ecosize是搜索空間中的生物數(shù)。在相互關(guān)系中，一個生物在與一個共同伙伴進行互動時，可能會從中獲得重大或輕微的利益。因此，隨機獲得的β1和β2是1或2，1和2分別表示輕效益和重效益。

通過Xbest分別與Xi和Xj進行交互，如果新的候選解的適應度值優(yōu)于傳統(tǒng)的解，則新的候選解將取代傳統(tǒng)的解。在這種情況下，X′i和X′j在下一代生態(tài)系統(tǒng)中分別取代Xi和Xj。 否則，X′i和X′j將被丟棄，而Xi和Xj將存活到下一代生態(tài)系統(tǒng)中。迭代表示為

(8)

(9)

式中：f(.) 為適應度評估函數(shù)。

3.1.2 共棲階段

在共棲階段，生態(tài)系統(tǒng)的第i個成員隨機選擇一個生物Xj與Xi(i≠j)相互作用。在這種情況下，Xi打算從Xj中受益，Xj既不從交互中獲得收益也不從交互中損失。通過與Xj和Xbest的交互，分別提高了設計向量Xi的適應度質(zhì)量和算法的尋優(yōu)能力。相互作用表示如下

X′i=Xi+U(-1,1)*(Xbest-Xj)

(10)

式中：Xbest為最佳適應值的生物，U(-1,1) 是-1和1之間均勻分布隨機數(shù)的向量，i=1,2,3,…,ecosize，j∈{1,2,3,…,ecosize|j≠i}，ecosize為搜索空間中的生物數(shù)。Xi根據(jù)式(8)進行更新。

3.1.3 寄生階段

在寄生階段，通過克隆第i個生物Xi， 并使用隨機生成的數(shù)字對其進行修改，產(chǎn)生了一種稱為寄生蟲載體的人工寄生蟲。然后，從生態(tài)系統(tǒng)中隨機選取Xj， 計算寄生蟲載體和Xj的適應度值。如果寄生物載體比Xj更適合，那么Xj被寄生物載體所代替，否則Xj將存活到下一代生態(tài)系統(tǒng)中，寄生物載體則被丟棄。Xj根據(jù)下式關(guān)系進行更新

(11)

式中：PV為寄生蟲載體。

該階段通過隨機剔除非活性解，引入活性解，增加了算法的探索能力。從而避免了早熟收斂，提高了收斂速度。

SOS算法的流程如圖2所示。

圖2 SOS算法的流程

3.2 提出的改進方案

傳統(tǒng)SOS算法存在3個明顯的不足：①初始種群隨機構(gòu)建，降低全局搜索能力；②早熟、收斂速度慢；③有可能陷入局部最優(yōu)。為此，所提算法針對這3個方面提出了改進措施：①利用準反射學習來構(gòu)建初始種群；②共棲階段中加入擾動項；③寄生階段中加入自適應變異率。

3.2.1 采用準反射學習機制的種群初始化

隨機初始化生物種群方法是標準SOS算法中的常用方法，但該方法存在一定的局限性，它對算法的全局搜索能力進行了一定的削弱，從而導致該方法的收斂精度大大降低，以致常常會出現(xiàn)早熟的現(xiàn)象。因此，為了更好解決該問題，通過采用準反射學習(quasi-reflection-based lear-ning，QRBL)機制對該算法的求解質(zhì)量和收斂速度進行強化。

(12)

(13)

為了進一步的對SOS算法的尋優(yōu)性能進行提高，給出了一種優(yōu)化的方法，該方法主要是在標準SOS算法的種群初始化階段中將準反射學習機制進行引入。經(jīng)過對它初始解的思考，以及評估它的準反射解，選取更優(yōu)的進行使用，如此一來，采用準反射學習機制對搜索空間的搜索會更加全面和充分，從而使得算法的收斂速度更快，同時又更可能找到近似全局最優(yōu)解的候選解，算法的精度也得到了較大的提高。

3.2.2 共棲階段中引入擾動項

共棲最主要的作用就是能夠在最優(yōu)解的引導下，實現(xiàn)對生物體的快速尋優(yōu)。然而，該措施存在的缺陷就是收斂的精度較低，并且收斂的速度相對較慢。針對此問題本文采取了新的改進措施，通過在共棲階段中，基于原搜索方程引入擾動項，其中加入的擾動項是Xbest和Xi的差向量，并且線性遞減的慣性權(quán)重ω也被引入，具體如下所示

(14)

其中，在[0,1]區(qū)間范圍內(nèi)的慣性權(quán)重由ω進行表示；慣性權(quán)重的最大值記作ωmax； 慣性權(quán)重的最小值記作ωmin； 算法的最大迭代次數(shù)由tmax來表示；t表示的是當前的迭代次數(shù)。

在此階段中，為維護個體間存在的差異，采取對差分擾動項進行增加的方法；此外，由于在算法迭代的初始階段中ω的值相對較大，算法的全局搜索能力也相對較強，為了盡可能避免陷入局部最優(yōu)，所以還將線性遞減的慣性權(quán)重ω進行了引入。在算法不斷迭代后，ω的值也會不斷減小，并且在較優(yōu)解的鄰域內(nèi)，算法中個體的搜索能力也會得到加強，收斂的精度也會隨之提高，并且收斂的速度也會變快。

3.2.3 寄生階段中加入自適應變異

在進行寄生操作時，通常情況下，傳統(tǒng)SOS算法選取的變異率是固定值，其中存在一個較大的缺陷就是這使得算法陷入局部最優(yōu)的概率較大，以致收斂的精度也會大大降低。針對該問題本文所提的算法做出了相應的改進，基于傳統(tǒng)SOS算法，將其中的固定變異率由適應值進行動態(tài)調(diào)整的變異率來替代，詳細的公式過程如下

(15)

式中：pv為動態(tài)變異率;生物體的平均適應值用fave(Xi) 進行表示，其中，選取f(Xi) 作為生物體適應值來進行寄生操作；種群中的最大適應值記作fmax(Xi)；d1、d2表示的是隨機數(shù)。

鑒于適應值動態(tài)調(diào)整的變異率，采取寄生的操作方式，這可以使具有較高適應值的生物體變異率盡可能的變低，具有較低適應值的生物體變異率盡可能的變高，讓優(yōu)質(zhì)生物體的數(shù)量得到增加，從而進一步實現(xiàn)對算法收斂速度以及精度的提高[24]。

3.3 任務調(diào)度問題中的生物編碼

在該算法中，生物的種群結(jié)構(gòu)被表示為一組實例類型，每個生物是種群中的一個個體，代表了搜索空間的一部分。生物坐標系中的每個坐標(每個字段)都是云環(huán)境中的實例類型。在d維解決方案搜索空間中，n個生物的搜索種群表示為X={X1,X2,X3,…,Xn}。 第i個生物的位置表示為Xi={xi1,xi2,xi3,…,xid}。 為了定義問題的解決方案，每個生物代表一個完整的任務時間表。實數(shù)值表示要選擇的備用實際類型[25]。該確定生物在解決方案搜索空間中位置的坐標系取決于生物的維數(shù)。舉個例子說明，生物的7個任務時間表如圖3所示，其中生物是一個7維的生物，它在搜索空間上的位置由坐標1到7定義。

圖3 生物編碼及其與VM映射的對應任務

生物的移動范圍由執(zhí)行任務的可用實例數(shù)決定，因此，生物搜索空間的坐標值可以是一個或多個可用實例。由于所選VM的適應度值是離散的，因此生物位置中每個坐標的最近整數(shù)值對應的就是執(zhí)行該坐標定義任務的實例類型。

由圖3中的示例可知，資源池中有3個實例，因此每個坐標值的范圍為0～3。坐標1的值0.6表示任務1已分配給實例類型2。坐標2的值2.7表示任務2已分配給實例類型3。其余的坐標遵循相同的邏輯。其中將生物坐標轉(zhuǎn)換為任務時間表的算式如下

(16)

4 仿真及分析

實驗基于CloudSim仿真平臺進行，測試中使用一個數(shù)據(jù)中心、5個VM和300個cloudlet執(zhí)行。云環(huán)境的模擬參數(shù)見表1。

改進SOS算法中，種群規(guī)模是100，個體維數(shù)是5，最小權(quán)重ωmin和最大權(quán)重ωmax分別是0和1，最大迭代步數(shù)是100。

表1 模擬參數(shù)

4.1 性能指標

所提算法使用相應的指標評估能量、時間、成本、資源利用率和服務水平協(xié)議(service level agreement，SLA)違反情況。

(1)能耗：所有響應或服務的能量消耗

(17)

(2)時間：任務在傳輸、確認和執(zhí)行操作中整個過程的時間，計算如式(1)。

(3)成本：虛擬機上任務執(zhí)行所需的總成本，包括資源成本和執(zhí)行成本，計算如式(2)。

(4)資源利用：資源應得到均衡利用，即分配給vmj的CPU不能超過數(shù)據(jù)中心的總CPU，以及分配給vmj的內(nèi)存不能超過數(shù)據(jù)中心的總內(nèi)存。數(shù)學表達如下

(18)

(5)SLA違反情況：當云提供商的處理器數(shù)量小于所需的任務或Cloudlet的數(shù)量時，就會發(fā)生SLA沖突，因此處理的任務數(shù)不能超過上限

SLA=tc

(19)

4.2 調(diào)度性能評估

4.2.1 不同迭代次數(shù)下的收斂曲線

為了論證所提算法的收斂特性，將其與文獻[11]、文獻[14]、文獻[17]進行對比分析，其中不同算法的總執(zhí)行時間和成本隨著迭代次數(shù)的收斂性如圖4所示。

圖4 不同迭代次數(shù)下的收斂曲線

由圖可知，迭代次數(shù)在30～40時，算法基本上都完成了任務的執(zhí)行。從圖4(a)可以看出，所提算法完工時間約為2.9 ms，優(yōu)于文獻[11]、文獻[14]、文獻[17]所提方法所需要的4.9 ms、4.5 ms和3.5 ms。從圖4(b)可以看出，在成本開銷方面，所提方法相較于文獻[11]方法大約節(jié)省50%的成本開銷；相較于較為節(jié)省成本的文獻[17]，也能節(jié)省約15%的成本開銷。在最開始時，算法分配任務都是根據(jù)站點處理速度以及性價比來進行相應的分配，因此成本低且耗時長。在之后時間和成本的收斂速度開始變快，這主要是由于每個任務包都會根據(jù)自身利益去爭奪對自己最有效的資源。在競爭完成后，算法機制會讓參與者將工作負載到相對較弱的站點中。該機制的優(yōu)勢是保證了在參與者個體行為自私的情況下能產(chǎn)生一個全局最優(yōu)解。所有的任務包最終都能夠達到平衡狀態(tài)，即無法繼續(xù)進行優(yōu)化改善。相比與其它算法，所提算法的完成收斂的時間最短，且成本開銷最小。

4.2.2 在不同任務量下本文算法的性能指標

實驗中，所有的性能指標都是針對指定數(shù)量的任務進行評估的，范圍從50到200，針對不同的種群規(guī)模Pop(如Pop5、Pop15和Pop25，分別代表種群數(shù)量為5、15、25)評估性能度量。能量隨著任務增加的變化如圖5所示。

圖5 能量與任務的對比分析

從圖5中可以看出，隨著任務數(shù)量的增加，能量也在不斷增加。當任務為200時，種群規(guī)模25的能量達到最大值。當任務容量為50時，能量最小。同樣，隨著任務數(shù)量的增加，其完成時間與成本也在不斷的增加，因此不再贅述。

對于不同的任務量，其資源利用情況如圖6所示。

圖6 資源利用與任務分析

對于不同的種群標準，任務數(shù)量的增加對資源的利用沒有太大的影響，只在總體數(shù)量較低時，不同種群標準的資源利用率都較低，但仍有90%左右，總體較為穩(wěn)定。因此，綜合看來資源利用率相對較高，平均達到92%。從此外，任務量對SLA沖突的影響如圖7所示。

圖7 SLA沖突與任務分析

從圖7中可以看出，與種群數(shù)量15和25相比，種群數(shù)量5執(zhí)行的50個任務顯示出70%的高違反率。當對種群數(shù)量5和15執(zhí)行100個任務時，與種群數(shù)量25相比，違反率為12%。當對種群數(shù)量5和25執(zhí)行200個任務時，與種群數(shù)量15相比，違反率為8%。當種群數(shù)量5執(zhí)行150個任務時，種群數(shù)量15和25的違規(guī)率分別為4%、3%和5%。在150個任務中，執(zhí)行的總違反率最少，性能最佳。

4.3 調(diào)度性能對比及分析

為了論證所提算法的性能，將其與文獻[11]、文獻[14]、文獻[17]中算法在時間、成本、資源利用等方面進行對比分析。不同任務數(shù)的時間和成本對比結(jié)果如圖8所示。

圖8 不同算法的時間和成本對比

從圖8中可以看出，相比于其它算法，不同任務數(shù)量下，所提算法完成任務調(diào)度的耗時最少。由于所提的目標函數(shù)中的帶寬參數(shù)，考慮了調(diào)度任務的傳輸時間，其相比于其它云環(huán)境下的任務調(diào)度算法，時間消耗減少了32%。并且所提算法的成本也得到了相應的減少，降低了29%，具有較高的效率。文獻[11]通過元啟發(fā)式的任務調(diào)度方法優(yōu)化異構(gòu)MPSoC的性能和功耗，但其受故障機制的影響較大，因此執(zhí)行時間和成本較大。文獻[14]的LB-RC負載均衡機制，應用元啟發(fā)式蝙蝠算法以獲得最佳資源聚類及其聚類中心，能夠在給定的限制內(nèi)實現(xiàn)較小的執(zhí)行時間和成本。文獻[17]通過演化博弈論尋得最優(yōu)的調(diào)度方案，較大的協(xié)同收益有助于系統(tǒng)中的有效分工，但時間復雜度較高，因此耗費的時間和成本較大。

不同算法在資源利用方面的比較如圖9所示。

圖9 不同算法的資源利用對比

從圖9中可以看出，所提算法相比于其它云環(huán)境下的任務調(diào)度算法，資源利用率降低了68%。文獻[11]受故障機制影響較大，文獻[17]的時間復雜度較高，因此兩者的資源利用率較高。而文獻[14]的負載均衡機制能夠減少網(wǎng)絡資源的使用。

綜上所述，在最小的時間、成本、資源使用下，所提算法可以在虛擬機上實現(xiàn)最優(yōu)的任務分配。

5 結(jié)束語

現(xiàn)如今，云環(huán)境的應用越來越廣泛，人們的需求也在日益增加，隨之而來亟需解決問題就是任務要如何進行調(diào)度才更有效率以及如何對應用進行動態(tài)的引導。為了滿足用戶的QoS，提出了一種云環(huán)境下基于改進SOS的多目標任務調(diào)度算法。基于構(gòu)建的多目標任務調(diào)度模型，設計相應的目標函數(shù)與約束條件，并利用改進的SOS算法進行模型求解，以得到最優(yōu)的生物坐標，并將其轉(zhuǎn)換為任務時間表，通過設定坐標即可完成任務分配。在CloudSim仿真平臺上對所提調(diào)度算法進行實驗分析，結(jié)果表明，改進的SOS算法能夠?qū)崿F(xiàn)快速收斂，且相比于其它算法，所提算法完成任務調(diào)度所需的時間短、耗能低、資源利用率高，同時SLA違反情況最少。由此可證明，所提算法能夠?qū)崿F(xiàn)多目標任務的最優(yōu)調(diào)度，對實際云環(huán)境的任務分配具有重要借鑒意義。

所提算法在完成調(diào)度的過程中并未考慮用戶數(shù)據(jù)安全等問題，下一步，我們將側(cè)重于研究該采取何種方式來執(zhí)行調(diào)度才能最大程度保護相關(guān)用戶的隱私以及敏感度的問題。