高一鳴,袁友偉,2,錢 逯

(1.杭州電子科技大學(xué)計算機(jī)學(xué)院,浙江 杭州 310018;2.浙江省腦機(jī)協(xié)同智能重點(diǎn)實(shí)驗室,浙江 杭州 310018)

0 引 言

隨著無線網(wǎng)絡(luò)和物聯(lián)網(wǎng)技術(shù)的快速發(fā)展,移動用戶設(shè)備在網(wǎng)絡(luò)邊緣產(chǎn)生的數(shù)據(jù)量迅速增長,以云計算模型為核心的服務(wù)器端架構(gòu)已無法滿足當(dāng)前網(wǎng)絡(luò)環(huán)境對延遲、能耗等需求。移動邊緣計算(Mobile Edge Computing, MEC)[1]是一種新的計算范式,通過建立一個在接近物理實(shí)體或服務(wù)源處提供服務(wù)的集成平臺,使應(yīng)用程序在邊緣執(zhí)行運(yùn)算,以提高網(wǎng)絡(luò)服務(wù)的響應(yīng)速度[2-3]。在MEC環(huán)境中,邊緣服務(wù)器節(jié)點(diǎn)可視作額外計算資源,移動設(shè)備將高計算需求任務(wù)傳輸至邊緣服務(wù)器的過程稱為計算卸載[4]。計算卸載將任務(wù)卸載至具有更高計算能力的邊緣節(jié)點(diǎn)上,降低了任務(wù)的執(zhí)行延時與設(shè)備能耗,彌補(bǔ)了移動設(shè)備本地計算能力不足的缺陷。但是,隨著移動設(shè)備的增多和無線網(wǎng)絡(luò)的日益復(fù)雜,現(xiàn)有的任務(wù)調(diào)度技術(shù)已無法滿足調(diào)度的需求,不合理的調(diào)度方式往往造成更大的任務(wù)延時和傳輸能耗。改進(jìn)的非支配排序遺傳算法(Non-dominated Sorting Genetic Algorithm Ⅱ,NSGA Ⅱ)[5]是一種利用非支配排序?qū)ΨN群進(jìn)行分級,通過計算種群個體間的擁擠距離得到近似解的算法。本文針對邊緣用戶的工作流信息、服務(wù)器可靠性、用戶計算時延等信息進(jìn)行建模,運(yùn)用NSGA-Ⅱ算法生成最優(yōu)的調(diào)度方案,提出一種基于可靠性約束的工作流調(diào)度(Workflow Scheduling)算法NSGA-Ⅱ-WS,在可靠性約束下,最小化工作流執(zhí)行時延及能耗。

1 移動邊緣計算系統(tǒng)模型

移動邊緣計算系統(tǒng)模型主要包括工作流模型、可靠性模型、時間模型和能耗模型。

1.1 工作流模型

在移動邊緣計算環(huán)境中,需要定義工作流和計算環(huán)境。用有向無環(huán)圖表示工作流,工作流任務(wù)定義為w={V,E,wRD}。其中,V={t0,t1,…,tn}為任務(wù)集合,ti為工作流中的第i個任務(wù);E={(tm,tn,tdm,n)|tm,tn∈V}為任務(wù)之間的邊集,表示任務(wù)之間的依賴關(guān)系,tm為tn的前驅(qū)任務(wù),tdm,n表示tm向tn傳輸數(shù)據(jù)集;wRD為該工作流的可靠性需求(Reliability Demand,RD)系數(shù)。工作流子任務(wù)的可靠性需求系數(shù)為tiRD,tiRD越大,任務(wù)ti的可靠性需求越高。φ(ti)={tk|(tk,ti,tk,i)∈E}為ti的所有前驅(qū)任務(wù)集合,φ(ti)={tk|(ti,tk,ti,k)∈E}為ti的后繼任務(wù)集合。每個任務(wù)有3個屬性ti={di,ci,oi},di,ci和oi分別表示輸入數(shù)據(jù)、計算量和輸出數(shù)據(jù)。此外,當(dāng)前設(shè)備為1臺本地服務(wù)器時,編號為0,MEC環(huán)境中可用邊緣服務(wù)器數(shù)量為m,則可用服務(wù)器列表集合為S={s0,…,si…,sm}。

1.2 可靠性模型

