MEC 系統(tǒng)中的資源分配算法研究綜述

黃星，殷鋒，袁平

（1.四川大學(xué)計(jì)算機(jī)學(xué)院，成都 610065；2.西南民族大學(xué)圖書館，成都 610041；3.重慶第二師范學(xué)院數(shù)學(xué)與信息工程學(xué)院，重慶 400067）

0 引言

近些年，物聯(lián)網(wǎng)的快速發(fā)展使得需要處理的數(shù)據(jù)量大大增加，增強(qiáng)現(xiàn)實(shí)（Augmented Reality，AR）、虛擬現(xiàn)實(shí)（Virtual Reality，VR）等各種新興應(yīng)用的出現(xiàn)又對(duì)時(shí)延和帶寬提出了更高的要求。邊緣設(shè)備的計(jì)算和存儲(chǔ)能力太弱，無(wú)法處理和存儲(chǔ)龐大的數(shù)據(jù)。另外，執(zhí)行計(jì)算集中型任務(wù)所消耗的能量對(duì)于能量有限的邊緣設(shè)備來(lái)說(shuō)也是一個(gè)很大的挑戰(zhàn)。

為了解決邊緣設(shè)備計(jì)算和存儲(chǔ)能力不足的問(wèn)題，移動(dòng)云計(jì)算（Mobile Cloud Computing，MCC）應(yīng)運(yùn)而生。在移動(dòng)云計(jì)算中，可以通過(guò)將邊緣設(shè)備所產(chǎn)生的計(jì)算任務(wù)卸載到云服務(wù)器中進(jìn)行計(jì)算來(lái)增強(qiáng)邊緣設(shè)備的計(jì)算和存儲(chǔ)能力，并且延長(zhǎng)移動(dòng)設(shè)備的運(yùn)行時(shí)間。但是，這樣做會(huì)導(dǎo)致三個(gè)問(wèn)題：①邊緣設(shè)備和云端的距離太過(guò)遙遠(yuǎn)，從而使得傳輸時(shí)延和總的通信時(shí)延都很高，這無(wú)法滿足各種新興應(yīng)用的毫秒級(jí)時(shí)延要求。②整個(gè)物聯(lián)網(wǎng)每年產(chǎn)生的數(shù)據(jù)量非常龐大，據(jù)思科全球云指數(shù)白皮書[1]中顯示，2019 年，人和物產(chǎn)生的總數(shù)據(jù)量達(dá)到了500ZB，而全球云數(shù)據(jù)中心的網(wǎng)絡(luò)流量?jī)H能達(dá)到1ZB，也就是說(shuō)網(wǎng)絡(luò)容量是遠(yuǎn)遠(yuǎn)達(dá)不到物聯(lián)網(wǎng)所產(chǎn)生的數(shù)據(jù)量的。假設(shè)將大部分?jǐn)?shù)據(jù)傳輸?shù)皆贫诉M(jìn)行處理，勢(shì)必會(huì)給主干網(wǎng)絡(luò)帶來(lái)極大的壓力，極有可能導(dǎo)致網(wǎng)絡(luò)阻塞甚至癱瘓。③原始數(shù)據(jù)包含著大量隱私，從邊緣設(shè)備到云服務(wù)器的傳輸鏈路過(guò)長(zhǎng)會(huì)使得隱私泄露的可能性增大。

歐洲電信標(biāo)準(zhǔn)化協(xié)會(huì)（European Telecommunications Standards Institute，ETSI）在 2014 年提出了移動(dòng)邊緣計(jì)算（Mobile Edge Computing，MEC）來(lái)主要解決長(zhǎng)時(shí)延和網(wǎng)絡(luò)容量不足問(wèn)題。作為邊緣計(jì)算概念的一種主要形式，移動(dòng)邊緣計(jì)算的主要定義為：在網(wǎng)絡(luò)邊緣向應(yīng)用開發(fā)者和內(nèi)容提供者提供云計(jì)算能力和IT 服務(wù)環(huán)境。相比于移動(dòng)云計(jì)算，移動(dòng)邊緣計(jì)算可以將計(jì)算任務(wù)卸載至邊緣服務(wù)器，并不經(jīng)過(guò)廣域網(wǎng)，從而達(dá)到既減少時(shí)延和能耗，又緩解網(wǎng)絡(luò)帶寬壓力的目的。

