聯合遺傳算法和強化學習的虛擬網絡功能映射與調度方法

摘要："網絡功能虛擬化環境下，為滿足用戶不同需求并提高資源利用效率，將虛擬網絡功能映射與調度聯合考慮。首先，通過構建網絡低時延、虛擬機資源高利用及能量低損耗的多目標優化模型，設計了一種強化學習（RL）聯合第三代非支配排序遺傳算法（NSGA Ⅲ）的優化方法RL-NSGA Ⅲ；然后，采用兩段式初始化技術求得高質量初始解，利用強化學習的優勢自適應調節交叉變異參數，以保持種群多樣性；最后，基于參考點的第三代非支配排序遺傳算法，將虛擬網絡功能映射至虛擬機并進行調度服務，得到多目標優化策略。仿真結果表明：相較于已有的NSGA Ⅲ、NSGA Ⅱ和MOPSO算法，采用RL-NSGA Ⅲ算法計算得到的時延降低了17%～28%，節點負荷提高了9%～19%，能量損耗降低了12%～26%，表明所提算法在提高網絡速率和降低網絡運營支出上的有效性。

關鍵詞："網絡功能虛擬化；虛擬網絡功能；映射與調度；強化學習；第三代非支配排序遺傳算法

中圖分類號："TP393"文獻標志碼：A

DOI："10·7652/xjtuxb202408018"文章編號：0253-987X（2024）08-0175-10

Function Mapping and Scheduling Method of Virtual Network Combining

Genetic Algorithm and Reinforcement Learning

LIU Guangyuan"1，2， CAO Jingyi"1，2， DU Jie"1，2

（1. School of Information Science and Technology， Shijiazhuang Tiedao University， Shijiazhuang 050043， China;

2. Hebei Provincial Key Laboratory of Electromagnetic Environmental Effects and Information Processing，

Shijiazhuang 050043， China）

Abstract："In order to meet different needs of users and improve resource utilization efficiency in the network function virtualization environment， this paper examines virtual network function mapping and scheduling together. Firstly， an optimization method RL-NSGA Ⅲ based on reinforcement learning （RL） combined with the third-generation non-dominated sorting genetic algorithm （NSGA Ⅲ） is designed by constructing a multi-objective optimization model with low network delay， high utilization of virtual machine resources and low energy loss. Then， the two-stage initialization technique is used to obtain a high-quality initial solution， and RL’s advantage is used to adjust the crossover and variation parameters adaptively to maintain the diversity of the population. Finally， NSGA Ⅲ based on reference points is used to map virtual network functions for virtual machines and perform scheduling services to obtain a multi-objective optimization strategy. The simulation results show that compared with the existing methods NSGA Ⅲ， NSGA Ⅱ and MOPSO， the RL-NSGA Ⅲ method reduces latency by 17% to 28%， improves node load by 9% to 19%， and reduces energy loss by 12% to 26%， which verifies the effectiveness of the proposed method in improving network speed and reducing network operating expenses.

Keywords："network function virtualization; virtual network function; mapping and scheduling; reinforcement learning; the third generation of non-dominated sorting genetic algorithm

在傳統網絡中，網絡功能的實現通常要依靠部署專用的硬件設備，若想擴寬或者增加網絡功能，則需要更換或者部署新設備"［1］。然而，專用網絡設備成本高，能量開銷大，靈活性差，給網絡運營管理人員帶來諸多不便"［2］。為了克服傳統網絡引起的困難，適應當前網絡需求，電信公司提出了網絡功能虛擬化（network function virtualization， NFV）技術"［3］。NFV技術是將軟件與硬件進行解耦，通過虛擬化技術，在已有商用設備上以軟件的形式實現各種各樣的網絡功能，以便隨時供給網絡需求，這樣不僅減緩了傳統網絡對硬件的約束，改善了網絡的靈活性，也降低了依賴硬件所產生的成本"［4-6］。

在NFV環境中，根據虛擬網絡功能（virtual network function， VNF）的類型、功能以及用戶的實際需求，將其進行有序組合，編排形成特定網絡功能的服務功能鏈（service function chain， SFC）。通過NFV部署，網絡功能的編排和管理均變得十分便捷。針對特定的網絡功能需求，運營商可以實時將虛擬網絡功能映射在虛擬機節點上進行實例化調度服務"［7］。

雖然網絡功能虛擬化技術具有諸多優勢，但隨著時代的快速發展及技術的不斷革新，人們在享受網絡帶來方便的同時，又對網絡提出了新的要求。根據不同用戶需求，虛擬網絡功能映射與調度有不同的優化目標"［8］。對于虛擬現實（VR）設備、微型手術機器人、短視頻平臺、語音IP服務商來說，他們對網絡的實時傳輸速率有較高要求，在一定程度下，低時延是優化的首要目標。對于網絡數據中心、5G網絡基站而言，在網絡正常運行的基礎上，節省能耗是他們優化的首要目標。

