移動邊緣網絡下服務緩存與資源分配聯合優化策略

龍隆，劉子辰，陸在旺,2，張玉成,2，李蕾,2

（1.中國科學院計算技術研究所，北京 100190；2.中國科學院大學計算技術研究所，北京 100049）

0 引言

隨著移動通信與物聯網的高速發展，許多計算密集和時延敏感應用（如無人駕駛、圖像識別以及自然語言處理等）產生，這類具有低時延高可靠特點的應用對終端設備的計算能力提出較高要求[1]。由于計算能力有限的終端設備在處理這類應用時將產生較高的任務時延，因此如何降低應用處理時延是目前亟待解決的關鍵問題之一。移動云計算（MCC,mobile cloud computing）技術的出現很好地解決了終端計算能力受限的問題。MCC 的目標是將云端豐富的計算資源擴展至資源受限的終端設備，從而增強終端設備潛在的計算能力[2-4]。終端設備與云服務器間較遠的通信距離所產生的網絡時延使單純依靠MCC 無法滿足時延敏感型應用程序的時延要求。為了克服以上問題，并對MCC 技術進行補充，移動邊緣計算（MEC,mobile edge computing）作為一種新的技術被提出[5-6]。移動邊緣計算主要由基站及其邊緣服務器組成。當終端設備執行計算任務時，由基站與服務器組成的邊緣節點可以就近為這些終端提供計算、通信以及數據存儲等服務，從而降低任務執行時延、提高系統性能。目前，基于MEC 網絡的任務卸載和資源分配等問題已有相關研究。文獻[7-9]在不同應用場景下以最大化能效為目標，對系統頻譜資源和功耗等進行聯合優化。文獻[10-11]分別以最小化能耗、時延為目標，對計算與頻譜資源進行聯合優化。然而在實際應用中，邊緣服務器的計算資源與存儲資源是有限的，過多的計算請求必然為邊緣服務器帶來較高的計算與存儲壓力，進而影響系統性能。MCC 與MEC 融合網絡下的資源分配與卸載方案為解決以上問題提供了新的解決思路。在MCC 與MEC 融合的網絡架構中，終端設備進行任務請求時，既可以在本地執行，也可以在邊緣服務器或云端執行。因此，該網絡架構可以為終端提供更高效且更靈活的卸載服務，從而滿足不同的服務需求。目前已有相關研究表明，在三級網絡架構下通過卸載決策與資源分配聯合優化的方式可以提升網絡性能[12-13]。在MEC 與MCC 融合的集中式網絡下，文獻[12]對卸載決策與資源進行聯合優化，以降低所有終端的任務時延；文獻[13]以最大化系統收益為目標，對任務卸載與資源分配進行聯合優化設計。

上述研究從不同方面解決任務卸載與資源分配聯合優化問題，但是這些研究忽略了任務卸載與服務緩存耦合性對系統性能的影響。這里的服務緩存是指將與計算任務相關的數據庫、應用程序、函數庫以及相關代碼等放在邊緣服務中，從而支持不同類型的應用程序。從任務卸載角度可以將現有MEC 研究分為兩大類，即計算任務完全卸載與計算任務部分卸載。完全卸載模型適用于高度集成或相對簡單的任務，如自然語言處理、導航等任務，這些任務不能被分割，并且只能在移動設備上執行或者作為一個整體由邊緣服務器執行。部分卸載模型適用于可分割的任務，如圖像識別、增強現實（AR,augmented reality）應用等，這類應用的任務可以被分割為多個子任務通過并行或串行的方式執行。與完全卸載模型相比，基于部分卸載模型的資源分配更加合理，資源利用率也更高。目前，關于服務緩存與資源分配已有相關研究。文獻[14]以最小化供應商成本為目標，提出了一種整數線性規劃和隨機搜索算法，對邊緣節點間的服務緩存資源進行優化。文獻[15]以最小化服務緩存總成本為目標，對邊緣服務器的位置和用戶服務需求進行聯合優化。文獻[16]以最小化時延與成本為目標，對邊緣服務器的內容緩存進行協同優化。盡管以上研究通過任務卸載與服務緩存優化使系統性能得到提升，但都是基于任務不可分的情況進行的資源分配優化，而對任務可分的情況不適用。