移動邊緣計算系統(tǒng)中,故障包含瞬時故障與永久故障。瞬時故障出現(xiàn)時間短且不會損害處理器,因此,本文僅將瞬時故障和可靠性結(jié)合在一起。一般來說,系統(tǒng)故障發(fā)生在設(shè)備通信與任務(wù)執(zhí)行上,通信時間往往小于設(shè)備執(zhí)行時間,因此,本文設(shè)計模型時,僅考慮處理器故障,不將通信故障納入優(yōu)化問題。在工作流應(yīng)用中,任務(wù)在服務(wù)器上的執(zhí)行可靠性通常與任務(wù)的執(zhí)行時間和服務(wù)器的故障率有關(guān),且任務(wù)的瞬態(tài)故障遵循泊松分布[6]。設(shè)λj為服務(wù)器sj的處理器每單元時間的恒定故障率,在時間間隔(0,τ]內(nèi),任務(wù)ti在服務(wù)器sj上執(zhí)行的可靠性為:

R(ti,sj)=e-λjτ

(1)

用戶設(shè)備可視為1個本地服務(wù)器,編號為0,當(dāng)任務(wù)在本地設(shè)備上發(fā)生故障時,立即進(jìn)行任務(wù)重啟。若工作流w中的每個任務(wù)ti的調(diào)度位置已知,則工作流w的執(zhí)行可靠性為:

(2)

式中,s(ti)為任務(wù)ti的執(zhí)行位置。通過遍歷服務(wù)器得到工作流w的最小可靠性值Rmin(w)和最大可靠性值Rmax(w)。對于R(w),勢必存在約束0≤Rmin(w)≤R(w)≤Rmax(w)≤1,否則,執(zhí)行方案不能滿足工作流可靠性需求。當(dāng)任務(wù)調(diào)度時,移動設(shè)備通過任務(wù)復(fù)制機(jī)制確保服務(wù)器故障時任務(wù)能夠重新開始執(zhí)行。

1.3 時間模型

在工作流調(diào)度過程中,任務(wù)完成時間包括任務(wù)的傳輸時間與執(zhí)行時間。當(dāng)用戶設(shè)備選擇將任務(wù)進(jìn)行卸載時,μ時刻時,設(shè)備i向設(shè)備j數(shù)據(jù)傳輸速率trans(i,j)表示為:

(3)

任務(wù)ti向服務(wù)器sj的傳輸時間為:

(4)

任務(wù)的執(zhí)行時間與邊緣節(jié)點(diǎn)性能和任務(wù)工作量有關(guān),該任務(wù)的執(zhí)行時間為:

(5)

式中,fj,k(ti)為服務(wù)器sj為ti提供的計算頻率。

工作流w中的所有任務(wù)均完成,w才算完成。令l表示sj緩沖隊列中的任務(wù)數(shù),則工作流w的時延為:

(6)

1.4 能耗模型

在邊緣計算環(huán)境中進(jìn)行任務(wù)調(diào)度時,必然要考慮用戶設(shè)備的能耗問題。用戶設(shè)備的能耗主要包括本地執(zhí)行任務(wù)產(chǎn)生的能耗和向其他邊緣服務(wù)器傳輸數(shù)據(jù)產(chǎn)生的能耗。

對于工作流w,設(shè)本地設(shè)備計算功率為Pc,則本地執(zhí)行能耗為:

(7)

式中,O為本地執(zhí)行的任務(wù)集合。

設(shè)本地設(shè)備傳輸功率為Pt,工作流w通信產(chǎn)生的傳輸能耗為:

(8)

則設(shè)備總能耗為:

E=Eex(w)+Etrs(w)

(9)

2 基于可靠性約束的工作流調(diào)度算法

在改進(jìn)NSGA-Ⅱ算法基礎(chǔ)上,本文提出一種基于可靠性約束的工作流調(diào)度算法NSGA-Ⅱ-WS,在滿足可靠性約束條件下,最小化設(shè)備的能耗和響應(yīng)時間。

對于工作流w及其所有子任務(wù)V={t0,t1,…,tn},各任務(wù)可靠性需求系數(shù)tiRD∈[0,1],工作流可靠性需滿足最低值,令{t0,t1,…,tj-1}表示已分配至滿足可靠性約束的服務(wù)器或本地服務(wù)器的任務(wù)集合,{tj,tj+1,…,tn}表示未分配集合,Rgoal(w)表示工作流w的可靠性需求。當(dāng)分配任務(wù)tj時,存在服務(wù)器滿足條件Rj(w)≥Rgoal(w)。

定理對于工作流w中的每個任務(wù)tj,總能找到1個合適的服務(wù)器,且滿足以下條件:

(10)

