陳卓，馮鋼，劉怡靜，周楊

（1.重慶理工大學計算機科學與工程學院，重慶 200433；2.電子科技大學通信抗干擾技術(shù)國家級重點實驗室，四川 成都 710077；3.奧本大學計算機科學與軟件工程學院，奧本 36849)

1 引言

移動邊緣計算（MEC,mobile edge computing）作為一種新的云服務(wù)模式，將傳統(tǒng)集中式部署和管理的云端資源分布式地部署至無線接入網(wǎng)（RAN，radio access network），使移動業(yè)務(wù)就近得到處理，從而獲得良好業(yè)務(wù)體驗[1-2]的同時降低了回程網(wǎng)絡(luò)的網(wǎng)絡(luò)負載[3]。將網(wǎng)絡(luò)功能虛擬化（NFV,network function virtualization）技術(shù)[4]應(yīng)用于MEC，運營商能將提供服務(wù)所需的IT 資源以虛擬網(wǎng)絡(luò)功能（VNF,virtual network function）的形式快速實例化，這進一步提升了MEC 的服務(wù)彈性。將服務(wù)節(jié)點成簇互聯(lián)形成集群化的MEC 網(wǎng)絡(luò)[5-7]能根據(jù)業(yè)務(wù)所需的網(wǎng)絡(luò)功能類型及業(yè)務(wù)量的變化情況動態(tài)調(diào)整VNF 的實例化規(guī)模，使業(yè)務(wù)流盡可能地在MEC 集群內(nèi)完成端到端的服務(wù)從而達成就近高效服務(wù)的目標。但集群化的MEC 的部署需要結(jié)合移動應(yīng)用的請求位置分散且對資源的需求動態(tài)變化等特點，同時還存在著單個MEC 集群的IT 資源受限、MEC 集群之間的網(wǎng)絡(luò)資源受限及多個VNF 需根據(jù)業(yè)務(wù)類型進行邏輯關(guān)聯(lián)等諸多限制，因此，在集群化MEC 網(wǎng)絡(luò)中合理部署VNF 和進行業(yè)務(wù)流傳輸路徑的優(yōu)選，為移動業(yè)務(wù)提供最優(yōu)的端到端服務(wù)時延頗具挑戰(zhàn)。目前，缺乏針對性的研究工作，亟需深入探討。

在集群化的MEC 網(wǎng)絡(luò)中，本文以為時延敏感類移動業(yè)務(wù)提供低時延服務(wù)為目標，基于開放Jackson 排隊網(wǎng)絡(luò)建立了業(yè)務(wù)流的端到端時延的數(shù)學優(yōu)化模型。通過將該優(yōu)化問題歸結(jié)為一個二維背包問題（2KP,twodimensional knapsack problem），從而證明其NP 性，進一步提出了一種集群化部署的MEC 網(wǎng)絡(luò)中通過合理部署VNF 及業(yè)務(wù)流路徑選擇的策略——iGSA（improvedgenetic and simulated annealing），該策略結(jié)合了遺傳算法和模擬退火算法分別在全局解和局部解的搜索能力的優(yōu)勢，通過對服務(wù)節(jié)點的提前映射機制避免了在節(jié)點部署時可能帶來的MEC 網(wǎng)絡(luò)擁塞，同時通過個體的約束性判斷和糾正遺傳的方法避免了局部最優(yōu)的出現(xiàn)。在多個網(wǎng)絡(luò)場景下的對比實驗表明，iGSA 策略均能在單個MEC 集群內(nèi)或多個MEC 集群之間，通過優(yōu)化改善VNF 部署和業(yè)務(wù)流的路徑選擇提供更低的業(yè)務(wù)流端到端時延，有效地改善了移動業(yè)務(wù)的體驗。

2 相關(guān)研究工作

在集群化部署的MEC 網(wǎng)絡(luò)中提供低時延服務(wù)所面臨的挑戰(zhàn)及具有智能特征的算法在大規(guī)模系統(tǒng)中快速求得優(yōu)化解方面所具有的獨特優(yōu)勢形成了本文研究方法的依據(jù)。與本文相關(guān)的工作可按照MEC網(wǎng)絡(luò)的部署場景和VNF 的部署方法進行分類討論。

