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

喬楠楠 尤佳莉

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

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

喬楠楠 尤佳莉

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

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

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

0 引 言

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

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

Zhu等提出一種新的多媒體云計(jì)算框架[2]，也即媒體邊緣子云(MEC)，將存儲(chǔ)、中央處理單元和圖形處理單元部署在云邊緣位置，以便為各類設(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è)備，單個(gè)服務(wù)節(jié)點(diǎn)的計(jì)算能力可能較弱，然而依托于特有的低延遲、位置感知特性，這些節(jié)點(diǎn)可能提供更具實(shí)時(shí)性的服務(wù)。

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

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

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

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

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

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

Khaled等提出基于遺傳算法的任務(wù)調(diào)度方法[5]，該算法將一個(gè)調(diào)度方案表示為一個(gè)染色體，并利交叉、變異等運(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ā)，通過(guò)適應(yīng)度函數(shù)來(lái)評(píng)價(jià)解的優(yōu)劣，并通過(guò)迭代尋找最優(yōu)解。相比于遺傳算法，PSO通過(guò)追隨當(dāng)前搜索到的最優(yōu)值來(lái)尋找全局最優(yōu)解，規(guī)則更為簡(jiǎn)單，不需要進(jìn)行交叉和變異等操作。Kenney和Eberhard定義的粒子坐標(biāo)更新的方式如下所示：

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

(1)

xid=xid+vid

(2)

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

由于PSO致力于在連續(xù)解空間中進(jìn)行搜索，對(duì)于解決離散解空間中的問題具有局限性。1997年，Kenney等提出了基于離散二進(jìn)制解空間的粒子群優(yōu)化算法[7]，在該算法中，每一個(gè)粒子的坐標(biāo)都是二進(jìn)制取值。Kenney等對(duì)粒子坐標(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()時(shí)，粒子xi在d維的坐標(biāo)取1，否則取0。

(4)

上述方法有效解決了粒子群在二進(jìn)制解空間中的粒子坐標(biāo)編碼問題，通過(guò)該方法得出的粒子坐標(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)解，并非代表整個(gè)群體的最優(yōu)信息，因此，以局部最優(yōu)解為導(dǎo)向的進(jìn)化可能會(huì)損失一部分性能；

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

根據(jù)主流的云計(jì)算平臺(tái)如AmazonEC2提供的計(jì)費(fèi)機(jī)制，用戶因使用彈性資源而支付的費(fèi)用主要包含兩方面，一方面是占用虛擬機(jī)的計(jì)算資源及存儲(chǔ)資源所帶來(lái)的開銷，另一方面開銷則來(lái)自數(shù)據(jù)傳輸費(fèi)用。在虛擬機(jī)資源計(jì)費(fèi)方面，為適應(yīng)不同使用場(chǎng)景下的用戶需求，Amazon制定了3種可選使用方式，也即按需使用型實(shí)例、預(yù)留型實(shí)例及即時(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)度方法所對(duì)應(yīng)的任務(wù)執(zhí)行開銷，參考Amazon制定的按需使用計(jì)費(fèi)方式，假設(shè)單個(gè)服務(wù)節(jié)點(diǎn)的計(jì)算成本正比于該節(jié)點(diǎn)上任務(wù)的完成用時(shí)。除此之外，用戶還需支付其向服務(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ù)測(cè)完成時(shí)間，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ù)測(cè)執(zhí)行用時(shí)，ifsi為Ti的源文件大小，mipsj為節(jié)點(diǎn)Sj單位時(shí)間可處理的源文件大小，sti,j為Ti在Sj上最早開始時(shí)間，at為批量任務(wù)的到達(dá)時(shí)間，itj為Sj的最早空閑時(shí)間，bpsj為Sj在工作狀態(tài)下單位時(shí)間內(nèi)的運(yùn)行開銷，該取值與Sj的計(jì)算能力也即單位時(shí)間內(nèi)的文件處理能力正相關(guān)。ttr(u,j,ifsi)為從用戶節(jié)點(diǎn)到服務(wù)節(jié)點(diǎn)Sj傳輸大小為ifsi的文件所需時(shí)間，令用戶節(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時(shí)，該項(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)

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

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

(2) 對(duì)于每一個(gè)任務(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)的最早空閑時(shí)間；

2.3 粒子群初始化

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

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

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

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

(11)

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

(12)

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

2.5.1 基于精英解集的多方向粒子移動(dòng)

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

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

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

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

(13)

(14)

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

(15)

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

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

(1) 迭代次數(shù)超過(guò)預(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值超過(guò)b+的解，并以一定概率淘汰budget值超過(guò)b-的解，從而實(shí)現(xiàn)對(duì)于群體budget的整體控制。

3 仿真測(cè)試

(16)

(17)

(18)

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

3.1 測(cè)試環(huán)境

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

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

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

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

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

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

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

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

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

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

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

在圖1、圖2及圖3中，實(shí)例1對(duì)應(yīng)的數(shù)據(jù)曲線標(biāo)記為MDPSO-1及DPSO-1，實(shí)例2對(duì)應(yīng)的數(shù)據(jù)曲線標(biāo)記為MDPSO-2及DPSO-2，橫坐標(biāo)表示9個(gè)數(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通過(guò)合理降低b+值，也即降低budget的上限，可以在每一輪迭代中促使更多無(wú)效的解被淘汰，因此粒子的數(shù)目明顯減少，在后續(xù)的迭代中計(jì)算復(fù)雜度逐漸降低，runtime明顯低于DPSO。

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

4 結(jié) 語(yǔ)

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

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

[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。中國(guó)科學(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