網絡功能虛擬化是SFC根據網絡需求的變化，動態地將VNF映射到虛擬機上進行實例化調度服務。因此，隨著業務需求的變化和網絡請求分配調度的結束，網絡負載變得不均衡，大量的資源碎片降低了物理資源利用率，導致網絡請求接受率低下，浪費物理資源的同時增加了能量損耗。

在網絡功能虛擬化背景下，為滿足用戶需求、降低網絡時延及能量損耗，本文將強化學習算法（RL）與第三代非支配排序遺傳算法（NSGA Ⅲ）相結合，設計了RL-NSGA Ⅲ算法。該算法通過優化虛擬節點映射與功能調度順序，可有效降低端到端網絡整體時延，提高虛擬機工作負荷，降低能量損耗。本文的主要貢獻如下：

（1）在網絡功能虛擬化環境下，根據其特性建立了低時延、低能耗、虛擬機高利用率的映射與調度模型；

（2）設計了一種自適應交叉及變異參數的RL-NSGA Ⅲ算法，將虛擬網絡功能動態映射到虛擬節點，同時優化功能調度排序，得到映射與調度最優方案；

（3）將本文方法與其他現有方法進行比較，驗證了方法的有效性。

本文結構如下：第1節，對研究人員在虛擬網絡功能映射與調度方面的工作進行簡要總結；第2節，對虛擬網絡功能映射與調度進行描述，構建相關網絡模型；第3節，對RL-NSGA Ⅲ多目標映射與調度算法進行介紹；第4節，采用上述網絡模型和算法進行仿真實驗研究，并將所提方法與其他現有算法進行對比，展示本方法的優越性；第5節，對文章進行總結，并展望了未來的工作。

1"相關工作

與本文相關的研究工作大多集中在針對VNF映射或調度的單一問題上。文獻［8］提出VNF調度本身為非確定性多項式（NP-hard）問題，從而以總服務時延最短為目標，研究了VNF調度延遲的特定問題，并通過建立整數線性模型，設計了一種基于貪婪的啟發式算法進行優化求解，結果表明所提算法降低了網絡總體服務時延。文獻［9］針對模擬部署衛星VNF映射到底層物理網絡時延過大的問題，提出了一種維特比（Viterbi）算法與圖形模式匹配相結合的動態映射方法，結果表明所提算法能夠有效降低網絡時延，并減少資源消耗。文獻［10］在VNF映射相關問題中，提出采用第二代非支配排序遺傳算法（NSGA Ⅱ）優化求解，結果表明該算法能夠提高物理資源利用率及減少物理主機的數量，并具有魯棒性。文獻［11］為了在物聯網環境中解決VNF映射相關問題，提出了一種新的基于模糊推理的方法，通過優化VNF映射機制以及VNF動態實例化，以滿足特定的服務需求。文獻［12］為提高物理資源利用率，提出了一種服務功能鏈的設計及VNF映射算法，采用整數線性規劃模型在小規模網絡中求出總帶寬消耗（TBC）的最優解，結果表明在不同的網絡場景下，該方法都能夠有效地降低帶寬消耗。文獻［13］以服務功能鏈中所有VNFs調度的執行時間最小化為目的，提出了一種討價還價的分布式帶寬策略，并引入多層編碼遺傳算法求解VNF模型，驗證了算法的有效性。文獻［14］考慮了VNF傳輸和處理延遲，以最小化端到端網絡服務的總延遲為目標，通過改進遺傳算法的交叉變異，降低了問題的復雜性，結果表明改進的遺傳算法可以有效降低端到端網絡延遲。文獻［15］將NFV環境中的SFC調度問題表述為混合整數非線性規劃，以滿足延遲和可靠性約束請求數量的最大化為目標，采用改進的強化學習算法學習SFC調度策略，提高了SFC調度請求的成功率，實驗結果表明：改進強化學習算法的調度請求成功率明顯高于基準算法。

由于多數情況下SFC是動態達到，VNF映射情況未知，不同節點的運算及資源存儲能力具有較大差異，因此將VNF映射在不同的節點上，導致服務功能鏈調度的完成時間、物理資源利用率、網絡服務能量損耗等均有較大差異。VNF映射和VNF調度兩階段緊密相連，二者統籌考慮既是當前技術趨勢，又是NFV實施過程中面臨的巨大挑戰。雖然VNF映射和VNF調度聯合優化技術尚不成熟，但隨著學者對VNF映射和VNF聯合優化的關注，目前在該方面也有一些成果。

