陳孝如，曾碧卿

(1.廣州軟件學(xué)院 軟件工程系，廣東 廣州 510990；2.華南師范大學(xué) 軟件學(xué)院，廣東 佛山 528225)

0 引 言

近年來(lái)，為了滿足大規(guī)模應(yīng)用程序的計(jì)算需求，云計(jì)算憑借其計(jì)算資源的高效性和靈活性得到了大規(guī)模部署[1]。云計(jì)算提供服務(wù)的主要形式有3種，分別為：基礎(chǔ)設(shè)施即服務(wù)(infrastructure as a service，IaaS)、平臺(tái)即服務(wù)(platform as a service，PaaS)以及軟件即服務(wù)(software as a service，SaaS)[2,3]。其中，IaaS可實(shí)現(xiàn)大規(guī)模應(yīng)用程序部署，能夠提供靈活和可擴(kuò)展計(jì)算資源的訪問(wèn)[4]。然而，在IaaS云上高效且有效的執(zhí)行大規(guī)模任務(wù)調(diào)度，仍然是一個(gè)亟待解決的問(wèn)題[5]。

近年來(lái)，各種啟發(fā)式算法被用于求解任務(wù)調(diào)度問(wèn)題，取得了一定的成效[6]。然而，面對(duì)大規(guī)模計(jì)算任務(wù)時(shí)，元啟發(fā)式算法的計(jì)算時(shí)間較長(zhǎng)，由于局部搜索與全局搜索過(guò)早收斂和失衡的影響，可能會(huì)使算法陷入局部最優(yōu)解。不同于傳統(tǒng)的元啟發(fā)式算法，松鼠搜索算法(squirrel search algorithm，SSA)[7]具有魯棒性和更快的收斂速度，在處理多目標(biāo)約束優(yōu)化問(wèn)題的同時(shí)，可對(duì)復(fù)雜的多維搜索空間進(jìn)行有效地優(yōu)化。由于無(wú)需特定的算法參數(shù)，SSA已被用于解決任務(wù)調(diào)度、無(wú)線通信以及經(jīng)濟(jì)調(diào)度等優(yōu)化問(wèn)題[8]。

基于上述分析，針對(duì)云計(jì)算中大規(guī)模應(yīng)用程序的任務(wù)調(diào)度問(wèn)題，提出一種改進(jìn)SSA的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法，以對(duì)搜索空間進(jìn)行有效的優(yōu)化，合理調(diào)度多目標(biāo)任務(wù)。所提方法的創(chuàng)新點(diǎn)總結(jié)如下：

(1)為了實(shí)現(xiàn)任務(wù)的高效調(diào)度，構(gòu)建IaaS云模型，基于該模型設(shè)計(jì)多目標(biāo)任務(wù)調(diào)度算法框架，并將成本和執(zhí)行時(shí)間的最小化作為目標(biāo)函數(shù)，從而有效地將用戶任務(wù)分配給各種可用的處理單元；

(2)由于傳統(tǒng)SSA存在容易陷入局部最優(yōu)的問(wèn)題，所提方法將入侵雜草優(yōu)化算法(invasive weed optimization，IWO)的空間變異和擴(kuò)散機(jī)制應(yīng)用于SSA，并利用改進(jìn)型SSA求解多目標(biāo)優(yōu)化問(wèn)題，從而在最短時(shí)間內(nèi)尋得最優(yōu)調(diào)度方案。

1 相關(guān)研究

任務(wù)調(diào)度優(yōu)化分為單目標(biāo)優(yōu)化和多目標(biāo)優(yōu)化。單目標(biāo)優(yōu)化方法只對(duì)完工時(shí)間或成本進(jìn)行優(yōu)化。然而，由于云計(jì)算的快速發(fā)展，需要考慮到多個(gè)服務(wù)質(zhì)量(quality of service，QoS)目標(biāo)，使得任務(wù)調(diào)度成為一個(gè)多目標(biāo)優(yōu)化問(wèn)題[9]。由于用戶和提供者各自具有不同的優(yōu)化目標(biāo)，故多目標(biāo)任務(wù)優(yōu)化問(wèn)題較為復(fù)雜[10]。就目前的研究現(xiàn)狀而言，針對(duì)云環(huán)境下的多目標(biāo)任務(wù)調(diào)度優(yōu)化問(wèn)題的求解，主要采用的方法有啟發(fā)式算法、分層方法以及帕累托優(yōu)化等[11,12]。

