基于次模優化的邊云協同多用戶計算任務遷移方法

梁冰，紀雯

（1.中國科學院計算技術研究所，北京 100190；2.中國科學院大學計算機科學與技術學院，北京 100190；3.移動計算與新型終端北京市重點實驗室，北京 100190；4.鵬城實驗室，廣東 深圳 518055）

1 引言

隨著人工智能和物聯網移動應用的快速發展，自然語言處理、增強現實、人臉識別、行為分析等高計算能力和通信資源需求的服務被廣泛地應用在各種移動終端設備中。由于移動終端設備受到電池電量、計算能力和存儲空間等限制，通常難以滿足上述應用的超低時延和低能耗的需求。因此，高資源需求的應用服務與資源受限的移動設備之間的鴻溝給當前及未來物聯網移動應用的發展帶來了極大挑戰[1-3]。

針對上述挑戰，移動云計算（MCC,mobile cloud computing）的提出為這些應用需求提供了新的解決思路[4-5]。MCC 利用無線網絡將移動終端的應用任務卸載到計算能力更強的云端執行，可以解決終端計算能力不足的問題，并降低終端能耗。然而，云服務器往往位于遠離用戶終端位置的核心網，因此終端與云服務器之間的數據交換過程需要花費較多的傳輸時間和能耗。并且，針對許多特定的應用，例如語音識別、智能環境控制等，較長的時延會損害用戶的使用體驗并影響相關應用的性能表現。

為了解決上述移動云計算的缺點，歐洲電信標準化協會（ETSI,European Telecommunications Standards Institute）提出了一種新型的計算和存儲服務技術——移動邊緣計算（MEC,mobile edge computing）[6-7]。MEC 作為5G 的一項核心技術，通過將服務器部署在離用戶更近的邊緣位置，例如附近的網關和基站側，能更有效地解決用戶對特定應用服務的需求，例如高計算能力、存儲服務、高可靠性、移動性支持和低時延等[8-10]。利用MEC 網絡將地理分散的用戶的計算任務從移動終端設備遷移到資源豐富的MEC 服務器，從而加快任務的執行[11-12]。然而，受限于移動邊緣計算網絡的通信能力以及MEC 服務器的計算資源和存儲容量的限制，卸載過多的計算任務到邊緣側會給計算資源有限的MEC 服務器及網絡傳輸帶來沉重的負擔，進而降低邊緣計算服務的用戶體驗[13-14]。對于上述云計算和邊緣計算所存在的缺點，結合各自優勢的基于邊云聯合計算的方式為當前的應用需求提供了新的解決思路。然而，如何平衡云端和邊緣端的計算任務的負載，提高邊云聯合計算的服務質量，成了邊云聯合計算待解決的關鍵問題之一[15-16]。

本文提出了一種基于邊云聯合計算下的多用戶任務卸載方案，該方案聯合考慮了用戶任務卸載選擇、邊緣端和云端的通信及計算資源分配的問題，進而最大化系統的效用。本文的主要貢獻如下。

1) 基于用戶QoE（quality of experience）的效用函數，將用戶任務卸載選擇以及邊緣端和云端的通信、計算資源分配的問題表示為一個混合整數非線性規劃（MINLP,mixed integer nonlinear programming）問題。本文以最大化系統效用為目標，對用戶的任務卸載決策、發射功率、邊緣節點的計算資源分配以及回程鏈路的通信資源分配等問題進行了聯合優化。

2) 本文將原始的系統效用最大化問題分解成2 個子問題，分別為固定用戶的卸載決策后的資源分配問題以及優化資源分配問題后對應的最優值函數下的任務卸載決策問題。對于資源分配問題，本文進一步將該問題分解為用戶上傳發射功率分配問題、邊緣端計算資源分配問題和核心網傳輸帶寬分配問題，并利用擬凸和凸優化技術對上述3 個問題進行了求解。