文獻［16］聯合VNF布局和調度問題，將其表述為整數線性規劃（ILP）問題，并提出了基于貪婪和基于禁忌搜索兩種啟發式算法來解決該問題，實驗結果表明所提方法實現了較大收益。文獻［17］綜合考慮網絡服務VNF映射和調度，將其描述為一個靈活的作業車間調度問題，以優化最大與最小公平性、同時確保不同服務鏈的延遲為目標，提出了一種基于離線近端策略優化的深度強化學習方法，該方法基于未完成的SFC狀態，能夠動態地確定映射和調度決策，結果表明該算法在服務公平性、接受率兩方面均優于傳統的隨機森林和貪婪算法。

針對VNF映射與調度優化的相關問題，雖然學者們已提出許多模型和解決方案，但當前研究仍存在以下問題：①大多數文獻僅考慮虛擬網絡功能映射或調度的單一問題，少有文獻將其進行聯合優化；②優化的目標較少。在實際的虛擬網絡功能映射與調度問題中，應將網絡服務的時延、能耗及虛擬機的利用率這3種影響因素結合起來研究；③使用啟發式算法，未對參數因子進行自適應，影響解的質量。

2"物理網絡與問題模型

2.1"物理網絡模型

在問題模型中，底層物理網絡用無向圖"G=（A，E）表示，其中A為分布式資源服務池中為網絡執行實例化服務的虛擬機（virtual machine，VM），數量為m，可表示為Aj（j=1，2，…，m），或Ao（o=1，2，…，m）；E為物理鏈路的集合，E=（Aj，Ao）|Aj，Ao，A"j，ogt;0[JB）}]，其中A"j，o表示兩節點之間的鏈路。

2.2"VNF映射與調度模型

在端到端網絡中，當客戶端對網絡產生需求時，會對網絡端發出網絡服務請求，網絡端根據網絡數據流量特性，選取k個大小合適的VNF，按特定的順序組建n條SFC。此時，VNF可表示為vh（ h=1，2，…，k），SFC可表示為fi（i=1，2，…，n）。

SFC組建完成后，需要將VNF進行映射并調度。VNF映射問題也被稱作轉發圖嵌入（FGE）問題，是一個NP-hard問題。映射階段的主要任務是有效地將VNF 映射到可執行實例化服務器上，該階段也是影響網絡服務性能和資源利用的關鍵"［13］。VNF通常可映射在多個服務器上，但VNF只能被一個虛擬機執行實例化，故在該階段，需將VNF與VM一對多的映射關系形成集合列表，然后將VNF與VM進行一對一映射后進行調度服務。每個虛擬節點VM可對不同功能大小的VNF進行實例化服務，例如，當vh選擇虛擬機Aj進行映射，則vh將在Aj上進行實例化調度服務，此時vh在虛擬節點Aj進行實例化服務的產出時延為t"fivhAj，其中fivhAj∈（0，1），fivhAj為1表示虛擬任務在該虛擬機中執行實例化完成。此外，虛擬網絡功能數據流量l"vh從虛擬節點Aj到Ao進行虛擬鏈路傳輸，產生的傳輸時延為t"l"vh。

SFC映射實例如圖1所示。其中，SFC1、SFC2為2條待映射的服務功能鏈，分別由3個不同功能的VNF組建而成。VNF1-1代表服務功能鏈SFC1上的第一個虛擬網絡功能，根據約束條件只能被映射到虛擬機A1進行實例化服務；VNF1-2對應A2、A3，代表VNF1-2可以選擇映射至A2或者A3進行實例化服務；VNF1-3對應A3、A5、A6，代表VNF1-3可以映射至A3、A5或者A6進行實例化服務。余者同理。

VNF映射與調度階段的約束條件可表示為

t"ini+t"fivhAj≤t"fin≤t"fiv"h+1（1）

式中：t"ini表示fi上vh開始執行實例化時間；t"fivhAj表示fi上vh在虛擬機節點Aj上執行實例化所用時間；t"fin表示fi上vh執行完成時間；t"fiv"h+1表示fi上v"h+1開始執行實例化時間。

在同一時間內，一個VM只能對一個VNF進行實例化服務，表示如下

t"fivh+t"fivhAj≤t"fcvp+z（1－y"fivhfcvpAj）（2）

t"fivh≤t"fiv"h+1+z（1－y"fiv"h+1fcvpAj）（3）

式中：z為正整數；y"fivhfcvpAj為二值變量，其值為1表示fi上vh先于服務功能鏈fc上的vp在Aj上執行調度，其值為0表示fi上vh不先于fc上的vp在Aj上執行調度。

一個VNF只能選擇一個VM映射后進行實例化調度服務，寫為

