基于強(qiáng)化學(xué)習(xí)的高可靠性多域虛擬網(wǎng)絡(luò)映射算法

收稿日期：2021-10-27；修回日期：2021-12-17

基金項(xiàng)目：國家自然科學(xué)基金資助項(xiàng)目（61531013）；國家重點(diǎn)研發(fā)計(jì)劃重點(diǎn)專項(xiàng)資助項(xiàng)目（2018YFB1800300）

作者簡介：趙季紅（1964-），女，陜西西安人，教授，博導(dǎo)，主要研究方向?yàn)閹捦ㄐ啪W(wǎng)、新一代網(wǎng)絡(luò)的管理和控制、物聯(lián)網(wǎng)、語義Web、異構(gòu)融合網(wǎng)絡(luò)、網(wǎng)絡(luò)虛擬化；宋航（1996-），男（通信作者），陜西西安人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)虛擬化、資源分配（1150331856@qq.com）；曲樺（1961-），男，陜西西安人，教授，博導(dǎo)，主要研究方向?yàn)楝F(xiàn)代通信網(wǎng)、計(jì)算機(jī)網(wǎng)絡(luò)體系結(jié)構(gòu)、5G網(wǎng)絡(luò)關(guān)鍵技術(shù)、新一代網(wǎng)絡(luò)技術(shù)等；雷智麟（1996-），男，河南南陽人，碩士研究生，主要研究方向?yàn)榫W(wǎng)絡(luò)切片、服務(wù)功能鏈部署.

摘 要：現(xiàn)有的虛擬網(wǎng)絡(luò)映射算法大多是依賴于人工規(guī)則對節(jié)點(diǎn)進(jìn)行排序，決定節(jié)點(diǎn)先后映射的順序，來優(yōu)化節(jié)點(diǎn)映射從而提高虛擬網(wǎng)絡(luò)請求的成功率。而在鏈路映射階段普遍采用廣度優(yōu)先搜索算法，忽略了節(jié)點(diǎn)資源和鏈路資源具有強(qiáng)相關(guān)性的特點(diǎn)，從而只能取得局部最優(yōu)的映射結(jié)果。針對上述問題，基于5G多域異構(gòu)網(wǎng)絡(luò)環(huán)境，從網(wǎng)絡(luò)的可生存性的保護(hù)角度出發(fā)，提出一種使用雙層強(qiáng)化學(xué)習(xí)的虛擬網(wǎng)絡(luò)映射算法。將強(qiáng)化學(xué)習(xí)同時(shí)應(yīng)用于網(wǎng)絡(luò)映射的節(jié)點(diǎn)和鏈路兩階段，使用梯度策略和反向傳播的方法對該網(wǎng)絡(luò)模型進(jìn)行訓(xùn)練，并使用此訓(xùn)練模型完成映射。仿真結(jié)果表明，與對比算法相比，該算法在優(yōu)化節(jié)點(diǎn)映射的同時(shí)優(yōu)化了鏈路映射，且在映射成功率、長期收益率、節(jié)點(diǎn)和鏈路的利用率等方面均取得較好結(jié)果。

關(guān)鍵詞：5G多域網(wǎng)絡(luò)； 虛擬網(wǎng)絡(luò)映射； 強(qiáng)化學(xué)習(xí)； 映射策略網(wǎng)絡(luò)

中圖分類號：TP393.01"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2022）06-035-1809-05

doi：10.19734/j.issn.1001-3695.2021.10.0594

High-reliability multi-domain virtual network mapping algorithm based on reinforcement learning

Zhao Jihong1，2， Song Hang1， Qu Hua2， Lei Zhilin1

（1.School of Communication amp; Information Engineering， Xi’an University of Posts amp; Telecommunications， Xi’an 710121， China; 2.School of Electronic amp; Information Engineering， Xi’an Jiaotong University， Xi’an 710049， China）

Abstract：Most of the existing virtual network mapping algorithms rely on manual rules to sort nodes and determine the sequence of node mapping so as to optimize node mapping and improve the success rate of virtual network requests. In the link mapping stage， it generally uses the breadth-first search algorithm， ignoring the strong correlation between node resources and link resources， so that it can only obtain local optimal mapping results. In response to the above problems， based on the 5G multi-domain heterogeneous network environment， from the perspective of network survivability protection， this paper proposed a virtual network mapping algorithm using two-layer reinforcement learning. It applied reinforcement learning to both the node and link stages of network mapping， used the gradient strategy and back propagation method to train the network model of this paper， and used the training model of this paper to complete the mapping. The simulation results show that， compared with the comparison algorithms， the algorithm optimizes the link mapping while optimizing the node mapping， and achieves better results in the mapping success rate， long-term return rate， and node and link utilization rate.

Key words：5G multi-domain network; virtual network mapping; reinforcement learning; mapping strategy network

0 引言