3) 通過對用戶系統效用函數的分析，本文從卸載決策的角度證明了系統效用函數是一個次模函數，進而基于次模理論設計了一種貪心的卸載策略算法用來求解用戶任務的卸載決策問題。仿真實驗結果表明，與其他卸載方案相比，本文提出的基于邊云聯合的計算方案下的用戶卸載方法能夠有效降低用戶任務執行時延和能耗，并且在資源受限的條件下仍然能夠保持穩定良好的系統效用值。

2 相關工作

如今，國內外學者開展了大量針對移動云計算和移動邊緣計算的任務卸載問題的研究。文獻[17]研究了動態環境下的多用戶計算卸載問題。考慮到多個物聯網設備同時通過無線信道卸載計算任務時的信道干擾問題，該研究將用戶的計算卸載決策問題表述為一種進化博弈的模型，并設計了一種基于強化學習的進化博弈算法用來求解用戶的卸載決策。文獻[18]研究了基于車輛邊緣計算網絡中的計算卸載問題。考慮到車輛需要在動態網絡環境下實時確定其任務卸載策略，該研究提出了一種多用戶非合作計算卸載博弈，以調整車輛邊緣計算網絡中每輛車的任務卸載概率，并同時考慮了車輛與邊緣計算接入點之間的距離。進一步地，該研究基于計算卸載博弈模型構造了分布式最佳響應算法，以最大化每種車輛的效用。文獻[19]構建了適用于移動和普適計算場景的三層架構下的用戶卸載問題，提出了一種分布式的均衡計算算法用來確定用戶的計算任務卸載的決策。文獻[20]研究了動態環境下移動云計算的多用戶計算卸載問題，考慮到移動用戶在將計算任務卸載到移動云上的自利性和自私性，將動態環境下移動用戶的卸載決策過程描述為隨機博弈問題，最后求解用戶的卸載決策。文獻[21]提出了移動邊緣計算和云計算的聯合卸載優化問題，并設計了一種基于博弈論的卸載調度和負載均衡方案，但該研究僅對分層框架下的用戶卸載決策進行了建模與優化，并未優化邊、云的計算以及通信資源的分配問題。上述相關研究對用戶任務卸載的決策問題給出了一些求解的方法，但是這些研究主要集中在用戶的卸載決策問題上，忽略了卸載過程中系統有限的通信與計算資源分配的問題。針對上述研究存在的問題，文獻[4]研究了基于移動邊緣云計算的無線信道干擾環境下的多信道多用戶的計算卸載問題，提出了一種分布式的用戶計算卸載算法并聯合考慮了邊緣云的計算資源分配問題。文獻[22]以移動邊緣計算系統下的用戶移動設備能耗最小化為目標，提出了一種計算卸載、子載波分配和計算資源分配的聯合優化策略，并設計了一個有界改進分支定界算法來尋找全局最優解。文獻[23]提出了一種聯合用戶計算任務部分卸載和資源分配的方案，聯合考慮所需能耗、部分卸載和資源分配約束條件，最大程度地減少所有設備任務執行產生的時延之和。文獻[24]提出了一種由半定松弛、交替優化和連續調節組成的三步算法，聯合優化了用戶任務的卸載決策以及計算和通信資源的分配，以最大限度地降低所有用戶執行任務產生的能耗和時延。文獻[25]考慮了移動邊緣計算用戶計算卸載的花費和時延問題，該研究以最小化移動設備系統花費和時延為目標，提出了一種多目標的計算卸載與資源分配的算法，以聯合優化用戶的卸載決策以及邊緣端的資源分配。文獻[26]面向工業物聯網場景下的霧節點計算任務，以霧節點能耗最小化為目標，提出了一種節能的計算卸載方案，并綜合考慮了霧節點能耗、本地計算、傳輸狀態和等待狀態的能耗。針對該能耗最小化問題，該研究提出了一種加速梯度算法，可以快速找到最優的任務卸載比，從而提高了傳統方法的收斂速度。文獻[27]考慮了基于移動邊緣計算的節能卸載框架并聯合優化無線通信資源和計算資源，以最小化用戶設備的能耗為目標，設計了基于基尼系數的貪婪啟發式算法以降低用戶的能耗。文獻[28]研究了5G 異構網絡的MEC 節能計算卸載機制，以最小化系統能耗為目標，聯合優化任務卸載和無線資源分配問題，并結合5G 異構網絡的多址特性，提出了一種節能計算卸載（EECO,energy-efficient computation offloading）算法，有效提升了系統能耗的效率。文獻[29-30]研究了邊緣端或近端云的聯合用戶卸載決策與資源優化的問題，并分別提出了一種啟發式的卸載決策算法提升系統的效用。但上述研究僅考慮用戶任務只向邊緣端或云端進行任務卸載，并未考慮在邊云聯合計算的環境下用戶如何進行卸載的策略以及資源的優化問題。

