面向動態(tài)拓?fù)渚W(wǎng)絡(luò)的深度強(qiáng)化學(xué)習(xí)路由技術(shù) *

伍元勝

(中國西南電子技術(shù)研究所，成都 610036)

0 引 言

無線自組網(wǎng)(例如車聯(lián)網(wǎng)、無人機(jī)網(wǎng)絡(luò)等)隨著網(wǎng)絡(luò)節(jié)點(diǎn)的移動，網(wǎng)絡(luò)拓?fù)涑掷m(xù)動態(tài)變化。傳統(tǒng)的動態(tài)路由技術(shù)通常基于固定的路由策略，難以適應(yīng)網(wǎng)絡(luò)的動態(tài)變化。例如，目的節(jié)點(diǎn)序列距離矢量(Destination Sequenced Distance Vector,DSDV)路由協(xié)議[1]以路由跳數(shù)為鏈路權(quán)值，計算最短路徑，無法適應(yīng)拓?fù)渥兓鸬钠款i鏈路變化，從而導(dǎo)致網(wǎng)絡(luò)擁塞。近年來，深度強(qiáng)化學(xué)習(xí)在決策與智能化控制問題上取得了巨大的進(jìn)步。深度強(qiáng)化學(xué)習(xí)可以適應(yīng)環(huán)境的變化，已被用于求解網(wǎng)絡(luò)的路由問題[2-12]。現(xiàn)有的深度強(qiáng)化學(xué)習(xí)路由大多使用傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)(如多層感知機(jī)[4-11]、卷積神經(jīng)網(wǎng)絡(luò)[3,12]、長短期記憶神經(jīng)網(wǎng)絡(luò)[5])，并不適合學(xué)習(xí)圖結(jié)構(gòu)信息[2]，無法提取網(wǎng)絡(luò)拓?fù)鋱D的特征，這導(dǎo)致算法需要針對不同的網(wǎng)絡(luò)拓?fù)溥M(jìn)行修改和重新訓(xùn)練，無法適應(yīng)拓?fù)涞膭討B(tài)變化。

在圖像識別、自然語言處理領(lǐng)域，深度學(xué)習(xí)取得了巨大的成功，這得益于深度學(xué)習(xí)具有自動提取特征的能力。現(xiàn)代的深度學(xué)習(xí)方法通常遵循“端到端”的設(shè)計哲學(xué)，強(qiáng)調(diào)最小化先驗(yàn)表示與計算假設(shè)，并避免顯式的結(jié)構(gòu)與手工特征[13]。然而，在網(wǎng)絡(luò)路由領(lǐng)域，傳統(tǒng)的端到端深度學(xué)習(xí)難以提取網(wǎng)絡(luò)拓?fù)涮卣鳌Ｎ墨I(xiàn)[8]研究表明,深度學(xué)習(xí)結(jié)合傳統(tǒng)的特征工程具有更好的路由性能。另一種思路是使用圖神經(jīng)網(wǎng)絡(luò)自動提取網(wǎng)絡(luò)拓?fù)涞奶卣鳎瑢?shí)現(xiàn)對不同網(wǎng)絡(luò)拓?fù)涞姆夯痆2]。

文獻(xiàn)[2]基于K條候選路徑路由，使用消息傳遞神經(jīng)網(wǎng)絡(luò)(Message Passing Neural Network,MPNN)近似DQN(Deep Q-Network)強(qiáng)化學(xué)習(xí)算法中的Q值函數(shù)，DQN算法訓(xùn)練完成后，從K條候選路徑中選擇Q值最大的候選路徑作為業(yè)務(wù)路徑。然而，K條候選路徑路由需要事先為每對節(jié)點(diǎn)計算K條候選路徑，拓?fù)渥兓瘜?dǎo)致事先計算的K條候路徑失效，因此并不適用于動態(tài)拓?fù)渚W(wǎng)絡(luò)；另外，多約束的K條候選路由問題通常是NP難的，即使采用啟發(fā)式算法時間復(fù)雜度也非常大，候選路徑的數(shù)量(即K值)難以做到很大，這將嚴(yán)重限制路由的解空間。