伴隨著互聯(lián)網(wǎng)的快速發(fā)展，傳統(tǒng)網(wǎng)絡(luò)架構(gòu)越來越僵化，無法高效靈活地利用網(wǎng)絡(luò)資源。業(yè)界普遍認(rèn)為，解決網(wǎng)絡(luò)僵化的最優(yōu)方案是網(wǎng)絡(luò)虛擬化［1］。網(wǎng)絡(luò)虛擬化是對網(wǎng)絡(luò)資源進(jìn)行抽象、分配、隔離的一種機(jī)制，可以實(shí)現(xiàn)多個(gè)虛擬網(wǎng)絡(luò)同時(shí)共享單個(gè)物理網(wǎng)絡(luò)的目的。虛擬網(wǎng)絡(luò)（virtual network，VN）可以根據(jù)用戶的不同需求完成對底層資源的合理劃分，從而為用戶提供最優(yōu)的服務(wù)［2］。在網(wǎng)絡(luò)虛擬化的環(huán)境中，基礎(chǔ)設(shè)施提供商（infrastructure provider，InP）負(fù)責(zé)管理物理網(wǎng)絡(luò)（substrate network，SN）的資源，服務(wù)提供商（service provider， SP）通過各自租用InP的資源來構(gòu)建自己的虛擬網(wǎng)絡(luò)［3］。虛擬網(wǎng)絡(luò)技術(shù)使得在同一個(gè)物理網(wǎng)絡(luò)上可以生成多個(gè)虛擬網(wǎng)絡(luò)，或?qū)⒉煌奈锢砭W(wǎng)絡(luò)相互連接，形成跨域的虛擬網(wǎng)絡(luò)［4］。這些虛擬網(wǎng)絡(luò)可以獨(dú)立地進(jìn)行部署和管理并且互相并不干擾。在這種靈活的多層架構(gòu)中，InP面臨的問題是如何有效地管理物理網(wǎng)絡(luò)資源，盡可能地服務(wù)更多的虛擬網(wǎng)絡(luò)請求（virtual network request，VNR），從而獲取最大收益［5］。事實(shí)上，InP必須在線確定物理節(jié)點(diǎn)和鏈路的需求資源（計(jì)算能力、鏈路帶寬）來完成一組有約束條件的VNR。在網(wǎng)絡(luò)虛擬化問題中，最大的挑戰(zhàn)就是多個(gè)VN之間如何高效地共享SN資源［6］。虛擬網(wǎng)絡(luò)映射算法（virtual network embedding，VNE）的好壞將直接決定SN的利用率和InP的長期收益。眾多學(xué)者也相繼提出了啟發(fā)式VNE算法［7］和基于機(jī)器學(xué)習(xí)的VNE算法［8，9］，合理化利用節(jié)點(diǎn)和鏈路資源。

然而啟發(fā)式算法缺乏有效的迭代終止條件，對收斂速度要求較高，時(shí)間復(fù)雜度較高，面對復(fù)雜問題不能及時(shí)解決［10］。但面對接收到的大量數(shù)據(jù)，機(jī)器學(xué)習(xí)可以進(jìn)行及時(shí)有效的處理，完成對信息的分類或預(yù)測。強(qiáng)化學(xué)習(xí)作為機(jī)器學(xué)習(xí)領(lǐng)域中的典型應(yīng)用，在面對復(fù)雜任務(wù)時(shí)展現(xiàn)出巨大潛力［11］。強(qiáng)化學(xué)習(xí)借助agent以試錯(cuò)的方法來與環(huán)境進(jìn)行交互信息，尋找最佳方案，以達(dá)到agent獲得最大收益的目的［12］。目前已有一些機(jī)器學(xué)習(xí)的方法應(yīng)用在虛擬網(wǎng)絡(luò)映射中，并取得突破性的進(jìn)展。文獻(xiàn)［13］提出了蒙特卡羅樹算法，把兩階段法中節(jié)點(diǎn)映射的決策視為馬爾可夫決策過程，當(dāng)VNR到來時(shí)，使用搜索樹進(jìn)行決策，并且可以根據(jù)VNR到來的繁忙程度，動(dòng)態(tài)地調(diào)整算法復(fù)雜度，尋求最佳方案。文獻(xiàn)［14］將神經(jīng)網(wǎng)絡(luò)算法引入了虛擬網(wǎng)絡(luò)映射問題，提出了一種基于人工神經(jīng)網(wǎng)絡(luò)的系統(tǒng)來更加靈活地使用資源。通過將物理節(jié)點(diǎn)和鏈路轉(zhuǎn)換為人工智能神經(jīng)網(wǎng)絡(luò)，輸入底層網(wǎng)絡(luò)資源狀態(tài)，輸出決策結(jié)果，之后再通過強(qiáng)化學(xué)習(xí)的誤差函數(shù)來優(yōu)化人工神經(jīng)網(wǎng)絡(luò)的輸出結(jié)果，完成整個(gè)映射過程;但該算法只探究了單域的情況，而忽略了多域的虛擬網(wǎng)絡(luò)。Blenk等人［15］等提出使用循環(huán)神經(jīng)網(wǎng)絡(luò)預(yù)測虛擬網(wǎng)絡(luò)請求能否成功。Yao等人［10］提出基于強(qiáng)化學(xué)習(xí)的映射算法，使用策略網(wǎng)絡(luò)自動(dòng)調(diào)整節(jié)點(diǎn)映射中的參數(shù)，輸入底層節(jié)點(diǎn)的特征矩陣，輸出各物理節(jié)點(diǎn)的映射概率，用廣度優(yōu)先搜索算法完成鏈路映射，但忽略了底層節(jié)點(diǎn)和鏈路資源的具有強(qiáng)相關(guān)性的特點(diǎn)。

綜上所述，現(xiàn)有的大多數(shù)虛擬網(wǎng)絡(luò)映射算法都是基于核心網(wǎng)的單域映射算法，以長期收益率和映射成功率為目標(biāo)，很少關(guān)注5G多域異構(gòu)網(wǎng)絡(luò)和虛擬網(wǎng)絡(luò)映射的可生存性的問題，并且在可生存性方面大多都是從故障發(fā)生后的恢復(fù)方面入手，而恢復(fù)需要在故障發(fā)生后重新計(jì)算映射路徑，需要較多時(shí)間。事實(shí)上，在故障發(fā)生前的部署階段，對映射的結(jié)果極為重要。本文提出了雙層強(qiáng)化學(xué)習(xí)的網(wǎng)絡(luò)映射算法，從虛擬網(wǎng)絡(luò)映射的可生存性的保護(hù)角度出發(fā)，將強(qiáng)化學(xué)習(xí)同時(shí)應(yīng)用于節(jié)點(diǎn)映射和鏈路映射，使用梯度策略和反向傳播的方式對模型進(jìn)行訓(xùn)練，在優(yōu)化節(jié)點(diǎn)映射的同時(shí)優(yōu)化鏈路映射，從而得到更優(yōu)的映射結(jié)果。

