基于改進灰狼優(yōu)化算法的服務(wù)功能鏈映射算法

張岳，張俊楠，吳曉春，洪晨，周靜靜

基于改進灰狼優(yōu)化算法的服務(wù)功能鏈映射算法

張岳，張俊楠，吳曉春，洪晨，周靜靜

（浙江工商大學(xué)信息與電子工程學(xué)院（薩塞克斯人工智能學(xué)院），浙江 杭州 310018）

隨著工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)、元宇宙等新型互聯(lián)網(wǎng)應(yīng)用的興起，網(wǎng)絡(luò)的低時延、可靠性、安全性、確定性等方面的需求正面臨嚴峻挑戰(zhàn)。采用網(wǎng)絡(luò)功能虛擬化技術(shù)在虛擬網(wǎng)絡(luò)部署過程中，存在服務(wù)功能鏈映射效率低與部署資源開銷大等問題，聯(lián)合考慮節(jié)點激活成本、實例化開銷，以最小化平均部署網(wǎng)絡(luò)成本為優(yōu)化目標(biāo)建立了整數(shù)線性規(guī)劃模型，提出基于改進灰狼優(yōu)化算法的服務(wù)功能鏈映射（improved grey wolf optimization based service function chain mapping，IMGWO-SFCM）算法。該算法在標(biāo)準(zhǔn)灰狼優(yōu)化算法基礎(chǔ)上添加了基于無環(huán)最短路徑（shortest path，SP）問題算法的映射方案搜索、映射方案編碼以及基于反向?qū)W習(xí)與非線性收斂改進三大策略，較好地平衡了其全局搜索及局部搜索能力，實現(xiàn)服務(wù)功能鏈映射方案的快速確定。仿真結(jié)果顯示，該算法在保證更高的服務(wù)功能鏈請求接受率下，相較于對比算法降低了 11.86%的平均部署網(wǎng)絡(luò)成本。

網(wǎng)絡(luò)功能虛擬化；服務(wù)功能鏈；資源優(yōu)化

0 引言

在傳統(tǒng)運營商網(wǎng)絡(luò)中，來自用戶的海量服務(wù)需要大量專用的硬件設(shè)備部署實現(xiàn)。隨著工業(yè)互聯(lián)網(wǎng)、車聯(lián)網(wǎng)[1]、元宇宙等新型互聯(lián)網(wǎng)應(yīng)用的興起，人們對網(wǎng)絡(luò)的需求呈指數(shù)級增長，各式各樣的服務(wù)請求日新月異。為了應(yīng)對大量復(fù)雜的服務(wù)請求，服務(wù)提供商通常需要對一些已經(jīng)部署的設(shè)備進行更新，傳統(tǒng)網(wǎng)絡(luò)功能與專用物理設(shè)備的高耦合，給服務(wù)提供商帶來了較高的硬件成本、人工成本及維護成本。

網(wǎng)絡(luò)功能虛擬化（network function virtualization，NFV）技術(shù)有效解決了上述問題。通過傳統(tǒng)的網(wǎng)絡(luò)功能解耦于傳統(tǒng)專用物理設(shè)備，并以軟件的形式部署在通用設(shè)備之上，顯著減少了網(wǎng)絡(luò)服務(wù)提供商的運營成本及資本支出。在NFV架構(gòu)下，服務(wù)功能鏈（service function chain，SFC）由若干有序的虛擬網(wǎng)絡(luò)功能（virtual network function，VNF）組成，為用戶的網(wǎng)絡(luò)服務(wù)功能鏈請求（service function chain request，SFCR）提供服務(wù)，通過編排形成的SFC按照方案映射后即可部署。優(yōu)秀的部署方案可以有效地降低平均部署網(wǎng)絡(luò)成本，提高資源利用率，為網(wǎng)絡(luò)服務(wù)提供商更豐厚的利益。

NFV是使能網(wǎng)絡(luò)重構(gòu)的關(guān)鍵技術(shù)之一。通過 NFV 管控系統(tǒng)按需編排虛實網(wǎng)絡(luò)資源,優(yōu)化部署和遷移虛擬SFC可以實現(xiàn)網(wǎng)絡(luò)切片和靈活部署,滿足端到端的業(yè)務(wù)體驗和高效的網(wǎng)絡(luò)運營需求。近年雖然出現(xiàn)了大量關(guān)于虛擬服務(wù)功能鏈映射部署問題的研究，但大部分只專注于解決其中一個問題且存在一些弊端。比如文獻[2-5]都是使用整數(shù)線性規(guī)劃的方法建模求解 SFC 映射問題，分別實現(xiàn)了降低端到端時延、減少物理服務(wù)器數(shù)量和最小化帶寬使用率的優(yōu)化目標(biāo)，基本思路都是求解裝箱問題，但由于其資源配額是靜態(tài)的，不能反映VNF彈性特性，所以求解SFC映射時存在一定局限性。文獻[6-7]提出的算法分別在映射和部署過程中做到帶寬資源最小化，但都由于在SFC構(gòu)建時對底層網(wǎng)絡(luò)的考慮不足分別造成了部署開銷和節(jié)點資源的更大損耗。文獻[8]提出一種資源感知的服務(wù)功能鏈協(xié)同構(gòu)建和映射算法，考慮了底層網(wǎng)絡(luò)狀態(tài)，但對映射順序的忽視，增加了時延開銷。文獻[9-11]提到了基于貪心策略的啟發(fā)式算法的映射部署方法，雖說啟發(fā)式算法求解速度很快，但是會出現(xiàn)易陷入局部最優(yōu)的問題。文獻[12]提出對資源需求較少的SFC優(yōu)先映射的方法，做到了減少資源開銷，但是同樣出現(xiàn)了易陷入局部最優(yōu)的問題。由此分析，目前映射部署方法主要存在兩方面問題：一方面單一的構(gòu)建方案造成資源開銷較高，另一方面啟發(fā)式的方式易陷入局部最優(yōu)，因此需要在保障資源優(yōu)化和時延保障的同時，重視陷入局部最優(yōu)問題，做到快速進行SFC的映射與部署。

