基于單用戶和分類任務的MEC任務卸載策略及性能優化

李小良，李 偉，金順福,*

(1. 開灤集團 信息與控制中心，河北 唐山 063018；2. 燕山大學 信息科學與工程學院，河北 秦皇島 066004)

0 引言

隨著移動設備使用數目的增加以及5G技術的飛速發展，人們開始對數據計算等有了更高的要求。根據互聯網數據中心(Internet Data Center, IDC)報告[1]，預計到2025年，全球數據總量將會超過163 ZB，這其中有超過40%的數據將在網絡邊緣處理。面對網絡新時代，傳統的云計算平臺暴露出了實時性差、阻塞率高、能耗開銷大等諸多不足[2]。為了用戶的網絡服務體驗，移動邊緣計算(Mobile Edge Computing, MEC)的范式應運而生[3-4]。MEC平臺下的任務卸載策略問題成為相關領域的研究熱點。

為了制定合理的任務卸載策略，近年來，國內外諸多學者已經進行了大量工作。Kuo等[5]搭建了關于MEC的能量消耗模型，提出了一種系統級方法用于找尋任務卸載過程中最佳的節能方案。為了使MEC中能耗達到最優水平，Long等[6]提出了一個邊緣云協作架構，并將框架中計算卸載問題建模為一個帶有約束的NP難題，應用貪心算法以及模擬退火算法得出了最佳計算卸載方案。龍隆等[7]提出了一種基于博弈論的計算卸載與資源分配的聯合優化算法，用于解決MEC中移動終端產生的高時延問題。上述文獻對MEC系統卸載策略問題的研究均局限于一個度量角度，不能夠全面地提升用戶體驗。

針對不同應用情景下的MEC服務，研究人員搭建出了各具特色的MEC系統框架。為了研究MEC環境下車輛的能耗和延遲等問題，Yang等[8]搭建了一個由多臺同構虛擬機組成的車輛MEC框架，并設法解決任務卸載決策和計算資源分配的聯合優化問題。Delfin等[9]搭建了一個由用戶層、霧計算層和云層等三部分組成的霧計算框架。通過在霧計算層配備多臺同構虛擬機，縮減了用戶的請求響應時間。Li等[10]提出了一種由邊緣和云共同組成的邊緣云架構，云負責管理和監視邊緣中的資源和服務，而邊緣則負責處理分配給自己的服務請求。上述文獻所構建的MEC系統框架考慮的均為同構邊緣。然而，在實際MEC情景中，邊緣往往是異構的，即分布在MEC邊緣處的計算資源種類多樣，計算能力存在一定差異。

本文對整體智能家居等專用MEC應用情景中的卸載問題進行研究，考慮不同任務的處理需求，提出一種基于單用戶和任務分類的MEC任務卸載策略。搭建帶有異構邊緣的MEC系統框架，建立由M/M/1、M/M/c和M/M/∞等經典排隊組成的系統模型，評估基于單用戶和任務分類的MEC任務卸載策略的系統性能，并進行系統實驗。以最小化系統成本為目標，應用卡羅需-庫恩-塔克(Karush-Kuhn-Tucker, KKT)條件方法，給出任務卸載策略聯合優化方案。

1 MEC系統框架及任務卸載策略

1.1 MEC系統框架

在整體智能家居等專用MEC應用場景中，家庭網關通常會同時收到來自家庭內部的多種數據任務[11]。這些任務或者直接在本地處理，或者被卸載到網絡邊緣和云端。結合整體智能家居等專用MEC的應用特點，在MEC系統中，引入分類處理機制，將任務劃分為低速、中速和高速等三類。為了充分滿足各類任務的處理需求，搭建基于單用戶和任務分類的MEC系統架構，如圖1所示。

圖1 基于單用戶和任務分類的MEC系統架構Fig.1 Architecture of a MEC system based on single-user and tasks classification

圖1所示的MEC系統架構由本地端、基站、邊緣端和云端四部分組成。本地端和邊緣端分別部署了一臺任務調度器，用來實施任務的卸載策略。通過調節任務調度器上的任務卸載策略參數，實現各類任務在MEC系統中的合理分配。

在本地端，考慮一名用戶(單臺移動設備)的接入。本地端配備有本地調度器、本地處理器、本地發送端口和本地接收端口等裝置，分別用于實現任務在本地端的決策、處理、發送和接收等功能。本地處理器、本地發送端口和本地接收端口各自帶有一個容量不限的緩存空間。當本地處理器、本地發送端口或本地接收端口被占用時，新到來的任務會在緩存區中排隊等待。

