喬楠楠 尤佳莉

(中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心 北京 100190)

一種面向網(wǎng)絡(luò)邊緣任務(wù)調(diào)度問題的多方向粒子群優(yōu)化算法

喬楠楠 尤佳莉

(中國科學(xué)院聲學(xué)研究所國家網(wǎng)絡(luò)新媒體工程技術(shù)研究中心 北京 100190)

任務(wù)調(diào)度是云計(jì)算及網(wǎng)格計(jì)算環(huán)境中的重要問題，已有的調(diào)度算法往往僅致力于最小化任務(wù)的總執(zhí)行時間而不設(shè)置其他約束條件，以致難以實(shí)現(xiàn)多種性能指標(biāo)的同時優(yōu)化。所提出的面向網(wǎng)絡(luò)邊緣任務(wù)調(diào)度問題的多方向粒子群優(yōu)化算法，用于解決并發(fā)任務(wù)在網(wǎng)絡(luò)邊緣服務(wù)節(jié)點(diǎn)中的分布式調(diào)度問題，調(diào)度的目標(biāo)是在任務(wù)執(zhí)行的資源開銷不超過閾值的情況下，最小化任務(wù)完成的總時間。該方法與現(xiàn)有的離散粒子群優(yōu)化算法相比同時降低了任務(wù)的總完成時間及資源開銷，且在合理預(yù)設(shè)資源開銷上限的情況下，其計(jì)算復(fù)雜度實(shí)現(xiàn)了較大程度優(yōu)化。仿真表明，所提出的方法比現(xiàn)有的離散粒子群優(yōu)化算法的任務(wù)總完成時間縮短約10.52%～13.23%，資源開銷減少約10.32%～13.29%。同時，在合理降低資源開銷閾值的情況下，該方法的程序運(yùn)行時間比現(xiàn)有的粒子群調(diào)度方法明顯縮短。

任務(wù)調(diào)度 多方向粒子群優(yōu)化 最小化完成時間 開銷閾值

0 引 言

在Web2.0時代，大規(guī)模的任務(wù)處理需求開始呈現(xiàn)，例如多媒體特效任務(wù)、大數(shù)據(jù)處理任務(wù)等。在這些任務(wù)場景下，最常見的用戶需求就是實(shí)時性需求，也即要求任務(wù)能夠被快速響應(yīng)、快速執(zhí)行、且執(zhí)行結(jié)果能夠快速回傳給用戶，因此，最小化任務(wù)完成時間是任務(wù)調(diào)度問題中最常見的目標(biāo)。除此之外，任務(wù)調(diào)度問題考慮的因素還涉及硬件設(shè)備功耗、分布式設(shè)備負(fù)載均衡度等。

云計(jì)算[1]通常通過互聯(lián)網(wǎng)來提供動態(tài)易擴(kuò)展的虛擬化的資源，以往的任務(wù)調(diào)度策略研究也大多是基于云環(huán)境展開。在云計(jì)算之后，近年來研究者提出了一些基于網(wǎng)絡(luò)邊緣環(huán)境的分布式計(jì)算模型。

Zhu等提出一種新的多媒體云計(jì)算框架[2]，也即媒體邊緣子云(MEC)，將存儲、中央處理單元和圖形處理單元部署在云邊緣位置，以便為各類設(shè)備提供分布式并行處理及QoS適配。思科于2011年提出霧計(jì)算[3]架構(gòu)，霧計(jì)算是半虛擬化的服務(wù)計(jì)算架構(gòu)模型，它更強(qiáng)調(diào)網(wǎng)絡(luò)邊緣計(jì)算設(shè)備的作用。在霧計(jì)算架構(gòu)中，服務(wù)節(jié)點(diǎn)可能是分散在網(wǎng)絡(luò)邊緣的零散設(shè)備，單個服務(wù)節(jié)點(diǎn)的計(jì)算能力可能較弱，然而依托于特有的低延遲、位置感知特性，這些節(jié)點(diǎn)可能提供更具實(shí)時性的服務(wù)。

以上基于網(wǎng)絡(luò)邊緣的分布式計(jì)算架構(gòu)利用網(wǎng)絡(luò)邊緣的低延遲特性，為用戶請求提供了實(shí)時性響應(yīng)。本文所討論的任務(wù)調(diào)度問題，正是基于以下環(huán)境特點(diǎn)：

