面向移動(dòng)邊緣計(jì)算中多應(yīng)用服務(wù)的虛擬機(jī)部署算法

李光輝 周 輝 胡世紅

(江南大學(xué)人工智能與計(jì)算機(jī)學(xué)院 無(wú)錫 214122)

1 引言

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

VM是一個(gè)邏輯容器，可使用數(shù)據(jù)運(yùn)行軟件實(shí)例。在MEC中使用VM技術(shù)，能使MEC服務(wù)器成為特定應(yīng)用的應(yīng)用服務(wù)器，即特定的應(yīng)用請(qǐng)求只能由部署有相關(guān)應(yīng)用VM的MEC服務(wù)器提供服務(wù)。目前，已有許多關(guān)于MEC中VM管理問(wèn)題的研究。由于用戶(hù)的移動(dòng)性，MEC系統(tǒng)需要在用戶(hù)位置隨時(shí)間變化時(shí)進(jìn)行服務(wù)遷移，文獻(xiàn)[5]提出了一種代理VM遷移方案，采用基站與霧節(jié)點(diǎn)在本地提供計(jì)算資源的方式來(lái)為用戶(hù)提供服務(wù)。為了減少服務(wù)遷移過(guò)程中出現(xiàn)的性能下降問(wèn)題，文獻(xiàn)[6]提出了一種自適應(yīng)VM切換方法來(lái)減少用戶(hù)移動(dòng)時(shí)進(jìn)行服務(wù)遷移需要傳輸?shù)臄?shù)據(jù)量?？紤]到用戶(hù)多種服務(wù)需求，文獻(xiàn)[7]提出3種啟發(fā)式算法尋找VRC最優(yōu)部署位置來(lái)最小化平均請(qǐng)求響應(yīng)時(shí)間。此外，文獻(xiàn)[8]設(shè)計(jì)了一種VM容錯(cuò)部署機(jī)制來(lái)針對(duì)可能出現(xiàn)的邊緣服務(wù)器故障問(wèn)題。然而，很少有研究考慮邊緣網(wǎng)絡(luò)中關(guān)于數(shù)據(jù)流量的綠色通信問(wèn)題。

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

因此，本文以最小化移動(dòng)邊緣網(wǎng)絡(luò)中云邊數(shù)據(jù)流量和最小化服務(wù)配置總成本為目標(biāo)，構(gòu)建了一種云邊協(xié)同的計(jì)算架構(gòu)，在此架構(gòu)基礎(chǔ)上對(duì)支持多種應(yīng)用服務(wù)的虛擬機(jī)部署問(wèn)題進(jìn)行研究，在邊緣服務(wù)器服務(wù)能力一定且提供多種應(yīng)用服務(wù)前提下，將問(wèn)題形式化描述為資源約束下的最小化云邊數(shù)據(jù)流量和部署總成本的優(yōu)化問(wèn)題。本文主要工作如下：

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

(2) 針對(duì)上述問(wèn)題，本文首先從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)特性出發(fā)，計(jì)算每個(gè)邊緣服務(wù)器的中心性特征，根據(jù)定義的適應(yīng)度模型，提出了一種基于適應(yīng)度的啟發(fā)式部署算法(Fitness-based Heuristic Placement Algorithm, FHPA)。另外，從用戶(hù)對(duì)不同應(yīng)用服務(wù)需求差異化考慮，定義適應(yīng)度模型，通過(guò)子問(wèn)題劃分策略，設(shè)計(jì)了一種基于分治的啟發(fā)式部署算法

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

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

2 系統(tǒng)模型

2.1 移動(dòng)邊緣計(jì)算架構(gòu)

