移動邊緣計算系統的雙服務器協同與計算通信資源聯合優化

李宇龍，梁靜軒，王 豐

（廣東工業大學 信息工程學院, 廣東 廣州 510006）

隨著互聯時代的快速發展，眾多計算密集型和時延敏感型應用興起，如在線游戲、虛擬/增強現實、智能駕駛等。這使計算能力有限、電池電量不足和存儲容量有限的移動終端設備面臨著巨大的挑戰。云計算可以將到達終端的任務卸載到云端服務器進行處理，其強大處理能力能有效地降低計算時延，并顯著降低設備消耗電量的速度。近幾年，隨著無線終端設備數量的劇增，海量數據被上傳到云端服務器，造成網絡堵塞，服務效率降低。移動邊緣計算提供了一種解決上述問題的解決方案，通過在靠近無線終端設備的網絡邊緣端部署服務器來處理設備卸載的計算任務，分擔云端服務器的任務處理壓力，進一步降低任務處理時延和設備的電量消耗[1-4]。

移動邊緣計算中的計算卸載策略主要分為二進制卸載和部分卸載[5-8]，二進制卸載將計算任務完整地進行卸載，而部分卸載將計算任務分割為多個部分后卸載其中部分任務。在二進制卸載策略下，文獻[9]針對MEC系統網絡中移動終端設備因計算能力不足，在處理低時延、高可靠應用時產生的高時延問題，提出一種基于博弈論的求解方法，用于聯合優化計算卸載與資源分配；文獻[10]考慮了最小化系統的執行延遲和用戶能耗的加權和，通過聯合優化任務卸載決策、卸載調度和功率分配，設計了一種兩級交替優化框架來求解非凸混合整數優化問題；文獻[11]考慮了最小化用戶卸載決策下的時延，通過聯合優化計算卸載和資源分配問題；文獻[12]從用戶的角度考慮了最小化用戶能耗和傳輸、計算成本，通過聯合優化計算卸載和資源分配問題，提出了一種基于博弈論的求解方法；文獻[13]考慮了兩層MEC系統，以最小化系統服務時延和用戶能耗為目標，聯合優化了服務緩存和計算卸載策略；文獻[14]考慮了一種能量感知卸載方案，通過最小化能耗和時延之間的權衡，在能量有限和延遲敏感的條件下聯合優化通信和計算資源分配。上述文獻中，任務的決策會取決于終端設備的運行狀態，系統的性能對設備的要求較高。

部分卸載策略下，文獻[15]考慮了在隨機應用請求、不可預測的無線設備狀態、時變的信道狀態以及計算資源等因素的基礎上最小化系統的時延與能耗；聯合優化多用戶的部分卸載決策、傳輸調度和計算資源分配；并提出了一種在線資源協調與分配方案。文獻[16]考慮了最小化系統總延遲，聯合優化計算卸載和無線傳輸調度問題；文獻[17]考慮了MEC服務器部署在宏基站和小型基站下的多用戶場景，通過聯合優化用戶與基站之間的計算卸載、用戶與小型基站的連接、用戶的CPU (Central Processing Unit)頻率和發射功率，達到MEC系統的總能耗最小化的目的。文獻[18]通過聯合優化用戶的任務分配比例和卸載發射功率來最小化設備之間的任務延遲。文獻[19]將非正交多址技術引入到MEC系統中，通過聯合優化任務卸載和資源分配以最大化系統處理能力。文獻[20]在考慮卸載延遲和保密約束的前提下，通過聯合優化通信和計算資源分配實現總保密卸載數據最大化的部分卸載比。文獻[21]在多用戶多服務器MEC系統下，利用改進的深度強化學習算法，優化服務器的選擇和卸載任務比例以最小化計算時延與能耗。然而在部分卸載模式下，大部分工作僅考慮了時延或能耗的單目標優化，未考慮時延和能耗的均衡優化。