(1) 所有服務(wù)節(jié)點(diǎn)均分布于網(wǎng)絡(luò)邊緣的ISP中，用戶節(jié)點(diǎn)位于其中某個ISP。用戶節(jié)點(diǎn)及服務(wù)節(jié)點(diǎn)均具有帶寬感知能力，可以對本節(jié)點(diǎn)到其他節(jié)點(diǎn)的數(shù)據(jù)傳輸時延進(jìn)行預(yù)測。

(2) 任務(wù)的執(zhí)行成本采用pay-as-you-go原則進(jìn)行計(jì)算，也即，執(zhí)行任務(wù)所對應(yīng)的資源開銷與實(shí)際的資源用量正相關(guān)。

1 現(xiàn)有任務(wù)調(diào)度算法及存在的問題

任務(wù)調(diào)度問題是NP-hard問題，已有的任務(wù)調(diào)度算法主要分為兩大類，一類是基于局部貪心策略的算法[4]，另一類是啟發(fā)式的智能搜索方法。

在局部貪心策略方面，Max-Min算法用ECT矩陣表示各個任務(wù)在各個機(jī)器節(jié)點(diǎn)上的完成時間的預(yù)測值，且每次優(yōu)先調(diào)度具有最長完成時間的作業(yè)。Min-Min算法與Max-Min算法計(jì)算方式相似，不同之處在于，Min-Min優(yōu)先調(diào)度具有最短完成時間的作業(yè)。Sufferage算法用任務(wù)在機(jī)器上的最早完成時間與次早完成時間差值的絕對值表示為損失度，并優(yōu)先調(diào)度損失度較大的任務(wù)。此類基于局部貪心策略的算法，調(diào)度的原則是讓當(dāng)前任務(wù)盡可能占用較優(yōu)的服務(wù)器資源，因而可能無法讓所有任務(wù)公平地占用資源。

Khaled等提出基于遺傳算法的任務(wù)調(diào)度方法[5]，該算法將一個調(diào)度方案表示為一個染色體，并利交叉、變異等運(yùn)算符實(shí)現(xiàn)調(diào)度方案的進(jìn)化。遺傳算法所實(shí)現(xiàn)的方案進(jìn)化是均勻的進(jìn)化，其收斂速度較慢。

粒子群優(yōu)化算法(PSO)[6]由Kenney等在1995年提出。PSO算法從隨機(jī)解出發(fā)，通過適應(yīng)度函數(shù)來評價解的優(yōu)劣，并通過迭代尋找最優(yōu)解。相比于遺傳算法，PSO通過追隨當(dāng)前搜索到的最優(yōu)值來尋找全局最優(yōu)解，規(guī)則更為簡單，不需要進(jìn)行交叉和變異等操作。Kenney和Eberhard定義的粒子坐標(biāo)更新的方式如下所示：

vid=vid+φ(pid-xid)+φ(pgd-xid)

(1)

xid=xid+vid

(2)

其中，d是解空間的一個維度，xi表示粒子群中的第i個粒子，也即第i個解，pi是xi當(dāng)前在歷次迭代中的獲得的最優(yōu)解，也即局部最優(yōu)解，pg則是整個粒子群當(dāng)前的全局最優(yōu)解。

由于PSO致力于在連續(xù)解空間中進(jìn)行搜索，對于解決離散解空間中的問題具有局限性。1997年，Kenney等提出了基于離散二進(jìn)制解空間的粒子群優(yōu)化算法[7]，在該算法中，每一個粒子的坐標(biāo)都是二進(jìn)制取值。Kenney等對粒子坐標(biāo)更新的方式進(jìn)行了重新定義：