邊緣端配備有MEC調度器、MEC服務器和MEC發送機等裝置，分別用于實現任務在邊緣端的決策、處理和發送。MEC服務器是異構的，它由三簇物理機構成。這些物理機分別被命名為簇1、簇2和簇3，每簇物理機的數目不盡相同。處在同一簇中的物理機具有相同的任務處理速率且共享一個緩存。處在不同簇的物理機具有不同的任務處理速率：簇1中物理機任務處理速率相對較低，適合于低速類任務；簇2中物理機的任務處理速率居中，適合于中速類任務；簇3中物理機的任務處理速率相對較高，適合于高速類任務。

云端上部署著大量云服務器，這些服務器有著強大的計算能力，用于處理卸載到云端的全部任務。同時云端還擁有眾多大功率發送機，用于發送被云服務器處理完畢的任務。

1.2 MEC任務卸載策略

結合1.1節所搭建的MEC系統架構，提出一種基于單用戶和任務分類的MEC任務卸載策略。

在移動設備上生成的任務被劃分為低速、中速或高速中的某一類。根據本地調度器上設定的此類任務卸載策略參數，該任務以一定概率送到本地處理器，以一定的概率送往本地輸出端口。任務在本地端接受處理時，不會進行類別的區分。

送往本地輸出端口的任務卸載到邊緣端或者云端進行處理。卸載的任務在離開本地發送端口后，進入傳輸信道，經過附近基站的轉發，最終抵達邊緣端。任務在抵達邊緣端后，根據MEC調度器上設置的此類任務卸載策略參數，該任務以一定的概率在MEC服務器上接受處理，以一定的概率卸載到云端進行處理。根據任務類別，在MEC調度器的控制下，MEC服務器上的任務被分配到相對應的物理機簇上接受處理。各類任務在物理機上處理結束后，由MEC發送機統一發送。發送后的任務經過傳輸信道再次回到本地端，并由本地接收端口進行接收。

如果任務被卸載到云端進行處理，那么任務在離開邊緣端后會再次經過傳輸信道傳輸到云端。考慮到云服務器數目眾多且計算能力強大，任務在云端處不再進行種類區分，全部由云服務器進行處理。各類任務在處理完畢后，由云發送機發送到傳輸信道返回本地端，由本地接收端口進行接收。

2 系統模型

2.1 本地計算模型

抽象任務在基于單用戶和分類任務的MEC任務卸載策略下的行為，將不同類任務看作多類顧客，本地處理器、本地發送端口、本地接收端口、物理機、MEC發送機、云服務器和云發送機等看作服務臺，將對任務的處理、發送和接收等過程看作對顧客的服務過程。根據任務在各處服務臺上的服務特點，將基于單用戶和任務分類的MEC任務卸載策略建模為一個具有單輸入流與多類顧客的排隊模型。

(1)

其中，θ為一個任務包含的平均數據量。

(2)

被卸載的任務首先需要經過本地發送端口的發送。假設任務在本地發送端口上的發送時間服從相同的負指數分布。那么任務在本地發送端口上的發送過程可以看作是一個M/M/1排隊。

令rop表示本地發送端口單位時間內發送的數據量，則rop的表達式為

(3)

根據M/M/1排隊的理論分析結果，可以得出任務在本地發送端口的平均逗留時間top如式

(4)

卸載處理的任務經過MEC發送機或云發送機返回本地端，并由本地接收端口進行接收。假設各個任務在本地接收端口的接收時間服從相同的負指數分布，那么任務在本地接收端口的接收過程可以看作是一個M/M/1排隊。令rrp表示本地接收端口單位時間內接收的數據量。任務在本地接收端口的平均逗留時間trp為

(5)

2.2 邊緣計算模型

(6)

其中，s1為本地端與邊緣端之間的信道長度，v是任務在信道中的傳輸速率(m/s)。

MEC服務器上的三簇物理機各司其職，分別用來處理低速類、中速類和高速類等三類任務。假設任務在同一簇物理機上的處理時間服從相同的負指數分布，那么任務在MEC服務器上的處理過程可看作一個M/M/c排隊。設簇i(i=1,2,3)中有ci臺物理機，每臺物理機的處理速率均為μi。根據M/M/c排隊的理論分析結果，任務在簇i物理機上的平均逗留時間ti為

