移動性感知的邊緣服務遷移策略

吳大鵬，呂吉，李職杜，王汝言

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

1 引言

隨著移動互聯網的不斷發展，虛擬現實、智能家居等資源密集型應用在人們的生產和生活中發揮著越來越重要的作用[1-2]。這些應用通常具有超低時延和海量數據處理等需求，給儲能、計算及緩存能力有限的移動設備帶來了極大的挑戰。移動邊緣計算網絡把移動邊緣計算（MEC,mobile edge computing）與移動云計算（MCC,mobile cloud computing）的各自優勢相結合，為這些應用需求提供了新的解決思路[3-4]。然而，如何為移動中的設備（如車輛、軌道交通等）提供連續不間斷的服務是制約移動邊緣計算網絡進一步提高用戶服務質量的瓶頸之一。

在移動邊緣計算網絡中，由于用戶的移動性、服務請求的多樣性及區域請求量的差異性，容易造成邊緣服務器負載不平衡、熱點地區網絡擁塞等問題，從而嚴重降低用戶的服務質量。雖然邊緣服務遷移技術能夠保證為用戶提供連續化服務，而且還能平衡邊緣服務器之間的工作負擔，但受限于移動邊緣計算網絡的通信能力、計算資源及存儲容量，如何根據用戶的實時位置信息快速、高效地進行邊緣服務遷移，成為移動邊緣計算網絡動態服務遷移中待解決的關鍵問題之一。

本文從實際情況出發，提出了一種移動性感知的邊緣服務遷移策略，考慮到用戶的運動軌跡具有部分可預測性及服務請求類別的多樣性，對用戶的服務遷移決策與移動邊緣計算網絡的通信-計算-存儲資源進行了聯合優化。本文主要貢獻如下。

1)通過Lyapunov 優化理論有效地將長期遷移成本預算轉換為實時優化，在不需要任何用戶位置先驗信息的條件下，根據用戶的實時位置信息進行快速、高效的在線服務遷移，克服了由于用戶運動軌跡的隨機性而導致的無法建立馬爾可夫狀態轉移模型的問題。

2)從服務提供商的角度出發，考慮到用戶服務的頻繁遷移會造成系統長期遷移成本超出遷移閾值，運用Lyapunov 優化方法在保證系統長期遷移成本穩定的基礎上，最小化用戶服務請求的平均感知時延。

3)為降低混合整數非線性規劃問題的求解復雜度，設計了一種以用戶為中心的異步最佳響應方案來尋找近似最優的邊緣服務遷移策略，在顯著降低算法運行時間的同時，進一步降低了用戶服務請求的平均感知時延。

2 相關工作

針對移動邊緣計算網絡中動態服務遷移問題，國內外學者均開展了相關的研究。文獻[5]根據用戶的地理位置及其服務請求類型，考慮服務運行過程中表現出非對稱帶寬的需求，提出了一種滿足多維（存儲、計算與通信）約束的聯合優化算法，有效解決了多維約束條件下MEC 增強的多蜂窩網絡中的服務放置和請求路由問題。文獻[6]考慮到邊緣服務器的異構性問題，以最大化服務放置獎勵為優化目標，提出了一種靈活的服務放置算法。該算法將每個邊緣節點看作某一類應用服務器，在每個時隙進行服務放置決策。上述2 種算法無法為正在移動的用戶提供無間斷服務，嚴重降低了用戶服務質量。文獻[7]通過構造多參數馬爾可夫決策過程（MDP,Markov decision process）收益函數解決了由于邊緣服務器服務范圍有限而造成對移動車輛服務中斷的問題，改進了單純基于距離進行服務遷移方案的不足，但在遷移決策中沒有對服務提供方的成本開銷進行合理地建模與評估。在用戶接入節點固定的非重疊覆蓋場景下，Ouyang 等[8]考慮到用戶的移動性與服務請求到達的不確定性問題，提出了具有概率分布模型的馬爾可夫近似算法，通過構建不可約馬爾可夫鏈得到了不同時間段的最優服務遷移策略。但對于多節點覆蓋場景，該算法無法做出用戶服務請求的節點選擇決策。文獻[9]提出了云-邊-端三層架構模型，在該模型中，每個基站覆蓋下的用戶首先向本地MEC 服務器請求服務，當本地MEC 服務器沒有響應用戶的服務需求時，該請求可通過基站路由到遠端云服務器。然而，該方法將導致邊緣服務器負載不均衡，部分用戶服務質量嚴重下降等問題，此外，該方案忽略了用戶的移動性。文獻[10]提出了一種基于邊緣認知計算（ECC,edge cognitive computing）的動態服務遷移機制，該機制可以根據用戶的行為認知快速地進行服務遷移，解決了用戶在不同行為下服務質量大幅度波動的問題。但該機制以滿足用戶個性化服務為目標，忽視了多用戶場景中邊緣服務器資源有限的情況。文獻[11]結合遠程加載與重定向技術提出了基于虛擬機的快速服務遷移方法（FSMM,fast service migration method），該方法基于最短距離為用戶實現用戶服務遷移，具體地，在邊緣服務器覆蓋范圍內的用戶均就近接受服務，不在任何邊緣服務器覆蓋范圍內的用戶均由遠端云服務器提供服務。文獻[12]從理論的角度來量化間歇性連接對移動邊緣計算的影響，所提間歇性服務遷移方法（ISMM,intermittent service migration method）根據當前網絡環境自適應調整用戶服務遷移響應間隔，有效降低了用戶的平均感知時延。文獻[13]將服務遷移問題描述為馬爾可夫決策過程，通過用戶與服務位置之間的相對距離來獲取近似的底層狀態空間，然而，該決策模型僅適用于一維服務遷移場景。