針對上述考慮，本文提出一種基于改進灰狼優(yōu)化（improved grey wolf optimization，IMGWO）算法的服務(wù)功能鏈映射方法。相關(guān)研究已證明，SFC 的映射及部署問題是 NP難（NP-hard）[13-15]問題。在算法設(shè)計中，本文首先考慮部署過程的資源優(yōu)化和時延保障，針對計算資源和帶寬資源建立相關(guān)的資源約束，構(gòu)建虛擬網(wǎng)絡(luò)功能實例化部署所需的總網(wǎng)絡(luò)成本模型，并將優(yōu)化目標(biāo)公式化為一個優(yōu)化函數(shù)。選擇利用元啟發(fā)式的相關(guān)群智能算法并改進使其匹配SFC映射優(yōu)化問題就是在多項式時間內(nèi)找到該問題的較優(yōu)解?；依莾?yōu)化（grey wolf optimization，GWO）算法是Mirjalili等[16]于2014年提出的一種元啟發(fā)式的全局搜索算法。迄今為止，灰狼優(yōu)化算法已被廣泛應(yīng)用且在不斷的改進當(dāng)中，主要應(yīng)用在約束函數(shù)優(yōu)化、流水車間調(diào)度問題、多級閾值圖像分割、高維優(yōu)化問題、路徑優(yōu)化等領(lǐng)域。相對其他進化算法，標(biāo)準(zhǔn)灰狼優(yōu)化算法能更好地提高優(yōu)化效率，并控制搜索方向，具有較強的全局搜索能力。但是由于標(biāo)準(zhǔn)灰狼優(yōu)化算法確實無法直接應(yīng)用于離散問題（即不能直接應(yīng)用于SFC映射問題中）并發(fā)揮出其優(yōu)勢，且存在收斂速度較慢及易陷入局部最優(yōu)解的情況。首先為了實現(xiàn)改進灰狼優(yōu)化算法在SFC映射問題中的適用，添加了基于無環(huán)最短路徑（shortest path，SP）問題算法的映射方案搜索、映射方案編碼策略，其次針對收斂速度和局部最優(yōu)問題分別添加了基于反向?qū)W習(xí)與非線性收斂改進的策略。通過添加三大策略改進后的算法得到的映射方案既可以做到平均部署網(wǎng)絡(luò)成本低于同類型的算法，同時加強了前期全局尋優(yōu)能力和后期局部尋優(yōu)能力，提高了物理拓撲的服務(wù)功能鏈請求接受率。

1 相關(guān)研究現(xiàn)狀

1.1 服務(wù)功能鏈映射研究現(xiàn)狀

目前服務(wù)功能鏈的優(yōu)化映射及部署問題通常被建模成為整數(shù)線性規(guī)劃模型或混合整數(shù)線性規(guī)劃模型，現(xiàn)有的工作根據(jù)求解所采用的優(yōu)化算法類型可以劃分為求解器、啟發(fā)式算法、元啟發(fā)式算法及強化學(xué)習(xí)算法四大類。優(yōu)化算法特點總結(jié)見表1。

常見的求解器有 CPLEX[17]、CVX[18]及Gurobi[19]。文獻[4,20]將服務(wù)功能鏈的優(yōu)化映射問題建模成為整數(shù)線性規(guī)劃模型后，利用 CPLEX 求解器進行了問題的求解。文獻[21]利用Convex（CVX）求解器求解了所建立的整數(shù)線性規(guī)劃模型。文獻[22]則利用Gurobi求解了根據(jù)最小化服務(wù)功能鏈端到端時延原則而建立的混合整數(shù)線性規(guī)劃模型。此類利用求解器的方法均表現(xiàn)出小規(guī)模網(wǎng)絡(luò)拓撲求解速度快、大規(guī)模時速度就會變慢的特點，無法滿足用戶在大規(guī)模網(wǎng)絡(luò)拓撲中快速獲得映射方案的需求。

近年來，強化學(xué)習(xí)算法憑借其解決決策問題的先天優(yōu)勢逐漸在各個領(lǐng)域中得到了應(yīng)用[23]。文獻[24]提出基于雙重深度Q網(wǎng)絡(luò)的 VNF 部署算法，根據(jù)基于閾值的策略部署和釋放 VNF 實例。仿真顯示，該算法在負載均衡及吞吐量方面均擁有較好的性能。強化學(xué)習(xí)算法針對優(yōu)化目標(biāo)的通用性主要由設(shè)置不同的反饋算法實現(xiàn)，這對算法設(shè)計者的要求頗高。

表1 優(yōu)化算法特點總結(jié)

面對大規(guī)模網(wǎng)絡(luò)拓撲中快速求解服務(wù)功能鏈的優(yōu)化映射及部署問題，各類啟發(fā)式算法相繼被提出。文獻[25]評估最適合當(dāng)前服務(wù)功能鏈請求的節(jié)點及鏈路資源利用率，并設(shè)計了啟發(fā)式部署算法，以最大化服務(wù)功能鏈請求接受率。文獻[26]提出了基于特征分解的啟發(fā)式算法，通過對服務(wù)功能鏈請求及物理拓撲進行特征分解，將VNF部署后的鏈路集成到鄰接矩陣中，并在物理拓撲中找到最接近的映射圖，確定最終的服務(wù)功能鏈映射方案，實現(xiàn)請求接受率的提高及資源開銷的優(yōu)化。啟發(fā)式算法雖說表現(xiàn)出求解速度快的特點，但無法保障所得的解為全局最優(yōu)解，且單種啟發(fā)式算法僅適用于特定的問題場景及相關(guān)優(yōu)化目標(biāo)。

元啟發(fā)式算法結(jié)合了隨機算法與局部搜索的策略[27]，對啟發(fā)式算法進行了改進。例如，文獻[28]使用了禁忌搜索算法，隨機生成一個初始解，隨后將與其鄰居解進行比較，若表現(xiàn)得更優(yōu)，則更新最優(yōu)解并通過不斷迭代得到最終的映射方案，實現(xiàn)服務(wù)功能鏈部署開銷的最小化。文獻[29]利用基于改進麻雀搜索算法的服務(wù)功能鏈優(yōu)化映射算法進行求解，針對同一時刻到來的多個請求，進行映射權(quán)重的排序，優(yōu)先映射權(quán)重高的請求。仿真結(jié)果顯示，該算法降低了部署開銷。但元啟發(fā)式算法的弊端是面對大規(guī)模的物理拓撲時易陷入局部最優(yōu)解。而本文提出的改進灰狼優(yōu)化算法的服務(wù)功能鏈映射方法可以通過非線性收斂策略加強算法的前期全局尋優(yōu)及后期局部尋優(yōu)能力。