基于MEC的系統(tǒng)框架如圖1所示，該框架由移動(dòng)設(shè)備、MEC服務(wù)器組成的邊緣網(wǎng)絡(luò)和遠(yuǎn)端云中心構(gòu)成，其中，邊緣網(wǎng)絡(luò)采用的是MEC服務(wù)器與基站共同部署在無(wú)線接入網(wǎng)內(nèi)的結(jié)構(gòu)。各種資源密集型和時(shí)間敏感型的移動(dòng)應(yīng)用源服務(wù)器，例如a1,a2,a3，運(yùn)行在遠(yuǎn)端云計(jì)算中心，同時(shí)在邊緣端，邊緣服務(wù)器 M ECS1和M ECS3分別部署有應(yīng)用a1的 VM，可充當(dāng)應(yīng)用a1的應(yīng)用服務(wù)器(Application Server, AS)，為移動(dòng)用戶(hù)提供特定的服務(wù)請(qǐng)求。

圖1 提供多種應(yīng)用服務(wù)的移動(dòng)邊緣計(jì)算架構(gòu)

所有來(lái)自用戶(hù)的請(qǐng)求首先由本地邊緣服務(wù)器進(jìn)行處理，每個(gè)邊緣服務(wù)器會(huì)根據(jù)當(dāng)前邊緣網(wǎng)絡(luò)的資源利用情況為服務(wù)請(qǐng)求做出最優(yōu)路由抉擇，確保其從邊緣網(wǎng)絡(luò)相應(yīng)AS或遠(yuǎn)端云中心獲取服務(wù)。例如，M ECS2服 務(wù)范圍內(nèi)的移動(dòng)用戶(hù)對(duì)應(yīng)用a1的請(qǐng)求將被路由到部署有應(yīng)用a1相 應(yīng)VM的M ECS1，由服務(wù)器M ECS1提供服務(wù)。同時(shí)對(duì)每個(gè)邊緣服務(wù)器的服務(wù)容量進(jìn)行約束，當(dāng)網(wǎng)絡(luò)中AS的服務(wù)資源耗盡時(shí)，如 M ECS1和M ECS3全部過(guò)載，新接收的應(yīng)用a1的請(qǐng)求由云中心提供服務(wù)。

2.2 網(wǎng)絡(luò)模型

3 問(wèn)題描述

3.1 平均數(shù)據(jù)流量最小化問(wèn)題

移動(dòng)用戶(hù)的服務(wù)請(qǐng)求在云邊協(xié)同的MEC架構(gòu)獲取服務(wù)產(chǎn)生的數(shù)據(jù)流量包括：(1)由邊緣網(wǎng)絡(luò)中的AS為移動(dòng)設(shè)備提供服務(wù)的邊緣流量；(2)遠(yuǎn)端云提供服務(wù)產(chǎn)生的云邊通信流量。將邊緣網(wǎng)絡(luò)中任意兩臺(tái)邊緣服務(wù)器間的最短路徑作為二者間的路由選擇，使用變量dv,u表示邊緣服務(wù)器v到u的最短路徑跳數(shù)，則MEC服務(wù)器v服務(wù)區(qū)域內(nèi)的用戶(hù)請(qǐng)求路由到MEC服務(wù)器u獲取對(duì)應(yīng)用a請(qǐng)求服務(wù)的數(shù)據(jù)流量定義為

3.2 應(yīng)用服務(wù)配置總成本問(wèn)題

配置總成本由VM部署成本和請(qǐng)求服務(wù)的數(shù)據(jù)流量成本構(gòu)成。將相同應(yīng)用相應(yīng)VM間的狀態(tài)同步和部署VM到邊緣服務(wù)器的資源需求作為部署成本，定義為所有應(yīng)用種類(lèi)數(shù)和支持每種應(yīng)用VM數(shù)的2次函數(shù)，即ε·k·|A|， 其中0＜ε ＜1。數(shù)據(jù)流量成本體現(xiàn)了邊緣網(wǎng)絡(luò)的擁堵情況，可由所取得的邊緣端流量De和 云端流量Dc的線性函數(shù)表示，分別為σ1·De和σ2·Dc，其中σ1,σ2＞0。對(duì)部署成本和數(shù)據(jù)流量成本經(jīng)過(guò)標(biāo)準(zhǔn)化函數(shù)f,N計(jì)算后，定義整個(gè)系統(tǒng)的服務(wù)配置總成本為