綜上所述，已有的相關研究主要從3 個方面實現用戶的服務遷移。1)假設用戶移動路徑已知的情況下，對系統資源與服務遷移策略進行聯合優化，使系統某一性能（如用戶感知時延、系統吞吐量等）達到最優。2)在服務遷移決策過程中，忽略服務遷移所產生的成本開銷與用戶被多個微基站重疊覆蓋的情況，以提高用戶服務質量為優化目標。3)假設邊緣服務器擁有充足的計算與存儲資源，把用戶的移動性建模為一維或二維馬爾可夫狀態轉移模型，根據用戶在每個時刻所處的環境狀態進行邊緣服務遷移決策。然而，在實際應用場景中，用戶的地理位置具有部分可預測性，對于運動軌跡無法預測的用戶，其移動性無法通過馬爾可夫狀態轉移模型進行刻畫。其次，已有研究沒有從服務提供商的角度考慮如何在保證用戶服務質量的前提下，使邊緣服務遷移成本開銷保持長期穩定。最后，由于移動邊緣計算網絡的通信資源、計算能力以及存儲容量是有限的，忽略對這類資源的合理調度將導致網絡無法應對數量呈爆發式增長且服務質量需求日益增高的各類應用請求。

3 系統模型

本文的系統模型如圖1 所示，在宏基站（MBS,macro base station）覆蓋范圍內存在多個小基站（SBS,small base station），其中MEC 增強的SBS 又稱為邊緣節點（EP,edge point）。考慮到每個小基站覆蓋范圍內服務請求量的差異性，為節約部署成本，服務請求量相對較小的地區不需要部署邊緣服務器，但對于熱點區域情況則相反。實際上，非熱點區域的服務請求可以通過小基站轉發至宏基站，并由宏基站轉發到遠端云服務器或者周邊的邊緣服務器。例如：小基站SBS1沒有部署邊緣服務器，所以用戶user1只能通過宏基站向云服務器或者鄰近的邊緣服務器請求服務。對于沒有被小基站覆蓋的用戶，其服務請求只能通過宏基站轉發到云服務器或者邊緣服務器。由于用戶的移動性或新用戶的加入使網絡的拓撲結構發生變化，導致用戶的服務進程從原來的服務器遷移到另一個服務器。開始時刻，小基站SBS2為用戶user2提供服務。一段時間后，用戶user2移動到小基站SBS3所覆蓋的區域。由于邊緣服務器存儲資源、計算資源以及通信資源有限，在每個邊緣服務器上僅能運行有限的應用服務，小基站SBS3沒有可供用戶user2服務需求使用的資源，因此用戶user2在小基站SBS2的服務配置文件只能通過宏基站遷移到鄰近的邊緣服務器SBS4，從而實現邊緣服務遷移。

在宏基站覆蓋范圍內部署M個SBS 與I個邊緣服務器，用戶數量為N+1。令T={0,1,2,…,T}表示時間離散化序列集合，表示用戶k在時隙t內關于BSj（j=0 時為MBS，j≠0 時為SBS）的接入參數，用戶k接入BSj，則，否則。通常情況下，用戶k只能接入到一個BS。因此，對任意的用戶k來說，其接入約束條件如式(1)所示。

