羅 雨,顧憶宵,夏 斌

(上海交通大學(xué) 電子信息與電氣工程學(xué)院,上海200240)

0 引 言

移動邊緣計算技術(shù)(Mobile Edge Computing,MEC)在網(wǎng)絡(luò)邊緣接收處理用戶卸載的計算任務(wù),緩解核心網(wǎng)絡(luò)擁堵的同時提高用戶的體驗特質(zhì)(Quality of Experience,QoE)、降低計算任務(wù)的處理成本,在移動互聯(lián)網(wǎng)時代得到快速發(fā)展。研究者們通過對增強(qiáng)現(xiàn)實[1]和在線游戲[2]等邊緣計算場景下的計算任務(wù)展開內(nèi)容相關(guān)性和請求動態(tài)特征的研究以降低資源開銷、提高服務(wù)器工作效率。

文獻(xiàn)[3-4]對任務(wù)相關(guān)性展開了研究、通過構(gòu)建任務(wù)相關(guān)性感知的任務(wù)卸載機(jī)制以提高調(diào)度算法的性能表現(xiàn),后者進(jìn)一步引入了計算任務(wù)的遷移特征并建立馬爾可夫決策過程(Markov Decision Process,MDP)。利用任務(wù)相關(guān)性建立同類任務(wù)并行計算的處理機(jī)制可以減少計算開銷。文獻(xiàn)[5-6]進(jìn)一步從任務(wù)請求動態(tài)變化的角度出發(fā)進(jìn)行討論,前者將用戶請求的到達(dá)情況建模為隨機(jī)變量并基于排隊模型進(jìn)行優(yōu)化研究,后者對車聯(lián)網(wǎng)邊緣計算場景下的計算任務(wù)隨車輛運動的特征變化做出了討論。任務(wù)動態(tài)變化特征可用于預(yù)測任務(wù)的未來變化趨勢,輔助設(shè)計動態(tài)規(guī)劃算法。

但上述研究忽略了計算任務(wù)的生滅特性,該特性在無線網(wǎng)絡(luò)環(huán)境下廣泛存在,如視頻編碼任務(wù)[7]、新移動應(yīng)用計算任務(wù)[8]等。這一缺失降低了任務(wù)請求動態(tài)特征描述的準(zhǔn)確性,同時使得動態(tài)規(guī)劃算法難以突破當(dāng)前的復(fù)雜度瓶頸得到進(jìn)一步優(yōu)化?；诖?本文綜合考慮任務(wù)相關(guān)性感知和生滅動態(tài)特征構(gòu)建MEC架構(gòu),利用相關(guān)性特征設(shè)計任務(wù)處理機(jī)制降低時延能耗成本,并在現(xiàn)有任務(wù)請求動態(tài)特征研究的基礎(chǔ)上進(jìn)一步將任務(wù)請求的到達(dá)情況建模為生滅過程。在使用貝爾曼方程求解無限期平均成本馬爾可夫決策問題的過程中,通過提取任務(wù)請求的生滅特征對未來變化趨勢作出判斷,進(jìn)而估計調(diào)度策略的時延能耗成本以輔助求得最優(yōu)策略。這一優(yōu)化定理對策略迭代操作進(jìn)行狀態(tài)空間和決策空間的剪枝以提高系統(tǒng)性能,基于此提出批處理調(diào)度算法。所提算法綜合考慮任務(wù)的相關(guān)性和動態(tài)特征以取得性能優(yōu)勢,并通過基于生滅特征的剪枝方法突破了策略迭代的復(fù)雜度瓶頸。

1 系統(tǒng)模型

考慮一個離散時間多用戶的MEC系統(tǒng),網(wǎng)絡(luò)中存在一個與云端服務(wù)器相連接的MEC服務(wù)器以及K個與MEC服務(wù)器相連接的獨立用戶,記作K={1,2,3,…,K},如圖1所示。用戶將請求卸載至接入點(Access Point),對應(yīng)的邊緣服務(wù)器將用戶請求存儲到隊列中,運算完成后將結(jié)果傳輸給用戶,超出邊緣服務(wù)器承載能力的請求會卸載到云端服務(wù)器進(jìn)行處理。