綜上所述，已有的相關研究主要包含以下2 個方面：1) 在不考慮通信及計算資源分配的情況下，優化云或邊緣計算的用戶卸載決策；2) 針對云或邊緣計算的用戶任務卸載，聯合優化用戶的卸載決策以及資源分配的問題。然而，在實際應用場景中，當選擇任務卸載的用戶數量增多時，考慮到邊緣節點的計算能力以及遠端云傳輸帶寬的受限性，僅面向云端或邊緣端的任務卸載將帶來任務卸載的高時延性問題[1]。當多用戶選擇將任務卸載到云端時，由于遠端的云需要支撐大量用戶的接入需求，因此還需要考慮傳輸過程中核心網有限的帶寬資源分配問題。針對上述問題，本文研究了基于邊云聯合計算下的任務卸載方法，聯合優化了該方法下的用戶計算任務卸載決策、邊緣端計算和通信資源及遠端傳輸過程中核心網有限的帶寬資源分配。并且，本文提出的方法還能夠解決僅考慮邊緣計算或云計算情況下的用戶計算卸載問題，因此具有更廣泛的適用性。

3 系統模型

如圖1 所示，本文給出了基于邊云聯合計算的任務卸載框架的系統模型。系統模型由一個宏eNode B（MeNB）和其所覆蓋小區內的多個終端設備用戶組成。該宏eNode B 配備了邊緣計算服務器并通過核心網與遠端的云服務器相連。

圖1 邊云聯合計算的多用戶任務卸載框架

本文定義MeNB 覆蓋下的用戶數量的集合為U={1,2,…,U}，u∈U 表示該用戶集合中的某一個用戶。設用戶u需要執行的計算任務為Tu={du,cu}，且該任務不可再分割。其中du為該任務執行需要傳輸的數據量（例如系統的設置、參數的設置以及程序代碼等），cu為該任務執行所需要的計算資源（例如完成該任務所需要的CPU cycle 總數）。每個用戶可以選擇的任務執行模式如下：1) 本地計算，即用本地的終端設備處理任務；2) 邊緣計算，即通過蜂窩網絡將任務卸載到MeNB 后，在邊緣計算服務器處理任務；3) 云端計算，首先通過蜂窩網絡將任務卸載到MeNB 后，再通過核心網傳至遠端的云服務器處理。此外，本文定義了任務卸載決策變量xu,j={0,1}。其中xu,j=1表示用戶u選擇模式j進行計算，xu,j=0表示用戶u選擇其他模式進行計算。j=0,1,2 表示所選擇的任務執行模式，其中j=0 表示本地計算，j=1 表示邊緣端計算，j=2 表示云端計算。接下來，本文將分別給出本地計算、邊緣端計算及云端計算。

3.1 本地計算

根據文獻[20,28]，用戶執行任務Tu的能耗可表示為

3.2 邊緣端計算

