王 曉,唐 倫 ,賀小雨,陳前斌
1.重慶郵電大學 通信與信息工程學院,重慶 400065
2.重慶郵電大學 移動通信技術重點實驗室,重慶 400065
為了在同一物理網絡上同時支持多元化的業務場景,“網絡切片”普遍被業界認為是一種理想的網絡模型。網絡功能虛擬化(Network Function Virtualization,NFV)是支撐網絡切片的關鍵技術之一。NFV技術利用云計算和虛擬化技術編排不同的虛擬網絡功能(Virtualized Network Function,VNF),并將其映射在通用物理服務器設備上完成相應網絡功能。一個完整的服務請求由多個VNF 有序連接而成,形成一條服務功能鏈(Service Function Chain,SFC),多個相同業務類型的SFC 組成一個網絡切片[1-2]。如何在底層物理網絡上部署SFC 是NFV 技術的關鍵問題。SFC 部署問題的實質是將VNF和連接VNF的虛擬鏈路分別在底層物理網絡滿足資源容量需求的服務器與物理鏈路上實例化,并將底層網絡的物理資源(如計算資源、鏈路帶寬資源)分配給SFC 的各個組成部分(VNF、虛擬鏈路),形成一條端到端通路,完成相應的用戶服務請求[3-4]。網絡資源是有限的,如何在保證用戶SFC服務質量的前提下節約資源消耗,降低運營成本,對運營商來說至關重要。
目前,針對SFC 的研究并不完善,現有研究通常根據不同的服務需求和網絡場景來設定一個服務功能鏈映射的優化目標,并設計啟發式算法進行求解。如文獻[5]考慮在保證資源限制的前提下優化SFC的部署成本,提出了一種基于動態規劃的成本優化算法進行求解。文獻[6]考慮動態網絡功能部署和路由優化問題,聯合優化可接受最大流速率(Flowrate)和能耗,建立了一個混合整數線性規劃模型,設計了一種基于流補償的近似分配算法進行求解。文獻[7]考慮在內容分發網絡場景下部署實現內容分發功能的SFC,在保證時延要求的前提下最小化部署成本,并將此優化問題轉化為一個整數線性規劃問題,提出了一種前攝性VNF 鏈部署算法進行求解。
以上研究均是針對SFC在核心網的部署,然而對于無線用戶,在接入網端進行無線資源(如子載波資源、發送功率等)分配是完成端到端服務必不可少的一部分,因此,在NFV場景下,將無線資源分配與SFC部署進行聯合優化還需進一步深入研究。此外,經證明SFC部署問題是NP-hard 問題[8],現有研究通常設計啟發式算法來求出次優解,并且較少考慮到無線環境的動態性而在單時隙中優化網絡性能。然而,面對復雜多變的網絡環境,這樣的啟發式算法難以達到理想的優化效果。
針對上述問題,本文聯合考慮SFC部署和無線資源分配,提出一種基于深度強化學習(Deep Reinforcement Learning,DRL)的SFC多維資源聯合分配算法。主要貢獻包括:
(1)針對無線用戶的SFC 服務請求,構建一種基于環境感知的SFC資源分配機制,將用戶可達的無線速率作為SFC部署的流速率,以此作為依據來分配SFC節點計算資源和鏈路帶寬等資源;
(2)根據上述基于環境感知的SFC 資源分配機制,建立用戶時延要求、無線速率需求以及資源容量約束下的SFC部署成本最小化模型;
(3)將此優化模型轉化為在離散時間下的具有連續狀態空間、高維度動作空間的無模型馬爾科夫決策過程(Markov Decision Process,MDP)模型,并提出一種基于深度確定性策略梯度(Deep Deterministic Policy Gradient,DDPG)[9]的SFC多維資源聯合分配算法,實現對SFC多維資源的聯合優化。
本文的網絡場景采用基于NFV/SDN(Software Defined Network)控制面與數據面相分離的架構,如圖1所示。控制面的NFV管理編排器(Management and Orchestration,MANO)負責對用戶的SFC進行部署和資源分配決策,數據面的NFV 基礎設施(NFV Infrastructure,NFVI)為分布式高性能通用服務器,負責用戶SFC中VNF的實例化和鏈路傳輸。

