基于改進灰狼優化算法的服務功能鏈映射算法

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

基于改進灰狼優化算法的服務功能鏈映射算法

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

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

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

網絡功能虛擬化；服務功能鏈；資源優化

0 引言

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

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

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

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

1 相關研究現狀

1.1 服務功能鏈映射研究現狀

目前服務功能鏈的優化映射及部署問題通常被建模成為整數線性規劃模型或混合整數線性規劃模型，現有的工作根據求解所采用的優化算法類型可以劃分為求解器、啟發式算法、元啟發式算法及強化學習算法四大類。優化算法特點總結見表1。

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

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

表1 優化算法特點總結

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

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

1.2 灰狼優化算法

2 問題描述和數學建模

本節首先通過一個典型案例說明根據不同的映射方案進行SFC的部署將會帶來不同的網絡成本，隨后介紹網絡模型并對問題進行數學建模，最后通過分析確定映射的相關約束及優化目標。

2.1 問題描述

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

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

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

2.2 網絡模型

2.3 約束分析及優化目標

綜合考慮網絡拓撲中各節點計算資源、鏈路帶寬資源以及SFC端到端時延的約束，根據相關映射方案部署時產生的平均網絡成本最小化，VNF的映射問題可以建模成一個整數規劃模型。

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

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

3.1 基于無環KSP算法的映射方案搜索策略

為了實現改進灰狼優化算法在服務功能鏈映射問題中的適用，需要搜索網絡拓撲中可能存在的映射方案，使改進灰狼優化算法能基于反向學習策略生成初始種群。主要分為兩步，首先需要查找網絡拓撲中源節點到目的節點中的前SP，然后需要根據第一步所得的條路徑及所需部署SFC中VNF的具體個數進行映射方案的搜索并得到相關集合。

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

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

圖2 映射方案搜索過程

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

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

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

FnFunction:Select（鏈路長度，SFC長度）映射方案 = 映射方案+ 當前節點；

3.2 映射方案編碼策略

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

圖3 映射方案編碼策略

圖4描述了該編碼策略在多節點映射方案中與灰狼個體的對應關系。一個灰狼個體代表一種服務功能鏈映射方案，不同的映射方案構成了狼群。圖4展示了兩種可能的映射方案，5個VNF被映射在6個物理節點構成的網絡拓撲中。可以看出方案1的映射方案為（1,2,2,2,3），方案2的為（1,1,4,4,4）。類似方案1、方案2的灰狼個體在不斷的迭代中更新優勢狼群，最后得到最優個體并輸出相應的映射方案。

3.3 基于反向學習和非線性收斂的改進灰狼優化算法

標準灰狼優化算法相較于傳統元啟發式算法具有調節參數少、結構簡單、易于實現的優點，已經被廣泛運用在多個領域的優化問題中。但仍然存在后期收斂速度慢，可能會陷入與真實最優解相差很大的局部最優中。針對這兩方面的問題，通過基于反向學習的種群初始化策略及收斂因子非線性優化策略對標準灰狼優化算法進行了改進，提出了改進灰狼優化（IMGWO）算法。

3.3.1 基于反向學習的種群初始化策略

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

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

3.3.2 收斂因子非線性優化策略

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

3.3.3 IMGWO算法工作流程

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

步驟1 設定灰狼種群初始化規模，最大迭代次數，初始化各參數。

步驟2 根據隨機初始化的結果利用反向學習生成初始種群。

步驟3 計算狼群中每個灰狼個體的適應度值，根據適應度值排序選取前三的優勢狼。

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

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

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

3.3.4 IMGWO算法的測試

3.4 映射算法設計

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

表3 測試函數結果

算法2 單節點映射算法

輸出：映射方案

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

算法3 基于改進灰狼優化的服務功能鏈映射算法

輸出：映射方案

4 仿真與結果分析

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

4.1 仿真設計

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

表4 仿真參數

4.2 性能指標

為了驗證網絡功能虛擬化環境中IMGWO- SFCM的可用性，使用服務功能鏈請求接受率、網絡節點計算資源利用率、鏈路帶寬資源利用率、平均部署網絡成本4個性能指標作為仿真分析對象。

4.3 仿真結果分析

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

圖7 服務功能鏈請求接受率

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

圖8 單條服務功能鏈的平均部署網絡成本

整個過程表明了IMGWO-SFCM算法對于網絡拓撲中資源使用情況的優化要優于另外幾種算法，可以為用戶節省服務功能鏈的部署成本。

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

圖9 網絡節點計算資源利用率

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

圖10 鏈路帶寬資源利用率

5 結束語

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

本文研究集中在水平方向于對服務功能鏈進行優化，考慮服務功能鏈中不同的虛擬網絡功能之間存在不產生相互邏輯影響的情況，未來可以通過數據流的復制及兼并實現虛擬網絡功能的并行執行，從垂直的角度進行優化，進一步壓縮服務功能鏈端到端的長度，降低端到端時延。

[1] 彭新玉, 周揚, 董振江. 基于車聯網遠程駕駛的虛擬資源智能協同管理技術[J]. 電信科學, 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] 李卓峰. 低能耗服務功能鏈的映射研究[D]. 成都: 電子科技大學, 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] 湯紅波, 邱航, 游偉, 等. 基于聯合備份的服務功能鏈可靠性保障的部署方法[J]. 電子與信息學報, 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網絡下資源感知的服務功能鏈協同構建和映射算法[J]. 西安交通大學學報, 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] 程洪閃, 孟歡,張曉輝. 服務功能鏈的優化映射策略[J]. 計算機與網絡, 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] 陳學松, 楊宜民. 強化學習研究綜述[J]. 計算機應用研究, 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] 朱國暉, 景文煥, 李世昌. 基于改進麻雀搜索算法的服務功能鏈優化映射算法[J]. 計算機應用研究, 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]. 計算機工程與設計, 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] 劉昀. 虛擬網絡功能資源分配與服務功能鏈路由研究[D]. 合肥: 中國科學技術大學, 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

浙江省自然科學基金資助項目（NO.LY19F020002，No.LY19F020006）；浙江省新型網絡標準與應用技術重點實驗室（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? ），女，浙江工商大學碩士生，主要研究方向為知識圖譜、新一代網絡技術架構。

張俊楠（1997? ），男，浙江工商大學碩士生，主要研究方向為新一代網絡技術架構。

吳曉春（1983? ），女，博士，浙江工商大學高級實驗師、碩士生導師，主要研究方向為新一代網絡技術架構、軟件定義網絡、網絡功能虛擬化、人工智能與網絡安全的結合等。

洪晨（1998? ），女，浙江工商大學碩士生，主要研究方向為知識圖譜、新一代網絡技術架構。

周靜靜（1980? ），女，博士，浙江工商大學副教授、碩士生導師，主要研究方向為新一代網絡技術架構、軟件定義網絡、網絡流量建模與分析、大數據處理、深度學習等。