面向移動邊緣計算中多應用服務的虛擬機部署算法

李光輝 周 輝 胡世紅

(江南大學人工智能與計算機學院 無錫 214122)

1 引言

近年來，5G技術和物聯網技術快速發展，移動設備(如智能手機和可穿戴設備等)的數量急劇增長。各種應用服務的爆炸性激增對計算能力和實時處理提出了嚴格的要求。受限于計算資源和能源供給[1]的移動設備已經無法應對這一挑戰。移動邊緣計算[2](Mobile Edge Computing, MEC)作為一種有潛力的新興計算范式，可通過在用戶附近部署計算和存儲等資源來提高服務質量[3]。AR和視頻游戲等實時交互應用的增多導致移動邊緣網絡中的數據流量迅速增長，造成嚴重的網絡資源消耗，使用戶訪問應用服務時延遲增加。因此，為了更好地控制網絡時延并減少潛在的核心網堵塞，必須減少邊緣網絡的數據流量。一個有效的解決方案是在邊緣網絡中部署支持多種應用服務的虛擬機(Virtual Machine, VM)為移動用戶提供各種近端服務[4]，依靠高帶寬和脫機可用性來緩解核心網絡的擁塞，同時通過滿足延遲和能耗等關鍵應用需求進一步提高計算服務質量。

VM是一個邏輯容器，可使用數據運行軟件實例。在MEC中使用VM技術，能使MEC服務器成為特定應用的應用服務器，即特定的應用請求只能由部署有相關應用VM的MEC服務器提供服務。目前，已有許多關于MEC中VM管理問題的研究。由于用戶的移動性，MEC系統需要在用戶位置隨時間變化時進行服務遷移，文獻[5]提出了一種代理VM遷移方案，采用基站與霧節點在本地提供計算資源的方式來為用戶提供服務。為了減少服務遷移過程中出現的性能下降問題，文獻[6]提出了一種自適應VM切換方法來減少用戶移動時進行服務遷移需要傳輸的數據量。考慮到用戶多種服務需求，文獻[7]提出3種啟發式算法尋找VRC最優部署位置來最小化平均請求響應時間。此外，文獻[8]設計了一種VM容錯部署機制來針對可能出現的邊緣服務器故障問題。然而，很少有研究考慮邊緣網絡中關于數據流量的綠色通信問題。

盡管現有工作對MEC中邊緣網絡的資源配置問題提出了很多解決方案，但存在一個共同的局限性：沒有具體考慮用戶對多種應用服務的需求。在邊緣網絡中提供多種應用服務將面臨許多挑戰，如不同應用對傳輸帶寬的需求差異會導致不同的平均鏈路時延，所需服務資源的多樣性會導致邊緣服務器不同的工作負載等。文獻[9]采用云邊資源協作的方式為用戶提供服務，提出一種云邊協同模式下的任務分配機制將應用負載分配給合適的微云(Cloudlet)來最小化用戶響應時延。文獻[10]通過圖分割的方式將實際的物理網絡抽象為一個完全圖，用服務器之間的通信時延表示邊緣網絡中的費用，提出一種數據訪問延遲最小化的虛擬機部署最優近似算法。然而他們沒有考慮為用戶提供多種不同特性的應用服務。文獻[11]設計了一種有效的任務調度和資源管理策略最小化任務完成時間，文中提到可以支持多種應用類型，但是沒有明確指出支持的不同應用之間的區別。多數工作在部署邊緣網絡中的資源提供服務時，沒有詳細考慮提供多種應用的差異性[12]，而是集中于研究邊緣服務器和移動用戶之間的交互及協作[13,14]，他們簡單地假設所有移動用戶的資源需求是統一的[15]，而實際情況中，必須考慮不同應用對資源的需求差異，這些將顯著影響最優路由選擇和工作負載分配。

因此，本文以最小化移動邊緣網絡中云邊數據流量和最小化服務配置總成本為目標，構建了一種云邊協同的計算架構，在此架構基礎上對支持多種應用服務的虛擬機部署問題進行研究，在邊緣服務器服務能力一定且提供多種應用服務前提下，將問題形式化描述為資源約束下的最小化云邊數據流量和部署總成本的優化問題。本文主要工作如下：

