超密集網絡中多基站博弈邊緣卸載策略

王汝言，吳 和，崔亞平，吳大鵬，張 鴻

(1.重慶郵電大學 通信與信息工程學院，重慶 400065；2.重慶高校市級光通信與網絡重點實驗室，重慶 400065；3.泛在感知與互聯重慶市重點實驗室，重慶 400065)

移動應用和物聯網的快速發展，使得僅具備有限電量和計算資源的移動設備已經無法滿足當前資源密集型應用的低延遲[1]、高可靠、用戶體驗連續性等嚴格要求。為了應對以上挑戰，移動邊緣計算(Mobile Edge Computing，MEC)應運而生，移動網絡運營商和云服務提供商將以合作的形式在網絡邊緣提供豐富的通信和計算資源，增強移動設備的能力[2]。移動邊緣計算允許終端用戶通過基站卸載任務至相連的邊緣計算服務器，既滿足了移動設備計算能力的擴展需求，也減輕了云計算時回程網絡的負擔，大大減少了端到端的延遲。然而，傳統的移動邊緣計算網絡覆蓋密度較小，已很難滿足用戶日益增長的大數量連接需求；在密集用戶區域，中心計算節點的負載量過大，邊緣計算服務器中有限的資源會增加任務執行的延遲和能耗，嚴重影響用戶體驗[3]。

超密集網絡技術通過密集部署低功率小基站，不但可以提高無線網絡的覆蓋率解決網絡覆蓋盲點的問題，還可以提升無線網絡的容量，緩解用戶大規模連接的壓力，從而改善網絡的整體性能。因此，將超密集網絡技術和移動邊緣計算相結合的架構成為未來無線接入網發展的趨勢[4]。但是，超密集邊緣計算網絡中的用戶處在多個小基站覆蓋范圍內，用戶在同一時間內可訪問多個邊緣計算服務器，而不同小基站和服務器的資源情況和傳輸環境不盡相同，使得用戶會產生資源競爭和服務器選擇的問題[5]，如何為用戶進行卸載服務器關聯選擇以及資源分配來滿足用戶服務體驗具有重要意義。

針對移動邊緣計算網絡中用戶任務的卸載和資源分配，國內外研究人員進行了大量深入的研究。文獻[6]利用隨機化方法研究了多用戶移動邊緣計算系統中功耗和延遲之間的權衡，提出一種基于李雅普諾夫優化的在線算法，來解決帶有任務緩沖穩定性約束的功耗最小化問題；但該文獻的場景只考慮了單服務器的情況，存在無線與計算資源嚴重短缺，遠程云計算訪問時間過長的問題。文獻[7]在多用戶多服務器的邊緣計算網絡系統中，提出一種基于李雅普諾夫優化的在線動態卸載算法，以獲得最小的執行成本和最大數量的卸載任務。文獻[8]考慮了一個可再生移動邊緣云系統中的多用戶多任務卸載調度方案，使用李雅普諾夫優化方法來確定能量獲取策略，并提出集中式和分布式兩種貪婪算法來解決任務卸載調度問題，但這些文獻沒有考慮網絡資源的分配，降低了系統資源的使用效率。文獻[9]研究了多服務器中資源配置和卸載決策的優化問題，提出一種考慮負載分布的啟發式算法，在提高服務質量的同時，還降低了邊緣計算服務器的能耗和回程流量；但該文獻忽略了多服務器下用戶的競爭性和自私性，影響用戶的卸載體驗。

綜上所述，研究了在超密集移動邊緣計算網絡下，將卸載和資源分配與用戶自私性相結合的方法，主要貢獻如下：

(1) 設計了一種超密集網絡下的移動邊緣計算架構，將系統效用建模為網絡時延和能耗的加權和，聯合計算資源分配和任務卸載為一個NP難優化問題。

(2) 提出了一種多基站博弈卸載算法，采用拉格朗日乘數法求解計算資源分配問題，運用匹配博弈理論協調用戶與邊緣計算服務器之間的相互選擇，依據雙方偏好效用函數得到最佳的卸載策略。

1 系統模型

1.1 網絡模型

(1)

其中，σ2是用戶數據傳輸時的高斯白噪聲，B是所接入小基站的信道帶寬，Pmn是用戶n到小基站m任務數據的傳輸功率，hm，n是無線信道中的信道增益。

圖1 系統模型

1.2 計算模型

(1) 本地計算

(2)

其中，λ1和λ2分別表示時延和能耗的權重參數，0≤(λ1，λ2)≤1。

(2) 邊緣計算

若用戶n選擇通過小基站中連接的邊緣計算服務器執行任務，則其執行的時間由3部分組成：任務數據上傳時間、服務器執行時間以及執行結果的回傳時間。一般情況下，回傳的執行結果遠小于任務上傳的輸入數據，所以忽略任務執行結果的回傳時間和能耗[12]。因此，用戶任務邊緣計算的總執行時間為