圖1 基于任務(wù)相關(guān)性感知的MEC系統(tǒng)

1.1 任務(wù)模型

將服務(wù)時間以秒為單位劃分為多個長度為τ的時隙,有索引t∈N+,用戶在每個時隙隨機(jī)向服務(wù)器卸載請求,考慮該邊緣計算場景中有N種計算任務(wù)的請求,記作N={1,2,3,…,N}。將用戶k∈K在t時隙卸載的屬于任務(wù)類型n的請求的數(shù)量記作rn,k(t),所有用戶卸載的屬于任務(wù)類型n的請求總數(shù)記作an(t)?∑k∈Krn,k(t),有r(t)?{rn,k(t):n∈N,k∈K},a(t)?{an(t):n∈N}。

計算任務(wù)的生滅變化建模如下:在任務(wù)類型n處于生狀態(tài)時,這一類別的請求會在用戶處產(chǎn)生并被卸載到MEC服務(wù)器;當(dāng)任務(wù)類型n處于滅狀態(tài)時,這一類別的請求不會被卸載到服務(wù)器。用b(t)?{bn(t):n∈N}表示任務(wù)的生滅狀態(tài)。當(dāng)bn(t)=1,任務(wù)類型n在t時隙處于生狀態(tài)。當(dāng)bn(t)=0,任務(wù)類型n在t時隙處于滅狀態(tài)。以VR場景為例,場景內(nèi)事件的發(fā)生會帶來一系列計算任務(wù),這些計算任務(wù)隨交互事件的出現(xiàn)消失而出現(xiàn)消失,交互事件出現(xiàn)時對應(yīng)任務(wù)類型處于生狀態(tài),出現(xiàn)前或消失后處于滅狀態(tài)。

(1)

式中:1(Ω)為指示函數(shù),滿足條件Ω時值為1,否則為0。時隙t新到的來自用戶k的屬于任務(wù)類別n的請求數(shù)量可以表示為rn,k(t)·bn(t)。

1.2 調(diào)度模型

t時隙MEC服務(wù)器隊列中累積的同屬于類別n的任務(wù)請求的數(shù)量記作qn(t)。在每個時隙開始時,服務(wù)器會選擇一部分類別的任務(wù)請求來進(jìn)行處理運算。用指示變量un(t)∈{0,1}來標(biāo)記類別n的被選情況:當(dāng)un(t)=1時,類別n的請求將會在t時隙進(jìn)行處理,并在下一時隙將結(jié)果傳輸給用戶,否則un(t)=0。相應(yīng)地,把t時隙的調(diào)度決策記作u(t)?{un(t)|n∈N}∈U,決策空間大小為|U|。將t時隙決定進(jìn)行處理的任務(wù)請求類別集合記作N(t)={n|un(t)=1,n∈N}或Nu,類別數(shù)目記作m(t)=∑n∈Nun(t)。

如果決定對類別n的任務(wù)請求進(jìn)行處理,則會將MEC服務(wù)器隊列中累積的所有該類別的請求一并處理,同時清空請求隊列qn(t)。因此,由用戶k卸載的屬于類別n的請求隊列動態(tài)變化情況表示如下:

qn,k(t+1)=

min{1(un(t)≠1)qn,k(t)+rn,k(t)·bn(t),qmax}

(2)

式中:qmax是單個用戶卸載的單類任務(wù)請求在服務(wù)器處的最大存儲數(shù)量。在此基礎(chǔ)上將類別n的任務(wù)請求積累數(shù)量記作qn(t)=∑n∈Nqn,k(t),對于時延容忍度為Tn的任務(wù)類別n,對應(yīng)的t時隙的時延成本可以記作Dn(t)=qn(t)·Tn。同時整個系統(tǒng)在t時隙的總時延成本為

(3)