(1) 基于MEC架構，本文首次研究了在提供多種應用服務的邊緣網絡中，將每種應用的k個VM部署到|S|個邊緣服務器上，以最小化邊緣網絡中的平均數據流量(Minimizing the Average Data Traffic, MADT)為目標。

(2) 針對上述問題，本文首先從網絡拓撲結構特性出發，計算每個邊緣服務器的中心性特征，根據定義的適應度模型，提出了一種基于適應度的啟發式部署算法(Fitness-based Heuristic Placement Algorithm, FHPA)。另外，從用戶對不同應用服務需求差異化考慮，定義適應度模型，通過子問題劃分策略，設計了一種基于分治的啟發式部署算法

(Divide-and-Conquer Based Heuristic Placement Algorithm, DCBHPA)。

(3) 仿真結果表明，相比于基準算法和FHPA，DCBHPA能最大限度地減少數據流量，有效地緩解遠端云的流量壓力，減少潛在的核心網擁塞。同時，對邊緣網絡中提供服務的配置總成本問題進行了研究。

2 系統模型

2.1 移動邊緣計算架構

基于MEC的系統框架如圖1所示，該框架由移動設備、MEC服務器組成的邊緣網絡和遠端云中心構成，其中，邊緣網絡采用的是MEC服務器與基站共同部署在無線接入網內的結構。各種資源密集型和時間敏感型的移動應用源服務器，例如a1,a2,a3，運行在遠端云計算中心，同時在邊緣端，邊緣服務器 M ECS1和M ECS3分別部署有應用a1的 VM，可充當應用a1的應用服務器(Application Server, AS)，為移動用戶提供特定的服務請求。

圖1 提供多種應用服務的移動邊緣計算架構

所有來自用戶的請求首先由本地邊緣服務器進行處理，每個邊緣服務器會根據當前邊緣網絡的資源利用情況為服務請求做出最優路由抉擇，確保其從邊緣網絡相應AS或遠端云中心獲取服務。例如，M ECS2服 務范圍內的移動用戶對應用a1的請求將被路由到部署有應用a1相 應VM的M ECS1，由服務器M ECS1提供服務。同時對每個邊緣服務器的服務容量進行約束，當網絡中AS的服務資源耗盡時，如 M ECS1和M ECS3全部過載，新接收的應用a1的請求由云中心提供服務。

2.2 網絡模型

3 問題描述

3.1 平均數據流量最小化問題

移動用戶的服務請求在云邊協同的MEC架構獲取服務產生的數據流量包括：(1)由邊緣網絡中的AS為移動設備提供服務的邊緣流量；(2)遠端云提供服務產生的云邊通信流量。將邊緣網絡中任意兩臺邊緣服務器間的最短路徑作為二者間的路由選擇，使用變量dv,u表示邊緣服務器v到u的最短路徑跳數，則MEC服務器v服務區域內的用戶請求路由到MEC服務器u獲取對應用a請求服務的數據流量定義為

3.2 應用服務配置總成本問題

配置總成本由VM部署成本和請求服務的數據流量成本構成。將相同應用相應VM間的狀態同步和部署VM到邊緣服務器的資源需求作為部署成本，定義為所有應用種類數和支持每種應用VM數的2次函數，即ε·k·|A|， 其中0＜ε ＜1。數據流量成本體現了邊緣網絡的擁堵情況，可由所取得的邊緣端流量De和 云端流量Dc的線性函數表示，分別為σ1·De和σ2·Dc，其中σ1,σ2＞0。對部署成本和數據流量成本經過標準化函數f,N計算后，定義整個系統的服務配置總成本為

4 算法設計

4.1 基于適應度的啟發式部署算法

