基于邊緣計算的計算資源分配和偏分任務卸載算法

王喜鴻，王良成，張小波

（1三亞理工職業學院 海南 三亞 572000）

（2三亞學院 海南 三亞 572000）

0 引言

隨著移動設備和應用的飛速增加，對無線網絡的吞吐量、低延時提出了更高的需求[1]。為了解決用戶超低延時和用戶設備更低能耗的需求，歐洲電信標準協會（European Telecommunications Standard Institute，ETSI）提出了移動邊緣計算（mobile edge computing，MEC），其是在無線網絡內為附近用戶提供基礎IT和云服務。另外，還出現了許多中邊緣計算方式，如微云（cloudlets）、移動云計算（mobile cloud computing，MCC）、霧計算（fog computing）等。雖然概念十分相似，但是在技術上存在著非常大的差別。

1 MEC的概念

MEC是一種能夠解決資源受限移動設備和資源密集型應用的技術，其具有MEC的數據中心，且在無線接入點或蜂窩基站部署了云資源，從而使終端設備用戶和公有云數據中心的延遲得到了有效降低。MEC與MCC對比情況見表1。

表1 MEC與MCC對比情況

2 MEC的相關研究

當前關于MEC的相關研究包括資源分配、任務卸載兩個方面，因此主要研究目標主要集中以下幾方面。

2.1 降低任務處理時間

為了避免相同資源分配方案與用戶狀態的重復學習，采用多疊強化學習（reinforcement learning，RL）算法，同時對于頻譜分配、傳輸功率分配進行優化，以此來實現用戶之間的傳輸延遲最小化。也有非合作博弈方法，通過分布式迭代算法解決MEC任務，最小化任務執行延遲。

2.2 降低設備處理任務的能耗

胡錦天等[2]研究了MEC系統中時延敏感應用的節能任務接納，并且提出了約束條件下總能耗最小化邊緣服務器的計算資源和延遲。在時間截止、傳輸錯誤率等約束條件下，還提出了一種最小化移動設備能耗的卸載決策方法，并且該方法在可接受試驗和通信質量下具有良好的效果。

2.3 在設備能耗間和任務處理時間的平衡

MEC應用程序的任務卸載功能能夠提高移動設備的處理能力，并降低能耗，但其前提條件需集中在一個系統中。無線信道帶寬有限，而設備需要網絡資源，彼此之間會互相競爭，導致感染現象，降低數據傳輸速率，從而進一步延長數據傳輸時間[3]。另外，在邊緣云數據中心計算資源有限時，最佳選擇并不是邊緣云端將所有應用程序卸載。而是，當前的移動終端設備性能在逐漸提升，在終端中處理部分移動應用程序，在邊緣云數據中心處理另一部分，可以降低移動設備間數據傳輸時間延長的問題，并且對于數據中心計算資源的需求也可以顯著下降。

綜上所述，當前主要考慮的是任務卸載問題，如任務在本地設備處理、在邊緣云處理[4]。因此，針對MEC的邊緣云計算資源分配與偏分任務卸載問題開展研究。

3 設置MEC模型