∑[DD（]"m"ih"j=1[DD）]fivhAj=1（4）

式中：m"ih表示第i條服務功能鏈上第h個VNF可映射虛擬機的個數。

2.3"優化目標

映射集合階段存在VNF映射一個或多個物理節點，而VNF僅需選取一個物理節點執行實例化節點，于是如何選取物理節點將VNF進行映射與排序調度，將會直接影響到鏈路傳輸時延和實例化執行時延。不同學者在VNF映射與調度問題的研究上有著不同的目標。本文的主要優化目標如下。

（1）VNF映射與調度服務時延目標，表示為

T=min[JBlt;2（]max[JB（（]∑[DD（]"n，k，m"i=1，h=1，j=1[DD）]t"fivhAj[JB））]+∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fivht"l"vh[JBgt;2）]（5）

（2）VNF映射與調度服務虛擬機工作負荷目標，表示為

W=∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]∑[DD（]m"j=1[DD）]fivhAjt"fivhAjpj（6）

式中：pj為虛擬機節點Aj的流量負載功率。

（3）VNF映射與調度服務能量損耗目標，表示為

E=∑[DD（]m"j=1[DD）]（∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fivhAjt"fivhAjpj+

（tj－∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fivhAjt"fivhAj）uj）（7）

式中：uj為虛擬機節點Aj空載功率；tj為虛擬機節點Aj上任務完成的時間。

3"RL-NSGA Ⅲ映射與調度算法

虛擬網絡任務映射與調度優化是多目標優化求解問題，學者們提出采用高維多目標進化算法來解決此類問題。根據多目標進化機制的不同，可分為基于非支配關系的多目標進化算法、基于分解的多目標進化算法、基于指標的多目標進化算法等。現階段，啟發式基于非支配關系的多目標進化算法有著較多的研究成果。NSGA系列算法在求解多目標任務時也受到了諸多學者的青睞，可目前仍存在一些問題，如NSGA Ⅱ算法采用擁擠度和擁擠度比較算子，代替了需要指定共享半徑的適應度共享策略，但在高維目標空間中的作用并不明顯；NSGA Ⅱ 算法在求解兩個以上目標時表現得力不從心，且隨著求解目標的增多求解性會逐漸變差。NSGA Ⅲ算法"［19］是在NSGA Ⅱ算法的基礎上改進而來，雖然二者具有相似的算法框架，但選擇機制有較大不同。NSGA Ⅲ算法對擁擠度排序進行了較大修改，通過引入廣泛分布參考點維持種群的多樣性，能夠適應較多的求解目標，從而解決了VNF映射與調度的多目標問題。

NSGA Ⅲ算法是在遺傳算法基礎上演變而來，交叉變異操作對求解結果有著至關重要的作用，如果交叉或變異參數過大，種群中較合適的個體容易被摧毀丟失，不利于解的收斂和最優解；如果交叉或變異參數太小，則很難產生新的個體"［20］，不利于得到最優解。在傳統的NSGA系列求解算法中，交叉變異參數經常是固定，然而隨著算法迭代求解過程進行，固定的交叉變異概率會影響多樣性。

為避免固定交叉變異因子的影響，以求得高質量的解，本文設計了一種自適應多目標求解算法RL-NSGA Ⅲ，首先，采用VNF-VM兩段式初始化方法對VNF、VM分別進行初始化，在保留種群多樣性的同時提高初始解的質量；其次，采用強化學習的演員-評論家（actor-critic，AC）算法，隨著算法迭代，根據過去和未來的狀態做出適當預測，自適應地調節交叉變異參數；最后，通過第三代非支配排序，對VNF映射與調度所產生的時延、能量損耗、虛擬機負荷3個目標進行聯合優化求解。

3.1"種群初始化

在使用啟發式算法求解該類問題時，學者常常使用集成編碼的方式，該方式雖然簡單，但因基因過多，在交叉變異過程中極易出現非法解。為了避免非法解的產生并保持種群多樣，采用VM-VNF兩段式方法對染色體進行編碼，設定VM部分染色體長度為∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fivh，然后依次按照虛擬網絡功能和調度順序進行編碼排序。