由于邊緣服務器處理任務的輸出結果遠小于任務大小[14-17]，本文只考慮上行信道資源分配。假設系統的通信資源塊（RB,resource block）總數為F，每個通信資源塊的帶寬為WMHz，宏基站的資源塊總數為C0，剩余的F-C0通信資源塊由SBS復用。由于不同SBS 所管理的無線資源存在差異性，所以對于任意的SBSj，其占用的無線資源塊數應滿足Cj≤F-C0，1≤j≤M。因此，對任意的BSj，為保證用戶所占用的通信資源在其承受范圍內，其通信資源約束條件需滿足

圖1 系統模型

由于服務器計算與存儲能力有限，對于任意的時隙t，服務器i服務用戶所需的計算與存儲不能超過其總的計算與存儲資源，因此服務器i的計算資源約束條件如式(3)所示，存儲資源約束條件如式(4)所示。

其中，φi和Bi分別表示服務器i的總計算資源與總存儲資源；分別表示用戶k請求服務s所需要的計算資源與存儲資源；S+1 表示所有用戶服務請求服務類別的總和；表示用戶k被服務器i所托管，i=0 時表示云服務器，否則表示邊緣服務器。

3.1 服務體驗模型

由于用戶發起的服務請求被邊緣服務器或者云服務器響應，因此用戶的數據傳輸存在一定的傳輸時延。在本文模型中，傳輸時延可分為以下三類：1)用戶的服務請求被本地邊緣服務器響應；2)用戶的服務請求通過MBS 轉發到鄰近的邊緣服務器；3)沒有邊緣服務器響應用戶的服務請求時，該請求只能被遠端云服務器響應。因此，系統中所有用戶發送服務請求到BS 的傳輸時延Dc(t)為

MBS 轉發服務請求到SBS 或者云服務器的傳輸時延Df(t)為

所有用戶的服務請求被服務器響應的總時延Dtotal(t)為

3.2 系統性能與成本

首先，為緩解數據上傳到遠端云服務器對核心網造成的流量擁塞問題，部署在邊緣服務器上的服務應最大化滿足用戶的需求。其次，為降低網絡拓撲結構變化所帶來的服務遷移成本，系統中所有用戶在時隙t內的服務遷移成本E(t)應保持在預期的范圍之內，令Eavg表示長期預算遷移成本，可得成本約束條件如式(10)所示。

在保證系統長期平均遷移成本小于預算成本的約束條件下，根據用戶服務請求制定最優的服務遷移策略，使所有用戶的平均感知時延與服務遷移時延之和最小，可得如下優化問題。

4 基于Lyapunov 優化的在線服務遷移

用戶的移動容易造成用戶服務在服務器之間頻繁遷移，為服務提供商帶來高昂的遷移費用。從服務提供商角度考慮，如何在保證服務遷移成本不超出其所能承受閾值的基礎上，最大化降低用戶所需服務的感知時延是動態服務遷移策略必須滿足的關鍵目標之一。為實現該目標，本文運用Lyapunov 優化方法保證系統的長期遷移成本小于遷移閾值的同時，滿足用戶對感知時延的要求。Lyapunov 優化的關鍵思想是在當前用戶的感知時延和遷移成本之間取得相對的平衡，通過為長期成本預算引入虛擬隊列來保持遷移成本的長期穩定。首先將虛擬隊列定義為超出預算成本的歷史度量，假設初始隊列長度為0 bit（即Q(0)=0 bit），隊列更新方式如式(11)所示。

直觀上，Q(t)可以作為當前服務遷移成本狀況的評價標準。Q(t)越大，表示自實施在線服務遷移策略開始，遷移成本超過長期預算遷移成本Eavg越多。為了保證長期遷移成本低于Eavg，Q(t)必須滿足，其中 E[?]表示數學期望。

由于Q(0)=0，可進一步得到

式(13)表明了長期遷移成本不能超過預算成本。為了保持虛擬隊列穩定，首先分別定義二次Lyapunov 函數與Lyapunov 漂移函數[18-20]如式(14)與式(15)所示。

其中，Δ(Q(t))表示在二次Lyapunov 函數中，相鄰時隙間遷移成本的變化量，該變化量有助于調整服務遷移策略以適應系統的動態變化。