1 多域異構(gòu)網(wǎng)絡(luò)模型

考慮到網(wǎng)絡(luò)規(guī)模大、網(wǎng)絡(luò)異構(gòu)等因素，網(wǎng)絡(luò)控制系統(tǒng)需要分域控制，根據(jù)地域、功能域等因素劃分網(wǎng)絡(luò)實(shí)現(xiàn)分域控制。如圖1所示，本文基于5G多域異構(gòu)網(wǎng)絡(luò)環(huán)境中，底層網(wǎng)絡(luò)的資源和基礎(chǔ)設(shè)施的拓?fù)湫畔⑹悄芊裢瓿捎成涞年P(guān)鍵。其中底層網(wǎng)絡(luò)節(jié)點(diǎn)分為無線接入網(wǎng)絡(luò)節(jié)點(diǎn)、傳輸網(wǎng)節(jié)點(diǎn)、核心網(wǎng)絡(luò)節(jié)點(diǎn)。將底層網(wǎng)絡(luò)構(gòu)建成一個(gè)無向圖GS=（NS，IS，ASN，ASL），其中NS和IS分別表示底層網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的集合。為了便于建立模型和仿真，網(wǎng)絡(luò)資源抽象描述為節(jié)點(diǎn)和鏈路資源。其中ASN和ASL表示所有底層節(jié)點(diǎn)和鏈路屬性。使用無向圖GV=（NV，LV，CVN，CVL）來表示一個(gè)VNR，其中NV和LV表示VNR的節(jié)點(diǎn)和鏈路的集合，CVN和CVL表示節(jié)點(diǎn)屬性和鏈路屬性。當(dāng)一個(gè)VNR到來時(shí)，底層網(wǎng)絡(luò)資源必須大于該請求所需資源，即CVL（NV，LV）→GS（NS，LS），且NV∈NS、LV∈LS。圖1簡單地表示了一個(gè)完整的VNR映射圖。最底層是5G多域異構(gòu)網(wǎng)絡(luò)實(shí)體，其中無線接入網(wǎng)域由龐大的終端用戶、物聯(lián)網(wǎng)設(shè)備、無線網(wǎng)基站等構(gòu)成。傳輸網(wǎng)負(fù)責(zé)將網(wǎng)元數(shù)據(jù)傳送到另一個(gè)網(wǎng)元上，采用光纖直連、波分復(fù)用和光傳輸網(wǎng)等技術(shù)將無線接入網(wǎng)和核心網(wǎng)連接，具有高級別的帶寬。核心網(wǎng)由交換機(jī)、路由設(shè)備和數(shù)據(jù)中心組成，具有較高的計(jì)算能力。

2 基于強(qiáng)化學(xué)習(xí)高可靠性多域虛擬網(wǎng)絡(luò)映射算法

2.1 雙層強(qiáng)化學(xué)習(xí)映射算法流程

本文所提出的SDRL-VNE算法屬于兩階段法，整體算法框框架如圖2所示。主要分為三個(gè)步驟：a）節(jié)點(diǎn)映射階段采用強(qiáng)化學(xué)習(xí)模型，根據(jù)輸入的訓(xùn)練集VNRs和底層網(wǎng)絡(luò)完成映射，訓(xùn)練好節(jié)點(diǎn)映射策略網(wǎng)絡(luò);b）鏈路階段采用強(qiáng)化學(xué)習(xí)模型，將訓(xùn)練好的節(jié)點(diǎn)映射策略網(wǎng)絡(luò)的輸出結(jié)果輸入鏈路映射策略網(wǎng)絡(luò)，完成映射，訓(xùn)練好鏈路映射策略網(wǎng)絡(luò);c）根據(jù)訓(xùn)練好的節(jié)點(diǎn)和鏈路強(qiáng)化學(xué)習(xí)模型直接對在線VNR完成映射，輸出完整的映射結(jié)果。

2.2 節(jié)點(diǎn)映射

在節(jié)點(diǎn)映射階段，引入強(qiáng)化學(xué)習(xí)RLN-model模型來訓(xùn)練節(jié)點(diǎn)策略網(wǎng)絡(luò)。算法將節(jié)點(diǎn)的映射建模成一個(gè)馬爾可夫決策過程，使用強(qiáng)化學(xué)習(xí)的技術(shù)優(yōu)化節(jié)點(diǎn)映射。算法整體框架如圖3所示。

2.2.1 提取環(huán)境特征值

強(qiáng)化代理對底層資源的全面了解是網(wǎng)絡(luò)能否高效完成映射的關(guān)鍵，本文算法共提取五個(gè)全局拓?fù)涮卣鳎脕頊?zhǔn)確地表述節(jié)點(diǎn)當(dāng)前的狀態(tài)，用所有節(jié)點(diǎn)的特征向量組成全局節(jié)點(diǎn)的特征狀態(tài)矩陣，描述底層網(wǎng)絡(luò)資源的狀態(tài)，輸入強(qiáng)化學(xué)習(xí)模型進(jìn)行映射。節(jié)點(diǎn)的特征如下：

a）節(jié)點(diǎn)的CPU。節(jié)點(diǎn)的計(jì)算能力CPU 是節(jié)點(diǎn)最重要的特征，具有高計(jì)算能力的節(jié)點(diǎn)能處理更多的任務(wù)。用CPU（nsk）表示底層第k個(gè)節(jié)點(diǎn)所剩余的計(jì)算能力。