(3)

(4)

(5)

根據式(2)～(5)，可得系統的總開銷為

(6)

2 問題描述

基于上述系統模型，將計算卸載和資源分配表述為優化問題，目標是達到系統開銷最小化。顯然，要降低整個系統的開銷成本，需要為用戶找到滿足任務要求的最佳卸載決策以及計算資源分配策略，問題描述如下：

(7)

優化問題式(7)中的卸載決策A是一個二進制變量，計算資源F是一個連續變量，使得式(7)是一個混合整數非線性規劃問題，從而是一個NP難問題[13]。為有效解決大規模設備的系統優化的NP難問題，已有許多研究采用了問題分解的次優化方法。因此，根據式(7)的目標函數和約束條件的結構，可以將式(7)分解為目標和約束分離的兩個子問題[5]。子問題1是在給定卸載下的計算資源分配問題：

(8)

子問題2是在給定計算資源分配下的卸載決策問題：

(9)

多基站博弈卸載算法使用拉格朗日乘數法和匹配博弈論來尋找最優的F和A，通過確定最優的F和A可以尋找式(7)的最優解。

3 多基站博弈卸載算法

該部分提出了多基站博弈卸載選擇算法。該算法首先利用拉格朗日乘數法解決子問題1，然后子問題2先轉化為用戶-服務器匹配問題，根據子問題1得到的計算資源分配解，進一步采用匹配博弈卸載求解。每個用戶都需要得到自己的任務處理結果，并期望該任務處理的開銷盡可能小。由此，對于每個用戶獨立進行任務決策是非常合理的，他們可以根據本地終端的資源以及可利用的網絡資源自行決定任務的處理方式。同理，不同的邊緣計算服務器之間沒有相互耦合，可以獨立地控制與管理其所服務范圍內的用戶。

3.1 計算資源分配

(10)

定理1計算資源分配問題是一個凸函數。

證明：通過求導，可得

(11)

(12)

因此，式(10)為一個凸函數，詳細的證明可以參考文獻[14]。另外，其約束條件C 4和C 5都是線性的，使得式(10)為一個凸優化問題，依據KKT(Karush-Kuhn-Tucker)優化條件，最優解可以通過拉格朗日乘數法求得。對于邊緣計算服務m所服務的用戶n的計算資源分配的最優解為

(13)

在求解子問題1后，需要進一步解決子問題2，才能得到系統開銷最小的解。下面在3.2和3.3節詳細描述該卸載決策問題。

3.2 用戶與服務器匹配

對于子問題2，邊緣計算服務器的選擇很大程度上影響任務的卸載決策，用戶需要比較本地終端與多個服務器的處理開銷，從而確定最佳的卸載策略。為保證所有用戶的卸載公平性，設置了一種卸載決策機制，先假定所有的用戶任務都進行卸載處理，在其選定最優的卸載服務器之后，再與本地終端計算進行比較，從而決定最終的卸載決策。此時，卸載決策問題可以轉化為用戶與服務器的匹配問題：

(14)

在求解用戶與邊緣計算服務器的匹配問題時，常常會選擇就近卸載的方案，考慮到滿足用戶體驗，這可能會造成某些服務器負載較重或者某些因負載較輕而造成空耗現象的發生。如果能在用戶和服務器兩者匹配時進行雙向選擇，則可能達到一個最優的匹配。

匹配博弈論是一種廣泛且強大的方法來有效地模擬兩組成員之間的交互過程；考慮到用戶以及邊緣計算服務器的自私性與合理性，雙方都會根據自身的偏好找到雙方最優的選擇結果，將匹配博弈理論應用到用戶與服務器匹配問題來進行組合問題的分布式求解是非常可行的[15]。在超密集邊緣計算網絡系統中，一個用戶只能選擇一個服務器進行卸載，而一個服務器可以同時接受多個用戶的卸載請求，實現了多對一的匹配方式。為準確描述用戶與邊緣計算服務器之間的匹配關系，定義了一個多對一的匹配對，對于給定的匹配對用戶n∈N以及服務器m∈M滿足以下條件：

(15)

其中，條件①表示用戶n所匹配到的服務器是其所能連接到的服務器集合Mn之一；條件②表示服務器m所匹配的用戶是其所覆蓋范圍內的用戶集合Nm之一；條件③表示用戶n所匹配的服務器最多不能超過一個；條件④表示用戶n與能夠與服務器m建立匹配，那么服務器m同樣也能夠與用戶n建立匹配。

3.3 多基站博弈算法

每一個用戶以及邊緣計算服務器匹配過程中需要考慮關聯要求，匹配關聯算法允許用戶和服務器首先定義自身的偏好效用函數。為了找到穩定的匹配，需要根據偏好效用函數構建自己的偏好列表。