文獻(xiàn)[13]提出一種改進(jìn)的非支配排序遺傳算法得出Pareto最優(yōu)解集，并利用模糊優(yōu)選法對(duì)該解集進(jìn)行選優(yōu)，確定了產(chǎn)品開(kāi)發(fā)任務(wù)調(diào)度的最優(yōu)執(zhí)行方案。通過(guò)兩個(gè)經(jīng)典多目標(biāo)測(cè)試函數(shù)的求解及對(duì)比分析結(jié)果表明了改進(jìn)算法的有效性和優(yōu)越性。但在優(yōu)化應(yīng)用程序的執(zhí)行時(shí)間、可靠性和負(fù)載平衡時(shí)未考慮計(jì)算資源的異構(gòu)性。文獻(xiàn)[14]提出了一種蟻群算法的測(cè)試任務(wù)并行任務(wù)調(diào)度優(yōu)化方法，對(duì)測(cè)試問(wèn)題進(jìn)行描述并與蟻群算法結(jié)合，設(shè)計(jì)了啟發(fā)函數(shù)、狀態(tài)轉(zhuǎn)移規(guī)則；通過(guò)依據(jù)算法流程來(lái)得到測(cè)試速度最快的任務(wù)調(diào)度序列；在任務(wù)序列多解的問(wèn)題上，主要是通過(guò)提出資源均衡度的評(píng)價(jià)標(biāo)準(zhǔn)，得到最優(yōu)的資源任務(wù)調(diào)度序列。然而，不同目標(biāo)的結(jié)果取決于所分配權(quán)重的值，這些權(quán)重值也許不能充分代表用戶的決策。此外，該方法只產(chǎn)生不適合多目標(biāo)決策問(wèn)題的解決方案。

分層方法按順序優(yōu)化任務(wù)調(diào)度目標(biāo)，根據(jù)目標(biāo)的重要性確定任務(wù)調(diào)度目標(biāo)的優(yōu)化次序，并根據(jù)目標(biāo)的排序交替求解[15]。例如，文獻(xiàn)[16]提出一種基于蟻群算法的分層調(diào)度算法，將調(diào)度過(guò)程分為預(yù)分配、粗略調(diào)度和精細(xì)調(diào)度3個(gè)步驟，對(duì)目標(biāo)函數(shù)進(jìn)行順序優(yōu)化。測(cè)試結(jié)果表明，使用這種新機(jī)制可以有效地減少計(jì)算時(shí)間。文獻(xiàn)[17]提出一種基于離散粒子群算法的靜態(tài)任務(wù)調(diào)度方法；求解過(guò)程中假定任務(wù)是非優(yōu)先并且獨(dú)立的，使用負(fù)載平衡技術(shù)提高了方法的性能。然而，該方法時(shí)效性較差，優(yōu)化過(guò)程需要多次迭代，尤其是當(dāng)有多個(gè)目標(biāo)約束時(shí)[18]。

