面向多應用的綠色卸載與處理方案研究

張竣銘，王俊義，彭 捷，李 然

(桂林電子科技大學 信息與通信學院，廣西 桂林 541004)

0 引言

隨著物聯(lián)網(wǎng)技術(shù)的快速發(fā)展,大量新型物聯(lián)網(wǎng)應用也隨之迅速發(fā)展,激發(fā)包括人臉識別、VR、AR在內(nèi)的時延敏感、計算密集型應用廣泛應用于智慧城市等場景,極大地促進了信息化社會進程[1]。但由于終端設(shè)備的有限計算資源和有限的功率供應,無法全面滿足所有的物聯(lián)網(wǎng)時延需求。為解決上述問題,移動邊緣計算(Mobile Edge Computing, MEC)應運而生。MEC在接入網(wǎng)端部署有限的計算資源并允許終端設(shè)備將應用請求通過接入節(jié)點上傳到邊緣云端進行處理,旨在實現(xiàn)低時延的應用響應[2]。

然而部分終端設(shè)備由于有限的功率供應無法將應用請求實時通過接入節(jié)點上傳到邊緣云端,因此為充分利用終端設(shè)備上的計算資源進而提高網(wǎng)絡容量,終端設(shè)備可以將應用請求上傳到其他空閑的終端設(shè)備進行處理(D2D卸載模式)[3]。同時考慮到實際情況中,多應用請求面對有限的計算資源存在激烈競爭,導致大量應用請求僅獲得少量的計算資源,進而導致應用請求失效。因此為擴展系統(tǒng)服務能力并降低系統(tǒng)功耗,合理協(xié)調(diào)多個應用請求的處理順序是有效的方式之一。

已有的文獻中,單終端設(shè)備場景下的邊緣計算卸載研究中涉及移動視頻流服務性能以及基于無線電力傳輸?shù)墓?jié)能研究[4-5]。文獻[6]考慮了D2D卸載模型對降低單個應用請求時延的影響,證明了終端設(shè)備間的協(xié)作卸載機制對實現(xiàn)快速的應用響應具有重要作用。文獻[7-10]考慮了多終端設(shè)備場景,文獻[7-8]分別對多終端設(shè)備場景的MEC系統(tǒng)中的安全性和節(jié)能問題進行研究。文獻[9-10]進一步考慮到了終端設(shè)備之間的協(xié)作機制(D2D卸載),文獻[9]考慮了2個終端設(shè)備,通過終端設(shè)備間的毫米波通信技術(shù)顯著降低了網(wǎng)絡延遲并提高了網(wǎng)絡容量;文獻[10]進一步研究了利用ETSI多址的多終端設(shè)備間D2D輔助卸載機制,以實現(xiàn)實時的網(wǎng)絡服務。此外,維持系統(tǒng)的長效性能也十分重要。因此文獻[11]考慮了多用戶MEC系統(tǒng)的動態(tài)緩存、計算卸載和計算資源分配問題,并考慮基于流行度的邊緣緩存策略,最小化成本函數(shù)的長期平均值。然而考慮到現(xiàn)實情況中,應用請求的產(chǎn)生時刻具有差異性,因此文獻[12]考慮了應用請求的不同到達時間,提出一個基于激勵機制的任務卸載框架,然后提出的定價算法通過考慮在邊緣計算節(jié)點上的延遲成本來給出最優(yōu)的計算定價和卸載方案。進一步,文獻[13]考慮在邊緣計算節(jié)點上應用請求的處理順序,在有限計算資源下提高有效卸載量,應用處理過程被建模為M/M/1/B隊列,證明了合理協(xié)調(diào)應用請求的處理順序有利于提高系統(tǒng)的卸載性能。然而目前已有的工作還未充分探究基于D2D輔助卸載的MEC系統(tǒng)中應用處理順序?qū)ο到y(tǒng)帶來的影響,有待進一步探究。

