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

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

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

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

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

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

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

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

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

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

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

1.1 系統(tǒng)模型

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

圖1 系統(tǒng)模型

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

1.2 通信模型

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

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

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

1.3 計算模型

1.3.1 本地計算

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

1.3.2 卸載計算

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

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

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

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

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

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

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

式中：sk-1表示k-1時刻的真實狀態(tài)向量；f（·）為非線性系統(tǒng)中的狀態(tài)轉(zhuǎn)移函數(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）。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 仿真結(jié)果與分析

3.1 參數(shù)設(shè)置

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

表1 仿真參數(shù)表

3.2 仿真分析

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

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

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

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

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

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

3.2.2 位置預(yù)測成功率仿真分析

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

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

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

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

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

4 結(jié)束語

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