面向多接入邊緣計算的VNFM分布式部署方案

馬 悅，張玉梅

(1.陜西中醫藥大學 信息化建設管理處，陜西 咸陽 712046；2.陜西師范大學 計算機科學學院，陜西 西安 710119)

移動互聯網的飛速發展促使數據流量空前增長，5G多樣化和動態化的網絡服務對移動通信網絡提出超可靠低延遲(Ultra-Reliable Low-Latency Communications，URLLC)的需求。移動多接入邊緣計算(Multi-access Edge Computing，MEC)作為5G通信網絡的重要支撐技術，將計算能力、存儲能力“下沉”到移動邊緣節點，降低延遲并提升帶寬速率，為更多用戶提供高可靠、低時延的網絡服務。實際部署中，網絡功能虛擬化(Virtual Network Functions，NFV)為多接入邊緣計算的實現提供了網絡架構級解決方案。歐洲電信標準協會(European Telecommunications Standards Institute，ETSI)提出在多接入邊緣計算架構中部署虛擬網絡功能(Virtual Network Function，VNF)實例來實現網絡功能虛擬化[1]。在不改造底層物理網絡的基礎上分層解耦部署VNF，將各個物理資源池劃分為不同的管理域，并通過在管理域上部署獨立的虛擬化網絡功能管理器(Virtual Network Function Manager，VNFM)實現對虛擬網絡功能實例的分布式管理。

可見，虛擬化網絡功能管理器實例的部署將直接影響網絡性能。近年來，虛擬網絡功能部署問題得到廣泛研究，但是關于虛擬化網絡功能管理器部署的文獻相對匱乏。典型的虛擬化網絡功能管理器部署算法通常以合理配置所需的計算和通信資源為目標[2]進行研究。文獻[3-4]在能耗、網絡流量等約束條件的限制下最大化計算和通信資源利用率。文獻[5-6]聚焦于降低部署成本，設計了面向用戶服務質量(Quality of Service，QoS)優化的虛擬化網絡功能管理器部署方案。針對混合云架構下的虛擬化網絡功能管理器部署方案，文獻[7-8]研究了不同基礎架構組合起來的混合云環境虛擬化網絡功能管理器部署問題，但并不涉及邊緣部署。在此基礎上，文獻[9]提出了一種虛擬化網絡功能管理器部署解決方案。該方案實現了多云環境中成本效率與用戶服務質量之間的折衷。上述文獻聚焦于如何提高虛擬化網絡功能管理器部署過程中的資源利用率和用戶服務質量等。由于多接入邊緣計算邊緣托管的網絡服務對傳輸時延較為敏感，而上述算法沒有考慮傳輸時延的優化問題，因此難以滿足多接入邊緣計算的實際應用需求。

在多接入邊緣計算架構中，為了向用戶提供低時延的網絡服務，運營商將部分時延敏感的網絡功能“下沉”到了網絡邊緣，在業務面形成了分布式的虛擬網絡功能部署架構。然而，傳統的虛擬化網絡功能管理器部署方案僅考慮了同一管理域內的時延優化問題，因此虛擬化網絡功能管理器主要部署在網絡中心。在多接入邊緣計算場景下，上述方案無法保證邊緣虛擬網絡功能的管理面時延。為了解決上述問題，筆者聚焦于研究分布式云平臺環境下的虛擬化網絡功能管理器部署問題，旨在設計分布式的虛擬化網絡功能管理器部署算法，保證多接入邊緣計算架構下的管理面時延。目前，多接入邊緣計算場景下的虛擬網絡功能部署問題已經出現了一些研究成果，但是相應的虛擬化網絡功能管理器部署問題并未得到深入研究。文獻[10-12]提出邊緣云架構下的虛擬化網絡功能管理器部署問題應考慮相關VNFC組件在中心云基礎架構物理機和多接入邊緣計算服務器上的協同部署。針對邊緣云和中心云的混合環境中的虛擬網絡功能部署問題，文獻[13]考慮到最小帶寬和最大端到端延遲的要求，在邊緣和中心云基礎架構上引入虛擬網絡功能部署算法和優化策略。文獻[14]通過在傳統云中部署更多的虛擬網絡功能從而增加邊緣云的最大利用率。文獻[15]將計算資源分配給虛擬實例，并將其部署在傳統云基礎架構上，提高了服務可用性并降低了管理成本。在此基礎上，文獻[16]提出了邊緣云混合架構中虛擬網絡功能部署的最小延遲算法。文獻[17]針對高可靠低延遲的需求，設計了一種基于遺傳算法的虛擬網絡功能方案，得到虛擬網絡功能實例部署最小通信開銷的思路。