大多數復雜的應用程序由多個不同的執行組件組成，如執行實時面部識別任務時需要將其分為4 個子任務分別處理，即人臉檢測、圖像處理與特征提取、人臉識別。這些子任務所需的計算資源、存儲資源以及帶寬資源各不相同。因此，如何基于部分任務卸載和服務緩存聯合優化是目前亟待解決問題。文獻[17]通過構建服務鏈模型，在存儲資源以及計算資源約束下以最小化網絡響應時延為目標，通過開放馬爾可夫排隊網絡模型構建邊緣節點服務調度模型，并對緩存決策與計算資源聯合優化，但在任務卸載過程中忽略終端設備以及云服務器資源等可用資源。文獻[18]基于部分卸載模型，在計算資源約束下對服務緩存與任務卸載進行聯合優化研究，但其假設帶寬資源均勻分配，導致計算數據量較大的任務得到較少的帶寬資源而產生較高時延，計算數據量較少的任務得到較多的帶寬資源造成資源浪費。另外，文獻[18]并未對邊緣節點的存儲空間進行約束，這意味著在該研究中邊緣服務端擁有無限大的存儲空間，可以緩存所有任務執行所需的相關數據，這在實際應用場景下顯然不合理。

綜上所述，本文將在終端、邊緣服務以及云構成的三層網絡架構下，綜合考慮無線帶寬資源、計算資源以及存儲資源等因素。通過計算、通信、存儲融合的思想，以最小化所有終端設備的任務時延為目標，綜合考慮存儲資源、計算資源、卸載決策以及任務卸載比例等對任務時延的影響，提出一種服務緩存與資源分配的聯合優化算法。具體創新點介紹如下。

1) 構建了一個由多用戶、邊緣服務器以及云服務器組成的三層網絡架構，每個用戶的計算任務可以通過部分卸載的方式將任務分別卸載至本地、邊緣服務器或云服務器。引入了最小化終端任務時延模型，考慮了用戶計算資源、邊緣服務的計算資源、存儲資源以及帶寬資源等因素對時延的影響。

2) 提出了服務緩存與資源分配聯合（JSCRA,joint service caching and resource allocation）優化策略。首先，將原問題的連續變量與離散變量進行解耦，變為2 個子問題，即服務緩存決策問題、計算資源與通信資源聯合優化問題。其次，基于重構線性化技術（RLT,reformulation linearization technique）、松弛以及凸優化方法對2 個子問題進行交替迭代優化。最后，獲得問題次優解。

3) 仿真結果表明，與隨機緩存和資源分配（RCRA,random caching and resource allocation）策略相比，所提策略在收斂速度和性能表現上都有明顯優勢，可以獲得更低的任務時延。

1 系統模型

1.1 集中式移動邊緣網絡模型

集中式移動邊緣網絡如圖1 所示。從圖1 可以看出，集中式移動邊緣網絡由云服務器、單一服務節點（由邊緣服務器與基站組成）以及L個具有計算與通信能力的終端組成。這里的終端泛指具有計算能力的終端設備，如手機、平板電腦、車輛等。終端個數表示為L={1,2,…,L}，i∈L。云服務器與服務節點通過光纖進行有線連接，為終端提供穩定的通信、計算以及存儲服務。這里的云服務器主要由云服務器集群組成，因此擁有豐富的計算資源與存儲資源。

圖1 集中式移動邊緣網絡