b）相鄰鏈路的帶寬和。每個(gè)資源節(jié)點(diǎn)都相鄰一個(gè)或多個(gè)鏈路。用BW（nsk）表示底層第k個(gè)節(jié)點(diǎn)相連可用鏈路的帶寬和。

BW（nsk）=∑ls∈L（nsk）BW（ls）（1）

c）節(jié)點(diǎn)的度。節(jié)點(diǎn)的度表示與它相連鏈路的個(gè)數(shù)，度越大表示與其他物理節(jié)點(diǎn)相連的可能性越大。用DEG（nsk）表示物理網(wǎng)絡(luò)上第k個(gè)節(jié)點(diǎn)的度。其中Degree（nsk）表示節(jié)點(diǎn)nsk相鄰鏈路總數(shù)，m表示底層物理節(jié)點(diǎn)總數(shù)。

DEG（nsk）=Degree（nsk）m－1（2）

d）映射節(jié)點(diǎn)間相對距離。VNR進(jìn)行節(jié)點(diǎn)映射時(shí)，選取一個(gè)合理地理位置的節(jié)點(diǎn)進(jìn)行映射，避免選路徑較遠(yuǎn)的節(jié)點(diǎn)作為待映射節(jié)點(diǎn)，可以有效減少鏈路中轉(zhuǎn)發(fā)節(jié)點(diǎn)的個(gè)數(shù)，降低鏈路的帶寬成本，更加合理地利用底層資源。其中|Ns|代表VNR中已被映射的虛擬節(jié)點(diǎn)所在的物理節(jié)點(diǎn)。

DS（nsk）=∑ns∈NsSP（nsk，ns）|Ns|+1（3）

e）特征向量中心性。一個(gè)節(jié)點(diǎn)的重要程度跟隨其相鄰節(jié)點(diǎn)的重要程度變化而變化，即一個(gè)節(jié)點(diǎn)連接點(diǎn)的節(jié)點(diǎn)越重要，該節(jié)點(diǎn)也越重要。

EG（nsk）=1λ∑i∈M（nsk）EG（nsi）（4）

用提取到的五個(gè)節(jié)點(diǎn)特征來描述節(jié)點(diǎn)的狀態(tài)，然后對特征值進(jìn)行0-1的最大最小歸一化處理，去除奇異的樣本數(shù)據(jù)，求得X′。

X′=X－XminXmax－Xmin（5）

用Vk來表示第k個(gè)物理節(jié)點(diǎn)的特征向量。

Vk=（CPU（nsk），BW（nsk），DEG（nsk），DS（nsk）EG（nsk））T（6）

用所有的物理節(jié)點(diǎn)Vk構(gòu)建底層物理節(jié)點(diǎn)的狀態(tài)矩陣Mf。

Mf=（v1，v2，…，vn）T（7）

2.2.2 節(jié)點(diǎn)映射策略網(wǎng)絡(luò)

VNE問題的狀態(tài)空間為連續(xù)值，所以本文構(gòu)建節(jié)點(diǎn)映射策略網(wǎng)絡(luò)，引入強(qiáng)化學(xué)習(xí)中的基于策略的方法，使用代理來優(yōu)化整個(gè)訓(xùn)練模型。策略網(wǎng)絡(luò)包含input層、conv層、softmax層、filter層和output層，如圖4所示。使用策略網(wǎng)絡(luò)來為待映射的虛擬節(jié)點(diǎn)選擇物理節(jié)點(diǎn)。

在輸入層，計(jì)算底層網(wǎng)絡(luò)節(jié)點(diǎn)的特征矩陣并傳入卷積層，在卷積層中對矩陣進(jìn)行卷積運(yùn)算，生成一個(gè)向量表示每個(gè)物理節(jié)點(diǎn)的可用資源hk。

hk=a.Vk+b if a.Vk+bgt;0

0otherwise（8）

其中：hk表示卷積的第k個(gè)輸出;a是權(quán)重向量;b是偏置項(xiàng)。在softmax層中將hk轉(zhuǎn)換成每個(gè)物理節(jié)點(diǎn)被選擇的概率，選取高概率節(jié)點(diǎn)進(jìn)行映射，得到更優(yōu)的映射結(jié)果。概率Pk的計(jì)算公式如下：

Pk=ehk∑iehi（9）

對于那些不滿足映射基本規(guī)則的節(jié)點(diǎn)在過濾層中進(jìn)行過濾，篩選出來具有足夠計(jì)算資源節(jié)點(diǎn)，并在輸出層重新計(jì)算概率分布，輸入結(jié)果如下：

P=（p1，p2，…，pn）（10）

2.2.3 獎(jiǎng)賞函數(shù)

強(qiáng)化學(xué)習(xí)模型使用無監(jiān)督的方式，訓(xùn)練集中的數(shù)據(jù)沒有標(biāo)簽，僅依靠代理的獎(jiǎng)勵(lì)來判斷模型是否正常工作。大的獎(jiǎng)勵(lì)表示當(dāng)前選擇的動(dòng)作有效，應(yīng)該保持;小的獎(jiǎng)勵(lì)甚至于懲罰表明代理當(dāng)前的選擇動(dòng)作是錯(cuò)誤的，應(yīng)及時(shí)修改。因此，獎(jiǎng)勵(lì)函數(shù)的選擇至關(guān)重要，直接決定訓(xùn)練過程和最終結(jié)果。本文將映射收益和成功率作為目標(biāo)，設(shè)置如下獎(jiǎng)勵(lì)函數(shù)：

Re=RE（nk）α.C（nk）+β.AR（nk） if VNR is mapped

0otherwise （11）

