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

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

0 引言

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

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

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

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

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

1.1 系統(tǒng)模型

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

1.1.1 應(yīng)用卸載模型

(1)

(2)

1.1.2 應(yīng)用響應(yīng)時(shí)延模型

(3)

(4)

終端設(shè)備m的應(yīng)用請(qǐng)求通過(guò)無(wú)線通信鏈路上傳到終端設(shè)備m′后,應(yīng)用處理時(shí)延可表示為:

(5)

(6)

(7)

(8)

1.1.3 功耗模型

(9)

(10)

(11)

1.1.4 應(yīng)用處理順序模型

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

(12)

(13)

(14)

(15)

(16)

1.2 問(wèn)題建模

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

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

2 問(wèn)題求解與算法設(shè)計(jì)

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

(17)

(18)

(19)

(20)

(21)

(22)

(23)

(24)

(25)

(26)

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

算法1:GOAPSA1. 輸出:最優(yōu)的任務(wù)卸載決策α?,卸載功耗決策Poff,?,應(yīng)用處理順序變量?。2. 對(duì)所有終端設(shè)備m∈,如果cm≤Cm,?mcm≤Pm,令m(1)=m。3. Repeat4. 根據(jù)式(20)對(duì)?m∈求出對(duì)應(yīng)的can-offm。5. 對(duì)?m∈令αmm′=1,其中m′=argmaxm″∈{can-offm,C}hHm,m″。6. 求出over={m∈∑m′∈offmαm′mcm′>Cm∪Pm>Pmaxm},即過(guò)度使用的終端設(shè)備集合。7. Whileover≠?8. For i=1 toover9. 對(duì)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. 對(duì)?m∈,C,所有的最大容許時(shí)延排序表示為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. 對(duì)?m∈,根據(jù)式(25)和式(26)求出Poffm(i),m。

3 算法復(fù)雜度分析

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

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

4.1 仿真場(chǎng)景設(shè)置

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

4.2 仿真結(jié)果

圖3展示了本文提出GOAPSA迭代次數(shù)與終端設(shè)備數(shù)間的關(guān)系,顯然隨著終端設(shè)備的數(shù)量增加,GOAPSA的迭代次數(shù)也隨之增加。當(dāng)終端設(shè)備數(shù)較大時(shí)(例如終端設(shè)備數(shù)為70或80時(shí)),本文的迭代次數(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 有效服務(wù)終端個(gè)數(shù)v.s.CmFig.5 The number of effective applications vs Cm

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

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

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

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

5 結(jié)束語(yǔ)

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