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

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

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

0 引言

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

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

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

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

1 模型構建與問題建模

1.1 系統模型

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

1.1.1 應用卸載模型

(1)

(2)

1.1.2 應用響應時延模型

(3)

(4)

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

(5)

(6)

(7)

(8)

1.1.3 功耗模型

(9)

(10)

(11)

1.1.4 應用處理順序模型

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

(12)

(13)

(14)

(15)

(16)

1.2 問題建模

綜上所述,本文考慮終端設備有限的計算資源、有限的功率供應和應用請求處理的時延約束,最小化系統終端設備的總功率消耗。總體優化問題可規劃為如下P1問題:

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

2 問題求解與算法設計

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

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

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

算法1:GOAPSA1. 輸出:最優的任務卸載決策α?,卸載功耗決策Poff,?,應用處理順序變量?。2. 對所有終端設備m∈,如果cm≤Cm,?mcm≤Pm,令m(1)=m。3. Repeat4. 根據式(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},即過度使用的終端設備集合。7. Whileover≠?8. For i=1 toover9. 對m∈offi求出其最小卸載功率向量Poff-minm={Poff-minm,1,Poff-minm,2,…,Poff-minm,M,Poff-minm,C}。10. 根據式(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∈,根據式(25)和式(26)求出Poffm(i),m。

3 算法復雜度分析

4 仿真結果與分析

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

4.1 仿真場景設置

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

4.2 仿真結果

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

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

圖4 系統總功耗v.s.CmFig.4 Total system power consumption vs Cm

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

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

圖6 系統總功耗v.s.終端設備數Fig.6 Total system power consumption vs thenumber of terminal devices

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

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

5 結束語

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