如果當(dāng)前策略能得到較高的收益比，說明映射是有效的，如果得不到可行的方案，那么返回值將是0，在后續(xù)學(xué)習(xí)中持續(xù)進(jìn)行調(diào)整。其中，RE（nk）表示虛擬網(wǎng)絡(luò)的收益;C（nk）表示映射時(shí)占用的成本;AR（nk）表示映射的成功率;α、β為系數(shù)，經(jīng)過多次訓(xùn)練可知，應(yīng)將α、β值分別設(shè)為0.7和0.3。

2.2.4 訓(xùn)練節(jié)點(diǎn)映射策略網(wǎng)絡(luò)模型

本文使用梯度策略法（policy gradients）來訓(xùn)練多域網(wǎng)絡(luò)中節(jié)點(diǎn)映射策略網(wǎng)絡(luò)。在策略網(wǎng)絡(luò)中引入一個(gè)手工制作的標(biāo)簽來臨時(shí)考慮強(qiáng)化學(xué)習(xí)代理作出的每個(gè)決策是否正確。假設(shè)選擇第k個(gè)多域物理網(wǎng)絡(luò)中的節(jié)點(diǎn)，則策略網(wǎng)絡(luò)中手工制作的標(biāo)簽將是一個(gè)向量yk ，除第k個(gè)是1，其余皆為0。交叉熵?fù)p失函數(shù)L（y，p）如式（12）所示。

L（y，p）=－∑k（yk log （pk））（12）

其中：yk、pk分別為手工標(biāo)簽的第k個(gè)節(jié)點(diǎn)和策略網(wǎng)絡(luò)的輸出。同時(shí)采用小批量梯度下降法來動(dòng)態(tài)更新策略網(wǎng)絡(luò)參數(shù)。在迭代中選擇batch_size個(gè)樣本數(shù)完成一次更新，并引入?yún)?shù)α來調(diào)整梯度的大小和訓(xùn)練的計(jì)算速度。梯度太小會(huì)使模型難以收斂，梯度太大會(huì)導(dǎo)致模型不穩(wěn)定，并且難以改善結(jié)果。經(jīng)過參數(shù)調(diào)優(yōu)將α和batch_size設(shè)為0.05和100。算法1給出了基于強(qiáng)化學(xué)習(xí)的節(jié)點(diǎn)映射策略網(wǎng)絡(luò)模型的訓(xùn)練過程。

算法1 節(jié)點(diǎn)映射策略網(wǎng)絡(luò)算法

輸入：物理網(wǎng)絡(luò)Gs；訓(xùn)練集VNRs；迭代次數(shù)Num。

輸出：訓(xùn)練好的節(jié)點(diǎn)映射策略網(wǎng)絡(luò);網(wǎng)絡(luò)參數(shù)a、b。

初始化節(jié)點(diǎn)映射策略網(wǎng)絡(luò)參數(shù)a、b。

while iterationlt;Num do

count=0

for vnr∈VNRs do

for nv∈vnr do

特征矩陣初始化

for nsk∈Gs do

Vk=（CPU（nsk），DEG（nsk），BW（nsk），DS（nsk））T

end for

特征矩陣數(shù)據(jù)歸一化處理

根據(jù)策略網(wǎng)絡(luò)輸出選概率選節(jié)點(diǎn)

更新物理網(wǎng)絡(luò)資源

end for

if nv∈vnr is Mapped then

bfs_LinkMap（vnr）

end if

if VNR successfully Mapped then

reward=RE（nk）/（a.c（nk）+b.AR（nk））

computeGradient（reward）

end if

counter++

end for

iteration++

end while

2.3 鏈路映射

與節(jié)點(diǎn)映射強(qiáng)化學(xué)習(xí)模型相似，本文為鏈路映射節(jié)點(diǎn)引入RLL-model強(qiáng)化學(xué)習(xí)模型，算法整體框架如圖5所示。模型的輸入是已經(jīng)訓(xùn)練好的節(jié)點(diǎn)映策略網(wǎng)絡(luò)輸出的節(jié)點(diǎn)映射方案。

2.3.1 提取環(huán)境特征值

鏈路和節(jié)點(diǎn)特征值提取的方法略有不同，因?yàn)椴荒芎唵蔚貙︽溌分苯犹崛√卣髦?，一條虛擬網(wǎng)絡(luò)鏈路并不是由單一的物理網(wǎng)絡(luò)完成映射，有可能是由一個(gè)或多個(gè)物理鏈路組成。所以為使代理高效地選擇物理路徑，算法需提前計(jì)算物理網(wǎng)絡(luò)中所有節(jié)點(diǎn)對之間的互通鏈路的路徑作為策略網(wǎng)絡(luò)的輸入。本文對物理鏈路提取以下兩個(gè)特征：

a）帶寬。兩節(jié)點(diǎn)之間最小可用鏈路帶寬值，用BW（lsj）表示。其中，l∈lsj表示物理路徑上第j條物理路徑上所有物理鏈路。

BW（lsj）=minl∈lsj（bw（l））（13）

b）鏈路的度。以經(jīng)過某鏈路的最短路徑數(shù)目來度量鏈路重要性的指標(biāo)，用BE（lsj）表示物理網(wǎng)絡(luò)上第j條物理路徑的度。其中，Sl表示經(jīng)過鏈路l的最短路徑數(shù)，Sall為所有最短路徑數(shù)目。

BE（lsj）=∑l∈lsjslsalllen（lsj）－1（14）

lj=（BW（lsj），BE（lsj））T（15）

提取物理路徑特征值后進(jìn)行0-1之間歸一化處理，即可得到鏈路的特征向量lj，構(gòu)造鏈路狀態(tài)矩陣Mf。

Mf=（l1，l2，…，ln）T（16）

2.3.2 鏈路映射策略網(wǎng)絡(luò)