在MEC 網(wǎng)絡(luò)場景類似的工作介紹如下[5-7]。文獻[5-6]將NFV 引入邊緣節(jié)點并建立起虛擬化MEC網(wǎng)絡(luò)架構(gòu)，通過構(gòu)建服務(wù)功能鏈（SFC,service function chain）為移動邊緣應(yīng)用提供就近的IT 彈性服務(wù)。文獻[5]側(cè)重于通過SFC 實現(xiàn)緩存服務(wù)改善移動業(yè)務(wù)的體驗，而文獻[6]則著重從主動故障恢復機制設(shè)計方面，探討提升虛擬化MEC 網(wǎng)絡(luò)的系統(tǒng)可靠性問題。文獻[5-7]在集群化部署的MEC 網(wǎng)絡(luò)場景下，力圖通過計算最優(yōu)的MEC 集群數(shù)量來提高業(yè)務(wù)流的服務(wù)質(zhì)量。但局限在獨立的MEC 集群中開展研究，缺乏對更一般化的MEC 部署場景中的相關(guān)問題進行探討。另外，和中心化的云服務(wù)相比較，MEC 最顯著的優(yōu)勢是能夠為用戶就近提供低時延服務(wù)，因此，本文從MEC 的主要功能特性出發(fā)，研究并提出改善集群化部署的MEC 網(wǎng)絡(luò)中端到端服務(wù)時延的策略。針對VNF 的優(yōu)化部署方法，相關(guān)工作參考文獻[8-12]。其中文獻[8-10]針對不同類型的業(yè)務(wù)請求，分別從效用最大化、能耗最低及能夠容納的業(yè)務(wù)流最大化等角度進行了研究，并提出了將預(yù)先定義了次序的多個VNF 進行鏈接部署，建立起SFC 的策略。文獻[11]通過優(yōu)化多個微服務(wù)提供服務(wù)的時序，以達到改善移動應(yīng)用服務(wù)體驗的目的。文獻[12]則借助強化學習方法研究了VNF 部署過程中虛擬節(jié)點到物理節(jié)點的優(yōu)化映射和實例化的問題。上述研究工作[8-12]的網(wǎng)絡(luò)場景是IT 資源（節(jié)點計算資源、節(jié)點存儲資源和網(wǎng)絡(luò)帶寬）相對充裕的數(shù)據(jù)中心網(wǎng)絡(luò)或移動核心網(wǎng)絡(luò)，其關(guān)注的重點集中在有效提升虛擬化的IT 資源使用效率問題或提高整個系統(tǒng)服務(wù)能力的問題上，所采用的方法通常是將多個物理指標轉(zhuǎn)化為統(tǒng)一的系統(tǒng)開銷和系統(tǒng)收益，并建立優(yōu)化模型加以分析。與之相比，本文所研究的處于網(wǎng)絡(luò)邊緣的MEC 節(jié)點IT 資源相對稀缺，網(wǎng)絡(luò)系統(tǒng)在提供低時延端到端服務(wù)的同時，合理分配IT 資源顯得尤其重要。而這涉及在MEC 集群內(nèi)和MEC 集群之間的VNF 優(yōu)化部署及業(yè)務(wù)流虛擬路徑的合理選擇。

與已有工作相比較，本文的創(chuàng)新性主要體現(xiàn)在以下2 個方面。1)在多個MEC 集群共存的邊緣網(wǎng)絡(luò)場景下，面向移動業(yè)務(wù)請求位置分散及對IT 資源需求動態(tài)變化的特點，通過排隊網(wǎng)絡(luò)模型對端到端的服務(wù)時延進行了形式化分析并建立最優(yōu)化模型。2)分析求證了1)中優(yōu)化問題的NP 性，并提出了一種易于部署的快速求解策略——iGSA。該策略通過將遺傳算法和模擬退化算法合理的結(jié)合，在進行全局最優(yōu)解搜索的同時有效地提高了求解效率并降低了運行時間，這對在大規(guī)模MEC 網(wǎng)絡(luò)中進行快速的VNF 部署決策具有積極的借鑒意義。

3 模型化分析

3.1 網(wǎng)絡(luò)場景描述及形式化定義

本文考慮集群化部署的MEC 網(wǎng)絡(luò)場景。如圖1所示，MEC 集群化部署在移動通信網(wǎng)絡(luò)邊緣且和一個或多個eNode B 連接[6]，MEC 集群通過PDN-GW（packet data network gateway）和云化的5G 移動核心網(wǎng)連接。一個MEC 集群可以包括若干個虛擬化MEC 節(jié)點。另外，MEC 集群之間通過網(wǎng)絡(luò)連接，具備多個MEC 集群之間協(xié)作的能力。與云化的數(shù)據(jù)中心網(wǎng)絡(luò)或移動核心網(wǎng)中的IT 資源可近乎認為無限不同的是，MEC 集群中節(jié)點數(shù)量和能提供的IT 資源都是受限的。MEC 集群優(yōu)先在本集群內(nèi)完成對請求業(yè)務(wù)的服務(wù)，當資源無法滿足時，則利用其他MEC 集群的可用IT 資源構(gòu)建新的VNF 完成服務(wù)。整個MEC 集群的資源統(tǒng)計和分配由位于移動核心網(wǎng)中的網(wǎng)絡(luò)控制器實現(xiàn)[13]。集群化的MEC部署方式，能夠跨越多個eNode B 和網(wǎng)絡(luò)區(qū)域，為時延敏感類移動業(yè)務(wù)提供端到端的低時延服務(wù)，這對智能車/無人駕駛這類時延敏感類應(yīng)用尤其重要。