為了克服聚合和分層方法的缺點(diǎn)，提出了基于帕累托的優(yōu)化方法，以解決多目標(biāo)任務(wù)調(diào)度問(wèn)題。帕累托方法為優(yōu)化問(wèn)題的目標(biāo)找到了幾個(gè)最優(yōu)的折衷方案。使用帕累托支配的概念來(lái)為個(gè)體分配適應(yīng)度。帕累托方法不需要將多個(gè)目標(biāo)轉(zhuǎn)化為單目標(biāo)公式，并在一個(gè)單一的過(guò)程中產(chǎn)生多個(gè)權(quán)衡解決方案。文獻(xiàn)[19]提出了工作流任務(wù)調(diào)度問(wèn)題的多目標(biāo)遺傳算法，在考慮任務(wù)優(yōu)先級(jí)的同時(shí)還兼顧了云計(jì)算中的任務(wù)能耗。使任務(wù)的完工時(shí)間和成本達(dá)到最小化。采用遺傳算法解決了完工時(shí)間、成本和能耗之間的帕累托最優(yōu)權(quán)衡問(wèn)題，仿真結(jié)果表明了該方法的有效性。同樣，文獻(xiàn)[20]基于包括車(chē)輛云、路邊小云和集中式云三層體系結(jié)構(gòu)，提出一種混合自適應(yīng)粒子群優(yōu)化(hybrid adaptive particle swarm optimization，HAPSO)算法資源分配和任務(wù)優(yōu)化調(diào)度算法，可以有效地滿足來(lái)自道路用戶的大量任務(wù)請(qǐng)求，同時(shí)保持改進(jìn)的服務(wù)質(zhì)量。結(jié)果表明，對(duì)于多目標(biāo)優(yōu)化調(diào)度問(wèn)題，HAPSO的收斂速度比標(biāo)準(zhǔn)粒子群優(yōu)化和自適應(yīng)粒子群優(yōu)化更具優(yōu)勢(shì)。然而，在帕累托任務(wù)調(diào)度方法中，由于帕累托優(yōu)勢(shì)是一個(gè)偏序，很難為下一代選擇合適的個(gè)體。因此，如果選擇算子不能保持足夠的多樣性，所得到的解可能無(wú)法覆蓋整個(gè)帕累托前沿，則在開(kāi)發(fā)多目標(biāo)任務(wù)調(diào)度有效分配個(gè)體適應(yīng)度的同時(shí)保持對(duì)整個(gè)優(yōu)化方案的有效估計(jì)，仍是一個(gè)具有挑戰(zhàn)性的研究課題。

Jain M提出了SSA[21]，該算法模仿了飛松鼠的動(dòng)態(tài)跳躍策略和特征，對(duì)于優(yōu)化問(wèn)題的最優(yōu)搜索具有易于實(shí)現(xiàn)的優(yōu)點(diǎn)，并且不易陷入局部最優(yōu)。其數(shù)學(xué)模型主要包括食物和捕食者的位置，整個(gè)優(yōu)化過(guò)程包括夏季和冬季兩個(gè)階段。然而，與其它智能進(jìn)化算法相似，SSA也存在收斂精度低、收斂速度慢等缺點(diǎn)。根據(jù)SSA，全局搜索能力的單冬搜索方法不夠，使得算法容易陷入局部最優(yōu)。此外，隨機(jī)夏季搜索方法降低了收斂速度，收斂精度也降低[22]。為了提高算法的收斂精度和收斂速度，提出了一種改進(jìn)的松鼠搜索算法(improved squirrel search algorithm，ISSA)，包括跳躍搜索法和漸進(jìn)搜索法。當(dāng)松鼠與捕食者相遇時(shí)，將“逃逸”和“死亡”操作引入跳躍搜索方法，將“突變”操作引入漸進(jìn)搜索方法。在優(yōu)化過(guò)程中，ISSA還通過(guò)線性回歸選擇策略選擇合適的搜索方法。

2 系統(tǒng)模型與問(wèn)題建模

2.1 IaaS云模型

(1)

2.2 多目標(biāo)調(diào)度的目標(biāo)函數(shù)

(2)

只考慮一個(gè)實(shí)例序列和一個(gè)定價(jià)方案，其中實(shí)例序列類(lèi)型是計(jì)算密集型的。則任務(wù)調(diào)度 (ET,C) 的目標(biāo)函數(shù)為

minf=(ET,cost)e

(3)

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