圖1 網絡場景
針對無線用戶的下行SFC請求,要完成完整的端到端通信除了需要常規的VNF 部署之外,還需要在無線接入網端為用戶分配無線頻譜和發送功率等資源。在傳統SFC 部署問題中,通常為一條SFC 指定一個流速率,或者為SFC 中的每個VNF 和虛擬鏈路指定所需的資源消耗[6],但由于SFC 在有線鏈路的流速率與最終用戶可達的無線速率不匹配,導致核心網資源浪費。針對這一問題,本文構建了一種基于環境感知的SFC資源分配機制。所謂“環境感知”,即在無線端監測用戶的信道狀態,并分配相應無線資源,從而根據香農公式獲得用戶可達的無線速率,以此速率作為整個SFC 的流速率,進行相應VNF和虛擬鏈路的計算資源和鏈路帶寬資源的分配。這樣,以用戶可達的無線速率作為依據來分配SFC 各部分資源,節約了核心網資源消耗,從而有效降低了SFC 的部署成本。本文的資源分配在核心網中考慮物理節點計算資源與有線鏈路帶寬資源,在無線接入網中考慮子載波分配。
底層物理網絡用無向圖G=(N,E)表示。其中N={n1,n2,…}為物理節點集合,由分布式的標準化高性能通用服務器組成,用Nr={r1,r2,…}表示無線接入網中小基站(Small Base Station,SBS)集合,有Nr?N;E={(ni,nj)|ni,nj∈N,Bi,j >0}為物理鏈路集合。用C1×|N|=[c1,c2,…]表示物理節點計算資源容量,其中ci為物理節點ni的計算資源容量;用B|N|×|N|=[Bi,j]表示物理節點的關聯矩陣,其元素Bi,j表示節點ni和nj間的鏈路帶寬容量,若兩點間無鏈路則為0;用表示SBS的子載波資源向量,其中表示SBSri的子載波個數。
服務請求集合用F={1,2,…,f,…}表示。一個SFC請求為一個五元組f=<sfcf,Loadf,rf,Delayf,Cf >,其中sfcf表示f的SFC 邏輯鏈路,Loadf表示f的負載(單位:Mbit),rf表示發起該服務請求的用戶所關聯的SBS,Delayf表示f的時延要求,Cf表示f的無線速率要求。
本文的研究目標是在動態變化的無線信道環境中,為每個時隙的服務請求做出SFC 部署與資源分配決策。部署變量包括每個時隙的VNF部署變量及其計算資源分配、鏈路映射變量及其帶寬分配以及無線接入網子載波分配。用二進制矩陣表示VNF 部署矩陣,其中表示在t時隙VNF部署在物理節點nj上,否則為0;用表示sfcf鏈路部署變量,在t時隙當sfcf中從vi出發的虛擬鏈路映射在物理鏈路(np,nq)上時,有否則為0,進而可用表示sfcf中所有鏈路的映射集合。當節點映射完成后,以SFC相鄰節點間映射的物理節點的Dijkstra最短路徑作為該虛擬鏈路的映射結果。如圖2 所示,SFC 中一條虛擬鏈路(i,j)的相鄰兩個VNF分別映射在物理節點n1和n3上,則該虛擬鏈路映射即為節點n1和n3間的Dijkstra 最短路徑n1→n2→n3。

圖2 鏈路映射示意圖
用矩陣W(t)=[Wi,f(t)]表示SBS 子載波分配矩陣,其中Wi,f(t)表示在t時隙SBSri分配給服務請求f的子載波數量。用cpuf(t) 表示t時隙分配給sfcf中的VNF 的計算資源,用Bf(t)表示分配給sfcf的鏈路帶寬資源。假設t時隙節點處理速率與所分配計算資源cpuf(t)成正比:

其中,φ為轉化因子,根據本文所構建的基于環境感知的SFC 資源分配機制,節點處理速率和鏈路帶寬Bf(t)應與用戶可達的無線速率Cf(t)一致,即Bf(t)=Cf(t),則可得計算資源的需求量為:

本文的優化目標是在滿足服務請求時延要求和無線速率需求的前提下,最小化SFC部署成本。根據本文構建的基于環境感知的SFC資源分配機制,首先要在每一時隙開始時監測用戶無線接入網端的信號強度,SBS通過平均分配的方法對用戶進行功率分配,從而得到用戶的信干噪比γi,f(t),即:


其中,B是單個子載波帶寬。將此用戶可達的無線速率作為該用戶SFC的流速率,以此為依據對SFC進行資源分配。
本文考慮的部署成本由無線子載波資源成本、物理節點計算資源成本以及鏈路帶寬資源成本三部分組成,可表示為:

其中,ρw、ρc、ρb為三種成本權重因子,costw(t)為子載波資源消耗,costc(t)為物理節點計算資源消耗,costb(t)為有線鏈路帶寬資源消耗,分別表示如下:

每條SFC 需滿足由其自身服務特點所決定的時延需求。一條SFC的總時延D由物理節點處理時延Dc、有線鏈路傳輸時延Dl以及無線鏈路傳輸時延Dw組成。設節點處理時延與SFC負載Loadf成正比,與節點處理速率成反比,因此服務請求f的SFC節點處理時延為:

設有線鏈路傳輸時延與SFC負載Loadf成正比,與分配到的鏈路帶寬資源Bf(t)成反比,因此服務請求f的SFC有線鏈路傳輸時延為:

設無線傳輸時延與SFC負載Loadf成正比,與無線速率Cf(t)成反比,因此服務請求f的無線鏈路傳輸時延為:

由此可得,服務請求f的總時延為:

綜上所述,本文的優化目標可歸納如下:


其中,C1表示各個服務請求的時延要求,C2表示各個服務請求的無線速率需求,C3 表示每個VNF 必須映射到一個物理節點上,C4 表示每個物理節點計算資源的容量限制,C5表示每條物理鏈路帶寬資源限制,C6表示物理節點流守恒,C7表示SFC是一條不可分離流,C8表示SBS 無線子載波資源容量限制,C9 表示用戶的vr必須映射到與之關聯的SBS上。
上述模型中的環境狀態是動態變化的用戶信干噪比,狀態空間具有馬爾科夫性且為連續值[10],同時,模型中的決策變量包括每個用戶的子載波分配及其SFC 中每一個VNF 的部署,維度較高。馬爾科夫決策過程(MDP)是序貫決策的數學模型,用于系統狀態具有馬爾科夫性質的環境,通過與環境的不斷交互來獲得更大的收益。因此上述優化問題可轉化為具有連續狀態空間和高維度動作空間的離散時間MDP模型。深度確定性策略梯度(DDPG)算法是一種基于行動者-評論家(Actor-Critic,AC)算法架構的深度強化學習算法[9],在智能決策問題中具有良好的性能優勢。它利用神經網絡從連續狀態空間和高維動作空間中提取特征,并結合了深度Q網絡(Deep Q Network,DQN)算法中“經驗回放”(Experience Replay)和“固定目標網絡”(Fixed Target Network)的思想,可以使算法在MDP 中達到理想的收斂速率和穩定性[11]。因此,本文提出一種基于DDPG的SFC多維資源聯合分配算法求解上述優化模型。
根據本文建立的SFC部署優化問題,將該優化問題轉化為一個具有連續狀態空間和高維度動作空間的無模型MDP模型。MDP由一個四元組表示<S,A,Pr,r >,S表示狀態空間,A表示動作空間,Pr表示狀態轉移概率,r表示獎勵函數。其中,狀態空間S由時隙t各個用戶無線端可能的信干噪比組成,因此時隙t系統的狀態為:

動作空間由用戶無線端子載波分配和VNF映射矩陣組成,則時隙t的動作為:

根據本文構建的基于環境感知的SFC 資源分配機制,以子載波分配W(t)所得到的用戶可達的無線速率作為用戶SFC計算資源和鏈路帶寬資源分配的依據,并通過映射矩陣將 SFC 中各個 VNF 映射到滿足資源容量約束的物理節點上,完成部署。
狀態轉移概率Pr可表示為:

其中,f(·)為狀態轉移概率密度函數。由于本MDP 中狀態空間為用戶在無線環境中的信干噪比,無法直接量化其狀態轉移概率,因此將其視為未知概率。所謂“無模型”MDP,即狀態轉移概率難以求得,不依賴于環境的MDP模型。
當環境處于狀態st時執行動作at,系統會進入下一狀態st+1,并得到即時獎勵rt,本文優化目標為SFC的部署總成本,因此將成本的相反數設為獎勵函數,即:

動作a的來源為一個確定性策略π,由策略π可得到每個時隙的子載波分配和SFC部署決策,π為狀態空間S到動作空間A的一個映射,可表示為:

動作值函數Q(s,a)表示從當前狀態并采取某一動作后執行某一策略得到的累計獎勵的期望值,即在一段時間k內的累積部署成本Cost(t)的相反數,因此在狀態s根據策略π采取動作a的動作值函數可表示為:

其中,λ∈(0,1)為權衡各個時刻回報函數的折扣因子。Q函數的迭代形式稱為貝爾曼方程(Bellman Equation),如下式所示:

定義一個策略目標函數J(π)來衡量策略的性能表現,它表示為動作值函數的均值,如下式所示:

其中,d(s)為狀態空間的分布函數。該MDP 模型的優化目標即為,找到一個子載波分配和SFC 部署策略π,使Q函數的期望值最大,從而達到本文最小化SFC部署成本的優化目標,即:

本文需要在NFV框架下對無線用戶進行子載波分配和SFC的部署,由式(14)和式(15)可知其狀態空間和動作空間維度極大且狀態轉移概率Pr未知,無法通過式(20)的貝爾曼方程進行迭代獲得Q值。由此,深度強化學習利用神經網絡從高維空間中提取特征,從而輸出Q值的近似值,解決了維度過高的問題。在各類深度強化學習中,DDPG算法在AC算法的基礎上結合了DQN算法中“經驗回放”和“固定目標網絡”的思想,相比于AC算法提高了穩定性與收斂性。
DDPG算法架構如圖3所示,其智能體(Agent)包括Actor 和Critic 兩部分。其中,Actor 負責構建參數化的策略,根據當前狀態輸出動作,Critic 負責構建Q 網絡,根據環境反饋的獎勵值來評估當前策略,輸出時間差分(Temporal Difference,TD)誤差(目標Q 網絡與在線Q網絡輸出之差)來更新Actor 和Critic 兩部分的參數,使MDP的優化目標J(π)最大化。所謂“經驗回放”是指設置一個存放狀態轉移過程<st,at,rt,st+1>的經驗池,它將每一次與環境交互的過程記錄下來,每次訓練時從經驗池中隨機抽取小批量狀態轉移過程進行學習,其目的是為了打破學習樣本中數據間的時間相關性,這樣網絡可以從過去更廣泛的經驗中進行學習而不僅僅局限于當前環境[9,12]。由于狀態空間和動作空間的高維性,在Actor和Critic兩部分智能體中,均使用神經網絡來構建參數化的策略和動作值函數,而神經網絡往往因其目標值的參數與估計值的參數同時變化,從而導致學習過程不穩定和發散。DQN中“固定目標網絡”的方法可以有效解決這一問題,即在用一個神經網絡估計值的同時,建立另一個神經網絡作為目標網絡,其參數在一定的迭代過程中保持不變,經過指定迭代次數后再用當前評估網絡的參數替換該目標網絡的參數,這種目標網絡的更新方式稱為“硬更新”(Hardupdate)。與DQN 算法不同的是,DDPG 采用“軟更新”(Softupdate)的方式來更新目標網絡參數,即每一步都會更新目標網絡,但更新的幅度非常小,這樣做使學習過程更接近于監督式學習[9,13]。研究表明,使用上述目標網絡的方法可以使神經網絡的收斂過程更加穩定。

圖3 DDPG算法架構
2.3.1 Critic部分
在DDPG 算法中,Critic 部分利用兩個神經網絡來估計Q 值,從而評估當前策略。其中一個神經網絡為“在線Q網絡”,其參數設為w,在線Q網絡的輸出為動作值函數的估計值Qw(st,at),另一個神經網絡為“目標Q 網絡”,其參數為w′,輸出為動作值函數的目標值yt,有:


訓練時,將從經驗池中隨機抽取M組狀態轉移過程<si,ai,ri,si+1>進行訓練,根據損失函數來更新在線Q 網絡的參數w,Critic 的損失函數L(w)定義為TD 誤差的均方值:

利用損失函數L(w)關于參數w的梯度,使用梯度下降法來更新在線Q網絡的參數,使w朝著L(w)下降的方向進行更新,即:

其中,αc為Critic 的學習率。同時,使用上述“軟更新”的方式更新目標Q 網絡的參數w′,設置“軟更新系數”τ來控制每一步目標網絡更新的幅度,則目標Q網絡的更新方式為:

2.3.2 Actor部分
DDPG算法的Actor部分負責構建參數化的策略并根據狀態輸出動作。與Critic部分一樣,Actor也使用了兩個神經網絡來構建參數化的策略,分別為“在線策略網絡”和“目標策略網絡”。其中,目標策略網絡用于構建目標策略πθ′(s),其參數為θ′,其輸出為目標Q網絡提供動作a′=πθ′(s),用于式(23)計算動作值函數的目標值yt,從而計算TD誤差;在線策略網絡用于構建在線策略πθ(s),其參數為θ,為整個智能體輸出動作a并與環境進行交互,其參數采用策略梯度算法進行更新[14]。由于在DDPG算法中,用神經網絡來輸出Q值,則可將式(21)中的Qπ(s,a)用在線Q網絡的輸出Qw(s,a)代替,則策略目標函數J(π)可改寫如下:

策略梯度是指策略目標函數J(π)關于參數θ的梯度,表示為:

與Critic相同,Actor的訓練樣本也來自經驗池中的M組狀態轉移過程<si,ai,ri,si+1>。于是,上述策略梯度可改寫如下:

由此,可以得出Critic的參數更新公式為:

同樣地,使用“軟更新”方式對目標策略網絡參數進行更新:

為了讓智能體輸出的動作有可能獲得更大的獎勵,為Actor 輸出的動作增加探索機制(Exploration),即在在線策略網絡輸出的動作中加入一個隨機的探索噪聲noise,表達為:

探索噪聲隨著訓練回合的進行不斷減小,直到最終獲得使獎勵穩定且收斂的策略。
綜上所述,可將基于DDPG的SFC多維資源聯合分配算法歸納如下:
算法1基于DDPG的SFC多維資源聯合分配算法


本文通過 Python 3.0 和 TensorFlow、OpenAI gym等工具實現本文提出的基于DDPG 的服務功能鏈多維資源聯合優化算法仿真,并使用Matlab繪圖完成。為了評估本文所提機制及算法的有效性,現將其與文獻[5]中的DP-COA啟發式算法,以及其他兩種強化學習算法策略梯度算法(Policy Gradient,PG)[14]和AC算法[10]進行性能比較。本文共設置10個物理節點,其中包括2個接入節點(SBS),每個物理節點擁有4個虛擬CPU(vCPU)資源,每個vCPU 的數據處理速率均為160 Mbit/s,每一條物理鏈路總帶寬為300 Mbit/s,每個接入節點的子載波個數為50,每個子載波帶寬為0.18 MHz[15]。3個成本權重因子分別設為ρc=0.4,ρb=0.2,ρw=0.4[7]。學習過程中,訓練共進行500 個回合,每回合200 步,經驗池大小M設為10 000,因此每當回合數進行到50 時,經驗池填滿,開始學習。
首先,對于強化學習算法,學習率是影響算法收斂速度和決策性能的關鍵因素。圖4 描繪了當有10 個用戶請求,且性能需求為無線速率需求為20 Mbit/s以及用戶平均時延要求為20 ms時,在不同學習率下算法的收斂效果。從圖4 中可以看出,當訓練過程到達50 回合時,經驗池填滿,算法開始從經驗池中批量抽取狀態轉移過程進行學習,SFC 部署成本開始迅速下降。當Actor 學習率αa為 0.001、Critic 學習率αc為 0.01 時,算法收斂快速穩定,且系統成本最低,表現出良好的性能優勢。因此本文在后續的仿真中均選擇αa=0.001,αc=0.01 為DDPG算法的學習率。

