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

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

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

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

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

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

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

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

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

1 系統(tǒng)模型

1.1 網絡模型

(1)

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

圖1 系統(tǒng)模型

1.2 計算模型

(1) 本地計算

(2)

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

(2) 邊緣計算

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

(3)

(4)

(5)

根據(jù)式(2)～(5)，可得系統(tǒng)的總開銷為

(6)

2 問題描述

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

(7)

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

(8)

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

(9)

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

3 多基站博弈卸載算法

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

3.1 計算資源分配

(10)

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

證明：通過求導，可得

(11)

(12)

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

(13)

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

3.2 用戶與服務器匹配

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

(14)

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

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

(15)

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

3.3 多基站博弈算法

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

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

(16)

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

(17)

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

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

③ forn=1 to |No| do

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

⑥ end for

⑦ form=1 toMdo

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

4 仿真分析

4.1 仿真參數(shù)設置

表1 仿真參數(shù)設置

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

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

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

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

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

4.2 仿真結果分析

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

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

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

圖3 系統(tǒng)開銷與用戶數(shù)的關系

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

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

圖4 系統(tǒng)開銷與任務輸入大小的關系

圖5 系統(tǒng)開銷與服務器數(shù)的關系

圖6 系統(tǒng)開銷與服務器容納數(shù)的關系

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

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

5 結束語

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