1 理論基礎(chǔ)

移動(dòng)邊緣計(jì)算和移動(dòng)云計(jì)算中在計(jì)算卸載技術(shù)上唯一的不同就是卸載的目的地不同，前者是將計(jì)算任務(wù)卸載至邊緣服務(wù)器中執(zhí)行，后者是將計(jì)算任務(wù)卸載至云服務(wù)器中執(zhí)行。計(jì)算卸載技術(shù)最重要的兩步是卸載決策和卸載計(jì)算資源分配[2]。卸載決策所解決的是是否卸載、卸載多少計(jì)算量和卸載哪部分計(jì)算量的問(wèn)題，卸載計(jì)算資源分配所解決的則是在有多個(gè)邊緣服務(wù)器的情況下，選擇將計(jì)算任務(wù)卸載到哪個(gè)邊緣服務(wù)器的問(wèn)題[3]。卸載決策的目的是計(jì)算所要卸載的任務(wù)大小以及具體的任務(wù)部分（如果不卸載，卸載的任務(wù)大小為0），而卸載計(jì)算資源分配的目的是決定卸載的目標(biāo)服務(wù)器（一般在多邊緣服務(wù)器場(chǎng)景下）。這兩者都涉及計(jì)算資源分配，在比較復(fù)雜的邊緣計(jì)算系統(tǒng)中，往往還需要考慮無(wú)線資源分配，因此，資源分配是計(jì)算卸載過(guò)程中所要解決的關(guān)鍵問(wèn)題，主要包括計(jì)算資源分配和無(wú)線資源分配。

卸載決策可以分為完全卸載和部分卸載兩類。完全卸載指的是將全部計(jì)算任務(wù)都卸載至邊緣服務(wù)器或其它服務(wù)器中執(zhí)行，而部分卸載則只是將部分計(jì)算任務(wù)卸載至服務(wù)器中執(zhí)行，剩下的計(jì)算任務(wù)還在本地執(zhí)行。

考慮到卸載任務(wù)的并行性，卸載計(jì)算資源分配可以分為單點(diǎn)計(jì)算資源分配和多點(diǎn)計(jì)算資源分配。當(dāng)卸載任務(wù)不能被切分，即不能并行執(zhí)行時(shí)，那么就只將卸載任務(wù)卸載至單個(gè)節(jié)點(diǎn)，等效于將單個(gè)節(jié)點(diǎn)的計(jì)算資源分配于該任務(wù)。如果卸載任務(wù)還可以被切分，可以并行執(zhí)行，那么就可以將其切分，再把切分后的計(jì)算任務(wù)分配至多個(gè)節(jié)點(diǎn)處執(zhí)行，這就是多點(diǎn)計(jì)算資源分配。

2 研究現(xiàn)狀

按照邊緣計(jì)算系統(tǒng)的規(guī)模來(lái)分，可以把資源分配問(wèn)題分為三類：?jiǎn)斡脩暨吘売?jì)算系統(tǒng)、多用戶邊緣計(jì)算系統(tǒng)和異構(gòu)服務(wù)器邊緣計(jì)算系統(tǒng)。下面介紹關(guān)于這三類資源分配問(wèn)題的研究現(xiàn)狀。

（1）單用戶邊緣計(jì)算系統(tǒng)

考慮到資源利用效率，一般不考慮單用戶多服務(wù)器的邊緣計(jì)算系統(tǒng)，因?yàn)樗馁Y源利用率很低，所以單用戶邊緣計(jì)算系統(tǒng)一般是指由一個(gè)邊緣設(shè)備和一個(gè)邊緣服務(wù)器組成的系統(tǒng)。

