袁友偉，黃錫愷+，俞東進(jìn)，李忠金

(1.杭州電子科技大學(xué) 計(jì)算機(jī)學(xué)院，浙江 杭州 310018；2.復(fù)雜系統(tǒng)建模與仿真教育部重點(diǎn)實(shí)驗(yàn)室，浙江 杭州 310018)

0 引言

隨著移動(dòng)互聯(lián)網(wǎng)技術(shù)的不斷發(fā)展，涌現(xiàn)出越來越多的新型移動(dòng)應(yīng)用程序，其中部分應(yīng)用如人臉識別、自然語言處理和增強(qiáng)現(xiàn)實(shí)[1]對于計(jì)算資源有較高的需求。由于移動(dòng)設(shè)備在存儲器、電池和處理器等方面[2-3]的限制，部分新型移動(dòng)應(yīng)用程序無法在其上運(yùn)行，而移動(dòng)邊緣計(jì)算(Mobile Edge Computing, MEC)的出現(xiàn)，為解決上述問題提供了新的平臺和思路。在MEC的工作流調(diào)度過程中，將移動(dòng)設(shè)備中需要大量計(jì)算資源的任務(wù)卸載至邊緣側(cè)的演進(jìn)節(jié)點(diǎn)(evolved Node B，eNB)中執(zhí)行[4]，可以減少任務(wù)執(zhí)行時(shí)間。服務(wù)工作流延時(shí)優(yōu)化[5]是MEC環(huán)境下工作流調(diào)度的核心問題，然而隨著應(yīng)用的不斷發(fā)展，服務(wù)工作流所需要的計(jì)算資源需求量日益增加，傳統(tǒng)的調(diào)度方案已經(jīng)不能夠滿足日漸增長的計(jì)算需求，故需對調(diào)度方案[6]進(jìn)行優(yōu)化。在任務(wù)執(zhí)行過程中，服務(wù)器通常會因資源節(jié)點(diǎn)的軟件或者硬件故障問題出現(xiàn)資源失效情況[7]，導(dǎo)致在其上運(yùn)行的任務(wù)執(zhí)行失敗，故需引入容錯(cuò)技術(shù)減少任務(wù)失敗率，提高工作流執(zhí)行的穩(wěn)定性。目前調(diào)度算法大都只針對工作流延時(shí)問題或容錯(cuò)策略中的某一方面進(jìn)行考慮，而在實(shí)際工作流調(diào)度過程中，任務(wù)出錯(cuò)無法避免，故需要綜合考慮工作流延時(shí)問題和容錯(cuò)策略。

基于上述分析，本文研究了移動(dòng)邊緣環(huán)境下服務(wù)工作流容錯(cuò)調(diào)度，針對移動(dòng)端的服務(wù)工作流調(diào)度問題，提出一種適用于多服務(wù)工作流的容錯(cuò)免疫粒子群優(yōu)化調(diào)度算法(Fault Tolerant Immune Particle Swarm Optimization algorithm, FT-IPSO)。該算法利用異構(gòu)最早完成時(shí)間(Heterogeneous Earliest Finish Time, HEFT)算法對抵達(dá)的工作流進(jìn)行分層，并計(jì)算其中的任務(wù)權(quán)重生成就緒隊(duì)列，保證了調(diào)度的公平性；通過免疫算法保持粒子群尋優(yōu)的全局性，避免粒子陷入局部最優(yōu)解；制定了一種混合容錯(cuò)策略，根據(jù)任務(wù)子期限以及任務(wù)期望執(zhí)行時(shí)間確定任務(wù)容錯(cuò)方法，保證服務(wù)工作流在執(zhí)行過程中的魯棒性；在粒子的編碼設(shè)計(jì)中以整數(shù)映射任務(wù)和資源節(jié)點(diǎn)的調(diào)度關(guān)系，并考慮了主副版本任務(wù)的調(diào)度位置，加快了粒子群的尋優(yōu)速度。

1 相關(guān)工作

