基于深度強化學習的無線網(wǎng)絡智能路由算法

孔凌輝，饒哲恒，徐彥彥，潘少明

（武漢大學 測繪遙感信息工程國家重點實驗室，武漢 430079）

0 概述

路由是為網(wǎng)絡中的數(shù)據(jù)包選擇傳輸路徑的過程，是通信網(wǎng)的核心功能之一。合適的路由決策能夠更合理地利用網(wǎng)絡資源、提升網(wǎng)絡性能。在無線網(wǎng)絡中網(wǎng)絡拓撲結(jié)構(gòu)高度動態(tài)變化，而現(xiàn)有的路由算法難以適應動態(tài)變化的網(wǎng)絡拓撲結(jié)構(gòu)，無法做出最恰當?shù)穆酚蓻Q策，給網(wǎng)絡性能的提升帶來了挑戰(zhàn)。

傳統(tǒng)的路由協(xié)議如開放式最短路徑優(yōu)先［1］（Open Shortest Path First，OSPF），僅根據(jù)當前網(wǎng)絡拓撲結(jié)構(gòu)選擇最短路徑，不考慮實時網(wǎng)絡狀態(tài)，難以做出恰當?shù)穆酚蓻Q策。為解決此類問題，研究人員提出基于深度學習和強化學習的智能路由算法［2-3］。然而，基于深度學習的智能路由算法過于依賴訓練樣本，而強化學習無法對復雜的網(wǎng)絡特征進行有效表征，導致學習緩慢或無效。

深度強化學習（Deep Reinforcement Learning，DRL）集成了深度學習在視覺等感知問題上強大的理解能力以及強化學習的決策能力，在處理無線網(wǎng)絡的復雜流量等領域具有較優(yōu)的能力［4-5］?；贒RL 的智能路由算法利用神經(jīng)網(wǎng)絡提取網(wǎng)絡特征，利用強化學習生成路由決策。研究表明，相較于傳統(tǒng)方法和基于強化學習的方法，基于DRL 的智能路由算法能夠更好地學習網(wǎng)絡狀態(tài)并據(jù)此做出更恰當?shù)穆酚蓻Q策［6-7］。但是，大部分基于DRL 的智能路由算法難以適應動態(tài)變化的網(wǎng)絡拓撲結(jié)構(gòu)。這是因為現(xiàn)有方法大多使用的是標準神經(jīng)網(wǎng)絡，如全連接神經(jīng)網(wǎng)絡、卷積神經(jīng)網(wǎng)絡，這些網(wǎng)絡在處理圖像等歐氏空間數(shù)據(jù)方面取得了巨大的成功，但是不具備準確提取和充分利用網(wǎng)絡拓撲結(jié)構(gòu)等非歐氏空間數(shù)據(jù)的能力。

近年來，圖神經(jīng)網(wǎng)絡（Graph Neural Network，GNN）［8］克服了上述缺點，在學習和處理圖結(jié)構(gòu)信息方面表現(xiàn)出明顯的優(yōu)勢，被廣泛應用于圖像識別［9］等領域。GNN 被用來對圖結(jié)構(gòu)進行建模和操作，有助于學習圖元素之間的關系和規(guī)則，實現(xiàn)關系推理和組合泛化。網(wǎng)絡拓撲結(jié)構(gòu)是一種典型的圖結(jié)構(gòu)，研究表明，GNN 在網(wǎng)絡建模和路由優(yōu)化領域取得了顯著的成果［10-11］。消息傳遞神經(jīng)網(wǎng)絡（Message Passing Neural Network，MPNN）［12］是GNN 的一個變種，被廣泛用于處理圖結(jié)構(gòu)信息，通過迭代消息傳遞算法在圖的節(jié)點之間傳遞消息，使每個節(jié)點都能獲取到周圍鄰居的特征，擴大節(jié)點的感知域，有助于進行更恰當?shù)穆酚蓻Q策。網(wǎng)絡拓撲作為一種標準的圖結(jié)構(gòu)，圖中的每條邊都具有自己的特征，使用MPNN能夠有效聚合多階鄰居邊的特征，為路由決策提供更全面的信息。