1.2 灰狼優(yōu)化算法

2 問題描述和數(shù)學(xué)建模

本節(jié)首先通過一個典型案例說明根據(jù)不同的映射方案進行SFC的部署將會帶來不同的網(wǎng)絡(luò)成本，隨后介紹網(wǎng)絡(luò)模型并對問題進行數(shù)學(xué)建模，最后通過分析確定映射的相關(guān)約束及優(yōu)化目標(biāo)。

2.1 問題描述

針對用戶在應(yīng)用程序?qū)影l(fā)起的完全相同的服務(wù)功能鏈請求（service function chain request，SFCR），控制層在收到后需將其編排為服務(wù)功能鏈。根據(jù)不同的映射方案進行部署的SFC會消耗不同的計算資源、內(nèi)存資源、帶寬資源、節(jié)點激活成本及部署成本，進而使得不同的部署方案在相同的網(wǎng)絡(luò)拓撲中產(chǎn)生各有差異的網(wǎng)絡(luò)成本，此外也會帶來不一樣的端到端時延。不同映射方案部署對比如圖1所示。

因此根據(jù)服務(wù)功能鏈的映射及部署的4個基本原則，圖1（a）包含3個VNF的簡單服務(wù)功能鏈，圖1（b）描述了該服務(wù)功能鏈的兩種不同的映射及部署方案，分別為SFCa與SFCb，其中實線代表映射方案A，虛線代表映射方案B。數(shù)據(jù)由交換機A處流入并由交換機F處流出。在映射方案A中，占用網(wǎng)絡(luò)拓撲中3條鏈路的帶寬資源，而映射方案B占用了網(wǎng)絡(luò)拓撲中4條鏈路的帶寬資源，并多進行了一次數(shù)據(jù)交換，占用了不必要的帶寬資源，因此映射方案A的網(wǎng)絡(luò)成本更佳。

上述兩種映射方案說明了，針對用戶的SFCR進行不同的服務(wù)功能鏈映射方案的確定及部署，可使得網(wǎng)絡(luò)整體性能表現(xiàn)不同，所帶來的網(wǎng)絡(luò)成本及資源利用率各有差異。具體來說，SFC中VNF的不同節(jié)點部署會帶來不一樣的資源開銷及網(wǎng)絡(luò)成本，接下來將會對SFC的映射方案確定問題進行數(shù)學(xué)建模。

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

2.3 約束分析及優(yōu)化目標(biāo)

綜合考慮網(wǎng)絡(luò)拓撲中各節(jié)點計算資源、鏈路帶寬資源以及SFC端到端時延的約束，根據(jù)相關(guān)映射方案部署時產(chǎn)生的平均網(wǎng)絡(luò)成本最小化，VNF的映射問題可以建模成一個整數(shù)規(guī)劃模型。

3 基于改進灰狼算法的服務(wù)功能鏈映射算法

引言中提到，SFC部署被證實為NP困難問題。通常采用元啟發(fā)式算法進行求解，元啟發(fā)式算法中包括大量群智能算法[31]，如粒子群算法、蟻群算法、灰狼優(yōu)化算法等。本文提出IMGWO-SFCM，并利用基于無環(huán)即最短路徑問題（shortest path，SP）算法的搜索方案提供初始種群的生成范圍，基于映射節(jié)點的方案編碼提供灰狼個體與映射方案對應(yīng)的編碼方案。隨后通過改進灰狼優(yōu)化算法，迭代確定最終方案。

3.1 基于無環(huán)KSP算法的映射方案搜索策略

為了實現(xiàn)改進灰狼優(yōu)化算法在服務(wù)功能鏈映射問題中的適用，需要搜索網(wǎng)絡(luò)拓撲中可能存在的映射方案，使改進灰狼優(yōu)化算法能基于反向?qū)W習(xí)策略生成初始種群。主要分為兩步，首先需要查找網(wǎng)絡(luò)拓撲中源節(jié)點到目的節(jié)點中的前SP，然后需要根據(jù)第一步所得的條路徑及所需部署SFC中VNF的具體個數(shù)進行映射方案的搜索并得到相關(guān)集合。

SP問題可以劃分為限定無環(huán)SP和一般SP[32]，前者要求得到的路徑都必須是簡單路徑，后者則對路徑?jīng)]有任何限制，SFC的映射方案搜索問題即限定無環(huán)SP問題。目前限定無環(huán)SP算法主要有偏離路徑算法與改進Dijkstra算法，本文采用文獻[33]所提的偏離路徑算法進行前條最短路徑的搜索。

在第一步得到包含節(jié)點數(shù)不一的各條路徑后，為確定可能存在的映射方案，需要對各條路徑進一步搜索。搜索的依據(jù)是所需部署SFC中VNF及物理節(jié)點的數(shù)量，多個VNF可映射在同一物理節(jié)點中，但映射順序不得異于數(shù)據(jù)流方向。圖2所示映射方案搜索過程為例，包含兩個VNF的SFC在有兩個節(jié)點的物理鏈路中有3種映射方案，分別是均映射于節(jié)點1、均映射于節(jié)點2和按次序分別映射于節(jié)點1和節(jié)點2。

圖2 映射方案搜索過程

算法1展示了單鏈路映射方案搜索算法的具體工作流程，偽代碼如下。算法1以遞歸為核心思想，如算法1第12行所示，該算法從每條鏈路的第1個節(jié)點開始，進行所有首個VNF映射位置為該節(jié)點的映射方案的搜索，同時將相關(guān)方案寫入映射方案集合。該節(jié)點搜索完畢后循環(huán)至鏈路中下一節(jié)點。

算法1 單鏈路映射方案搜索算法

輸入：前條最短鏈路集合，服務(wù)功能鏈請求

FnFunction:Select（鏈路長度，SFC長度）映射方案 = 映射方案+ 當(dāng)前節(jié)點；

3.2 映射方案編碼策略