4 算法設(shè)計(jì)

4.1 基于適應(yīng)度的啟發(fā)式部署算法

為了解決MADT問(wèn)題，本文提出一種基于適應(yīng)度的啟發(fā)式部署算法。對(duì)于應(yīng)用a，F(xiàn)HPA尋找k個(gè)適應(yīng)度最高的MEC服務(wù)器部署應(yīng)用虛擬機(jī)，其中每個(gè)MEC服務(wù)器的適應(yīng)度評(píng)價(jià)由4種網(wǎng)絡(luò)連接特征構(gòu)成，包括接近中心性(closeness centrality)、度中心性(degree dentrality)、中介中心性(betweenness centrality)和特征向量中心性(eigenvector centrality)，再根據(jù)熵權(quán)法對(duì)每個(gè)連接特征的權(quán)重進(jìn)行計(jì)算。下面首先介紹上述連接特征的概念。

(1)度中心性。度中心性的基本思想是網(wǎng)絡(luò)中重要節(jié)點(diǎn)為與其他節(jié)點(diǎn)的連接邊數(shù)較多的節(jié)點(diǎn)。相應(yīng)地，MEC服務(wù)器s的度中心性為與他直接相連的MEC服務(wù)器個(gè)數(shù)，歸一化后服務(wù)器s的度中心性計(jì)算表達(dá)式為

對(duì)于應(yīng)用a∈A，基于每個(gè)MEC服務(wù)器的適應(yīng)度降序排序結(jié)果，選擇前k個(gè)服務(wù)器為應(yīng)用a的初始AS，分別分配到集合Xi,i=1,2,...,k，結(jié)合文獻(xiàn)[17]，設(shè)計(jì)一個(gè)聚類(lèi)機(jī)制如表1，輪詢(xún)地將全部候選MEC服務(wù)器劃分到與其最近的初始AS所在集合Xi。對(duì)集合Xi中的每一個(gè)MEC服務(wù)器，將其作為該集合中應(yīng)用a的AS為集合中其他邊緣服務(wù)器服務(wù)范圍內(nèi)的應(yīng)用請(qǐng)求提供服務(wù)，并計(jì)算所產(chǎn)生的數(shù)據(jù)流量，最后選擇能最小化該集合中平均數(shù)據(jù)流量的MEC服務(wù)器，部署應(yīng)用VM。FHPA通過(guò)將MADT問(wèn)題劃分為k個(gè)子問(wèn)題，在每個(gè)子問(wèn)題中尋找應(yīng)用服務(wù)a的一個(gè)VM最優(yōu)部署位置，然后通過(guò)整合子問(wèn)題的最優(yōu)解求解原問(wèn)題，F(xiàn)HPA詳情如表2所示。

表1 聚類(lèi)過(guò)程

表2 基于適應(yīng)度的啟發(fā)式部署算法

4.2 基于分治的啟發(fā)式部署算法

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

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

在每次迭代中，DCBHPA選擇P值更高的MEC服務(wù)器作為初始AS，k次迭代更新后，選擇k個(gè)初始AS加入集合Xi,i=1,2,...,k進(jìn)行初始化，之后的求解MADT過(guò)程同F(xiàn)HPA，DCBHPA詳情見(jiàn)表3。

表3 基于分治的啟發(fā)式部署算法

4.3 算法分析

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