針對現(xiàn)有的深度強(qiáng)化學(xué)習(xí)路由無法用于動態(tài)拓?fù)渚W(wǎng)絡(luò)的不足，本文提出面向動態(tài)拓?fù)涞纳疃葟?qiáng)化學(xué)習(xí)路由算法，主要貢獻(xiàn)如下：

(1)在PPO(Proximal Policy Optimization)[14]強(qiáng)化學(xué)習(xí)算法的基礎(chǔ)上，使用圖網(wǎng)絡(luò)[13]近似策略函數(shù)和值函數(shù)，顯式地將網(wǎng)絡(luò)拓?fù)渥鳛樯疃葟?qiáng)化學(xué)習(xí)的狀態(tài)，實(shí)現(xiàn)算法對不同拓?fù)涞姆夯?/p>

(2)將鏈路的權(quán)值作為策略函數(shù)的輸出，使用傳統(tǒng)的約束最短路由算法實(shí)時計算滿足約束的最小權(quán)值路徑，克服了深度學(xué)習(xí)難以學(xué)習(xí)約束路徑的難題，并避免了K條候選路徑路由無法適用于動態(tài)拓?fù)涞膯栴}，實(shí)現(xiàn)了路徑計算對拓?fù)涞倪m應(yīng)；

(3)通過仿真實(shí)驗(yàn)驗(yàn)證了本文所提方法可用于動態(tài)拓?fù)渚W(wǎng)絡(luò)環(huán)境，路由智能體可通過強(qiáng)化學(xué)習(xí)與網(wǎng)絡(luò)環(huán)境交互的經(jīng)驗(yàn)中自動學(xué)習(xí)路由策略。仿真結(jié)果表明本文所提的方法在網(wǎng)絡(luò)吞吐量方面優(yōu)于傳統(tǒng)的路由跳數(shù)最少的最短路算法。

1 背景介紹

1.1 圖網(wǎng)絡(luò)

圖網(wǎng)絡(luò)[13]是DeepMind在總結(jié)大量圖神經(jīng)網(wǎng)絡(luò)的基礎(chǔ)上進(jìn)一步推廣而得到的一種通用圖模型。圖網(wǎng)絡(luò)處理的圖可表示為G=(u,V,E)，其中，u為圖的全局屬性；V={vi}i=1:Nv為節(jié)點(diǎn)集合，vi是節(jié)點(diǎn)屬性，Nv是節(jié)點(diǎn)的數(shù)量；E={(ek,rk,sk)}k=1:Ne為邊集合，ek是邊屬性，rk是邊的宿節(jié)點(diǎn)索引，sk是邊的源節(jié)點(diǎn)索引，Ne是邊的數(shù)量。

圖網(wǎng)絡(luò)的基本構(gòu)建單元是圖網(wǎng)絡(luò)塊，圖網(wǎng)絡(luò)塊以圖作為輸入和輸出，實(shí)現(xiàn)對輸入圖的節(jié)點(diǎn)、邊和全局屬性的變換。圖網(wǎng)絡(luò)塊包含3個更新函數(shù)和3個聚合函數(shù)，如式(1)所示,其中，3個更新函數(shù)φe、φv、φu分別實(shí)現(xiàn)對邊屬性、節(jié)點(diǎn)屬性和全局屬性的更新，3個聚合函數(shù)ρe→v、ρe→u、ρv→u分別實(shí)現(xiàn)對節(jié)點(diǎn)的所有鄰邊屬性的聚合、圖中所有邊屬性的聚合和圖中所有節(jié)點(diǎn)屬性的聚合。聚合函數(shù)需要滿足排列不變性，即聚合的邊與節(jié)點(diǎn)的順序不影響聚合結(jié)果。常用的聚合函數(shù)包括逐元素的求和、求平均、求最大值函數(shù)。

