基于圖卷積神經(jīng)網(wǎng)絡(luò)的智能路由算法

唐 鑫，徐彥彥，潘少明

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

0 概述

隨著互聯(lián)網(wǎng)高速發(fā)展，網(wǎng)絡(luò)用戶迅速增加，各種新興應(yīng)用不斷涌現(xiàn)，這給通信網(wǎng)絡(luò)帶來(lái)了巨大挑戰(zhàn)，傳統(tǒng)的路由算法已經(jīng)難以滿足用戶高度差異化的服務(wù)質(zhì)量需求。傳統(tǒng)的路由協(xié)議如最短路徑優(yōu)先協(xié)議OSPF，考慮拓?fù)浣Y(jié)構(gòu)計(jì)算出最短路徑，而非網(wǎng)絡(luò)實(shí)時(shí)狀態(tài)，可能會(huì)造成某些鏈路承擔(dān)過(guò)度的網(wǎng)絡(luò)負(fù)載而降低網(wǎng)絡(luò)性能，造成網(wǎng)絡(luò)擁塞和空余資源浪費(fèi)。在真實(shí)的網(wǎng)絡(luò)環(huán)境中，鏈路狀態(tài)會(huì)隨時(shí)間變化而變化，而目前傳統(tǒng)路由算法難以感知用戶多樣化的服務(wù)質(zhì)量需求并根據(jù)當(dāng)前鏈路狀態(tài)對(duì)路由策略進(jìn)行調(diào)整。為解決此類問(wèn)題，很多基于數(shù)學(xué)模型優(yōu)化的路由協(xié)議設(shè)計(jì)方案被提出［1-2］，這類方法通常會(huì)針對(duì)應(yīng)用場(chǎng)景進(jìn)行假設(shè)來(lái)簡(jiǎn)化問(wèn)題，并使用現(xiàn)有數(shù)學(xué)方法建模求解，但真實(shí)應(yīng)用場(chǎng)景往往難以完全符合這些理想化假設(shè)。

近年來(lái)，基于深度學(xué)習(xí)（Deep Learning，DL）的人工智能技術(shù)飛速發(fā)展，廣泛應(yīng)用于圖像識(shí)別［3］和語(yǔ)言處理［2］等領(lǐng)域。網(wǎng)絡(luò)設(shè)備的計(jì)算能力和容量的提升，使得DL 模型用于解決路由優(yōu)化問(wèn)題成為可能。相比采用模型驅(qū)動(dòng)的傳統(tǒng)路由算法，基于深度學(xué)習(xí)的智能路由算法采用數(shù)據(jù)驅(qū)動(dòng)來(lái)代替原本的數(shù)學(xué)模型進(jìn)行求解，將網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)特征作為輸入，路由決策或鏈路狀態(tài)作為輸出［4］。這類方法能夠利用真實(shí)數(shù)據(jù)對(duì)算法模型進(jìn)行訓(xùn)練，而不需要對(duì)網(wǎng)絡(luò)環(huán)境進(jìn)行建模。根據(jù)輸入數(shù)據(jù)和訓(xùn)練好的深度學(xué)習(xí)模型能夠快速準(zhǔn)確地計(jì)算出路由決策結(jié)果，路由收斂速度更快。同一算法模型在不同的訓(xùn)練數(shù)據(jù)和標(biāo)簽中可以解決不同網(wǎng)絡(luò)優(yōu)化需求問(wèn)題，因此具有準(zhǔn)確性、高效性和通用性等優(yōu)勢(shì)，代表了路由決策未來(lái)的發(fā)展方向。