在圖1 所示場景中，服務節點不僅可以為終端提供通信、計算以及存儲資源，而且扮演著協調器的角色，即根據終端的任務請求提供存儲決策以及計算決策。這里假設邊緣服務器存儲計算服務的最大存儲容量為C，最大計算能力為F。計算服務數據主要由數據庫、數據字典以及相關的應用代碼組成，其中每一種應用代表一個類型的計算任務。此外，由于存儲是一個長期的過程，因此需要服務緩存進行定時更新。本文認為系統在離散的時間段中運行，每個時間段的持續時間與服務緩存和任務分配決策更新的時間尺度相匹配。本文對其中一個時間段進行研究，忽略其他時間段的索引[18]。在一個時間段的開始階段，每個終端隨機請求一個計算任務，其中一類計算任務對應一類計算服務。這里假設存在計算服務K={1,2,…,K}，表示用戶i請求計算服務Ai相應的任務，Ai∈K，其中，表示終端i執行服務Ai相關任務的輸入數據大小，si表示執行1 bit 數據所需循環數。為了便于分析，本文做出如下合理假設。

1) 服務節點已知信道狀態信息（CSI,channel state information）、每個任務輸入數據的大小以及執行任務所需的循環數。基于以上假設，可以得到優化的卸載決策以及資源分配[19]。

2)每種應用的計算結果數據都遠小于計算輸入數據，因此忽略計算結果的回程鏈路傳輸時延[20]。

1.2 通信模型

本文采用正交頻分復用的方式將頻譜資源分配給終端設備，頻譜的總帶寬為B。由于每個終端設備將計算任務卸載至服務節點時會占用上行頻譜資源，因此終端i執行服務Ai相關任務的上行傳輸速率可以表示為[12]

其中，為終端上傳數據所占上行帶寬百分比，Pi,s為終端的發送功率，hi,B為基站與終端間的信道衰落系數，d為終端與基站的距離，r為路徑損耗，σ2為信道的噪聲功率。

1.3 服務緩存模型

若邊緣服務器存儲計算服務，則意味著服務節點可以處理相關的計算任務，否則將任務交由云服務器執行。由于邊緣服務器的存儲空間有限，故無法滿足所有終端設備的計算請求，因此邊緣服務器需要對所緩存的服務數據進行決策。這里將服務端的存儲決策表示為，∈ { 0,1}且Ai∈K，i∈L；表示服務器是否緩存終端設備請求的Ai，xAi=1表示服務器緩存計算服務Ai，=0表示服務器沒有緩存相應的計算服務Ai。每個服務Ai所需存儲大小為，而邊緣服務器緩存決策受到存儲容量的限制，即

1.4 計算任務卸載模型

任務部分卸載意味著計算任務可以分解成多個大小不同的子任務。本文將基于卸載模型（即向代碼分區的應用，如圖像識別，這類應用分為多個模塊，其中一個模塊的輸出結果為下一個模塊的輸入）進行研究，接下來本文將在部分卸載模型下，對任務執行時延模型進行描述。

1) 當計算服務Ai存儲在邊緣服務器時，任務可以在邊緣服務器執行，此時任務執行時延分析如下。

如果部分任務在服務節點卸載，任務卸載至邊緣服務器時，任務卸載百分比表示為1-，相應的任務卸載至邊緣服務器的數據大小表示為。分配給終端設備的計算資源表示為，任務在邊緣服務器的執行時延表示為

當任務卸載至邊緣服務器時，終端設備將占用上行鏈路對數據進行傳輸，此時上行鏈路的傳輸時延表示為

綜上所述，當計算服務存儲在服務中心時，任務執行總時延表示為

2) 當計算服務Ai未存儲在邊緣服務器時，計算任務將在本地以及云端進行部分卸載。

如果任務卸載至云服務器，卸載百分比表示為1-，其中，任務卸載至邊緣服務器的數據大小表示為。基于前文假設，云服務器具有豐富的計算資源，所以任務執行時延只與傳輸時延有關，即上行鏈路傳輸時延以及回程鏈路傳輸時延。因此，任務在云服務器執行時其傳輸時延表示為