近年來，隨著MEC的發(fā)展，大量學(xué)者對移動(dòng)邊緣環(huán)境下的工作流卸載問題以及工作流容錯(cuò)調(diào)度算法進(jìn)行了研究，本章主要從MEC下工作流卸載和容錯(cuò)算法兩方面對研究現(xiàn)狀進(jìn)行介紹。

MEC是一種新穎的并行計(jì)算技術(shù)，該技術(shù)可將移動(dòng)設(shè)備中具有嚴(yán)格延遲要求的計(jì)算密集型任務(wù)卸載至邊緣服務(wù)器中執(zhí)行，有效降低任務(wù)的傳輸延時(shí)。ZHAO等[8]針對移動(dòng)邊緣環(huán)境下具有延遲限制工作流任務(wù)卸載的問題，提出一種最小化延時(shí)優(yōu)化算法，將具有嚴(yán)格延遲邊界的任務(wù)卸載到邊緣云，并將松散延遲邊界的任務(wù)卸載到遠(yuǎn)程云。CHAMOLA等[9]通過將計(jì)算密集型任務(wù)卸載到云服務(wù)器，解決了cloudlet網(wǎng)絡(luò)中的任務(wù)分配問題，降低了任務(wù)延時(shí)。LE等[10]針對移動(dòng)邊緣環(huán)境中多用戶共享資源的任務(wù)卸載問題，制定了相應(yīng)的聯(lián)合優(yōu)化問題優(yōu)化算法，使得用戶任務(wù)的完成時(shí)間最小化。CHEN等[4]利用軟件定義網(wǎng)絡(luò)的思想，將工作流任務(wù)卸載問題表示為NP-hard的混合整數(shù)非線性程序，并提出一種工作流任務(wù)卸載方案，有效減少了任務(wù)的執(zhí)行時(shí)間。

容錯(cuò)策略能夠增強(qiáng)工作流運(yùn)行的穩(wěn)定性，減少因任務(wù)失敗帶來的損失，從而提高工作流執(zhí)行效率，經(jīng)典的工作流容錯(cuò)策略主要包括任務(wù)復(fù)制[11-12]、重提交[13]和檢查點(diǎn)[14]等。ZHAO等[11]提出了根據(jù)任務(wù)特性制定不同數(shù)量的副本任務(wù)個(gè)數(shù)的容錯(cuò)算法，在利用任務(wù)復(fù)制策略保證系統(tǒng)可靠性的同時(shí)降低了系統(tǒng)冗余程度。VINAY等[12]提出了一種啟發(fā)式的基于異構(gòu)最早完成時(shí)間(Cluster based Heterogeneous Earliest Finish Time, C-HEFT)算法，其通過使用配置資源的空閑時(shí)間重新提交失敗的任務(wù)，減少了任務(wù)的失敗率從而保證了工作流的成功執(zhí)行。WANG等[13]提出一種基于復(fù)制策略的最大化系統(tǒng)可靠性調(diào)度(Replication-based scheduling for Maximizing System Reliability, RMSR)算法，該算法通過任務(wù)的動(dòng)態(tài)副本機(jī)制，大幅減少了復(fù)制機(jī)制引起的額外通信量。NIRMALA等[14]使用輕量級同步檢查點(diǎn)重新提交失敗的任務(wù)，確保任務(wù)在不穩(wěn)定的環(huán)境中能夠成功執(zhí)行。ABDELFATTAH等[15]提出一種任務(wù)復(fù)制策略和重提交策略相結(jié)合的混合容錯(cuò)模型，一旦故障發(fā)生到最高可靠性處理節(jié)點(diǎn)，將重新計(jì)劃任務(wù)，確保任務(wù)的正確執(zhí)行。LEE等[16]提出了考慮檢查點(diǎn)和復(fù)制機(jī)制相結(jié)合的容錯(cuò)調(diào)度算法，提高了準(zhǔn)確性，減少了資源消耗并降低了任務(wù)的平均執(zhí)行時(shí)間。

2 系統(tǒng)模型

