MEC 中資源分配與卸載決策聯合優化策略

劉繼軍，鄒山花，盧先領+

1.江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫214122

2.江南大學物聯網工程學院,江蘇無錫214122

3.江蘇省物聯網應用技術重點建設實驗室，江蘇無錫214100

隨著資源密集型和時延敏感型應用的逐漸增多，如增強現實、無人駕駛等，用戶對于低時延與低能耗的任務處理需求愈發顯著[1-2]。作為第五代移動通信的核心技術之一——移動邊緣計算（mobile edge computing，MEC）將計算資源與存儲資源部署到無線網絡邊緣，以處理資源密集型和時延敏感型任務[3-4]，解決了云計算在通信資源占有量高、任務處理時延長等方面的問題。用戶可通過計算卸載，將任務傳輸到邊緣服務器上處理，從而降低處理時延與能耗，滿足服務質量需求。

計算卸載作為MEC 關鍵技術，目前已有許多相關研究。在MEC 計算卸載結構上，文獻[5-7]主要考慮“邊-端”兩層結構，忽略了云在計算卸載過程中的輔助作用。文獻[8]以隨機優化理論為基礎，提出了一種最小化能耗的動態卸載決策算法。文獻[9]將任務緩存概念引入卸載決策中，分別采用凸優化方法和0-1 規劃算法對任務卸載與任務緩存問題進行求解，從而實現最小化任務處理能耗。文獻[10]針對邊緣節點過載問題，提出一種多路徑傳輸負載平衡優化方案，利用多路徑傳輸的邊緣計算架構作為傳輸協議支持車輛之間的通信和邊緣節點間的實時虛擬機遷移，以最小化任務處理時延。文獻[8-10]僅考慮到能耗或時延單一指標，忽略了兩者對任務卸載處理性能的綜合影響。在計算卸載研究中不同用戶任務在緊迫程度或重要性上存在差異。文獻[11]根據任務類型不同將其分為三種處理級別，但同級別任務之間并未給出細致劃分。文獻[12]分別將用戶任務和邊緣服務器建模為獨立泊松流和M/M/1 隊列模型，對卸載任務采取先到先處理原則。上述文獻忽略了任務優先級對計算卸載性能的影響。文獻[13]在分布式邊緣計算異構網絡中，提出了一種計算卸載和資源分配聯合優化方案，但未考慮到邊緣服務器過載問題。文獻[14]在超密集網絡場景下對卸載策略、信道資源和傳輸功率進行聯合優化，并將邊緣服務器上閑置的計算資源全部分配給卸載任務，以最小化系統總能耗，但是未實現邊緣服務器計算資源的合理利用。

不同于上述文獻，本文提出了“云-邊-端”三層MEC 計算卸載結構下的資源分配與卸載決策聯合優化策略。為全面考慮影響計算卸載性能的因素，將優化問題規劃為用戶任務處理時延與能耗相對減少的加權和，定義為用戶任務處理增益；考慮到用戶任務屬性及其服務質量需求之間的差異，為任務設置優先級，并根據任務數據量大小初始化卸載決策方案；針對優化問題求解，首先采用基于均衡傳輸性能的信道分配算法，為卸載處理任務分配傳輸信道；然后根據邊緣服務器計算資源占用情況，提出一種基于收益最大化的計算資源競爭算法，在保證邊緣服務器不超載的情況下最大化計算資源效率與利用率；最后基于博弈論證明了優化問題存在納什均衡，在迭代過程中通過用戶增益值比較獲得最大化系統總增益下的卸載決策方案。

1 系統模型

本文構建了一個由云、宏基站（macro base station，MBS）、Ns個微基站（small base station，SBS）和用戶端組成的“云-邊-端”三層MEC 計算卸載結構，如圖1所示，并將邊緣服務器部署在MBS 和SBS 上，用集合N={1,2,…,Ns}表示結構內所有SBS。每個SBS 下包含Nc個用戶，用集合U={1,2,…,Nc}表示。

Fig.1 “Cloud-Edge-End”three-tier MEC computation offloading structure圖1“云-邊-端”三層MEC 計算卸載結構

1.1 計算與通信模型

（2）當任務taski,j卸載處理時，首先將任務數據上傳至邊緣或云端，同一SBS 下用戶的無線通信頻帶被分成K個正交子信道，用集合C={1,2,…,K}表示，用戶通過分配子信道進行卸載傳輸，而不同SBS下的用戶則復用子信道進行傳輸。定義∈{0,1}為taski,j的子信道分配因子，1 表示將子信道k分配給taski,j進行傳輸，反之亦反，用矩陣A表示所有用戶任務的信道分配方案。考慮到用戶上行傳輸時受到相鄰微基站上同信道傳輸用戶的干擾，ui,j上傳速率可表示為：