在整個(gè)調(diào)度過(guò)程中，如果計(jì)算資源(包括CPU和存儲(chǔ)系統(tǒng))無(wú)法滿足用戶的任務(wù)需求，則可以通過(guò)任務(wù)管理器進(jìn)行采集和處理任務(wù)數(shù)據(jù)。任務(wù)管理器具有接受和管理任務(wù)的功能，需要向調(diào)度器提供數(shù)據(jù)。任務(wù)管理器將通過(guò)成本、存儲(chǔ)和時(shí)間限制進(jìn)行工作分配，并且通過(guò)全局資源管理系統(tǒng)對(duì)分配的資源進(jìn)行了標(biāo)記。整個(gè)調(diào)度算法是在云計(jì)算平臺(tái)中進(jìn)行，兼容不同的物理服務(wù)器[23]。同時(shí)，可以訪問(wèn)本地服務(wù)器資源管理(local server resource management，LRM)，每個(gè)LRM都支持許多虛擬機(jī)。IaaS云環(huán)境下的任務(wù)調(diào)度算法結(jié)構(gòu)如圖1所示。

圖1 IaaS云環(huán)境下的任務(wù)調(diào)度

云計(jì)算系統(tǒng)由多個(gè)數(shù)據(jù)中心組成，這些數(shù)據(jù)中心可以通過(guò)使用來(lái)自世界各地的互聯(lián)網(wǎng)進(jìn)行訪問(wèn)，每個(gè)數(shù)據(jù)中心都有許多計(jì)算、存儲(chǔ)以及其它的資源。在每個(gè)服務(wù)器集群中，處理單元通過(guò)高帶寬連接網(wǎng)絡(luò)。在所提調(diào)度模型中，有效地將用戶任務(wù)分配給各種可用的處理單元，以優(yōu)化用戶成本和時(shí)間。

3 改進(jìn)型松鼠搜索算法

SSA是模擬飛行松鼠為躲避捕食者、尋找捕食的最佳地點(diǎn)以及以較小的代價(jià)進(jìn)行捕食的滑翔行為。飛行松鼠的覓食策略靈活多變，這可以幫助飛行松鼠以最佳的方式應(yīng)對(duì)食物資源。相比于其它搜索優(yōu)化算法，SSA對(duì)搜索空間要求較少，且搜索效率較高，但在優(yōu)化過(guò)程中也存在易陷入局部最優(yōu)解，收斂速度較慢的問(wèn)題。

3.1 松鼠搜索算法

松鼠是一種多樣的樹(shù)棲和夜間活動(dòng)的嚙齒動(dòng)物，其類(lèi)似降落傘的薄膜特別適合滑翔。其滑翔搜索能力可以幫助其躲避捕食者、尋找捕食的最佳地點(diǎn)和以較小的代價(jià)進(jìn)行捕食。松鼠可以通過(guò)展示動(dòng)態(tài)覓食行為來(lái)優(yōu)化食物資源的利用[24]。

在溫暖的秋天，由于橡樹(shù)籽數(shù)量多，且能夠滿足松鼠在秋天的營(yíng)養(yǎng)需要，當(dāng)它們發(fā)現(xiàn)橡樹(shù)籽后，會(huì)立即食用。在滿足了每天的能量需求后，開(kāi)始尋找冬天的最佳食物來(lái)源；而在冬季，森林中樹(shù)葉的脫落增加了被捕食的風(fēng)險(xiǎn)，因此它們變得不活躍，但不冬眠。由于較低的溫度會(huì)導(dǎo)致更高的營(yíng)養(yǎng)需求，儲(chǔ)存山核桃仁將有助于它們?cè)跇O端天氣條件下維持能量需求，從而提高存活概率。因此，根據(jù)營(yíng)養(yǎng)需要，有選擇地吃一些堅(jiān)果，而將其它堅(jiān)果儲(chǔ)存起來(lái)，這使得兩種堅(jiān)果得到了充分利用。到冬季末，松鼠又活躍起來(lái)了開(kāi)始覓食。如此循環(huán)往復(fù)，一直延續(xù)到松鼠生命的結(jié)束。在這個(gè)過(guò)程中，它們通過(guò)改變位置來(lái)探索不同的森林區(qū)域。SSA的尋優(yōu)流程如圖2所示。

圖2 SSA的流程