由于GWO一般用于求解連續(xù)型問題，不能直接應(yīng)用于離散型的服務(wù)功能鏈映射[34]，因此要對服務(wù)功能鏈的映射方案進行編碼，使灰狼個體與映射方案進行對應(yīng)。IMGWO-SFCM算法中灰狼個體編碼采用與物理節(jié)點對應(yīng)的編碼策略，映射解的長度與服務(wù)功能鏈中所需映射的虛擬網(wǎng)絡(luò)功能個數(shù)相等。映射方案編碼策略如圖3所示，將需要部署的VNF與網(wǎng)絡(luò)拓撲中的物理節(jié)點編號進行對應(yīng)?？蓪⑵鋵?yīng)映射方案編碼為（1,1,2,2,3）。

圖3 映射方案編碼策略

圖4描述了該編碼策略在多節(jié)點映射方案中與灰狼個體的對應(yīng)關(guān)系。一個灰狼個體代表一種服務(wù)功能鏈映射方案，不同的映射方案構(gòu)成了狼群。圖4展示了兩種可能的映射方案，5個VNF被映射在6個物理節(jié)點構(gòu)成的網(wǎng)絡(luò)拓撲中?？梢钥闯龇桨?的映射方案為（1,2,2,2,3），方案2的為（1,1,4,4,4）。類似方案1、方案2的灰狼個體在不斷的迭代中更新優(yōu)勢狼群，最后得到最優(yōu)個體并輸出相應(yīng)的映射方案。

3.3 基于反向?qū)W習(xí)和非線性收斂的改進灰狼優(yōu)化算法

標(biāo)準(zhǔn)灰狼優(yōu)化算法相較于傳統(tǒng)元啟發(fā)式算法具有調(diào)節(jié)參數(shù)少、結(jié)構(gòu)簡單、易于實現(xiàn)的優(yōu)點，已經(jīng)被廣泛運用在多個領(lǐng)域的優(yōu)化問題中。但仍然存在后期收斂速度慢，可能會陷入與真實最優(yōu)解相差很大的局部最優(yōu)中。針對這兩方面的問題，通過基于反向?qū)W習(xí)的種群初始化策略及收斂因子非線性優(yōu)化策略對標(biāo)準(zhǔn)灰狼優(yōu)化算法進行了改進，提出了改進灰狼優(yōu)化（IMGWO）算法。

3.3.1 基于反向?qū)W習(xí)的種群初始化策略

對于群體智能優(yōu)化算法，種群在搜索空間內(nèi)的初始位置分布直接決定了初代種群的環(huán)境適應(yīng)能力，即初代精英狼會直接影響狼群的狩獵效率，若初始精英狼正好在獵物附近，那么狼群可以快速逼近獵物并投入更多的精力用于精準(zhǔn)定位獵物位置。在標(biāo)準(zhǔn)GWO算法中，初始種群隨機初始化生成，無法保證較好的種群多樣性[35]，一定程度上限制了算法的尋優(yōu)性能。為了提高標(biāo)準(zhǔn)GWO算法的初始解質(zhì)量，IMGWO算法采用基于反向?qū)W習(xí)的種群初始化策略來生成狼群集合，得到質(zhì)量較好的初始解，有利于提高算法的收斂性能。

在映射方案確定的問題中，反向數(shù)的獲取區(qū)間為搜索后得到的映射方案集合，初始灰狼與反向灰狼對應(yīng)關(guān)系如圖5所示。代表集合中第一個映射方案，代表集合中最后一個映射方案，為隨機生成的其中一個初始灰狼個體，為其對應(yīng)的反向灰狼個體。

3.3.2 收斂因子非線性優(yōu)化策略

收斂因子對比如圖6所示。為了直觀地展示收斂因子的迭代變化情況，圖6展示了其與標(biāo)準(zhǔn)線性降低策略相比較的數(shù)值曲線。由迭代變化情況可以觀察到收斂因子在非線性優(yōu)化策略下，在迭代前期的數(shù)值變化較為平緩，可以使參數(shù)在前期保持較大的值，有助于全局尋優(yōu)，快速找到全局最優(yōu)區(qū)域。隨著迭代次數(shù)的增加，的變化趨勢逐漸加快，使得灰狼更加專注于在全局最優(yōu)區(qū)域內(nèi)挖掘最優(yōu)解，實現(xiàn)獵物的圍捕。改進后的收斂因子能夠更好地平衡算法的全局搜索與局部搜索能力。

3.3.3 IMGWO算法工作流程

根據(jù)前述基于反向?qū)W習(xí)的種群初始化策略及收斂因子非線性優(yōu)化策略的改進灰狼優(yōu)化算法很好地兼顧了全局搜索及局部搜索的能力，加快了算法的整體收斂速度，IMGWO具體可以分為以下7步。

步驟1 設(shè)定灰狼種群初始化規(guī)模，最大迭代次數(shù)，初始化各參數(shù)。

步驟2 根據(jù)隨機初始化的結(jié)果利用反向?qū)W習(xí)生成初始種群。

步驟3 計算狼群中每個灰狼個體的適應(yīng)度值，根據(jù)適應(yīng)度值排序選取前三的優(yōu)勢狼。

步驟4 更新灰狼個體位置。

步驟5 計算灰狼個體位置更新后的種群適應(yīng)度值，并更新優(yōu)勢狼群和它們的位置。

步驟7 判斷是否達到算法的約束條件或達到最大迭代次數(shù)，若滿足，則算法結(jié)束，輸出最優(yōu)解；若不滿足，則返回并重新執(zhí)行步驟3～步驟6。

3.3.4 IMGWO算法的測試

3.4 映射算法設(shè)計

基于改進灰狼優(yōu)化算法的服務(wù)功能鏈映射算法首先根據(jù)網(wǎng)絡(luò)拓撲及服務(wù)功能鏈服務(wù)圖進行物理節(jié)點資源、SFC所需計算資源及帶寬資源的計算，并根據(jù)相應(yīng)資源狀況進行單節(jié)點部署可能性的判定。在服務(wù)功能鏈實際部署的過程中會帶來相關(guān)的部署成本及開啟物理節(jié)點的激活成本，服務(wù)鏈中的網(wǎng)絡(luò)功能部署在多個物理節(jié)點之上可以帶來可用性上的保證，但也會使得服務(wù)功能鏈的端到端時延及部署網(wǎng)絡(luò)成本顯著增加。因此，當(dāng)網(wǎng)絡(luò)拓撲中存在物理節(jié)點能夠支持單節(jié)點的服務(wù)功能鏈完全部署時，執(zhí)行單節(jié)點部署操作可以減少物理節(jié)點的占用、降低物理節(jié)點激活成本、服務(wù)功能鏈端到端時延及部署成本。