此外，在路由路徑的生成方面，現(xiàn)有的智能路由算法主要分為基于路徑選擇和逐跳路由生成方式［13］?；诼窂竭x擇的方式預先計算所有可行路徑，根據(jù)網(wǎng)絡狀態(tài)選擇合適的路徑。這種方式能夠有效緩解路由空洞、路由環(huán)路等問題。但是，隨著拓撲規(guī)模增大，可行路徑的數(shù)量呈指數(shù)級增長，容易造成算法訓練緩慢甚至難以收斂［14］。為加快模型的訓練速度，研究人員提出多種剪枝搜索空間的方法。文獻［15］提出選取k條最短可行路徑，再從k條路徑中進行路由決策。文獻［16］提出結(jié)合ILP 求解器的智能路由算法，先由DRL 算法給出一個初始解，再用ILP 求解器在初始解的子搜索空間中搜索最終解。這些方法通過犧牲算法的最優(yōu)性來提升收斂速度，但是很可能導致算法無法收斂到全局最優(yōu)解。逐跳路由生成方式每次只進行下一跳轉(zhuǎn)發(fā)節(jié)點的選擇，通過多步?jīng)Q策生成完整的路由路徑。相比路徑選擇方式，逐跳路由生成方式能夠顯著降低搜索空間的維度，提高算法的可擴展性，使算法適用于較大的網(wǎng)絡拓撲，但受限于感知域較小，容易陷入局部最優(yōu)問題。文獻［17］的研究表明，隨著拓撲結(jié)構(gòu)規(guī)模增大，基于路徑選擇方式的可行路徑數(shù)量呈指數(shù)級增長，其搜索空間遠大于逐跳路由生成方式。

針對現(xiàn)有的智能路由算法難以適應動態(tài)變化的網(wǎng)絡拓撲，以及基于路徑選擇和逐跳路由生成方式存在的訓練速度緩慢問題，本文提出一種結(jié)合圖神經(jīng)網(wǎng)絡和深度強化學習的智能路由算法MPNNDQN。利用MPNN 的圖數(shù)據(jù)結(jié)構(gòu)處理不規(guī)則的網(wǎng)絡拓撲，對網(wǎng)絡拓撲中當前節(jié)點的k階鄰居進行特征聚合，根據(jù)聚合的鄰居信息預測下一跳轉(zhuǎn)發(fā)鄰居的價值。根據(jù)預測結(jié)果，利用DQN（Deep Q-Network）模型進行恰當?shù)穆酚蓻Q策，實現(xiàn)一種能夠更好地適應動態(tài)變化網(wǎng)絡拓撲結(jié)構(gòu)的智能路由算法。此外，基于路徑選擇和逐跳路由生成，提出一種基于k階鄰居信息的逐跳路由生成方法，以適用于中大型網(wǎng)絡拓撲。同時，利用MPNN 聚合的k階鄰居信息，提前感知到路由空洞等異常情況并進行規(guī)避。

1 模型框架

本文提出結(jié)合MPNN 和DQN 的智能路由算法，在NS3 上部署仿真網(wǎng)絡環(huán)境并進行信息采集，在OpenAI Gym 平臺上部署DQN 的智能體和MPNN 框架，并進行特征提取、學習以及路由決策。本文提出智能路由算法的路由決策架構(gòu)如圖1 所示，其架構(gòu)分為數(shù)據(jù)平面和控制平面2 層。

圖1 智能路由方案架構(gòu)Fig.1 Architecture of intelligent routing scheme

數(shù)據(jù)平面通過控制器收集拓撲信息，建立全網(wǎng)視圖，在控制平面部署的MPNN-DQN 算法基于此信息做出路由決策，由數(shù)據(jù)平面負責路由決策的執(zhí)行?？刂破矫娴墓ぷ鬟^程主要包括網(wǎng)絡狀態(tài)感知、特征提取、路由決策、獎勵生成和模型訓練。

1）網(wǎng)絡狀態(tài)感知。從NS3 仿真網(wǎng)絡環(huán)境中獲取當前網(wǎng)絡拓撲結(jié)構(gòu)、當前路由需求、實時網(wǎng)絡狀態(tài)信息以及QoS 信息，更新記錄狀態(tài)信息的狀態(tài)向量。

2）特征提取。根據(jù)狀態(tài)向量，利用MPNN 聚合每條邊的k階鄰居信息，將聚合后的特征進行輸出，幫助智能體進行路由決策。