本章主要介紹MEC環(huán)境下服務(wù)工作流容錯(cuò)調(diào)度模型、工作流模型、可靠性模型以及調(diào)度目標(biāo)，其中工作流容錯(cuò)調(diào)度模型為整體的結(jié)構(gòu)模型，工作流模型、可靠性模型為工作流容錯(cuò)調(diào)度模型的組成部分，描述了所研究的工作流的結(jié)構(gòu)和調(diào)度過程中任務(wù)執(zhí)行出錯(cuò)的可能性，具體模型描述如下。

2.1 MEC環(huán)境下服務(wù)工作流容錯(cuò)調(diào)度模型

MEC環(huán)境下服務(wù)工作流容錯(cuò)調(diào)度模型如圖1所示。系統(tǒng)首先對用戶提交的服務(wù)工作流進(jìn)行建模并分層生成就緒任務(wù)隊(duì)列，然后將其提交至用戶設(shè)備(User Equipment，UE)端的任務(wù)調(diào)度器進(jìn)行編碼，并利用容錯(cuò)免疫粒子群優(yōu)化調(diào)度算法確定各個(gè)任務(wù)所采用的容錯(cuò)方案調(diào)度尋優(yōu)，輸出調(diào)度結(jié)果，將其交給UE端任務(wù)管理器，根據(jù)所得調(diào)度方案對任務(wù)進(jìn)行分配，根據(jù)任務(wù)執(zhí)行情況進(jìn)行動(dòng)態(tài)資源調(diào)整，最后得到最優(yōu)調(diào)度方案下的服務(wù)工作流執(zhí)行結(jié)果。

2.2 工作流模型

在MEC中，服務(wù)工作流以有向無環(huán)圖集DAGs表示：W={w1,w2,…,wN}。其中：N為工作流數(shù)。wi={(V,E),RD}(i=1,2，…,n)表示其中一條工作流，V={ti,0,ti,1,…,ti,n}為任務(wù)集合;ti,j代表第i個(gè)服務(wù)工作流中的第j個(gè)任務(wù);RD為服務(wù)工作流可靠性需求;E={(ti,m,ti,n,tdi,m,n)|ti,m,ti,n∈V}為任務(wù)之間的邊集，描述任務(wù)之間的依賴關(guān)系，ti,m為ti,n的前驅(qū)任務(wù)，tdi,m,n為ti,m向ti,n傳輸?shù)臄?shù)據(jù)集。任務(wù)的前驅(qū)和后繼任務(wù)集定義如下：

定義1前驅(qū)和后繼任務(wù)集。ti,j所有的前驅(qū)任務(wù)集為其所有前驅(qū)任務(wù)組成的集合：pred(ti,j)={ti,k|(ti,k,ti,j,tdi,k,j)∈E}，后繼任務(wù)集為：succ(ti,j)={ti,m|(ti,j,ti,m,tdi,j,m)∈E}。

每個(gè)任務(wù)都有自身的屬性：ti,j={di,j，ci,j,oi,j},di,j、ci,j和oi,j分別表示輸入數(shù)據(jù)大小、完成該任務(wù)需求計(jì)算資源和輸出數(shù)據(jù)大小。如圖2所示為一個(gè)移動(dòng)邊緣環(huán)境下健康應(yīng)用程序的工作流實(shí)例圖，選取了工作流中有依賴關(guān)系的兩個(gè)任務(wù)節(jié)點(diǎn)，并列出了詳細(xì)的配置信息。節(jié)點(diǎn)ti,j從文件中讀取數(shù)據(jù)，在獲取體重?cái)?shù)據(jù)之后將結(jié)果寫至相應(yīng)文件，節(jié)點(diǎn)ti,k從多個(gè)輸入文件中讀取數(shù)據(jù)并計(jì)算健康狀況，將結(jié)果寫至結(jié)果文件。

本文主要考慮單出入口節(jié)點(diǎn)的服務(wù)工作流，并將服務(wù)工作流任務(wù)按層進(jìn)行劃分，任務(wù)的深度計(jì)算公式如下：

(1)

其中DP(ti,j)為任務(wù)深度，若ti,j為入口任務(wù)，則其深度為0。

2.3 可靠性模型

在MEC環(huán)境中，任務(wù)在n號資源節(jié)點(diǎn)上執(zhí)行的失敗概率

(2)