證明采用數(shù)學(xué)歸納法證明。在分配入口任務(wù)t0時,所有任務(wù)都未分配任務(wù)調(diào)度位置,應(yīng)用程序w需要滿足如下可靠性目標(biāo):

(11)

假設(shè)任務(wù)tj已經(jīng)找到滿足可靠性目標(biāo)的可用服務(wù)器,則有:

(12)

同理,對于任務(wù)tj+1,其工作流執(zhí)行可靠性為:

(13)

將式(13)代入式(12),可得:

(14)

所以,至少存在1個MEC服務(wù)器或者本地服務(wù)器滿足Rgoal(w),即:

Rj+1(w)≥Rgoal(w)

(15)

對于工作流w中的每個任務(wù)tj總能找到1個合適的服務(wù)器來滿足Rj(w)≥Rgoal(w)。證畢。

由定理可知,必定存在調(diào)度方案使得每個任務(wù)都能找到滿足可靠性約束的服務(wù)器,再運(yùn)用NSGA-Ⅱ-WS算法搜索滿足可靠性約束條件下最優(yōu)的工作流調(diào)度解。NSGA-Ⅱ-WS算法流程如圖1所示。根據(jù)工作流信息初始化種群,采用選擇、交叉、變異對種群進(jìn)行更新,并運(yùn)用精英策略篩選出種群中優(yōu)秀個體,經(jīng)過不斷迭代得到最優(yōu)種群。任務(wù)調(diào)度過程中若出現(xiàn)服務(wù)器故障,則重新執(zhí)行NSGA-Ⅱ-WS算法。

圖1 NSGA-Ⅱ-WS算法執(zhí)行流程示意圖

將任務(wù)編號與服務(wù)器編號視為對應(yīng)關(guān)系,每1條染色體代表1種MEC環(huán)境下工作流調(diào)度方案。假設(shè)存在工作流w,其子任務(wù)個數(shù)為n,移動邊緣環(huán)境中服務(wù)器個數(shù)為m。染色體表示1個一維矩陣X,代表移動邊緣計算環(huán)境下服務(wù)工作流調(diào)度問題的1個可行解,且染色體中的每個基因位都是正整數(shù),X=[x0x1x2…xn],其中xi表示第i個任務(wù)的分配位置。

在正式初始化之前需要根據(jù)工作流子任務(wù)的優(yōu)先級進(jìn)行排序。使用隨機(jī)法初始化任務(wù)調(diào)度位置與任務(wù)執(zhí)行順序,在[0,m]范圍中生成1個隨機(jī)數(shù)ri,若ri非整數(shù),則對ri進(jìn)行向下取整,將ri作為任務(wù)i所卸載的設(shè)備編號,生成相應(yīng)的工作流調(diào)度方案,最終使用貪心策略生成初始化種群Pk={X1,X2,X3,…,XN},保證工作流調(diào)度方案的可靠性需求。

本文主要在移動邊緣環(huán)境下實(shí)現(xiàn)一種基于可靠性約束的工作流調(diào)度算法,在滿足可靠性約束的同時實(shí)現(xiàn)能耗和時延最小化。對于工作流w,優(yōu)化目標(biāo)函數(shù)表示為:

minαE+(1-α)T
s.t.T=T(w)
E=Eex(w)+Etrs(w)
00<α<1

(16)

式中,E為設(shè)備能耗,α為權(quán)重因子,T為工作流時延。優(yōu)化目標(biāo)函數(shù)在本模型中也被視為系統(tǒng)成本。選取該任務(wù)調(diào)度目標(biāo)作為適應(yīng)度評價指標(biāo),通過計算調(diào)度方案的適應(yīng)度,評估調(diào)度方案的可靠性、時延與能耗,適應(yīng)度值越小表示方案越優(yōu)。該問題是一個NP-hard問題,需要在滿足可靠性約束同時實(shí)現(xiàn)能耗和時延最小化。

本文提出的NSGA-Ⅱ-WS算法具體執(zhí)行步驟如下。

(2)交叉操作是算法優(yōu)劣的關(guān)鍵。單點(diǎn)交叉算子選擇位置效率較低,不能有效搜索解空間,故本文提出混合交叉算子。在單點(diǎn)交叉算子的基礎(chǔ)上,隨機(jī)在父代個體上選取q個不連續(xù)基因,對另一個交叉?zhèn)€體同位置基因進(jìn)行交換,然后得到子代個體。基因的不連續(xù)性使父代與子代的差異性更大,從而擴(kuò)大了解空間。