VM-VNF編碼分為兩部分，以下給出3條服務功能鏈上共8個虛擬網絡功能、6個虛擬機編碼的初始化實例。設置染色體ci=［13121214|12131223］，其中前8個數值表示VM選擇結果，為f1v1、f1v2、f1v3、f2v1、f2v2、f2v3、f3v1、f3v2，分別對應可執行實例化服務的虛擬機集合中的編號，第一個數值1，表示f1v1對應可執行實例化服務的虛擬機集合列表中的第1個，如f1v1可執行實例化服務的虛擬機列表中有A1，A2，A3，…，對應的編號1即代表A1；第二個數值3，表示f1v2對應可執行實例化服務的虛擬機集合列表中的第3個，如f1v2可執行實例化服務的虛擬機列表有A1，A3，A5，…，對應的編號3即代表A5。根據虛擬機選擇，可得出f1v1、f1v2、f1v3、f2v1、f2v2、f2v3、f3v1、f3v2選擇的機器號分別為A1、A5、A2、A2、A4、A3、A1、A6。染色體中后8個數值表示VNF的排序結果，即虛擬網絡功能執行調度的順序，對該段染色體從左到右進行編碼，數值對應服務功能鏈，則該部分染色體虛擬網絡功能排序為：f1v1→f2v1→f1v2→f3v1→f1v3→f2v2→f2v3→f3v2。

3.2"交叉變異操作

初始化部分采用兩段式編碼方式，故種群需要分別對VM、VNF進行交叉變異，以生成新的個體。為保證種群的多樣性，根據編碼中每個基因先后順序不變的特點，VM選擇時采用均勻交叉和隨機點變異"［16］方式，VNF排序時為保留父代特性，采用POX交叉方式。

取出染色體ci中代表虛擬機選擇部分的∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fvivh基因因子，在該區間內隨機產生r個互不相等的整數，根據產生的整數將父代虛擬機選擇部分染色體c1與c2中對應的基因分別復制給子代虛擬機選擇部分染色體c"2，1與c"2，2并保持其位置與順序，再將剩余的基因分別復制給子代虛擬機選擇部分染色體c"2，2與c"2，1并保持其位置與順序。虛擬機選擇部分經過交叉生成了新的個體。取出染色體ci中代表虛擬網絡任務排序部分的基因因子，將其隨機劃分為兩個網絡任務排序集合VNF1、VNF2，將父代虛擬網絡任務部分染色體c1與c2中包含在VNF1/VNF2中的虛擬網絡任務，復制到子代虛擬網絡任務部分染色體c"2，1與c"2，2中保持其位置和順序，其余VNF1/VNF2中的虛擬網絡任務復制到子代虛擬網絡任務部分染色體c"2，2與c"2，1并保持其位置與順序。

在虛擬網絡任務不進行變異的前提下，虛擬機選擇部分采用隨機多點變異，即在變異染色體ci中選取代表虛擬機選擇部分的∑[DD（]n"i=1[DD）]∑[DD（]k"h=1[DD）]fvivh基因因子，隨機選取多個基因位，依次將基因上的虛擬機設定為當前虛擬網絡可執行實例化服務所用時間最短的虛擬機。

3.3"非支配排序

在虛擬網絡任務多目標優化求解問題中，非支配排序是關鍵部分，由于執行與傳輸時延、虛擬機負荷、能量損耗多個目標相互作用及相互影響，導致優化方向具有不一致性，有時多個目標無法全部求取最優解，因而在該階段需要將多個目標之間進行整體優化，實現均衡可行。

第三代非支配排序算法是在第二代算法的基礎上，引入廣泛分布參考點以維持種群的多樣性。第三代非支配排序求解的主要步驟如下。

步驟一"通過交叉變異獲得子代種群Qt，將父代種群Pt與生成的子代種群Qt合并成為種群Rt，t表示代的數量。

步驟二"求出理想點Z"min，對種群Rt進行非支配排序，形成若干非支配層F1，F2，F3，…，Fl，l表示層數。從F1層開始，依次選擇個體放入個體集St中，到Fl層時，依次選取最不擁擠的參考點以及距離該參考點最近的點，直到K個個體完全加入到St中。

3.4"AC調節參數

RL-NSGA Ⅲ算法由環境、狀態、動作集合、獎賞4個模塊組成。該算法將NSGA Ⅲ算法當作環境，將交叉變異概率作為動作集合，隨著算法迭代，環境狀態從當前狀態變為下一步狀態，再根據算法做出的動作得到獎勵。一旦環境和狀態進行變化，AC算法需要重新進行探索學習，適應新的狀態空間。此外，狀態數目過大或無限，均會影響價值函數和策略函數的計算能力，進而影響算法的性能。本文根據文獻［20］定義環境狀態的范圍，研究服務時延（記為x）、工作負荷（記為y）、能量損耗（記為z）3個目標整體最優，故將獎勵設定為3個目標即x、y、z的加權回報最高。AC調節NSGA Ⅲ算法的流程如圖2所示。

圖2所示流程圖的具體描述如下。

①狀態： 強化學習所在的環境狀態為NSGA Ⅲ算法中交叉變異的概率數值。根據文獻［20］定義交叉參數pc，取值為0.4～0.9，每個動作間隔為"0.05；變異參數pm，取值為0.01～0.21，每個動作間隔為0.02。