文獻(xiàn)［5］提出一種基于深度置信網(wǎng)絡(luò)的路由決策方案，將路由器分為邊緣和域內(nèi)路由器，根據(jù)部分網(wǎng)絡(luò)狀態(tài)特征進(jìn)行路由決策。文獻(xiàn)［6］提出一種基于塊的深度學(xué)習(xí)智能路由策略，利用遞歸分區(qū)方法將網(wǎng)絡(luò)分為多個(gè)子塊實(shí)現(xiàn)網(wǎng)絡(luò)流量控制。文獻(xiàn)［7］提出一種基于張量使用深度信念網(wǎng)絡(luò)結(jié)構(gòu)的智能分組路由策略，考慮網(wǎng)絡(luò)流量的多個(gè)參數(shù)建立相關(guān)N維張量求解路徑。文獻(xiàn)［8］利用深度強(qiáng)化學(xué)習(xí)技術(shù)和集中控制結(jié)構(gòu)來(lái)平衡流量，為可移動(dòng)和部署的骨干網(wǎng)絡(luò)節(jié)點(diǎn)單元設(shè)計(jì)一種自適應(yīng)路由方法。文獻(xiàn)［9］提出一種在無(wú)線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)基于深度強(qiáng)化學(xué)習(xí)低能耗的流量控制方法。文獻(xiàn)［10］通過(guò)卷積神經(jīng)網(wǎng)絡(luò)（Convolutional Neural Network，CNN）得到鏈路實(shí)時(shí)阻塞集合，經(jīng)重新篩選和匹配后得到新的路徑。文獻(xiàn)［11］采用深度強(qiáng)化學(xué)習(xí)方法為每項(xiàng)數(shù)據(jù)傳輸任務(wù)選擇路徑，在避免擁塞的前提下盡可能縮短數(shù)據(jù)傳輸路徑長(zhǎng)度。文獻(xiàn)［12］提出一種利用深度卷積神經(jīng)網(wǎng)絡(luò)來(lái)判斷當(dāng)前所選擇的路由路徑是否阻塞的方法，如果阻塞則重新計(jì)算路徑。現(xiàn)有研究表明，相比于傳統(tǒng)路由算法，基于深度學(xué)習(xí)的智能路由算法能夠快速準(zhǔn)確地計(jì)算出決策結(jié)果，路由收斂速度更快。但以上算法均以網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)狀態(tài)信息作為輸入，以路由決策作為輸出，而當(dāng)網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)，需要重新調(diào)整訓(xùn)練標(biāo)簽才能繼續(xù)監(jiān)督深度學(xué)習(xí)模型是否輸出恰當(dāng)?shù)穆窂剑瑹o(wú)法保證輸出路徑的正確性。同時(shí)，上述算法采用的均為傳統(tǒng)深度學(xué)習(xí)模型，不具備擴(kuò)展性，當(dāng)輸入的網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)，需要重新調(diào)整輸入來(lái)訓(xùn)練模型，這會(huì)造成較大的處理時(shí)延，且無(wú)法及時(shí)更新路由路徑。

圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Network，GNN），是一種能夠有效處理不規(guī)則拓?fù)湫畔⒌纳窠?jīng)網(wǎng)絡(luò)結(jié)構(gòu)，其可將網(wǎng)絡(luò)的節(jié)點(diǎn)特征向量根據(jù)拓?fù)潢P(guān)系變化進(jìn)行更新，最終收斂到確定值。文獻(xiàn)［13］采用GNN 模型，增加路由器接口作為額外節(jié)點(diǎn)來(lái)標(biāo)識(shí)鏈路的特征，根據(jù)網(wǎng)絡(luò)拓?fù)渥兓P(guān)系來(lái)更新網(wǎng)絡(luò)節(jié)點(diǎn)和鏈路的特征，但其主要對(duì)網(wǎng)絡(luò)結(jié)構(gòu)信息進(jìn)行建模，沒(méi)有考慮節(jié)點(diǎn)的多種特征參數(shù)，難以適用于復(fù)雜網(wǎng)絡(luò)。此后提出的圖卷積神經(jīng)網(wǎng)絡(luò)（Graph CNN，GCN），在GNN 的基礎(chǔ)上增加了圖卷積算子，能夠自動(dòng)提取圖中隱含且復(fù)雜的信息模式，對(duì)網(wǎng)絡(luò)結(jié)構(gòu)和特征具有更好的表征能力［14］。因此，面對(duì)復(fù)雜的節(jié)點(diǎn)特征，通常采用GCN 模型，其特征提取性能較好，能夠獲得良好聚類效果。此外，相較于GNN而言，GCN 具有局部特性，考慮圖中的各節(jié)點(diǎn)為中心對(duì)鄰居進(jìn)行處理，應(yīng)用在路由算法中時(shí)能夠滿足路由問(wèn)題中應(yīng)考慮到下一跳路由開(kāi)銷的需求。

針對(duì)現(xiàn)有智能路由方案在網(wǎng)絡(luò)拓?fù)鋭?dòng)態(tài)變化時(shí)需要重新訓(xùn)練，造成路由更新不及時(shí)的問(wèn)題，本文提出一種基于圖卷積神經(jīng)網(wǎng)絡(luò)（GCN）的自適應(yīng)智能路由算法。利用GCN 模型的可擴(kuò)展性輸入動(dòng)態(tài)變化的網(wǎng)絡(luò)拓?fù)洌谶M(jìn)行多屬性特征提取后輸出單跳路由開(kāi)銷，最終迭代出全局最小開(kāi)銷的路由路徑，實(shí)現(xiàn)路由策略隨網(wǎng)絡(luò)動(dòng)態(tài)變化而自適應(yīng)更新。此外，算法采用模糊C 均值（Fuzzy C-Means，F(xiàn)CM）聚類算法對(duì)鏈路狀態(tài)進(jìn)行離散化分析獲取數(shù)據(jù)集標(biāo)簽，有監(jiān)督地訓(xùn)練GCN 模型。