(1) 用戶偏好：在進行多服務器選擇時，用戶在綜合考慮多項偏好因素下，包括用戶與所連接邊緣計算服務器之間的距離、信道增益、噪聲干擾等，會選擇傳輸速率較高的服務器，這不僅減小了數據的傳輸時延，也降低了傳輸的開銷。除此之外，利用子問題1求得的用戶資源分配解，在等待處理結果回傳時，也需要其閑置等待的開銷盡可能少，則用戶的效用函數Φn，P(m)為

(16)

(2) 邊緣計算服務器偏好：服務器挑選卸載用戶時，會盡可能考慮任務數據上傳時間較少的用戶，避免服務器預留給該用戶計算資源的閑置時間過長，從而提高計算資源的利用率。則邊緣計算服務器的效用函數Φm，P(n)為

(17)

多基站博弈卸載算法具體描述如下：

算法1多基站博弈卸載算法。

③ forn=1 to |No| do

⑤ 設置kmn=1發送卸載請求給服務器m

⑥ end for

⑦ form=1 toMdo

⑨ 通過式(17)設置服務器的偏好

4 仿真分析

4.1 仿真參數設置

表1 仿真參數設置

采用Python仿真平臺對所提出的算法進行性能評估。仿真環境是基于EUA數據集設計的，其中包含墨爾本CBD區域內125個邊緣基站以及在內的816個用戶的實際地理位置[16]。為了更進一步模擬真實環境，進行了移動性設置，即每個用戶會在每個時隙中進行位置的隨機更替。仿真默認參數如表1所示。

因開銷定義為用戶任務處理和時延的加權和，所以開銷無量綱。為了驗證算法的優劣性，引入文獻[17]中3種代表性的基準算法進行對比。

(1) 隨機卸載：每個用戶的任務隨機進行本地執行或者部分分割卸載給邊緣計算服務器。

(2) 貪婪通信卸載：每個用戶的任務將會選擇最近的邊緣計算服務器進行卸載，如果一個用戶所挑選的服務器已經分配給其他用戶，那么該用戶將會選擇信道增益次之的服務器。

(3) 貪婪計算卸載：每一個用戶的任務都分割卸載給邊緣計算服務器，盡可能地利用服務器的資源。

4.2 仿真結果分析

圖2顯示了20個邊緣計算服務器，40個用戶場景下4種算法不同時隙用戶的平均開銷，其中單個時隙為3×10-3s。多基站博弈卸載在每個移動的時隙基本能夠穩定在一個較低開銷，相對于貪婪通信卸載，隨機卸載和貪婪計算卸載平均可節省14.50%、20.70%以及28.66%。貪婪計算卸載由于采用全部卸載方式，分配的帶寬被多移動設備所共享，從而造成通信速度大大降低，開銷高于能夠隨機進行本地處理的隨機卸載。貪婪通信卸載雖然也采用全部卸載的方式，但其性能優于隨機卸載和貪婪計算卸載而遜于多基站博弈卸載，是因為在貪婪通信卸載考慮了最佳的信道增益，降低了任務傳輸的開銷，說明通信傳輸對于開銷有較大的影響。

圖3顯示了20個邊緣計算服務器下系統開銷與用戶數量的關系圖。隨著用戶數量的增加，4種算法的曲線都呈上升趨勢，在相同用戶數量下，所提出的多基站博弈卸載的系統開銷最小。在用戶數量較小，如為20時，多基站博弈卸載、貪婪通信卸載、隨機卸載和貪婪計算卸載的開銷相近，多基站博弈卸載開銷節省分別為9.507%，16.220%，20.990%。這是因為此時通信與計算資源充足，相比于本地計算，用戶更傾向于進行任務卸載，使得開銷差異不明顯。當用戶數量增加為40時，多基站博弈卸載開銷節省分別為14.50%、20.70%以及28.66%。這是因為卸載用戶對邊緣計算服務器中有限的通信資源和計算資源相互競爭，用戶平均資源分配低，增加了系統的開銷。尤其是貪婪通信卸載，由于每個服務器只能接收一個用戶任務，通信資源緊缺，使其開銷增長迅速。而多基站博弈卸載依據低開銷的效用函數，充分地利用本地終端資源，減小通信資源的競爭，同時進行計算資源的合理分配，從而保持較小的開銷增長。

圖2 用戶平均開銷與時隙的關系

圖3 系統開銷與用戶數的關系