(3)變異操作擴(kuò)大了工作流調(diào)度解的采樣空間,增加了算法的搜索能力,避免工作流的解陷入局部最優(yōu)。設(shè)置初始變異概率值為θ0,最大變化概率為ρ,最大迭代次數(shù)為ψ,當(dāng)前迭代次數(shù)為k,變異概率計算公式為:

(17)

計算θN后,判斷是否需要變異。若需要變異操作,則從種群中隨機(jī)選取個體,對個體中的隨機(jī)k個任務(wù)位置進(jìn)行突變,至此得到子代種群Qk。

(4)精英策略將父代進(jìn)行選擇、交叉、變異后產(chǎn)生的子代混合得到混合種群Rk,并對Rk進(jìn)行快速非支配排序,獲取種群中的優(yōu)秀個體并形成新的種群Nk+1,保證了工作流調(diào)度方案的魯棒性與全局性。

對第l支配層中的個體i計算擁擠度id,擁擠度表示每個個體周圍個體的密度,具體計算公式為:

id=|E(pki+1)-E(pki-1)|+|T(pki+1)-T(pki-1)|

(18)

式中,E(pki+1)為在個體pki+1下調(diào)度所產(chǎn)生的能耗,T(pki+1)為在個體pki+1下調(diào)度所產(chǎn)生的任務(wù)延時,i-1,i+1表示前后個體。對于個體im與個體in,若idm>idn,則將im排在in之前。記第l非支配層中的個體數(shù)為z(l),種群Pk+1中當(dāng)前的個體數(shù)為z(Pk+1),對第l非支配層中的所有個體進(jìn)行擁擠度排序,取前z(l)-[z(Pk+1)-N]個個體,使種群Pk+1的規(guī)模變?yōu)镹。

(5)判斷是否符合結(jié)束條件,符合或者達(dá)到迭代次數(shù)則停止更新,返回工作流任務(wù)調(diào)度方案以及最優(yōu)種群個體。不符合則k=k+1,返回步驟1繼續(xù)迭代。

3 仿真實(shí)驗與評估

3.1 實(shí)驗環(huán)境與實(shí)驗參數(shù)

為了更好地模擬工作流調(diào)度系統(tǒng)的運(yùn)行模式,使用工作流生成器生成工作流,其中任務(wù)數(shù)量為10～100,任務(wù)數(shù)據(jù)大小為1～5 MB,計算需求為1～6 GHz,可靠性需求為0.6～0.9。邊緣服務(wù)器的可靠性系數(shù)服從[0.999 00,0.999 99]的均勻分布,服務(wù)器個數(shù)為5～25,計算頻率為5 GHz。用戶設(shè)備帶寬為10 MHz,傳輸速率為5 Mbps,計算頻率為0～3 GHz,計算功耗為0.5 W,數(shù)據(jù)接受功率為50 mW,數(shù)據(jù)發(fā)射功率為100 mW,移動設(shè)備與服務(wù)器距離為0～200 m,信號干擾因子為-174 dbm/Hz,路徑損耗常數(shù)為0.01,路徑損耗指數(shù)為4[7]。實(shí)驗中,NSGA-Ⅱ-WS算法的種群個數(shù)為100,最大迭代次數(shù)為400,初始變異概率θ0=0.5,最大變化概率ρ=0.3。優(yōu)化目標(biāo)中權(quán)重系數(shù)α為0.6。

選取本文的NSGA-Ⅱ-WS算法、輪詢調(diào)度(Round Robin,RR)算法[8]、貪心算法Greedy和粒子群算法(Particle Swarm Optimization,PSO)[9]進(jìn)行實(shí)驗,其中,RR算法中,任務(wù)依次被均衡卸載到其他服務(wù)器節(jié)點(diǎn);Greedy算法中,優(yōu)先選擇可靠性最高的服務(wù)器進(jìn)行卸載;PSO算法將工作流調(diào)度方案初始化為一群隨機(jī)粒子,在保證可靠性的同時,通過迭代獲取粒子的最優(yōu)解,得到最優(yōu)的工作流調(diào)度方案。

3.2 不同可靠性約束下的性能

當(dāng)可靠性約束系數(shù)tiRD分別為0.6和0.8時,采用4種算法進(jìn)行實(shí)驗,得到不同可靠性約束下的能耗如圖2所示,平均時延如圖3所示。

圖2 不同可靠性約束下,任務(wù)數(shù)量和能耗的關(guān)系

