基于位置預測的多MEC服務器協(xié)同卸載算法

王 翊，盧興俊，許耀華，蔣 芳

(安徽大學計算智能與信號處理教育部重點實驗室，安徽 合肥 230601)

隨著5G技術的快速發(fā)展普及，很多計算密集型的移動應用為用戶提供了優(yōu)質的服務體驗，如人臉／語言識別、高清視頻流、實時在線游戲、虛擬現(xiàn)實等［1］。由于移動終端的計算能力與存儲容量有限，移動用戶在獲得高質量服務的同時，會面臨高能耗的挑戰(zhàn)［2］。移動云計算將計算任務卸載到遠程云緩解終端計算壓力，但數(shù)據(jù)傳輸時間長，在實際運用中無法滿足超高速率的用戶需求。移動邊緣計算（Mobile Edge Computing，MEC）可在移動網(wǎng)邊緣提供服務環(huán)境和計算能力，減少網(wǎng)絡操作和服務交付的時延，提高用戶體驗［3］。MEC服務器的超高計算能力和超低時延，使其成為新一代移動通信的關鍵技術［4］。

在處理計算密集型任務［5］時，MEC主要通過計算卸載和資源分配來有效降低時延和能耗。文獻［6］研究MEC超密集網(wǎng)絡中的任務卸載問題，采用軟件定義網(wǎng)絡的思想，提出一種有效的計算卸載策略，以達到任務處理時延最小的目的。文獻［7］提出了一種聯(lián)合優(yōu)化資源分配和任務卸載分配的策略，保持算法低復雜度并減小了設備能耗。部分學者針對邊緣計算系統(tǒng)時延和能耗兩個方面進行優(yōu)化，設定時延和能耗的相關權重系數(shù)，根據(jù)不同的場景改變權重數(shù)值。文獻［8］研究了多MEC服務器的邊緣計算系統(tǒng)的任務卸載和資源聯(lián)合優(yōu)化問題，考慮了基站重疊覆蓋的情況，通過多服務器卸載策略、上行功率分配策略、資源分配策略的聯(lián)合優(yōu)化，最大化權衡后的綜合效用。上述文獻采用不同算法制定卸載策略對有限的計算資源進行分配，但是忽視了終端設備的移動性對卸載決策的影響。

由于服務器的覆蓋范圍有限，用戶在移動的時候可能會中斷與服務器的連接。原先請求卸載的服務器無法在用戶的下一位置及時發(fā)送計算結果，會引起服務器計算資源的浪費，增加用戶再次上傳卸載計算任務的時延和能耗。因此，對用戶設備的未來位置進行預測顯得尤為重要。文獻［9］通過預測用戶的移動對虛擬機的遷移策略進行優(yōu)化，并提出了基于用戶移動性的服務遷移預測方案，對遷移成本和服務質量采取了折中的辦法。但是對于一些即時性要求較高且任務量較小的應用程序，遷移成本過大。文獻［10］通過長短期記憶方法建立用戶位置預測模型，位置預測的結果更接近真實位置，但是需要復雜的特征數(shù)據(jù)，難以用于普通場景。文獻［11］通過對用戶移動性的預測，在收集任務處理結果時確定終端與邊緣服務器的連接性，從而決定將任務分配到哪一個邊緣服務器。但其用戶運動模型是線性的，沒有考慮用戶移動中存在加速度的情況，為符合實際應用，本文將在研究中考慮存在加速度的場景。

對于用戶的可卸載任務，許多研究都會采取全部卸載到MEC服務器中執(zhí)行的方式［12-13］。但是當用戶數(shù)量較多或卸載任務量較大時，有限的服務器計算資源會導致任務排隊，卸載計算時延增長。文獻［14］給出了部分卸載的辦法，將一部分任務留在移動終端，減少MEC服務器的計算量，并利用KKT條件來解決能耗最小化問題。文獻［15］對能量收集時間、局部計算頻率、卸載時間和功率進行聯(lián)合優(yōu)化，提高計算效率。但是上述研究只將任務卸載到一個MEC服務器，當服務器負載較大或者卸載任務量較大時，計算時延依舊會較大。并且網(wǎng)絡中的MEC服務器負載狀況不同，部分服務器的計算資源可能未被充分利用，為了解決以上問題，文獻［16］利用網(wǎng)絡中多個可用邊緣節(jié)點并行處理卸載任務。本文將卸載任務劃分為多個子任務，并由移動用戶與多個服務器協(xié)同處理。