(1)

其中:

圖網(wǎng)絡(luò)塊的計算過程為：首先,使用邊屬性更新函數(shù)φe對圖中的每條邊的屬性進(jìn)行更新；然后，使用鄰邊屬性聚合函數(shù)ρe→v對節(jié)點(diǎn)的鄰邊屬性進(jìn)行聚合，再使用節(jié)點(diǎn)更新函數(shù)φv對圖中的每個節(jié)點(diǎn)進(jìn)行更新；最后，使用節(jié)點(diǎn)屬性聚合函數(shù)ρe→u和邊屬性聚合函數(shù)ρv→u對圖中的所有節(jié)點(diǎn)屬性和圖中所有邊屬性分別進(jìn)行聚合后，使用全局屬性更新函數(shù)φu更新全局屬性。

圖網(wǎng)絡(luò)由1個或多個圖網(wǎng)絡(luò)塊組合而成，每個圖網(wǎng)絡(luò)塊相當(dāng)于傳統(tǒng)神經(jīng)網(wǎng)絡(luò)中的層，多個圖網(wǎng)絡(luò)塊可以序列方式組合(對應(yīng)傳統(tǒng)的多層感知機(jī))，也可以遞歸的方式組合(對應(yīng)傳統(tǒng)的遞歸神經(jīng)網(wǎng)絡(luò))。圖網(wǎng)絡(luò)具有很高的靈活性，如式(1)所示，圖網(wǎng)絡(luò)塊中的更新函數(shù)可以是包含傳統(tǒng)的神經(jīng)網(wǎng)絡(luò)在內(nèi)的任意函數(shù)，更新函數(shù)的參數(shù)都是可選的，聚合函數(shù)也可以是任何具有排列不變性的函數(shù)。圖網(wǎng)絡(luò)中的多個圖網(wǎng)絡(luò)塊的配置可以是共享的也可以是各不相同的。圖網(wǎng)絡(luò)的高靈活性使圖網(wǎng)絡(luò)具有很強(qiáng)的表示能力，可以表示很多類型的圖神經(jīng)網(wǎng)絡(luò)，如MPNN、關(guān)系網(wǎng)絡(luò)、深度集合、信念傳播嵌入等。

1.2 深度強(qiáng)化學(xué)習(xí)

強(qiáng)化學(xué)習(xí)是一個迭代學(xué)習(xí)的過程，在每輪迭代中，智能體在回報函數(shù)指導(dǎo)下探索狀態(tài)與動態(tài)空間。狀態(tài)空間用狀態(tài)集合S表示，動作空間用動作集合A表示，則智能體與環(huán)境的交互過程為：給定環(huán)境的某個狀態(tài)s∈S，智能體將執(zhí)行某個動作a∈A，環(huán)境的狀態(tài)將從s遷移到新狀態(tài)s′∈S，同時智能體從環(huán)境獲得回報r。強(qiáng)化學(xué)習(xí)的目標(biāo)是學(xué)習(xí)最大化長期累積回報的最優(yōu)策略。強(qiáng)化學(xué)習(xí)算法大體上可分為3類，即值函數(shù)方法、策略搜索方法和混合類型的AC(Actor-Critic)算法。值函數(shù)方法主要用于求解離散動作空間的強(qiáng)化學(xué)習(xí)問題，對于連續(xù)的動作空間，通常采用策略搜索或AC算法。AC算法是值函數(shù)方法與策略搜索方法的結(jié)合，其中actor與critic分別對應(yīng)策略函數(shù)與值函數(shù)，策略函數(shù)從值函數(shù)獲取反饋進(jìn)行學(xué)習(xí)。