然而，F(xiàn)HPA也存在兩個(gè)缺點(diǎn)。第1個(gè)缺點(diǎn)是選擇虛擬機(jī)部署的MEC服務(wù)器時(shí)，沒(méi)有考慮用戶(hù)的請(qǐng)求數(shù)。來(lái)自用戶(hù)的服務(wù)請(qǐng)求由本地邊緣服務(wù)器處理將不會(huì)注入流量到邊緣網(wǎng)絡(luò)，從而選擇覆蓋范圍內(nèi)有大量應(yīng)用請(qǐng)求的MEC服務(wù)器部署應(yīng)用虛擬機(jī)，并將其作為AS可以減少網(wǎng)絡(luò)的流量負(fù)載。因此，邊緣服務(wù)器范圍內(nèi)移動(dòng)用戶(hù)的服務(wù)請(qǐng)求數(shù)也是影響其部署應(yīng)用虛擬機(jī)成為AS的重要因素。然而，F(xiàn)HPA從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的連接特征出發(fā)來(lái)確定應(yīng)用虛擬機(jī)部署位置，沒(méi)有利用移動(dòng)用戶(hù)請(qǐng)求數(shù)來(lái)提升部署效益。第2個(gè)缺點(diǎn)是當(dāng)大量用戶(hù)集中在邊緣網(wǎng)絡(luò)同一局部地區(qū)時(shí)，F(xiàn)HPA容易造成部分AS過(guò)載。因此，本文從用戶(hù)請(qǐng)求角度出發(fā)進(jìn)一步提出DCBHPA算法求解MADT問(wèn)題。

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

5 仿真分析

本文利用Python工具完成了仿真實(shí)驗(yàn)。不失一般性，從Topology Zoo獲得真實(shí)的在線網(wǎng)絡(luò)拓?fù)溆糜赩M部署實(shí)驗(yàn)[19]，網(wǎng)絡(luò)拓?fù)鋱D結(jié)構(gòu)如表4所示。不同應(yīng)用服務(wù)的網(wǎng)絡(luò)帶寬需求設(shè)置為[800 kB,1600 kB]，并假定分布在整個(gè)邊緣網(wǎng)絡(luò)的移動(dòng)用戶(hù)數(shù)在500～3000。默認(rèn)設(shè)置3種應(yīng)用以及每種應(yīng)用部署4個(gè)VM和noel通信網(wǎng)絡(luò)進(jìn)行實(shí)驗(yàn)。同時(shí)，選擇文獻(xiàn)[20]中的RPA算法和文獻(xiàn)[21]中的DBC算法進(jìn)行性能比較。

表4 網(wǎng)絡(luò)拓?fù)浔?/p>

5.1 網(wǎng)絡(luò)數(shù)據(jù)流量

如圖2所示，各算法產(chǎn)生的平均數(shù)據(jù)流量隨著支持每種應(yīng)用的VM數(shù)增加而單調(diào)減少。這是因?yàn)殡S著邊緣網(wǎng)絡(luò)中支持同一應(yīng)用服務(wù)的VM數(shù)增多，即該應(yīng)用的AS數(shù)量增加，可以在本地進(jìn)行更多的請(qǐng)求處理，從而減少注入到邊緣網(wǎng)絡(luò)中的數(shù)據(jù)流量。同時(shí)，配置更多的VM可以減少邊緣網(wǎng)絡(luò)中移動(dòng)用戶(hù)與請(qǐng)求的目的AS之間的平均距離，導(dǎo)致邊緣網(wǎng)絡(luò)更小的數(shù)據(jù)流量產(chǎn)生。從圖2可以發(fā)現(xiàn)，DCBHPA在最小化平均數(shù)據(jù)流量方面相比其他算法可以獲得最優(yōu)性能，F(xiàn)HPA性能表現(xiàn)要優(yōu)于DBC，且二者都優(yōu)于RPA。

圖2 不同VM數(shù)對(duì)數(shù)據(jù)流量的影響