其中：λ為故障系數(shù)，RDi為第i條工作流wi的可靠性需求，TLn為編號為n的資源節(jié)點(diǎn)的可信度。

2.4 調(diào)度目標(biāo)

本文以最小化延時(shí)為目標(biāo)調(diào)度服務(wù)工作流，若系統(tǒng)中有n個(gè)服務(wù)工作流，則服務(wù)工作流平均延時(shí)

(3)

式中makespan(wi)表示服務(wù)工作流wi的完工時(shí)間，

makespan(wi)=max{lft(wi,M)}-lft(wi,0)。

(4)

式中：max{lft(wi,M)}為最大層任務(wù)結(jié)束時(shí)間，lft(wi,0)為服務(wù)工作流首個(gè)任務(wù)的到達(dá)時(shí)間。式(3)給出了未考慮容錯(cuò)的調(diào)度目標(biāo)，但是在實(shí)際中會有任務(wù)執(zhí)行失敗的情況發(fā)生，第3章將結(jié)合可靠性模型詳細(xì)介紹任務(wù)容錯(cuò)方法。

3 容錯(cuò)免疫粒子群優(yōu)化調(diào)度算法

在移動(dòng)邊緣環(huán)境下的多服務(wù)工作流調(diào)度中，本文提出的FT-IPSO算法以粒子群算法[17-18]為基礎(chǔ)算法，在粒子群算法中加入工作流調(diào)度問題，利用免疫算法的免疫操作保證工作流調(diào)度方案的全局性，并加入容錯(cuò)策略保證工作流執(zhí)行的魯棒性。本章主要從容錯(cuò)策略、粒子編碼設(shè)計(jì)、粒子適應(yīng)度函數(shù)、算法流程方面對FT-IPSO算法進(jìn)行介紹，并分析算法的復(fù)雜度。移動(dòng)邊緣環(huán)境下服務(wù)工作流調(diào)度算法定義如下：

定義2映射關(guān)系。在移動(dòng)邊緣環(huán)境中，任務(wù)和資源節(jié)點(diǎn)之間的分配關(guān)系映射為整數(shù)，如Xi,j=5表示將Xi,j分配至5號資源節(jié)點(diǎn)。其中Xi,j∈[0,n+0.5]，i∈[1,m],j∈[1,2n]，n為資源節(jié)點(diǎn)數(shù)目，i表示種群編號，j表示相應(yīng)的任務(wù)的分配節(jié)點(diǎn)，Xi,j取值為小數(shù)時(shí)，則取整數(shù)部分作為任務(wù)調(diào)度節(jié)點(diǎn)位置。

3.1 容錯(cuò)策略

本文結(jié)合任務(wù)復(fù)制和重提交策略，設(shè)計(jì)了一種混合容錯(cuò)策略，主要包含兩個(gè)版本任務(wù)，分別為主本任務(wù)和副本任務(wù)，副本任務(wù)的容錯(cuò)方式根據(jù)下式確定：

(5)

dl(ti,j)=TDP(m)+lft(wi,m),DP(ti,j)=m。

(6)

式中：DP(ti,j)為任務(wù)ti,j所在層的深度;TDP(m)和lft(wi,m)分別為每層可分配期限和工作流中第m層的運(yùn)行結(jié)束時(shí)間，每層可分配期限

TDP(m)=(dl(wi)-lft(wi,0))×

(7)

層結(jié)束時(shí)間由該層中最遲結(jié)束的任務(wù)確定，若服務(wù)工作流的最大深度為M，則層結(jié)束時(shí)間計(jì)算方法如式(8)所示：

lft(wi,m)=

(8)

其中：at(wi)為工作流wi到達(dá)時(shí)間，st(ti,j)為任務(wù)ti,j的開始時(shí)間，Te(ti,j)為任務(wù)ti,j的執(zhí)行時(shí)間。

3.2 粒子編碼設(shè)計(jì)