(7)

任務在MEC服務器上處理完畢后，將送往MEC發送機。假設任務在MEC發送機上的發送時間服從相同的負指數分布，那么任務在MEC發送機上的發送過程可以看作一個M/M/1排隊。

令res表示單位時間內由MEC發送機發出的數據量。任務在MEC發送機上的平均逗留時間tes為

(8)

2.3 云端計算模型

(9)

其中，v為任務在傳輸信道的傳輸速度。

考慮到云服務器強大的計算能力，假設任務在到達云端后，可以立刻在云服務器上接受處理。假設任務在云服務器上的處理時間服從相同的負指數分布，任務在云服務器上的處理過程可以看作是一個M/M/∞排隊。此時，任務在云服務器上的逗留時間即為任務在云服務器上的處理時間。

設任務在云服務器上的處理速率為μcd，即單位時間內云服務器處理的任務個數。任務在云服務器上的平均逗留時間tcd為

(10)

任務在云服務器上處理完畢后，由云發送機返回到本地端。考慮云發送機強大的發送能力，假設任務在被送往云發送機后，將立刻進行發送。假設任務在云發送機上的發送時間服從相同的負指數分布，任務在云發送機上的發送過程可以看作是一個M/M/∞排隊。此時，任務在云發送機上的逗留時間即為任務在云發送機上的發送時間。

令rcs表示云發送機的發送能力(bit/s)，即單位時間內云發送機發送的數據量。任務在云發送機上的平均逗留時間tcs為

(11)

3 策略性能評估

為了評估MEC任務卸載策略的系統性能，求解各類任務的平均處理時延和各類任務對應的移動設備能耗水平。

在計算各類任務的平均處理時延時，需要同時考慮任務的本地處理、任務的上行和任務的下行三個過程。

(12)

(13)

(14)

移動設備的能耗包含本地處理器處理任務時的能耗、本地發送端口發送任務時的能耗和本地接收端口接收任務時的能耗等三部分。

在實際應用中，任務在本地處理器緩存中等待時的能耗要遠小于任務在本地處理器中進行處理的能耗。設本地處理器的功率ηlp為

ηlp=γ1f?+γ2，

(15)

其中，?、γ1和γ2均是與本地處理器芯片有關的參數，可由文獻[14]方法測量得出。

本地處理器每處理一個任務，移動設備的平均能耗ψlp為

(16)

設本地發送端口的功率為ηop，本地發送端口每發送一個任務，移動設備的平均能耗ψop為

(17)

設本地接收端口的功率為ηrp，本地接收端口每接收一個任務，移動設備的平均能耗ψrp為

(18)

(19)

4 系統實驗

進行系統實驗，分析任務種類、任務比重以及任務本地處理概率對系統性能的影響。系統實驗在MATLAB R2011a環境下進行，文獻[15]在保證系統穩定的條件下的設置實驗參數如表1所示。

表1 實驗參數設置Tab.1 Parameters setting in experiments

利用表1設定的實驗參數，針對不同任務比重，給出三類任務的平均處理時延變化趨勢，如圖2所示。

在圖2(a)中，低速類任務在三類任務比重下對應的最小平均處理時延分別為4.403 ms、4.522 ms和4.716 ms；圖2(b)中，中速類任務在三類任務比重下對應的最小平均處理時延分別為 4.386 ms、4.508 ms和4.685 ms；圖2(c)中，高速類任務在三類任務比重下對應的最小平均處理時延分別為4.368 ms、4.492 ms和4.662 ms。

(a) 低速類任務

從圖2實驗的數值結果可以看出，在相同的任務到達率下，某類任務比重的增大會引起該類任務最小平均處理時延的增大。此外，在相同的任務比重下，不同種類的任務之間的最小平均處理時延存在差異。任務響應程度越高，最小平均處理時延越小，這是由于MEC服務器對三類種類任務處理速率不同造成的。

此外，通過觀察圖2中曲線的最低點可以得出，對于同一類型的任務，隨著該類任務比重的增大，任務對應的最佳本地處理概率將逐漸減小。相比MEC服務器和云服務器，本地處理器有著較低的任務處理速率。隨著任務數目的增多，任務在本地處理器的平均逗留時間成為導致任務平均處理時延增長的主要影響因素，因此，該任務將更有可能以卸載的方式進行處理，最佳的本地處理概率會變小。