②動作：在算法的每一次迭代時，智能體均會選取合適的pc、pm，強化學習在未知環境中進行探索，通過不斷嘗試做出的動作得到回報，智能體在NSGA Ⅲ每一次迭代過程中選擇一組pc、pm。

③獎勵：智能體通過做出的動作得到獎勵，由于文本的優化目標有3個，且方向具有不一致性，故需要對3個適應度進行加權處理，通過歸一化加權處理得到整體的優化目標，表示如下

Yt=wxaxx+wyayy+wzazz（8）

式中：wx、wy、wz分別為目標x、y、z的權重；ax、ay、az為目標權重歸一化參數。

將優化的增量作為回報，獎勵函數可寫為

R（t）=Y（t）－Y（t－1）（9）

式中：Y（t）、Y（t－1）分別為t時刻及t-1時刻的回報。

4"仿真實驗

本節中，針對虛擬網絡功能映射與調度聯合優化問題，采用RL-NSGA Ⅲ算法對網絡時延、節點負荷、能量損耗3方面的性能進行評估，通過與現有文獻中較優方案進行對比，驗證本文模型與算法的優越性。

4.1"實驗設置

在Win10操作系統、Intel i7處理器、DDR4 16GB內存、NVIDIA GTX 1050顯卡的環境下，采用Pytorch工具開展仿真實驗，隨后在Openstack平臺上進行部署，以驗證算法的有效性。實驗參數設置與文獻［22］相似，服務功能鏈條數為10～100，服務功能鏈上的虛擬網絡功能個數為3～5，虛擬機節點數為10，虛擬網絡映射的虛擬機節點數為2～4， 虛擬機節點采用全連通的方式。此外，參照文獻［8］將虛擬網絡功能在映射的虛擬節點執行實例化時間設置為10～20ms，對應的傳輸時延設置為5～20ms。服務功能鏈均為可完全到達狀態，虛擬網絡功能均為完全執行實例化服務。

4.2"結果分析

為了驗證本文RL-NSGA Ⅲ算法的優越性，將其與NSGA Ⅲ算法、文獻［10，23］中的NSGA Ⅱ算法、文獻［24-25］中的MOPSO算法在網絡時延、虛擬機節點負荷及能量損耗3個方面的性能進行對比。

首先，采用10條服務功能鏈進行虛擬網絡功能映射與調度服務。為直觀地展示算法性能，圖3給出了本文算法與對比算法所得結果的三維散點圖。由圖可見，對于本文的RL-NSGA Ⅲ算法，優化虛擬網絡功能映射與調度服務的時延穩定在90～110ms，虛擬機節點綜合負荷在590～605W，能量損耗在1000W以下，100次實驗所求得的解均比較集中；而NSGA Ⅱ與MOPSO算法得到的優化虛擬網絡功能映射與調度服務的時延均較長，能量損耗較高，解相對不穩定。相較于其他算法，本文算法在時延、能量損耗等方面均較小，而虛擬機整體負荷較高，表明了資源能夠得到有效利用。由于RL-NSGA Ⅲ算法中，RL需對NSGA Ⅲ算法進行動態調整，從而提升了算法的整體復雜度，導致實驗中CPU的平均執行時間較其他3個算法略長；然而，由于RL-NSGA Ⅲ算法具有較強的自適應能力，相較于其他3個算法能夠較快收斂，所以在平均迭代到第16次時，即可收斂達到最優解。

為了進一步驗證RL-NSGA Ⅲ算法的優越性與穩定性，采用200條服務功能鏈在10個虛擬機節點上進行映射與調度實驗。圖4～圖6分別給出了相同SFC數量下，本文RL-NSGA Ⅲ算法與其他3種算法在映射與調度總時延、虛擬機總負荷及能量損耗方面的對比結果。可見，隨著SFC數量的增加，4種算法的總時延、虛擬機負荷、能量損耗均增大。

從圖4和圖5可以看出，當第一階段SFC數量為20時，本文算法的時延最低，機器負載最高，但總的來說，此時4種算法得到的時延、機器負荷方面差距較小。隨著SFC不斷增加，4種算法的差距明顯增大，本文RL-NSGA Ⅲ算法幾乎成線性且始終保持時延最小，虛擬機負載最大。當200條服務功能鏈服務全部完成時，與NSGA Ⅲ、NSGA Ⅱ和MOPSO算法相比，本文RL-NASGⅢ算法所得到的時延分別減少了17%、25%、28%，機器負荷分別提高了9%、13%、19%。