為了簡(jiǎn)化數(shù)學(xué)模型，需要考慮以下假設(shè)[25]：

(1)森林里有n只會(huì)飛的松鼠，假設(shè)樹(shù)上只有一只會(huì)飛的松鼠；

(2)每只松鼠都獨(dú)立地尋找食物，并通過(guò)表現(xiàn)出動(dòng)態(tài)的覓食行為來(lái)優(yōu)化現(xiàn)有食物資源的利用；

(3)在森林中，只有3種樹(shù)可供選擇，如普通樹(shù)、橡樹(shù)(橡樹(shù)籽的來(lái)源)和山核桃樹(shù)(山核桃仁的來(lái)源)；

(4)假設(shè)森林區(qū)域由k橡樹(shù)和一棵山核桃樹(shù)組成。

在SSA中，對(duì)于d維優(yōu)化問(wèn)題，每個(gè)松鼠的位置可以用一個(gè)d維向量來(lái)表示

Xi=[xi1,xi2,…,xij,…,xid],i=1,2,…,nxij=xmin+δ(0,1)·(xmax-xmin),j=1,2,…,d

(4)

式中：xmax和xmin分別是飛行松鼠位置的上下限，δ(0,1) 是[0,1]范圍內(nèi)的均勻分布隨機(jī)數(shù)。

根據(jù)用戶定義的適應(yīng)度函數(shù)，計(jì)算出每只飛鼠所在地的適應(yīng)度值f(Xi)， 對(duì)應(yīng)的值描述了可供搜索的食物源的質(zhì)量，即最佳食物源(山核桃樹(shù))、正常食物源(橡樹(shù))和無(wú)食物源(普通樹(shù))。

3.2 引入空間變異與擴(kuò)散機(jī)制

SSA算法在優(yōu)化過(guò)程中不可避免地陷入局部最優(yōu)解，收斂速度較慢。因此，受IWO的啟發(fā)，將空間變異和擴(kuò)散行為結(jié)合到SSA中，提出了一種ISSA。

第i只飛行的松鼠在一定范圍內(nèi)選擇樹(shù)Ni上降落，以確保在該范圍內(nèi)找到最佳食物來(lái)源，這個(gè)過(guò)程被稱(chēng)為空間變異。Ni的個(gè)數(shù)由IWO算法中的生長(zhǎng)和再生思想決定

(5)

式中：dmax和dmin分別是空間變化的最大和最小數(shù)量。f(·) 是適應(yīng)度函數(shù)，fmax、fmin分別是f(·) 的最大值和最小值。

然后，由正態(tài)分布的空間擴(kuò)散產(chǎn)生Ni隨機(jī)位置，平均值為第i只飛行松鼠的當(dāng)前位置，標(biāo)準(zhǔn)差為σt， 其中σt的值根據(jù)迭代次數(shù)確定為

(6)

式中：σinitial為初始標(biāo)準(zhǔn)差，σfinal為最終標(biāo)準(zhǔn)差，t為當(dāng)前迭代次數(shù)，tmax為最大迭代次數(shù)，n為非線性調(diào)和指數(shù)，常取3。

由上可知，空間擴(kuò)散產(chǎn)生的新Ni位置可以表示為

(7)

式中：N(0,1) 是標(biāo)準(zhǔn)正態(tài)分布隨機(jī)數(shù)。

對(duì)隨機(jī)生成的Ni適應(yīng)度函數(shù)值進(jìn)行排序，選擇適應(yīng)度函數(shù)值最小的位置作為第i只飛行松鼠的當(dāng)前新位置。式(7)描述了ISSA的基本特征，即早期強(qiáng)調(diào)全局搜索，后期強(qiáng)調(diào)局部搜索。

ISSA的偽代碼如算法1所示。

算法1：ISSA的偽代碼。

Begin

定義輸入?yún)?shù)：εg是隨機(jī)滑行距離；R是[0,1]范圍內(nèi)的隨機(jī)數(shù)；Gc是滑動(dòng)常數(shù)，常取1.9；Pd為捕食者存在概率。

