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

（武漢大學(xué) 測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，武漢 430079）

0 概述

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

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

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

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

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

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

1 模型框架

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

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

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

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

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

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

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

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

2 智能路由設(shè)計(jì)

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

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

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

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

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

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

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

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

2.3 特征提取

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

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

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

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

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

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

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

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

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

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

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

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

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

2.4 路由決策

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

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

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

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

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

2.5 獎(jiǎng)勵(lì)生成

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

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

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

生成的獎(jiǎng)勵(lì)值將與狀態(tài)信息、動(dòng)作信息等一起輸入到智能體，用于模型的訓(xùn)練。

2.6 模型訓(xùn)練

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

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

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

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

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

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

3 仿真實(shí)驗(yàn)

3.1 仿真環(huán)境

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

3.2 實(shí)驗(yàn)設(shè)置

為測(cè)試MPNN-DQN 在動(dòng)態(tài)變化網(wǎng)絡(luò)拓?fù)湎碌男阅?，本文設(shè)置了3 種不同的測(cè)試場(chǎng)景，分別為在原拓?fù)渖系男阅?、在部分鏈路發(fā)生故障時(shí)的性能及在全新拓?fù)渖系男阅?。本文使用GEANT2 網(wǎng)絡(luò)［20］、Germany網(wǎng)絡(luò)［21］、GBN網(wǎng)絡(luò)［22］以 及synth50 網(wǎng)絡(luò)這4 個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，其中，GEANT2 網(wǎng)絡(luò)具有24 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，Germany 網(wǎng)絡(luò)具 有50 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，GBN 網(wǎng)絡(luò)具有17 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)，synth50 網(wǎng)絡(luò)具有50 個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)。這4 個(gè)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖6 所示。

圖6 本文所用的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)Fig.6 Structure of network topology used in this paper

本文實(shí)驗(yàn)根據(jù)拓?fù)湮募薪o定的信息進(jìn)行參數(shù)設(shè)置，并設(shè)置了{(lán)15,20,25,30,35}這5 個(gè)單位為Mb/s的流量需求，以測(cè)試各方法在不同流量需求下的性能表現(xiàn)。

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

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

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

為驗(yàn)證MPNN-DQN 在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化場(chǎng)景下的性能，本文設(shè)置3 種不同的實(shí)驗(yàn)場(chǎng)景。場(chǎng)景1 首先在GEANT2 網(wǎng)絡(luò)拓?fù)渖线M(jìn)行訓(xùn)練和性能評(píng)估。場(chǎng)景2 是逐漸減少GEANT2 網(wǎng)絡(luò)拓?fù)渲械倪厰?shù)量，以模擬部分鏈路出現(xiàn)故障的場(chǎng)景，并進(jìn)行性能評(píng)估。當(dāng)故障鏈路過多時(shí)，本文認(rèn)為該拓?fù)渑c原拓?fù)湎嚓P(guān)性極低，設(shè)置了場(chǎng)景3，即在全新的、與原拓?fù)洳幌嚓P(guān)的拓?fù)渖线M(jìn)行性能評(píng)估。本文綜合以上3 種場(chǎng)景，驗(yàn)證MPNN-DQN 應(yīng)對(duì)動(dòng)態(tài)變化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的性能。

3.3 訓(xùn)練過程

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

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

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

3.4 性能評(píng)估

為驗(yàn)證MPNN-DQN 應(yīng)對(duì)動(dòng)態(tài)變化網(wǎng)絡(luò)拓?fù)涞哪芰?，本文設(shè)置3 種不同的實(shí)驗(yàn)場(chǎng)景：在原始拓?fù)渖系男阅鼙憩F(xiàn)、在原始拓?fù)渖喜糠宙溌樊a(chǎn)生故障時(shí)的性能表現(xiàn)以及在全新拓?fù)渖系男阅鼙憩F(xiàn)。

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

圖8 不同方法在原始拓?fù)銰EANT2 上的性能對(duì)比Fig.8 Performance comparison among different methods on original topology GEANT2