上述研究全面地考慮了分布式云架構下虛擬網絡功能部署的用戶服務質量優化問題。但是虛擬化網絡功能管理器功能作為NFV管理編排(MANagement and Orchestration，MANO)模塊中的基礎組件，需要周期性的采集所有邊緣服務器的個體狀態信息，形成網絡全局視圖。上述研究沒有考慮如何優化多接入邊緣計算架構下業務面VNF實例與VNFM之間的傳輸時延，因此難以保證NFV管理平面的實時性。

基于此，以多接入邊緣計算架構下的超可靠低延遲應用場景為導向，提出了一種面向多接入邊緣計算的VNFM功能分布式部署方案。首先，利用混合整數規劃模型對VNFM部署問題進行建模，提出基于整數線性規劃的VNFM部署模型；然后，在所提整數線性規劃模型的基礎上，設計了一種基于免疫優化算法的部署方案。算法綜合考慮個體的抗體親和度和抗原親和度，通過引入更全面的個體評價機制對VNFM部署策略的多樣性進行評價，并加入了相應的免疫機制，從而得出最佳VNFM實例部署方案。免疫算法在保留智能算法優良特性的前提下，有目的地利用多樣性特征信息來抑制其優化過程中出現的退化現象，能夠更加全面地評價個體，同時能夠有效避免算法在部署過程中陷入局部最優解，提高算法性能。可見，免疫優化算法適用于解決多接入邊緣計算中的VNFM部署問題。仿真結果證明，相比于量子遺傳算法，免疫優化算法的個體評價機制能夠更有效地描述VNFM部署問題中個體的適應度和個體間的相似度，減少算法在局部反復迭代的次數，提高算法的收斂效率和性能。

1 VNFM部署問題與模型描述

1.1 基于MEC架構的VNFM分布式部署

為了降低MEC架構下遠端VNF實例與NFV管理平面之間的傳輸時延，筆者采用了分布式VNFM部署方法，其邏輯示意圖如圖1所示。其中，網絡的基礎設施包含多個地理上呈分布式部署的物理資源池，各個物理資源池由多個功能邊緣服務器和網絡轉發設備組成，負責為邊緣云VNF實例提供業務處理所需的計算、存儲和網絡資源。為了提高分布式NFV 平臺的管理效率，將MANO模塊中的VNFM功能抽象為分布式部署的多個邏輯模塊。在VNFM功能部署的過程中，首先將各個資源池劃分為不同的管理域，并通過在各個管理域部署獨立的VNFM管理實例以實現系統的分布式管理，各個域的VNFM實例通過統一的服務化接口互聯互通，在邏輯上形成集中的管理平面對地理上呈分布式部署的VNF實例進行集中管理。文中關注的問題是如何設計合理的部署算法，劃分各個管理域并選擇合適的節點部署VNFM實例，使得管理平面的傳輸時延最小，提高MEC架構下NFV MANO管理平面的通信效率。

1.2 基于整數線性規劃的部署模型

在VNFM部署模型中，設物理網絡為無向賦權圖GS=(NS，LS)，其中，NS代表物理服務器節點組成的集合，LS代表服務器節點間鏈路組成的集合。VNFM部署請求為無向賦權圖GV=(NV，LV)，其中，NV為請求的VNFM功能實例組成的集合，LV為實例間鏈路組成的集合。設定物理服務器的數量為n，VNFM實例的數量為m。定義n維列向量W，其中的任一元素wi表示服務器i上需要管理的VNF實例數量。定義n×m維矩陣D，其中任一元素dij表示服務器i與VNFM實例j之間的時延，同時根據服務水平協議(Service Level Agreement，SLA)中的QoS需求，設定最大時延閾值為s。最后，定義二值化n維列向量X，其中任一元素xi=1，表示在服務器i上部署VNFM實例，反之xi=0。設二值化n×m維矩陣Z，其中任一元素zij=1表示服務器i上的VNF實例由VNFM實例j負責管理。綜合上述定義，VNFM部署問題可以規約為如下0-1規劃模型。

優化目標：

(1)

約束條件：

(2)

zij≤xj， ?i∈NS，j∈NV，

(3)

(4)

dij≤s， ?i∈NS，j∈NV，

(5)

zij∈{0，1}，xi∈{0，1}， ?i∈NS，j∈NV。

(6)

2 基于免疫優化算法的VNFM部署方案

為了獲取VNFM實例部署的最小通信開銷，部署方案需要確定需要部署的VNFM實例的數量、各個VNFM部署的物理服務器位置，以及每個VNFM實例的管理范圍。相比于現有的智能算法[18-19](如遺傳算法、粒子群算法和蟻群算法等)以種群中個體適應度為導向的尋優策略，免疫優化算法借鑒了免疫系統的多樣性特征，引入了個體親和度，能夠更加全面地評價個體。筆者提出了一種基于免疫優化算法的VNFM部署方案，加入了對VNFM部署策略的多樣性評價和相應的免疫機制，并用其求解上述0-1規劃模型，從而得出最佳VNFM實例部署方案。