粒子編碼方案如圖3所示，在使用容錯(cuò)免疫粒子群優(yōu)化調(diào)度算法實(shí)現(xiàn)多服務(wù)工作流調(diào)度時(shí)，需考慮任務(wù)的執(zhí)行順序并分配卸載位置。任務(wù)的執(zhí)行順序由就緒隊(duì)列給定，編碼中相鄰兩個(gè)位置為某個(gè)任務(wù)不同卸載位置，以整數(shù)表示。若編碼值為小數(shù)，則取整，當(dāng)任務(wù)卸載位置為0時(shí)，其將在本地執(zhí)行，否則任務(wù)將被卸載至相應(yīng)編號的邊緣服務(wù)器中執(zhí)行。

3.3 粒子適應(yīng)度函數(shù)

根據(jù)容錯(cuò)調(diào)度策略，若任務(wù)在某個(gè)資源節(jié)點(diǎn)執(zhí)行成功，則副本任務(wù)或重提交任務(wù)將不會執(zhí)行；若主本任務(wù)執(zhí)行失敗，則副本任務(wù)在不同資源節(jié)點(diǎn)中繼續(xù)執(zhí)行。因此，任務(wù)的期望時(shí)間E(ts)為：

Pkeep(ftj)×(ftj+1-ftj);

(9)

(10)

其中：Pkeep(sts)和Pkeep(fts)分別為任務(wù)在時(shí)間點(diǎn)sts和fts之后繼續(xù)執(zhí)行的概率，sts和fti分別表示在第s次執(zhí)行的開始時(shí)間和第i次執(zhí)行的結(jié)束時(shí)間，粒子適應(yīng)度

fit(Xi)=E(Xi)+α·Pfail(Xi)。

(11)

式中：E(Xi)為粒子Xi的期望調(diào)度時(shí)間，α為對于任務(wù)失敗率的懲罰系數(shù)，Pfail(Xi)為粒子Xi調(diào)度的整體失敗率。

3.4 FT-IPSO算法流程

如圖4所示為FT-IPSO算法的流程，主要包括以下步驟：首先，利用隨機(jī)數(shù)和得到的就緒隊(duì)列根據(jù)編碼策略初始化粒子群;然后,計(jì)算服務(wù)工作流子期限，確定任務(wù)使用的容錯(cuò)策略，并采用免疫操作避免粒子在迭代過程中陷入局部最優(yōu)解，保證尋優(yōu)的全局性；最后，利用更新公式更新粒子群，通過種群迭代尋找最優(yōu)調(diào)度方案。若粒子調(diào)度序列的適應(yīng)度值不再更新，則認(rèn)為當(dāng)前調(diào)度方案最優(yōu)，并輸出最優(yōu)調(diào)度方案。

3.4.1 工作流分層排序

本文使用HEFT算法對初始工作流進(jìn)行加工并生成就緒隊(duì)列，該算法首先計(jì)算每個(gè)任務(wù)深度并分層，然后對任務(wù)權(quán)重進(jìn)行計(jì)算，最后對每一層的任務(wù)按照權(quán)重值大小進(jìn)行升序排序合并，任務(wù)權(quán)重計(jì)算方法如下：

(12)

rank(ti,j)=ci,j/Pref。

(13)

3.4.2 工作流中粒子群容錯(cuò)方法選取

本文提出一種任務(wù)復(fù)制和重提交相結(jié)合的容錯(cuò)策略，首先對主本任務(wù)和副本任務(wù)的執(zhí)行時(shí)間和相應(yīng)的數(shù)據(jù)傳輸時(shí)間進(jìn)行計(jì)算，再利用所得結(jié)果根據(jù)

式(5)確定工作流任務(wù)所采用的容錯(cuò)方式。若滿足公式，則將任務(wù)的容錯(cuò)方法設(shè)置為重提交，副本任務(wù)將在主本任務(wù)失敗后重提交至不同服務(wù)器中執(zhí)行；否則使用主動(dòng)任務(wù)復(fù)制策略，主副版本任務(wù)將會一同提交至不同服務(wù)器執(zhí)行，工作流任務(wù)容錯(cuò)方法選取如算法1所示。

算法1工作流任務(wù)容錯(cuò)方法選取算法。

輸入：任務(wù)子期限矩陣dead_t，開始時(shí)間矩陣strat_t，eNB性能集合P_eNB，