為了得到計(jì)算卸載發(fā)生的條件，Salvador 等人同時(shí)對(duì)計(jì)算時(shí)間和通信時(shí)間進(jìn)行建模，得到了任務(wù)在本地計(jì)算和卸載到服務(wù)器計(jì)算兩種情況的完成時(shí)間[4]。之前的研究表明，只考慮時(shí)延的話，當(dāng)任務(wù)在本地計(jì)算的時(shí)延比卸載到服務(wù)器執(zhí)行的時(shí)延還要高時(shí)，就可考慮卸載[5]。Salvador 等人為了得到邊緣計(jì)算系統(tǒng)參數(shù)和卸載任務(wù)參數(shù)之間的關(guān)系，引入了CCR（Computation-to-Communication Ratio）和 RLR（Remote-to-Local Ratio）兩個(gè)參數(shù)對(duì)計(jì)算卸載發(fā)生的條件進(jìn)行分析，得出了CCR 和RLR 的不等式。作者假設(shè)通信系統(tǒng)處于非阻塞情況下，去掉排隊(duì)時(shí)延和轉(zhuǎn)發(fā)時(shí)延，最后得到了邊緣計(jì)算系統(tǒng)參數(shù)和計(jì)算任務(wù)參數(shù)的不等式。該不等式可以作為卸載決策的參考公式，滿足這個(gè)不等式的計(jì)算任務(wù)才可以被卸載到邊緣服務(wù)器中執(zhí)行。

和文獻(xiàn)[4]研究的問(wèn)題不同，文獻(xiàn)[6]研究的是怎樣在給定完成時(shí)間的約束下，最小化移動(dòng)設(shè)備的能耗的問(wèn)題。邊緣設(shè)備所產(chǎn)生的計(jì)算任務(wù)要么在本地執(zhí)行，要么卸載到服務(wù)器處執(zhí)行。作者假設(shè)任務(wù)不可分割，只能全部卸載，于是當(dāng)計(jì)算任務(wù)在邊緣設(shè)備執(zhí)行時(shí)，只需要考慮邊緣設(shè)備的計(jì)算能耗，當(dāng)計(jì)算任務(wù)在服務(wù)器處執(zhí)行時(shí)，只需要考慮無(wú)線通信的能耗。本文作者提出隨機(jī)無(wú)線信道下最小化邊緣設(shè)備能耗的框架。當(dāng)計(jì)算任務(wù)在邊緣設(shè)備執(zhí)行時(shí)，通過(guò)動(dòng)態(tài)調(diào)整時(shí)鐘頻率來(lái)最小化CPU 能耗；當(dāng)計(jì)算任務(wù)在服務(wù)器處執(zhí)行時(shí)，通過(guò)調(diào)整邊緣設(shè)備的無(wú)線傳輸功率來(lái)最小化無(wú)線通信能耗。通過(guò)對(duì)這兩個(gè)調(diào)度問(wèn)題的求解，得到了最佳卸載決策，從而最小化邊緣設(shè)備的能耗。

雖然文獻(xiàn)[6]給出了在給定時(shí)間約束下，如何調(diào)度和分配計(jì)算資源和存儲(chǔ)資源以最小化能耗的問(wèn)題的解，但是它忽略了任務(wù)間的依賴。文獻(xiàn)[7]則考慮了任務(wù)間的依賴，并且由于現(xiàn)有移動(dòng)設(shè)備大多具備多核CPU，所以該文把邊緣設(shè)備邏輯表示為多個(gè)CPU 核的集合。在該文獻(xiàn)中，作者研究在滿足給定時(shí)間的約束的條件下，如何利用big.LITTLE 架構(gòu)來(lái)最小化能耗。首先對(duì)計(jì)算和存儲(chǔ)資源的分配問(wèn)題進(jìn)行建模，再結(jié)合模型把物理問(wèn)題形式化為混合整數(shù)非線性規(guī)劃問(wèn)題，然后提出啟發(fā)式算法來(lái)解決該卸載決策和任務(wù)調(diào)度問(wèn)題。該啟發(fā)式算法分成三個(gè)階段：第一個(gè)階段是初始化階段，目的是在滿足任務(wù)依賴約束的條件下，最小化時(shí)間；第二個(gè)階段是任務(wù)重分配階段，基于關(guān)鍵路徑，重新分配任務(wù)以最小化能耗，當(dāng)然前提是不超過(guò)完成時(shí)間約束；最后一個(gè)階段是對(duì)第二階段的補(bǔ)充，如果這時(shí)還有剩余完成時(shí)間，那么可以應(yīng)用動(dòng)態(tài)電壓頻率調(diào)整技術(shù)（Dynamic Voltage Frequency Scaling，DVFS）來(lái)進(jìn)一步降低能耗。實(shí)驗(yàn)表明，和其他方法相比，能耗最少可以降低24.1%。