將一個集群化部署的 MEC 網(wǎng)絡(luò)定義為G={G1,…,Gg}，其中g(shù)為集群的數(shù)量，Gn表示第n個MEC 集群。定義一個無向圖Gn=（Vn,En），其中Vn和En分別為MEC 集群Gn中的邊緣節(jié)點和集群內(nèi)網(wǎng)絡(luò)鏈路。(u,w)表示2 個邊緣節(jié)點u和w之間的鏈路，此外，u和w可以屬于同一個或不同的集群MEC。lu,w表示鏈路(u,w)的可用網(wǎng)絡(luò)帶寬資源，邊緣節(jié)點u和w的距離表示為Du,w。nv(v∈V)表示用于構(gòu)建VNF 的通用服務(wù)節(jié)點（即虛擬機）數(shù)量。Mn表示在MEC 集群Gn中由邊緣節(jié)點經(jīng)虛擬化后的通用服務(wù)節(jié)點集合，對于MEC 集群Gn中某個通用服務(wù)節(jié)點m(m∈Mn)，當前可用計算資源表示為。集群化部署的MEC 網(wǎng)絡(luò)為各類移動業(yè)務(wù)提供服務(wù)，以H表示MEC 網(wǎng)絡(luò)在時間T內(nèi)收到h個移動服務(wù)請求，H={d1,d2,…,dh}。對于服務(wù)請求di(di∈H)的入口節(jié)點和出口節(jié)點分別用Ii和Ei表示，Ii到Ei的路徑表示為Pi，di的數(shù)據(jù)率為Ri。根據(jù)不同移動應(yīng)用業(yè)務(wù)的需求，多個VNF 按照某種次序從邏輯上連接成一種串行結(jié)構(gòu)或并行結(jié)構(gòu)的SFC[13]，其中采用并行連接有助在MEC 網(wǎng)絡(luò)中提高時延敏感類移動業(yè)務(wù)的服務(wù)效率。如圖2 所示，為服務(wù)請求di提供服務(wù)的SFC 表示為Si={Si,1,Si,2,Si,3,…,Si,K}，其長度表示為|Si|，其中Si,j(1≤j≤K)表示SFC 上的某一個VNF 或經(jīng)并行連接后為di提供服務(wù)的多個VNF 組成的集合，例如圖 2 中的。假設(shè)在時間T內(nèi)在MEC 網(wǎng)絡(luò)中能建立不同類型的VNF，用集合F表示。對于某一類型的 VNFf(f∈F)能最多被實例化建立|Nf|個，定義fk為建立類型為VNFf(f∈F)的第k個實例，其計算資源占用量表示為表示fk和之間的通信所占用網(wǎng)絡(luò)帶寬，?f,f'∈F，1≤k≤|Nfk|，1≤k' ≤|Nf'|。定義矩陣B為G中各條鏈路的帶寬占用量。定義I(Si,j)為di提供服務(wù)的SFC 的路徑Pi中對應(yīng)的通用服務(wù)節(jié)點的索引。對于di的業(yè)務(wù)流按指定的順序遍歷多個 VNF，即I(Si,j)≤I(Si,j')，?Si,j,Si,j'∈Si，j＜j'。

圖1 集群化部署的MEC 網(wǎng)絡(luò)框架

圖2 MEC 集群中串行或并行邏輯連接的多個VNF

3.2 服務(wù)時延模型

移動業(yè)務(wù)通過集群化MEC 網(wǎng)絡(luò)實現(xiàn)端到端服務(wù)的過程中產(chǎn)生的時延包括業(yè)務(wù)流數(shù)據(jù)分組在VNF 處等待處理的排隊時延、業(yè)務(wù)流數(shù)據(jù)分組接受VNF 的處理時延及業(yè)務(wù)流數(shù)據(jù)分組在MEC 集群內(nèi)和MEC 集群之間傳輸產(chǎn)生的時延。特別說明的是，對于VNF 在通用服務(wù)節(jié)點之上的運行部署可能帶來不同影響程度的處理時延，在評估集群化部署的MEC 網(wǎng)絡(luò)中端到端服務(wù)時延時必須要將其納入進行考慮[14-15]。

首先業(yè)務(wù)流從入口節(jié)點到出口節(jié)點需經(jīng)過一條SFC 中的多個VNF 進行處理，每個VNF 在處理業(yè)務(wù)流時將產(chǎn)生處理時延。本文基于M/M/1/c 類型的Jackson 排隊網(wǎng)絡(luò)[15]對業(yè)務(wù)流在MEC 網(wǎng)絡(luò)中的處理時延進行建模，將一個MEC 網(wǎng)絡(luò)中的VNF 視作服務(wù)節(jié)點，假設(shè)業(yè)務(wù)數(shù)據(jù)分組到達該VNF 的過程是一個泊松過程。對于VNFfk，定義λf,k和uf,k分別表示其平均到達率和平均服務(wù)率，且。為保證VNF 服務(wù)的系統(tǒng)穩(wěn)定性，有ρf,k＜ 1。對于MEC 網(wǎng)絡(luò)中的某個VNF，輸入流量來自入口節(jié)點直接導入，也可能來自同集群或鄰居集群的VNF流量輸出，因此，定義Pjw表示業(yè)務(wù)流在VNFj完成處理并輸出至VNFw的概率，定義表示從MEC入口節(jié)點到VNFw的流量。VNFw的輸入流量速率可表示為