1 模型框架

本文所提智能路由算法的實(shí)現(xiàn)，借鑒SDN 架構(gòu)［15］的集中控制器思想，將深度學(xué)習(xí)模型部署于集中控制器中，以解決深度學(xué)習(xí)模型對(duì)運(yùn)算能力的需求，并統(tǒng)一管理路由網(wǎng)絡(luò)。同時(shí)，線下訓(xùn)練GCN 模型以便線上使用，防止因線上數(shù)據(jù)采集不夠豐富而導(dǎo)致模型訓(xùn)練不足，得到的路由結(jié)果無(wú)法滿足用戶需求的問(wèn)題。

在線下訓(xùn)練時(shí)，采集仿真網(wǎng)絡(luò)中不同拓?fù)浣Y(jié)構(gòu)下的鏈路帶寬、傳輸時(shí)延、流量、丟包率等網(wǎng)絡(luò)參數(shù)，通過(guò)FCM 聚類算法對(duì)鏈路狀況進(jìn)行離散化處理，得到聚類結(jié)果生成訓(xùn)練數(shù)據(jù)集的標(biāo)簽，以有監(jiān)督地訓(xùn)練GCN 模型。線上路由策略的方案架構(gòu)如圖1 所示，基于GCN的智能路由生成過(guò)程包括采集信息、輸入網(wǎng)絡(luò)狀態(tài)、輸出節(jié)點(diǎn)開(kāi)銷、更新路由路徑這4 個(gè)步驟。

步驟1采集信息。集中控制器周期性獲取拓?fù)鋱D中所有節(jié)點(diǎn)的連接信息和網(wǎng)絡(luò)狀態(tài)信息，根據(jù)鏈路和節(jié)點(diǎn)的實(shí)時(shí)特征信息以及網(wǎng)絡(luò)拓?fù)潢P(guān)系的變化，更新節(jié)點(diǎn)特征向量和網(wǎng)絡(luò)鄰接矩陣。

步驟2向GCN 模型輸入網(wǎng)絡(luò)狀態(tài)。集中控制器將步驟1 得到的特征向量和鄰接矩陣輸入訓(xùn)練好的GCN 模型，以便輸出路由決策依據(jù)。

步驟3GCN 模型輸出單跳路由開(kāi)銷。控制器更新單跳路由開(kāi)銷，根據(jù)鄰接矩陣迭代出路由開(kāi)銷最小的路徑，若所得到的路徑若相較于上一時(shí)刻有所更改，則更新路徑。

步驟4更新路由路徑。網(wǎng)絡(luò)將源節(jié)點(diǎn)到目的節(jié)點(diǎn)的路由路徑更新為集中控制器指定的路徑。

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

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

本文算法目的在于解決端到端的路由路徑動(dòng)態(tài)選擇問(wèn)題，選擇源節(jié)Src到目的節(jié)點(diǎn)Dst的一條最優(yōu)路徑，以避免鏈路阻塞情況，最大化利用網(wǎng)絡(luò)資源為用戶提供更優(yōu)質(zhì)的體驗(yàn)。設(shè)定網(wǎng)絡(luò)拓?fù)浒琈個(gè)節(jié)點(diǎn)、N條邊。對(duì)于路由節(jié)點(diǎn)而言，能支持的最大流量遠(yuǎn)大于鏈路帶寬，因此，無(wú)法使用路由節(jié)點(diǎn)來(lái)代替鏈路表示。而GCN 模型只能處理節(jié)點(diǎn)的特征信息、鏈路的連接關(guān)系以及鏈路的單一權(quán)重信息，無(wú)法對(duì)路由網(wǎng)絡(luò)中鏈路的多屬性參數(shù)進(jìn)行分析［14］。為了具體描述鏈路信息，本文根據(jù)節(jié)點(diǎn)間的關(guān)系增加“虛”節(jié)點(diǎn)來(lái)表示鏈路特征，“虛”節(jié)點(diǎn)與連接關(guān)系一一對(duì)應(yīng)，如圖2 所示。

圖2 “虛”節(jié)點(diǎn)表示鏈路Fig.2 Virtual nodes represent links