if (rand()

(3)

其中S(v) 是Sigmoid函數(shù)，如式(4)所示，Sigmoid函數(shù)取值與自變量取值呈正相關(guān)，其函數(shù)值位于區(qū)間[0,1]。當(dāng)S(vid)大于隨機(jī)數(shù)rand()時，粒子xi在d維的坐標(biāo)取1，否則取0。

(4)

上述方法有效解決了粒子群在二進(jìn)制解空間中的粒子坐標(biāo)編碼問題，通過該方法得出的粒子坐標(biāo)均為二進(jìn)制取值。

在此之后，研究者們基于粒子群及離散粒子群優(yōu)化算法提出了多種任務(wù)調(diào)度方法，這些方法的優(yōu)化思路包括粒子坐標(biāo)編碼[8]、自適應(yīng)速度調(diào)整[9]及局部搜索[10]等。然而現(xiàn)有的基于粒子群優(yōu)化的任務(wù)調(diào)度方法仍然存在以下問題：

(1) 現(xiàn)有方法大多沿用經(jīng)典粒子群中的群體遷移思想，即選取全局最優(yōu)解和局部最優(yōu)解作為粒子進(jìn)化的方向。由于局部最優(yōu)解僅為當(dāng)前粒子所取得的歷史最優(yōu)解，并非代表整個群體的最優(yōu)信息，因此，以局部最優(yōu)解為導(dǎo)向的進(jìn)化可能會損失一部分性能；

(2) 現(xiàn)有方法中，隨著迭代次數(shù)增加，群體中的粒子數(shù)目維持恒定，對于在無效解空間中的搜索行為缺少制約條件。

2 多方向粒子群優(yōu)化算法解決任務(wù)調(diào)度問題

針對上一節(jié)中提到的現(xiàn)有粒子群調(diào)度算法存在的問題，本節(jié)提出一種多方向粒子群優(yōu)化算法。所提出的算法主要致力于從以下2個方面實(shí)現(xiàn)創(chuàng)新及改進(jìn)：

(1) 提出一種新的群體遷移方式。在實(shí)際的調(diào)度問題中，由于一個粒子實(shí)際指代調(diào)度問題的一個可行解，也即一個任務(wù)分配方案，而非自然界中的個體位置信息，因此粒子的移動無須保持自身的原有軌跡。本文提出的粒子群優(yōu)化算法，從任務(wù)總完成時間(makespan)及資源總開銷(budget)2個維度分別得出精英解集，以2個精英解集為方向?qū)崿F(xiàn)粒子遷移，使得粒子群同時向makespan優(yōu)化和budget優(yōu)化2個方向移動，提供了一種有效的信息共享方法。

(2) 提出基于模糊集合的粒子淘汰機(jī)制。該算法制定了基于模糊集合的適應(yīng)度函數(shù)，并根據(jù)粒子適應(yīng)度的優(yōu)劣進(jìn)行粒子淘汰，避免了在無效解空間的搜索行為，在一定條件下，可降低程序的計(jì)算復(fù)雜度。

2.1 問題假設(shè)及目標(biāo)

假設(shè)用戶發(fā)起N個任務(wù){(diào)T1,T2,…,TN}，位于網(wǎng)絡(luò)邊緣ISP中的M個服務(wù)節(jié)點(diǎn){S1,S2,…,SM}提供任務(wù)響應(yīng)及處理。該調(diào)度問題基于以下假設(shè)：

(1) 每個任務(wù)可以被任一服務(wù)節(jié)點(diǎn)執(zhí)行；

(2) 每個服務(wù)節(jié)點(diǎn)在同一時刻只能處理1個任務(wù)；

(3) 每個服務(wù)節(jié)點(diǎn)處理單位大小的源文件所需的時間是已知的；

(4) 每個服務(wù)節(jié)點(diǎn)在工作狀態(tài)下單位時間內(nèi)的資源開銷是已知的；

(5) 同一個ISP內(nèi)部的多個服務(wù)節(jié)點(diǎn)之間的數(shù)據(jù)傳輸造成的資源開銷可忽略不計(jì)，跨ISP傳輸單位大小文件造成的資源開銷是已知的；

(6) 同一個ISP內(nèi)部的多個服務(wù)節(jié)點(diǎn)之間的數(shù)據(jù)傳輸速率大于不同ISP之間的數(shù)據(jù)傳輸速率。