1.2 優化問題建模

根據1.1 節給出的計算與通信模型，可得taski,j調度后的時延與能耗：

式中，I{*}表示若*式成立，則I{*}=1，否則I{*}=0。

根據式（2）和式（3）可得關于taski,j時延與能耗的增益：

式中，ξi,j∈[0,1]為時延與能耗的權衡因子，其取值大小由和ui,j上剩余能耗綜合決定，可利用熵值法求得。

本文目標是最大所有用戶時延與能耗總增益，即：

式中，矩陣F為計算資源分配方案；約束條件（1）為任務處理最大時延約束，保證每個任務時延不超時；約束條件（2）給出了卸載決策因子的取值范圍，明確了卸載決策矩陣M中元素取值范圍；約束條件（3）給出了子信道分配因子的取值范圍，明確了信道分配矩陣A中元素取值范圍；約束條件（4）和（6）分別為taski,j在滿足最大時延約束條件下，若卸載到SBS 服務器或MBS 服務器上所需分配到的最小計算資源，便于計算資源的初始分配；約束條件（5）表示SBSi服務器為卸載任務分配的計算資源總和不得超過SBSi服務器總的計算資源，防止在計算資源分配過程中SBSi服務器過載；約束條件（7）表示MBS 服務器為卸載任務分配的計算資源總和不得超過MBS 服務器總的計算資源fM，防止在計算資源分配過程中MBS 服務器過載。

2 資源分配與卸載決策算法

2.1 初始化處理

首先，由于不同用戶任務在服務質量需求上存在差異，需設置任務優先級。任務的數據量與其處理所需的周期數存在一定關系，即ci,j=μdi,j，其中μ是一個常量，取值為312，單位為cycle/bit[16]。因此本文可根據用戶任務taski,j的數據量與最大時延約束兩個屬性，構建任務緊急度Emi,j的數學計算模型。

式中，αi,j∈[0,1]為關于taski,j的數據量與最大時延約束的權衡因子，可以通過熵值法求得。

采用排序算法對所有用戶任務緊急度按照由高到低進行排序，并依序設置任務優先級。

然后，考慮到任務的數據量與其處理所需周期數之間的線性關系，并根據1.1 節中任務處理時延模型及其約束條件，忽略任務傳輸過程中受到的干擾，則可得到任務數據量與處理模式之間的關系。

根據任務數據量大小初始化卸載決策方案：當di,j∈(0,D1]，則初始化mi,j=0；當di,j∈(D1,D2]，則初始化mi,j=1；當di,j∈(D2,D3]，則初始化mi,j=2；否則初始化mi,j=3。

2.2 資源分配算法

傳統子信道分配算法旨在將所受干擾最小的子信道分配給卸載任務進行傳輸，但是會存在這樣一種情況：當卸載任務在所受干擾最小的子信道上傳輸時，會對同在該子信道上傳輸的其他卸載任務造成嚴重干擾，從而導致這些卸載任務傳輸速率迅速惡化。

算法1均衡信道性能分配算法

輸入：信道增益矩陣、任務優先級、卸載決策矩陣。

輸出：信道分配矩陣A。

在計算卸載過程中，大部分計算卸載算法[13-14]忽略了計算資源分配對計算卸載性能的影響，一般都是按照卸載任務先后到達順序將邊緣服務器上的閑置計算資源全部提供給其進行處理，處理完畢后釋放資源，再供給下一個卸載任務進行處理。當某一邊緣服務器上有大量卸載任務等待處理時，后到達的任務需等待較長時間，從而導致任務超時。為避免這種情況的產生，需設計一種合理的計算資源分配算法。

根據式（5）及其約束條件可得關于計算資源分配優化問題及其約束條件，具體表示如下：

對于上述計算資源分配問題，可建模為多用戶之間的計算資源競爭：當用戶卸載任務通過子信道傳輸并被邊緣服務器接收后，服務器會對每個卸載任務的服務質量需求進行分析，從而避免邊緣服務器負荷超載；然后根據其閑置計算資源量，在滿足最大時延約束條件下為每個卸載任務分配所需的最小計算資源；最后將邊緣服務器剩余計算資源分割成若干個資源塊，卸載任務通過競爭資源塊實現計算資源利用率與卸載任務處理增益最大化，具體如算法2 所示。

算法2計算資源競爭算法

輸入：任務優先級、邊緣服務器計算資源、卸載決策矩陣、本地計算頻率fL。

輸出：計算資源分配矩陣F。

2.3 卸載決策算法