在鏈路映射階段構(gòu)同樣建立鏈路映射策略網(wǎng)絡(luò)，同樣由五層組成。輸入鏈路狀態(tài)矩陣Mf，輸出每個(gè)物理路徑被選擇的概率。策略網(wǎng)絡(luò)每層的作用與節(jié)點(diǎn)策略網(wǎng)絡(luò)一致，不再贅述。

2.3.3 訓(xùn)練鏈路映射策路網(wǎng)絡(luò)模型

在鏈路映射策略網(wǎng)絡(luò)中同樣適用梯度策略法對網(wǎng)絡(luò)進(jìn)行訓(xùn)練，使用相同的函數(shù)作為獎(jiǎng)賞函數(shù)，模型中的參數(shù)batch-size和α不變，依舊為100和0.05。算法2給出了基于強(qiáng)化學(xué)習(xí)的鏈路映射策略網(wǎng)絡(luò)模型的訓(xùn)練過程。

算法2 鏈路映射策略網(wǎng)絡(luò)

輸入：物理網(wǎng)絡(luò)Gs;訓(xùn)練集VNRs；迭代次數(shù)Num。

輸出：訓(xùn)練好的鏈路映射策略網(wǎng)絡(luò)。

初始化節(jié)點(diǎn)映射策略網(wǎng)絡(luò)參數(shù)a、b

while iterationlt;Num do

count=0

for vnr∈VNRs do

node_map with node

if nv∈vnr is mapped then

for lv∈vnr do

鏈路特征矩陣初始化

for lsJ∈all_simple_path（Gs） do

lj=（BW（lsj），BE（lsj））T

end for

特征矩陣數(shù)據(jù)歸一化

path=random_select（R）

end for

if VNR successfully mapped then

reward=RE（nk）/（a.c（nk）+b.AR（nk））

computeGradient（reward）

end if

counter++

end if

end for

iteration++

end while

2.4 SDRL全局虛擬網(wǎng)絡(luò)映射算法

基于以上訓(xùn)練好的節(jié)點(diǎn)和鏈路策略網(wǎng)絡(luò)，提出基于雙層強(qiáng)化學(xué)習(xí)的生存性映射算法（SDRL-VNE），該算法分別在節(jié)點(diǎn)和鏈路映射階段使用訓(xùn)練好的策略網(wǎng)絡(luò)，動(dòng)態(tài)地完成整個(gè)映射過程，輸出全局的最優(yōu)的虛擬網(wǎng)絡(luò)映射方案。相比較于人工規(guī)則的節(jié)點(diǎn)貪心算法和鏈路廣度優(yōu)先搜索算法，每次定制一系列的規(guī)則和假設(shè)，簡單的數(shù)學(xué)計(jì)算得出映射方案。本文算法通過智能體與環(huán)境交互，利用獎(jiǎng)勵(lì)學(xué)習(xí)最優(yōu)映射機(jī)制，動(dòng)態(tài)地進(jìn)行反饋，能有效地發(fā)現(xiàn)物理網(wǎng)絡(luò)的表示和虛擬網(wǎng)絡(luò)請求之間的關(guān)系，從而高效地完成虛擬網(wǎng)絡(luò)映射。仿真結(jié)果表示，本文算法遠(yuǎn)優(yōu)異于人工規(guī)則的節(jié)點(diǎn)貪心和鏈路路徑最短的虛擬網(wǎng)絡(luò)映射算法。

算法3 基于強(qiáng)化學(xué)習(xí)多域高可靠性虛擬網(wǎng)絡(luò)映射算法

輸入：物理網(wǎng)絡(luò)Gs;虛擬網(wǎng)絡(luò)請求Gv;節(jié)點(diǎn)和鏈路映射策略網(wǎng)絡(luò)。

輸出：完整的映射方案。

for nv∈Nv do

狀態(tài)矩陣初始化

for nsk∈Gs do

Vk=（CPU（nsk），DEG（nsk），BW（nsk），DS（nsk））T

end for

特征矩陣Mf數(shù)據(jù)歸一化

ns=maxProbablity（p）

nodep ←nodep+{（nv，ns）}

end for

if nv∈Nv is mapped then

for lv∈LV do

狀態(tài)矩陣初始化

for lsj∈all_simple_path（Gs） do

lj=（BW（lsj），BE（lsj））T

end for

特征矩陣Mf數(shù)據(jù)歸一化

path=maxProbablity（R）

linkmap←linkmap +{（lv，paths）}

end for

if lv∈LV is mapped then

更新映射方案

return MR

else

return failure

end if

else

return failure

end if

3 仿真與性能評估

3.1 實(shí)驗(yàn)環(huán)境配置

實(shí)驗(yàn)環(huán)境設(shè)置在Windows 10下，使用強(qiáng)化學(xué)習(xí)框架Tensor Flow 2.0［16］在anaconda環(huán)境下進(jìn)行仿真結(jié)果分析。使用Transit-Stub［17］模型來生成底層物理網(wǎng)絡(luò)來確保仿真環(huán)境能模擬多域網(wǎng)絡(luò)環(huán)境中的接入網(wǎng)域、傳輸網(wǎng)域和核心網(wǎng)域。網(wǎng)絡(luò)生成一個(gè)30個(gè)骨干節(jié)點(diǎn)組成的transit域，作為流量的傳輸網(wǎng)絡(luò)，模擬為傳輸網(wǎng)域，有較高的鏈路帶寬。考慮到無線接入網(wǎng)的多終端用戶，生成一個(gè)包含40節(jié)點(diǎn)的stub模擬無線接入網(wǎng)域，并生成一個(gè)30節(jié)點(diǎn)的stub域作為核心網(wǎng)域，提供用戶連接、對用戶的管理以及業(yè)務(wù)完成承載。為了使網(wǎng)絡(luò)更加符合實(shí)際情況，域間鏈路設(shè)為500～1 000，保證域間鏈路遠(yuǎn)高于域內(nèi)鏈路。多域網(wǎng)絡(luò)的具體參數(shù)如表1、2所示。