基于以上假設(shè)，調(diào)度問題的一個可行解可表示為x=[x(1),x(2),…,x(N)]，其中x(i)為第i個任務(wù)對應(yīng)的服務(wù)節(jié)點(diǎn)ID。該調(diào)度問題的目標(biāo)為：尋找一個任務(wù)-服務(wù)節(jié)點(diǎn)分配矩陣，在任務(wù)執(zhí)行的總開銷不超過預(yù)設(shè)上限的前提下，最小化任務(wù)的總完成時間。

2.2 性能指標(biāo)計(jì)算

根據(jù)主流的云計(jì)算平臺如AmazonEC2提供的計(jì)費(fèi)機(jī)制，用戶因使用彈性資源而支付的費(fèi)用主要包含兩方面，一方面是占用虛擬機(jī)的計(jì)算資源及存儲資源所帶來的開銷，另一方面開銷則來自數(shù)據(jù)傳輸費(fèi)用。在虛擬機(jī)資源計(jì)費(fèi)方面，為適應(yīng)不同使用場景下的用戶需求，Amazon制定了3種可選使用方式，也即按需使用型實(shí)例、預(yù)留型實(shí)例及即時型實(shí)例；在數(shù)據(jù)傳輸計(jì)費(fèi)方面，數(shù)據(jù)在同一可用區(qū)域之內(nèi)傳輸不計(jì)費(fèi)，在不同的區(qū)域之間視InternetData計(jì)費(fèi)。

在本文所涉及的任務(wù)執(zhí)行成本計(jì)算原則上，為詳細(xì)分析不同任務(wù)調(diào)度方法所對應(yīng)的任務(wù)執(zhí)行開銷，參考Amazon制定的按需使用計(jì)費(fèi)方式，假設(shè)單個服務(wù)節(jié)點(diǎn)的計(jì)算成本正比于該節(jié)點(diǎn)上任務(wù)的完成用時。除此之外，用戶還需支付其向服務(wù)節(jié)點(diǎn)傳輸任務(wù)源文件所造成的數(shù)據(jù)傳輸費(fèi)用，此項(xiàng)費(fèi)用正比于跨區(qū)域傳輸?shù)膶?shí)際數(shù)據(jù)量。

基于以上原則，用ecti,j表示任務(wù)Ti在服務(wù)節(jié)點(diǎn)Sj上的預(yù)測完成時間，bi,j表示Ti在機(jī)器Sj上的執(zhí)行開銷，則ecti,j和bi,j的計(jì)算方式如式(5)-式(8)所示：

eti,j=ifsi/mipsj

(5)

sti,j=max(at,itj)+ttr(u,j,ifsi)

(6)

ecti,j=sti,j+eti,j

(7)

bi,j=bpsj×eti,j+btr(u,j,ifsi)

(8)

其中，eti,j為任務(wù)Ti在服務(wù)節(jié)點(diǎn)Sj上的預(yù)測執(zhí)行用時，ifsi為Ti的源文件大小，mipsj為節(jié)點(diǎn)Sj單位時間可處理的源文件大小，sti,j為Ti在Sj上最早開始時間，at為批量任務(wù)的到達(dá)時間，itj為Sj的最早空閑時間，bpsj為Sj在工作狀態(tài)下單位時間內(nèi)的運(yùn)行開銷，該取值與Sj的計(jì)算能力也即單位時間內(nèi)的文件處理能力正相關(guān)。ttr(u,j,ifsi)為從用戶節(jié)點(diǎn)到服務(wù)節(jié)點(diǎn)Sj傳輸大小為ifsi的文件所需時間，令用戶節(jié)點(diǎn)u到服務(wù)節(jié)點(diǎn)Sj的傳輸速率為bwu,j，則ttr(u,j,ifsi)的計(jì)算方式如式(9)所示。btr(u,j,ifsi)為從用戶節(jié)點(diǎn)u到Sj傳輸ifsi大小文件所需網(wǎng)絡(luò)資源開銷，當(dāng)u與Sj屬于同一區(qū)域ISP時，該項(xiàng)取值為0，否則，令跨區(qū)域傳輸單位數(shù)據(jù)量所需的網(wǎng)絡(luò)資源開銷為ξ，則btr(u,j,ifsi)計(jì)算方式如式(10)所示。

ttr(u,j,ifsi)=ifsi/bwu,j

(9)

btr(u,j,ifsi)=ξ×ifsi

