基于可靠性約束的工作流調度算法

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

(1.杭州電子科技大學計算機學院,浙江 杭州 310018;2.浙江省腦機協同智能重點實驗室,浙江 杭州 310018)

0 引 言

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

1 移動邊緣計算系統模型

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

1.1 工作流模型

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

1.2 可靠性模型

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

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

(1)

用戶設備可視為1個本地服務器,編號為0,當任務在本地設備上發生故障時,立即進行任務重啟。若工作流w中的每個任務ti的調度位置已知,則工作流w的執行可靠性為:

(2)

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

1.3 時間模型

在工作流調度過程中,任務完成時間包括任務的傳輸時間與執行時間。當用戶設備選擇將任務進行卸載時,μ時刻時,設備i向設備j數據傳輸速率trans(i,j)表示為:

(3)

任務ti向服務器sj的傳輸時間為:

(4)

任務的執行時間與邊緣節點性能和任務工作量有關,該任務的執行時間為:

(5)

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

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

(6)

1.4 能耗模型

在邊緣計算環境中進行任務調度時,必然要考慮用戶設備的能耗問題。用戶設備的能耗主要包括本地執行任務產生的能耗和向其他邊緣服務器傳輸數據產生的能耗。

對于工作流w,設本地設備計算功率為Pc,則本地執行能耗為:

(7)

式中,O為本地執行的任務集合。

設本地設備傳輸功率為Pt,工作流w通信產生的傳輸能耗為:

(8)

則設備總能耗為:

E=Eex(w)+Etrs(w)

(9)

2 基于可靠性約束的工作流調度算法

在改進NSGA-Ⅱ算法基礎上,本文提出一種基于可靠性約束的工作流調度算法NSGA-Ⅱ-WS,在滿足可靠性約束條件下,最小化設備的能耗和響應時間。

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

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

(10)

證明采用數學歸納法證明。在分配入口任務t0時,所有任務都未分配任務調度位置,應用程序w需要滿足如下可靠性目標:

(11)

假設任務tj已經找到滿足可靠性目標的可用服務器,則有:

(12)

同理,對于任務tj+1,其工作流執行可靠性為:

(13)

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

(14)

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

Rj+1(w)≥Rgoal(w)

(15)

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

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

圖1 NSGA-Ⅱ-WS算法執行流程示意圖

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

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

本文主要在移動邊緣環境下實現一種基于可靠性約束的工作流調度算法,在滿足可靠性約束的同時實現能耗和時延最小化。對于工作流w,優化目標函數表示為:

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

(16)

式中,E為設備能耗,α為權重因子,T為工作流時延。優化目標函數在本模型中也被視為系統成本。選取該任務調度目標作為適應度評價指標,通過計算調度方案的適應度,評估調度方案的可靠性、時延與能耗,適應度值越小表示方案越優。該問題是一個NP-hard問題,需要在滿足可靠性約束同時實現能耗和時延最小化。

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

(2)交叉操作是算法優劣的關鍵。單點交叉算子選擇位置效率較低,不能有效搜索解空間,故本文提出混合交叉算子。在單點交叉算子的基礎上,隨機在父代個體上選取q個不連續基因,對另一個交叉個體同位置基因進行交換,然后得到子代個體?；虻牟贿B續性使父代與子代的差異性更大,從而擴大了解空間。

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

(17)

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

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

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

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

(18)

式中,E(pki+1)為在個體pki+1下調度所產生的能耗,T(pki+1)為在個體pki+1下調度所產生的任務延時,i-1,i+1表示前后個體。對于個體im與個體in,若idm>idn,則將im排在in之前。記第l非支配層中的個體數為z(l),種群Pk+1中當前的個體數為z(Pk+1),對第l非支配層中的所有個體進行擁擠度排序,取前z(l)-[z(Pk+1)-N]個個體,使種群Pk+1的規模變為N。

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

3 仿真實驗與評估

3.1 實驗環境與實驗參數

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

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

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

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

圖2 不同可靠性約束下,任務數量和能耗的關系

圖3 不同可靠性約束下,任務數量和平均延時的關系

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

從圖3可以看出,隨著任務數量的增加,4種算法的工作流平均延遲也在增加。4種算法中,NSGA-Ⅱ-WS算法的平均延遲最低,因為NSGA-Ⅱ-WS算法將任務執行時間與能耗的加權和作為適應度進行迭代優化,縮短了平均延時。

3.3 系統成本

實驗中,將系統成本定義為設備能耗與工作流時延基于權重系數α的加權和,當權重系數α=0.6時,采用4種算法進行實驗,得到系統成本與任務數量和節點數量的關系如圖4和圖5所示。

圖4 任務數量和系統成本的關系

圖5 服務器節點數和系統成本的關系

從圖4可以看出,隨著任務數量的增加,NSGA-Ⅱ-WS算法的優勢逐漸顯現,因為NSGA-Ⅱ-WS算法通過任務復制保證在故障發生時,能夠調度至其他服務器繼續執行,降低了故障損失。

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

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

圖6 不同優化權重下系統成本對比

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

4 結束語

在保證工作流可靠性的基礎上,充分考慮工作流任務對數據傳輸的依賴及不同服務器的故障率,采用改進的非支配排序遺傳算法求解工作流的最優卸載位置,本文設計了一種基于可靠性約束的工作流調度算法,降低了移動設備的能耗,減少了任務時延,提高了工作流執行可靠性,保證了工作流調度方案的多樣性與全局性。但是,本文在研究中未考慮邊緣環境中服務器容量、負載狀態和服務更替成本等指標,且未滿足網絡流量不斷增長的需求與提升服務器及其他資源的利用效率,后續將針對服務器負載均衡等方面展開研究,實現在任務執行中各負載指標相互獨立。