不同于以上研究，本文考慮在雙MEC服務器與多用戶協同場景下，以最小化系統計算時延和用戶能耗加權和為目標，在有限的時間內完成用戶的任務并將任務計算結果發送到遠處數據驅動端進行驅動。由于用戶和單MEC服務器進行卸載時會有其他MEC服務器空閑，造成資源浪費，因此考慮雙服務器協同任務處理方式，最終完成數據驅動端的驅動。本文通過聯合優化計算任務分割和卸載發射功率以最小化系統時延與用戶能耗加權和，提出了一種較低計算復雜度的算法方案實現最優任務分割和發射功率。

本文的主要貢獻總結如下：(1) 針對雙MEC服務器協同多用戶場景，基于用戶能耗與系統計算時延加權和最小化準則，建模本地計算和雙MEC服務器協同計算的聯合優化問題；在計算時延和發射功率約束條件下，聯合優化用戶計算任務分割和計算卸載發射功率。(2) 針對該聯合設計問題，提出一種較低計算復雜度的聯合優化算法方案，將原問題解耦成計算卸載和計算任務分割的2個子問題，分別采用內點法和單純形法實現快速求解。(3) 大量數值仿真實驗表明，本文所提聯合優化算法的系統性能優于已有啟發式基準方案，并在較少的算法運行時間下，本算法方案能取得與最優拉格朗日乘子法基準方案相同的系統性能。

1 系統模型與問題構造

考慮一個包含數據驅動端的雙MEC服務器協同多用戶系統。如圖1所示，該模型包含K個無線設備、2個部署了MEC服務器的邊緣基站和1個數據驅動端。假設每個用戶通過頻分多址(Frequency Division Multiple Aaccess，FDMA) 技術接入基站，用i∈K表示圖1中第i個無線設備，其中K=Δ{1,···,K} 表示K個無線設備組成的集合。每個無線設備通過本地和卸載處理計算任務[15-21]。本文考慮通過無線設備和雙MEC服務器協同計算來完成到達無線設備的計算任務，并將任務計算結果傳輸到數據驅動端。假設基站1和基站2之間、基站2和數據驅動端之間通過光纖進行通信[17]。

圖1 基于雙服務器協同的多用戶系統模型Fig.1 Multi-user system model based on cooperation of two servers

1.1 任務模型

本文采用三元物理量( αi,βi,γi)來 表示第i個無線設備的計算任務，其中 αi為無線設備i的計算任務的輸入數據量(單位：bit) ， βi為完成計算任務所需的CPU周期數以及 γi為完成計算任務后輸出的結果數據量(單位：bit)。假設這些計算任務是可以被任意分割的[22]，且對應的輸入數據量、所需CPU周期數和輸出數據量以相同的比例進行分割。令x1,i、x2,i和x3,i分別為無線設備i、基站1和基站2需要完成的計算任務相應的比例，并且有式(1) 的限制條件。

式中：i=1,···,K。

1.2 時延模型

1.2.1 無線設備計算、傳輸的時延

第i個無線設備處理任務時，產生的時延主要由任務處理和傳輸輸入數據、輸出數據3部分組成。第i個無線設備進行本地計算時所需的時間為

式中：i=1,···,K；x1,iβi為第i個無線設備需要通過本地計算完成的計算量； βi為完成相應計算任務所需的CPU周期數；fi為其進行本地計算時的CPU頻率。

接下來建模無線設備傳輸輸出數據和部分輸入數據所需的時間。記ri為 第i個無線設備和基站1無線通信時的傳輸速率。本文采用基于FDMA的多用戶計算卸載通訊模式，記Bi為 系統分配給第i個無線設備的上下行鏈路的頻譜帶寬。根據香農公式，第i個無線設備的上下行鏈路傳輸速率ri為

式中：i=1,···,K；pi為該無線設備通信時的發射功率；hi＞0為該無線設備與基站1的上下行鏈路信道增益； σ2為基站接收機的高斯白噪聲功率。因此，第i個無線設備的輸入輸出數據的傳輸時間表示為[22]

式中： αi和γi分別為到達無線設備i的計算任務的輸入數據量和計算結果的數據量。結合式(2) 和式(4) ，第i個無線設備進行本地計算和數據傳輸所產生的時延，記為

1.2.2 基站產生的計算、傳輸的時延

基站1產生的時延包括計算部分任務、傳輸部分輸入數據和傳輸輸出數據3部分?；?計算部分任務產生的時延為