(10)

對于已知的任務(wù)集合{T1,T2,…,TN}及服務(wù)節(jié)點(diǎn)集合{S1,S2,…,SM}，若存在調(diào)度問題的一個可行解x=[x(1),x(2),…,x(N)]，則該解對應(yīng)的任務(wù)總完成時間makespan(x)及總開銷budget(x)計(jì)算方式如下：

(1) 將makespan(x)及budget(x)賦值為0；

(2) 對于每一個任務(wù)Ti，執(zhí)行步驟(3)-步驟(5)；

(3) 根據(jù)式(3)計(jì)算ecti,x(i)；

(4) 根據(jù)式(4)計(jì)算bi,x(i)，更新budget(x)的值為budget(x)+bi,x(i)；

(5) 更新服務(wù)節(jié)點(diǎn)Sx(i)的最早空閑時間；

2.3 粒子群初始化

調(diào)度問題的一個可行解稱為一個粒子，在初始化階段，若種群初始規(guī)模設(shè)置為L，則生成L個隨機(jī)粒子x1,x2,…,xL。其中，每一個粒子xi為N維向量，可表示為x=[xi(1),xi(2),…,xi(N)]，其中第j維度坐標(biāo)值xi(j)為第j個任務(wù)對應(yīng)的服務(wù)節(jié)點(diǎn)ID。

2.4 適應(yīng)度函數(shù)

由于該調(diào)度問題的優(yōu)化目標(biāo)是在任務(wù)執(zhí)行的總開銷不超過預(yù)定閾值b+的情況下，最小化任務(wù)的總完成時間，因此設(shè)定粒子的適應(yīng)度值f(x)與其對應(yīng)的任務(wù)總完成時間makespan(x)負(fù)相關(guān)，即，一個可行解對應(yīng)的makespan(x)值越大，其適應(yīng)度越低。同時，對于執(zhí)行開銷超過閾值的解，對其適應(yīng)度取值加以限制。

設(shè)定任務(wù)執(zhí)行開銷的閾值b+和準(zhǔn)閾值b-(b-b+，則b屬于A的概率為0，也即絕對不屬于A，當(dāng)b-

(11)

如前所述，任務(wù)調(diào)度的目標(biāo)是在任務(wù)執(zhí)行的總開銷不超過既定閾值的情況下，最小化任務(wù)的總完成時間。因此，適應(yīng)度函數(shù)設(shè)定的原則為：當(dāng)粒子對應(yīng)的調(diào)度方案總執(zhí)行開銷不超過準(zhǔn)閾值b-時，其適應(yīng)度值與任務(wù)的總完成時間成反比，若其總開銷超過b-，則粒子適應(yīng)度以一定的風(fēng)險取0，若其總開銷超過閾值b+，則其適應(yīng)度以100%的概率取0。適應(yīng)度函數(shù)定義如式(12)所示，其中A為式(11)所定義的模糊集合。

(12)

2.5 多方向粒子群進(jìn)化

2.5.1 基于精英解集的多方向粒子移動

由于一個粒子實(shí)際指代調(diào)度問題的一個可行解，也即一個任務(wù)分配方案，而非自然界中的個體位置信息，因此粒子的移動無須保持自身的原有軌跡。在每一輪迭代中，為保證領(lǐng)導(dǎo)者提供優(yōu)質(zhì)的信息，只選取全局最優(yōu)解作為種群的領(lǐng)導(dǎo)者。

根據(jù)2.2節(jié)所述的成本計(jì)算原則，可以得出makespan和budget兩個性能指標(biāo)之間的基本關(guān)聯(lián)：因?yàn)楣?jié)點(diǎn)單位時間內(nèi)的運(yùn)行成本與其計(jì)算能力正相關(guān)，因此，具有較優(yōu)計(jì)算資源的節(jié)點(diǎn)在快速處理任務(wù)的同時也造成更多資源開銷。但是，makespan與budget兩項(xiàng)指標(biāo)又在一定程度上存在一致性，由于一個區(qū)域ISP內(nèi)部的數(shù)據(jù)傳輸不計(jì)成本，且傳輸速率大于不同ISP之間的數(shù)據(jù)傳輸速率，因此，在一定程度上減少跨區(qū)域的數(shù)據(jù)傳輸，可能實(shí)現(xiàn)makespan和budget的同時優(yōu)化。