當用戶選擇通過將任務卸載到邊緣端及云端時，完成任務的總時間包括：1) 用戶將計算任務上傳至MeNB 所需的時間；2) 用戶任務在MEC的執行時間；3) 將任務完成的結果從MEC 傳輸到用戶設備的時間。如果該任務卸載到云端執行，則完成該任務的總時間除了包含將任務上傳至MeNB 所需的時間外，還包含：1) 用戶將計算任務從MeNB 上傳至云端所需的時間；2) 用戶任務在云端的執行時間；3) 將任務完成的結果從云端傳輸到MeNB 的時間。由于通常情況下，任務完成的輸出結果的大小遠遠小于任務的輸入大小，并且考慮到傳輸的下行速度遠大于上行速度，因此本文忽略任務從云端傳輸到MEC 的時間以及MEC 傳輸到用戶設備的時間[29,33-34]。

本文考慮上傳時用戶網絡為多用戶正交頻分多址接入（OFDMA,orthogonal frequency division multiple access）系統，該系統中的每個信道都是正交的，因此可以忽略小區內的干擾。定義B為系統的無線鏈路的上行帶寬，則每個用戶可用的上行帶寬，其中N為小區內的用戶數量。由此，得到用戶u的任務Tu的上行傳輸速率為

其中，pu表示用戶u上傳任務的輸入為du時的發射功率，pu為正數且不超過允許的最大值Pu，即0

接下來，給出用戶u的任務Tu在MEC 的執行時間。本文設MEC 服務器的計算資源上限為fe，其表示邊緣服務器可用的CPU cycle 總數。所有請求將任務卸載到MEC 服務器進行計算的用戶共同分享MEC 服務器的計算資源。定義MEC 服務器分配給卸載到邊緣的用戶u的計算資源大小為，且。由于MEC 服務器計算資源有限，分配給所有將任務卸載到邊緣端的用戶的計算資源總和不能超過MEC 服務器的計算資源的上限，因此滿足約束條件，即

根據式(4)和式(6)，可以得出當給定用戶發射功率pu時，用戶選擇邊緣計算模式執行任務卸載的總時延為

3.3 云端計算

當用戶選擇云端計算模式執行任務卸載時，假設云端給卸載任務Tu分配的計算資源大小為。盡管云端具有非常豐富的計算資源，但由于需求遠程云端計算的任務請求數量非常龐大，因此云端會為每個用戶分配固定且受限的計算資源。本文設為固定大小，且等于云端能為用戶分配的計算資源的最大值。因此，類似于式(6)，可以得出用戶任務在云端的計算時間為

考慮到在云端執行用戶任務需要通過核心網傳至遠端的云服務器，因此可以得出選擇云端執行模式時任務卸載的總上傳時延為

由于用戶僅在將任務上傳至MeNB 時有能源消耗，因此用戶通過云端計算模式產生的能耗為

3.4 基于邊緣端?云端聯合計算的系統效用最大化問題

在邊緣端?云端聯合計算框架下，用戶的QoE 主要由完成任務所產生的時延和能耗體現。基于3.1～3.3節各模式下計算卸載模型及用戶偏好，本文定義用戶u的卸載效用函數為[29-30]

在上述系統效用最大化問題中，卸載決策x與通信資源和計算資源的優化相結合。由于卸載決策x是0-1 整型向量且f、p、R是連續型向量，因此式(15)優化問題是一個MINLP 問題[35]。考慮到優化問題的表達結構，當給定卸載決策x的取值時，可以將復雜度較高的原始優化問題分解為具有較低復雜度的主問題和一系列的子問題[36]。因此，式(15)所示問題可以轉化為

由于卸載決策的限制條件C1 與資源分配策略的限制條件C2～C6 是可分離的，因此式(16)所示的優化問題可以分解為主問題和子問題，分別如式(17)和式(18)所示。

將式(15)的優化問題分解為式(17)和式(18)的優化問題并不會改變其最優解[36]，接下來，本文將分別給出式(17)和式(18)優化問題的求解方法，并最終求解出式(15)問題。

3.5 聯合優化邊云資源方法

根據式(14)的形式，當給定卸載決策x時，式(18)優化問題可以轉化為