每個用戶可通過尋求自身處理增益最大化，從而實現“云-邊-端”三層MEC 計算卸載結構下系統總增益最大化，但是不同用戶任務之間存在差異，基于凸優化的卸載決策方案會造成部分任務的服務質量需求得不到滿足，因此本文在初始化卸載決策方案的基礎上提出基于博弈論的卸載決策算法，將卸載決策問題建模為博弈Ω={U,M,Gi,j}，相關要素描述如下：

（1）集合U為博弈Ω中的玩家集合，即整個“云-邊-端”架構下的用戶集合；

（2）M={(mi,j):mi,j∈{0,1,2,3},i∈N,j∈U}為博弈Ω中每個玩家可選的策略空間；

（3）Gi,j為博弈Ω中玩家ui,j的增益函數，具體計算如式（5）所示。

定義1（勢博弈）如果博弈Ω存在函數φ滿足下述條件，則該博弈為勢博弈[17]：

定理1博弈Ω的勢函數為：

證明

情況1當taski,j由本地處理模式轉變為卸載處理模式時，即mi,j=0 轉變為mi,j′＞0。在此過程中會占用傳輸子信道和邊緣服務器計算資源，從而造成部分任務的傳輸性能和計算性能下降，用tasku,v泛指受到影響的任務。

情況2當taski,j由卸載處理模式轉變為本地處理模式時，即mi,j＞0 轉變為=0。在此過程中會釋放傳輸子信道和邊緣服務器計算資源，從而使得部分用戶的傳輸性能和計算性能提高，用tasku,v泛指受到影響的任務，得

情況3當taski,j由一種卸載模式轉變為另一種卸載模式時，即mi,j與均大于0，但此時又可以分兩種情況討論：

①當taski,j傳輸子信道未發生變化時，只需考慮邊緣服務器計算資源變化對用戶任務的影響：

②當taski,j傳輸子信道發生變化時，不僅需要考慮邊緣服務計算器資源變化對用戶任務的影響，還需要考慮傳輸子信道變化對用戶任務的影響：

綜上所述，當Gi,j(M)-Gi,j(M′)＞0 時，則可得φ(M)-φ(M′)＞0，反之易可證得。因此可得φ(M)為博弈Ω的勢函數，該博弈即為勢博弈，從而可知博弈Ω在有限異步更新過程中收斂于納什均衡[17]。

卸載決策過程中由于用戶任務卸載處理模式的不斷變化，信道資源與計算資源需要重新再分配，直至用戶任務獲得最大增益值。本文通過迭代增益值比較法得到納什均衡下的卸載決策方案：首先對用戶任務按照處理模式不同進行分類；然后對每一類處理模式下的任務進行卸載處理模式調整，并重新分配信道資源和計算資源；最后通過比較卸載模式調整前后任務增益值大小，保留增益值較大下的處理模式，并更新卸載決策矩陣M，具體如算法3 所示。

算法3增益值迭代比較算法

輸入：初始化卸載決策矩陣M0。

輸出：納什均衡下的卸載決策矩陣M。

2.4 算法復雜度分析

本文針對優化問題分別提出了資源分配算法與卸載決策算法，實現系統總增益值最大化。資源分配算法分為兩種：信道資源分配算法復雜度為O(N)，其中N為卸載處理用戶任務數量；計算資源分配算法復雜度為O(Ns×Nc)。從而可得卸載決策算法復雜度為O(NsNclbN)。相較于文獻[5]中計算卸載算法復雜度O(NsNclb(NsNc))和文獻[14]中計算卸載算法復雜度O((NsNc)2)，本文所提策略能夠有效降低算法復雜度。

3 仿真結果及分析

本文仿真場景考慮了“云-邊-端”三層MEC 計算卸載結構，在500 m×500 m 的空間內，MBS 部署在中心位置，SBS部署服從均值為0、方差為1的正態分布，移動用戶在每個SBS 覆蓋范圍內隨機分布；MBS 上的邊緣服務器計算資源為50 GHz，SBS 上的邊緣服務器計算資源為10 GHz；其余仿真參數詳見表1[14,16]。

Table 1 Simulation parameters表1 仿真參數

Fig.2 Transmission rate obtained under different channel resource allocation algorithms圖2 不同信道資源分配算法下獲得的傳輸速率

圖2 描述了在Nc=20 時，三種Ns取值下各子信道的平均傳輸速率。將本文基于均衡傳輸性能的信道分配算法與文獻[14]中基于改進匈牙利算法和貪婪算法的信道分配算法、平均信道分配算法進行對比。文獻[14]中的信道分配算法以用戶所受干擾作為信道性能評估標準，將所受干擾最小的子信道分配給卸載任務傳輸；平均子信道分配算法將各子信道均分給卸載任務傳輸；兩種信道分配算法在一定程度上使得各子信道傳輸性能相當。本文算法考慮了兩種干擾因素并將其作為信道性能評估標準，所得信道分配結果下的各子信道傳輸性能均衡并且在傳輸速率上優于其他兩種算法。此外，根據圖2 中三種Ns取值下的實驗結果分析可知隨著Ns取值的增加，卸載任務數量增加，使得各子信道復用率上升，子信道間干擾加劇，從而導致子信道平均傳輸速率降低。