(1) 將當(dāng)前粒子群中的所有粒子按照makespan值進(jìn)行升序排序，并將前K個粒子存放入精英解集Archive1；

(2) 將所有粒子按budget值進(jìn)行升序排序，并將前K個粒子存放入精英解集Archive2；

(13)

(14)

β=[prob1,prob2,1-prob1-prob2]

(15)

2.5.2 基于模糊集合的粒子淘汰

為了控制粒子的budget值，使其滿足約束條件，在每一輪迭代中淘汰適應(yīng)度為0的粒子，從而使群體中保留的粒子均符合約束條件。當(dāng)滿足下列條件之一時，迭代終止。

(1) 迭代次數(shù)超過預(yù)設(shè)值Max(Iters)

(2) 剩余粒子數(shù)目小于預(yù)設(shè)值Min(Population)

粒子群進(jìn)化算法表示如下所示：

Initial the swarm with x1,x2,…,xL;

Setthebudgetconstraintb+andb-;

Settheprobabilityprob1andprob2;

t←1;

whiletheterminalconditionisnotmetdo

GettheelitesetArchive1andArchive2;

fort←1toLdo

endfor

fort←1toLdo

endif

endfor

L←thecurrentpopulationoftheswarm;

t←t+1;

endwhile;

上述方法在每一輪迭代中，淘汰適應(yīng)度為0的解，即，以100%的概率淘汰budget值超過b+的解，并以一定概率淘汰budget值超過b-的解，從而實(shí)現(xiàn)對于群體budget的整體控制。

3 仿真測試

(16)

(17)

(18)

上述方法提供了適用于本文調(diào)度問題的離散坐標(biāo)編碼方式，從而提供了重現(xiàn)的可能性。同時，該方法與本文具有相似的優(yōu)化目標(biāo)，也即致力于優(yōu)化并發(fā)任務(wù)的總完成時間，因此本節(jié)對上述方法進(jìn)行重現(xiàn)，并與本文提出的多方向粒子群優(yōu)化方法進(jìn)行比較，著重分析任務(wù)處理的總時間(makespan)、資源開銷(budget)及程序運(yùn)行的時間(runtime)。

3.1 測試環(huán)境

基于Windows平臺Matlab7.1工具進(jìn)行了仿真測試，處理器型號為Inteli5-4570，CPU頻率為3.2GHz，可用內(nèi)存為3.43GB。

3.2 任務(wù)規(guī)模及服務(wù)節(jié)點(diǎn)設(shè)置

提供服務(wù)的14個虛擬機(jī)節(jié)點(diǎn)VM1-VM14分布在ISP1-ISP3中。CP表示虛擬機(jī)節(jié)點(diǎn)計(jì)算能力，也即節(jié)點(diǎn)在單位時間內(nèi)處理的文件規(guī)模(KB/s)，BPS表示節(jié)點(diǎn)在工作狀態(tài)下每秒的開銷(cent/s)。發(fā)起任務(wù)請求的客戶端建立在ISP2中的VM9節(jié)點(diǎn)上，在測試初始化時發(fā)起15個任務(wù)，任務(wù)的源文件規(guī)模為32～64MB。如表1所示。

表1 服務(wù)節(jié)點(diǎn)計(jì)算能力及開銷設(shè)置

假設(shè)一個ISP內(nèi)部多個節(jié)點(diǎn)之間的文件傳輸代價可忽略，跨ISP的文件傳輸開銷與文件大小呈正相關(guān)，具體設(shè)置如表2所示。同一個ISP內(nèi)各虛擬機(jī)之間傳輸速率為1.25Mbps，不同ISP的虛擬機(jī)之間傳輸速率為10Mbps。

表2 各ISP之間文件傳輸開銷設(shè)置

3.3 仿真結(jié)果及分析

在如下所示2個實(shí)例中，精英解集Archive1和Archive2的元素個數(shù)均設(shè)置為K=5，開銷“準(zhǔn)閾值”b-均比b+減少10cent，即b+-b-=10，其余各個參數(shù)取值設(shè)置如表3所示。