根據式(22)的形式可以發現，當給定卸載策略x時，式(22)等號右邊的第三項為常數。對于式(22)的上傳發射功率pu、邊緣計算資源以及核心網傳輸帶寬的分配，其目標函數和約束條件可以彼此解耦。因此，可以將式(21)的優化問題轉化為求解以下3 個獨立的優化問題：1) 上傳發射功率分配問題；2) 邊緣端計算資源分配問題；3) 核心網傳輸帶寬分配問題。

3.5.1 上傳發射功率分配問題

上傳發射功率分配優化問題的表達形式為

3.5.2 邊緣端計算資源分配問題

邊緣端計算資源分配優化問題的表達形式為

證明詳見附錄2。

3.5.3 核心網傳輸帶寬分配問題

核心網傳輸帶寬分配優化問題的表達形式為

證明證明過程與引理2 的思路相同。

3.6 聯合資源分配的任務卸載策略算法

定理1系統效用函數V為次模函數

證明詳見附錄3。

根據定理1，上述系統效用最大化問題式(34)能夠被證明是NP-hard 問題[39-40]。針對該問題，本文提出了一種基于次模理論的貪心卸載策略算法，求解出問題式(34)的近似解[41-42]。

算法2基于次模理論的貪心卸載策略算法

3.7 算法時間復雜度分析

4 仿真結果

本節通過仿真實驗評估所提出的邊云聯合計算方案下的優化資源分配和多用戶任務卸載決策算法的系統效用。具體仿真環境如下：假設U個用戶隨機均勻地分布在200 m×200 m 的小區中，基站部署在小區的中心位置，N 為小區內覆蓋用戶的數量。用戶計算任務輸入數據大小du在100～1 000 KB隨機均勻分布，所對應的完成任務需要的計算資源cu（CPU cycle 總數）在[0.2,1]Gcycle 隨機均勻分布。考慮到用戶本地設備計算能力的異構性，在{0.5 GHz,0.8 GHz,1.0 GHz}集合內等概率取值[20]。參考之前研究的用戶設備功率參數值選擇[4,30]，并結合當前最新相關的實測設備功率情況，本文選擇的用戶設備計算能力所對應的={0.5 W,0.75 W,0.9 W}[32]。設用戶最大傳輸發射功率Pu=100 mW，MeNB 到云端的上行總傳輸速率Rc=100 Mbit/s[43]。其余相關仿真參數設置如表1 所示。

表1 仿真參數設置

在同等的參數設置下，本節選擇將本文提出的基于邊云聯合計算方案下的用戶卸載策略的系統效用表現分別與以下方案進行對比。

1) 本地計算：所有的用戶全部采用本地計算的方式來完成任務。

2) 基于邊緣計算的聯合資源優化的全卸載策略：所有的用戶全部將任務卸載到邊緣端執行，如文獻[44-45]，并采用3.4 節的優化資源分配方案。

3) 基于云端計算的聯合資源優化的全卸載策略：所有的用戶全部將任務卸載到云端執行，如文獻[44-45]，并采用3.4 節的優化資源分配方案。

不失一般性地，仿真結果均為各仿真實驗重復1 000 次并取平均的結果。

隨著用戶數量的變化，各方案的系統效用值的變化如圖2 所示。從圖2 可以看出，隨著用戶數量的增加，對比其他方案，本文提出的方案（以下簡稱本文方案）的系統效用值有很大的提升。當用戶數量較少時，除本地計算方案外，其他各方案的系統效用值隨用戶數量的增加而增加，且本文方案系統效用值要高于其他2 種方案。當用戶總數超過某一閾值時，伴隨著用戶數量的增加，選擇全卸載的邊緣計算和云計算方案的系統效用值會逐漸下降，且當用戶的數量超過一定閾值時，系統效用值低于本地計算方案。這是因為當卸載用戶數量過多時，受限的上行通信資源和邊緣計算資源不能為每個需求用戶提供更豐富的資源需求，進而導致更高的計算時間和傳輸時延。用戶通過全卸載的方式發送和執行任務將導致所有的用戶對有限的資源進行競爭。當卸載用戶過多時，邊緣計算方案下的邊緣節點分配給用戶的計算資源會低于本地的計算資源，而云計算方案下用戶較低的上行通信資源會導致任務卸載的傳輸時延過高，進而導致以上2 種方案的系統效用降低甚至低于本地計算的效用。而隨著用戶增加，應用本文方案下的用戶卸載策略選擇算法仍能維持較高且穩定的系統效用值。這是因為該方案能夠合理地為用戶規劃任務卸載的模式選擇，從而保證有限的計算和通信資源的最大化利用。

