MEC 系統中的資源分配算法研究綜述

黃星，殷鋒，袁平

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

0 引言

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

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

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

1 理論基礎

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

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

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

2 研究現狀

按照邊緣計算系統的規模來分，可以把資源分配問題分為三類：單用戶邊緣計算系統、多用戶邊緣計算系統和異構服務器邊緣計算系統。下面介紹關于這三類資源分配問題的研究現狀。

（1）單用戶邊緣計算系統

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

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

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

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

（2）多用戶邊緣計算系統

多用戶邊緣計算系統一般是指多個用戶和一個邊緣服務器組成的系統。

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

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

（3）異構服務器邊緣計算系統

異構服務器邊緣計算系統一般是指多個服務器和多個邊緣服務器組成的系統，有的研究把云服務器加入這個系統組成端-邊-云三層架構。

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

3 結語

本文詳細介紹了資源分配問題的分類和研究現狀。從上述文獻中可看出，資源分配算法在本質上是等同于計算卸載的。雖然目前對資源分配算法的研究文章較多，但仍有不少問題等著學者去研究解決，例如在線任務切分，大規模的系統優化。