3）路由決策。智能體根據(jù)MPNN 聚合后的特征，通過DQN 模型做出路由決策。

4）獎勵生成。在執(zhí)行路由決策后，根據(jù)從NS3 底層獲取到狀態(tài)向量中的QoS 信息，計算得到的獎勵值，并用于模型訓練。

5）模型訓練。將過去的決策作為樣本，對同回合內(nèi)的樣本進行拼接后存入經(jīng)驗回放緩沖區(qū)，用于模型的訓練。

2 智能路由設計

2.1 網(wǎng)絡與流量模型

假設將網(wǎng)絡表示為一個有向圖G=(V,E)，其中，V={v1,v2,…,vn}表示網(wǎng)絡中的節(jié)點（路由器），E={e(v1,v2),e(v2,v1),…,e(vn,vm)}表示路由器之間的鏈路。

本文所設計的深度強化學習在每一回合中需要完成從源節(jié)點到目的節(jié)點且指定流量大小的路由需求。本文采用基于k階鄰居信息的逐跳路由生成方法，由多步?jīng)Q策共同完成一次路由需求，因此將每一步的路由需求表示為R={vsrc,vdst,vcur,fDemand}，其中，vsrc表示源節(jié)點，vdst表示目的節(jié)點，vcur表示在逐跳路由生成方式下的當前節(jié)點，fDemand表示流量大小。

2.2 網(wǎng)絡狀態(tài)感知

本文模型利用網(wǎng)絡狀態(tài)監(jiān)視器在每個監(jiān)視周期內(nèi)讀取數(shù)據(jù)包統(tǒng)計信息，從中獲取當前網(wǎng)絡拓撲結(jié)構(gòu)、當前路由需求以及每條鏈路的特征，計算得到當前周期內(nèi)的實時網(wǎng)絡狀態(tài)，以及反映路由決策效果的QoS 信息，將這些信息封裝成狀態(tài)向量，并作為環(huán)境提供給智能體的狀態(tài)信息。

本文模型根據(jù)網(wǎng)絡狀態(tài)監(jiān)視器反饋的信息，得到每條鏈路的特征代表鏈路v在周期t的網(wǎng)絡狀態(tài)。Fbandwidth表示當前周期內(nèi)該鏈路的物理帶寬，F(xiàn)delay表示鏈路的物理時延，F(xiàn)packets表示該鏈路上已路由的數(shù)據(jù)包數(shù)，fDemand表示當前周期內(nèi)的流量大小。根據(jù)拓撲中每條鏈路的特征構(gòu)造特征向量，并作為輸入MPNN 的信息。

根據(jù)監(jiān)視周期內(nèi)傳入數(shù)據(jù)報文中記錄的信息計算得到的QoS 信息，本文考慮的QoS 信息如表1 所示，這些信息將作用于第2.5 節(jié)的獎勵生成。

表1 本文考慮的QoS 信息 Table 1 QoS information to consider in this paper

2.3 特征提取

針對路徑選擇方式和逐跳路由生成方式的不足，本文提出一種基于k階鄰居信息的逐跳路由生成方法MPNN-DQN。通過MPNN 聚合每個節(jié)點的k階鄰居信息，為逐跳路由生成方式的路由決策提供更大的感知域，能夠感知到路由空洞或孤立節(jié)點等異常情況并進行規(guī)避，有助于進行更恰當?shù)穆酚蓻Q策，最大化利用網(wǎng)絡資源，從而提升網(wǎng)絡性能。

節(jié)點鏈路轉(zhuǎn)換示意圖如圖2 所示。

圖2 節(jié)點鏈路轉(zhuǎn)換示意圖Fig.2 Schematic diagram of node-link transformation

本文根據(jù)網(wǎng)絡狀態(tài)監(jiān)視器反饋的信息構(gòu)建網(wǎng)絡拓撲，并對其進行節(jié)點鏈路轉(zhuǎn)換，將拓撲中的邊進行轉(zhuǎn)換并作為MPNN 的輸入對象，使得MPNN 能夠?qū)︽溌诽卣鬟M行更好地學習。

MPNN 將圖卷積視為消息傳遞過程，在圖節(jié)點之間對信息進行直接傳遞。MPNN 的前向傳遞有2 個階段：消息傳遞階段（Message Passing）和讀出階段（Readout）。在消息傳遞階段中，消息函數(shù)定義為m，節(jié)點更新函數(shù)定義為u，t為運行的時間步。MPNN 的消息傳遞和節(jié)點狀態(tài)更新過程如圖3所示。