式中：i=1,···,K；fmec1為基站1使用其CPU計算部分任務時使用的CPU頻率； βi為完成相應計算任務所需的CPU周期數。

接下來分別建?；?和基站2傳輸輸入數據和輸出數據所需的時間。本文假設基站端和數據驅動端采用光纖通信，因此，基站與基站間、基站與數據驅動端進行數據傳輸的傳輸速率都為R?；?需要傳輸的數據內容包括來自多個無線設備和基站1的任務結果數據以及基站2進行任務處理需要的輸入數據，該傳輸過程所需的時間為

式中：i=1,···,K；αi和 γi分 別為到達無線設備i的計算任務的輸入數據量和計算結果的數據量。結合式(6)和(7) 處理第i個無線設備所需的時間Tmec1,i，其表達式為

基站2產生的時延同樣包括任務計算和數據傳輸兩部分，區別在于任務分配比例?；?完成對應比例的任務計算量所需的時間以及傳輸輸出數據到數據驅動端所需的時間分別為

式中：i=1,···,K； βi和 γi分別為完成相應計算任務所需的CPU周期數和計算結果的數據量；fmec2為基站2計算任務分配的CPU頻率。記Tmec2,i為基站2完成任務計算和完成數據傳輸所需的時間和，其表達式為

式中：i=1,···,K。

結合式(5) 、(8) 和(10) 可得系統處理第i個無線設備的所需的總時間。記Ti為系統完成到達第i個無線設備的計算任務并將計算結果傳輸到數據驅動端所需的總時間，考慮下一部分任務計算需要上一部分任務計算的結果進行驅動，其表達式為[23]

式中：i=1,···,K。系統在給定的時限內完成所有的計算任務并將計算結果傳輸到數據驅動端。建模計算任務完成所需時延約束為

式中：i=1,···,K；TDL是給定的計算任務完成時限。

1.3 能耗模型

本文考慮無線設備在任務計算以及數據傳輸過程的能量消耗。無線設備i由于任務計算產生的能耗表示為

式中：i=1,···,K；κ 為與處理器的結構相關的能耗常數[24]。第i個無線設備傳輸輸入數據和輸出數據的所需時間由式(4) 給出，由此可得數據傳輸能耗為

結合式(13) 和(14) ，計算第i個無線設備進行任務計算和數據傳輸的總能耗，具體為

1.4 優化問題構造

分別記w1，w2為用戶執行任務的能耗和系統時延的偏好因子，并且w1+w2=1，可以根據任務完成時間的需求和剩余電池壽命來進行設置。本文以最小化系統時延和無線設備能耗的加權和為目標提出以下優化問題。

式中：x1,i,x2,i,x3,i為對所有任務的分配比例；約束C 1保證系統通過協同完成所有任務；約束 C2為任務卸載發射功率的范圍；約束 C3為全部任務完成并傳輸到數據驅動段所需的時間必須不大于時限TDL。在偏好因子確定的情況下，通過設置合理的時延約束TDL來實現MEC的性能偏好。

2 問題(16)優化分析與求解

由于問題(16) 目標函數中任務分配比例和發射功率是耦合的，因此該問題是一個非凸優化問題。為此，本文設計一種較低計算復雜度的算法方案，將原問題解耦成任務分割和計算卸載2個子問題，首先利用內點法求解計算卸載子問題，再利用單純形法求解最優任務分割子問題。

2.1 傳輸功率優化

將原問題解耦成計算卸載子問題，其中問題(16)可以變換為子問題(17)。

式中：f(oi) 為式(18) 中的目標函數，υi為迭代過程中的懲罰因子。算法1對求解式(18) 所采用的內點法進行了總結。

2.2 任務分配比例優化

在取得最優發射功率p*

i的情況下，問題(16) 可以轉化為求解任務分割子問題。將優化問題(16) 的C1約 束轉化為x3,i=1-x1,i-x2,i，并與目標函數和其他約束條件結合，形成下述優化問題(20) 。

本文利用單純形算法求解變換后的優化問題(20) 。