圖3 不同可靠性約束下,任務(wù)數(shù)量和平均延時的關(guān)系

從圖2可以看出,隨任務(wù)數(shù)量的增加,4種算法的能量消耗不斷提升,其中,NSGA-Ⅱ-WS算法的能耗最小,因為NSGA-Ⅱ-WS算法生成調(diào)度序列時考慮了相同優(yōu)先級任務(wù)的并行性,通過可靠性約束對交叉概率、變異概率以及精英策略進(jìn)行自適應(yīng)調(diào)整,使算法總能獲得最佳的帕累托前沿,降低了工作流調(diào)度方案在可靠性約束下的能耗。

從圖3可以看出,隨著任務(wù)數(shù)量的增加,4種算法的工作流平均延遲也在增加。4種算法中,NSGA-Ⅱ-WS算法的平均延遲最低,因為NSGA-Ⅱ-WS算法將任務(wù)執(zhí)行時間與能耗的加權(quán)和作為適應(yīng)度進(jìn)行迭代優(yōu)化,縮短了平均延時。

3.3 系統(tǒng)成本

實(shí)驗中,將系統(tǒng)成本定義為設(shè)備能耗與工作流時延基于權(quán)重系數(shù)α的加權(quán)和,當(dāng)權(quán)重系數(shù)α=0.6時,采用4種算法進(jìn)行實(shí)驗,得到系統(tǒng)成本與任務(wù)數(shù)量和節(jié)點(diǎn)數(shù)量的關(guān)系如圖4和圖5所示。

圖4 任務(wù)數(shù)量和系統(tǒng)成本的關(guān)系

圖5 服務(wù)器節(jié)點(diǎn)數(shù)和系統(tǒng)成本的關(guān)系

從圖4可以看出,隨著任務(wù)數(shù)量的增加,NSGA-Ⅱ-WS算法的優(yōu)勢逐漸顯現(xiàn),因為NSGA-Ⅱ-WS算法通過任務(wù)復(fù)制保證在故障發(fā)生時,能夠調(diào)度至其他服務(wù)器繼續(xù)執(zhí)行,降低了故障損失。

從圖5可以看出,NSGA-Ⅱ-WS算法具有更低的系統(tǒng)成本。因為NSGA-Ⅱ-WS算法通過基因變異和精英策略等手段生成足夠優(yōu)秀的調(diào)度解,將任務(wù)分配至合適的基站,使工作流調(diào)度方案在服務(wù)器節(jié)點(diǎn)較少時也具有更低的系統(tǒng)成本,滿足可靠性的同時降低了能耗與任務(wù)執(zhí)行時間。

為了探究不同優(yōu)化權(quán)重系數(shù)α對NSGA-Ⅱ-WS算法的影響,本實(shí)驗采用相同的工作流,通過改變優(yōu)化權(quán)重系數(shù)α比較其能耗和時延,結(jié)果如圖6所示。

圖6 不同優(yōu)化權(quán)重下系統(tǒng)成本對比

從圖6可以看出,隨著權(quán)重系數(shù)的增大,工作流調(diào)度方案中的用戶能耗進(jìn)一步降低,但工作流時延隨之增加。隨著優(yōu)化函數(shù)中權(quán)重系數(shù)α的提高,為了得到適應(yīng)度更低的個體,種群在搜索過程中會偏向能耗更低的個體。綜上分析可知,可以通過改變權(quán)重系數(shù)α來迎合用戶的不同偏好。

4 結(jié)束語

在保證工作流可靠性的基礎(chǔ)上,充分考慮工作流任務(wù)對數(shù)據(jù)傳輸?shù)囊蕾嚰安煌?wù)器的故障率,采用改進(jìn)的非支配排序遺傳算法求解工作流的最優(yōu)卸載位置,本文設(shè)計了一種基于可靠性約束的工作流調(diào)度算法,降低了移動設(shè)備的能耗,減少了任務(wù)時延,提高了工作流執(zhí)行可靠性,保證了工作流調(diào)度方案的多樣性與全局性。但是,本文在研究中未考慮邊緣環(huán)境中服務(wù)器容量、負(fù)載狀態(tài)和服務(wù)更替成本等指標(biāo),且未滿足網(wǎng)絡(luò)流量不斷增長的需求與提升服務(wù)器及其他資源的利用效率,后續(xù)將針對服務(wù)器負(fù)載均衡等方面展開研究,實(shí)現(xiàn)在任務(wù)執(zhí)行中各負(fù)載指標(biāo)相互獨(dú)立。