圖3 節(jié)點1 在2 個時間步內(nèi)的消息更新過程Fig.3 Message update process for node one within two time steps

在消息傳遞過程中，通過式（1）的消息函數(shù)m聚合節(jié)點1 所有鄰居節(jié)點的特征。

其中：N(1)表示節(jié)點1 的鄰居節(jié)點集；表示中間狀態(tài)。節(jié)點1 的更新狀態(tài)過程如式（2）所示：

經(jīng)過k輪的消息傳遞和狀態(tài)更新過程，每個節(jié)點聚合了k階鄰居的特征信息。特征提取流程如圖4所示。

圖4 特征提取流程Fig.4 Procedure of feature extraction

在每輪循環(huán)中，智能體對每條邊的一階鄰居邊進行消息傳遞和聚合，采用一個循環(huán)神經(jīng)網(wǎng)絡（Recurrent Neural Network，RNN）實現(xiàn)節(jié)點特征更新。經(jīng)過k輪后，即完成了k階鄰居信息的聚合。

MPNN 讀出階段的Readout 函數(shù)來計算信息聚合后整張圖的特征向量，如式（3）所示：

其中：V表示圖中的節(jié)點集；計算得到的結(jié)果為MPNN 預測得到的當前動作價值。智能體將根據(jù)此信息進行路由決策。

2.4 路由決策

智能體找出當前節(jié)點vcur的所有鄰居節(jié)點，針對每一種情況生成特征向量輸入MPNN，根據(jù)MPNN的預測結(jié)果，利用DQN 模型的ε-greedy 策略做出最終的路由決策，即下一跳轉(zhuǎn)發(fā)鄰居的選擇。

ε-greedy 策略的決策方式如式（4）所示：

其中：at表示在周期t內(nèi)做出的路由決策；r表示在[0,1]范圍內(nèi)的隨機數(shù)；ε表示初值為1 的控制隨機探索概率的變量，其值隨著迭代次數(shù)增加逐漸減小。當r>ε時，選擇預期價值最大的動作；當r≤ε時，隨機選擇一個可行的動作。這種方法的意義在于迭代初期，讓模型以較大概率進行隨機探索，盡可能探索所有情況。隨著迭代次數(shù)增加，增大選擇預期價值最大動作的概率。其衰減函數(shù)如式（5）所示：

其中：εstart為迭代開始時ε的初值；εend表示ε的最小閾值；εdecay為衰減因子。隨著迭代次數(shù)I的增加，ε的值逐漸減小，逐漸收斂至εend，達到策略穩(wěn)定的效果。

ε-greedy 作為DQN 模型中最常見的學習策略，本文通過設置可變的ε值，使DQN 模型在訓練初期即可探索到所有情況，并在訓練后期進行更高效學習，從所有情況中選取全局最優(yōu)解，做出高質(zhì)量的路由決策。本文采用基于k階鄰居信息的逐跳路由方法，其做出的下一跳轉(zhuǎn)發(fā)鄰居選擇決定了下一步?jīng)Q策的搜索空間。本文通過聚合k階鄰居信息，避免在路由決策時只注重下一跳最優(yōu)，而是從更高的角度選擇最合適的情況，避免逐跳路由生成方式因感知域小而陷入局部最優(yōu)的情況。

2.5 獎勵生成

在每次路由決策執(zhí)行后，本文根據(jù)設計的獎勵函數(shù)給出獎勵值，獎勵值的大小反映了此次決策的優(yōu)劣程度。本文方法通過獲取到的QoS 信息來計算獎勵，這些QoS 信息包括平均傳輸時延、平均吞吐量、丟包率以及鏈路負載。

本文設計的獎勵函數(shù)除了衡量路由決策的優(yōu)劣、指導模型的收斂以外，還起到了避免路由環(huán)路的重要作用。針對逐跳路由生成方式路由決策可能存在的路由環(huán)路問題，獎勵函數(shù)對產(chǎn)生路由環(huán)路的情況進行了“懲罰”，降低再次出現(xiàn)環(huán)路的概率。同時，本文對成功到達目的地、完成當前路由需求的情況進行“獎勵”，逐漸引導算法朝著全局最優(yōu)的方向收斂。獎勵函數(shù)的詳細內(nèi)容如式（6）所示：