則在VNFfk的緩存隊列中的數(shù)據(jù)分組平均數(shù)可表示為

V NFfk可運行部署在節(jié)點w之上，則fk的服務(wù)率導入至物理節(jié)點w可表示為，其中R(w)由對業(yè)務(wù)流的傳輸能力決定，更詳細的計算方法可參考文獻[15]。由Little 定理[16]可得到VNFfk的處理時延，則有

其中，λi表示第i條業(yè)務(wù)流的速率，表示di需要fk提供服務(wù)，則表示di不需要fk提供服務(wù)。則對于移動業(yè)務(wù)請求di的處理時延可表示為

基于M/M/1/c 排隊網(wǎng)絡(luò)進行模型化分析，單個VNF 的平均排隊時延可表示為

其中，qj表示當有j個用戶到達系統(tǒng)時的平滑概率[16]，則業(yè)務(wù)請求的排隊時延可表示為

本文定義了一個由二元決策變量組成的矩陣A，矩陣中的任意元素為，且有表示業(yè)務(wù)流fk經(jīng)由MEC 集群n中的通用服務(wù)節(jié)點u進行處理，表示業(yè)務(wù)流fk沒有流經(jīng)MEC 集群n中的通用服務(wù)節(jié)點u。另外，定義二元決策變量表示映射到底層網(wǎng)絡(luò)鏈路lu,w，表示沒有映射到底層網(wǎng)絡(luò)鏈路lu,w。

業(yè)務(wù)請求的傳播時延可表示為

其中，p表示信號在物理鏈路上的傳輸速率，Du,w表示物理鏈路的長度，E表示整個MEC 集群內(nèi)的網(wǎng)絡(luò)鏈路組成的整體集合。

在集群化部署的MEC 收到多個業(yè)務(wù)請求的情況下，對于存在各種資源限制的集群化部署MEC 網(wǎng)絡(luò)中，本文通過VNF 的部署和業(yè)務(wù)流路徑的選擇優(yōu)化業(yè)務(wù)流端到端服務(wù)時延。該最優(yōu)化模型可表示為

該優(yōu)化模型中，式(9)表示同一個MEC 集群中的2個通用服務(wù)節(jié)點間的鏈路帶寬資源限制。式(10)表示MEC 集群之間的鏈路帶寬資源限制。式(11)表示MEC 集群n中的節(jié)點u上當前已部署的一個或多個VNF 占用的計算資源不能超過其計算資源總量。式(12)表示MEC 網(wǎng)絡(luò)中除入口節(jié)點和出口節(jié)點之外所有活動節(jié)點需要滿足流量守恒。式(13)和式(14)表示服務(wù)請求僅從一個入口節(jié)點進入MEC網(wǎng)絡(luò)且僅從一個出口節(jié)點離開集群化部署的MEC網(wǎng)絡(luò)。式(15)要求一條SFC 業(yè)務(wù)流需經(jīng)過其預(yù)定義的所有VNF。式(16)表示業(yè)務(wù)請求的時延約束。式(17)和式(18)分別表示需要具備可行的鏈路和節(jié)點映射。

3.3 NP 性討論

在運籌學領(lǐng)域，多維背包問題（MKP,multidimensional knapsack problem）是一個經(jīng)典的優(yōu)化問題，其求解目標是在滿足各項資源約束的前提下,從候選對象集中找出可以使目標價值達到最大（或最?。┑膶ο笞蛹?。該問題已被證明是一種 NP-Hard[17]問題。

在3.2 節(jié)建立的最優(yōu)化模型中，集群化的MEC網(wǎng)絡(luò)同時為多條業(yè)務(wù)流提供端到端服務(wù)，并為業(yè)務(wù)流服務(wù)的多個VNF 需求同時占用計算處理資源和轉(zhuǎn)發(fā)業(yè)務(wù)流的鏈路帶寬資源。由于VNF 部署于MEC 網(wǎng)絡(luò)中的通用服務(wù)節(jié)點之上，因此這2 種資源的占用分別不能超過通用服務(wù)節(jié)點的可用計算資源和通用服務(wù)節(jié)點之間的物理鏈路帶寬（包括MEC集群內(nèi)和MEC 集群間的鏈路帶寬）。假設(shè)MEC 集群中能為第i條業(yè)務(wù)流提供服務(wù)的通用服務(wù)節(jié)點為n個，r1,j表示為業(yè)務(wù)流提供服務(wù)需占用第j個通用服務(wù)節(jié)點的計算資源，r2,m和r3,m分別表示為業(yè)務(wù)流提供服務(wù)第j個通用服務(wù)節(jié)點需占用的MEC 集群內(nèi)和MEC 集群間的帶寬資源。定義xj表示通用服務(wù)節(jié)點xj是否被選中用于部署為業(yè)務(wù)流提供服務(wù)的VNF。由于業(yè)務(wù)流的端到端服務(wù)需經(jīng)過多個部署了VNF 的通用服務(wù)節(jié)點，因此定義pj表示當業(yè)務(wù)流通過通用服務(wù)節(jié)點xj產(chǎn)生的時延，則式(8)所描述的最優(yōu)化問題可簡化為，滿足約束條件I：和約束條件II表示通用服務(wù)節(jié)點被選中，xj=1表示通用服務(wù)節(jié)點未被選中。若進一步將服務(wù)業(yè)務(wù)流對于MEC集群內(nèi)和MEC集群間的鏈路帶寬資源占用視作一類資源，則式(8)簡化后的最優(yōu)化問題是一個2KP。根據(jù)MKP 問題的NP 性，因此本文所描述的在集群化部署的MEC 網(wǎng)絡(luò)中的業(yè)務(wù)流端到端時延最小化問題也是一個NP-Hard 問題。