為了解決MADT問題，本文提出一種基于適應度的啟發式部署算法。對于應用a，FHPA尋找k個適應度最高的MEC服務器部署應用虛擬機，其中每個MEC服務器的適應度評價由4種網絡連接特征構成，包括接近中心性(closeness centrality)、度中心性(degree dentrality)、中介中心性(betweenness centrality)和特征向量中心性(eigenvector centrality)，再根據熵權法對每個連接特征的權重進行計算。下面首先介紹上述連接特征的概念。

(1)度中心性。度中心性的基本思想是網絡中重要節點為與其他節點的連接邊數較多的節點。相應地，MEC服務器s的度中心性為與他直接相連的MEC服務器個數，歸一化后服務器s的度中心性計算表達式為

對于應用a∈A，基于每個MEC服務器的適應度降序排序結果，選擇前k個服務器為應用a的初始AS，分別分配到集合Xi,i=1,2,...,k，結合文獻[17]，設計一個聚類機制如表1，輪詢地將全部候選MEC服務器劃分到與其最近的初始AS所在集合Xi。對集合Xi中的每一個MEC服務器，將其作為該集合中應用a的AS為集合中其他邊緣服務器服務范圍內的應用請求提供服務，并計算所產生的數據流量，最后選擇能最小化該集合中平均數據流量的MEC服務器，部署應用VM。FHPA通過將MADT問題劃分為k個子問題，在每個子問題中尋找應用服務a的一個VM最優部署位置，然后通過整合子問題的最優解求解原問題，FHPA詳情如表2所示。

表1 聚類過程

表2 基于適應度的啟發式部署算法

4.2 基于分治的啟發式部署算法

由于應用請求在本地MEC服務器進行處理將不會注入流量到邊緣網絡，因此，選擇覆蓋范圍內應用請求數較大的MEC服務器作為AS，可以減少產生到邊緣網絡的流量。然而，由于AS容量受限，這樣會導致該AS附近的邊緣服務器的應用請求發送到云端的比例將上升，進而增加系統流量成本。因此，本節進一步提出一種基于分治的啟發式部署算法，與文獻[18]只考慮用戶請求密度不同，DCBHPA將當前已配置應用a相應VM的邊緣服務器對網絡中其他將部署同應用服務VM的候選MEC服務器的影響進行了考慮，從而避免應用a的AS集中在網絡某一局部地區，提高服務資源的利用率。

變量Q表示已部署應用a相應VM的MEC服務器集，與當前已部署的AS越遠，則候選MEC服務器所受影響越小，設當前已部署的ASj對候選MEC服務器i ∈S的影響因子為θ·t(i,j)，其中0＜θ ＜1,t(i,j)為i和j歸一化后的距離。每個候選MEC服務器將受到當前所有已部署AS的影響，影響因子為

在每次迭代中，DCBHPA選擇P值更高的MEC服務器作為初始AS，k次迭代更新后，選擇k個初始AS加入集合Xi,i=1,2,...,k進行初始化，之后的求解MADT過程同FHPA，DCBHPA詳情見表3。

表3 基于分治的啟發式部署算法

4.3 算法分析

FHPA是一個簡單有效的算法。它首先計算每個MEC服務器的連接特征。其中，每個MEC服務器的接近中心性表明它與邊緣網絡中其余MEC服務器的平均距離。度中心性越高，則該MEC服務器能在相同的距離內與更多的MEC服務器相連，距離越短則服務請求產生的數據流量越小。因此具有更高度中心性的MEC服務器更適合部署應用虛擬機。當網絡中所有移動設備的應用服務請求路由到相應的應用服務器時，通過每個MEC服務器的路徑個數能顯示該MEC服務器上需傳輸數據的到達速率，邊緣網絡中路由路徑數越多經過該MEC服務器，表明該MEC服務器節點擁堵程度越高，則請求數據在該服務器節點的等待時間將很長，這一特性通過中介中心性表現出來。為了避免在網絡中影響程度較低的MEC服務器成為應用服務器，將每個MEC服務器的特征向量中心性考慮進來。因此，基于歸一化的連接特征值，計算每個MEC服務器上的所有連接特征的權重之和，得出每個MEC服務器部署應用虛擬機的適應度。最后FHPA選擇適應度最高的k個MEC服務器部署應用虛擬機。