對(duì)于包含M個(gè)節(jié)點(diǎn)、N條邊的網(wǎng)絡(luò)拓?fù)涠裕黾恿恕疤摗惫?jié)點(diǎn)來(lái)表示網(wǎng)絡(luò)鏈路特征，則節(jié)點(diǎn)數(shù)為M+N，鏈路數(shù)為2N。路由策略問(wèn)題關(guān)注源節(jié)Src、目的節(jié)點(diǎn)Dst、轉(zhuǎn)發(fā)節(jié)點(diǎn)和網(wǎng)絡(luò)鏈路（“虛”節(jié)點(diǎn)），為具體描述網(wǎng)絡(luò)拓?fù)洌霟o(wú)向圖G=來(lái)表示。其中，集合V={Ns，N*s}表示網(wǎng)絡(luò)節(jié)點(diǎn)，集合E={e1，e2，…，e2N}表示插入“虛”節(jié)點(diǎn)后的鏈路。集合V中Ns={ν1，ν2，…，νM}表示路由節(jié)點(diǎn)，集合N*s={νM+1，νM+2，…，νM+N}表示“虛”節(jié)點(diǎn)。

用2N階方陣A=(aij)來(lái)表示節(jié)點(diǎn)之間的連接關(guān)系，如式（1）所示，其中，i，j=1，2，…，2N。

用對(duì)角矩陣D來(lái)表示節(jié)點(diǎn)的度，如式（2）所示，其中，d(νi)表示與該節(jié)點(diǎn)相連接的鏈路數(shù)量，i=1，2，…，M+N。

對(duì)于每個(gè)節(jié)點(diǎn)（包括“虛”節(jié)點(diǎn)），定義特征向量xi(i=1，2，…，M+N)來(lái)表示節(jié)點(diǎn)νi的特征，如式（3）所示，其中，Bwi為鏈路帶寬，Thi為流量，Dri為丟包率，Dei為傳輸時(shí)延。

則網(wǎng)絡(luò)拓?fù)鋱D的特征矩陣X為：

定義R={Src，Dst，B(ν)}表示路由路徑，其中，Src為源節(jié)點(diǎn)，Dst為目的節(jié)點(diǎn)，B(ν)為轉(zhuǎn)發(fā)節(jié)點(diǎn)的集合。定義表示轉(zhuǎn)發(fā)節(jié)點(diǎn)νi到鄰居節(jié)點(diǎn)的開(kāi)銷B(νi，Ccost)={(νi，Ccostij)，…，(νi，Ccostik)}，其 中，Ccostij表示節(jié) 點(diǎn)νi到節(jié)點(diǎn)νj的路由開(kāi)銷。路由R的迭代示例過(guò)程如圖3所示，其中，ν1作為源節(jié)點(diǎn)Src，ν5作為目的節(jié)點(diǎn)Dst。

圖3 全局最小開(kāi)銷路徑的迭代過(guò)程Fig.3 Iteration process of global minimum cost path

假設(shè)ν1-ν2-ν5路徑的路由開(kāi)銷最小，則從ν1出發(fā)，不斷迭代出到目的節(jié)點(diǎn)的下一跳開(kāi)銷，最終得到開(kāi)銷最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合B(ν)={B(ν1，Ccost)，B(ν2，Ccost)}，則路由路徑R={ν1，ν5，B(ν)}。路由路徑由集中控制器根據(jù)鄰居矩陣統(tǒng)一迭代，避免了路由器節(jié)點(diǎn)逐一迭代出現(xiàn)回環(huán)。

2.2 模型標(biāo)簽

目前已有的網(wǎng)絡(luò)數(shù)據(jù)集沒(méi)有合適的鏈路狀態(tài)標(biāo)簽數(shù)據(jù)，難以訓(xùn)練GCN 模型。對(duì)于鏈路狀態(tài)而言，數(shù)據(jù)集中的對(duì)象不能生硬地劃分成明顯分離的簇，被直接歸類到某一個(gè)特定狀態(tài)。為對(duì)鏈路狀態(tài)離散化分析，生成網(wǎng)絡(luò)數(shù)據(jù)集的鏈路標(biāo)簽，以便有監(jiān)督地訓(xùn)練GCN 模型，本文引入FCM 算法［16］。模糊理論的概念應(yīng)用于神經(jīng)網(wǎng)絡(luò)的計(jì)算和學(xué)習(xí)，可通過(guò)模糊技術(shù)提高神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)性能。而FCM 算法融合了模糊理論，實(shí)現(xiàn)了一種非概率特性的聚類。