卡爾曼濾波（Kalman Filter，KF）作為一種對系統(tǒng)狀態(tài)進行估計的算法，具有較低的時間復雜度和空間復雜度，在移動網(wǎng)絡的資源分配與網(wǎng)絡狀態(tài)估計中也有應用［17-19］。但是其僅適用于線性系統(tǒng)，當系統(tǒng)為非線性時，更適用改進后的卡爾曼濾波，即擴展卡爾曼濾波（Extended Kalman Filter，EKF）。 但目前尚未應用于MEC計算卸載的研究中，本文將利用擴展卡爾曼濾波解決進行非線性移動的用戶的計算卸載問題。

根據(jù)密集網(wǎng)絡中小基站數(shù)量眾多的特點，本文的研究場景建立在一個分布式的多MEC服務器系統(tǒng)中，提出了一種基于位置預測的多MEC服務器協(xié)同卸載算法，通過預測移動用戶的未來位置和劃分卸載任務來降低計算卸載的時延和能耗。本文的主要工作有：

（1）首先針對非勻速運動的用戶建立非線性運動模型，再采用擴展卡爾曼濾波的方法預測用戶的未來位置，提高移動用戶與MEC服務器的連接成功率，有效避免用戶跨越MEC服務器覆蓋區(qū)時傳輸中斷。

（2）在用戶位置預測的基礎上，將用戶的卸載任務劃分為多個子任務，交由用戶移動路徑上的MEC服務器協(xié)同處理，任務劃分以最優(yōu)化任務處理時延和能耗加權和為目標。最終的計算結果提前發(fā)送到離用戶預測位置最近的服務器，隨后轉發(fā)給用戶，有效降低時延和能耗。

1 移動用戶的任務協(xié)同卸載模型

1.1 系統(tǒng)模型

在圖1所示的系統(tǒng)模型中，有一個移動用戶和多個無線接入點，每個無線接入點連接一臺MEC服務器。用戶移動性的預測是在服務器或終端本身進行的，將用戶發(fā)送卸載請求的位置作為當前位置，利用當前位置信息與運動狀態(tài)預測的用戶下一位置作為預測位置。用戶在請求位置處向服務器m1所在的無線接入點發(fā)送卸載任務，服務器m1接收到卸載任務后，根據(jù)任務的處理時間和能耗將其劃分為多個子任務，并聯(lián)合附近的服務器對任務進行處理，最后將處理結果通過預測位置處的無線接入點發(fā)送給用戶。根據(jù)用戶的移動路徑，可能會有多個MEC服務器參與到卸載任務的處理與傳輸中。

圖1 系統(tǒng)模型

設移動用戶u移動路徑周圍有N個MEC服務器，構成服務器集M＝｛m1，m2，m3，…，mi，…，mN｝，i∈［1，N］。 用戶需要計算的任務d＝｛c，b｝，c表示任務所需的計算CPU周期數(shù)，b是任務卸載過程中所傳輸?shù)臄?shù)據(jù)量。將任務d劃分為N＋1個子任務，即d＝｛d0，d1，d2，…，dj，…，dN｝，j∈［0，N］，其中第j個子任務dj＝δjd，δj表示任務的劃分比例，即用戶卸載到服務器mi的任務占總任務的比例。

1.2 通信模型

MEC服務器在靠近用戶的網(wǎng)絡邊緣側提供計算服務，分布范圍廣且部署靈活。本文中，每個MEC服務器連接一個無線接入點，卸載任務通過無線回傳鏈路在移動用戶與MEC服務器間、MEC服務器與MEC服務器間傳輸。設部分子任務由本地計算，另一部分則由MEC服務器計算。用戶u到最近服務器m1的上行鏈路傳輸速率是ru，m1，表達式為

式中：B為信道帶寬，pu為用戶的傳輸功率，為用戶到最近服務器m1的信道增益，ω0為噪聲功率。

假設參數(shù)β1代表任務的劃分開銷因子，即劃分任務時產生的額外計算量，β2代表車輛上行鏈路的傳輸開銷因子，用表示子任務dj從移動用戶u到服務器m1的上行鏈路傳輸時間，則