深度學(xué)習(xí)可自動地從高維數(shù)據(jù)中提取低維的特征，可用于解決“維數(shù)災(zāi)難”問題，與強(qiáng)化學(xué)習(xí)結(jié)合，即深度強(qiáng)化學(xué)習(xí)，可解決傳統(tǒng)強(qiáng)化學(xué)習(xí)難以解決的具有高維的狀態(tài)和動作空間的決策問題。深度強(qiáng)化學(xué)習(xí)面臨的關(guān)鍵問題是深度神經(jīng)網(wǎng)絡(luò)引入后算法的不穩(wěn)定性問題。TRPO(Trust Region Policy Optimization)算法[15]使用信賴域(trust region)方法，阻止與先前的策略偏離太遠(yuǎn)的策略更新，使策略的性能單調(diào)性的改進(jìn)，防止災(zāi)難性的壞的策略更新。PPO算法[14]屬于上述的AC算法，是對TRPO算法的改進(jìn)，使用截斷(clipping)的替代目標(biāo)函數(shù)實(shí)現(xiàn)了對策略更新的限制，達(dá)到與TRPO使用復(fù)雜的共軛梯度算法保證策略更新約束類似的效果，但比TRPO算法要簡單很多，且通用性更好。

2 深度強(qiáng)化學(xué)習(xí)路由算法

2.1 深度強(qiáng)化學(xué)習(xí)路由模型

本文考慮如下動態(tài)路由場景：業(yè)務(wù)逐條到達(dá)網(wǎng)絡(luò)，路由算法需要為每條業(yè)務(wù)計算路徑，如果算路成功，則接受業(yè)務(wù)并為業(yè)務(wù)分配帶寬資源；如果算路失敗則拒絕業(yè)務(wù)，重復(fù)以上業(yè)務(wù)路由過程，直到連續(xù)m個業(yè)務(wù)被拒絕為止。上述路由問題中，網(wǎng)絡(luò)的拓?fù)洹㈡溌房捎脦捄蛥?shù)m是給定的、業(yè)務(wù)的源節(jié)點(diǎn)、宿節(jié)點(diǎn)、帶寬以及路由約束也是給定的，路由算法需要計算合適的路徑，讓業(yè)務(wù)路由過程停止時網(wǎng)絡(luò)的總吞吐量(即已成功路由業(yè)務(wù)的總帶寬)最大。在動態(tài)拓?fù)渚W(wǎng)絡(luò)中，網(wǎng)絡(luò)的拓?fù)淇赡芤蚬?jié)點(diǎn)移動、節(jié)點(diǎn)或鏈路故障而改變，路由算法需要具有適應(yīng)拓?fù)渥兓哪芰Γ赐負(fù)渥兓笠材苷＿\(yùn)行。

針對上述動態(tài)路由問題，本文提出圖網(wǎng)絡(luò)+PPO算法的面向動態(tài)拓?fù)渚W(wǎng)絡(luò)的深度強(qiáng)化學(xué)習(xí)路由算法。首先，在強(qiáng)化學(xué)習(xí)路由模型中，將網(wǎng)絡(luò)拓?fù)渥鳛榄h(huán)境狀態(tài)的一部分，讓路由智能體進(jìn)行路由決策時可以顯式地考慮網(wǎng)絡(luò)拓?fù)涞挠绊憽Ｆ浯危趧幼骺臻g設(shè)計時，將網(wǎng)絡(luò)中鏈路的權(quán)值作為路由智能體的動作，然后使用傳統(tǒng)的約束最短路算法計算最小成本路徑。這樣設(shè)計具有如下兩大優(yōu)勢：

(1)可以處理復(fù)雜的路由約束。現(xiàn)有的深度學(xué)習(xí)技術(shù)很難直接輸出滿足復(fù)雜約束的路徑，以鏈路權(quán)值作為動作，可有機(jī)地將深度學(xué)習(xí)技術(shù)與傳統(tǒng)的帶約束的最短路由算法結(jié)合起來，既可很好地處理路由約束，又不損害深度強(qiáng)化學(xué)習(xí)對路由的控制，因?yàn)橐坏╂溌窓?quán)值確定后，帶約束的最小成本路徑也可唯一確定。