針對不同的本地處理器時鐘頻率，給出各類任務對應的移動設備能耗水平隨該類任務本地處理概率的變化趨勢，如圖3所示。由式(19)可知，任務對應的移動設備能耗水平與任務類別無關。這意味著三類任務對應的移動設備能耗水平在該類任務本地處理概率下呈現相同的變化趨勢，因此用一張圖即可表示對三類任務的實驗探究結果。

圖3 第i類任務對應的移動設備能耗水平Fig.3 Energy consumption level of mobile device corresponding to the class i tasks

5 策略優化

折衷考慮任務的平均處理時延和移動設備的能耗水平，引入權重系數，建立系統的成本函數，研究基于單用戶和任務分類的MEC任務卸載策略聯合優化問題。

設任務平均處理時延和移動設備能耗水平所對應的權重系數分別為f1和f2，且存在關系式f1+f2=1。通過加權平均法，得到系統的成本函數F(x)為

(20)

至此，可以得到一個聯合優化問題P如式

(21)

為了降低系統成本，應用KKT條件方法優化任務卸載策略。對于優化變量x，需要同時考慮系統穩態條件和任務分配比例自身范圍等兩種約束。令gk(x)≤0表示優化變量間存在的不等式約束，可以得出gk(x)為

(23)

其中，式gk(x)(k=1,2,…,7)由系統的穩態條件得出，式gk(x)(k=8,9,…,19)由分配比例自身的范圍得出。

將優化問題P轉換為KKT條件方法的解決形式

(24)

s.t.gk(x)≤0,k=1,2,…,19。

(25)

綜合式(20)和式(23)，得到拉格朗日函數W(x)為

(26)

其中，δk(k=1,2,…,19)為拉格朗日乘子，并且滿足δk≥0。

根據KKT條件，所要求解的最優變量組合滿足

(27)

式中，k=1,2,…,19。

沿用表1中設置的實驗參數，考慮不同的任務到達率及任務比重，應用上述KKT條件方法，給出任務卸載策略優化方案，并求解出此時的最小系統成本，如表2所示。

表2 任務卸載策略聯合優化結果Tab.2 Jointly optimal results of the task of floading strategy

從表2中的優化結果可以發現，任務到達率λ越大，最小系統成本F(x*)也會越大。因為任務到達率越大，系統阻塞率越高，導致任務在系統中的平均處理時延加大。此外，由于本地處理器、本地發送端口和本地接收端口等裝置的功率恒定，時延的增大無疑會導致移動設備的能耗水平提高。任務平均處理時延的增加和移動設備能耗水平的提升，都會使得系統成本增大。

此外，對比表2中數據還發現，在同一任務到達率λ下，隨著三類任務比例(α1,α2,α3)的變化，最優任務卸載策略x*將進行適當調整，但是最小系統成本F(x*)卻保持不變。在三類任務總到達率保持不變的前提下，一類任務到達率的增大意味著另一類任務到達率的減小。任務到達率的增大將帶來更高系統成本，而任務到達率的降低則會帶來更小的系統成本。通過調節任務卸載策略，均衡三類任務本地處理和卸載處理的比例，基于單用戶和分類任務的MEC系統能夠維持穩定，任務處理所產生的平均最小系統成本保持不變。

應用表1中的實驗參數，變換任務卸載策略參數，得出不同任務卸載策略下的系統成本，結果如表3所示。

表3 不同任務卸載策略對比Tab.3 Comparison of different task offloading strategy

對比表3中數據發現，相比策略1(三類任務全都在本地端處理)和策略2 (三類任務全都卸載處理)，所提出的任務卸載優化策略能夠有效地降低系統成本。

6 結論

針對整體智能家居等MEC應用場景，搭建了由本地端、邊緣端和云端組成的系統框架，提出了一種基于單用戶和任務分類的MEC任務卸載策略。考慮異構邊緣網絡，通過建立具有單輸入流與多類顧客的排隊模型，推導了任務的平均處理時延和移動設備能耗水平等性能指標。實驗結果表明，通過設置合理的任務本地處理概率，可以使任務的平均處理時延達到最小。此外，實驗結果還揭示出，任務對應的移動設備能耗與任務本地處理概率呈正相關。權衡不同性能指標，構建系統的成本函數，應用KKT條件方法，給出了任務卸載策略的優化方案，實現了系統成本的最小化。

后續的研究中，將考慮邊緣端和云端的用戶競爭，面向多用戶MEC應用研究任務卸載問題。