1.3 計算模型

1.3.1 本地計算

用戶在本地計算的部分任務即為d0，本地可以處理的最大計算量為，計算d0所需時間為是移動用戶的穩(wěn)定處理速度（每秒處理的計算量）。d0的計算能耗為， 其中λ0表示移動設備上每CPU周期消耗能量的系數(shù)。

1.3.2 卸載計算

假設用戶的卸載任務從當前位置傳輸?shù)筋A測位置涉及到N個服務器，則用戶卸載的任務可分為N＋1個子任務，由用戶與N個服務器協(xié)同處理?？紤]到MEC服務器的計算資源有限，劃分到MEC服務器的子任務不超過服務器可以處理的最大計算量。根據(jù)每個子任務各自處理的時延和能耗，選取一個使任務的整體能耗和時延加權和最小的劃分比例。子任務dj選擇在服務器mi執(zhí)行，服務器可以處理的最大計算量為則計算子任務dj消耗的時間為，其中fm是服務器的穩(wěn)定處理速度。

2 基于位置預測的協(xié)同卸載算法

2.1 基于擴展卡爾曼濾波的位置預測方法

考慮用戶進行非線性運動，k時刻的真實狀態(tài)向量可以表示為sk＝［lx，vx，ax，ly，vy，ay］T， 其中l(wèi)x、vx、ax表示二維平面中橫坐標方向上的位置、速度、加速度，ly、vy、ay表示二維平面中縱坐標方向上的位置、速度、加速度。

經過時間Δt后，用戶移動到新的位置，用戶的運動狀態(tài)可以通過以下運動方程得到

式中，v＝v0＋a·Δt。

在系統(tǒng)的狀態(tài)空間中，狀態(tài)變量每時每刻都在變化，可以由狀態(tài)轉移方程表示為

式中：sk-1表示k-1時刻的真實狀態(tài)向量；f（·）為非線性系統(tǒng)中的狀態(tài)轉移函數(shù)；qk是狀態(tài)噪聲，假定均值為0，協(xié)方差矩陣為Qk＝cov（qk），服從正態(tài)分布，即：qk～N（0，Qk）。

系統(tǒng)中狀態(tài)測量方程是將隱含的真實狀態(tài)空間映射到測量空間，表示為

式中：zk為測量向量，是狀態(tài)向量的映射；h（·）為測量函數(shù)；rk為狀態(tài)噪聲，假定均值為0，協(xié)方差矩陣為Rk＝cov（rk），服從正態(tài)分布，即：rk～N（0，Rk）。

假設在每一時隙中，用戶的運動狀態(tài)與前一狀態(tài)保持一致，僅在下一狀態(tài)發(fā)生改變。采用擴展卡爾曼濾波方法，根據(jù)移動用戶當前時刻的狀態(tài)值（速度、加速度），通過預測和測量反饋兩個步驟，實現(xiàn)對用戶未來時刻位置的預測。

（1）線性化系統(tǒng)：利用泰勒級數(shù)將非線性方程展開，略去高階項，轉換成線性系統(tǒng)。

（2）濾波過程：進行擴展卡爾曼濾波中的預測和測量反饋。如圖2所示，系統(tǒng)初始化后，首先在預測階段，通過k-1時刻的狀態(tài)值計算k時刻的預測值以及預測值和真實值的誤差協(xié)方差Pk｜k-1；在測量反饋階段，先計算卡爾曼增益Kk，并根據(jù)測量值修正此時的狀態(tài)值得到，然后計算估計值與真實值之間的誤差協(xié)方差Pk用于下一次遞推，直到狀態(tài)值為最優(yōu)估計值。

圖2 位置預測方法的擴展卡爾曼濾波流程圖

2.2 協(xié)同卸載效用函數(shù)及優(yōu)化方法

根據(jù)第1節(jié)中對系統(tǒng)模型的描述，當用戶移動到某服務器的覆蓋區(qū)域時，可以與該服務器建立無線連接，并將需要卸載的任務傳輸?shù)椒掌魃稀Ｐ遁d延遲包括4個部分：上行鏈路通信延遲、回程鏈路延遲、下行鏈路通信延遲和任務處理延遲。由于回程鏈路延遲遠小于上行鏈路，且下行鏈路傳輸?shù)臄?shù)據(jù)量遠小于上行鏈路，所以在分析的時候忽略了這兩種延遲，只考慮上行鏈路通信延遲和任務處理延遲。當計算任務和任務處理結果在服務器間傳輸時，由于任務處理結果數(shù)據(jù)量遠小于計算任務的數(shù)據(jù)量，所以只考慮上行鏈路通信延遲。此外，由于本研究是從用戶的角度考慮能耗和時延，故服務器的計算能耗不包括在內。