(2)可解決K候選路徑路由無法用于動態(tài)拓?fù)鋱鼍奥酚傻膯栴}。以鏈路權(quán)值為動作，然后實(shí)時計算最小權(quán)值路徑，可避免拓?fù)渥兓驥候選路徑失效的問題，而且還解決了多約束的K條路徑計算難題(NP難問題)，以及K候選路徑限制路由解空間損失路由優(yōu)度的問題。

將鏈路權(quán)值作為動作，會導(dǎo)致連續(xù)型的動作空間，將無法使用DQN等值函數(shù)強(qiáng)化學(xué)習(xí)算法，因此本文選擇使用PPO算法。PPO算法是目前最先進(jìn)的連續(xù)型深度強(qiáng)化學(xué)習(xí)算法之一，PPO算法的全面介紹可參閱文獻(xiàn)[14]。最后，圖網(wǎng)絡(luò)被用于近似PPO算法框架中的策略函數(shù)與值函數(shù)，以解決傳統(tǒng)的深度神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)路由策略無法適應(yīng)拓?fù)渥兓膯栴}。

本文將上述動態(tài)路由問題建模為如下深度強(qiáng)化學(xué)習(xí)路由問題。路由智能體通過與網(wǎng)絡(luò)環(huán)境交互學(xué)習(xí)可最大化網(wǎng)絡(luò)吞吐量的最優(yōu)路由策略。環(huán)境狀態(tài)定義為網(wǎng)絡(luò)的當(dāng)前拓?fù)洹㈡溌返目捎脦挕?dāng)前業(yè)務(wù)的源、宿節(jié)點(diǎn)與帶寬，智能體的動作定義為當(dāng)前拓?fù)渲忻織l鏈路的權(quán)值。網(wǎng)絡(luò)環(huán)境根據(jù)路由智能體的動作(即鏈路權(quán)值)使用傳統(tǒng)的帶約束的最短路算法計算最小成本路徑，如果算路成功則下發(fā)業(yè)務(wù)，并向路由智能體反饋回報，回報為業(yè)務(wù)的帶寬；如果算路失敗，則回報為0。網(wǎng)絡(luò)環(huán)境從空網(wǎng)開始，當(dāng)下一個業(yè)務(wù)到達(dá)后，網(wǎng)絡(luò)環(huán)境切換到下一個狀態(tài)，重復(fù)上述過程直到連續(xù)m個業(yè)務(wù)算路失敗，則當(dāng)前幕(episode)結(jié)束，累積回報(又稱幕回報)即為網(wǎng)絡(luò)的吞吐量。

2.2 策略函數(shù)與值函數(shù)的圖網(wǎng)絡(luò)表示

PPO算法屬于AC算法，AC算法通過策略函數(shù)(即actor)學(xué)習(xí)環(huán)境狀態(tài)到智能體動作的映射，通過值函數(shù)(即critic)評估智能體的當(dāng)前動作。本文使用圖網(wǎng)絡(luò)參數(shù)化PPO算法中的策略函數(shù)和值函數(shù)，圖網(wǎng)絡(luò)中的參數(shù)通過PPO算法進(jìn)行學(xué)習(xí)。圖網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示，先用輸入圖網(wǎng)絡(luò)塊GNinp對輸入圖Ginp進(jìn)行處理得到圖G0，然后使用核心圖網(wǎng)絡(luò)塊GNcore對G0重復(fù)處理M次得到圖GM(M為超參)，最后使用輸出圖網(wǎng)絡(luò)塊GNout對圖GM處理得到輸出圖Gout。

圖1 圖網(wǎng)絡(luò)結(jié)構(gòu)示意圖