2.1 抗體群初始化

免疫優化算法是根據抗體與抗原間以及抗體之間親和度的尋優的智能算法。針對VNFM部署問題，采用直接編碼方式對抗體進行編碼。編碼后抗體為[α1，…，αm]，其中，任意碼字αi=ni表示VNFM實例i部署在序號為ni的服務器上，m為預設的VNFM實例數量。針對有30個服務器的邊緣云，預設請求的VNFM數量為4個，若編碼為[2，7，9，14]，則表示在序號為2，7，9，14的4個服務器上部署VNFM實例。此種編碼方式可以保證部署決策滿足式(4)和式(6)的約束條件。

2.2 多樣化評價

抗體與抗原親和度：抗體與抗原之間的親和度用于表示抗體對抗原的識別程度，在VNFM部署問題中表示求解的部署策略與優化目標之間的接近程度。針對第二節中提出的0-1規劃模型，本節設計了抗原與抗體v間親和度計算公式：

(7)

抗體間親和度：抗體間的親和度用于表示抗體之間的相似程度，此處采用R位連續匹配方案計算抗體間親和度的值，即

(8)

其中，kv，s表示抗體v和抗體s中連續相同的位數，m表示抗體編碼長度。在VNFM部署問題中抗體間親和度能夠有效地識別相似的部署策略，從而避免算法過早陷入局部最優，優化求解性能。

抗體濃度：抗體濃度表示種群中與抗體v相似的抗體所占的比例，即

(9)

其中，N表示種群數量，ε(·)表示階躍函數，δ表示適應度閾值，即超過該閾值則認為抗體間表現出過高的相似性。

期望繁殖概率：在種群中，任一抗體v的繁殖概率由抗體與抗原間親和度Av以及抗體濃度μv共同決定，即

(10)

抗體的抗原親和度越高，期望繁殖概率越大，同時抗體濃度機制會抑制相似的抗體不斷繁殖；當抗體濃度增加時，期望繁殖概率會下降。

2.3 基于免疫優化算法的VNFM部署

基于免疫優化算法的VNFM部署方案如算法1所示，算法輸入參數為云平臺的物理拓撲和時延矩陣，輸出參數為最優的VNFM部署決策矩陣。其中，第①、②行對免疫優化算法所需的基本參數進行了初始化，第③～⑨行實現免疫優化算法的迭代進化。第⑤行中算法隨機從種群中選擇兩個抗體進行配對，并隨機設置任意單點碼位作為交叉點，根據預設的交叉概率交換兩個抗體交叉點處的編碼字段，從而產生出兩個新的抗體。為了防止算法快速陷入局部最優，第⑥行采用了輪盤賭法選擇進行變異操作的碼位。輪盤賭選擇機制是一種放回式隨機采樣方法。利用期望繁殖概率表示其變異概率，個體期望繁殖概率越高，其發生變異的可能性越大。

算法1基于免疫優化算法的VNFM部署。

輸入：云平臺物理拓撲，時延矩陣D。

輸出：最優VNFM部署決策矩陣X*和Z*。

① 初始化免疫優化參數：種群規模NIND，最大進化代數MAXGEN，懲罰因子η和適應度閾值δ等。

② 初始化編碼種群中的全部抗體。

③ for gen=1∶MAXGEN

④ 計算各個抗體的期望繁殖概率。

⑤ 采用隨機交叉法執行抗體編碼字段交叉操作。

⑥ 采用輪盤賭法在抗體上選擇碼位執行變異操作。

⑦ 計算新生成抗體的期望繁殖概率。

⑧ 用子代中適應度高的染色體替換父代中適應度低的染色體，形成新的種群。

⑨ end for

⑩ 保留最終代中最優染色體，返回其對應的VNFM部署決策變量X*和管理關系Z*。

圖2 物理網絡拓撲圖

3 性能評估及分析

3.1 仿真環境

在Intel(R) Pentium(R) 3.40 GHz CPU，4 GB內存的PC機上仿真，使用GT-ITM生成物理網絡，拓撲結構如圖2所示。圖中物理拓撲共包含31個物理節點，每個節點表示一個邊緣高性能服務器配置參數選用華為2 288H V5型服務器，28核 2.2 GHzCPU，64 GB內存，2 TB硬盤，實驗所用物理拓撲如圖2所示。免疫優化算法參數設置如下：種群規模設為50，記憶庫容量為10，最大迭代次數為100，交叉概率為0.5，變異概率為0.4。

3.2 結果分析

