劉繼軍，鄒山花，盧先領(lǐng)+

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

2.江南大學物聯(lián)網(wǎng)工程學院,江蘇無錫214122

3.江蘇省物聯(lián)網(wǎng)應(yīng)用技術(shù)重點建設(shè)實驗室，江蘇無錫214100

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

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

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

1 系統(tǒng)模型

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

Fig.1 “Cloud-Edge-End”three-tier MEC computation offloading structure圖1“云-邊-端”三層MEC 計算卸載結(jié)構(gòu)

1.1 計算與通信模型

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

1.2 優(yōu)化問題建模

根據(jù)1.1 節(jié)給出的計算與通信模型，可得taski,j調(diào)度后的時延與能耗：

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

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

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

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

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

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

2.1 初始化處理

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

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

采用排序算法對所有用戶任務(wù)緊急度按照由高到低進行排序，并依序設(shè)置任務(wù)優(yōu)先級。

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

根據(jù)任務(wù)數(shù)據(jù)量大小初始化卸載決策方案：當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 資源分配算法

傳統(tǒng)子信道分配算法旨在將所受干擾最小的子信道分配給卸載任務(wù)進行傳輸，但是會存在這樣一種情況：當卸載任務(wù)在所受干擾最小的子信道上傳輸時，會對同在該子信道上傳輸?shù)钠渌遁d任務(wù)造成嚴重干擾，從而導致這些卸載任務(wù)傳輸速率迅速惡化。

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

輸入：信道增益矩陣、任務(wù)優(yōu)先級、卸載決策矩陣。

輸出：信道分配矩陣A。

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

根據(jù)式（5）及其約束條件可得關(guān)于計算資源分配優(yōu)化問題及其約束條件，具體表示如下：

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

算法2計算資源競爭算法

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

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

2.3 卸載決策算法

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

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

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

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

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

定理1博弈Ω的勢函數(shù)為：

證明

情況1當taski,j由本地處理模式轉(zhuǎn)變?yōu)樾遁d處理模式時，即mi,j=0 轉(zhuǎn)變?yōu)閙i,j′＞0。在此過程中會占用傳輸子信道和邊緣服務(wù)器計算資源，從而造成部分任務(wù)的傳輸性能和計算性能下降，用tasku,v泛指受到影響的任務(wù)。

情況2當taski,j由卸載處理模式轉(zhuǎn)變?yōu)楸镜靥幚砟Ｊ綍r，即mi,j＞0 轉(zhuǎn)變?yōu)?0。在此過程中會釋放傳輸子信道和邊緣服務(wù)器計算資源，從而使得部分用戶的傳輸性能和計算性能提高，用tasku,v泛指受到影響的任務(wù)，得

情況3當taski,j由一種卸載模式轉(zhuǎn)變?yōu)榱硪环N卸載模式時，即mi,j與均大于0，但此時又可以分兩種情況討論：

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

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

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

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

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

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

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

2.4 算法復雜度分析

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

3 仿真結(jié)果及分析

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

Table 1 Simulation parameters表1 仿真參數(shù)

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

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

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

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

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

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

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

Fig.5 Relationship between the number of users and total gain of system圖5 用戶數(shù)量與系統(tǒng)總增益的關(guān)系

Fig.6 Relationship between data size of tasks and total gain of system圖6 任務(wù)數(shù)據(jù)量與系統(tǒng)總增益的關(guān)系

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

4 結(jié)論

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