其中：Di表示平均時延；Li表示丟包率；Pi表示鏈路負載程度；Ti表示平均吞吐量；vdst表示當前路由需求的目的節(jié)點；vi表示當前節(jié)點；S表示當前回合已路由過的 節(jié)點集。本文使 用Di、Li、Pi、Ti指標計算獎勵，對計算結(jié)果歸一化并取負值，使得獎勵值與吞吐量呈正相關，與時延、丟包率、負載程度呈負相關的關系。除異常情況與正確到達目的節(jié)點的情況以外，在其余情況下獎勵值的取值范圍為(-1,0]。若vi?S，說明出現(xiàn)了環(huán)路，將獎勵值設為最小值-1，降低環(huán)路出現(xiàn)的概率；若vi?S且vi=vdst，則代表完成當前輪次的流量需求，對其獎勵值額外加1，引導算法向正確完成路由需求的方向收斂；其余情況給出正常獎勵值。

生成的獎勵值將與狀態(tài)信息、動作信息等一起輸入到智能體，用于模型的訓練。

2.6 模型訓練

深度強化學習從過往的經(jīng)驗中進行學習，將每回合生成的樣本存入經(jīng)驗回放緩沖區(qū)，通過隨機采樣的方法對模型進行訓練。

本文提出的MPNN-DQN 算法采用MPNN 進行特征提取，利用DQN 進行路由決策，本文使用的DQN 模型以Double DQN算法［18］為基礎。DQN 模型架構(gòu)如圖5 所示，利用策略生成網(wǎng)絡做出路由決策，將同回合內(nèi)的決策樣本進行拼接后存入經(jīng)驗回放緩沖區(qū)，并通過隨機采樣的方式進行模型訓練，更新神經(jīng)網(wǎng)絡的參數(shù)。

圖5 DQN 模型架構(gòu)Fig.5 Architecture of DQN model

為提升神經(jīng)網(wǎng)絡更新的穩(wěn)定性，本文引入文獻［17］提出的雙Q值網(wǎng)絡，通過2 個結(jié)構(gòu)相同但參數(shù)不同的神經(jīng)網(wǎng)絡提升訓練的穩(wěn)定性。通過2 個網(wǎng)絡計算得到的誤差，對網(wǎng)絡參數(shù)進行更新。誤差函數(shù)的定義如式（7）所示：

其中：θ-和θ為2 個神經(jīng)網(wǎng)絡的參數(shù)。策略生成網(wǎng)絡的參數(shù)在訓練過程中不斷更新，目標策略網(wǎng)絡則具有較穩(wěn)定版本的參數(shù)。在訓練過程中，策略生成網(wǎng)絡定期更新目標策略網(wǎng)絡的參數(shù)，使得訓練逐漸向一個固定的目標收斂，而不是一直改變的目標。

在MPNN-DQN 方法的每一回合中，通過多步?jīng)Q策完成從源節(jié)點vsrc到目的節(jié)點vdst的路由需求。每一回合的最后一步?jīng)Q策的獎勵值反映了本回合整體的決策效果，即每一步?jīng)Q策生成的樣本并沒有包含本回合決策的完整特征，而樣本特征不全面容易造成模型訓練效率降低。為此，本文提出一種樣本拼接方法對同回合內(nèi)的訓練樣本進行處理，將同一回合內(nèi)每一步的決策結(jié)果生成一個“小樣本”，當回合結(jié)束后，將同回合內(nèi)的所有“小樣本”拼接成一個“大樣本”，使其特征更全面，以提高模型的訓練效率。同回合內(nèi)樣本的拼接方式如式（8）所示：

3 仿真實驗

3.1 仿真環(huán)境

本文使 用NS3-Gym［19］編寫MPNN-DQN 的仿 真實驗環(huán)境。仿真平臺運行于Ubuntu18.04 操作系統(tǒng)，硬件平臺為具有64 個核心、256 GB RAM，并配備GeForce RTX 3090 GPU 的服務器。算法使用Keras實現(xiàn)（基于TensorFlow 2.7.0），語言版本為Python 3.7。

3.2 實驗設置