表3 測試函數(shù)結(jié)果

算法2 單節(jié)點映射算法

輸出：映射方案

如算法2偽代碼中的第1～5行所示，判斷服務(wù)功能鏈?zhǔn)欠衲軌蜻M行單節(jié)點部署首先需對網(wǎng)絡(luò)環(huán)境中各物理節(jié)點的資源狀況進行遍歷，尋找是否存在擁有足夠的資源供服務(wù)功能鏈部署及運營的物理節(jié)點，若存在相關(guān)節(jié)點，則進一步判斷部署后的端到端時延是否滿足用戶的最低時延需求。當(dāng)出現(xiàn)存在多個支持單獨部署且均滿足最低時延需求的節(jié)點情況時，則根據(jù)最小化服務(wù)功能鏈端到端時延的原則進行映射物理節(jié)點的確定。完成單節(jié)點映射可能性的判斷后，算法開始執(zhí)行多節(jié)點映射方案確定的相關(guān)步驟。首先根據(jù)SFC的源節(jié)點與目的節(jié)點，運用限定無環(huán)SP算法及進行前條最短路徑的篩選，隨后通過算法1進行可能映射方案的進一步搜索，使得灰狼種群初始化范圍得以確定。隨后，通過改進灰狼優(yōu)化算法相關(guān)流程輸出最佳映射方案?；诟倪M灰狼優(yōu)化的服務(wù)功能鏈映射算法偽代碼如算法3所示。

算法3 基于改進灰狼優(yōu)化的服務(wù)功能鏈映射算法

輸出：映射方案

4 仿真與結(jié)果分析

本節(jié)研究的優(yōu)化映射方案主要是針對于服務(wù)功能鏈請求不斷到達的情景，在不撤銷已部署的服務(wù)功能鏈的情況下對比仿真結(jié)果的分析。使用MATLAB 2020b軟件在配置為AMD Ryzen 7 5 800H CPU、16.0 GB RAM的計算機上完成，對IMGWO- SFCM算法在服務(wù)功能鏈的請求接受情況、平均部署網(wǎng)絡(luò)成本等方面的性能進行了評估，并與Random隨機算法、DP-COA[38]算法、First-fit算法、RACCM算法[7]、ProvisionTraffic算法[18]進行了比較。Random算法的部署是隨機選擇擁有足夠計算資源和鏈路帶寬資源的網(wǎng)絡(luò)節(jié)點進行節(jié)點映射和鏈路映射，F(xiàn)irst-Fit算法的部署是選擇第一個碰到的具有足夠資源的網(wǎng)絡(luò)節(jié)點進行節(jié)點映射和鏈路映射，DP-COA算法采用動態(tài)規(guī)劃的思想，將映射問題看作多階段決策過程進行求解。RACCM算法采用服務(wù)鏈構(gòu)建方案與映射方案不斷匹配的方式進行求解。ProvisionTraffic算法為每一條SFC請求建立一個多階段圖，將部署VNF時所有可能的服務(wù)器位置添加到圖中。

4.1 仿真設(shè)計

為了便于進行仿真分析，算法采用的網(wǎng)絡(luò)拓撲為典型物理網(wǎng)絡(luò)拓撲NSFNET[39]，網(wǎng)絡(luò)拓撲中某個時間段到達的服務(wù)功能鏈請求數(shù)量從0到 1 200依次遞增。拓撲參數(shù)及仿真過程中所需參數(shù)的設(shè)置基于研究[40]，見表4。每條鏈路的帶寬為 1 000 Mbit/s，各節(jié)點的CPU容量為100 MIPS，內(nèi)存為1 000 Mbit/s，每個節(jié)點的假定總激活開銷、VNF部署成本、CPU、內(nèi)存和帶寬的重要性相同，因此目標(biāo)函數(shù)中的權(quán)重系數(shù)、、均設(shè)置為1，、設(shè)置為0.1。在實際情況中，也可以根據(jù)實際需求調(diào)整這些權(quán)重參數(shù)，從而達到所需的優(yōu)化目標(biāo)。拓撲擁有14個節(jié)點和21條鏈路，對于NSFNET，能夠承載8種類型的VNF，每個SFCR最多包含3類VNF，每個SFCR的帶寬資源需求量的數(shù)值大小滿足(0,10]的隨機分布，每個VNF的具體CPU資源開銷及內(nèi)存資源開銷各不相同，需進行前期的設(shè)定。

表4 仿真參數(shù)

4.2 性能指標(biāo)

為了驗證網(wǎng)絡(luò)功能虛擬化環(huán)境中IMGWO- SFCM的可用性，使用服務(wù)功能鏈請求接受率、網(wǎng)絡(luò)節(jié)點計算資源利用率、鏈路帶寬資源利用率、平均部署網(wǎng)絡(luò)成本4個性能指標(biāo)作為仿真分析對象。

4.3 仿真結(jié)果分析

首先，將服務(wù)功能鏈請求數(shù)目作為變量，服務(wù)功能鏈請求接受率如圖7所示，顯示了不同算法在相同服務(wù)功能鏈請求數(shù)目下的請求接受率。由圖7變化趨勢可以得到，當(dāng)服務(wù)功能鏈請求數(shù)量不斷增加時，會出現(xiàn)部分請求無法得到滿足的情況，這個問題來源于網(wǎng)絡(luò)資源總量的限制。當(dāng)服務(wù)功能鏈請求數(shù)量較少時，網(wǎng)絡(luò)拓撲中的資源余量充足，不會出現(xiàn)負載過高的情況。服務(wù)請求數(shù)量在600左右時，幾種算法均能100%的實現(xiàn)請求的接受，但是隨著請求數(shù)目的增加，各算法的請求接受率均不同程度地下降。其中，Random算法下降趨勢最明顯，當(dāng)請求數(shù)量達到1 200時，接受率只有65%。這是因為服務(wù)功能鏈請求數(shù)量的增加導(dǎo)致部分節(jié)點的資源被大量消耗，同時產(chǎn)生了大量的資源碎片，剩余的資源量無法繼續(xù)容納新的虛擬網(wǎng)絡(luò)功能，越來越多的請求無法被滿足，降低了服務(wù)功能鏈映射的成功率。在相同的下降趨勢中，IMGWO-SFCM算法通過灰狼位置更新策略，不斷為到達的服務(wù)功能鏈請求搜索當(dāng)前最佳的映射方案，使請求接受率相較于其他算法始終保持相對較高水平，該算法的運用可以使得網(wǎng)絡(luò)拓撲接受更多的服務(wù)請求。