首先，設置優化問題的一個初始可行解；其次，在初始可行解條件下，如果存在非初始變量si≥0，則找出最大非初始變量作為換入變量；然后，從初始變量中找到換出變量，進行初等行列變換，將新的初始變量轉換為單位矩陣。最后，循環迭代此過程直到非初始變量為非正。因此，對于問題(20)添加非初始變量si，即可得到問題(21)，表示為

優化問題(21) 是一個標準的線性規劃問題，算法2對求解問題(21) 所使用的單純形法的求解步驟進行了總結。

算法2求解問題(21)的單純形法。

3 仿真結果分析與對比

仿真結果驗證了本模型的有效性和優越性?？紤]在雙MEC服務器協同多用戶場景下，將系統任務計算結果發送到遠處數據驅動端進行驅動，其中每個基站覆蓋范圍為100 m，di為無線設備至基站的距離，其信道功率增益設置為hi=Γidi-3.5|hˉi|[26]，其中hˉi～CN(0,1)為 小尺度衰落效應，Γi= -32 dBm為用戶i參考距離為1 m時的路徑損耗。未作額外說明時，該模型的系統參數設置如下：系統分配給第i個無線設備的上下行鏈路的頻譜帶寬Bi=20 MHz[9]，基站接收機的高斯白噪聲功率 σ2=10-9W，任意無線設備i采用fi=1.5 GHz的CPU頻率來處理任務；第1個和第2個基站服務器的計算頻率為fmec1= 2 GHz、fmec2=4 GHz;無線設備的最大通信發射功率Pmax=1 W[17]；κ =10-27為無線設備進行本地計算時與處理器的結構相關的能耗常數[25]；最大時延約束為TDL=1.3 s；偏好因子ω1=0.5,ω2=0.5；基站與基站間、基站與數據驅動端進行數據傳輸的傳輸速率R= 1 Gbps。

為了比較算法性能，本文考慮了5種已有的啟發式基準方案和1種最優拉格朗日法基準方案，即：(1) 啟發式基準方案1：完全本地計算，所有任務都在無線設備端進行本地計算。(2) 啟發式基準方案2：單服務器卸載，所有任務僅由無線設備和第一個基站分配。(3) 啟發式基準方案3：混合比例卸載，所有任務由本地和服務器按比例完成任務分配和計算。(4) 啟發式基準方案4：固定無線設備發射功率，即令pi=0.4 W。(5) 啟發式基準方案5：粒子群算法[27]，其中學習因子 C1= 2，C2=2，慣性權重W=0.4。(6) 最優拉格朗日乘子法基準方案6：拉格朗日乘子法[22]，采用內點法進行迭代求解。

圖2顯示了本文所提方案與最優拉格朗日乘子法基準方案6的運行時間隨不同無線設備數目變化的曲線。隨著無線設備數目K的增加，本文所提方案和最優拉格朗日法基準方案6的運行時間均增加。本文所提方案的運行時間明顯少于最優拉格朗日乘子法基準方案6。隨著K增大，本文所提方案和最優拉格朗日法基準方案6的運行時間差距呈現增大的趨勢。例如，較最優拉格朗日法基準方案6，當K=17時，本文所提算法能節省1.5 s的運行時間，當K=45時，本文所提算法能節省2.6 s的運行時間。

圖2 不同無線設備數目K下的系統運行時間Fig.2 System runtime under different number of wireless device K

圖3顯示了能耗與系統時延加權和隨不同輸入數據量 αi變化的性能曲線，其中K=10，輸出數據量γi=106bit，由圖可知，6種方案的時延與能耗的加權和性能均隨著輸入數據量的增大而增加，其中本文提出的優化方案優于其他基準方案1、2、3和4?？紤]到時延約束的影響，當輸入數據較小時，可以全卸載進行計算，基準方案5可以很快收斂到最優系統性能，隨著輸入數據的增大，本文所提方案的時延與能耗加權和會逐漸接近基準方案3，數據會分配到本地進行處理；基準方案5中的粒子群可能會陷入局部最優，但可以通過較低的復雜度接近本文所提方案的系統性能；本文提出方案能取得和基準方案6相似的系統性能，但在大規模用戶的情況下，該算法的計算復雜度遠大于本文提出方案。