4 基于遺傳模擬退火算法的部署策略

第3 節(jié)所定義的問題難以在多項式時間復雜度內(nèi)找到全局最優(yōu)解。而當問題的規(guī)模較大時，若采用貪心法或者枚舉法等精確算法的運行時間代價較高，很難在集群化MEC 網(wǎng)絡(luò)中進行實際部署。因此需要采用相應(yīng)的近似算法對其進行求解。而以模擬退火算法[18]和遺傳算法[19]為代表的智能算法近年在多個領(lǐng)域得到了廣泛有效的應(yīng)用。其中，模擬退火算法模擬固體物質(zhì)退火過程的熱平衡問題與隨機搜索尋優(yōu)問題的相似性來達到尋找全局最優(yōu)或近似全局最優(yōu)的目的。若在模擬退火算法的運行過程中融入遺傳算法，稱為遺傳模擬退火算法[20-21]。

本文所研究的問題從本質(zhì)上是根據(jù)業(yè)務(wù)流類型和性能約束條件，按照某種預(yù)定義順序?qū)⒍鄠€VNF 映射到多個MEC 通用服務(wù)節(jié)點之上，實現(xiàn)時延最優(yōu)的離散優(yōu)化問題。在求解該優(yōu)化問題時，需要權(quán)衡好求解方法的執(zhí)行效率和求解質(zhì)量。本文所提的iGSA 策略做了2 個規(guī)定：1)依據(jù)業(yè)務(wù)請求到達MEC 網(wǎng)絡(luò)的時間先后順序進行分析，如果多個業(yè)務(wù)請求同時到達，則針對這些請求所形成的業(yè)務(wù)流的總時延為優(yōu)化目標；2)當一個MEC 群集中已實例化的VNF 資源不足以滿足服務(wù)需求時，則采用在當前MEC 集群中新開啟通用服務(wù)節(jié)點并實例化VNF 或?qū)I(yè)務(wù)流引導至相鄰MEC 集群。iGSA策略設(shè)計時在2 個方面做了性能改進，一方面在K最短路徑的選擇和業(yè)務(wù)流的引導之前進行在通用服務(wù)節(jié)點的映射（即虛擬機的映射），以避免網(wǎng)絡(luò)擁塞；另一方面對不符合約束的個體加以糾正，然后將糾正的個體放入下一代個體中，以避免陷入局部最優(yōu)。iGSA 策略的主要步驟包括編碼、選擇復制、交叉、變異和可行性檢測。

4.1 編碼

設(shè)第k代種群中的個體數(shù)目為N，這里每個個體即為nv×mf染色體矩陣，mf表示需要使用多少個VNF，nv表示當前已經(jīng)開啟的通用服務(wù)節(jié)點數(shù)量。矩陣Qk={A1,A2,…,Ak}表示個體，第k代種群的第r個個體表示為

4.2 選擇復制

其中，tk表示狀態(tài)k下的溫度，而初始的溫度值定義為，Z為一個常量，，其中。

4.3 交叉

本文使用多行矩陣雜交，例如使Qk中的和進行配對，并且將相對應(yīng)的行以概率Pc=0.6進行互換。種群中2 個染色體之間的交叉過程如下

4.4 變異和可行性檢測

本文假設(shè)突變的概率Pm=0.01。對于任何個體，需要判斷是否發(fā)生了突變。如果發(fā)生了突變，就需要對該個體進行可行性檢測。