然而，FHPA也存在兩個缺點。第1個缺點是選擇虛擬機部署的MEC服務器時，沒有考慮用戶的請求數。來自用戶的服務請求由本地邊緣服務器處理將不會注入流量到邊緣網絡，從而選擇覆蓋范圍內有大量應用請求的MEC服務器部署應用虛擬機，并將其作為AS可以減少網絡的流量負載。因此，邊緣服務器范圍內移動用戶的服務請求數也是影響其部署應用虛擬機成為AS的重要因素。然而，FHPA從網絡拓撲結構的連接特征出發來確定應用虛擬機部署位置，沒有利用移動用戶請求數來提升部署效益。第2個缺點是當大量用戶集中在邊緣網絡同一局部地區時，FHPA容易造成部分AS過載。因此，本文從用戶請求角度出發進一步提出DCBHPA算法求解MADT問題。

DCBHPA考慮了當前已部署應用虛擬機的邊緣服務器對邊緣網絡中其余候選MEC服務器的影響因素。第1個是每個MEC服務器與當前已部署虛擬機的MEC服務器間的平均距離，為了避免應用服務器集中部署在邊緣網絡的某一局部地區，候選MEC服務器與當前已部署應用虛擬機的MEC服務器距離越遠越合適。第2個是在當前已部署的應用服務器提供服務的情況下，每個邊緣服務器接收的應用請求數量。為了減少邊緣網絡中的平均數據流量，接收應用請求數量更多的MEC服務器更適合部署應用虛擬機作為下一個AS。DCBHPA在每次迭代中選擇適應度最高的MEC服務器來部署應用虛擬機，對于應用a∈A， 在k次迭代后，獲得k個最適合部署關于應用a相應虛擬機的邊緣服務器。因此，DCBHPA在共經過k·|A|次迭代后，完成所有應用的虛擬機部署。

5 仿真分析

本文利用Python工具完成了仿真實驗。不失一般性，從Topology Zoo獲得真實的在線網絡拓撲用于VM部署實驗[19]，網絡拓撲圖結構如表4所示。不同應用服務的網絡帶寬需求設置為[800 kB,1600 kB]，并假定分布在整個邊緣網絡的移動用戶數在500～3000。默認設置3種應用以及每種應用部署4個VM和noel通信網絡進行實驗。同時，選擇文獻[20]中的RPA算法和文獻[21]中的DBC算法進行性能比較。

表4 網絡拓撲表

5.1 網絡數據流量

如圖2所示，各算法產生的平均數據流量隨著支持每種應用的VM數增加而單調減少。這是因為隨著邊緣網絡中支持同一應用服務的VM數增多，即該應用的AS數量增加，可以在本地進行更多的請求處理，從而減少注入到邊緣網絡中的數據流量。同時，配置更多的VM可以減少邊緣網絡中移動用戶與請求的目的AS之間的平均距離，導致邊緣網絡更小的數據流量產生。從圖2可以發現，DCBHPA在最小化平均數據流量方面相比其他算法可以獲得最優性能，FHPA性能表現要優于DBC，且二者都優于RPA。

圖2 不同VM數對數據流量的影響

從圖3可以清楚地發現，在相同數量的移動用戶情況下，與FHPA, DBC和RPA相比，DCBHPA總是可以獲得最小的平均數據流量。此外，在移動用戶數較小的情況下，各算法性能差異較小，隨著用戶數不斷增加，所有4種算法提供服務產生的平均數據流量都會增加，其中RPA數據流量增加最為明顯。當移動用戶數為3000時，DCBHPA相比RPA可以減少25.8%的流量生成，反映了DCBHPA在大規模移動邊緣網絡中為移動用戶提供多種應用服務進行VM配置的優勢。

圖3 移動用戶數對數據流量的影響