其中，R為邊緣服務與云服務器之間的傳輸速率。因此，計算服務存儲在云服務器時任務執行總時延表示為

2 問題的形式化描述

由于存儲是一個長期統計的過程，因此其在短期內變化很小，但計算與通信資源是實時的，需要根據不同用戶的任務需求實時變化。基于以上特點，本文考慮在當前時間段內對計算、通信以及存儲資源進行聯合優化。本文的主要目標是在計算、通信、存儲資源約束條件下，對服務緩存決策x、上行頻譜資源θ、任務部分卸載百分比α和β，以及服務器計算資源f聯合優化，以最小化所有終端設備執行任務總時延。優化目標可以表示為

從P0 可以看出，約束條件C1表示分配給所有終端設備的計算資源總和小于或等于服務器的最大計算能力，C2 表示分配給所有終端設備的頻譜資源小于或等于總頻譜帶寬，C3 表示任務卸載比例，C4 表示服務緩存決策，C5 表示邊緣服務器可以緩存計算服務的最大容量。此外，P0 是由離散變量與連續變量組成的混合整數非線性規劃問題，很難求解，因此需要設計一種新的優化方法對該問題進行求解。

3 服務緩存與資源分配聯合優化策略

為了解決以上問題，本文提出一種面向任務卸載與服務緩存問題的服務緩存與資源分配的聯合優化策略，簡稱為服務緩存與資源分配的聯合優化策略。首先，將原問題的連續變量與離散變量進行解耦，變為2 個子問題，即服務緩存決策問題以及計算資源與通信資源聯合優化問題；其次，在固定緩存決策基礎上對計算與通信資源分配問題進行求解；再次，在得到優化的資源分配變量后對緩存決策進行優化；最后，通過循環迭代得到原問題的解。

3.1 計算資源與通信資源聯合優化

首先，初始化緩存決策；隨后，對計算與通信資源進行聯合優化。在給定緩存決策條件下，P0 變成由計算資源、帶寬資源以及任務卸載比例等連續變量組成的函數。接下來將對連續變量進行求解。在給定初始緩存決策為x(0)后，多終端時延優化函數表示為

相應的優化問題表示為

緩存決策確定后，其相應的約束條件同時發生變化，其約束條件將由C1變為C6。為了避免除零情況的發生，對變量加入常量ε1、ε2，可表示為。最后將該變量代入式(10)以及對應的約束條件中，得到新的函數以及約束條件。相應的問題表示為

由P2 可以看出，式(12)中存在2 個變量相乘的乘積項，因此該問題是一個非凸優化問題。為了求解P2，需要對以上問題進行再次變換。

3.2 基于RLT 的問題轉換

其中，{·}LS表示線性化步驟。將代入式(14)可得

其中，?i∈L。同理，對應的RLT 因子積約束條件為

經過以上變換后，得到新的優化問題P3 為

3.3 緩存優化問題的解決

獲得P1的解后，下面解決緩存決策問題。首先，將獲得的資源分配方案α(0)、β(0)、θ(0)、f(0)代 入P0，得到緩存決策問題P4 為

P4 是0-1 問題，可以通過分支定界法對以上問題進行求解。然而，分支定界法在最壞的情況下需要運算2k次，當輸入數據量較小時，其復雜度是可接受的；隨著輸入數據量的增大，則很難在有效時間內獲得近似最優解。為了降低時間復雜度，本文將整型變量松弛成的連續變量。此時，P4 變為凸優化問題，可以通過內點法與KKT（Karush-Kuhn-Tucker）條件進行求解。隨后采用四舍五入的方法對連續變量進行恢復，這里將閾值簡單設置為0.5。

3.4 算法描述

基于上述分析可知，邊緣服務器通過階段性獲取當前接入終端的完整信息，執行JSCRA 優化策略，并將緩存決策以及資源分配結果發送至終端設備，從而最小化所有設備任務的執行時延，具體步驟如算法1 所示。

算法1服務緩存與資源分配聯合優化算法