圖7 服務(wù)功能鏈請求接受率

更高的請求接受率代表了網(wǎng)絡(luò)拓撲中依據(jù)映射方案部署了更多的服務(wù)功能鏈，同時也帶來了更高的總部署網(wǎng)絡(luò)成本。為了更好地對IMGWO-SFCM算法在部署成本方面的優(yōu)化進行體現(xiàn)，單條服務(wù)功能鏈的平均部署網(wǎng)絡(luò)成本如圖8所示，顯示了單條服務(wù)功能鏈的平均部署網(wǎng)絡(luò)成本隨服務(wù)功能鏈請求數(shù)目變化的情況。首先觀察變化趨勢，隨著請求數(shù)目的不斷增加，5種算法的平均部署網(wǎng)絡(luò)成本在初期達到最高，其原因在于前期到達的服務(wù)請求在節(jié)點激活方面產(chǎn)生的開銷較多，同時較少的請求數(shù)目無法均分部署帶來的帶寬資源開銷。在4種算法平均部署網(wǎng)絡(luò)成本的比較中，IMGWO-SFCM算法的成本均處于最低水平，在請求數(shù)量較大時，仍然保持了較好的部署網(wǎng)絡(luò)成本控制。Random算法帶來的部署網(wǎng)絡(luò)成本較高，資源浪費的情況較為嚴重，當(dāng)請求數(shù)目達到1 000后無法接受新的請求，因此平均部署網(wǎng)絡(luò)成本保持不變。First-Fit算法帶來的部署網(wǎng)絡(luò)成本呈現(xiàn)持續(xù)上漲的趨勢，并在請求數(shù)目達到1 000時超過Random和RACCM算法。

圖8 單條服務(wù)功能鏈的平均部署網(wǎng)絡(luò)成本

整個過程表明了IMGWO-SFCM算法對于網(wǎng)絡(luò)拓撲中資源使用情況的優(yōu)化要優(yōu)于另外幾種算法，可以為用戶節(jié)省服務(wù)功能鏈的部署成本。

網(wǎng)絡(luò)節(jié)點計算資源利用率如圖9所示，給出了4種算法的網(wǎng)絡(luò)節(jié)點計算資源利用率隨服務(wù)功能鏈請求數(shù)目變化的折線圖。隨著請求的不斷到達，IMGOW-SFCM算法擁有明顯的性能優(yōu)勢，這是由于其相較于另外幾種算法而言擁有較強的全局搜索能力，充分挖掘滿足部署條件的映射方案，有效緩解了計算資源的碎片化或鏈路帶寬資源的瓶頸造成的影響，在提高請求接受率的同時提高了網(wǎng)絡(luò)節(jié)點的計算資源利用率。IMGOW-SFCM算法的計算資源利用率相比表現(xiàn)最差的Random算法提高了8%。

圖9 網(wǎng)絡(luò)節(jié)點計算資源利用率

鏈路帶寬資源利用率如圖10所示，描述了帶寬資源利用率隨服務(wù)功能鏈請求數(shù)量的變化趨勢。Random算法的隨機搜索機制導(dǎo)致了其較高的端到端路由跳數(shù)，在前期占用了較多的鏈路帶寬資源，后期由于較低的請求接受率，其帶寬資源利用率反而表現(xiàn)不佳。隨著請求數(shù)目的增加，IMGOW-SFCM算法的帶寬資源利用率逐漸達到最高水平，相較于其他幾種算法均有所提升，尤其比Random提升了5.2%。由于所提算法更多地考慮了單節(jié)點中多VNF的部署，減少了不必要的鏈路帶寬消耗，提高了底層網(wǎng)絡(luò)的請求接受率，其鏈路帶寬資源利用率高于另外幾種算法。

圖10 鏈路帶寬資源利用率

5 結(jié)束語

本文主要解決了網(wǎng)絡(luò)功能虛擬化環(huán)境中，在滿足服務(wù)功能鏈時延要求的情況下提供平均部署網(wǎng)絡(luò)成本最優(yōu)化的映射方案并進行部署的問題。首先描述了服務(wù)功能鏈部署的具體場景，并分析了影響平均部署網(wǎng)絡(luò)成本的因素，其次建立了在滿足用戶時延需求及各項網(wǎng)絡(luò)資源約束下的服務(wù)功能鏈部署總網(wǎng)絡(luò)成本最小化模型，最后提出一種基于改進灰狼優(yōu)化的粒度可變SFC部署算法求解該組合優(yōu)化問題。仿真結(jié)果表明，該算法可以獲得比對照算法更高的服務(wù)功能鏈請求接受率及更低的平均網(wǎng)絡(luò)成本。

本文研究集中在水平方向于對服務(wù)功能鏈進行優(yōu)化，考慮服務(wù)功能鏈中不同的虛擬網(wǎng)絡(luò)功能之間存在不產(chǎn)生相互邏輯影響的情況，未來可以通過數(shù)據(jù)流的復(fù)制及兼并實現(xiàn)虛擬網(wǎng)絡(luò)功能的并行執(zhí)行，從垂直的角度進行優(yōu)化，進一步壓縮服務(wù)功能鏈端到端的長度，降低端到端時延。

[1] 彭新玉, 周揚, 董振江. 基于車聯(lián)網(wǎng)遠程駕駛的虛擬資源智能協(xié)同管理技術(shù)[J]. 電信科學(xué), 2020, 36(4): 61-68 .

PENG X Y, ZHOU Y, DONG Z J. Intelligent collaborative management technology of virtual resources based on internet of vehicles remote driving[J]. Telecommunications Science, 2020, 36(4): 61-68.

[2] 李卓峰. 低能耗服務(wù)功能鏈的映射研究[D]. 成都: 電子科技大學(xué), 2018．

LI Z F. Energy-efficient research of service function chain mapping[D]. Chengdu: University of Electronic Science and Technology of China, 2018.

[3] QU L, ASSI C, SHABAN K. Delay-aware scheduling and resource optimization with network function virtualization[J]. IEEE Transactions on Communications, 2016, 64(9): 3746-3758.