3.2 仿真結(jié)果分析

為評估本文SDRL-VNE算法的性能，與全局資源整合映射算法（GRC-VNE）［4］ 、蒙特卡羅樹映射算法（MCTS-VNR）［11］、節(jié)點(diǎn)貪心和鏈路最短路徑算法（RG-LS-VNE）［19］和強(qiáng)化學(xué)習(xí)映射算法（RLN-VNE）［10］ 四種映射算法進(jìn)行比較。GRC算法通過引入節(jié)點(diǎn)和鏈路資源屬性來計(jì)算節(jié)點(diǎn)的重要性，是經(jīng)典的虛擬網(wǎng)絡(luò)映射算法。RG-LS是節(jié)點(diǎn)使用貪心算法排序進(jìn)行映射，鏈路使用最短路徑算法映射，是最為常見的兩階段映射算法。本文算法與GRC和RG-LS算法比較可以體現(xiàn)強(qiáng)化學(xué)習(xí)與環(huán)境動(dòng)態(tài)交互，通過獎(jiǎng)勵(lì)函數(shù)不斷求得全局最優(yōu)解的特點(diǎn)。RLN算法使用強(qiáng)化學(xué)習(xí)的方法，但僅引入節(jié)點(diǎn)映射策略網(wǎng)絡(luò)，優(yōu)化了節(jié)點(diǎn)映射，鏈路映射仍采用BFS算法。與該算法對比，表現(xiàn)出本文算法關(guān)注節(jié)點(diǎn)與鏈路的強(qiáng)相關(guān)性的特點(diǎn)，優(yōu)化鏈路映射的同時(shí)反過來優(yōu)化了節(jié)點(diǎn)映射結(jié)果。MCTS算法將強(qiáng)化學(xué)習(xí)與蒙特卡羅樹搜索算法相結(jié)合，每次映射一個(gè)新請求時(shí)，將會(huì)采用蒙特卡羅樹搜索多種映射方案，之后擇優(yōu)選取。與四種算法對比，可以表現(xiàn)出本文算法在鏈路映射時(shí)的高效性。

1）映射請求成功率 圖6表示請求映射成功率。在開始階段，四種算法的映射成功率都呈現(xiàn)急劇下降，因?yàn)榫W(wǎng)絡(luò)請求的到來，底層資源被快速占用，導(dǎo)致成功率下降。伴隨著網(wǎng)絡(luò)映射，底層資源逐漸減少，算法趨于穩(wěn)定。在映射開始階段和平穩(wěn)階段，SDRL算法的成功率都高于其他三種算法。表明本文算法使用雙層強(qiáng)化學(xué)習(xí)高效地完成了虛擬網(wǎng)絡(luò)映射全過程。在優(yōu)化節(jié)點(diǎn)的同時(shí)優(yōu)化鏈路起到了有效的作用。RG-LS算法在開始階段因使用貪心算法取得較高的成功率，但未考慮全局均衡，出現(xiàn)明顯上下波動(dòng)，然后處于穩(wěn)定狀態(tài)，成為成功率最低算法，符合實(shí)現(xiàn)預(yù)期結(jié)果。GRC算法在鏈路映射階段的減枝操作，在跨域網(wǎng)絡(luò)中表現(xiàn)出優(yōu)勢，映射結(jié)果好于只使用節(jié)點(diǎn)強(qiáng)化學(xué)習(xí)的RLN算法。

2）長期平均收益和開銷 圖7、8分別表示長期平均收益和長期平均花銷。SDRL算法在全階段都擁有最高的收益率，因?yàn)槠渚哂凶罡叩挠成涑晒β?，所以獲得了最高收益。但同時(shí)該算法的長期支出是最高的，因?yàn)樵谔摂M網(wǎng)絡(luò)映射中，鏈路映射的支出遠(yuǎn)高于節(jié)點(diǎn)映射。而SDRL在優(yōu)化節(jié)點(diǎn)的同時(shí)優(yōu)化了鏈路映射，為了提高映射成功率，沒有簡單地采用BFS算法，而是有可能選取較長的路徑進(jìn)行映射。本文算法是高支出高收益算法，雖然增加了網(wǎng)絡(luò)映射成本，但確保了網(wǎng)絡(luò)長期高效的穩(wěn)定運(yùn)行，從而獲取更多的收益。

3）節(jié)點(diǎn)和鏈路的平均利用率 圖9、10分別表示了節(jié)點(diǎn)和鏈路的平均利用率。SDRL不論是節(jié)點(diǎn)還是鏈路都擁有較好的資源利用率，驗(yàn)證了節(jié)點(diǎn)映射策略網(wǎng)絡(luò)和鏈路映射策略網(wǎng)絡(luò)對映射結(jié)果的有效性。RG-LS因?yàn)殒溌酚成涫褂米疃搪窂剿惴ǎ瑥亩@得了最高的鏈路使用率，但整體映射結(jié)果一般。SDRL和RLN算法使用相同的節(jié)點(diǎn)映射策略網(wǎng)絡(luò)，但SDRL的節(jié)點(diǎn)資源利用遠(yuǎn)高于RLN。這表明，雙重強(qiáng)化學(xué)習(xí)的鏈路階段在優(yōu)化鏈路階段的同時(shí)優(yōu)化了節(jié)點(diǎn)映射的策略，再次證明了雙層強(qiáng)化學(xué)習(xí)優(yōu)化了全局虛擬網(wǎng)絡(luò)映射的結(jié)果。

4 結(jié)束語