圖3 不同輸入數據量α i下的時延與能耗加權和性能Fig.3 Time delay and energy consumption weighted sum versus different input data size αi

圖4顯示了能耗與系統時延加權和隨不同輸出數據量 γi變 化的性能曲線，其中K=10，輸入數據量αi=107bit。由圖可知，隨著輸出數據量的增加，基準方案具有緩慢的增長趨勢。本文提出的方案在時延約束下優于其他已有的啟發式基準方案?；鶞史桨?的時延與能耗加權和不如本文所提方案和其他基準方案，這說明將計算任務卸載到邊緣服務器進行計算能有效地減少時延與能耗的加權和。且本文所提方案在大規模用戶條件下能以較低的復雜度達到與基準方案6相同的系統性能。

圖4 不同輸出數據量γ i下的時延與能耗加權和性能Fig.4 Time delay and energy consumption weighted sum versus output data size γi

圖5顯示了能耗與系統時延加權和隨不同時限TDL變 化的性能曲線，其中無線設備數量K=10，任務輸入數據量αi=107bit，任務的輸出數據量γi=106bit。由圖5可知，隨著所需時延約束的增加，本文所提方案和基準方案2、4、5和6都在減小，系統將數據更多地卸載到邊緣端進行計算，使得總體性能提升，當TDL取值較大時，雖然系統性能有所提升，但會使得任務完成總時延過大。當時延約束大于1.5 s時，本文提出方案和基準方案5、6均達到最優，但會造成過多的時延浪費，當時延約束小于1.5 s時，本文所提優化方案的性能優于其他基準方案1、2、3、4、5，并以較低的復雜度達到基準方案6所示的最優解。

圖5 不同時延長度T DL下的時延與能耗加權和性能Fig.5 Time delay and energy consumption weighted sum versus different delay length TDL

圖6顯示了系統時延和能耗的加權和隨著無線設備數量的增長變化的性能曲線。無線設備的數量從5增加到50，其中無線設備任務輸入數據量αi=107bit，任務的輸出數據量γi=106bit。由圖6可知，隨著無線設備數量的增加，優化方案和其他基準方案的時延與能耗加權和都在增加，這是因為無線設備個數的增加使得系統需要處理的計算任務增加，完成這些增加的計算任務需要更多時間與能耗。與已有的啟發式基準方案1、2、3、4和5相比，本文所提優化方案有較大的優勢；且能在較少的算法運行時間下達到最優拉格朗日乘子法基準方案6的系統性能。

圖6 不同無線設備個數K下的時延與能耗加權和性能Fig.6 Time delay and energy consumption weighted sum under different number of wireless device K

圖7顯示了能耗與系統時延加權和隨無線設備計算能力變化的性能曲線，其中無線設備數目K=10，任務輸入數據量 αi=107bit，任務的輸出數據量γi=106bit。由圖7可知，隨著無線設備計算能力的增長，本地能耗會增大，而計算時延會減小，基準方案1由于完全本地計算，能耗的影響會大于計算時延的影響，所以增長速率最快?；鶞史桨?考慮到單服務器資源有限，增長速率會高于本文所提方案?；鶞史桨?更傾向于卸載任務到基站端進行計算，無線設備計算能力的增長對其沒有影響?；鶞史桨?能夠達到較低的計算復雜度，但會陷入局部最優，而本文所提方案能夠以相對基準方案6較小的復雜度達到其最優解。

圖7 不同無線設備計算能力 fi下的時延與能耗加權和性能Fig.7 Time delay and energy consumption weighted sum of wireless devices versus computing capacities fi

4 結論

本文研究了雙MEC服務器協同與計算通信資源聯合優化設計方案，以系統計算時延和用戶能耗的加權和最小化為準則，聯合優化用戶計算任務分割和計算卸載發射功率。本文提出一種較低計算復雜度的算法方案，將原聯合設計問題解耦為計算卸載和任務分割的2個子問題，分別采用內點法和單純形法實現快速數值求解。仿真結果表明，本文所提算法的系統性能優于已有的啟發式基準方案，并在較低的算法運行時間下，本文所提方案能取得與最優拉格朗日乘子法基準方案相同的系統性能。