在交叉和變異操作之后，需要判斷這些新個體是否滿足資源限制條件。對于一個給定的染色體，可以得到VNF 映射策略，從中可進一步獲得決策變量的值，從而判斷是否滿足通用服務(wù)節(jié)點映射的約束。如果不滿足，則節(jié)點不滿足計算資源限制，并且將對應(yīng)于這些節(jié)點的行元素從1 隨機校正為0，直到滿足節(jié)點計算約束。通過VNF 的映射可以獲得相應(yīng)的最優(yōu)網(wǎng)絡(luò)鏈路映射，然后為每條業(yè)務(wù)流在K條最短路徑中選擇合適的路徑匹配，在滿足鏈路和時延約束的同時最小化適應(yīng)度函數(shù)。以這種方式，在第一階段中將糾正的個體和鏈接映射策略重復至下一代。在集群化部署的MEC 網(wǎng)絡(luò)中，iGSA策略的時間復雜度為O(n2)，其中n表示通用服務(wù)節(jié)點的數(shù)量。對于通用服務(wù)節(jié)點規(guī)模較小的MEC 網(wǎng)絡(luò)而言，該算法的計算復雜度在可接受的程度內(nèi)。iGSA 策略的偽碼如算法1 所示。

算法1基于遺傳模擬退火的啟發(fā)式策略——iGSA

輸入集群化部署的MEC 網(wǎng)絡(luò)通用服務(wù)節(jié)點和鏈路信息，各條鏈路的帶寬占用量矩陣B，某個MEC 集群Gn中某個通用服務(wù)節(jié)點m（m∈Mn）當前可用計算資源，VNF 的類型集合F，SFC 集合（包括SFC 長度、SFC 類型和Ri）。

輸出SFC 的部署策略Mbest和Bbest，以及對于在[t,t+T]時間間隔內(nèi)到達的業(yè)務(wù)請求的端到端時延預(yù)估值tavg

5 實驗與性能評估

5.1 實驗方法及仿真參數(shù)設(shè)置

本文通過 Matlab 建立數(shù)值仿真環(huán)境評估iGSA 策略的性能。實驗基于Congent[22]生成MEC集群網(wǎng)絡(luò)的拓撲。實驗生成了2 種類型的網(wǎng)絡(luò)（網(wǎng)絡(luò)I 和網(wǎng)絡(luò)II）以評估算法在不同MEC 集群網(wǎng)絡(luò)規(guī)模下的表現(xiàn)，其中網(wǎng)絡(luò)I 包括3 個MEC 集群，部署30 個通用服務(wù)節(jié)點、55 條集群內(nèi)和集群間的鏈路，集群內(nèi)的帶寬資源參數(shù)在10～200 Mbit/s 內(nèi)隨機選取，集群間的帶寬資源參數(shù)在10～100 Mbit/s內(nèi)隨機選取。網(wǎng)絡(luò)II 的MEC 集群數(shù)量為10 個，部署200 個通用服務(wù)節(jié)點、355 條集群內(nèi)和集群間的網(wǎng)絡(luò)鏈接，集群內(nèi)的帶寬資源參數(shù)在1～10 Gbit/s內(nèi)隨機選取，集群間的帶寬資源參數(shù)在200 Mbit/s～1 Gbit/s 內(nèi)隨機選取。2 種網(wǎng)絡(luò)中的服務(wù)功能鏈SFC 的平均長度為4。SFC 的類型、MEC 網(wǎng)絡(luò)中通用服務(wù)節(jié)點的計算資源、不同類型VNF 所需計算資源和VNF 之間的關(guān)聯(lián)關(guān)系等參數(shù)從各自的區(qū)間內(nèi)隨機選擇。與文獻[23]類似，集群化部署的MEC 網(wǎng)絡(luò)節(jié)點之間的傳播時延與其鏈路距離成比例，通過乘以在區(qū)間[0.8,1.5]中取得的隨機數(shù)引入適當?shù)碾S機性。本文參考文獻[24]，服務(wù)請求所需的流量服從冪率分布，設(shè)置α=2.1產(chǎn)生了xmin=10 Mbit/s 的服務(wù)請求。隨機地在MEC集群中選擇一個服務(wù)請求的入口網(wǎng)元和出口網(wǎng)元以模擬不同類型的移動業(yè)務(wù)。另外，突變概率為0.01，MEC 群集之間和內(nèi)部的交叉概率分別設(shè)置為Pc=0.6 和Pc=0.8，溫度變化系數(shù)ξ=0.45。

實驗中使用以下幾種典型策略進行對比以客觀評估 iGSA 策略的性能。1)AH 策略（AH strategy）[25]，該算法在一個MEC 網(wǎng)絡(luò)中優(yōu)先選擇具有最多剩余資源的可用節(jié)點部署VNF 和建立SFC。和iGSA 策略相比較，AH 策略減少了VNF的處理時延，但沒有考慮處理時延和傳播時延的整體優(yōu)化，特別沒有考慮多個MEC 集群共存的一般化場景。2)貪心策略（greedy strategy）：集群化部署的MEC 網(wǎng)絡(luò)逐個處理時間T內(nèi)的服務(wù)請求，并依次最小化每個服務(wù)請求的端到端時延。3)隨機策略（random strategy）在時間T內(nèi)收到i個服務(wù)請求，該策略在滿足計算資源限制、鏈路帶寬資源限制和服務(wù)請求的時延限制的通用服務(wù)節(jié)點用于部署VNF 和建立SFC。

5.2 實驗結(jié)果與分析