圖4顯示了系統開銷隨任務輸入數據大小變化的曲線。隨著任務大小的增加，4種算法都呈上升趨勢。當任務輸入數據較小，設置為1 500時，隨機卸載的開銷要小于貪婪通信卸載，分別為0.052 92和0.055 50。這是因為此時本地終端的計算資源有足夠的能力完成任務，而無線傳輸加上邊緣計算開銷較大，貪婪通信卸載和貪婪計算卸載因必須卸載而產生了較大的開銷，而且隨機卸載因兼具本地與卸載兩種任務處理方式，使其一開始開銷低于貪婪通信卸載，多基站博弈卸載盡量通過本地完成任務，從而開銷較低。而隨著任務輸入數據地進一步增大，本地終端的計算資源已難以成功完成任務并且開銷較大，必須將決策方式改為卸載才能減小系統開銷。此時，貪婪計算卸載由于全部卸載特性，開銷始終大于隨機卸載。而優化信道增益的貪婪通信卸載逐漸優于隨機卸載，但貪婪通信卸載因缺乏計算資源的分配，使其開銷始終要高于多基站博弈卸載。

圖5顯示了60個用戶場景下，系統開銷隨邊緣計算服務器數量變化的曲線。服務器數量較小，服務器數量為10時，多基站博弈卸載、貪婪通信卸載、隨機卸載和貪婪計算卸載的開銷相近，分別為0.110 2，0.121 0，0.120 9，0.124 8。這是因為所選服務器的數量有限，卸載可選的方式較少，使得4種算法開銷相差較小。隨著服務器數量的不斷增加，隨機卸載和貪婪計算卸載的開銷呈上升趨勢，這是因為更多的服務器選擇使得存在任務分割機制的隨機卸載和貪婪計算卸載所連接的服務器更多，從而增大了傳輸開銷。而多基站博弈卸載和貪婪通信卸載的開銷呈下降趨勢，這是因為它們能夠從增多的服務器中挑選最佳的服務器機會更大，使得系統開銷不斷減小，但當服務器數量達到80時，多基站博弈卸載和貪婪通信卸載的系統開銷分別收斂為0.059 5和0.074 2，此時意味著當服務器數量達到一定量時，多基站博弈卸載和貪婪通信卸載所選的最優服務器都不會再變化。

圖4 系統開銷與任務輸入大小的關系

圖5 系統開銷與服務器數的關系

圖6 系統開銷與服務器容納數的關系

圖6顯示了20個邊緣計算服務器，100個用戶場景下系統開銷隨服務器容納數變化的曲線。當容納數為1時，無計算資源分配優化，多基站博弈卸載、貪婪通信卸載、隨機卸載和貪婪計算卸載的開銷相近。隨著容納數的進一步增加，貪婪通信卸載由于服務器只能容納一個用戶，使其開銷幾乎不變，穩定在0.199 2。隨機卸載和貪婪通信卸載存在全部卸載機制，由于增加容納數從而對通信與計算資源的競爭加劇，使其開銷不斷增大。多基站博弈卸載存在低開銷的卸載機制與計算資源分配策略，使其在容納數增加的初期降低開銷，但隨著容納數的進一步增加，用戶間的資源競爭使其停止了繼續接收用戶卸載，從而使系統開銷基本保持不變，收斂在0.158 4。

通過對上述仿真結果分析可以看出，相對于其他算法，提出的多基站博弈卸載算法可以有效降低系統開銷成本。這是因為該算法使用了拉格朗日乘數法和匹配博弈的方法對系統進行了優化。性能的增益主要由計算資源分配和自私卸載選擇兩部分得到。首先是計算資源分配，使用拉格朗日乘數法，在任務最大容忍時延之前，為各邊緣計算服務器的計算資源進行合理分配，提高資源的利用效率。其次是自私性選擇，使用匹配博弈的方法，一方面為用戶尋找所偏好的邊緣計算服務器，另一方面也為服務器選擇效益較高的用戶，實現用戶與服務器的最佳雙邊匹配。綜合這兩部分，相對于其他傳統算法，提出的算法通過協調最佳用戶與服務器的配對，同時又進行各服務器計算資源的分配優化，減少了資源的浪費，從而比傳統算法節省系統開銷。

5 結束語

設計了一種超密集網絡下的移動邊緣計算架構，考慮到最小化邊緣計算網絡系統的開銷，將優化問題分解為計算資源分配和卸載決策兩個子問題，并提出一種多基站博弈卸載算法，利用拉格朗日乘數法求解計算資源分配問題，運用匹配博弈理論協調用戶與邊緣計算服務器之間的相互選擇，依據雙發偏好效用求得最佳的卸載策略。仿真結果表明，提出的多基站博弈卸載算法相對于3種基準算法，可有效節省系統開銷。另外，當用戶數量增多或任務輸入尺寸增大時，多基站博弈卸載算法的系統開銷會增大，而當服務器數量增多或服務器容納數增多時，多基站博弈卸載算法的系統開銷會逐漸減小直至收斂。