為解決上述問題,本文首先提出了一個基于D2D輔助卸載的移動邊緣計算模型,其中包括本地卸載、D2D輔助卸載和卸載到邊緣云端3種卸載模式,然后構(gòu)建在終端設(shè)備和邊緣云端上面向多應用的應用處理順序模型,最小化終端設(shè)備總功耗,以實現(xiàn)綠色卸載目標。對于這個終端設(shè)備總功耗最小化問題,基于貪婪配置思想和冒泡排序思想,并通過分析不同應用請求對等待時延的容許能力及其對總功耗的影響,提出了綠色卸載與應用處理排序算法(Green Offloading and Application Processing Sorting Algorithm, GOAPSA),實現(xiàn)了最小化所有終端設(shè)備的總功耗,充分發(fā)揮了終端設(shè)備間輔助卸載和靈活調(diào)整應用處理順序的優(yōu)勢。

1 模型構(gòu)建與問題建模

1.1 系統(tǒng)模型

圖1 D2D輔助的MEC模型Fig.1 D2D-assised MEC model

1.1.1 應用卸載模型

(1)

(2)

1.1.2 應用響應時延模型

(3)

(4)

終端設(shè)備m的應用請求通過無線通信鏈路上傳到終端設(shè)備m′后,應用處理時延可表示為:

(5)

(6)

(7)

(8)

1.1.3 功耗模型

(9)

(10)

(11)

1.1.4 應用處理順序模型

圖2 終端設(shè)備m的應用請求處理時間軸Fig.2 The timeline of application requests for terminal equipment m

(12)

(13)

(14)

(15)

(16)

1.2 問題建模

綜上所述,本文考慮終端設(shè)備有限的計算資源、有限的功率供應和應用請求處理的時延約束,最小化系統(tǒng)終端設(shè)備的總功率消耗?？傮w優(yōu)化問題可規(guī)劃為如下P1問題:

P1中共包含3類決策變量,分別為卸載決策變量α,卸載功率分配變量Poff和應用處理順序變量Q={Q1,Q2,…,QM,QC}。上述問題P1中,C1和C2為卸載決策變量約束,約束C3表示終端設(shè)備的計算資源有限,約束C4表示有限的終端功率供應,C5表示所有應用請求的時延約束。

2 問題求解與算法設(shè)計

問題P1表明,總功耗最小化問題涉及卸載決策變量α、卸載功率變量Poff和應用處理順序變量Q,其中卸載決策變量α為0～1變量,卸載功率分配變量為實數(shù)決策向量,應用處理順序變量為離散決策空間變量,且變量之間存在耦合關(guān)系。顯然P1問題為NP-hard問題,求解具有挑戰(zhàn)性。因此本文基于貪婪配置思想和冒泡排序算法思想,給出了如下的GOAPSA。

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

本文具體算法如算法1所示。

算法1:GOAPSA1. 輸出:最優(yōu)的任務卸載決策α?,卸載功耗決策Poff,?,應用處理順序變量?。2. 對所有終端設(shè)備m∈,如果cm≤Cm,?mcm≤Pm,令m(1)=m。3. Repeat4. 根據(jù)式(20)對?m∈求出對應的can-offm。5. 對?m∈令αmm′=1,其中m′=argmaxm″∈{can-offm,C}hHm,m″。6. 求出over={m∈∑m′∈offmαm′mcm′>Cm∪Pm>Pmaxm},即過度使用的終端設(shè)備集合。7. Whileover≠?8. For i=1 toover9. 對m∈offi求出其最小卸載功率向量Poff-minm={Poff-minm,1,Poff-minm,2,…,Poff-minm,M,Poff-minm,C}。10. 根據(jù)式(23)求出{msend,mreceive},令αmsendm=0,αmsendmreceive=1。11. End for12. End while13. Until∪m∈can-offm=?∪over=?14. 對?m∈,C,所有的最大容許時延排序表示為tw-maxm1≤tw-maxm2≤…≤tw-maxmoffm,令Qm(i)=mi其中?m∈offm,i∈[1,2,…,offm]。15. For i=1 to M16. For j=1 to offi17. For z=1 to offi-j18. If twaiti(i(z+1))+Tsumi(z)hHi,i(z+1)219. 交換i(z)以及i(z+1)。20. End if21. End for22. End for23. End for21. 對?m∈,根據(jù)式(25)和式(26)求出Poffm(i),m。

3 算法復雜度分析

4 仿真結(jié)果與分析