本文首先探討在同一時間段內(nèi)，到達集群化部署MEC 網(wǎng)絡(luò)中的服務(wù)請求數(shù)與平均端到端服務(wù)時延之間的關(guān)系。圖3 顯示了在網(wǎng)絡(luò)I 場景下，獲得服務(wù)的平均時延與服務(wù)請求數(shù)量之間的關(guān)系。從圖3 可以看到，服務(wù)的平均時延隨著服務(wù)請求的數(shù)量增加而增加，這主要是因為隨著業(yè)務(wù)請求的增加，當一個MEC 集群中的計算和網(wǎng)絡(luò)資源不足以開啟部署新的VNF 時，業(yè)務(wù)流將被引導至相鄰MEC 集群，而跨MEC 的帶寬資源受限從而導致服務(wù)的整體時延增加。和典型的AH 策略、貪心策略和隨機策略相比，基于遺傳模擬退火算法的iGSA策略在降低服務(wù)時延方面有更好的表現(xiàn)。同時由于貪心策略考慮了多個MEC 集群共存的情況，優(yōu)先在同一個MEC 集群中選擇通用服務(wù)節(jié)點以降低服務(wù)時延，因此其表現(xiàn)優(yōu)于AH 策略。在網(wǎng)絡(luò)I 場景中，相較于其他策略，iGSA 策略都具有穩(wěn)定的性能表現(xiàn)，分別比貪心策略、AH 策略及隨機策略有平均10.62%、23.94%和71.36%的端到端服務(wù)時延優(yōu)勢。

圖3 不同服務(wù)請求量下的服務(wù)時延對比(網(wǎng)絡(luò)I)

為業(yè)務(wù)請求提供持續(xù)高質(zhì)量的服務(wù)，多個不同類型的VNF 從邏輯上鏈接成SFC 或服務(wù)功能圖（SFG,service function graph），本文還深入探討了SFC 的長度與服務(wù)請求的平均時延之間的關(guān)系。從圖4 中可以觀察到，服務(wù)請求的平均時延隨著SFC 長度（即一條SFC 鏈上的VNF 的個數(shù)）的增加而同步增加，其主要原因是SFC 越長，表示業(yè)務(wù)流流經(jīng)的VNF 實例也越多，則在網(wǎng)絡(luò)資源固定的情況下需要更多的計算、網(wǎng)絡(luò)帶寬及存儲資源，從而導致可用的節(jié)點和鏈路變得更稀缺。本文在3.1 節(jié)圖2 中所描述的并行邏輯連接的多個VNF 構(gòu)成了SFG，該邏輯結(jié)構(gòu)是一種特殊的SFC。和SFC 的主要區(qū)別在于，SFG 通過分析業(yè)務(wù)流經(jīng)過的多個VNF 之間的依賴關(guān)系，引入VNF 的并行化執(zhí)行思想實現(xiàn)對業(yè)務(wù)流的更高效服務(wù)，基于SFG 模式的業(yè)務(wù)流服務(wù)，能顯著降低業(yè)務(wù)的端到端時延[26]。實驗場景中設(shè)置了部分服務(wù)請求不能以并行化只能以串行化SFC 的方式提供服務(wù)，SFC 和SFG 的總數(shù)量為100。在一個SFC 或一個SFG 中，業(yè)務(wù)流需經(jīng)過8 個VNF 的處理才能完成端到端的服務(wù)。該實驗通過增加SFG 的數(shù)量來評估對于服務(wù)請求的端到端平均時延的影響。從圖5中可以發(fā)現(xiàn)，在SFG 的數(shù)量從10 增到100 的過程中，即SFG 的占比增加，而SFC 的占比下降，服務(wù)請求的平均時延減少。其主要原因是當SFG 占比增加時，越來越多的VNF 都在并行處理業(yè)務(wù)流數(shù)據(jù)，完成端到端的服務(wù)時延減少。該實驗結(jié)論表明，本文所提的iGSA 策略能很好地適應(yīng)采用不同的 VNF 邏輯鏈接關(guān)系建立的MEC 應(yīng)用。

圖4 不同SFC 長度下的服務(wù)時延對比(網(wǎng)絡(luò)II)

圖5 不同SFG 下的服務(wù)時延對比(網(wǎng)絡(luò)II)