(1) 生成n只飛行松鼠的隨機(jī)位置：

Xi=[xi1,xi2,…,xid],i=1,2,…,n

(2) 評(píng)估每只飛行松鼠的位置是否適合。

(3) 通過(guò)空間變化和擴(kuò)散進(jìn)行重新定位：

(4) 根據(jù)它們的適應(yīng)值， 按升序排列飛行松鼠的位置。

(5) 上報(bào)山核桃樹(shù)、 橡樹(shù)和普通樹(shù)上的飛行松鼠。

(6) 隨機(jī)選擇一些在正常樹(shù)上的飛行松鼠向山核桃樹(shù)移動(dòng)， 其余的向橡樹(shù)移動(dòng)。

(7) While 不滿足停止條件

(8) Fort=1 ton1(在橡樹(shù)上向山核桃樹(shù)飛去的松鼠總數(shù))

(9) ifR1≥Pd

(12) end

(13) end

(14) Fort=1 ton2(在正常樹(shù)上向橡樹(shù)移動(dòng)的飛行松鼠的總數(shù))

(15) ifR2≥Pd

(18) end

(19) end

(20) Fort=1 ton3(在普通樹(shù)上向山核桃樹(shù)移動(dòng)的飛行松鼠總數(shù))

(21) ifR3≥Pd

(24) end

(25) end

(27) 使用更新季節(jié)常數(shù)Smin的最小值:

(28) 通過(guò)空間變化和擴(kuò)散進(jìn)行重新定位：

(29) 松鼠在山核桃樹(shù)上的位置是最終的最優(yōu)解。

End

4 仿真及分析

4.1 仿真設(shè)置

CloudSim仿真工具包支持模擬云計(jì)算場(chǎng)景，支持大規(guī)模計(jì)算環(huán)境的建模和仿真，可為數(shù)據(jù)中心、物理主機(jī)、云服務(wù)代理和調(diào)度系統(tǒng)提供建模支持，因此，在IaaS云環(huán)境下使用CloudSim 3.0.3仿真工具包實(shí)現(xiàn)所提方法的調(diào)度方案。在實(shí)驗(yàn)中，一個(gè)IaaS云提供商擁有一個(gè)數(shù)據(jù)中心、兩個(gè)主機(jī)和20個(gè)不同配置的虛擬機(jī)。數(shù)據(jù)中心和主機(jī)的配置見(jiàn)表1。虛擬機(jī)(virtual machine，VM)配置基于當(dāng)前amazonec2產(chǎn)品，見(jiàn)表2，虛擬機(jī)的處理能力(即工作負(fù)載參數(shù))見(jiàn)表3。

此外，ISSA算法的參數(shù)見(jiàn)表4。

4.2 性能指標(biāo)

將完工時(shí)間、成本(財(cái)務(wù)成本)、超體積作為性能指標(biāo)。ET是虛擬機(jī)最晚的完成時(shí)間，最小ET意味著用戶在執(zhí)行任務(wù)時(shí)要付出適度的成本，因?yàn)樵品?wù)中用戶通常是按每小時(shí)的虛擬機(jī)使用量收費(fèi)的。成本是從IaaS云提供商租賃VMs獲得的。

表1 IssA云環(huán)境的參數(shù)設(shè)置

表2 虛擬機(jī)的配置與類(lèi)型

表3 工作負(fù)載參數(shù)

表4 ISSA算法的參數(shù)設(shè)置

ET也稱(chēng)為總執(zhí)行時(shí)間，是執(zhí)行任務(wù)集合時(shí)使用的所有VMs最新完成時(shí)間，表示如下

(8)

成本是VMs成本與ET的乘積之和，四舍五入得最接近的整數(shù)表示為

(9)

超體積(hypervolume，HV)指標(biāo)是通過(guò)計(jì)算得到非支配解決方案和參考點(diǎn)之間目標(biāo)函數(shù)的空間體積，通過(guò)提供解集收斂性和多樣性之間的關(guān)系獲得的，是衡量多目標(biāo)優(yōu)化方法求解質(zhì)量的一種綜合指標(biāo)，計(jì)算如下