為了得到當前時隙下最優的服務遷移策略，可通過Lyapunov 優化方法把原始問題分解為實時性優化問題。為保持系虛擬隊列穩定，通過定義Lyapunov漂移加懲罰函數構建實時服務遷移問題，其中Lyapunov 漂移加懲罰函數如式(16)所示。

進一步可以得到

其證明如下。

運用Lyapunov 優化將問題P1轉化為用戶接入節點選擇與服務遷移決策的問題P2。對于問題P2 的求解，可使用窮舉法列舉所有可能的服務遷移策略，然后基于拉格朗日乘子法或者內點法求出當前服務遷移策略下的最優通信資源分配λ(t)。然而，窮舉法算法復雜度為O(FNM)，復雜度過高，無法應用于大型移動邊緣計算網絡。觀察問題P2 可知，其優化目標的第一項與用戶無線接入節點選擇Y(t)和通信資源分配λ(t)相關，第二項表示MBS 轉發所有用戶的服務請求到邊緣服務器或云服務器所需的總時延。

5 自適應最佳響應策略

5.1 快速邊緣決策算法

本文求解問題P2 的總體思路如下。首先，假設在t時隙內，用戶最優的無線接入節點選擇參數為Y*(t)。其次，將問題P2 分解為2 個子問題：通信資源分配問題與邊緣節點選擇問題。分別求解在已知無線接入策略Y*(t)的情況下最優的λ*(t)和X*(t)。最后，將λ*(t)與X*(t)代入問題P2，求解出最優的Y*(t)。具體地，通信資源分配問題P2_1表述如下。

運用拉格朗日乘子法消去約束條件(2)，得到如下優化算子。

進一步聯立式(19)和式(20)，可得

通過式(21)可以求得所有用戶的最佳通信資源分配策略λ*(t)。

同理可得，在已知全局最優的無線接入節點選擇策略Y*(t)后，服務遷移問題P2_2 表述如下。

化簡問題P2_2，可得

其中，符號.*表示矩陣點乘，符號sum(?)表示對矩陣所有元素求和。為減少計算復雜度，本文提出快速邊緣決策算法求解最優服務遷移決策參數X(t)，如算法1 所示。

算法1快速邊緣決策算法

輸入初始化矩陣X(t)=0

輸出最優服務遷移策略X*(t)

通過式(21)及算法1 求解X*(t)并化簡問題P2，使優化目標只包含決策參數Y*(t)。由于化簡后的問題仍是整數非線性規劃問題。為在計算復雜度與用戶的服務質量之間取得折中，本文進一步提出異步最佳響應算法，以用戶為中心，可以為用戶快速地選擇無線接入節點。

5.2 異步最佳響應更新策略

令U(Y(t))表示問題P2 的效用函數，用y-k={y0,…,yk-1,…,yN}表示除用戶k之外，所有用戶的邊緣節點選擇向量。在已知其他用戶的邊緣節點選擇策略情況下，用戶k通過選取某一個覆蓋該用戶的SBS 或者MBS 作為無線接入節點，使U(Y(t))最小化，如式(22)所示。

由于上述問題為非合作性的無線接入節點選擇問題，存在一個基于博弈論的無線接入策略，使所有用戶的接入節點選擇達到納什均衡。因此，當任何用戶都無法通過單方面更新其無線接入策略來進一步降低其成本時，所選擇的無線接入策略為最優Y*，即對于任意的用戶m來說，都有式(23)所示的不等式成立。

本文根據式(22)與式(23)提出了異步最佳響應算法，其主要流程如下。用戶將服務請求發送到初始連接的BS 后，MBS 為其服務請求分配一個唯一編號ID；然后根據分配的ID 順序更新所有用戶的邊緣節點選擇策略，具體地，對當前還沒有更新的最小ID 的用戶的服務請求分配一個更好的邊緣服務器或云服務器。因此，任意用戶k的無線接入節點選擇更新流程如式(24)所示。

其中，r表示策略更新輪數。在已知當前所有用戶的接入策略情況下，比用戶k的ID 小的用戶根據不等式(24)進行更新，比用戶k的ID 大的用戶接入策略保持不變。異步最佳響應算法如算法2所示。

算法2異步最佳響應算法

輸入初始化,隨機為每一個用戶服務請求分配一個接入節點，并設置初始迭代輪數r=0

輸出Y*