超出服務(wù)器存儲能力qmax的請求需要遷移到云端服務(wù)器進(jìn)行處理[10],將其產(chǎn)生的額外時延成本記作遷移成本:

Ln,k(t)=max(1(un(t)≠n)qn,k(t)+

rn,k(t)·bn(t)-qmax)·Tn,0}

(4)

有

(5)

1.3 計算模型

類別n的任務(wù)請求相關(guān)參數(shù)可以表示為In,On,Cn,Tn,In(單位:b),On(單位:b),Cn(單位:每比特所需CPU周期)分別代表該類任務(wù)請求的輸入數(shù)據(jù)量、輸出數(shù)據(jù)量、每比特數(shù)據(jù)計算所需CPU周期數(shù)。

(6)

進(jìn)而得到整個系統(tǒng)在t時隙的總計算能耗為

(7)

式中:κ為有效開關(guān)電容[13]。考慮到MEC服務(wù)器處的計算資源限制,同一時隙內(nèi)最多可并行使用的虛擬機(jī)數(shù)量上限為mmax[14],因此一次調(diào)度決策中決定進(jìn)行處理的任務(wù)種類數(shù)量存在上限m(t)≤mmax。

1.4 通信模型

著眼于通信資源受限的計算結(jié)果下行傳輸部分[15]。下行無線信道建模為塊衰落的有限狀態(tài)馬爾可夫信道[16],將t時隙內(nèi)用戶k與接入點之間的信道增益記作hk(t),對應(yīng)的可達(dá)速率(單位:b/s)為

(8)

式中:Pn,k(t),B,N0分別為傳輸功率、可用帶寬以及復(fù)白高斯信道噪聲的方差。為了在長度為τ的一個時隙內(nèi)完成對數(shù)據(jù)量為On的計算結(jié)果的傳輸,傳輸速率必須達(dá)到On/τ。傳輸功率會受到用戶中信道狀態(tài)最差者的限制,即hn(t)?mink∈Kn(t)hk(t),?n∈N,其中Kn(t)?{k|qn,k(t)>0,k∈K}?？紤]以上因素,系統(tǒng)在t時隙進(jìn)行任務(wù)類別n的計算結(jié)果的傳輸能耗表示如下:

(9)

(10)

2 問題建模與最優(yōu)性分析

本節(jié)將基于上述MEC模型建立起優(yōu)化問題并說明所采用的研究方法。首先基于貝爾曼方程對馬爾可夫決策過程的值函數(shù)進(jìn)行單調(diào)性分析,之后根據(jù)任務(wù)請求隊列和生滅狀態(tài)特征以及問題結(jié)構(gòu)提出數(shù)條優(yōu)化命題。

2.1 問題建模

t時隙開始時,MEC服務(wù)器需要根據(jù)系統(tǒng)狀態(tài)S(t)?{q(t),b(t)}∈S來確定調(diào)度決策u(t),將這一過程中使用的控制策略μ定義為由系統(tǒng)狀態(tài)到調(diào)度決策的映射關(guān)系μ:{q,b}→u,函數(shù)表示為μ(q,b)=u。在后續(xù)的討論中,前述時延、能耗成本可以表示為系統(tǒng)狀態(tài){q,b}和調(diào)度決策u的函數(shù):時延成本表示為D(q),計算能耗成本表示為E1(u),通信能耗成本表示為E2(q,u),遷移成本表示為L(q,u)。

引入加權(quán)和方法對各項成本進(jìn)行統(tǒng)籌優(yōu)化,該MEC系統(tǒng)的一步加權(quán)成本可以表示如下:

g(q,u)?D(q)+ω1E1(u)+ω2E2(q,u)+ω3L(q,u)

(11)

式中:ω1,ω2,ω3分別為計算能耗成本、通信能耗成本、遷移成本的權(quán)重參數(shù)。給定穩(wěn)定的單鏈控制策略μ,系統(tǒng)的長期平均成本可以表示如下:

(12)

問題1 長期系統(tǒng)成本最小化問題:

(13)

2.2 問題討論