圖4為不同網絡拓撲下FHPA, DCBHPA,DBC和RPA在邊緣網絡中最小化請求數據流量方面的性能比較結果，可以看到4種算法提出的服務配置方案產生的數據流量會隨著網絡規模的擴大而上升。在同一網絡下，DCBHPA在減小平均數據流量方面能獲得最佳性能表現。同時，圖5進一步比較了FHPA, DCBHPA, DBC和RPA在應用服務類型不斷增多情況下的性能。實驗結果表明，DCBHPA要優于其他3種算法。與此同時，隨著不同應用種類的增加，各算法進行VM配置提供服務所產生的數據流量都會增長，且DCBHPA與FHPA, DBC和RPA的性能差異也更加明顯。此外，FHPA和DBC的性能表現基本相近，且二者都要優于RPA。

圖4 網絡規模對數據流量的影響

圖5 應用服務種類數對數據流量的影響

接著，在支持每種應用服務的VM數量不同且應用服務種數不斷增加的前提下，進一步分析了DCBHPA的性能表現。仿真結果如圖6所示，當應用服務數量增加時，對于支持各應用服務的每組VM設置，DCBHPA獲得的平均數據流量呈指數增加。這是因為更多的應用服務種類意味著邊緣網絡中將有更多的應用請求需要提供服務，而這將導致AS可用服務資源的短缺，進而增加系統的數據流量產生。同時，更多的服務請求將發送到云端獲得服務從而增加流量成本。從圖6可以看出，當應用服務種類一定時，隨著支持每種應用服務的VM增加，系統的平均數據流量將越少，這與圖2的實驗結果相符。

圖6 不同應用服務下VM部署取得的數據流量

5.2 服務配置總成本

一個好的部署方案不僅要保證較低的平均數據流量，而且要考慮邊緣網絡中提供服務配置的成本因素，因此，我們進一步分析了DCBHPA提供服務時的總成本。如圖7所示，同一應用提供更多的VM部署到邊緣網絡將減少流量成本，同時增加部署成本。通過將歸一化后的流量成本和部署成本相加，可以得到服務提供總成本。從圖中可以發現，當VM部署數量不超過3時，總成本隨著VM配置數量的增加而下降，這是因為當VM的數量很小時，主導服務配置總成本的是數據流量成本，如圖2所述，因此總成本將隨著支持每種應用服務的VM數量的增加而減少。當部署VM的數量繼續增加時，VM的配置成本就會逐漸占據服務配置總成本的主導地位，導致當支持每種應用服務的VM數量超過3時，DCBHPA提供服務配置的總成本會隨著VM數的增加而增長。

圖7 不同VM數對歸一化服務配置總成本的影響

如圖8所示，在應用服務種類不斷增加且支持每種應用服務的VM數為4的情況下，對4種算法在應用服務部署成本方面的性能進行了比較。圖8表明，在最小化部署總成本方面，DCBHPA可以獲得最佳性能表現，且FHPA要優于DBC，同時二者都要強于RPA。根據定義，VM部署成本為支持每種應用的VM數和不同應用種類數的2次函數，因此部署成本將會隨著應用數的增加而上升。圖5表明所有算法產生的數據流量會隨著應用種類數的擴展而顯著增加，因此數據流量成本將隨著算法產生的數據流量增加而線性增長，所以服務配置總成本將隨著應用種類數的增加而上升，這與圖8的結果一致。

圖8 應用服務種類數對歸一化服務配置總成本的影響

6 結束語

本文研究了移動邊緣網絡中支持多種應用服務的VM部署問題，在提供多種應用服務請求和MEC服務器處理能力受限約束下，為了最小化移動邊緣網絡中的平均數據流量這一目標，提出了兩種啟發式的部署算法，并利用廣泛的仿真實驗來評估所提算法的性能。實驗結果表明，DCBHPA算法性能在最大限度地減少平均數據流量方面，要優于FHPA算法和基準算法，能有效減少云邊通信流量，緩解潛在的網絡堵塞問題。未來工作中，將進一步深入研究多應用服務下不同VM部署方案對用戶所需服務的平均請求響應時間的影響規律。