輸入圖網(wǎng)絡(luò)塊GNinp的配置如圖2所示，e、v和u分別表示輸入圖Ginp中的邊、節(jié)點(diǎn)和全局屬性，φe、φv和φu分別為邊屬性、節(jié)點(diǎn)屬性和全局屬性更新函數(shù)，更新后的邊、節(jié)點(diǎn)和全局屬性分別表示為e′、v′和u′。輸入圖網(wǎng)絡(luò)塊中的3個更新函數(shù)分別為3個無激活函數(shù)的單層神經(jīng)網(wǎng)絡(luò)，實(shí)現(xiàn)對輸入圖Ginp的所有邊、節(jié)點(diǎn)和全局屬性的變換，使變換后的屬性具有相同的維數(shù)d(d為超參)，以便于后續(xù)核心圖網(wǎng)絡(luò)塊的處理。

圖2 輸入圖網(wǎng)絡(luò)塊Ginp配置

圖3 核心圖網(wǎng)絡(luò)塊Gcore配置

(2)

(3)

u′=φu(u,ν′,ε′)=MLPu(u,ν′,ε′)，

(4)

(5)

(6)

(7)

輸出圖網(wǎng)絡(luò)塊GNout的配置如圖4所示，只對圖GM的邊屬性和全局屬性進(jìn)行變換，以適配PPO算法框架。邊更新函數(shù)φe被參數(shù)化為1個無激活函數(shù)的單層神經(jīng)網(wǎng)絡(luò)，輸入層有d個神經(jīng)元，輸出層有2個神經(jīng)元，分別表示邊對應(yīng)的鏈路的權(quán)值均值和對數(shù)標(biāo)準(zhǔn)差。全局更新函數(shù)φu被參數(shù)化為1個無激活函數(shù)的單層神經(jīng)網(wǎng)絡(luò)，輸入層有d個神經(jīng)元，輸出層只有1個神經(jīng)元，表示值函數(shù)的值。

圖4 輸出圖網(wǎng)絡(luò)塊配置

2.3 環(huán)境狀態(tài)的圖表示

圖網(wǎng)絡(luò)的輸入是圖Ginp，因此，需要將環(huán)境的狀態(tài)表示為圖。環(huán)境的狀態(tài)包括網(wǎng)絡(luò)拓?fù)洹⒕W(wǎng)絡(luò)可用帶寬和當(dāng)前業(yè)務(wù)源節(jié)點(diǎn)、宿節(jié)點(diǎn)和帶寬。網(wǎng)絡(luò)拓?fù)浔旧砜梢灾苯佑脠D表示，其他信息則需要以圖的節(jié)點(diǎn)屬性、邊屬性和全局屬性的形式表示。如圖5所示，邊屬性為1維向量，圖5中的8條鏈路，每鏈路的可用帶寬為5 Mb/s，表示為邊屬性值都是5。每個節(jié)點(diǎn)屬性為2維向量，第1個元素為入網(wǎng)帶寬，第2個元素表示出網(wǎng)帶寬，則業(yè)務(wù)可表示為節(jié)點(diǎn)屬性，即業(yè)務(wù)的源節(jié)點(diǎn)1的入網(wǎng)帶寬為2，業(yè)務(wù)宿節(jié)點(diǎn)6的出網(wǎng)帶寬為2，其他的節(jié)點(diǎn)屬性都為0。全局屬性為1維向量表示網(wǎng)絡(luò)的總可用帶寬，網(wǎng)絡(luò)共有8條鏈路，每條鏈路帶寬為5 Mb/s，共40 Mb/s，故全局屬性值為40。

圖5 環(huán)境狀態(tài)的圖表示

3 仿真結(jié)果及分析

3.1 仿真場景設(shè)置

本文所提的PPO+圖網(wǎng)絡(luò)深度強(qiáng)化學(xué)習(xí)路由智能體是在Stable Baselines[16]中PPO算法源代碼的基礎(chǔ)上，繼承ActorCriticPolicy類并使用圖網(wǎng)絡(luò)庫[13]的相關(guān)函數(shù)實(shí)現(xiàn)的；網(wǎng)絡(luò)環(huán)境則是對OpenAI Gym框架[17]進(jìn)行擴(kuò)展以支持可變的拓?fù)鋱D作為狀態(tài)空間和動作空間。