圖4 不同學習率下DDPG算法的收斂效果
圖5 描繪了三種基于策略的強化學習算法PG、AC以及DDPG 算法應用于本文模型的收斂效果和性能表現,三種算法均為可以解決高維度動作空間MDP 問題的強化學習算法。從圖中可以看出,對于復雜環境,PG算法難以達到一個理想的收斂效果和性能優化,AC 算法在收斂速度方面也不及DDPG 算法。其原因為,PG算法是單純的策略梯度算法,相當于DDPG 架構中的Actor部分,只能通過自身的策略梯度進行參數更新,缺少相應的評判部分(Critic)對其輸出的策略進行評估,因此對于復雜環境,PG 算法的智能體難以找到正確的參數更新方向,導致其收斂過程不穩定。而AC算法的智能體包含Actor 和Critic 兩部分,其中Actor 負責構建參數化的策略,根據環境狀態輸出相應的動作;Critic負責輸出Q值,對當前Actor中的策略進行評估,幫助策略網絡參數朝著可以獲得更大Q值的方向進行更新,因此AC算法可以得到比PG算法更好的優化效果。然而AC算法由于其智能體包括Actor和Critic兩部分,存在收斂過程緩慢的問題,DDPG針對這一問題,在AC算法架構的基礎上結合了“經驗回放”和“固定目標網絡”的思想,訓練時從經驗池中隨機抽取部分狀態轉移過程進行學習,打破了學習樣本中的時間相關性,這樣可以從過去更廣泛的經驗中進行學習而不僅僅局限于當前環境;固定目標網絡可以為Critic 的訓練提供穩定的目標Q 值,使得學習過程更加穩定,保證了Critic 網絡輸出Q 值的準確性,從而加快了Actor 中策略網絡的收斂。因此,DDPG 算法的收斂效果強于PG 和AC 算法。

圖5 不同強化學習算法的收斂效果
接下來對在不同服務請求數下的算法性能進行比較。首先比較在不同用戶請求數下的系統成本,用戶無線速率需求設為20 Mbit/s,如圖6所示。可以看出本文所使用的DDPG算法在三種不同在線人數情況下,系統總成本均處于最低。AC 強化學習算法由于其收斂緩慢,隨著用戶請求數的增加,其性能表現逐漸差于啟發式算法DP-COA。而DDPG算法由于在AC算法的基礎上結合了經驗回放和目標網絡方法,因此保證了算法收斂的穩定性,并具有良好的性能表現。在時延優化方面,從圖7可以看出,DDPG算法下的系統總時延在不同用戶請求數下均處于最優。DP-COA為動態規劃算法,它將每個時刻的SFC 部署按VNF 的順序依次進行決策,面對復雜的網絡環境,DP-COA 容易陷入局部最優。并且DP-COA算法考慮單純的SFC部署問題,未將無線資源的分配聯合考慮,對于無線用戶沒有完成完整的端到端服務。而DDPG 算法可以契合本文所構建的基于環境感知的SFC資源分配機制,從而解決無線用戶SFC 部署與無線資源的聯合優化問題。由此可見,DDPG 適用于更復雜的網絡場景,在擴展性方面強于DP-COA啟發式算法。

圖6 不同用戶請求下的系統總成本對比

圖7 不同用戶請求下的系統總時延對比
圖8 描繪了三種算法在不同無線速率需求下的性能對比,用戶請求數設為10。如圖8 所示,當無線速率需求較小時,三種算法在系統總成本上的性能表現相差不大,但隨著無線速率需求的增大,DDPG 算法在該性能上的優勢逐漸體現出來,且強化學習算法(DDPG、AC)對系統總成本的優化效果整體優于啟發式算法DP-COA。圖9 描繪了在不同無線速率需求下的系統總時延對比情況。可以看出,DDPG算法在三種無線速率需求下的時延性能優勢較為明顯,AC 算法由于其自身收斂緩慢,其時延性能表現不如啟發式算法DP-COA,再次說明了DDPG 算法中的經驗回放和固定目標網絡方法的有效性。

圖8 不同無線速率需求下的系統總成本對比

圖9 不同無線速率需求下的系統總時延對比
針對NFV下的無線用戶SFC請求的低成本部署問題,本文聯合考慮SFC 部署與無線資源分配,構建了一種基于環境感知的SFC資源聯合分配機制,并據此建立了在滿足用戶時延要求、無線速率需求以及資源容量約束下的SFC部署成本最小化模型,并將該優化模型轉化為具有連續狀態空間和高維度動作空間的無模型MDP模型,提出一種基于DDPG的SFC多維資源聯合分配算法求解該優化問題。仿真結果表明,在上述SFC部署機制下,使用該算法進行求解,可在保證用戶性能需求的同時,有效降低SFC部署成本和時延。