值迭代(Value Iteration,VI)和策略迭代(Policy Iteration,PI)都是解決MDP問題的常用方法?？紤]到本研究中優(yōu)化問題核心在于找到最優(yōu)策略,同時策略迭代在許多情況下的性能表現(xiàn)優(yōu)于值迭代[17],因此將策略迭代的方法作為研究的中心,并以此為基礎(chǔ)進(jìn)行優(yōu)化理論的設(shè)計。

問題1是一個單鏈無限期平均成本馬爾可夫決策問題,狀態(tài)空間和決策空間有限,存在最優(yōu)的確定性平穩(wěn)策略,可以通過如下貝爾曼方程求得:

(14)

(15)

引入狀態(tài)-決策成本函數(shù)J(q,b,u)?g(q,u)+E(V(q′,b′)),代入式(15)可得

(16)

2.3 最優(yōu)性分析

以模型中請求隊列和生滅狀態(tài)動態(tài)變化的特征為基礎(chǔ),結(jié)合值迭代的方法,分析得到值函數(shù)V(S)的如下性質(zhì):

引理1 值函數(shù)的單調(diào)性:對于任意一組系統(tǒng)狀態(tài)S1=(q1,b1),S2=(q2,b2)∈S滿足S1≤S2,有V(S1)≤V(S2)。

因篇幅所限,引理1的證明請用微信掃描本文OSID碼,在“開放科學(xué)數(shù)據(jù)與內(nèi)容”中查看。

以引理1為基礎(chǔ),結(jié)合問題的結(jié)構(gòu)特征,可以得到關(guān)于J(q,b,u)的如下性質(zhì):

命題1 狀態(tài)-決策成本函數(shù)關(guān)于請求隊列狀態(tài)的單調(diào)性:對于任意調(diào)度決策u,v∈U,有

J((q+en,k,b),u)-J((q+en,k,b),v)≤

J((q,b),u)-J((q,b),v)

(17)

式中:eu,k為一個N×K矢量(n∈Nu,k∈K),只有在(n,k)這一處的值為1,其他都為0。

命題的證明與文獻(xiàn)[18]引理3類似。

命題1說明,對于系統(tǒng)狀態(tài){q,b}和調(diào)度決策u,v,如果狀態(tài)-決策成本函數(shù)滿足J((q,b),u)≤J((q,b),v),則對于衍生狀態(tài)(q+en,k,b),決策之間的優(yōu)劣關(guān)系仍然成立,有J((q+en,k,b),u)-J((q+en,k,b),v)≤0。派生狀態(tài)與原狀態(tài)的生滅特征相同,隊列狀態(tài)的差別滿足命題1。由命題1出發(fā),可以得到如下定理:

定理1 最優(yōu)策略的最優(yōu)性繼承:使用策略迭代算法尋找最優(yōu)策略μ*的過程中,如果式(18a)和(18b)條件成立,u=μ*(q2,b),則有μ*(q1,b)=μ*(q2,b)。

(18a)

(18b)

定理1表明,在策略改進(jìn)步驟中計算狀態(tài){q1,b}所對應(yīng)的最優(yōu)調(diào)度決策時,如果已經(jīng)求得狀態(tài){q2,b}的最優(yōu)調(diào)度決策,同時這兩個狀態(tài)滿足命題1所述關(guān)系,則狀態(tài){q2,b}的最優(yōu)決策同時也是狀態(tài){q1,b}的最優(yōu)決策。定理1的方法對策略改進(jìn)過程中所需要遍歷的狀態(tài)空間進(jìn)行剪枝以降低計算復(fù)雜度。

基于引理1和J(q,b,u)的性質(zhì),另有如下命題:

命題2 決策關(guān)于生滅狀態(tài)的最優(yōu)性:對于系統(tǒng)狀態(tài){q,b}和調(diào)度決策u=μ(q,b)∈U,其中滿足?n∈N,bn=0,qn>0,un=0,m=∑n∈Nun

(19)

σ=∑(q0,b0)∈S0Pr((q0,b0)|(q,b),μ(q,b))