本節(jié)主要展示了GOAPSA仿真結(jié)果及分析。證實了GOAPSA通過靈活調(diào)整終端設(shè)備的卸載決策、卸載功率決策和應用處理順序決策,有效降低了所有終端設(shè)備的總功耗并提高了有效的應用請求數(shù)量。展示了GOAPSA在節(jié)能以及有效服務應用請求數(shù)量上的優(yōu)勢,對比了2種常見的計算卸載算法,包括只將應用請求卸載到邊緣云端或本地處理的貪婪計算卸載算法(GCOA_E)和隨機應用處理順序的貪婪卸載算法(GCOA_Rand)。

4.1 仿真場景設(shè)置

在本文的仿真中,設(shè)置接入節(jié)點的覆蓋半徑為300 m[17],其中終端數(shù)量M=80均勻分布在覆蓋范圍內(nèi)[17]。對于終端設(shè)備而言,其計算資源上限Cm=[0.5,2]×109cycle[18],最大的功率供應為5 W。

4.2 仿真結(jié)果

圖3展示了本文提出GOAPSA迭代次數(shù)與終端設(shè)備數(shù)間的關(guān)系,顯然隨著終端設(shè)備的數(shù)量增加,GOAPSA的迭代次數(shù)也隨之增加。當終端設(shè)備數(shù)較大時(例如終端設(shè)備數(shù)為70或80時),本文的迭代次數(shù)維持在80左右,具有較快的收斂速度。

圖3 算法迭代次數(shù) v.s. 終端設(shè)備數(shù)Fig.3 The iterations of GOAPSA vs the number ofterminal devices

圖4 系統(tǒng)總功耗v.s.CmFig.4 Total system power consumption vs Cm

圖5 有效服務終端個數(shù)v.s.CmFig.5 The number of effective applications vs Cm

圖6、圖7和圖8展示了本文提出的GOAPSA在充分利用終端設(shè)備間的D2D協(xié)作卸載以及靈活調(diào)整應用處理順序的優(yōu)勢。具體來說,在圖6中,隨著終端設(shè)備的增多,3種算法的系統(tǒng)總功耗都逐漸增加。這是因為終端設(shè)備的增加意味著應用請求和系統(tǒng)計算資源上限的增多,此時更多的計算資源被使用以滿足更多應用請求的時延需求,進而造成了系統(tǒng)總功耗的增加。同時由圖6可得出,在本文提出的GOAPSA控制下的系統(tǒng)總功耗小于GCOA_Rand這一結(jié)論。圖7表明在GOAPSA控制下,有效服務應用請求的數(shù)量大于GCOA_Rand,證實了在GOAPSA的控制下,通過靈活調(diào)整應用請求的處理順序可以有效降低系統(tǒng)總功耗并提高有效服務的應用請求個數(shù)。此外,圖7和圖8顯示,相比于GCOA_E,在本文提出的GOAPSA控制下的系統(tǒng)可以充分利用終端設(shè)備上計算資源(即更高的終端設(shè)備計算資源利用率)來為更多應用提供有效的服務(即更高的有效服務應用請求數(shù))。

圖6 系統(tǒng)總功耗v.s.終端設(shè)備數(shù)Fig.6 Total system power consumption vs thenumber of terminal devices

圖7 有效服務的終端設(shè)備數(shù) v.s. 終端設(shè)備數(shù)Fig.7 The number of effective applications vs thenumber of terminal devices

圖8 終端設(shè)備計算資源利用率v.s.終端設(shè)備數(shù)Fig.8 The computing resource utilization rate on terminaldevices vs the number of terminal devices

5 結(jié)束語

本文研究了MEC系統(tǒng)下面向多應用的計算卸載、傳輸功率分配和應用處理方案的聯(lián)合設(shè)計,創(chuàng)新性地探究了終端間的計算共享機制以及多應用的處理順序?qū)τ嬎阗Y源利用率以及終端設(shè)備總能耗的影響,分析了多應用請求對時延的容許能力,因此在面向?qū)嶋H中多個不同種類的應用請求時,分析其對時延、計算資源等因素的需求狀態(tài),可以實現(xiàn)對多應用的有效服務。仿真實驗證明本文通過充分探究終端設(shè)備間的計算共享機制并靈活調(diào)整應用請求的處理順序可以有效降低系統(tǒng)的總功耗,并提高有效服務的應用請求數(shù)量,為實際中計算資源有限的MEC系統(tǒng)下的高效計算資源部署和配置方案提供了一種新的思路和解決方案。