(10)

為了獲得HV值，每個(gè)方法在所有工作負(fù)載實(shí)例上獨(dú)立運(yùn)行30次，并將每個(gè)算法獲得的30次運(yùn)行的解合并成一個(gè)參考集，然后，在參考集上選取非支配解，形成帕累托前沿(pareto front，PF)，剔除由真PF支配的結(jié)果。將制造周期和成本標(biāo)準(zhǔn)化，使用參考點(diǎn)(1.1,1.1)計(jì)算HV值，該值越大，說(shuō)明解決方案與參考點(diǎn)的相對(duì)空間體積越大，解的質(zhì)量越高。

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

為了驗(yàn)證所提方法在成本和時(shí)間方面的性能，將其與文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]中的方法進(jìn)行對(duì)比分析。其中文獻(xiàn)[17]提出一種基于PSO算法的靜態(tài)任務(wù)調(diào)度方法，求解過(guò)程中假定任務(wù)是非優(yōu)先并且獨(dú)立的，使用負(fù)載平衡技術(shù)提高了方法的性能。文獻(xiàn)[19]采用遺傳算法(genetic algorithm，GA)算法解決了完工時(shí)間、成本和能耗之間的帕累托最優(yōu)權(quán)衡問(wèn)題，在考慮任務(wù)優(yōu)先級(jí)的同時(shí)還兼顧了云計(jì)算中的任務(wù)能耗，使任務(wù)的完工時(shí)間和成本達(dá)到最小化。文獻(xiàn)[21]提出了SSA算法，模仿了飛松鼠的動(dòng)態(tài)跳躍策略和特征，對(duì)于優(yōu)化問(wèn)題的最優(yōu)搜索具有易于實(shí)現(xiàn)的優(yōu)點(diǎn)。

為了確保不同方法之間的公平比較，工作負(fù)載實(shí)例的初始生態(tài)系統(tǒng)(總體)、生成數(shù)、停止條件和硬件資源都是相同的。并且NASA Ames iPSC/860是一些標(biāo)準(zhǔn)格式的工作負(fù)載，用于評(píng)估分布式系統(tǒng)的性能，而Uniform是合成工作負(fù)載。

4.3.1 不同并行任務(wù)種類(lèi)下的執(zhí)行時(shí)間和成本

對(duì)于所有測(cè)試的工作負(fù)載實(shí)例，將所提方法獲得最佳結(jié)果所耗費(fèi)的執(zhí)行時(shí)間(以秒為單位)與文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]進(jìn)行比較，結(jié)果如圖3所示。

圖3 執(zhí)行時(shí)間的對(duì)比結(jié)果

從圖3可以看出，對(duì)于所有測(cè)試的工作負(fù)載實(shí)例，所提方法的執(zhí)行時(shí)間均少于其它對(duì)比方法。所提方法利用改進(jìn)ISSA能夠在較短的計(jì)算時(shí)間內(nèi)獲得更高質(zhì)量的解決方案，優(yōu)于文獻(xiàn)[21]中傳統(tǒng)的SSA。文獻(xiàn)[17]和文獻(xiàn)[19]分別使用GA和PSO算法，雖能夠在一定程度上縮短執(zhí)行時(shí)間，但隨著任務(wù)數(shù)量的增加，算法處理效率不高，導(dǎo)致執(zhí)行時(shí)間較長(zhǎng)。由此可驗(yàn)證所提方法是求解多目標(biāo)任務(wù)調(diào)度優(yōu)化問(wèn)題的有效方法。

此外，由5000個(gè)大小的工作負(fù)載實(shí)例的非支配解決方案如圖4所示。