(20a)

S0={(q0,b0)|Pr((q0,b0)|(q,b)

(20b)

u0=μ(q0,b0)

(20c)

因篇幅所限,命題的證明請用微信掃描本文OSID碼,在“開放科學(xué)數(shù)據(jù)與內(nèi)容”中查看。

命題2表明,給定控制策略μ,如果有一組系統(tǒng)狀態(tài){q,b}與對應(yīng)的調(diào)度決策u=μ(q,b)滿足命題2所述條件,則控制策略μ不是最優(yōu)策略,且最優(yōu)策略μ*嚴(yán)格優(yōu)于μ。由命題2出發(fā),可以得到如下定理:

定理2 最優(yōu)策略的決策剪枝:求解最優(yōu)控制策略μ*下狀態(tài){q,b}的最優(yōu)調(diào)度決策μ*((q,b))時,如果狀態(tài){q,b}與對應(yīng)的調(diào)度決策u滿足?n∈N,bn=0,qn>0,un=0,m=∑n∈Nun

(21)

定理2表明,在遍歷所有策略尋找狀態(tài){q,b}的最優(yōu)策略的策略改進(jìn)過程中,對于滿足定理2的策略,應(yīng)當(dāng)直接予以排除,不需要迭代計算其值函數(shù)。由此實現(xiàn)對決策空間的剪枝,計算復(fù)雜度降低。

3 基于分析得到的最優(yōu)算法

將定理1、定理2的策略與標(biāo)準(zhǔn)的策略迭代算法(Policy Iteration Algorithm,PIA)相結(jié)合得到低復(fù)雜度的最優(yōu)算法,稱為剪枝策略迭代算法(Pruned Policy Iteration Algorithm,PPIA)。相較于標(biāo)準(zhǔn)的PIA,PPIA利用定理1和定理2對策略改進(jìn)步驟中需要遍歷的狀態(tài)空間和決策空間進(jìn)行剪枝。剪枝策略迭代算法偽代碼如下:

輸入:系統(tǒng)參數(shù),狀態(tài)空間S,決策空間U,轉(zhuǎn)移概率矩陣∑S′∈SPr[S′|S,u],一步成本g(q,u),初始控制策略μ,θ

輸出:最優(yōu)控制策略μ*

1 初始化所有狀態(tài)S∈S的值函數(shù)V(S)=0

2δ=θ

3 whileδ≥θdo:

4 forS∈S do:

5v←V(S)

6V(S)←g(S,μ(S))+∑S′∈SPr[S′|S,μ(S)](V(S′))

7δ←max {δ,|v-V(S)|}

8 end

9 end

10 PolicyStable←true

11 forS∈S do:

12 OldAction←μ(S)

13 if存在已遍歷的狀態(tài)S′滿足定理1 then:

14μ(S)=μ(S′)

15 else ifS滿足定理2 then:

17 foru∈Udo:

18 Ifu滿足定理2 then:

20 end

22 else

24 end

25 If OldAction≠μ(S) then

26 PolicyStable←false

27 end

28 if PolicyStable then 返回μ*=μ

29 else回到第3行

算法第2～9行是策略驗證步驟,第10～29行是策略改進(jìn)步驟。

從第11行開始以逆字典序遍歷狀態(tài)空間,在第13行對滿足定理1的狀態(tài)S進(jìn)行剪枝:如果其衍生狀態(tài)S′在本次策略改進(jìn)步驟中已經(jīng)被遍歷,則依照定理1將μ(S′)直接作為μ(S)的解,不再需要迭代求解,由此實現(xiàn)對狀態(tài)空間的剪枝。

從第15行開始,遍歷每個狀態(tài)的決策空間以找尋最優(yōu)決策,在此處引入定理2,對于滿足定理2的狀態(tài)-決策組合(State-action Combination)可以直接跳過不進(jìn)行遍歷,由此實現(xiàn)對決策空間的剪枝。

對于標(biāo)準(zhǔn)的PIA,需要遍歷大小為|S|的狀態(tài)空間和大小為|U|的決策空間來求得μ(S),每次迭代的總復(fù)雜度為O(|S|3+|U||S|2)。PPIA通過減少需要遍歷的狀態(tài)空間和決策空間大小,使得其計算復(fù)雜度低于PIA。由于采用了相同的迭代方法,PPIA的最優(yōu)性和可收斂性與PIA一致[17]。

4 性能仿真與分析

4.1 仿真環(huán)境與設(shè)置

通信模型與計算模型相關(guān)參數(shù)配置情況如表1所示,有限狀態(tài)馬爾可夫信道的信道增益hk參考[19]進(jìn)行配置。

表1 仿真參數(shù)配置

從算法運行速度和調(diào)度策略的平均成本這兩方面來進(jìn)行仿真設(shè)計。作為對照的算法包括標(biāo)準(zhǔn)的PIA算法[17]、同樣基于動態(tài)規(guī)劃但未考慮生滅特征的SPIA算法[18]、隨機(jī)策略、最長隊列優(yōu)先策略[20],以及基于本研究場景提出的啟發(fā)式策略。啟發(fā)式策略以隊列負(fù)荷為標(biāo)桿,優(yōu)先處理滅狀態(tài)、隊列負(fù)荷較高的任務(wù)請求。

4.2 算法運行時間分析

本小節(jié)與其他最優(yōu)算法的運行時間進(jìn)行對比,運行時間越短說明算法復(fù)雜度更低、運行效率更高。為體現(xiàn)優(yōu)化理論的剪枝性能,討論能耗權(quán)重參數(shù)ω1和ω2的變化對不同算法運行時間的影響。實驗結(jié)果如表2所示,PIA和SPIA的運行時間受權(quán)重參數(shù)變化的影響較小,PPIA的運行時間隨能耗參數(shù)減小而減小。原因在于,定理2的剪枝優(yōu)化性能受具體的權(quán)重參數(shù)影響,當(dāng)能耗權(quán)重參數(shù)ω1和ω2增大時,狀態(tài)空間和決策空間中滿足定理2中不等式條件的狀態(tài)與決策數(shù)量增加,可以剪枝處理掉的狀態(tài)更多,算法復(fù)雜度和運行時間隨之降低。PIA沒有進(jìn)行剪枝,SPIA沒有針對生滅過程進(jìn)行剪枝,因而運算時間長于PPIA。PPIA在ω1=0.4,ω2=0.4時將運行時間縮短至2.956 2 s,相較于PIA算法有高于26%的效率提升。

表2 系統(tǒng)的能耗權(quán)重參數(shù)ω1和ω2變化時不同算法所對應(yīng)的運行時間差別

為體現(xiàn)PPIA能在更復(fù)雜場景下保持性能優(yōu)勢,討論系統(tǒng)內(nèi)任務(wù)請求種類數(shù)量的變化對不同算法運行時間的影響。實驗結(jié)果如表3所示,隨著請求種類數(shù)量的上升,系統(tǒng)復(fù)雜度與算法運行時間提高,使用剪枝優(yōu)化的PPIA始終保持25%以上的運行時間優(yōu)勢。

表3 系統(tǒng)的任務(wù)請求種類數(shù)N變化時不同算法所對應(yīng)的運行時間差別

綜合以上兩則實驗場景可得,以定理2為基礎(chǔ)的剪枝算法PPIA能在保持最優(yōu)性的同時相較于PIA算法和SPIA算法有著更快的運行速度,在一定的能耗權(quán)重參數(shù)下表現(xiàn)更佳。

4.3 算法平均成本分析

本小節(jié)與其他次優(yōu)算法的平均成本進(jìn)行對比。為體現(xiàn)PPIA在不同系統(tǒng)負(fù)載下的平均成本優(yōu)勢,比較平均請求到達(dá)速率變化對不同算法所對應(yīng)的調(diào)度策略的平均成本的影響,實驗結(jié)果如圖2所示。隨著請求到達(dá)速率的提升,更多的請求帶來更多的時延、能耗成本,平均成本呈上升趨勢,當(dāng)?shù)竭_(dá)速率大于1.1時趨于穩(wěn)定,PPIA的調(diào)度方案平均成本由20.3839上升至26.740,保持最低的同時在到達(dá)速率較高時體現(xiàn)出明顯優(yōu)勢。啟發(fā)式算法在到達(dá)速率低于0.7時性能表現(xiàn)相對優(yōu)秀,但當(dāng)?shù)竭_(dá)速率逐漸上升時與PPIA之間的差異明顯增大。到達(dá)速率的提高帶來了更高的隊列負(fù)荷,需要消耗更多的能耗成本進(jìn)行處理或在節(jié)省能耗成本的同時面對更高的時延和遷移成本,PPIA能準(zhǔn)確權(quán)衡成本取舍,同時通過迭代尋求最優(yōu)解,因而相較于其他次優(yōu)算法表現(xiàn)良好。啟發(fā)式算法能平衡隊列負(fù)載,但當(dāng)請求到達(dá)速率較高時需要更高的能耗成本以保持隊列負(fù)載平衡,性能表現(xiàn)嚴(yán)重下降。