由圖6可見，隨著服務功能鏈數量增加，4種算法在能量損耗方面逐漸增加，本文RL-NSGA Ⅲ算法的能量損耗最小，這是由于RL-NSGAⅢ算法利用AC算法預測并調節其交叉變異參數，在得到優秀基因的同時保持了種群的多樣性。由于RL-NSGA Ⅲ算法將VNF分配并排序至較空閑的虛擬機，提高了整體利用率，因此有效節省了能耗。與NSGA Ⅲ、NSGA Ⅱ、MOPSO算法相比，本文RL-NASGⅢ算法得到的能量損耗分別降低了12%、19%、26%。

5"結"論

針對虛擬網絡功能映射和調度服務時間長、能量損耗高、物理資源利用率低的問題，構建了低時延、低能耗、虛擬機節點資源高利用的多目標優化模型，設計了一種自適應多目標RL-NSGA Ⅲ算法，將虛擬網絡功能映射和調度服務聯合優化，采用兩段式初始化自適應多目標優化算法，得到了質量的初始解；采用強化學習AC算法控制NSGA Ⅲ交叉變異參數，保留了種群多樣性；采用第三代非支配排序算法將虛擬網絡功能動態映射到合適虛擬機的同時，優化了虛擬網功能調度順序。

仿真結果表明：相較于NSGA Ⅲ、NSGA Ⅱ和MOPSO算法，RL-NSGA Ⅲ算法在時延方面減少了17%～28%，在節點負荷方面提高了9%～19%，能量損耗降低了12%～26%。本文為虛擬網絡功能映射和調度聯合優化問題提供了一種新的思路，接下來將進一步研究網絡功能虛擬化中VNF組鏈、映射、調度系統性問題，并將算法部署到真實的聯通云上進行測試，以提高算法的實用性。

參考文獻：

［1］LI Biyi， CHENG Bo， LIU Xuan， et al. Joint resource optimization and delay-aware virtual network function migration in data center networks ［J］. IEEE Transactions on Network and Service Management， 2021， 18（3）： 2960-2974.

［2］ZHANG Dong， ZHENG Zhifan， LIN Xiang， et al. Dynamic backup sharing scheme of service function chains in NFV ［J］. China Communications， 2022， 19（5）： 178-190.

［3］GIL HERRERA J D J， BOTERO VEGA J F. Network functions virtualization： a survey ［J］. IEEE Latin America Transactions， 2016， 14（2）： 983-997.

［4］孫士清， 彭建華， 游偉， 等. 5G網絡下資源感知的服務功能鏈協同構建和映射算法 ［J］. 西安交通大學學報， 2020， 54（8）： 140-148.

SUN Shiqing， PENG Jianhua， YOU Wei， 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.

［5］王珂， 曲樺， 趙季紅. 多域SFC部署中基于強化學習的多目標優化方法 ［J］. 計算機科學， 2021， 48（12）： 324-330.

WANG Ke， QU Hua， ZHAO Jihong. Multi-objective optimization method based on reinforcement learning in multi-domain SFC deployment ［J］. Computer Science， 2021， 48（12）： 324-330.

［6］唐倫， 賀蘭欽， 連沁怡， 等. 基于改進深度強化學習的虛擬網絡功能部署優化算法 ［J］. 電子與信息學報， 2021， 43（6）： 1724-1732.

TANG Lun， HE Lanqin， LIAN Qinyi， et al. Virtual network function placement optimization algorithm based on improve deep reinforcement learning ［J］. Journal of Electronics amp; Information Technology， 2021， 43（6）： 1724-1732.

［7］劉光遠， 曹晶儀， 龐紫園， 等. 一種低時延虛擬網絡功能映射及調度優化算法 ［J］. 西安交通大學學報， 2023， 57（2）： 121-130.

LIU Guangyuan， CAO Jingyi， PANG Ziyuan， et al. An optimized algorithm with low latency for virtual network function mapping and scheduling ［J］. Journal of Xi’an Jiaotong University， 2023， 57（2）： 121-130.

［8］徐冉， 王文東， 龔向陽， 等. 網絡功能虛擬化中延時感知的資源調度優化方法 ［J］. 計算機研究與發展， 2018， 55（4）： 738-747.

XU Ran， WANG Wendong， GONG Xiangyang， et al. Delay-aware resource scheduling optimization in network function virtualization ［J］. Journal of Computer Research and Development， 2018， 55（4）： 738-747.

［9］魏德賓， 楊鵬， 楊力， 等. 一種基于衛星網絡的虛擬網絡功能快速映射算法 ［J］. 計算機科學， 2020， 47（3）： 248-254.

WEI Debin， YANG Peng， YANG Li， et al. Virtual network function fast mapping algorithm over satellite network ［J］. Computer Science， 2020， 47（3）： 248-254.