（2）多用戶邊緣計(jì)算系統(tǒng)

多用戶邊緣計(jì)算系統(tǒng)一般是指多個(gè)用戶和一個(gè)邊緣服務(wù)器組成的系統(tǒng)。

在文獻(xiàn)[8]中，計(jì)算資源和無(wú)線通信資源都是邊緣服務(wù)器來(lái)集中分配的。為了解決集中式資源分配問(wèn)題，作者先是通過(guò)建立無(wú)線通信模型和計(jì)算模型將聯(lián)合無(wú)線和計(jì)算資源優(yōu)化問(wèn)題抽象化為凸優(yōu)化問(wèn)題，然后用拉格朗日乘子法求出凸優(yōu)化問(wèn)題的解。除此之外，作者還得出分配給每個(gè)信道的傳輸能量和分配給相關(guān)用戶的CPU 周期數(shù)之間存在著一一映射的關(guān)系，并且提出一種許可控制策略，其核心思想是允許的任務(wù)傳輸?shù)竭吘壧幚?，不允許的任務(wù)就在本地處理，這樣不僅可以保證邊緣服務(wù)器不過(guò)載，也保證了邊緣設(shè)備任務(wù)隊(duì)列的穩(wěn)定性。

與文獻(xiàn)[8]不同，文獻(xiàn)[9]解決的是分布式資源分配問(wèn)題。分布式資源分配問(wèn)題的定義是邊緣設(shè)備執(zhí)行資源分配過(guò)程，而集中式資源分配問(wèn)題的定義是服務(wù)器執(zhí)行該過(guò)程。作者先對(duì)計(jì)算資源和無(wú)線資源分配問(wèn)題進(jìn)行建模，再把它形式化為多用戶卸載博弈問(wèn)題并證明該卸載博弈問(wèn)題存在納什均衡。基于此，作者提出分布式計(jì)算卸載算法，得出了聚合時(shí)間的上限和系統(tǒng)總代價(jià)。實(shí)驗(yàn)結(jié)果證明，和其他算法相比，該算法的系統(tǒng)總代價(jià)，也就是時(shí)延和能耗的加權(quán)最少降低51%。

（3）異構(gòu)服務(wù)器邊緣計(jì)算系統(tǒng)

異構(gòu)服務(wù)器邊緣計(jì)算系統(tǒng)一般是指多個(gè)服務(wù)器和多個(gè)邊緣服務(wù)器組成的系統(tǒng)，有的研究把云服務(wù)器加入這個(gè)系統(tǒng)組成端-邊-云三層架構(gòu)。

文獻(xiàn)[10]考慮由邊緣設(shè)備、邊緣云和遠(yuǎn)端云所組成的三層系統(tǒng)架構(gòu)，其中邊緣云由多個(gè)邊緣服務(wù)器組成。由于邊緣云的計(jì)算能力和存儲(chǔ)能力有限，因此要考慮多用戶之間資源競(jìng)爭(zhēng)的問(wèn)題。作者利用排隊(duì)論來(lái)建立多用戶資源競(jìng)爭(zhēng)模型來(lái)獲取用戶交互信息和計(jì)算卸載對(duì)用戶感知性能的影響。作者隨后根據(jù)該模型將多用戶資源競(jìng)爭(zhēng)問(wèn)題形式化為廣義納什均衡問(wèn)題，也稱非合作博弈問(wèn)題。在深入分析均衡問(wèn)題的基礎(chǔ)上，提出了適合問(wèn)題結(jié)構(gòu)的分布式均衡算法。實(shí)驗(yàn)結(jié)果表明，響應(yīng)時(shí)延比其他方法降低了20%以上的時(shí)延。

3 結(jié)語(yǔ)

本文詳細(xì)介紹了資源分配問(wèn)題的分類和研究現(xiàn)狀。從上述文獻(xiàn)中可看出，資源分配算法在本質(zhì)上是等同于計(jì)算卸載的。雖然目前對(duì)資源分配算法的研究文章較多，但仍有不少問(wèn)題等著學(xué)者去研究解決，例如在線任務(wù)切分，大規(guī)模的系統(tǒng)優(yōu)化。