MEC 中基于改進(jìn)遺傳模擬退火算法的虛擬網(wǎng)絡(luò)功能部署策略

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

（1.重慶理工大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，重慶 200433；2.電子科技大學(xué)通信抗干擾技術(shù)國(guó)家級(jí)重點(diǎn)實(shí)驗(yàn)室，四川 成都 710077；3.奧本大學(xué)計(jì)算機(jī)科學(xué)與軟件工程學(xué)院，奧本 36849)

1 引言

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

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

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

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

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

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

3 模型化分析

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

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

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

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

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

3.2 服務(wù)時(shí)延模型

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

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

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

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

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

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

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

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

業(yè)務(wù)請(qǐng)求的傳播時(shí)延可表示為

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

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

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

3.3 NP 性討論

在運(yùn)籌學(xué)領(lǐng)域，多維背包問(wèn)題（MKP,multidimensional knapsack problem）是一個(gè)經(jīng)典的優(yōu)化問(wèn)題，其求解目標(biāo)是在滿足各項(xiàng)資源約束的前提下,從候選對(duì)象集中找出可以使目標(biāo)價(jià)值達(dá)到最大（或最小）的對(duì)象子集。該問(wèn)題已被證明是一種 NP-Hard[17]問(wèn)題。

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

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

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

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

4.1 編碼

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

4.2 選擇復(fù)制

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

4.3 交叉

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

4.4 變異和可行性檢測(cè)

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

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

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

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

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

5 實(shí)驗(yàn)與性能評(píng)估

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

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

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

5.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

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