根據(jù)實際應用分析，優(yōu)化目標相當于在限制條件的約束下最小化式（14）給出的效用函數(shù)φ（δ），由移動用戶做出關于計算任務劃分比例的決策。該問題可以表述為

對于?i∈［1，N］，C2表示計算密集型任務劃分成子任務的比例，C3表示由移動終端處理的子任務計算量不超過移動終端可處理的最大量，C4表示卸載到MEC服務器的子任務計算量不超過服務器可處理的最大量。

在本文的優(yōu)化模型中，自變量δ的約束條件為線性等式和線性不等式，系統(tǒng)效用模型為有約束的線性優(yōu)化問題?？紤]到單純形法對變量和約束數(shù)量不多的線性規(guī)劃問題有較好性能，因此將成為前述問題的優(yōu)化求解算法。求解可分為以下3步：（1）求一個初始基本可行解；（2）檢查該基本可行解是否為最優(yōu)解；（3）若是最優(yōu)解，則為線性優(yōu)化問題的解，若不是最優(yōu)解，則設法再求一個不同的基本可行解，并重復步驟1、2。

首先，為將線性規(guī)劃問題化為標準型，引入松弛變量 δ′0、δ′j、δ″j， 將約束 C3、C4、C5改寫為

其中，CY為非基本變量系數(shù)，CB為基本變量系數(shù)，B為基，Y為非基向量組。如果所有檢驗數(shù)大于0，則為最優(yōu)解，否則需要另求一個不同的基本可行解。

為求得一個不同的基本可行解，需要選擇一個在目標函數(shù)里系數(shù)為負的非基本變量δe（入基變量），將δe用基本變量δl（替出變量）表示，然后把δe變?yōu)榛咀兞?，δl變?yōu)榉腔咀兞?。替入變量對應的檢驗數(shù)是所有檢驗數(shù)中最小的。

把已確定的入基變量在各約束方程中的數(shù)除其所在約束方程中的常數(shù)項，把最小比值所在的約束方程中的原基變量確定為替出變量。假設該比值為θ，則有

換基后，重復以上步驟，直到當前各非基變量的檢驗數(shù)大于0，找到最優(yōu)解。通過以上的單純形法對式（15）進行優(yōu)化，得到的結果在下一節(jié)進行仿真分析。

3 仿真結果與分析

3.1 參數(shù)設置

本節(jié)將利用仿真對基于位置預測的多MEC服務器協(xié)同卸載算法進行性能評估。MEC廣泛分布于網(wǎng)絡邊緣，為了便于研究，仿真場景選取了一個半徑為200 m的小區(qū)，小區(qū)中設置了多個服務器，分布在不同位置，彼此通過無線回傳鏈路通信。若用戶移動進入新的小區(qū)，則會重新啟動新小區(qū)的協(xié)同卸載算法。仿真參數(shù)如表1所示。

表1 仿真參數(shù)表

3.2 仿真分析

3.2.1 效用函數(shù)性能仿真分析

仿真中考慮了兩個對比算法：對比算法1［20］是無預測的任務劃分算法，不考慮用戶的移動，假設有兩個MEC服務器參與到計算中；對比算法2［21］是無預測的任務卸載算法，綜合考慮任務處理的時延和能耗，選擇在本地處理計算任務或者選擇一個最優(yōu)服務器進行卸載。

圖3表示了任務數(shù)據(jù)量對效用函數(shù)的影響，設定用戶移動初始速度為60 km／h，加速度為2 m／s2，小區(qū)內服務器數(shù)量為20個。從圖中可以看出，隨著任務數(shù)據(jù)量的增加，3種算法的效用值都在增加。其中，數(shù)據(jù)量在0到6×108bit時，3種算法效用值都保持穩(wěn)定增加。對比算法1在數(shù)據(jù)量達到6×108bit后明顯增加，而本文所提出的方法一直保持穩(wěn)定較低的效用值，比對比算法1的效用值低15.29%。這是因為考慮到用戶移動后，參與計算的服務器數(shù)量隨用戶移動距離的增大而變多。相較于對比算法2，本文算法的效用值平均低33.10%左右，這是因為本文算法將計算任務優(yōu)先分配給離請求位置較近的若干服務器，減小了計算任務的排隊時間，因此有較低的效用值。