圖2 系統(tǒng)的請求到達(dá)速率變化時不同算法所對應(yīng)的平均成本差異

為體現(xiàn)PPIA在不同生滅場景下能保持性能穩(wěn)定,比較任務(wù)死亡率變化對不同算法平均成本的影響,實驗結(jié)果如圖3所示。隨著任務(wù)死亡率的上升,任務(wù)的平均激活周期變短,請求數(shù)量下降導(dǎo)致調(diào)度方案的平均成本下降,同時生滅頻率的變化會讓算法難以對請求的未來到達(dá)情況做出估計、降低算法性能的穩(wěn)定性。在死亡率低于0.4、任務(wù)生周期較長時,最長隊列優(yōu)先策略和啟發(fā)式策略難以在生狀態(tài)判斷是否應(yīng)當(dāng)積累請求等待后續(xù)處理,同時難以在滅狀態(tài)判斷是否應(yīng)當(dāng)?shù)却乱淮紊鸂顟B(tài)再行處理,因此綜合性能表現(xiàn)差?；谏鷾邕^程開發(fā)的PPIA能在不同生滅速率下準(zhǔn)確判斷未來狀態(tài)的請求到達(dá)期望以取得最優(yōu)性能表現(xiàn),平均成本保持在30以下。當(dāng)死亡率較高時,啟發(fā)式算法的平均成本變化趨于穩(wěn)定,但仍然劣于PPIA。