為測試MPNN-DQN 在動態(tài)變化網(wǎng)絡拓撲下的性能，本文設置了3 種不同的測試場景，分別為在原拓撲上的性能、在部分鏈路發(fā)生故障時的性能及在全新拓撲上的性能。本文使用GEANT2 網(wǎng)絡［20］、Germany網(wǎng)絡［21］、GBN網(wǎng)絡［22］以 及synth50 網(wǎng)絡這4 個網(wǎng)絡拓撲結(jié)構(gòu)，其中，GEANT2 網(wǎng)絡具有24 個網(wǎng)絡節(jié)點，Germany 網(wǎng)絡具 有50 個網(wǎng)絡節(jié)點，GBN 網(wǎng)絡具有17 個網(wǎng)絡節(jié)點，synth50 網(wǎng)絡具有50 個網(wǎng)絡節(jié)點。這4 個網(wǎng)絡拓撲結(jié)構(gòu)如圖6 所示。

圖6 本文所用的網(wǎng)絡拓撲結(jié)構(gòu)Fig.6 Structure of network topology used in this paper

本文實驗根據(jù)拓撲文件中給定的信息進行參數(shù)設置，并設置了{15,20,25,30,35}這5 個單位為Mb/s的流量需求，以測試各方法在不同流量需求下的性能表現(xiàn)。

本文選擇2 種傳統(tǒng)路由算法OSPF［1］、AODV［23］，一種基于深度學習的路由算法GCN［24］，以及2 種不同的基于DRL 的智能路由算法DRSIR［15］和DQN［25］作為對比方法，以驗證MPNN-DQN 在不同流量需求以及網(wǎng)絡拓撲動態(tài)變化場景下的適應能力，通過平均時延、丟包率、網(wǎng)絡吞吐量等指標衡量算法的性能。本文提出的方法和對比方法的信息如表2所示。

表2 不同方法的信息說明 Table 2 Information explanation among different methods

表3 MPNN-DQN 主要參數(shù) Table 3 The main parameters of MPNN-DQN

為驗證MPNN-DQN 在網(wǎng)絡拓撲動態(tài)變化場景下的性能，本文設置3 種不同的實驗場景。場景1 首先在GEANT2 網(wǎng)絡拓撲上進行訓練和性能評估。場景2 是逐漸減少GEANT2 網(wǎng)絡拓撲中的邊數(shù)量，以模擬部分鏈路出現(xiàn)故障的場景，并進行性能評估。當故障鏈路過多時，本文認為該拓撲與原拓撲相關性極低，設置了場景3，即在全新的、與原拓撲不相關的拓撲上進行性能評估。本文綜合以上3 種場景，驗證MPNN-DQN 應對動態(tài)變化網(wǎng)絡拓撲結(jié)構(gòu)的性能。

3.3 訓練過程

在實驗過程中，MPNN-DQN 設置的主要參數(shù)如表 3 所示。

在模型的訓練過程中，通過收集訓練過程中的loss 信息和每個回合的累積獎勵信息來判斷模型的訓練情況。與此同時，為驗證第2.6 節(jié)提出的同回合內(nèi)樣本拼接方法是否有效，本文進行了消融實驗。通過對比訓練過程中的loss 信息和累積獎勵信息來衡量訓練效率，消融實驗的結(jié)果如圖7 所示。

從圖7 可以看出：相較于直接用“小樣本”進行訓練，本文采用第2.6 節(jié)提出同回合內(nèi)的樣本拼接方法，使訓練的收斂時間更短且收斂效果更好，有效地提升模型的訓練效率。

3.4 性能評估

為驗證MPNN-DQN 應對動態(tài)變化網(wǎng)絡拓撲的能力，本文設置3 種不同的實驗場景：在原始拓撲上的性能表現(xiàn)、在原始拓撲上部分鏈路產(chǎn)生故障時的性能表現(xiàn)以及在全新拓撲上的性能表現(xiàn)。

首先，以GEANT2作為原始拓撲，在該拓撲上進行探索、訓練，訓練至收斂后對不同方法的性能進行評估，對比結(jié)果如圖8 所示。在不同流量需求下，相較于其他方法中性能最優(yōu)的DQN 方法，MPNN-DQN 的網(wǎng)絡吞吐量最小提升了3.27%，最大提升了14.57%。

圖8 不同方法在原始拓撲GEANT2 上的性能對比Fig.8 Performance comparison among different methods on original topology GEANT2