圖3 任務數(shù)據(jù)量對效用函數(shù)的影響

圖4表示了MEC服務器計算資源容量對效用值的影響，設定用戶移動的初始速度為60 km／h，加速度為2 m／s2，任務量為 5×108bit，小區(qū)內 MEC 服務器數(shù)量為20個。從圖中可以看出，隨著服務器計算資源容量的增加，3種算法的效用值都在減小，且本文算法的效用值一直最低。相較于對比算法1，本文由多個服務器協(xié)同卸載，減小了計算任務的傳輸和計算時延；而對比算法2只選擇一個MEC服務器處理卸載任務，當服務器計算資源容量有限時，任務排隊等待的時間會較長。由此得出，在計算資源受限時，本文算法通過靈活選擇多個MEC服務器處理計算任務，有效降低了任務處理的時延和能耗，相較于其他兩種算法優(yōu)勢較為明顯。

圖4 MEC服務器計算資源容量對效用函數(shù)的影響

3.2.2 位置預測成功率仿真分析

為體現(xiàn)位置預測成功率的性能，本小節(jié)將文獻［13］提出的算法作為連接對比算法1，該算法使用了勻速運動模型，采用卡爾曼濾波方法預測用戶的位置，但是沒有考慮實際情況中用戶運動加速度對預測結果的影響；連接對比算法2是無預測的卸載算法，只在用戶請求卸載的位置選擇最近的服務器卸載。

圖5展示了在服務器數(shù)量為20個、加速度為2 m／s2時，用戶初始速度對連接成功率的影響。隨著速度的增加，用戶移動的距離變長，但服務器的覆蓋范圍有限，因此連接的成功率會降低。本文算法與連接對比算法的連接成功率也隨速度的增加而拉大差距。在初始速度為10 km／h時，本文算法連接成功率相較于對比算法1和對比算法2差距并不明顯，當初始速度提高到100 km／h時，本文算法連接成功率相較于對比算法1和對比算法2分別提高13.06%和35.03%。這是因為連接對比算法1在預測時沒有考慮到加速度對位置預測的影響，選擇的服務器與用戶真實位置較遠。本文算法選擇的服務器離用戶真實位置較近，連接成功率更高；連接對比算法2選擇的服務器是相對于請求服務位置最近的，用戶移動后，連接成功率大大降低。

圖5 用戶初始速度對連接成功率的影響

圖6表示了用戶移動初始速度為60 km／h，加速度為2 m／s2時，連接成功率隨服務器數(shù)量的增加而增加。當MEC服務器數(shù)量為5個時，本文算法連接成功率為48.41%，隨著服務器數(shù)量的增加，本文算法連接成功率不斷提高，當MEC服務器數(shù)量為25個時，本文算法連接成功率達到72.5%。這是因為服務器的數(shù)量增加使服務器分布更加密集，用戶與服務器之間的距離變短，可選擇的服務器數(shù)量增加。本文算法可以選擇的卸載服務器數(shù)量較多，連接成功率相較于連接對比算法更高。

圖6 服務器數(shù)量對連接成功率的影響

4 結束語

在MEC網(wǎng)絡中服務器的計算資源受限的情況下，本文針對用戶移動性帶來的卸載任務傳輸延遲和能耗較大的問題，通過位置預測與任務劃分相結合的方法降低了任務卸載的時延和能耗。將移動用戶和服務器的總時延和總能耗作為優(yōu)化目標，給出效用函數(shù)模型，提出一種基于位置預測的多MEC服務器協(xié)同卸載算法，將擴展卡爾曼濾波和單純形法相結合對效用函數(shù)進行優(yōu)化。仿真結果表明，本文算法相較于兩種對比算法有更低的時延和能耗，且連接成功率更高。未來的研究中，將考慮小區(qū)中有多個移動用戶競爭計算資源，對用戶卸載的時延和能耗進行更好的優(yōu)化。