[4] LUIZELLI M C, BAYS L R, BURIOL L S, et al. Piecing together the NFV provisioning puzzle: efficient placement and chaining of virtual network functions[C]//Proceedings of 2015 IFIP/IEEE International Symposium on Integrated Network Management. Piscataway: IEEE Press, 2015: 98-106.

[5] MOENS H, DE TURCK F. VNF-P: a model for efficient placement of virtualized network functions[C]//Proceedings of 10th International Conference on Network and Service Management (CNSM) and Workshop. Piscataway: IEEE Press, 2014: 418-423.

[6] 湯紅波, 邱航, 游偉, 等. 基于聯(lián)合備份的服務(wù)功能鏈可靠性保障的部署方法[J]. 電子與信息學(xué)報, 2019, 41(12): 3006-3013.

TANG H B, QIU H, YOU W, et al. A reliability-guarantee method for service function chain deployment based on joint backup[J]. Journal of Electronics ＆ Information Technology, 2019, 41(12): 3006-3013.

[7] LI J L, SHI W S, YE Q, et al. Online joint VNF chain composition and embedding for 5G networks[C]//Proceedings of 2018 IEEE Global Communications Conference. Piscataway: IEEE Press, 2018: 1-6.

[8] 孫士清, 彭建華, 游偉, 等. 5G網(wǎng)絡(luò)下資源感知的服務(wù)功能鏈協(xié)同構(gòu)建和映射算法[J]. 西安交通大學(xué)學(xué)報, 2020, 54(8): 140-148.

SUN S Q, PENG J H, YOU W, et al. A coordinating composition and mapping algorithm for a service function chain with resource-aware[J]. Journal of Xi'an Jiaotong University, 2020, 54(8): 140-148.

[9] BOUET M, LEGUAY J, COMBE T, et al. Cost-based placement of vDPI functions in NFV infrastructures[J]. International Journal of Network Management, 2015, 25(6): 490-506.

[10] SUN Q Y, LU P, LU W, et al. Forecast-assisted NFV service chain deployment based on affiliation-aware vNF placement[C]//Proceedings of 2016 IEEE Global Communications Conference. Piscataway: IEEE Press, 2016: 1-6.

[11] BECK M T, BOTERO J F. Coordinated allocation of service function chains[C]//Proceedings of 2015 IEEE Global Communications Conference. Piscataway: IEEE Press, 2015: 1-6.

[12] 程洪閃, 孟歡,張曉輝. 服務(wù)功能鏈的優(yōu)化映射策略[J]. 計算機與網(wǎng)絡(luò), 2021, 47(8): 54-56.

CHENG H S, MENG H, ZHANG X H. Optimized mapping strategy of service function chain[J]. Computer & Network, 2021, 47(8): 54-56.

[13] COHEN R, LEWIN-EYTAN L, NAOR J S, et al. Near optimal placement of virtual network functions[C]//Proceedings of 2015 IEEE Conference on Computer Communications. Piscataway: IEEE Press, 2015: 1346-1354.

[14] TAJIKI M M, SALSANO S, CHIARAVIGLIO L, et al. Joint energy efficient and QoS-aware path allocation and VNF placement for service function chaining[J]. IEEE Transactions on Network and Service Management, 2018, 16(1): 374-388.

[15] YUAN B, REN B B. Embedding the minimum cost SFC with end-to-end delay constraint[C]//Proceedings of 2020 5th International Conference on Mechanical, Control and Computer Engineering (ICMCCE). Piscataway: IEEE Press, 2020: 2299-2303.

[16] MIRJALILI S, MIRJALILI S S M, LEWIS A. Grey wolf optimizer[J]. Advances in engineering software, 2014(69): 46-61.

[17] BLIEKLU C, BONAMI P, LODI A. Solving mixed-integer quadratic programming problems with IBM-CPLEX: a progress report[C]//Proceedings of the 26th RAMP Symposium. [S.l.:s.n.], 2014: 16-17.

[18] GRANT M, BOYD S. CVX: MATLAB software for disciplined convex programming, version 2.1[Z]. 2014.

[19] OPTIMIZATION G. Gurobi optimizer reference manual[Z]. 2020.

[20] BARI F, CHOWDHURY S R, AHMED R, et al. Orchestrating virtualized network functions[J]. IEEE Transactions on Network and Service Management, 2016, 13(4): 725-739.

[21] TAJIKI M M, SALSANO S, SHOJAFAR M, et al. Energy-efficient path allocation heuristic for service function chaining[C]//Proceedings of 2018 21st Conference on Innovation in Clouds, Internet and Networks and Workshops (ICIN). Piscataway: IEEE Press, 2018: 1-8.

[22] CZIVA R, PEZAROS D P. On the latency benefits of edge NFV[C]//Proceedings of 2017 ACM/IEEE Symposium on Architectures for Networking and Communications Systems. Piscataway: IEEE Press, 2017: 105-106.

[23] 陳學(xué)松, 楊宜民. 強化學(xué)習(xí)研究綜述[J]. 計算機應(yīng)用研究, 2010, 27(8): 2834-2838, 2844.

CHEN X S, YANG Y M. Reinforcement learning: survey of recent work[J]. Application Research of Computers, 2010, 27(8): 2834-2838, 2844.

[24] PEI J N, HONG P L, PAN M, et al. Optimal VNF placement via deep reinforcement learning in SDN/NFV-enabled networks[J]. IEEE Journal on Selected Areas in Communications, 2019, 38(2): 263-278.

[25] KUO T W, LIOU B H, LIN K C J, et al. Deploying chains of virtual network functions: on the relation between link and server usage[J]. IEEE/ACM Transactions on Networking, 2018, 26(4): 1562-1576.

[26] MECHTRI M, GHRIBI C, ZEGHLACHE D. A scalable algorithm for the placement of service function chains[J]. IEEE Transactions on Network and Service Management, 2016, 13(3): 533-546.

[27] ABDEL-BASSET M, ABDEL-FATAH L, SANGAIAH A K. Metaheuristic algorithms: a comprehensive review[M]//Computational Intelligence for multimedia big data on the cloud with engineering applications. Amsterdam: Elsevier, 2018: 185-231.

[28] MIJUMBI R, SERRAT J, GORRICHO J L, et al. Design and evaluation of algorithms for mapping and scheduling of virtual network functions[C]//Proceedings of the 2015 1st IEEE Conference on Network Softwarization (NetSoft). Piscataway: IEEE Press, 2015: 1-9.