任務(wù)位置矩陣X；

輸出：任務(wù)容錯(cuò)方案矩陣FT。

1. for i=0 to m+s do /*種群遍歷*/

2. for j=0 to 2n-1 do/*個(gè)體循環(huán)*/

3. Comp_time_p=c[i][j]/P_eNB(x[i][j])/*主本任務(wù)在所調(diào)度基站中的執(zhí)行時(shí)間*/

4. Comp_time_b=c[i][j]/P_eNB(x[i][j+1])/*副本任務(wù)在所調(diào)度基站中的執(zhí)行時(shí)間*/

5. Calculate tr_prime and tr_back /*計(jì)算在主副版本任務(wù)所調(diào)度基站的數(shù)據(jù)傳輸時(shí)間*/

6. if dead_t-strat_t>Comp_time_p+Comp_time_b+max(tr_prime,tr_back)

7. ft[i][j]=0/*用0表示重提交策略*/

8. else

9. ft[i][j]=1/*用1表示任務(wù)復(fù)制策略*/

10. end if

11. end for

12.end for

3.4.3 粒子群算法免疫操作

(14)

(15)

(16)

3.4.4 工作流任務(wù)調(diào)度序列信息更新方法

任務(wù)的調(diào)度位置和粒子速度更新公式如下：

(17)

3.5 算法復(fù)雜度分析

在FT-IPSO算法中，給定粒子群種群規(guī)模為s，每次隨機(jī)生成的抗體數(shù)量為m，同時(shí)給定n個(gè)服務(wù)工作流任務(wù)，則算法所占用的空間為：存儲任務(wù)調(diào)度位置和粒子適應(yīng)度值所占用的空間(s+m)×(2n+1)，粒子速度矩陣所占用的空間s×2n，以及其他變量和常量所需空間C，故空間復(fù)雜度為：S(n)=O(s×4n+m×2n+C)。在迭代過程共有s個(gè)粒子執(zhí)行尋優(yōu)工作且需要進(jìn)行maxG次迭代找到最優(yōu)工作流調(diào)度方案，故算法的時(shí)間復(fù)雜度為：T(n)=O(s×4n×maxG+C)。

4 仿真實(shí)驗(yàn)

為分析和評估FT-IPSO算法性能，本文進(jìn)行了大量實(shí)驗(yàn)：首先，對不同條件下的FT-IPSO算法表現(xiàn)進(jìn)行了實(shí)驗(yàn)，然后，為探究FT-IPSO算法與其他算法之間的性能差異，分別選取了C-HEFT算法[12]、基于聚類啟發(fā)式算法的檢查點(diǎn)和復(fù)制(Checkpointing and Replication based on Clustering Heuristics, CRCH)算法[14]和加入混合容錯(cuò)策略的反應(yīng)式容錯(cuò)(Reactive Fault Tolerance Approach, RFTA)算法[15]作為比較對象。

4.1 實(shí)驗(yàn)環(huán)境與實(shí)驗(yàn)參數(shù)

本文使用EdgeCloudSim[20]模擬MEC環(huán)境，隨機(jī)生成服務(wù)工作流任務(wù)，其中服務(wù)工作流[21]任務(wù)的計(jì)算量服從[1,10]的均勻分布(單位：GHz)，任務(wù)輸出數(shù)據(jù)的大小服從[1,10]的均勻分布(單位：Mb)，每個(gè)服務(wù)工作流包含的任務(wù)節(jié)點(diǎn)數(shù)為10～100個(gè)。另外，eNB個(gè)數(shù)為10個(gè)，工作可靠性需求(RD):0.6～0.9，服務(wù)器可信性等級(TL)：0.4～1.0，式(2)故障系數(shù)λ=2.7。移動(dòng)端的計(jì)算能力為1.2 GHz，上傳和下載速率分別為5 Mb/s和10 Mb/s；邊緣服務(wù)器的計(jì)算能力為4 GHz，傳輸速率為100 Mb/s。參考文獻(xiàn)[22]中的參數(shù)設(shè)置，本文實(shí)驗(yàn)中邊緣環(huán)境中粒子群參數(shù)設(shè)置為：粒子速度Vmax=0.6；最大迭代次數(shù)maxG=500；粒子群種群數(shù)s=50；每次循環(huán)新增抗體數(shù)量m=20；慣性權(quán)重w0=0.73；學(xué)習(xí)參數(shù)c1=c2=1.496 18；適應(yīng)度函數(shù)中γ=10。本文實(shí)驗(yàn)平臺如下：Inter(R)Core(TM)i7-8700K處理器；32 GB內(nèi)存；Windows 10專業(yè)版64位操作系統(tǒng)。