本文研究了在5G多域異構(gòu)網(wǎng)絡(luò)環(huán)境下虛擬網(wǎng)絡(luò)映射的可生存性問題，提出了一種基于雙層強(qiáng)化學(xué)習(xí)的虛擬網(wǎng)絡(luò)映射算法。此算法通過提取底層資源的特征值構(gòu)造特征向量，組成狀態(tài)矩陣，將狀態(tài)矩陣分別輸入對應(yīng)節(jié)點(diǎn)和鏈路映射策略網(wǎng)絡(luò)，輸出映射結(jié)果。仿真結(jié)果表明，在多域異構(gòu)的環(huán)境下，SDRL算法性能優(yōu)于對比算法，提高了映射成功率和底層網(wǎng)絡(luò)的資源利用率。然而由于本文僅從可生存性的部署角度出發(fā)，未考慮故障的恢復(fù)，所以下一步將重點(diǎn)考慮虛擬網(wǎng)絡(luò)映射的故障恢復(fù)。

參考文獻(xiàn)：

[1]曹浩彤.網(wǎng)絡(luò)虛擬化環(huán)境下虛擬網(wǎng)絡(luò)映射算法研究［D］.南京：南京郵電大學(xué)，2020.（Cao Haotong. Research on virtual network mapping algorithm under network virtualization environment［D］.Nanjing：Nanjing University of Posts and Telecommunications，2020.）

［2]趙國繁，唐倫，胡彥娟，等.面向可靠性的5G網(wǎng)絡(luò)切片重構(gòu)及映射算法［J］.電子與信息學(xué)報(bào)，2020，42（6）：1478-1485.（Zhao Guofan， Tang Lun， Hu Yanjuan， et al. Reconstruction and mapping algorithm for reliability-oriented 5G network slicing［J］.Journal of Electronics and Information Technology，2020，42（6）：1478-1485.）

［3]Fischer A， Botero J F， Beck M T， et al. Virtual network embedding：a survey［J］.IEEE Communications Surveys amp; Tutorials，2013，15（4）：1888-1906.

［4]吳怡.多域虛擬網(wǎng)絡(luò)映射算法研究［D］.北京：北京郵電大學(xué)，2020.（Wu Yi. Research on multi-domain virtual network mapping algorithm［D］.Beijing：Beijing University of Posts and Telecommunications，2020.）

［5]Cao Haotong，Yang Longxiang， Liu Zeyuan.Exact solutions of VNE：a survey［J］.China Communications，2016（6）：48-62.

［6]黃麗萍，楊龍祥.可生存性虛擬網(wǎng)絡(luò)映射算法的研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，2018，28（7）：144-148.（Huang Liping， Yang Long-xiang. Research on survivability virtual network mapping algorithm［J］.Computer Technology and Development，2018，28（7）：144-148.）

［7]Bai Huifeng， Chen Wenbin， Liu Lin， et al. Dynamic fragments awareness based virtual network mapping strategy of elastic optical networks［J］.Optoelectronics Letters，2021，17（7）：427-431.

［8]劉光遠(yuǎn)，徐明偉.可生存的虛擬網(wǎng)絡(luò)多層映射方法研究［J］.電子學(xué)報(bào)，2020，48（7）：1343-1347.（Liu Guangyuan， Xu Mingwei. Research on survivable multi-layer mapping method of virtual network［J］.Chinese Journal of Electronics，2020，48（7）：1343-1347.）

［9]劉祥如.基于可生存性的虛擬網(wǎng)絡(luò)映射策略的研究［D］.北京：北京郵電大學(xué)，2018.（Liu Xiangru. Research on virtual network mapping strategy based on survivability［D］.Beijing：Beijing University of Posts and Telecommunications，2018.）

［10]Yao Haipeng， Chen Xu， Li Maozhen et al. A novel reinforcement learning algorithm for virtual network embedding［J］.Neurocompu-ting，2018，285：1-9.

［11]張博.基于強(qiáng)化學(xué)習(xí)的虛擬網(wǎng)絡(luò)映射問題的研究與實(shí)現(xiàn)［D］.北京：北京郵電大學(xué)，2019.（Zhang Bo. Research and implementation of virtual network mapping problem based on reinforcement learning［D］.Beijing：Beijing University of Posts and Telecommunications，2019.）

［12]曲樺，趙季紅，李明霞，等.一種基于深度強(qiáng)化學(xué)習(xí)的虛擬網(wǎng)絡(luò)映射方法：中國，CN110365568A［P］.2019.（Qu Hua， Zhao Jihong， Li Mingxia， et al. A virtual network mapping method based on deep reinforcement learning：China，CN110365568A［P］.2019.）

［13]Haeri S， Trajkovic L. Virtual network embedding via Monte Carlo tree search［J］.IEEE Trans on Cybernetics，2018，48（2）：510-521.

［14]Mijumbi R， Gorricho J L， Serrat J， et al. Neural network-based autonomous allocation of resources in virtual networks［C］//Proc of European Conference on Networks amp; Communications.Piscataway，NJ：IEEE Press，2014：1-6.

［15]Blenk A， Kalmbach P， Smagt P， et al. Boost online virtual network embedding： using neural networks for admission control［C］//Proc of the 12th International Conference on Network amp; Service Management.Piscataway，NJ：IEEE Press，2016：10-18.

［16]Singh P， Manure A. Introduction to TensorFlow 2.0［M］//Learn TensorFlow 20.Berkeley，CA：Apress，2020：1-24.

［17]冀汶莉，李勇軍.Transit-Stub網(wǎng)絡(luò)拓?fù)淇梢暬芯浚跩］.微電子學(xué)與計(jì)算機(jī)，2007，24（1）：136-139.（Ji Wenli， Li Yongjun. Research on Transit-Stub network topology visualization［J］.Microelectronics and Computer，2007，24（1）：136-139.）