初始化邊緣服務的緩存策略，終端發射功率pi,s，任務的輸入數據大小，每比特輸入數據所需的計算量si，最大迭代次數tmax，算法終止條件ξ。

步驟1在已知服務緩存策略基礎上，原問題變換為連續非線性問題，得到新問題P2。

步驟2通過RLT 技術對P2 松弛，將非線性問題變為凸優化問題P3。

步驟3采用內點法對P3 進行求解，并得到在已知緩存決策條件下的資源分配方案。

步驟4將步驟3 得到的解代入P4，通過松弛法以及凸優化方法得到相應的卸載決策。

步驟5獲取步驟3 與步驟4 中目標函數的差值，如果差值小于ξ或者迭代次數達到最大值tmax，則停止計算；否則，對步驟3 以及步驟4 進行循環迭代。

4 仿真實驗與性能評估

本節在MATLAB 2017b 上進行仿真實驗，并分析JSCRA 優化策略的性能。此外，為了進行性能對比，本文對以下基準策略進行了仿真。

完全本地卸載（LOC,local offloading completely）策略：所有任務均在終端本地進行處理，此時假設本地終端存儲任務相關的服務數據[21]。

完全卸載至云（COC,cloud offloading completely）策略：任務相關服務數據全部存儲在云服務器，此時任務完全在云服務器執行，而上行鏈路帶寬資源均勻分配給每個終端設備[18]。

隨機緩存與資源分配（RCRA,random caching and resource allocation）策略：在存儲約束條件下，邊緣服務器采用隨機緩存策略盡可能多地緩存服務內容并在其基礎上對計算與帶寬資源進行優化[18]。

4.1 仿真參數設置

在仿真實驗中，終端設備的數量為10，隨機分布在邊長為500 m 的正方形區域內。hi,B服從均值為1 的指數分布[22]，計算任務數據大小表示為ci且服從[100,200]KB 的均勻分布，si設置為1 500 cycle/bit。仿真參數設置如表1 所示。

表1 仿真參數設置

4.2 算法復雜度與收斂性分析

由于原始問題P0 是混合整數非線性規劃問題，通過窮舉法求解問題的復雜度為O(2n)，呈現指數級增長。所提算法將原始問題P0 轉換成為P3 與P4，P3 為標準凸優化問題，可以通過內點法解決，內點法的復雜度為O(n3)；P4 為0-1 問題，離散變量經過松弛后為凸優化問題，其算法復雜度為O(n3)，此外，交替迭代次數的復雜度為O(n)，因此，所提算法總體復雜度為O(n3)。與窮舉法相比，所提算法復雜度大大降低。

算法收斂過程如圖2 所示。本文將通過窮舉法獲得的值作為最優解。由于窮舉法非常耗時，因此一般在小規模場景下使用。由圖2 可以看出，所提算法通過迭代25 次快速收斂并接近最優解，這表明所提算法性能非常接近于窮舉法的性能，并可以獲得近似最優解。

圖2 算法收斂過程

4.3 仿真結果和分析

本節仿真結果是在配置有 Intelcorei59400F 2.9 GHz 處理器和 16 GB RAM 的臺式機上用MATLAB 2017b 實現的。在N=10，C=300 GB，R=1的條件下，邊緣服務器的計算能力和存儲能力對任務執行時延的影響分別如圖3 和圖4 所示。

圖3 邊緣服務器的計算能力對任務執行時延的影響

圖4 邊緣服務器的存儲能力對任務執行時延的影響