4.2 不同條件下FT-IPSO算法表現(xiàn)

為探究FT-IPSO算法在不同條件下的表現(xiàn)，改變eNB個(gè)數(shù)和工作流任務(wù)到達(dá)率，對不同的工作流進(jìn)行實(shí)驗(yàn)并取平均值。在粒子群種群數(shù)為50、最大迭代次數(shù)為500和重復(fù)實(shí)驗(yàn)次數(shù)為10的條件下對算法進(jìn)行實(shí)驗(yàn)，得到的結(jié)果如圖5和圖6所示。

由圖5可以看出，當(dāng)eNB數(shù)量增多時(shí)，任務(wù)延時(shí)逐漸降低，其原因在于邊緣服務(wù)器和移動(dòng)設(shè)備的性能差異較大，當(dāng)FT-IPSO算法將計(jì)算需求較大的任務(wù)卸載至eNB中并行執(zhí)行，能夠縮短任務(wù)執(zhí)行時(shí)間，工作流的平均延時(shí)大幅降低。但是由于工作流中最大可并行任務(wù)數(shù)量存在上限，當(dāng)eNB數(shù)量超過一定值時(shí)，任務(wù)延時(shí)下降幅度減小。圖6顯示了在eNB數(shù)量為10的情況下，不同工作流到達(dá)率的任務(wù)平均延時(shí)的影響。FT-IPSO算法將部分計(jì)算量小但數(shù)據(jù)傳輸量大的任務(wù)保留至本地執(zhí)行，將計(jì)算量大的任務(wù)調(diào)度至邊緣服務(wù)器，減少任務(wù)執(zhí)行時(shí)間，從而降低了任務(wù)的平均延時(shí)。此外，本文統(tǒng)計(jì)了FT-IPSO算法在工作流數(shù)量為50的情況下，不同eNB的可信度值下任務(wù)失敗率變化情況，其中任務(wù)失敗率為主本任務(wù)執(zhí)行失敗的任務(wù)個(gè)數(shù)占總?cè)蝿?wù)數(shù)的百分比，實(shí)驗(yàn)結(jié)果如表1所示。

表1 不同eNB的可信度值下任務(wù)失敗率變化情況

續(xù)表1

由表1可知，當(dāng)資源節(jié)點(diǎn)可信度一定時(shí)，任務(wù)可靠性需求越高，任務(wù)失敗率越高；當(dāng)任務(wù)可靠性需求不變，資源節(jié)點(diǎn)可信度逐漸增加時(shí)，任務(wù)失敗率下降。

4.3 相同條件下不同算法對比實(shí)驗(yàn)

4.3.1 與C-HEFT算法對比

為驗(yàn)證FT-IPSO算法在求解服務(wù)工作流調(diào)度問題上的有效性，將FT-IPSO算法與C-HEFT算法和FT-IPSO算法進(jìn)行比較。在相同環(huán)境下，將FT-IPSO算法的種群數(shù)設(shè)置為50，最大迭代次數(shù)為500次，其他實(shí)驗(yàn)參數(shù)與C-HEFT算法保持一致，采用相同的初始解生成方式，對16個(gè)服務(wù)工作流實(shí)例進(jìn)行對比實(shí)驗(yàn)，兩種算法求解的調(diào)度方案適應(yīng)度值結(jié)果如表2所示。

表2 FT-IPSO算法與C-HEFT算法解的適應(yīng)度值對比