將NFV 技術(shù)引入MEC 網(wǎng)絡(luò)后，MEC 能夠根據(jù)服務(wù)的請求量動態(tài)調(diào)整通用服務(wù)節(jié)點的數(shù)量以實現(xiàn)在服務(wù)質(zhì)量和資源開銷之間的平衡。本文評估了當MEC 集群中根據(jù)業(yè)務(wù)請求開啟不同規(guī)模的通用服務(wù)節(jié)點時，不同算法的端到端服務(wù)時延對比，并比較了在網(wǎng)絡(luò)II 的10 個MEC 群集中從開啟80 個通用服務(wù)節(jié)點到260 個通用服務(wù)節(jié)點時端到端的平均服務(wù)時延，從圖6 可以觀察到，平均時延隨著MEC 集群中開啟的通用服務(wù)節(jié)點數(shù)量的增加而下降，其原因主要是隨著每個MEC集群開啟的通用服務(wù)節(jié)點數(shù)量的增加，實例化的VNF 數(shù)量也同步增加，服務(wù)請求更多地可以在入口網(wǎng)元所在的MEC 集群中得到處理，而不需要導入至其他相鄰的MEC 集群。進一步地可以看到，在一個MEC 集群中開啟相同的通用服務(wù)節(jié)點的情況下，得益于iGSA 策略能夠在多個MEC集群中進行跨區(qū)域的路徑選擇，該策略總能提供更低的端到端服務(wù)時延。相對于集中式部署的云數(shù)據(jù)中心或云化的移動核心網(wǎng)，MEC 的計算及網(wǎng)絡(luò)等IT 資源都相對受限，因此本文繼續(xù)對比了IT資源受限情況下不同的策略所提供的端到端服務(wù)時延，包括通用服務(wù)節(jié)點的計算資源以及MEC集群之間的平均鏈路帶寬受限。

圖6 MEC 集群中不同的通用服務(wù)節(jié)點規(guī)模下的服務(wù)時延對比(網(wǎng)絡(luò)II)

圖7 和圖8 分別對比了MEC 集群之間的帶寬資源和MEC 集群計算資源處于不同稀缺情況下的業(yè)務(wù)流端到端時延。MEC 集群之間的帶寬資源從200 Mbit/s 增加到1 Gbit/s，服務(wù)請求數(shù)為100 個。當IT 資源增加時，服務(wù)請求的平均服務(wù)時延逐漸降低。這是因為計算資源增加后更多的VNF 可以在本地MEC 集群中的通用服務(wù)節(jié)點生成。同時，由于MEC 集群之間的鏈路帶寬增加，可以將業(yè)務(wù)流所需的更多的計算和網(wǎng)絡(luò)資源引導至相鄰MEC 集群?？梢钥吹剑S著MEC 集群的計算資源的逐漸增加，更多的服務(wù)請求將在本地集群中得到處理，服務(wù)的端到端路徑將有效縮短。在圖7和圖8 中，當MEC 的計算資源處于不同稀缺程度時，相對于其他策略，iGSA 均能取得更好的性能。在不同的帶寬資源稀缺程度下，iGSA 策略分別比貪心策略和AH 策略平均有13.32%和48.76%的性能優(yōu)勢，在不同計算資源稀缺程度下，iGSA策略則分別比貪心策略和AH 策略平均有22.72%和35.29%的性能優(yōu)勢。

上述實驗對比中，通過設(shè)置不同的參數(shù)，包括服務(wù)請求數(shù)量、MEC 網(wǎng)絡(luò)中服務(wù)節(jié)點規(guī)模、MEC集群數(shù)量及VNF 之間的邏輯連接關(guān)系等，詳細對比了iGSA 策略和幾個相關(guān)策略性能。實驗結(jié)果表明，iGSA 策略通過將模擬退火和遺傳算法相結(jié)合，在保證算法效率的同時獲得了更優(yōu)的求解方案，使時延敏感類移動業(yè)務(wù)獲得更好體驗。實驗結(jié)論有力地支撐了本文通過改進遺傳模擬退火算法解決VNF在MEC 網(wǎng)絡(luò)中的優(yōu)化部署問題上所做的創(chuàng)新。

圖7 不同MEC 集群間的網(wǎng)絡(luò)帶寬資源下服務(wù)時延對比(網(wǎng)絡(luò)II)

圖8 不同MEC 集群計算資源下的服務(wù)時延對比（網(wǎng)絡(luò)II）

6 結(jié)束語

本文研究了多集群MEC 網(wǎng)絡(luò)中的VNF 的優(yōu)化部署策略，首先將業(yè)務(wù)流經(jīng)過部署在MEC 通用服務(wù)節(jié)點的多個 VNF 的過程形式化為一個開放Jackon 排隊網(wǎng)絡(luò)，并進一步得到業(yè)務(wù)流的服務(wù)時延最優(yōu)化模型。在證明了該優(yōu)化問題是一個NP-Hard問題的基礎(chǔ)上，通過將遺傳算法和模擬退火算法結(jié)合，提出一種MEC 集群網(wǎng)絡(luò)中基于遺傳模擬退火算法的VNF 部署及路徑優(yōu)選策略。通過在不同參數(shù)條件下，將所提策略與類似策略進行了詳細對比，結(jié)果表明所提出策略能為移動業(yè)務(wù)提供更低的端到端服務(wù)時延，有效改善業(yè)務(wù)的體驗。本文所提出的算法及結(jié)論能為優(yōu)化MEC 的資源部署提供有借鑒意義的參考。在將來的工作中，將把本文的場景繼續(xù)擴展到融合網(wǎng)絡(luò)切片的MEC 網(wǎng)絡(luò)，研究MEC 節(jié)點和網(wǎng)絡(luò)切片中的虛擬資源部署和聯(lián)合調(diào)度。