將VNFM數量設置為6個，分別為經過免疫優化算法和量子遺傳算法計算后得到如圖3和圖4所示的VNFM部署示意圖。從拓撲管理的角度分析，當節點位置符合“域內聚合、域間離散”時，對網絡拓撲進行管理的效果最佳。對比圖3和圖4，可知圖3所示免疫優化算法的部署結果能夠更好地實現網絡拓撲的管理域劃分。

圖3 免疫優化算法部署示意圖

圖4 量子遺傳算法部署示意圖

圖5給出了當前狀態下免疫優化算法、量子遺傳算法以及蟻群算法的通信開銷和收斂性對比圖，其中通信開銷由式(1)定義，表示VNFM管理面的總體通信時延。通過對比可以得出，文中所提基于免疫優化的VNFM部署方案能夠在量子遺傳算法和蟻群算法的基礎上降低VNFM實例間通信的總體時延。此外，所提免疫優化算法能夠提高收斂效率，更快地獲取VNFM部署的最優解。仿真結果證明，相比于量子遺傳算法和蟻群算法，免疫優化算法的個體評價機制能夠更全面和有效地描述VNFM部署問題中個體的適應度和個體間的相似度，減少算法在局部反復迭代的次數，提高算法的收斂效率和性能。

圖6給出在部署不同數量VNFM實例的場景下，免疫優化算法、量子遺傳算法和蟻群算法的通信開銷對比情況。如圖6所示，隨著VNFM數量的上升，3種算法的通信開銷都呈現出先下降后上升的趨勢，這是由于初始狀態VNFM實例的增多降低了遠端節點與管理平面之間的通信時延，從而實現系統通信開銷的下降；而隨著VNFM實例的持續增加，管理平面內部通信時延顯著增加，而此時VNFM節點的增加僅能少量地降低管理平面與遠端節點之間的通信時延，因此系統的總體通信開銷反而呈上升趨勢。比較3種算法，可見免疫優化算法的通信開銷較量子遺傳算法和蟻群算法更低。且相比于其他兩種算法，免疫優化算法引入了更全面的個體評價機制，綜合考慮了個體的抗體親和度和抗原親和度，有效地避免算法過早陷入局部最優解，從而在全局的角度更加逼近最優解。

圖5 算法收斂對比

圖6 網絡通信開銷對比

對比量子遺傳算法與免疫優化算法的進化過程，量子遺傳算法采用了單一的適應度函數描述VNFM部署問題的優化目標，且采用了編碼長度較長的量子編碼方法描述VNFM的部署結果。相比之下，免疫優化算法采用了抗原-抗體適應度相結合的復合方法描述該問題的優化目標，同時采用了編碼長度較短的整數編碼方式表示部署結果。通過綜合對比兩種算法在收斂曲線和通信開銷方面的性能可以得出結論，本文提出的免疫優化算法更適合分布式VNFM部署問題的求解。

圖7 算法執行CPU時間

圖7給出了7種算法執行的CPU時間對比，對比實驗中3種算法的最大進化代數都固定為50代。由圖7所示，本文所提免疫優化算法的CPU運行時間較其他兩種算法更低。相比于量子遺傳算法，免疫優化算法不需要進行量子旋轉門和個體之間的矩陣內積運算，降低了算法的復雜度，因此提高了算法的運行效率。與蟻群算法相比，在VNFM節點較少的場景中，因為免疫優化算法的適應度評價指標更加復雜，其消耗的CPU時間相對更長，但是隨著VNFM節點的增多，文中提出的免疫優化算法占用了更少的CPU時間。其主要原因在于免疫優化算法的評價方式更加全面，算法不易陷入局部最優，能夠更快地收斂到最優解。

4 結束語

針對MEC架構下的VNFM功能部署問題，筆者提出一種基于免疫優化算法的VNFM部署方案。首先，利用混合整數規劃模型對VNFM的部署問題進行建模，給出基于整數線性規劃的VNFM部署模型；然后，在所提整數線性規劃模型的基礎上，設計了一種基于免疫優化算法的部署方案。所提免疫優化算法在保留智能算法優良特性的前提下，借鑒免疫系統的多樣性特征，引入了個體親和度，同時關注系統整體及單個VNFM性能。通過引入更全面的個體評價機制對VNFM部署策略的多樣性進行評價，并加入了相應的免疫機制，從而得出最佳VNFM實例部署方案。仿真結果表明相比于量子遺傳算法，免疫優化算法的個體評價機制能夠更有效地描述VNFM部署問題中個體的適應度和個體間的相似度；算法能夠有效避免算法在部署過程中陷入局部最優解，提高算法性能；并且能夠加速算法收斂效率，降低算法執行的CPU時間。但是本文方案不能智能化地確定所需的VNFM實例數量。后續工作中將針對該問題進行改進。