設(shè)已有的鏈路狀態(tài)為n個(gè)向量xi，將這些數(shù)據(jù)劃分成c類，即將鏈路狀態(tài)定量分析為c個(gè)模糊組。為使得FCM 算法的目標(biāo)函數(shù)達(dá)到最小，需要求出每組的聚類中心。FCM 算法的第i個(gè)聚類中心為：

其中，uij為第j個(gè)數(shù)據(jù)點(diǎn)的隸屬度，用來(lái)確定每個(gè)給定數(shù)據(jù)點(diǎn)屬于各個(gè)模糊組的程度，m∈[1，∞) 是加權(quán)指數(shù)。FCM 算法分析參數(shù)對(duì)網(wǎng)絡(luò)數(shù)據(jù)集的標(biāo)簽過(guò)程如圖4 所示。

圖4 路由開(kāi)銷生成過(guò)程Fig.4 Routing cost generation process

具體過(guò)程如下：

1）線下通過(guò)網(wǎng)絡(luò)仿真器采集各種網(wǎng)絡(luò)拓?fù)浜途W(wǎng)絡(luò)狀態(tài)的信息，得到集合B，從中隨機(jī)選出特征向量xi，得到n個(gè)集合{H1，H2，…，Hn}。隨機(jī)初始化隸屬度uij后，通過(guò)FCM 算法分別對(duì)集合{H1，H2，…，Hn}進(jìn)行參數(shù)迭代，獲得聚類中心集合{ci，1，ci，2，…，ci，n}，則鏈路狀況被分為c類，分別對(duì)應(yīng)為{Ki，1，Ki，2，…，Ki，n}。

2）從集合B中隨機(jī)抽取出部分向量xi得到集合H′，利用聚類中心集合{ci，1，ci，2，…，ci，n}將H′中的鏈路信息分別歸類到{Ki，1，Ki，2，…，Ki，n}中，人工篩選出符合鏈路狀態(tài)劃分等級(jí)的鏈路狀態(tài)Ki和聚類中心ci。至此得到的聚類中心ci取決于n個(gè)數(shù)據(jù)集合而非完全手工劃分，能夠合理地離散化分析鏈路的特征。此外，將H′中各分類數(shù)據(jù)的時(shí)延、丟包率、流量和帶寬取平均值計(jì)算，再根據(jù)平均值對(duì)鏈路狀況進(jìn)行排序，鏈路狀況越好，路由開(kāi)銷越低。將得到的c類鏈路狀態(tài)Ki(i=1，2，…，c)從無(wú)負(fù)載到阻塞的排序結(jié)果與路由開(kāi)銷Ccosti(i=1，2，…，c)從低到高一一對(duì)應(yīng)。

3）根據(jù)聚類中心ci(i=1，2，…，c)將數(shù)據(jù)集合B中的所有數(shù)據(jù)標(biāo)記到路由開(kāi)銷Ccosti(i=1，2，…，c)中，以便監(jiān)督訓(xùn)練GCN 模型。

2.3 GCN 模型

GCN 網(wǎng)絡(luò)在隱藏層中對(duì)節(jié)點(diǎn)特征X進(jìn)行特征變換，則其第l+1層的特征為：

其中：X(l)為第l層節(jié)點(diǎn)的特征；σ為激活函數(shù)；W(l)為第l層的權(quán)重矩陣；b(l)為第l層的截距。通過(guò)度矩陣D對(duì)鄰居節(jié)點(diǎn)進(jìn)行歸一化處理：

圖卷積算子［14］為：

其中：Vi為節(jié)點(diǎn)νi的所有鄰居節(jié)點(diǎn)；為節(jié)點(diǎn)νi在第l+1 層的特征；為νj在第l層的特征。由式（9）可知，GCN 模型是一個(gè)一階模型，可以被用于處理圖中以某節(jié)點(diǎn)為中心的一階鄰居上的特征信息。對(duì)于路由而言，每個(gè)節(jié)點(diǎn)只關(guān)心鄰居節(jié)點(diǎn)的可達(dá)性，但當(dāng)前鏈路狀態(tài)也會(huì)被鄰居鏈路所影響，因此，采用兩層GCN 來(lái)提高模型處理能力。為緩解過(guò)擬合的問(wèn)題，增加網(wǎng)絡(luò)的稀疏性，第1 層GCN 網(wǎng)絡(luò)的激活函數(shù)選擇ReLU，第2 層GCN 網(wǎng)絡(luò)的激活函數(shù)選擇softmax，則節(jié)點(diǎn)的預(yù)測(cè)結(jié)果Z為：