由于用戶的隨機移動，使用戶在每一個時隙之間的地理位置可能不同。通過快速邊緣決策算法及異步最佳響應算法求解出每個時隙t的最優的邊緣節點與無線接入選擇策略，然后不斷更新每個時隙的虛擬隊列長度，最后得到系統長期服務遷移決策。其流程如算法3 所示。

算法3自適應最佳響應算法（AORAM,adaptive optimal response algorithm）

輸入初始化虛擬系統成本隊列Q(0)=0

6 數值分析

本文采用Python IDE PyCharm 作為實驗的仿真軟件，版本為 PyCharm Community Edition 2019.2.5。為縮短仿真時間，使用戴爾易安信PowerEdge R730 機架式服務器（Xeon E5-2603 V3/8 GB/1.2 TB）搭建仿真平臺。仿真場景設置如下：在900 m ×900 m區域內部署4 個SBS 和一個MBS，初始用戶數M=50。本文采用3 種對比算法，分別為當前最優服務器遷移（COSM,current optimal server migration）、ISMM[12]與FSMM[11]。COSM為一個基準算法，為防止用戶頻繁進行邊緣節點選擇，在每個時隙開始階段，只對位置發生變化的用戶進行邊緣節點選擇，其他用戶接入參數保持不變。ISMM 中，每隔一段時間τ0（實驗設置為4 s），BS 根據當前時刻T1的用戶位置信息進行服務遷移，并在下一個時間段T1-(T1+τ0)內不進行任何服務遷移[12]。FSMM 基本思想為每個邊緣服務器只服務其覆蓋范圍內的用戶，無邊緣服務器覆蓋的用戶均由遠端云服務器提供服務[11]。

考慮到現實情況中，用戶的運動軌跡可以分為確定性運動軌跡與非確定性運動軌跡，例如，用戶每天的上下班路徑及其所處地理位置可以根據大量的歷史數據預測出來，而用戶出差或者旅游的運動路徑由于數據稀疏性難于預測。本文把用戶的運動分為沿著確定軌跡運動與每個時隙的地理位置隨機2 種情況。具體仿真參數設置如表1 所示。

6.1 確定性用戶軌跡仿真模型

確定性用戶軌跡模型如圖2 所示，其中，用戶user1與user2分別沿著2 個確定的路徑軌道運動，其他用戶的地理位置保持不變。用戶user1與user2完成固定軌跡運動的時間均為T=800 s，在每一個時隙τ=1 s 內運動長度在x軸上的分量為1.125 m，其他用戶的坐標位置在t=0 時刻隨機分布。

表1 仿真參數

圖2 確定性用戶軌跡模型

圖3 用戶的平均感知時延

圖3 表示系統用戶的平均感知時延。可以看出，本文所提AORAM（即算法3）得到的用戶感知時延低于其他3 種對比算法。與AORAM 相比，其他算法均存在用戶數量閾值M0，當用戶數量M＜M0時，對比算法與所提算法在降低用戶感知時延性能方面表現大致相同；但當M≥M0時，隨著用戶數的增加，AORAM 與對比算法的時延性能差異也隨之增大，即所提算法明顯優于對比算法。造成上述現象的主要原因在于：當用戶數量相對較小時，本地邊緣服務器的計算、存儲與通信資源充足，能夠最快地響應本地用戶的服務請求，而當用戶數大于某一個閾值時，容易造成某些邊緣服務器負載過高，而某些邊緣服務器則相反。AORAM 通過轉發負載過重的邊緣服務器的用戶服務到空閑且離用戶相對較近的邊緣服務器，實現邊緣服務器之間的負載均衡，從而降低用戶的平均感知時延。此外，分別統計不同用戶數量情況下，所提AORAM相對于其他算法的性能增益，并計算平均值。從圖3(a)中可以看出，與ISMM 相比，AORAM 能夠使用戶的平均感知時延降低8.746%，當用戶數M≤38時，2 種算法最大差值為36.59 ms，即2 種算法在用戶服務質量性能方面表現大致相同，但用戶數M＞ 38時，時延差值隨著用戶數的增加而不斷增大。同理可知，在圖3(b)中，與COSM 相比，AORAM 能夠使用戶的平均感知時延降低11.57%，當用戶數M≤20時，2 種算法時延差值百分比為10.53%，最大差值為24.68 ms。在圖3(c)中，與FSMM 相比，AORAM 能夠使用戶的平均感知時延降低21.59%，當用戶數M≤12時，2 種算法最大差值為40.70 ms。從圖3(d)中可以看出，與其他算法相比，所提AORAM 的用戶平均感知時延分別降低了8.74%、11.57%、21.59%。顯然，AORAM 能有效地降低感知時延，提高用戶服務質量。