為驗證不同方法在動態(tài)變化拓撲上的性能，本文將原始拓撲中的邊逐漸減少，模擬部分鏈路故障場景，選擇25 Mb/s這一最具代表性的流量需求進行實驗。原始拓撲部分鏈路發(fā)生故障的場景示意圖如圖9所示。

圖9 原始拓撲部分鏈路發(fā)生故障的場景示意圖Fig.9 Schematic diagram of scenario where some links in the original topology fail

不同方法在原始拓撲部分鏈路故障場景下的性能對比如圖10所示。實驗結(jié)果表明，在部分鏈路發(fā)生故障的場景下，相比對比方法，MPNN-DQN 在鏈路發(fā)生故障時的性能損失更小，對動態(tài)變化網(wǎng)絡拓撲的適應能力更強。在不同鏈路故障數(shù)量下，相比其他方法，MPNN-DQN 的網(wǎng)絡吞吐量提升7.57%～23.03%。

圖10 不同方法在原始拓撲部分鏈路故障場景下的性能對比Fig.10 Performance comparison among different methods in the scenario of link failure in the original topology section

當原始拓撲中出現(xiàn)故障的鏈路過多時，當前拓撲與原始拓撲的相關性已經(jīng)非常低，因此，本文提出在全新的、訓練時從未見過的、不相關的網(wǎng)絡拓撲上對不同方法進行性能評估。本文實驗選擇1 個比原始拓撲規(guī)模小的網(wǎng)絡拓撲結(jié)構(gòu)GBN，選擇2 個比原始拓撲規(guī)模更大的網(wǎng)絡拓撲Germany 和synth50。不同方法在這3 個拓撲上的性能對比如圖11 所示。

圖11 不同方法在全新拓撲上的性能對比Fig.11 Performance comparison among different methods on new topology

在全新的網(wǎng)絡拓撲上，所有方法相較于在原拓撲上都有一定性能損耗，但是本文提出的方法仍然具有最優(yōu)的表現(xiàn)。其中，在Germany 拓撲上，MPNNDQN 方法的平均網(wǎng)絡吞吐量比其他方法最小提升了3.71%，最大提升了19.53%。在GBN 網(wǎng)絡拓撲上，MPNN-DQN 方法的平均網(wǎng)絡吞吐量比其他方法最小提升了7.12%，最大提升了20.56%。在synth50 網(wǎng)絡拓撲上，MPNN-DQN 方法的平均網(wǎng)絡吞吐量比其他方法最小提升了6.99%，最大提升了18.33%。

綜合以上實驗結(jié)果，相較于2 種傳統(tǒng)方法（OSPF、AODV），一種基于深度學習的方法（GCN）以及2 種基于深度強化學習的智能路由算法（DRSIR和DQN），MPNN-DQN 無論是在部分鏈路發(fā)生故障，還是在全新的網(wǎng)絡拓撲上都具有較優(yōu)的性能，證明了本文提出的MPNN-DQN 方法對動態(tài)變化的網(wǎng)絡拓撲具有更好的適應能力。

4 結(jié)束語

針對現(xiàn)有基于深度強化學習的智能路由算法無法適應無線網(wǎng)絡動態(tài)變化網(wǎng)絡拓撲結(jié)構(gòu)的問題，本文提出一種結(jié)合消息傳遞神經(jīng)網(wǎng)絡和DRL 的智能路由算法MPNN-DQN，是一種基于k階鄰居信息的逐跳路由生成方法。借助MPNN 對非歐氏空間數(shù)據(jù)的學習能力，對實時網(wǎng)絡狀態(tài)進行學習。同時，針對基于路徑選擇和逐跳路由生成方式的不足，該方法利用MPNN 聚合鄰居信息，使逐跳路由生成方式具有更廣闊的感知域，使得算法既能在中大型網(wǎng)絡拓撲中有效工作，也盡可能避免路由空洞、局部最優(yōu)等情況。實驗結(jié)果表明，與GCN、DRSIR、DQN 等算法相比，本文算法具有較優(yōu)的平均時延、丟包率和網(wǎng)絡吞吐量指標。后續(xù)將繼續(xù)研究本文所提算法在異構(gòu)網(wǎng)絡場景中的應用，使得該算法能夠適應于更多的應用場景。