綜上，兩層GCN 模型的感受域?yàn)槎A鄰居節(jié)點(diǎn)。以圖5 示例，GCN 模型通過(guò)聚合感受目標(biāo)節(jié)點(diǎn)νi的二階鄰居節(jié)點(diǎn)特征，得到目標(biāo)節(jié)點(diǎn)νi的對(duì)應(yīng)的路由開(kāi)銷zi(zi∈Z)。

圖5 兩層GCN 模型感知二階鄰居示意圖Fig.5 Schematic diagram of the process that two-layer GCN model perceives second-order neighbors

評(píng)估模型的損失函數(shù)采用交叉熵函數(shù)，如式（11）所示，其中，p(j)代表真實(shí)值；q(j)代表GCN 模型輸出值，c為標(biāo)簽總類別，j=1，2，…，c。

GCN 模型無(wú)法一步到位直接逼近鏈路的路由開(kāi)銷最優(yōu)值，如圖6 所示，其需要將預(yù)測(cè)推理得到的路由開(kāi)銷與網(wǎng)絡(luò)拓?fù)鋽?shù)據(jù)中真實(shí)路由標(biāo)簽值一一對(duì)應(yīng)，利用損失函數(shù)式（11）計(jì)算損失值，更新模型中的權(quán)重參數(shù)。在訓(xùn)練過(guò)程中，重復(fù)上述過(guò)程不斷迭代直到損失值不發(fā)生變化使得模型達(dá)到收斂，從而GCN 模型輸出能夠逼近真實(shí)的路由開(kāi)銷。

圖6 GCN 模型訓(xùn)練迭代過(guò)程Fig.6 GCN model training iteration process

2.4 路由策略

線上使用時(shí)，控制器將采集到的實(shí)時(shí)網(wǎng)絡(luò)信息輸入訓(xùn)練好的GCN 模型中。控制器以周期T來(lái)采集實(shí)時(shí)網(wǎng)絡(luò)信息，獲得實(shí)時(shí)網(wǎng)絡(luò)的無(wú)向圖G=、鄰接矩陣A和節(jié)點(diǎn)特征矩陣X，其中，V、E是在原有的網(wǎng)絡(luò)拓?fù)渖显黾恿随溌穼?duì)應(yīng)的“虛”節(jié)點(diǎn)后的集合。控制器將A和X輸入已訓(xùn)練好的GCN 模型，GCN 模型輸出各節(jié)點(diǎn)和“虛”節(jié)點(diǎn)即鏈路的路由開(kāi)銷Ccosti(i=1，2，…，c)，再通過(guò)鄰接矩陣A自適應(yīng)迭代出總開(kāi)銷最小的轉(zhuǎn)發(fā)節(jié)點(diǎn)集合B(ν)，得到路由路徑R。最后，控制器將更新后的路由路徑R加載至網(wǎng)絡(luò)中，并繼續(xù)周期性地采集數(shù)據(jù)。自適應(yīng)智能路由策略的具體算法描述如算法1 所示。

算法1自適應(yīng)智能路由策略

3 算法實(shí)現(xiàn)與性能分析

本文算法實(shí)現(xiàn)采用的計(jì)算平臺(tái)為英特爾至強(qiáng)E-2124 處理器，處理內(nèi)存為16 GB，操作系統(tǒng)為Ubuntu16.04。智能路由使用的GCN 模型采用深度學(xué)習(xí)框架Pytorch 實(shí)現(xiàn)，以Python3.5 編寫(xiě)，網(wǎng)絡(luò)仿真在網(wǎng)絡(luò)模擬器NS3.30 中實(shí)現(xiàn)。集中控制器以共享內(nèi)存的方式［17］由C++實(shí)現(xiàn)，實(shí)現(xiàn)NS3.30 的仿真網(wǎng)絡(luò)拓?fù)湫畔⑴cGCN 模型輸出的鏈路狀態(tài)互聯(lián)互通，實(shí)現(xiàn)路由路徑的智能更新。在本文實(shí)驗(yàn)中，流量生成基于泊松分布模型計(jì)算生成，并假設(shè)流量傳輸不受路由器節(jié)點(diǎn)影響，只受鏈路狀況影響。設(shè)置控制器的采集周期T=1 s，路由器節(jié)點(diǎn)緩沖區(qū)為1 GB。實(shí)驗(yàn)將鏈路帶寬設(shè)置最大為20 Mb/s，鏈路時(shí)延固定為1 ms。為訓(xùn)練GCN 模型，首先從NS3.30 采集10 000 條數(shù)據(jù)，并對(duì)鏈路狀態(tài)離散化分析生成路由開(kāi)銷數(shù)據(jù)集標(biāo)簽。