表3 仿真參數(shù)設(shè)置

在以上2個實(shí)例中，針對粒子群初始化規(guī)模為200、500、1 000三種情況進(jìn)行了仿真，且隨著迭代次數(shù)的改變，共得出9個數(shù)據(jù)點(diǎn)P1-P9，如表4所示。

表4 初始化粒子數(shù)目及迭代次數(shù)設(shè)置

在圖1、圖2及圖3中，實(shí)例1對應(yīng)的數(shù)據(jù)曲線標(biāo)記為MDPSO-1及DPSO-1，實(shí)例2對應(yīng)的數(shù)據(jù)曲線標(biāo)記為MDPSO-2及DPSO-2，橫坐標(biāo)表示9個數(shù)據(jù)點(diǎn)P1-P9，仿真結(jié)果如下所示。

圖1 Makespan仿真結(jié)果

圖2 Budget仿真結(jié)果

圖3 Runtime仿真結(jié)果

在實(shí)例1中，就makespan而言，如圖1所示，MDPSO算法的平均makespan為1 275.2s，相比于DPSO的1 469.7s平均減少 13.23%。就budget而言，如圖2所示，實(shí)例1受到閾值b+=150的限制，MDPSO算法的平均budget為144.2cent，相比于DPSO的160.8cent平均減少10.32%。

在實(shí)例2中，MDPSO平均實(shí)現(xiàn)了1297.5s的makespan，相比于DPSO的1 450.1s降低了10.52%，由于設(shè)置了更低的b+值，MDPSO算法實(shí)現(xiàn)了更低的budget，MDPSO的budget為138.3cent，相比于DPSO的159.5cent降低了13.29%。

就runtime而言，如圖3所示，由于MDPSO算法涉及全局較優(yōu)解集合的提取，該步驟具有較高的計(jì)算復(fù)雜度，在實(shí)例1中，隨著粒子數(shù)目及迭代次數(shù)增加，其runtime逐漸高于DPSO。但在實(shí)例2中MDPSO通過合理降低b+值，也即降低budget的上限，可以在每一輪迭代中促使更多無效的解被淘汰，因此粒子的數(shù)目明顯減少，在后續(xù)的迭代中計(jì)算復(fù)雜度逐漸降低，runtime明顯低于DPSO。

仿真表明，本文提出的多方向粒子群進(jìn)化方法具有較好的信息共享能力，通過makespan及budget兩個維度分別獲得全局最優(yōu)解，實(shí)現(xiàn)一種多方向粒子遷移，并使全局最優(yōu)解的優(yōu)質(zhì)的信息以較高的概率保存至新一代粒子群。同時，在適當(dāng)降低開銷閾值的情況下，算法的計(jì)算復(fù)雜度得以降低，實(shí)現(xiàn)較短的程序運(yùn)行時間。

4 結(jié) 語

本文提出了一種面向網(wǎng)絡(luò)邊緣任務(wù)調(diào)度問題的多方向粒子群優(yōu)化算法，該方法利用網(wǎng)絡(luò)邊緣ISP中的服務(wù)節(jié)點(diǎn)為終端用戶提交的任務(wù)請求提供實(shí)時響應(yīng)，致力于在任務(wù)執(zhí)行的總開銷不超過閾值的前提下，最小化所有任務(wù)的總完成時間。一方面，該算法設(shè)計(jì)了基于精英解集的粒子遷移方法，通過2個全局最優(yōu)解實(shí)現(xiàn)高效的信息共享，使得解空間中的粒子在makespan及budget兩個維度實(shí)現(xiàn)同時優(yōu)化。另一方面，該算法采用基于模糊集合的粒子淘汰方法，在一定條件下降低了算法的計(jì)算復(fù)雜度。

仿真表明，所提出基于精英解集的粒子遷移方法具有較好的信息共享能力，能夠?qū)崿F(xiàn)多個目標(biāo)的同時優(yōu)化，比現(xiàn)有的離散粒子群優(yōu)化算法實(shí)現(xiàn)的任務(wù)總完成時間縮短約10.52%～13.23%，資源開銷減少約10.32%～13.29%。同時，基于模糊集合的粒子淘汰方法，在每一輪迭代中淘汰適應(yīng)度極低的粒子，在合適的開銷閾值限制下，該方法能夠極大地縮短程序運(yùn)行的總時間。