從圖3 可以看出，隨著邊緣服務器的計算能力逐漸增大，所提JSCRA 優化策略與RCRA 策略的任務執行時延逐漸減小，而LOC 策略以及COC策略任務執行時延保持不變。這是因為LOC 策略的任務時延僅與本地計算能力有關，任務執行時延與邊緣服務器所擁有的資源沒有關系，所以LOC策略的所有任務執行時延保持不變。對于COC 策略而言，當任務在云服務器執行時，其任務執行時延僅與無線帶寬資源以及回程鏈路傳輸速率有關，因此COC 策略的任務執行時延不隨邊緣服務器計算能力的增大而改變。另外，從圖3 還可以看出，JSCRA 優化策略在性能上略優于RCRA 策略，這是因為JSCRA 優化策略對服務緩存進行合理優化，使更多任務可以在邊緣服務器中執行，因此性能優于RCRA 策略。

從圖4 可以看出，隨著邊緣服務器的存儲能力逐漸提升，所提策略與RCRA 策略任務執行時延逐漸減小，而LOC 策略以及COC 策略的任務執行時延保持不變。所提策略與RCRA 策略相比可以減少10%的任務執行時延，與COC 策略相比可以減少30%的任務執行時延。LOC 策略的任務執行時延僅與本地計算能力有關，COC 策略的任務執行時延與帶寬資源以及回程鏈路傳輸速率有關，所以LOC 策略與COC 策略的任務執行時延不隨邊緣服務器存儲能力的大小變化。此外，從圖4 可以看出，隨著邊緣服務器存儲能力的增加，與COC 策略相比，所提策略與RCRA 策略性能增益增大。這是因為當邊緣服務器存儲能力較小時，只能緩存部分計算服務，剩余服務將存儲在遠端云服務器。此時，大多數任務將在云服務中執行，因此所提策略與RCRA 策略的任務執行時延性能略優于COC 策略。但是，隨著存儲能力的增加，邊緣服務器可以緩存的服務內容增多，遠端執行任務比例逐漸降低，此時邊緣服務器計算資源被充分利用，因此所提策略與RCRA 策略的性能顯著優于COC 算法。

任務輸入數據大小對任務執行時延的影響如圖5 所示。從圖5 可以看出，任務輸入數據越大，所有策略的任務執行時延越大，而所提策略的性能優于其他策略。這是因為隨著輸入數據量的增大，任務所需的計算資源與通信資源將會增多，所有策略的任務執行時延逐漸增大。另外，由于所提策略對計算、通信以及存儲資源進行聯合優化，因此其性能優于其他策略。

圖5 任務輸入數據大小對任務執行時延的影響

邊緣服務器與遠端云間傳輸速率對任務執行時延的影響如圖6 所示。從圖6 可以看出，隨著邊緣服務器與遠端云間的傳輸速率逐漸增大，所提策略與RCRA 策略、COC 策略的所有任務總時長逐漸減小，當R=5 時，上述3 種策略性能基本相同。這是因為當邊緣服務器與遠端云間傳輸速率較小時，任務卸載至云服務器的時延大于在邊緣服務器的執行時延，此時大部分任務將在邊緣服務器執行，因此所提策略性能優于RCRA 策略以及COC 策略。隨著傳輸速率增大，任務在云端執行的時延與任務在邊緣服務器執行時延越來越接近，因此所提策略與RCRA 策略以及COC 策略的性能差異將越來越小，這也表明所提策略在傳輸速率較小時可以獲得較高的性能增益。此外，LOC 策略任務執行時延沒有變化，這是因為任務本地時延與終端自身計算資源有關與邊緣服務器，而與云端間的傳輸速率無關。

圖6 邊緣服務器與遠端云間傳輸速率對任務執行時延的影響

5 結束語

在多終端、單服務節點以及云服務器組成的集中式移動邊緣網絡下，針對任務卸載與服務緩存耦合性對任務時延的影響，本文提出了一種服務緩存與資源分配的聯合優化策略。首先，在計算、通信以及存儲容量約束下，建立服務緩存與資源分配聯合優化問題。隨后，將原問題進行分解為2 個子問題并通過重構線性化方法、松弛以及凸優化方法對其進行交替迭代優化。仿真結果表明，與RCRA 策略、LOC 策略和COC 策略相比，所提策略可以有效地降低系統時延并具有良好的收斂性。