為驗(yàn)證不同方法在動(dòng)態(tài)變化拓?fù)渖系男阅?，本文將原始拓?fù)渲械倪呏饾u減少，模擬部分鏈路故障場(chǎng)景，選擇25 Mb/s這一最具代表性的流量需求進(jìn)行實(shí)驗(yàn)。原始拓?fù)洳糠宙溌钒l(fā)生故障的場(chǎng)景示意圖如圖9所示。

圖9 原始拓?fù)洳糠宙溌钒l(fā)生故障的場(chǎng)景示意圖Fig.9 Schematic diagram of scenario where some links in the original topology fail

不同方法在原始拓?fù)洳糠宙溌饭收蠄?chǎng)景下的性能對(duì)比如圖10所示。實(shí)驗(yàn)結(jié)果表明，在部分鏈路發(fā)生故障的場(chǎng)景下，相比對(duì)比方法，MPNN-DQN 在鏈路發(fā)生故障時(shí)的性能損失更小，對(duì)動(dòng)態(tài)變化網(wǎng)絡(luò)拓?fù)涞倪m應(yīng)能力更強(qiáng)。在不同鏈路故障數(shù)量下，相比其他方法，MPNN-DQN 的網(wǎng)絡(luò)吞吐量提升7.57%～23.03%。

圖10 不同方法在原始拓?fù)洳糠宙溌饭收蠄?chǎng)景下的性能對(duì)比Fig.10 Performance comparison among different methods in the scenario of link failure in the original topology section

當(dāng)原始拓?fù)渲谐霈F(xiàn)故障的鏈路過多時(shí)，當(dāng)前拓?fù)渑c原始拓?fù)涞南嚓P(guān)性已經(jīng)非常低，因此，本文提出在全新的、訓(xùn)練時(shí)從未見過的、不相關(guān)的網(wǎng)絡(luò)拓?fù)渖蠈?duì)不同方法進(jìn)行性能評(píng)估。本文實(shí)驗(yàn)選擇1 個(gè)比原始拓?fù)湟?guī)模小的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)GBN，選擇2 個(gè)比原始拓?fù)湟?guī)模更大的網(wǎng)絡(luò)拓?fù)銰ermany 和synth50。不同方法在這3 個(gè)拓?fù)渖系男阅軐?duì)比如圖11 所示。

圖11 不同方法在全新拓?fù)渖系男阅軐?duì)比Fig.11 Performance comparison among different methods on new topology

在全新的網(wǎng)絡(luò)拓?fù)渖?，所有方法相較于在原拓?fù)渖隙加幸欢ㄐ阅軗p耗，但是本文提出的方法仍然具有最優(yōu)的表現(xiàn)。其中，在Germany 拓?fù)渖?，MPNNDQN 方法的平均網(wǎng)絡(luò)吞吐量比其他方法最小提升了3.71%，最大提升了19.53%。在GBN 網(wǎng)絡(luò)拓?fù)渖希琈PNN-DQN 方法的平均網(wǎng)絡(luò)吞吐量比其他方法最小提升了7.12%，最大提升了20.56%。在synth50 網(wǎng)絡(luò)拓?fù)渖希琈PNN-DQN 方法的平均網(wǎng)絡(luò)吞吐量比其他方法最小提升了6.99%，最大提升了18.33%。

綜合以上實(shí)驗(yàn)結(jié)果，相較于2 種傳統(tǒng)方法（OSPF、AODV），一種基于深度學(xué)習(xí)的方法（GCN）以及2 種基于深度強(qiáng)化學(xué)習(xí)的智能路由算法（DRSIR和DQN），MPNN-DQN 無論是在部分鏈路發(fā)生故障，還是在全新的網(wǎng)絡(luò)拓?fù)渖隙季哂休^優(yōu)的性能，證明了本文提出的MPNN-DQN 方法對(duì)動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)渚哂懈玫倪m應(yīng)能力。

4 結(jié)束語

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