黃星，殷鋒，袁平

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

0 引言

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

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

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

1 理論基礎(chǔ)

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

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

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

2 研究現(xiàn)狀

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

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

考慮到資源利用效率，一般不考慮單用戶多服務(wù)器的邊緣計算系統(tǒng)，因為它的資源利用率很低，所以單用戶邊緣計算系統(tǒng)一般是指由一個邊緣設(shè)備和一個邊緣服務(wù)器組成的系統(tǒng)。

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

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

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

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

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

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

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

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

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

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

3 結(jié)語

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