首先驗(yàn)證本文算法采用“虛”節(jié)點(diǎn)表示鏈路狀態(tài)的可行性，統(tǒng)計(jì)了增加“虛”節(jié)點(diǎn)前后的運(yùn)算時(shí)間、運(yùn)算內(nèi)存和存儲(chǔ)內(nèi)存的變化差值。如圖7 所示：運(yùn)算時(shí)間、運(yùn)算內(nèi)存和存儲(chǔ)內(nèi)存均未隨著“虛”節(jié)點(diǎn)數(shù)量的增加而線性變化，這是因?yàn)榫€上加載的是已訓(xùn)練完成的GCN 模型，運(yùn)算量較小；此外，兩層GCN 模型只考慮當(dāng)前節(jié)點(diǎn)及其二階鄰居節(jié)點(diǎn)的狀態(tài)進(jìn)行運(yùn)算，增加的“虛”節(jié)點(diǎn)數(shù)不會(huì)導(dǎo)致運(yùn)算時(shí)間和內(nèi)存占用的大幅增長(zhǎng)。

圖7 計(jì)算成本與“虛”節(jié)點(diǎn)數(shù)量的關(guān)系Fig.7 The relationship between the calculation cost and the number of virtual nodes

上文2.3 節(jié)闡述了兩層GCN 模型的理論原理，下文實(shí)驗(yàn)驗(yàn)證了模型層數(shù)設(shè)置為2 的必要性。如圖8 所示，隨著GCN 模型的層數(shù)增加，模型對(duì)節(jié)點(diǎn)狀態(tài)判斷的精確度不再顯著提升，而層數(shù)越多，算法復(fù)雜度就越高［14］，算法性能反而下降。經(jīng)過(guò)多次訓(xùn)練調(diào)參，最終設(shè)置兩層GCN模型的第1層和第2層卷積核個(gè)數(shù)均為16，權(quán)重矩陣W隨機(jī)初始化。權(quán)重衰減參數(shù)［14］設(shè)置為0.000 001，使得權(quán)重衰減到更小，減少過(guò)擬合。

圖8 GCN 模型層數(shù)與精確度的關(guān)系Fig.8 Relationship between the number of layers of GCN model and accuracy

算法所采用FCM 聚類算法的加權(quán)指數(shù)m取值已有廣泛研究，m=2 能獲得一個(gè)較好的聚類結(jié)果［16］，如圖9 所示，兩層GCN 模型的精確度隨著類數(shù)c的增加不斷降低。為了保證所劃分的類數(shù)c能表征更細(xì)致的鏈路狀態(tài)，在劃分更準(zhǔn)確路由開(kāi)銷的同時(shí)具有較高的模型精確度，本文設(shè)置FCM 聚類算法的類數(shù)c=5。

圖9 FCN 聚類類數(shù)c 與精確度的關(guān)系Fig.9 Relationship between the number of classes of FCM clustering and accuracy

為驗(yàn)證本文算法的實(shí)際性能，出于一般性，選用智能路由場(chǎng)景下經(jīng)典的GEANT2 基本拓?fù)浣Y(jié)構(gòu)［18］，如圖10 所示。為進(jìn)一步驗(yàn)證該算法能夠應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)涞淖兓瑢?shí)驗(yàn)時(shí)，隨機(jī)選擇時(shí)刻在GEANT2 拓?fù)浣Y(jié)構(gòu)上添加路由器并將其連接到拓?fù)渖系娜我宦酚善魃希蛘唠S機(jī)刪除拓?fù)浣Y(jié)構(gòu)中的路由器。

圖10 GEANT2 網(wǎng)絡(luò)拓?fù)銯ig.10 GEANT2 network topology

實(shí)驗(yàn)采用的對(duì)比算法有：智能路由中典型的等價(jià)多路徑傳輸轉(zhuǎn)發(fā)算法ECMP［19］；當(dāng)前機(jī)器學(xué)習(xí)利用流量分布計(jì)算路由的經(jīng)典算法DRL-TE［20］；基于GNN 實(shí)時(shí)感知流量的動(dòng)態(tài)調(diào)整路由策略SmartRoute［21］。首先，從傳輸時(shí)延、丟包率、吞吐量等性能指標(biāo)出發(fā)對(duì)本文算法與對(duì)比算法進(jìn)行比較。在相同速率下，傳輸時(shí)延越低、鏈路丟包率越低，吞吐量越高表明所選路徑越好。然后，比較本文算法與對(duì)比算法應(yīng)對(duì)拓?fù)渥兓瘯r(shí)的泛化能力。

