基于深度強化學習的無線網絡智能路由算法

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

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

0 概述

路由是為網絡中的數據包選擇傳輸路徑的過程，是通信網的核心功能之一。合適的路由決策能夠更合理地利用網絡資源、提升網絡性能。在無線網絡中網絡拓撲結構高度動態變化，而現有的路由算法難以適應動態變化的網絡拓撲結構，無法做出最恰當的路由決策，給網絡性能的提升帶來了挑戰。

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

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

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

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

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

1 模型框架

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

圖1 智能路由方案架構Fig.1 Architecture of intelligent routing scheme

數據平面通過控制器收集拓撲信息，建立全網視圖，在控制平面部署的MPNN-DQN 算法基于此信息做出路由決策，由數據平面負責路由決策的執行。控制平面的工作過程主要包括網絡狀態感知、特征提取、路由決策、獎勵生成和模型訓練。

1）網絡狀態感知。從NS3 仿真網絡環境中獲取當前網絡拓撲結構、當前路由需求、實時網絡狀態信息以及QoS 信息，更新記錄狀態信息的狀態向量。

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

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

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

5）模型訓練。將過去的決策作為樣本，對同回合內的樣本進行拼接后存入經驗回放緩沖區，用于模型的訓練。

2 智能路由設計

2.1 網絡與流量模型

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

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

2.2 網絡狀態感知

本文模型利用網絡狀態監視器在每個監視周期內讀取數據包統計信息，從中獲取當前網絡拓撲結構、當前路由需求以及每條鏈路的特征，計算得到當前周期內的實時網絡狀態，以及反映路由決策效果的QoS 信息，將這些信息封裝成狀態向量，并作為環境提供給智能體的狀態信息。

本文模型根據網絡狀態監視器反饋的信息，得到每條鏈路的特征代表鏈路v在周期t的網絡狀態。Fbandwidth表示當前周期內該鏈路的物理帶寬，Fdelay表示鏈路的物理時延，Fpackets表示該鏈路上已路由的數據包數，fDemand表示當前周期內的流量大小。根據拓撲中每條鏈路的特征構造特征向量，并作為輸入MPNN 的信息。

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

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

2.3 特征提取

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

節點鏈路轉換示意圖如圖2 所示。

圖2 節點鏈路轉換示意圖Fig.2 Schematic diagram of node-link transformation

本文根據網絡狀態監視器反饋的信息構建網絡拓撲，并對其進行節點鏈路轉換，將拓撲中的邊進行轉換并作為MPNN 的輸入對象，使得MPNN 能夠對鏈路特征進行更好地學習。

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

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

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

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

經過k輪的消息傳遞和狀態更新過程，每個節點聚合了k階鄰居的特征信息。特征提取流程如圖4所示。

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

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

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

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

2.4 路由決策

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

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

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

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

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

2.5 獎勵生成

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

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

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

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

2.6 模型訓練

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

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

圖5 DQN 模型架構Fig.5 Architecture of DQN model

為提升神經網絡更新的穩定性，本文引入文獻［17］提出的雙Q值網絡，通過2 個結構相同但參數不同的神經網絡提升訓練的穩定性。通過2 個網絡計算得到的誤差，對網絡參數進行更新。誤差函數的定義如式（7）所示：

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

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

3 仿真實驗

3.1 仿真環境

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

3.2 實驗設置

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

圖6 本文所用的網絡拓撲結構Fig.6 Structure of network topology used in this paper

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

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

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

表3 MPNN-DQN 主要參數 Table 3 The main parameters of MPNN-DQN

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

3.3 訓練過程

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

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

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

3.4 性能評估

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

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

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

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

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

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

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

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

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

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

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

4 結束語

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