為了評估本文方案針對應用任務時的系統效用性能，本文選擇人臉識別這一特定的應用任務：該計算任務輸入數據大小du=420 KB，完成該任務需要的計算資源cu=1 000 Mcycle[30]，相關實驗結果如圖3 所示。

圖2 不同用戶總數條件下各方案的系統效用

圖3 特定任務下的不同用戶總數條件下各方案的系統效用

從圖3 可以看出，當針對人臉識別這一特定的任務時，本文方案的系統效用值始終高于全卸載的邊緣計算方案和全卸載云計算方案。并且隨著用戶總數逐漸增多，全卸載邊緣計算方案和全卸載云計算方案的系統效用值會逐漸下降，而本文方案依舊能夠保持穩定較高的系統效用。本文方案通過聯合邊緣端、云端以及本地端的所有可用的計算和通信資源，在用戶數量增加時依然保持系統效用平穩占優。

基于人臉識別這一特定的應用任務，在不同用戶總數的條件下，本文方案中用戶對邊緣端、云端以及本地計算模式的任務卸載的決策選擇的總數如圖4 所示。從圖4 可以看出，當用戶數量較少時，用戶更傾向于將任務卸載到邊緣端和云端執行。隨著用戶數量的增加，選擇將任務卸載到邊緣端和云端的用戶數量逐漸趨于平穩，用戶主要由邊緣端和云端計算模式向本地計算模式遷移。這是因為，隨著用戶數量的增加，受到上行通信資源和邊緣計算資源的限制，邊緣節點的計算資源和上行的通信資源逐漸不能滿足用戶的計算和通信需求，進而更多用戶愿意選擇計算資源穩定且沒有傳輸時延的本地計算模式。

圖4 特定任務下的不同用戶總數條件下各模式參與用戶數

接下來，本文分析了在人臉識別這一特定的應用任務情況下，隨著用戶對時間偏好權重的變化，即從0.1 變化到0.9 的過程中，所有用戶的平均時間消耗情況，結果如圖5 所示。從圖5 可以看出，隨著用戶對時間偏好權重的增加，任務卸載的平均時間消耗逐漸降低。從不同用戶數量下的任務平均時間消耗曲線能夠看出，當系統中有更多的用戶時，任務的平均時間消耗更多。這是由于當系統中用戶數量增加時，將有更多的用戶爭奪有限的通信和計算資源，因此每個用戶所獲得的計算和通信資源會降低，進而導致通過任務卸載方式完成任務的平均時耗增加。

圖5 不同用戶對時間偏好權重下的任務卸載平均時耗對比

5 結束語

本文提出了一種基于邊云聯合計算的多用戶任務卸載方案。本文提出的方案通過聯合考慮邊緣計算以及云計算的相關優勢特性，解決了多用戶異構任務的卸載選擇問題并實現了邊緣端和云端資源的合理分配和充分利用。通過證明系統效用函數是次模函數，本文利用次模理論設計了一種基于邊云聯合計算的貪心的用戶卸載策略選擇算法，并聯合優化了邊云聯合計算框架下計算和通信資源的分配。仿真結果表明，在面對受限的通信資源和計算資源的條件下，且當卸載計算的用戶數量增加時，本文提出的方案仍能保持穩定良好的系統效用。

附錄1 Λ(pu)嚴格擬凸性證明

附錄2 引理2 證明

附錄3 效用函數為次模函數證明