典型的MEC系統，如下圖1所示。多個服務器構成的數據中心和N個物聯網設備構成了MEC系統模型。MEC系統模型，設物聯網設備i∈[1，2，…，N]的任務為i。物聯網設備中含有一個延遲敏感（delay-sensitive）、任務需要處理，而任務中需要大量的計算資源。通過本地設備、邊緣云數據中心對于任務進行處理。通過基站(base station，BS）實現物聯網設備對數據中心計算資源的訪問[5]。其中，Di為任務i的大小；F為邊緣云數據中心服務器的CPU頻率；λ∈（0，1）為任務i本地處理的比例；fi，t為物聯網設備任務i的CPU頻率大小；Ci為完成任務i所需的CPU周期數。

圖1 典型的MEC系統

3.1 本地計算模型

通過物聯網終端設備處理移動應用程序。fi，t為設備的計算能力，使用每秒CPU周期來衡量。因此，物聯網設備處理任務所需時間（Ti，t）和消耗的能耗（Ei，t）可表示為：

3.2 通信模型

利用無線信道，將應用程序卸載到邊緣云，可以獲得更多的上行鏈路傳輸能量和傳輸時間。上行傳輸的數據率（ri）可以表示為：

式中：Bi為分配給物聯網設備i的帶寬；q1為傳輸功率；h1為路徑損耗；N0為噪聲功率。

3.3 邊緣云計算模型

數據中心收到任務后重新分配計算資源，對于任務進行處理。假設其計算資源分配采用fi，e表示，那么其在邊緣云中的處理時間可表示為：

4 解決算法

4.1 問題構造

為了實現最小化系統計算開銷，構造的優化問題可表示為：

4.2 問題解決算法

通過定理1提出解決算法。

定理1 總是有supf（x，y）= supf∽（x，y）成立。其中，supf∽（x，y）= supf（x，y）。

上式表明，當最小化1個函數時，可以對部分變量優先進行優化，然后再對剩余變量進行優化。因此，可以將問題變成2個子問題：子題1邊緣云計算開銷的最小化；子題2本地計算開銷的最小化。其中，子題1可表達為：

其中，因為目標函數為凸函數，所以構造拉格朗日函數，并且基于凸優化中的KKT條件，得到以下結果：

通過式（7）、（8），可以了解到μ＞0，從而獲得：

5 基于MEC的負載均衡方案

基于大量密集型部署MEC服務器導致的高能量消耗，推出一種MEC服務器休眠的負載均衡方案。根據M/M/m多服務臺排隊理論，對于MEC服務器的卸載任務量進行建模，通過集合均值迭代比較算法，將卸載任務量劃分成2個不同卸載任務量集的MEC服務器集合，選擇卸載任務量較低的MEC服務器，通過休眠操作，降低系統能耗，保證網絡負載均衡。

5.1 系統模型

將1個宏基站和M各小區基站構成密集異構網絡，在小區基站側部MEC服務器，網絡用戶在MEC中卸載計算任務。設定每個MEC服務器的覆蓋范圍，假設用戶隨機接入，整個網絡的用戶卸載任務量會隨時間變化而變化[6]。

5.2 方案設計

假設網絡中一共有N個活躍狀態的MEC服務器，其休眠操作是以T為周期進行循環。在單個周期內操作步驟如下：

步驟1 宏基站獲取小區中MEC服務器卸載情況，根據預設卸載任務量閾值，得到MEC服務器休眠操作待選子集。在集合為0的情況下，表示當前周期T內MEC服務器不需要進行休眠操作。

步驟2 對于MEC服務器休眠操作待選子集，隨對應的卸載任務量集合排序后，進行MEC服務器休眠操作。

步驟3 執行集合均值迭代比較算法，在第i次進行計算平均卸載任務量的過程中，系統對集合中最后1個MEC服務器中的卸載任務量MEC服務器集合的算數平均值，如果該值大于或等于卸載任務量，則可以認為從MEC服務器開始，集合中各個MEC服務器的卸載任務量均低于平均卸載任務量。因此，該算法可以分為步驟3.1和步驟3.2這2個卸載任務量級別不同的集合，其中步驟3.1為卸載任務量較小的集合，可以將其納入休眠操作范圍；而步驟3.2為卸載任務量較大的集合，繼續保持活躍狀態[7]。

步驟4 根據步驟3的結果，選擇步驟3.1作為需要執行休眠操作的MEC服務器集合，宏基站將休眠信號發送到小區中的MEC服務器之前，詳細步驟3.1中的MEC服務器執行休眠操作是否會出現服務質量退化的情況。如果滿足該條件，則選擇相應的MEC服務器執行休眠操作。

在執行完上述步驟之后，進入單周期內的MEC服務器技術休眠操作流程，在下一個周期到來前，系統從最初步驟開始執行。通常情況下，當系統中的卸載任務量較少時，如果網絡中的MEC服務器保持活躍狀態的話，會消耗大量的能量，因此需要執行休眠操作，避免卸載任務量過少的空閑MEC服務器而產生大量能耗[8]。當系統中需要MEC服務器處理的卸載任務量增加之后，此時保持活躍狀態的MEC服務器所可以服務的卸載任務量會達到上限，隨后通知處于休眠狀態的MEC服務器進入活躍狀態，對于卸載任務量進行高效處理。

6 仿真實驗

6.1 設置參數

一個MEC系統中共有N個（N=5）設備，對于物聯網的參數設置見表2。本文研究更側重于部分任務卸載情景。

表2 參數設置

6.2 實驗結果

為了對于本文提出的算法有效性進行驗證，對于本地任務處理(local)（本地設備端處理所有的任務）和邊緣云任務處理（edge cloud）（所有任務均經過邊緣云設備端進行處理）進行對比。

物聯網設備的任務選擇決定如上圖2所示，物聯網設備的任務是由不同帶寬值來選擇確定的。其中，0表示任務卸載到了本地設備，而1表示物聯網設備將任務卸載到了邊緣云。可以看出，如設備1和設備2需要計算資源較少。如果帶寬值較小，則物聯網設備可以在邊緣云卸載任務，然后處理任務。

圖2 物聯網設備的任務選擇決定

隨寬帶變化的任務處理時間變化情況，如下圖3所示。其中，系統代價是以任務處理時間和能耗來進行判斷的。網絡帶寬值較小時，各個方面更大。

圖3 隨寬帶變化的任務處理時間變化情況

本地處理所需時間最小情境下的算法最低能耗如圖4所示，本地處理消耗的能量逐漸高于邊緣云處理所消耗的能量。

圖4 隨著寬帶變化的任務處理時間的變化

隨著網絡帶寬值的增加，邊緣云處理的系統代價要低于本地處理，系統代價更小，證實了算法的有效性。系統代價隨著寬帶的變化情況，如圖5所示。

圖5 系統代價隨著寬帶的變化情況

7 總結

綜上所述，因為當前多MEC服務器部署下，考慮到用戶和服務器效益，導致卸載和資源分配的難度大大提升。通過研究邊緣計算的計算資源分配和任務卸載問題，提出了任務卸載與計算資源分配算法，結果表明可以有效降低任務處理的能耗和延遲。