路由智能體在隨機(jī)生成的包含15個節(jié)點(diǎn)30條邊的網(wǎng)絡(luò)拓?fù)渖嫌?xùn)練完成后，為了驗(yàn)證路由智能體對動態(tài)拓?fù)涞倪m應(yīng)性，測試使用了隨機(jī)生成的3個完全不同的拓?fù)洌謩e是15個節(jié)點(diǎn)30條邊的小型網(wǎng)絡(luò)case1_15n30m、30個節(jié)點(diǎn)60條邊的中型網(wǎng)絡(luò)case2_30n60m和50個節(jié)點(diǎn)100條邊的大型網(wǎng)絡(luò)case3_50n100m。訓(xùn)練網(wǎng)絡(luò)和測試網(wǎng)絡(luò)中，鏈路的總帶寬都為20 Mb/s。在路由智能體的網(wǎng)絡(luò)環(huán)境中，業(yè)務(wù)逐個到達(dá)網(wǎng)絡(luò)，業(yè)務(wù)的源宿節(jié)點(diǎn)對由重力模型[17]生成，業(yè)務(wù)的帶寬都為1 Mb/s。

路由智能體的超參設(shè)置如表1所示。PPO算法訓(xùn)練過程如下：路由智能體與4個網(wǎng)絡(luò)環(huán)境同時交互，路由智能體在每個網(wǎng)絡(luò)環(huán)境執(zhí)行128步，共得到512個樣本，重復(fù)使用這些樣本進(jìn)行4次訓(xùn)練，每次訓(xùn)練都將所有樣本隨機(jī)打亂，然后分成4個每批128個樣本的迷你批，使用隨機(jī)梯度下降法優(yōu)化損失函數(shù)。重復(fù)以上采樣與訓(xùn)練過程，當(dāng)達(dá)到70萬步時退出。

表1 圖網(wǎng)絡(luò)的超參設(shè)置

仿真測試中使用兩個對比路由策略，即RND (Random)和SPR(Shortest Path Routing)。RND在鏈路權(quán)值取值范圍內(nèi)，按均分分布隨機(jī)設(shè)置鏈路權(quán)值，可實(shí)現(xiàn)網(wǎng)絡(luò)的負(fù)載均衡。SPR即最短路算法，將每條鏈路的權(quán)值都設(shè)置為1，可以最省地使用網(wǎng)絡(luò)帶寬資源。

本節(jié)所有的仿真測試都是在英特爾酷睿i7-9750H(12線程，2.6 GHz)、32 GB內(nèi)存、英偉達(dá)Quadro P600顯卡、Windows 10家庭版的移動工作站上進(jìn)行。

3.2 測試結(jié)果

圖6為路由智能體訓(xùn)練時幕回報隨時間步的變化曲線，圖7是損失函數(shù)隨時間步的變化曲線，從圖中可看出，訓(xùn)練過程總共運(yùn)行了70萬步，當(dāng)訓(xùn)練進(jìn)行到30萬步(即23 min)時，路由智能體就收斂了。

圖6 路由智能體訓(xùn)練期間的幕回報

圖7 路由智能體訓(xùn)練期間的損失函數(shù)值

PPO算法的損失函數(shù)[14]計算公式如式(8)所示:

(8)

當(dāng)路由智能體訓(xùn)練完成后，在3個網(wǎng)絡(luò)拓?fù)渖吓c對比算法進(jìn)行了路由性能測試。每種算法測試100次然后對測試結(jié)果取平均，結(jié)果如表2所示，其中，路由智能體的測試結(jié)果在表2中用PPO算法標(biāo)記。

表2 100次測試的平均路由性能對比