圖4 為4 種算法在不同懲罰因子V情況下虛擬隊列長度Q(t)隨時間的變化曲線。圖 4(a)為AORAM 在不同懲罰因子V下，虛擬隊列長度Q(t)的變化情況，可以看出，隨著時間推移，虛擬隊列長度Q(t)趨于某一個固定值（如當V=500時，虛擬隊列長度Q(t)的穩定值為127）。此外，當增大懲罰因子V時，虛擬隊列長度Q(t)也隨之增大，同時系統達到遷移成本穩定的收斂時間也變長。其原因在于，當增大懲罰因子V時，意味著系統優化目標更偏重于用戶的感知時延，導致系統為獲取更低的用戶感知時延，需要進行更加頻繁的服務遷移，從而增加了系統虛擬隊列長度Q(t)與達到穩定的時間。也就是說，為提高用戶的服務質量，系統需要投入更多的服務遷移成本來換取更高的虛擬隊列的積壓容忍度。圖4(b)為FSMM 在不同懲罰因子V下虛擬隊列長度Q(t)的變化情況。當用戶user1與user2在如圖2 所示的單個SBS 內移動時，其服務遷移決策保持不變，因此虛擬隊列長度保持不變；當user1和user2跨SBS 移動時，觸發服務遷移策略，其虛擬隊長隨時間的增長而下降。圖4(c)表示COSM 在不同懲罰因子V下虛擬隊列長度Q(t)的變化情況。可以看出，隨著時間的推移，Q(t)逐漸下降到某一穩定值。圖4(d)為ISMM 在不同懲罰因子V下虛擬隊列長度Q(t)的變化情況。當V值較小時，每個時刻遷移成本均小于長期遷移閾值Eavg，因此Q(t)值不斷變小并最后達到穩定；當V較大時，頻繁的服務遷移造成遷移成本大于遷移閾值，使其Q(t)不斷增大直到穩定。

圖5 為不同懲罰因子V下用戶的平均感知時延。可以看出，在平穩狀態時，AORAM 得到的用戶平均感知時延相對于其他3 種對比算法分別減少了90.84 ms、106.45 ms、112.55 ms。由于FSMM中服務遷移決策取決于用戶與SBS 的相對位置，所以V值不影響服務遷移決策，但容易造成邊緣服務器負載失衡，導致服務質量降低。當V＜100時，隨著V的增加，ISMM、COSM 與AORAM 的感知時延快速下降。但當200≤V＜2000時，AORAM 感知時延能夠達到更低值，表明所提的AORAM 在保障更高服務質量的同時增大了長期服務遷移閾值的可調范圍。圖6 表示不同懲罰因子V下系統的平均遷移成本。雖然AORAM 相比于其他算法具有較高的遷移成本，但其遷移成本隨著V值增大逐漸收斂，收斂值仍低于預期閾值Eavg，結合圖5 可知，AORAM 在保持系統遷移成本相對穩定的情況下能夠顯著降低用戶平均感知時延。

圖4 不同懲罰因子V下的虛擬隊列長度

圖5 用戶感知時延

圖6 平均遷移成本

圖7 展示了不同長期遷移預算成本Eavg下虛擬隊列的長度變化情況，其中M=20 。當Eavg＜15 時，虛擬隊列長度隨著時間的推移不斷增大，無法收斂。根據式(11)可知，過小的Eavg將導致每個時隙遷移成本超出預期，使虛擬隊列長度不斷增大，出現虛擬隊列長度隨時間推移而無法收斂的情況。同理，當Eavg為15～25 時，虛擬隊列長度最終都隨著時間的推移而收斂，且Eavg越大，收斂速度越快，收斂值越小。但是，過大的Eavg導致每個時隙的服務遷移成本都小于長期預算成本，如Eavg=50，根據式(11)可知，虛擬隊列長度急劇下降為0。

圖7 不同長期預算成本下的虛擬隊列長度

6.2 非確定性用戶軌跡的仿真模型