圖11～圖13 顯示，不同算法的平均丟包率、傳輸時(shí)延和吞吐量隨著網(wǎng)絡(luò)負(fù)載強(qiáng)度的增加均呈上升趨勢(shì)，其中，本文算法的平均丟包率、時(shí)延最低，吞吐量最高，這是因?yàn)镋CMP 的路由策略固定，DRL-TE 只依賴于神經(jīng)網(wǎng)絡(luò)對(duì)流量分布關(guān)聯(lián)性分析，SmartRoute 只對(duì)流量特征進(jìn)行提取。3 種對(duì)比算法只針對(duì)網(wǎng)絡(luò)中單一的流量因素作為判斷依據(jù)，所選擇的路徑不會(huì)根據(jù)網(wǎng)絡(luò)負(fù)載和鏈路情況進(jìn)行適配，而本文算法通過(guò)GCN 模型對(duì)鏈路多屬性參數(shù)的離散化分析，能夠?qū)崿F(xiàn)根據(jù)負(fù)載情況自適應(yīng)適配路徑，得到的全局路由開(kāi)銷更為精確，能夠得到更優(yōu)的路徑。

圖11 不同負(fù)載下平均丟包率對(duì)比Fig.11 Comparison of average packet loss rate under different loads

圖12 不同負(fù)載下傳輸時(shí)延對(duì)比Fig.12 Comparison of transmission delay under different loads

圖13 不同負(fù)載下吞吐量對(duì)比Fig.13 Comparison of throughput under different loads

圖14 顯示了隨著網(wǎng)絡(luò)拓?fù)涔?jié)點(diǎn)變化的數(shù)量增加不同算法的時(shí)延優(yōu)化結(jié)果，為正值表示時(shí)延性能相較于拓?fù)渥兓暗臅r(shí)延減少，為負(fù)值表示拓?fù)渥兓髸r(shí)延增加，因此時(shí)延優(yōu)化的結(jié)果越大越好。DRL-TE 算法采用循環(huán)神經(jīng)網(wǎng)絡(luò)計(jì)算路由策略，存在過(guò)擬合的缺點(diǎn)，訓(xùn)練完成后難以適應(yīng)與訓(xùn)練網(wǎng)絡(luò)不相同的拓?fù)洌虼藷o(wú)法完全正確選擇策略，時(shí)延優(yōu)化結(jié)果最差，而ECMP 和采用GNN 模型的SmartRoute可應(yīng)對(duì)網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)根據(jù)流量模式選擇路徑，但時(shí)延優(yōu)化結(jié)果相較于本文算法較差，時(shí)延波動(dòng)性也更大。這是因?yàn)楸疚乃惴▽?duì)拓?fù)渲墟溌穾挕⒘髁俊G包率和傳輸時(shí)延等多屬性參數(shù)分析后得到路由開(kāi)銷，再計(jì)算路由路徑，因此相較于單一的流量模式具有更強(qiáng)的泛化能力。

圖14 不同路由算法的泛化能力Fig.14 Generalization ability of different routing algorithms

4 結(jié)束語(yǔ)

針對(duì)現(xiàn)有基于深度學(xué)習(xí)的智能路由算法在網(wǎng)絡(luò)拓?fù)渥兓瘯r(shí)無(wú)法自適應(yīng)更新路由，需要重新訓(xùn)練深度學(xué)習(xí)模型的問(wèn)題，本文提出一種基于GCN 的智能路由算法。借助圖卷積神經(jīng)網(wǎng)絡(luò)的可擴(kuò)展性和多屬性網(wǎng)絡(luò)參數(shù)提取能力，根據(jù)當(dāng)前網(wǎng)絡(luò)的狀態(tài)獲得單跳路由開(kāi)銷，并自適應(yīng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的變化動(dòng)態(tài)選擇更優(yōu)的路由路徑，從而降低網(wǎng)絡(luò)擁塞，增加網(wǎng)絡(luò)吞吐量，解決智能路由更新不及時(shí)的問(wèn)題。實(shí)驗(yàn)結(jié)果表明，本文算法采用GCN 進(jìn)行網(wǎng)絡(luò)參數(shù)提取，應(yīng)對(duì)拓?fù)渥兓瘯r(shí)性能優(yōu)于ECMP、DRL-TE 和SmartRoute 算法。后續(xù)將優(yōu)化神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)結(jié)構(gòu)，使算法能夠直接從整體準(zhǔn)確分析全局路由開(kāi)銷，進(jìn)一步提升智能路由的自適應(yīng)更新效果。