由圖4可知，無(wú)論在NASA標(biāo)準(zhǔn)或是Uniform標(biāo)準(zhǔn)下，所提方法的性能明顯優(yōu)于其它對(duì)比方法。如圖4(a)所示，在NASA標(biāo)準(zhǔn)下，所提方法的顯著性能歸功于其底層SSA算法的全局收斂性，并且引入空間變異與擴(kuò)散機(jī)制，從而使其能夠獲得更好的收斂性，有效地處理大的搜索空間，因此，其對(duì)于成本的控制優(yōu)于其它文獻(xiàn)所提方法；其中，文獻(xiàn)[17]所提方法由于缺乏全局搜索能力，因此其性能相對(duì)較差；而文獻(xiàn)[21]和文獻(xiàn)[19]所提方法則處于中等水平。在Uniform標(biāo)準(zhǔn)下，如圖4(b)所示，文獻(xiàn)[17]的GA和文獻(xiàn)[19]的PSO算法在處理多目標(biāo)調(diào)度問(wèn)題，處理效率一般，且全局收斂性有待提高；文獻(xiàn)[21]方法與所提方法性能較為接近，但所提方法憑借其變異與擴(kuò)散機(jī)制帶來(lái)的更好的收斂性，具有更好的性能，因此略優(yōu)于文獻(xiàn)[21]所提方法。

4.3.2 不同任務(wù)數(shù)量下的HV指標(biāo)提升

對(duì)于不同任務(wù)數(shù)量，幾種方法在HV指標(biāo)方面的對(duì)比結(jié)果見(jiàn)表5。

從表5中可以看出，對(duì)于所有工作負(fù)載實(shí)例，相比文獻(xiàn)[17]、文獻(xiàn)[19]和文獻(xiàn)[21]提出的方法，所提方法的HV值有顯著提高。在不同的工作負(fù)載下，所提方法的HV值比文獻(xiàn)[21]的SSA算法提高了16.32%～35.51%，而相比文獻(xiàn)[19]的PSO算法性能提升了37.75%～63.89%，與文獻(xiàn)[17]中的GA相比，提高了94.40%～120.24%。由此可見(jiàn)，所提方法具有較好的收斂性和解決方案的多樣性，從而得到全局最優(yōu)解決方案，完成多目標(biāo)任務(wù)調(diào)度，實(shí)現(xiàn)成本和執(zhí)行時(shí)間最小化。

圖4 非支配解決方案的對(duì)比

表5 不同任務(wù)數(shù)量的HV指標(biāo)對(duì)比結(jié)果

5 結(jié)束語(yǔ)

針對(duì)云環(huán)境中多目標(biāo)任務(wù)調(diào)度優(yōu)化所存在的收斂慢且易陷入局部最優(yōu)的問(wèn)題，提出一種改進(jìn)SSA的云計(jì)算多目標(biāo)任務(wù)調(diào)度方法?；贗aaS云模型，設(shè)計(jì)了多目標(biāo)任務(wù)調(diào)度算法框架，并且將成本和執(zhí)行時(shí)間的最小化作為目標(biāo)函數(shù)，利用ISSA進(jìn)行問(wèn)題求解，其中引入空間變異與擴(kuò)散機(jī)制改進(jìn)傳統(tǒng)的SSA。此外，在CloudSim模擬器工具包中，使用NASA標(biāo)準(zhǔn)工作負(fù)載和Uniform合成工作負(fù)載對(duì)所提方法進(jìn)行實(shí)驗(yàn)驗(yàn)證，結(jié)果表明，所提方法的成本、執(zhí)行時(shí)間和HV均少于其它對(duì)比方法，以NASA為例，當(dāng)任務(wù)數(shù)量為5000時(shí)，其執(zhí)行時(shí)間和HV分別是32.12 s和21.50，并且當(dāng)執(zhí)行時(shí)間達(dá)到2500 s時(shí)，所提方法快速收斂，且成本僅約為10元。

所提方法具有較大的服務(wù)質(zhì)量提升空間，可以對(duì)其進(jìn)行擴(kuò)展，以處理對(duì)可靠性和安全性需求較高的大型負(fù)載實(shí)例。此外，實(shí)驗(yàn)僅考慮了NASA和Uniform兩種工作實(shí)例，后續(xù)工作中將考慮更多實(shí)例類(lèi)型，以提高所提方法的普適性。