Fig.3 Relationship between the number of users and average transmission rate of users圖3 用戶數量與用戶平均傳輸速率的關系

圖3 描述了隨著用戶數量增加，卸載任務所能獲得的平均傳輸速率變化情況。當用戶數量較少時，卸載傳輸過程中產生的干擾小，因此三種算法下的用戶平均傳輸速率較大；但是隨著用戶數量的增加，卸載處理的任務也越來越多，子信道復用頻率上升，導致傳輸過程中受到的干擾增強，信道傳輸性能下降，此時信道傳輸性能僅能滿足數據量較低的任務卸載處理需求，因而卸載傳輸的用戶數量變化趨于平穩，用戶平均速率下降趨勢也逐漸減緩。但是相比于其他兩種信道分配算法，本文算法下的卸載任務所獲得的平均傳輸速率最高。

圖4 描述了用戶任務在不同邊緣服務器數量上處理所得增益值。隨著Ns取值逐漸增大，各子信道平均傳輸速率逐漸下降，導致卸載任務在每個邊緣服務器上處理時所獲得的增益值逐漸減小。在對邊緣服務器上閑置的計算資源進行分配時，文獻[14]將邊緣服務器的所有閑置資源分配給卸載處理任務，處理完畢后釋放資源；文獻[5]采用基于凸優化的計算資源分配方式，而全部卸載算法基于卸載任務所需處理周期數進行計算資源分配。本文算法采用了基于收益最大化的資源競爭算法進行計算資源分配，在滿足任務處理時延約束的條件下，用戶任務通過競爭資源實現自身增益最大化，從而使得在本文計算資源分配算法下，卸載任務能夠在每個邊緣服務器上所獲得的計算資源最大化增益值產出。

圖5 描述了隨著用戶數量增加，系統總增益值的變化情況。與文獻[14]、文獻[5]和全部卸載算法相比，由于優化問題存在納什平衡，本文卸載決策算法在迭代過程中對用戶任務處理增益值進行比較，為用戶任務選擇最大增益值下的處理模式，從而確定卸載決策方案。從圖中可以看出當用戶數量較少時，卸載任務可獲得較高的傳輸速率和充足的計算資源，從而使得系統總增益值穩健增長；但是當用戶數量增加到300 左右時，信道傳輸性能下降，計算資源競爭激烈，用戶卸載處理時所能獲得增益值減少，從而使得系統總增益值增長速率降低。但相較于其他三種卸載決策算法，本文卸載決策算法在用戶數量變化的情況下，所獲得的系統總增益值更高。

Fig.4 Edge servers'gain value under different computing resource allocation algorithms圖4 不同計算資源分配算法下邊緣服務器的增益值

Fig.5 Relationship between the number of users and total gain of system圖5 用戶數量與系統總增益的關系

Fig.6 Relationship between data size of tasks and total gain of system圖6 任務數據量與系統總增益的關系

圖6 描述了在Nc=20 時，三種Ns取值下的任務數據量大小與系統總增益值之間的關系。將本文算法與其他算法進行對比時，可看出隨著任務數據量的增大，本文算法相比于其他算法具有更高的系統增益值。當用戶任務數據量較小時，卸載處理模式下的時延和能耗較低，增益值較大，從而使得卸載處理任務數量增加，系統總增益值急劇上漲；但是隨著任務數據量的增大，一方面卸載處理的傳輸時延增加，另一方面本地處理的能耗增加，兩相權衡，從而導致系統總增益值增長率降低。但是隨著任務數據量和Ns的增大，本文算法下的系統總增益值增長率始終大于0，而其他三種算法都出現了系統總增益值的負增長。

4 結論

本文研究了“云-邊-端”三層MEC 計算卸載結構下的資源分配與卸載決策聯合優化策略，在滿足用戶服務質量需求的基礎上，考慮了用戶任務處理時延與能耗，提出了以最大化系統總增益為目標的優化問題。首先根據任務屬性設置優先級，并基于任務數據量初始化卸載決策方案；然后采用一種均衡傳輸性能的信道分配算法為卸載任務分配信道資源，并對卸載到邊緣服務器上處理的用戶任務采用基于收益最大化的資源競爭算法分配計算資源；最后迭代比較用戶在各種處理模式下的增益值獲得最大化系統增益下的卸載決策方案，有效地提高了卸載任務傳輸速率，促進了任務處理時延與能耗的改善。