測試結(jié)果表明，PPO算法具有最大的網(wǎng)絡(luò)吞量，與RND算法相比，網(wǎng)絡(luò)吞吐量提升了15.76%～19.36%。由于RND算法隨機(jī)設(shè)置鏈路權(quán)值，相當(dāng)于不考慮路由成本極端地做負(fù)載均衡，很多路徑都不是最短路，因此具有最長的平均路徑長度、最大的平均鏈路利用率，網(wǎng)絡(luò)吞吐量也是最小的。SPR算法只考慮路由成本最小，完全不考慮負(fù)載均衡，因此，平均路徑長度和平均鏈路利用率都比RND算法的小，吞吐量與RND算法相比有很大提升，但吞吐量并不是最大的。PPO算法同時考慮路由成本與負(fù)載均衡，可避免SPR算法因所有業(yè)務(wù)使用最短路造成前面的業(yè)務(wù)耗盡了某些關(guān)鍵鏈路帶寬，導(dǎo)致后面的業(yè)務(wù)只能使用很長的路徑的問題，因此，PPO算法的平均路徑長度比SPR算法的更短，網(wǎng)絡(luò)吞吐量更大。此外，在以上3個不同規(guī)模的測試網(wǎng)例中，PPO算法表現(xiàn)出一致的結(jié)果，即在平均吞吐量上都優(yōu)于對比算法RND和SPR,在平均鏈路利用率上介于RND與SPR之間，在平均路徑長度上都短于RND和SPR。以上結(jié)果表明，PPO算法具有對不同拓?fù)涞姆夯裕蛇m用于動態(tài)拓?fù)渚W(wǎng)絡(luò)環(huán)境。

4 結(jié)束語

針對現(xiàn)有的深度強(qiáng)化學(xué)習(xí)路由算法無法適應(yīng)網(wǎng)絡(luò)拓?fù)渥兓膯栴}，本文提出了一種面向動態(tài)拓?fù)渚W(wǎng)絡(luò)的深度強(qiáng)化學(xué)習(xí)路由技術(shù)。首先，通過將網(wǎng)絡(luò)拓?fù)渥鳛榄h(huán)境狀態(tài)的一部分，讓路由智能體顯式考慮網(wǎng)絡(luò)拓?fù)鋵β酚刹呗缘挠绊懀欣诼酚芍悄荏w實(shí)現(xiàn)對不同網(wǎng)絡(luò)拓?fù)涞姆夯黄浯危ㄟ^將動作表示為鏈路的權(quán)值，然后結(jié)合傳統(tǒng)最小成本路由算法算路，有效解決了深度學(xué)習(xí)難以直接學(xué)習(xí)滿足復(fù)雜約束的路徑問題，同時也避免了K候選路徑路由無法用于動態(tài)拓?fù)涞膯栴}；最后，通過結(jié)合最先進(jìn)的連續(xù)型深度強(qiáng)化學(xué)習(xí)PPO算法與圖網(wǎng)絡(luò)技術(shù)，解決了傳統(tǒng)的深度神經(jīng)網(wǎng)絡(luò)難以提取拓?fù)涮卣鳎Ｐ蜔o法在不同拓?fù)浞夯膯栴}。本文通過仿真實(shí)現(xiàn)驗(yàn)證了所提技術(shù)的有效性，結(jié)果表明本文所提方法可獲得比最短路由算法更大的網(wǎng)絡(luò)吞吐量，且具有對不同網(wǎng)絡(luò)拓?fù)涞姆夯裕蛇m用于動態(tài)拓?fù)渚W(wǎng)絡(luò)環(huán)境。

與其他機(jī)器學(xué)習(xí)模型一樣，本文的路由智能體也要求訓(xùn)練環(huán)境與測試環(huán)境具有相近或一致的業(yè)務(wù)模型，后續(xù)工作將研究能在不同業(yè)務(wù)模型間遷移的智能路由技術(shù)。