[29] 朱國暉, 景文煥, 李世昌. 基于改進麻雀搜索算法的服務(wù)功能鏈優(yōu)化映射算法[J]. 計算機應(yīng)用研究, 2022, 39(7): 2120-2123, 2131.

ZHU G H, JING W H, LI S C. Optimized mapping algorithm of service function chain based on improved sparrow search algorithm[J]. Application Research of Computers, 2022, 39(7): 2120-2123, 2131.

[30] DWARAKI A, WOLF T. Adaptive service-chain routing for virtual network functions in software-defined networks[C]// Proceedings of the 2016 Workshop on Hot Topics in Middleboxes and Network Function Virtualization. [S.l.:s.n.], 2016: 32-37.

[31] 劉雪, 田云娜, 田園. 群智能算法研究綜述[J]. 信息與電腦(理論版), 2021, 33(24): 63-69.

LIU X, TIAN Y N, TIAN Y. A survey of swarm intelligence methods[J]. China Computer ＆ Communication, 2021, 33(24): 63-69.

[32] 徐濤, 丁曉璐, 李建伏.最短路徑算法綜述[J]. 計算機工程與設(shè)計, 2013, 34(11): 3900-3906, 3911.

XU T, DING X L, LI J F. Review onshortest paths algorithms[J]. Computer Engineering and Design, 2013, 34(11): 3900-3906, 3911.

[33] HERSHBERGER J, MAXEL M, SURI S. Finding theshortest simple paths: a new algorithm and its implementation[J]. ACM Transactions on Algorithms (TALG), 2007, 3(4): 45.

[34] GUPTA S, DEEP K. Cauchy grey wolf optimiser for continuous optimisation problems[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2018, 30(6): 1051-1075.

[35] GAIDHANE P J, NIGAM M J. A hybrid grey wolf optimizer and artificial bee colony algorithm for enhancing the performance of complex systems[J]. Journal of Computational Science, 2018(27): 284-302.

[36] XIA X W, LIU J N, LI Y X. Particle swarm optimization algorithm with reverse-learning and local-learning behavior[J]. Journal of Software, 2014, 9(2): 350-357.

[37] MARINI F, WALCZAK B. Particle swarm optimization (PSO). A tutorial[J]. Chemometrics and Intelligent Laboratory Systems, 2015, 149: 153-165.

[38] 劉昀. 虛擬網(wǎng)絡(luò)功能資源分配與服務(wù)功能鏈路由研究[D]. 合肥: 中國科學(xué)技術(shù)大學(xué), 2020.

LIU Y. Virtual network function resource allocation and service function chain routing[D]. Hefei: University of Science and Technology of China, 2020.

[39] MILLS D L, BRAUN H. The NSFNET backbone network[C]//Proceedings of the ACM Workshop on Frontiers in Computer Communications Technology - SIGCOMM '87. New York: ACM Press, 1988: 191-196.

[40] PEI J N, HONG P L, XUE K P, et al. Efficiently embedding service function chains with dynamic virtual network function placement in geo-distributed cloud system[J]. IEEE Transactions on Parallel and Distributed Systems, 2019, 30(10): 2179-2192.

Improved grey wolf optimization algorithm based service function chain mapping algorithm

ZHANG Yue, ZHANG Junnan, WU Xiaochun, HONG Chen, ZHOU Jingjing

School of Information and Electronic Engineering(Sussex Artificial Intelligence Institute), Zhejiang Gongshang University, Hangzhou 310018,China

With the rise of new Internet applications such as the industrial Internet, the Internet of vehicles, and the metaverse, the network’s requirements for low latency, reliability, security, and certainty are facing severe challenges. In the process of virtual network deployment, when using network function virtualization technology, there were problems such as low service function chain mapping efficiency and high deployment resource overhead. The node activation cost and instantiation cost was jointly considered, an integer linear programming model with the optimization goal of minimizing the average deployment network cost was established, and an improved grey wolf optimization service function chain mapping (IMGWO-SFCM) algorithm was proposed. Three strategies: mapping scheme search based on acyclicSP algorithm, mapping scheme coding and improvement based on reverse learning and nonlinear convergence were added to the standard grey wolf optimization algorithm to form this algorithm. The global search and local search capabilities were well balanced and the service function chain mapping scheme was quickly determined by IMGWO-SFCM. Compared with the comparison algorithm, IMGWO-SFCM reduces the average deployment network cost by 11.86% while ensuring a higher service function chain request acceptance rate.

network function virtualization, service function chain, resource optimization

TP393

A

10.11959/j.issn.1000–0801.2022275

2022?04?19；

2022?10?20

吳曉春，spring-403@zjgsu.edu.cn

浙江省自然科學(xué)基金資助項目（NO.LY19F020002，No.LY19F020006）；浙江省新型網(wǎng)絡(luò)標(biāo)準(zhǔn)與應(yīng)用技術(shù)重點實驗室（No.2013E10012）

The Natural Science Foundation of Zhejiang Province (No.LY19F020002, No.LY19F020006)，Zhejiang Key Laboratory of New Network Standards and Application Technology (No.2013E10012)

張岳（1998? ），女，浙江工商大學(xué)碩士生，主要研究方向為知識圖譜、新一代網(wǎng)絡(luò)技術(shù)架構(gòu)。

張俊楠（1997? ），男，浙江工商大學(xué)碩士生，主要研究方向為新一代網(wǎng)絡(luò)技術(shù)架構(gòu)。

吳曉春（1983? ），女，博士，浙江工商大學(xué)高級實驗師、碩士生導(dǎo)師，主要研究方向為新一代網(wǎng)絡(luò)技術(shù)架構(gòu)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)功能虛擬化、人工智能與網(wǎng)絡(luò)安全的結(jié)合等。

洪晨（1998? ），女，浙江工商大學(xué)碩士生，主要研究方向為知識圖譜、新一代網(wǎng)絡(luò)技術(shù)架構(gòu)。

周靜靜（1980? ），女，博士，浙江工商大學(xué)副教授、碩士生導(dǎo)師，主要研究方向為新一代網(wǎng)絡(luò)技術(shù)架構(gòu)、軟件定義網(wǎng)絡(luò)、網(wǎng)絡(luò)流量建模與分析、大數(shù)據(jù)處理、深度學(xué)習(xí)等。