從圖3可以清楚地發(fā)現(xiàn)，在相同數(shù)量的移動(dòng)用戶(hù)情況下，與FHPA, DBC和RPA相比，DCBHPA總是可以獲得最小的平均數(shù)據(jù)流量。此外，在移動(dòng)用戶(hù)數(shù)較小的情況下，各算法性能差異較小，隨著用戶(hù)數(shù)不斷增加，所有4種算法提供服務(wù)產(chǎn)生的平均數(shù)據(jù)流量都會(huì)增加，其中RPA數(shù)據(jù)流量增加最為明顯。當(dāng)移動(dòng)用戶(hù)數(shù)為3000時(shí)，DCBHPA相比RPA可以減少25.8%的流量生成，反映了DCBHPA在大規(guī)模移動(dòng)邊緣網(wǎng)絡(luò)中為移動(dòng)用戶(hù)提供多種應(yīng)用服務(wù)進(jìn)行VM配置的優(yōu)勢(shì)。

圖3 移動(dòng)用戶(hù)數(shù)對(duì)數(shù)據(jù)流量的影響

圖4為不同網(wǎng)絡(luò)拓?fù)湎翭HPA, DCBHPA,DBC和RPA在邊緣網(wǎng)絡(luò)中最小化請(qǐng)求數(shù)據(jù)流量方面的性能比較結(jié)果，可以看到4種算法提出的服務(wù)配置方案產(chǎn)生的數(shù)據(jù)流量會(huì)隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而上升。在同一網(wǎng)絡(luò)下，DCBHPA在減小平均數(shù)據(jù)流量方面能獲得最佳性能表現(xiàn)。同時(shí)，圖5進(jìn)一步比較了FHPA, DCBHPA, DBC和RPA在應(yīng)用服務(wù)類(lèi)型不斷增多情況下的性能。實(shí)驗(yàn)結(jié)果表明，DCBHPA要優(yōu)于其他3種算法。與此同時(shí)，隨著不同應(yīng)用種類(lèi)的增加，各算法進(jìn)行VM配置提供服務(wù)所產(chǎn)生的數(shù)據(jù)流量都會(huì)增長(zhǎng)，且DCBHPA與FHPA, DBC和RPA的性能差異也更加明顯。此外，F(xiàn)HPA和DBC的性能表現(xiàn)基本相近，且二者都要優(yōu)于RPA。

圖4 網(wǎng)絡(luò)規(guī)模對(duì)數(shù)據(jù)流量的影響

圖5 應(yīng)用服務(wù)種類(lèi)數(shù)對(duì)數(shù)據(jù)流量的影響

接著，在支持每種應(yīng)用服務(wù)的VM數(shù)量不同且應(yīng)用服務(wù)種數(shù)不斷增加的前提下，進(jìn)一步分析了DCBHPA的性能表現(xiàn)。仿真結(jié)果如圖6所示，當(dāng)應(yīng)用服務(wù)數(shù)量增加時(shí)，對(duì)于支持各應(yīng)用服務(wù)的每組VM設(shè)置，DCBHPA獲得的平均數(shù)據(jù)流量呈指數(shù)增加。這是因?yàn)楦嗟膽?yīng)用服務(wù)種類(lèi)意味著邊緣網(wǎng)絡(luò)中將有更多的應(yīng)用請(qǐng)求需要提供服務(wù)，而這將導(dǎo)致AS可用服務(wù)資源的短缺，進(jìn)而增加系統(tǒng)的數(shù)據(jù)流量產(chǎn)生。同時(shí)，更多的服務(wù)請(qǐng)求將發(fā)送到云端獲得服務(wù)從而增加流量成本。從圖6可以看出，當(dāng)應(yīng)用服務(wù)種類(lèi)一定時(shí)，隨著支持每種應(yīng)用服務(wù)的VM增加，系統(tǒng)的平均數(shù)據(jù)流量將越少，這與圖2的實(shí)驗(yàn)結(jié)果相符。

圖6 不同應(yīng)用服務(wù)下VM部署取得的數(shù)據(jù)流量

5.2 服務(wù)配置總成本