［10］"TAVAKOLI-SOMEH S， REZVANI M H. Multi- objective virtual network function placement using "NSGA-Ⅱ meta-heuristic approach ［J］. The Journal of Supercomputing， 2019， 75（10）： 6451-6487.

［11］"TARIQ M A， FAROOQ M U， ZEESHAN M， et al. FIPAM： fuzzy inference based placement and migration approach for NFV-Based IoTs ［J］. IEEE Transactions on Network and Service Management， 2022， 19（4）： 4298-4309.

［12］"朱國暉， 劉璐， 雷蘭潔. 基于VNF組合的服務功能鏈設計及映射算法 ［J］. 計算機工程， 2020， 46（4）： 183-188， 197.

ZHU Guohui， LIU Lu， LEI Lanjie. Service function chain design and mapping algorithm based on VNF combination ［J］. Computer Engineering， 2020， 46（4）： 183-188， 197.

［13］"YUAN Quan， TANG Hongbo， YOU Wei， et al. Virtual network function scheduling via multilayer encoding genetic algorithm with distributed bandwidth allocation ［J］. Science China Information Sciences， 2018， 61（9）： 092107.

［14］"LI Qi， WANG Xing， ZHAO Tao， et al. An improved genetic algorithm for the scheduling of virtual network functions ［C］//2019 20th Asia-Pacific Network Operations and Management Symposium （APNOMS）. Piscataway， NJ， USA： IEEE， 2019： 1-4.

［15］"JIA Junzhong， YANG Lei， CAO Jiannong. Reliability-aware dynamic service chain scheduling in 5G networks based on reinforcement learning ［C］//IEEE INFOCOM 2021-IEEE Conference on Computer Communications. Piscataway， NJ， USA： IEEE， 2021： 1-10.

［16］"PRO MWONGSA N， EBRAHIMZADEH A， GLITHO R H， et al. Joint VNF placement and scheduling for latency-sensitive services ［J］. IEEE Transactions on Network Science and Engineering， 2022， 9（4）： 2432-2449.

［17］"KUAI Zhenran， WANG Tianyu， WANG Shaowei. Fair virtual network function mapping and scheduling using proximal policy optimization ［J］. IEEE Transactions on Communications， 2022， 70（11）： 7434-7445.

［18］"HU Hongchao， ZHANG Fan， MAO Yuxing， et al. A forwarding graph embedding algorithm exploiting regional topology information ［J］. Frontiers of Information Technology amp; Electronic Engineering， 2017， 18（11）： 1854-1866.

［19］"DEB K， JAIN H. An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach： solving problems with box constraints ［J］. IEEE Transactions on Evolutionary Computation， 2014， 18（4）： 577-601.

［20］"CHEN Ronghua， YANG Bo， LI Shi， et al. A self-learning genetic algorithm based on reinforcement learning for flexible job-shop scheduling problem ［J］. Computers amp; Industrial Engineering， 2020， 149： 106778.

［21］"張韻， 鐘慧超， 張春江， 等. 基于機器學習的多策略并行遺傳算法 ［J］. 計算機集成制造系統， 2021， 27（10）： 2921-2928.

ZHANG Yun， ZHONG Huichao， ZHANG Chunjiang， et al. Multi-strategy parallel genetic algorithm based on machine learning ［J］. Computer Integrated Manufacturing Systems， 2021， 27（10）： 2921-2928.

［22］"王琛， 湯紅波， 游偉， 等. 一種5G網絡低時延資源調度算法 ［J］. 西安交通大學學報， 2018， 52（4）： 117-124.

WANG Chen， TANG Hongbo， YOU Wei， et al. A resource scheduling algorithm with low latency for 5G networks based on effective hybrid genetic algorithm and Tabu search ［J］. Journal of Xi’an Jiaotong University， 2018， 52（4）： 117-124.

［23］"GAMAL M， JAFARIZADEH S， ABOLHASAN M， et al. Mapping and scheduling for non-uniform arrival of virtual network function （VNF） requests ［C］//2019 IEEE 90th Vehicular Technology Conference （VTC2019-Fall）. Piscataway， NJ， USA： IEEE， 2019： 1-6.

［24］"CHANTRE H D， DA FONSECA N L S. Multi-objective optimization for edge device placement and reliable broadcasting in 5G NFV-based small cell networks ［J］. IEEE Journal on Selected Areas in Communications， 2018， 36（10）： 2304-2317.

［25］"WANG Ranyin， AGHVAMI H， FRIDERIKOS V. An end-to-end network slicing design policy ［C］//2020 IEEE 31st Annual International Symposium on Personal， Indoor and Mobile Radio Communications. Piscataway， NJ， USA： IEEE， 2020： 1-6.

（編輯"李慧敏"劉楊）