[1]ArmbrustM,FoxA,GriffithR,etal.Aviewofcloudcomputing[J].CommunicationsoftheACM,2010,53(4):50-58.

[2]ZhuW,LuoC,WangJ,etal.MultimediaCloudComputing[J].IEEESignalProcessingMagazine,2011,28(3):59-69.

[3]BonomiF,MilitoR,ZhuJ,etal.FogComputinganditsRoleintheInternetofThings[C]//ProceedingsofthefirsteditionoftheMCCWorkshoponMobileCloudComputing.ACM,2012:13-16.

[4]TabakEK,CambazogluBB,AykanatC.ImprovingthePerformanceofIndependentTaskAssignmentHeuristicsMinMin,MaxMinandSufferage[J].IEEETransactionsonParallelandDistributedSystems,2014,25(5):1244-1256.

[5]KhaledAKM,TalukderA,KirleyM,etal.MultiobjectivedifferentialevolutionforschedulingworkflowapplicationsonglobalGrids[J].ConcurrencyandComputation:Practice&Experience,2009,21(13):1742-1756.

[6]KennedyJ,EberhartR.Particleswarmoptimization[C]//IEEEInternationalConferenceonNeuralNetworks,1995:1942-1948.

[7]KennedyJ,EberhartRC.Adiscretebinaryversionoftheparticleswarmalgorithm[C]//IEEEInternationalConferenceonSystems,Man,andCybernetics.IEEE,1997:4104-4108.

[8]LiaoCJ,TsengCT,LuarnP.Adiscreteversionofparticleswarmoptimizationforflowshopschedulingproblems[J].Computers&OperationsResearch,2007,34(10):3099-3111.

[9]ZuoX,ZhangG,TanW.Self-AdaptiveLearningPSO-BasedDeadlineConstrainedTaskSchedulingforHybridIaaSCloud[J].IEEETransactionsonAutomationScienceandEngineering,2014,11(2):564-573.

[10]MoslehiG,MahnamM.AParetoapproachtomulti-objectiveflexiblejob-shopschedulingproblemusingparticleswarmoptimizationandlocalsearch[J].InternationalJournalofProductionEconomics,2011,129(1):14-22.

A MULTI-DIRECTIONAL PARTICLE SWARM OPTIMIZATION ALGORITHM FOR NETWORK EDGE TASK SCHEDULING

Qiao Nannan You Jiali

(NationalNetworkNewMediaEngineeringResearchCenter,InstituteofAcoustics,ChineseAcademyofSciences,Beijing100190,China)

Task scheduling is an important problem in cloud computing and grid computing environments. Existing scheduling algorithms are often only dedicated to minimizing the total execution time of tasks without setting other constraints, making it difficult to optimize multiple performance metrics simultaneously. The proposed multi-directional particle swarm optimization algorithm for network edge task scheduling problem solves the distributed scheduling problem of concurrent tasks in network edge service nodes. The goal of scheduling is to minimize the total time of task completion in the case that the resource cost of task execution less than the threshold. Compared with the existing discrete particle swarm optimization algorithm, this method reduces the total task completion time and resource cost, and achieves a large degree of optimization of its computational complexity in the case of a reasonable preset resource overhead. The simulation results show that compared with the existing discrete particle swarm optimization algorithm, this method can reduce the total task completion time by about 10.52%～13.23% and the resource cost by 10.32% ～13.29%. Meanwhile, the running time of this method is significantly shorter than that of the existing discrete particle swarm optimization algorithm in the case of a reasonable reduction of resource overhead threshold.

Task scheduling Multi-direction particle swarm optimization Minimal makespan Overhead threshold

2016-03-16。中國科學(xué)院戰(zhàn)略先導(dǎo)技術(shù)專項(xiàng)基金(XDA06040501)。喬楠楠，碩士生，主研領(lǐng)域：優(yōu)化算法，多媒體服務(wù)。尤佳莉，副研究員。

TP3

A

10.3969/j.issn.1000-386x.2017.04.053