一個(gè)好的部署方案不僅要保證較低的平均數(shù)據(jù)流量，而且要考慮邊緣網(wǎng)絡(luò)中提供服務(wù)配置的成本因素，因此，我們進(jìn)一步分析了DCBHPA提供服務(wù)時(shí)的總成本。如圖7所示，同一應(yīng)用提供更多的VM部署到邊緣網(wǎng)絡(luò)將減少流量成本，同時(shí)增加部署成本。通過(guò)將歸一化后的流量成本和部署成本相加，可以得到服務(wù)提供總成本。從圖中可以發(fā)現(xiàn)，當(dāng)VM部署數(shù)量不超過(guò)3時(shí)，總成本隨著VM配置數(shù)量的增加而下降，這是因?yàn)楫?dāng)VM的數(shù)量很小時(shí)，主導(dǎo)服務(wù)配置總成本的是數(shù)據(jù)流量成本，如圖2所述，因此總成本將隨著支持每種應(yīng)用服務(wù)的VM數(shù)量的增加而減少。當(dāng)部署VM的數(shù)量繼續(xù)增加時(shí)，VM的配置成本就會(huì)逐漸占據(jù)服務(wù)配置總成本的主導(dǎo)地位，導(dǎo)致當(dāng)支持每種應(yīng)用服務(wù)的VM數(shù)量超過(guò)3時(shí)，DCBHPA提供服務(wù)配置的總成本會(huì)隨著VM數(shù)的增加而增長(zhǎng)。

圖7 不同VM數(shù)對(duì)歸一化服務(wù)配置總成本的影響

如圖8所示，在應(yīng)用服務(wù)種類(lèi)不斷增加且支持每種應(yīng)用服務(wù)的VM數(shù)為4的情況下，對(duì)4種算法在應(yīng)用服務(wù)部署成本方面的性能進(jìn)行了比較。圖8表明，在最小化部署總成本方面，DCBHPA可以獲得最佳性能表現(xiàn)，且FHPA要優(yōu)于DBC，同時(shí)二者都要強(qiáng)于RPA。根據(jù)定義，VM部署成本為支持每種應(yīng)用的VM數(shù)和不同應(yīng)用種類(lèi)數(shù)的2次函數(shù)，因此部署成本將會(huì)隨著應(yīng)用數(shù)的增加而上升。圖5表明所有算法產(chǎn)生的數(shù)據(jù)流量會(huì)隨著應(yīng)用種類(lèi)數(shù)的擴(kuò)展而顯著增加，因此數(shù)據(jù)流量成本將隨著算法產(chǎn)生的數(shù)據(jù)流量增加而線性增長(zhǎng)，所以服務(wù)配置總成本將隨著應(yīng)用種類(lèi)數(shù)的增加而上升，這與圖8的結(jié)果一致。

圖8 應(yīng)用服務(wù)種類(lèi)數(shù)對(duì)歸一化服務(wù)配置總成本的影響

6 結(jié)束語(yǔ)

本文研究了移動(dòng)邊緣網(wǎng)絡(luò)中支持多種應(yīng)用服務(wù)的VM部署問(wèn)題，在提供多種應(yīng)用服務(wù)請(qǐng)求和MEC服務(wù)器處理能力受限約束下，為了最小化移動(dòng)邊緣網(wǎng)絡(luò)中的平均數(shù)據(jù)流量這一目標(biāo)，提出了兩種啟發(fā)式的部署算法，并利用廣泛的仿真實(shí)驗(yàn)來(lái)評(píng)估所提算法的性能。實(shí)驗(yàn)結(jié)果表明，DCBHPA算法性能在最大限度地減少平均數(shù)據(jù)流量方面，要優(yōu)于FHPA算法和基準(zhǔn)算法，能有效減少云邊通信流量，緩解潛在的網(wǎng)絡(luò)堵塞問(wèn)題。未來(lái)工作中，將進(jìn)一步深入研究多應(yīng)用服務(wù)下不同VM部署方案對(duì)用戶(hù)所需服務(wù)的平均請(qǐng)求響應(yīng)時(shí)間的影響規(guī)律。