由于用戶的運動路徑具有不可預測性，因此在每個時隙t的開始時刻，用戶的地理位置表現出隨機性。為仿真該情形，在每一個時隙對系統中15 個用戶的地理位置進行隨機化處理來代表用戶的位置變化。對3 000 個時隙進行了仿真，其中在每個時隙的開始時刻對用戶的地理位置進行隨機初始化處理，懲罰因子設置為V=10 000，遷移預算成本設置為Eavg=35。圖8 展示了該場景下虛擬隊列長度隨時間的變化情況。當所有用戶進行隨機運動時，前一時刻所得到的邊緣節點參數需全部更新為此時刻初始邊緣節點參數，即COSM 與AORAM 算法相同。

圖8 虛擬隊列長度隨時間的變化

從圖8(a)可以看出，當系統中所有用戶進行無規則運動時，AORAM 和COSM 得到的虛擬隊列長度在0～850 Mbit 之間波動。由于用戶位置的隨機性可能導致一段時間內大部分用戶的位置沒有大的變化，出現服務遷移成本低于遷移閾值的情況，根據式(11)可知，虛擬隊列長度將會一直處于下降狀態直到為0。同理可得，造成虛擬隊列長度接近850 Mbit的原因在于，在一段時間內用戶在每個時隙內的服務遷移成本一直大于遷移閾值，導致虛擬隊列長度一直處于上升階段。由圖8(b)可以看出，當用戶進行隨機移動時，FSMM 的虛擬隊列長度隨著時間的推移不斷增大，這表明長期遷移成本大于遷移閾值。從圖8(c)可以看出，由于ISMM 要求系統每隔一段時間后進行服務遷移，導致虛擬隊列長度出現為0 的時間段占總時間的比例達83.97%。通過分析可知，當用戶進行無規則隨機運動時，系統存在最小的遷移成本閾值，如果遷移預算成本Eavg大于該閾值，隨著時間不斷推移，虛擬隊列長度將在某一范圍內不斷波動，相反，虛擬隊列將不斷增大，無法收斂。在這種情況下，用戶的服務質量將嚴重失衡，例如，距離SBS 更近的用戶的服務質量更好，但距離SBS遠的用戶服務質量較差。過大的Eavg雖然能大幅度降低虛擬隊列長度，提高用戶的服務質量，但增加了服務提供商的服務遷移費用。

用戶平均感知時延如表2 所示。從表2 可以看出，相比于FSMM 與ISMM，所提算法能夠分別降低用戶感知時延18.45%、5.28%。

表2 用戶平均感知時延

圖9 表示所提快速邊緣決策算法（算法1）與窮舉法在不同懲罰因子V下的虛擬隊列長度值。可以觀察到，當懲罰因子V＜3 000時，基于2 種算法的虛擬隊列長度曲線重合，表明了所提算法與窮舉法所做出的服務遷移策略X(t)一致。當懲罰因子V＞3 000時，不同的服務遷移算法所得到的系統性能出現差異，其主要原因在于，隨著V值不斷增大，系統通過放寬虛擬隊列長度的容忍度，進行更好的服務遷移來進一步提高用戶服務質量。另一方面，增大V值意味著P2 優化目標更加偏重于用戶的感知時延。通過計算得到所提算法與窮舉法的平均虛擬隊列誤差值σ≈3.75%。為進一步驗證所提出的算法與窮舉法在用戶服務質量上的增益差異，仿真了不同用戶數下2 種算法的運行時間，如圖10 所示。可以看出，隨著用戶數的增加，2 種算法所需的平均運行時間也隨之變大，所提算法在運行時間上遠低于窮舉法。

圖9 平均虛擬隊列長度

圖10 平均運行時間

7 結束語

本文研究了移動邊緣計算網絡中用戶的移動性及其位置的動態性對用戶服務請求的平均感知時延的影響，提出了一種移動性感知的在線邊緣服務遷移算法。由于優化問題屬于高度耦合時間與空間相關性的混合整數非線性規劃問題，首先基于Lyapunov 方法將優化問題解耦為邊緣服務遷移與節點選擇問題，其次提出快速邊緣決策算法求解給定邊緣節點選擇策略下最優的資源分配與服務遷移策略，最后利用所提的異步最佳響應算法求解最優邊緣節點選擇策略。仿真結果表明，所提邊緣服務遷移策略能夠有效地降低用戶服務請求的平均感知時延。本文方案為移動場景下在線服務遷移的研究提供了新的思路，然而在實際場景中，還需要考慮諸如服務類型、服務請求的最大容忍時延等因素，未來工作將探索上述因素對在線服務遷移性能的影響，為實際網絡提供更加準確的決策。