圖3 系統(tǒng)的任務(wù)死亡率變化時不同算法所對應(yīng)的平均成本差別

綜合以上兩則實驗場景可得,啟發(fā)式算法和最長隊列優(yōu)先算法在低到達(dá)速率、低死亡率等場景下性能表現(xiàn)不佳,PPIA則能在不同系統(tǒng)條件下保持性能穩(wěn)定,平均成本低于其他次優(yōu)算法。

5 結(jié) 論

針對現(xiàn)有邊緣計算研究未考慮任務(wù)生滅特征而存在復(fù)雜度瓶頸,本文提出基于生滅過程和任務(wù)相關(guān)性感知的邊緣計算模型并給出剪枝策略迭代算法,利用任務(wù)的生滅特征對未來請求到達(dá)情況進(jìn)行判斷,輔助確定當(dāng)前狀態(tài)最優(yōu)決策以降低迭代過程中遍歷的狀態(tài)空間和決策空間大小。仿真結(jié)果表明,基于生滅特征取得的優(yōu)化定理使得所提算法突破了策略迭代的復(fù)雜度瓶頸,計算開銷低于標(biāo)準(zhǔn)策略迭代算法,同時時延能耗成本低于最長隊列優(yōu)先策略等次優(yōu)策略,且能在多變的系統(tǒng)狀態(tài)下保持性能穩(wěn)定。