由表2可知，與C-HEFT算法相比，本文所設(shè)計(jì)的FT-IPSO算法在16個(gè)工作流實(shí)例實(shí)驗(yàn)中均得到了兩種算法的中的最優(yōu)解，且解的提升幅度較大。在算法的標(biāo)準(zhǔn)方差上，由于FT-IPSO算法中引入了免疫算法，保證了解的全局最優(yōu)性，解的波動(dòng)性較小，因此，從解的質(zhì)量上可以看出，F(xiàn)T-IPSO算法具有較強(qiáng)的競爭力。

4.3.2 不同算法性能對比

為進(jìn)一步驗(yàn)證FT-IPSO算法在求解多服務(wù)工作流調(diào)度問題中的有效性，分別選取不同算法作為對比實(shí)驗(yàn)，并設(shè)置任務(wù)首次執(zhí)行失敗率、任務(wù)平均延時(shí)作為性能指標(biāo)，在相同的實(shí)驗(yàn)條件下，記錄不同算法的各項(xiàng)實(shí)驗(yàn)數(shù)據(jù)，并對其進(jìn)行分析，實(shí)驗(yàn)結(jié)果如圖7和圖8所示。

由圖7和圖8可知，F(xiàn)T-IPSO算法相對于CRCH算法、C-HEFT算法和RFTA算法擁有較小的工作流延時(shí)和較低的任務(wù)失敗率，其原因在于本文提出的FT-IPSO算法對容錯(cuò)策略進(jìn)行了優(yōu)化，利用任務(wù)復(fù)制和重提交相結(jié)合的容錯(cuò)策略降低了系統(tǒng)的冗余程度以及任務(wù)失敗率，一方面減少了系統(tǒng)因任務(wù)失敗導(dǎo)致的額外任務(wù)調(diào)度和執(zhí)行時(shí)間開銷，并且有部分任務(wù)采用重提交策略時(shí)，其主本任務(wù)執(zhí)行成功之后副本任務(wù)不需要再次執(zhí)行，節(jié)約了系統(tǒng)資源，從而降低了工作流延時(shí);另一方面通過改進(jìn)的免疫粒子群算法尋找最優(yōu)調(diào)度方案，提高了解的全局性，確保最終方案為使任務(wù)調(diào)度延時(shí)最低的調(diào)度方案。因此，F(xiàn)T-IPSO算法在求解多服務(wù)工作流調(diào)度問題時(shí)具有高效性，且解的質(zhì)量更優(yōu)，在延時(shí)上相對于使用混合容錯(cuò)策略的RFTA算法縮短了約4.1%，較CRCH算法和C-HEFT算法分別縮短了約6.3%和9.1%。

5 結(jié)束語

MEC中服務(wù)工作流調(diào)度是邊緣計(jì)算研究中的一個(gè)重要內(nèi)容。本文改進(jìn)了粒子群算法，并將其與服務(wù)工作流調(diào)度問題相結(jié)合，提出了FT-IPSO算法，改進(jìn)包括：利用HEFT算法對分層合并后的任務(wù)計(jì)算權(quán)重并生成就緒隊(duì)列，保證了調(diào)度公平性；在粒子群算法中算法融入免疫算法，解決了粒子易陷入局部最優(yōu)的缺陷，確保解的全局性；加入了一種任務(wù)復(fù)制和重提交策略相結(jié)合的容錯(cuò)算法，提高了工作流執(zhí)行的穩(wěn)定性。仿真實(shí)驗(yàn)結(jié)果表明，使用FT-IPSO算法能夠有效減少服務(wù)工作流延時(shí)，且其相對于CRCH算法和C-HEFT算法所占用的系統(tǒng)資源更少；在確定任務(wù)容錯(cuò)策略時(shí)，考慮了任務(wù)子期限，較RFTA算法更好地制定了任務(wù)所應(yīng)采用的容錯(cuò)方法，減少了任務(wù)錯(cuò)誤率，延時(shí)的優(yōu)化效果更優(yōu)。在未來工作中，期望能夠進(jìn)一步改進(jìn)算法，在算法中引入多服務(wù)工作流的費(fèi)用模型和移動(dòng)設(shè)備能耗模型，并對已知服務(wù)工作流歷史到達(dá)情況的調(diào)度問題進(jìn)行研究。