基于深度神經(jīng)網(wǎng)絡(luò)的無(wú)環(huán)路由算法

高會(huì)生，唐 驍，曹旺斌

(華北電力大學(xué) 電子與通信工程系，河北 保定 071003)

0 引言

隨著云服務(wù)、物聯(lián)網(wǎng)、互聯(lián)網(wǎng)應(yīng)用等信息技術(shù)和通信產(chǎn)業(yè)的快速發(fā)展，接入到通信網(wǎng)中的通信設(shè)備越來(lái)越多，使得網(wǎng)絡(luò)負(fù)載分布不均衡的現(xiàn)象日趨明顯[1]。現(xiàn)有的傳統(tǒng)流量工程方法，如啟發(fā)式算法或D算法對(duì)流量的控制能力有限。因此，一些基于深度學(xué)習(xí)的路由算法相繼被提出，然而，現(xiàn)有的基于深度學(xué)習(xí)的路由算法在路徑選擇時(shí)有一定幾率產(chǎn)生環(huán)路現(xiàn)象，使得這些方法在實(shí)際部署時(shí)出現(xiàn)困難。所以，在改善傳統(tǒng)路由方法帶來(lái)的擁塞問(wèn)題的同時(shí)，設(shè)計(jì)一種避免產(chǎn)生路由環(huán)路的算法，將會(huì)為智能路由研究領(lǐng)域開辟新的道路。

目前在路由優(yōu)化領(lǐng)域的深度學(xué)習(xí)方法主要分為2類：深度神經(jīng)網(wǎng)絡(luò)(Deep Neural Network,DNN)和與強(qiáng)化學(xué)習(xí)相結(jié)合的深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)。

在DNN方面，文獻(xiàn)[2]提出了一種基于DNN的流量工程算法，將請(qǐng)求信息作為神經(jīng)網(wǎng)絡(luò)輸入，以業(yè)務(wù)經(jīng)過(guò)鏈路的概率作為輸出，然后用神經(jīng)網(wǎng)絡(luò)模型進(jìn)行路徑計(jì)算。文獻(xiàn)[3-5]將全局網(wǎng)絡(luò)狀態(tài)作為DNN模型的輸入，將傳統(tǒng)算法得到的最優(yōu)路徑作為模型輸出來(lái)訓(xùn)練模型。部分文獻(xiàn)利用卷積神經(jīng)網(wǎng)絡(luò)[6-7]或圖神經(jīng)網(wǎng)絡(luò)[8-9]進(jìn)行路徑計(jì)算，能明顯改善網(wǎng)絡(luò)中諸如吞吐量、傳輸效率等一系列指標(biāo)的性能。

在DRL領(lǐng)域，文獻(xiàn)[10-12]借助DRL技術(shù)，提高了網(wǎng)絡(luò)運(yùn)行的可靠性和有效性。文獻(xiàn)[13-15]提出了一種基于DRL的路由優(yōu)化選路機(jī)制，通過(guò)將深度確定性策略梯度(Deep Determinstic Policy Gradient,DDPG)與軟件定義網(wǎng)絡(luò)(Software Defined Network，SDN)技術(shù)相結(jié)合，優(yōu)化了SDN的路由選路過(guò)程。

DNN和DRL在解決路由計(jì)算的問(wèn)題上各有優(yōu)劣。其中，相比于傳統(tǒng)的最短路徑算法，基于DNN的路由算法在諸如傳輸時(shí)延、網(wǎng)絡(luò)阻塞率等性能上有明顯的提升，但隨著網(wǎng)絡(luò)規(guī)模的不斷擴(kuò)大，一旦模型出現(xiàn)錯(cuò)誤，極易出現(xiàn)路由環(huán)路、鏈路阻塞等嚴(yán)重問(wèn)題[16]。與DNN不同的是，DRL能夠自適應(yīng)動(dòng)態(tài)變化的網(wǎng)絡(luò)環(huán)境，在路由優(yōu)化問(wèn)題上有著良好的通用性與泛化性。然而，當(dāng)網(wǎng)絡(luò)規(guī)模較大時(shí)，DRL模型在訓(xùn)練的探索階段會(huì)產(chǎn)生一些不盡人意的行動(dòng)，這些行動(dòng)同樣會(huì)導(dǎo)致在路由過(guò)程中產(chǎn)生路由環(huán)路現(xiàn)象，無(wú)法繼續(xù)路由。

目前專門針對(duì)避免產(chǎn)生環(huán)路現(xiàn)象的相關(guān)文獻(xiàn)還很少。本文針對(duì)上述出現(xiàn)的路由環(huán)路問(wèn)題，提出了一種基于前饋的DNN的無(wú)環(huán)路由(Loop-free Routing,LFR)算法，并與文獻(xiàn)[5]算法進(jìn)行比較，結(jié)果表明本文的算法不會(huì)產(chǎn)生環(huán)路，且能夠改善最短路徑算法帶來(lái)的擁塞問(wèn)題，對(duì)研究方法的可部署性問(wèn)題有較大的實(shí)際意義。

1 相關(guān)技術(shù)理論

采用前饋的DNN作為后續(xù)算法優(yōu)化的基礎(chǔ)。DNN示意如圖1所示。 DNN由若干層相互連接的神經(jīng)元組成，其中第一層為輸入層，最后一層為輸出層，中間若干層都稱為隱藏層。

圖1 DNN示意Fig.1 Schematic diagram of DNN

DNN中的層與層之間是全連接的，即第k層的任一神經(jīng)元一定是與第k+1層的任意神經(jīng)元連接。任意一個(gè)輸入樣本X={x1,x2,...,xn}，都有一組輸出值{q1,q2,...,qm}與之對(duì)應(yīng)。DNN前向傳播算法的計(jì)算過(guò)程為：從輸入層開始，利用每層的權(quán)重系數(shù)ω與其相連神經(jīng)元對(duì)應(yīng)的偏置b和輸入向量X進(jìn)行一系列線性運(yùn)算和激活運(yùn)算，并且將上一層的輸出作為下一層的輸入，由前向后逐層計(jì)算，直至輸出層得到輸出結(jié)果。

使用前向傳播算法計(jì)算出DNN模型的輸出后，使用損失函數(shù)表征模型輸出和真實(shí)訓(xùn)練樣本輸出之間的誤差。

DNN的損失函數(shù)多用均方誤差(Mean-Square Error,MSE)來(lái)表示，對(duì)每個(gè)樣本，都有：

(1)

式中，qL為模型輸出；y為樣本的真實(shí)輸出；k為常數(shù)，其值設(shè)定與具體實(shí)驗(yàn)有關(guān)，一般取2。

模型輸出和真實(shí)訓(xùn)練樣本輸出之間的誤差足夠小時(shí)，認(rèn)定DNN模型訓(xùn)練結(jié)束，即對(duì)損失函數(shù)進(jìn)行優(yōu)化求極小值，當(dāng)損失函數(shù)達(dá)到極小值時(shí)對(duì)應(yīng)的一系列權(quán)重矩陣W和偏置b即為訓(xùn)練完成的DNN參數(shù)。對(duì)損失函數(shù)逐步求得極小值的數(shù)學(xué)工具稱為優(yōu)化器。優(yōu)化器的選擇將在后文進(jìn)行描述。

對(duì)于一個(gè)合格的DNN模型，應(yīng)該具備對(duì)位置數(shù)據(jù)的準(zhǔn)確預(yù)測(cè)能力。在訓(xùn)練初始階段，若DNN模型擬合的函數(shù)在訓(xùn)練數(shù)據(jù)集上擬合得好，但對(duì)于測(cè)試數(shù)據(jù)集不適用，此時(shí)稱模型過(guò)擬合。當(dāng)模型出現(xiàn)過(guò)擬合時(shí)，往往是因?yàn)橛?xùn)練數(shù)據(jù)中噪聲干擾過(guò)大、參數(shù)太多、模型復(fù)雜度過(guò)高造成的。因此，一般采取的方法有縮小模型復(fù)雜度、降低特征數(shù)量和正則化。

2 算法設(shè)計(jì)

2.1 DNN指標(biāo)設(shè)計(jì)

為了保證模型訓(xùn)練過(guò)程中不出現(xiàn)過(guò)擬合問(wèn)題，采取一種正則化方法，即早停法(Early Stopping)。該方法將訓(xùn)練數(shù)據(jù)集分為2部分：訓(xùn)練集和驗(yàn)證集，只將訓(xùn)練集用于模型訓(xùn)練，在每次前向計(jì)算與反向傳播的過(guò)程結(jié)束后，在驗(yàn)證集上得出精度結(jié)果并記錄，當(dāng)模型在驗(yàn)證集上的精度不再有明顯增長(zhǎng)甚至減小時(shí)，停止訓(xùn)練。

DNN模型的輸出以列向量表示。在模型訓(xùn)練結(jié)束后，對(duì)模型準(zhǔn)確率σ進(jìn)行統(tǒng)計(jì)：

(2)

式中，Q為DNN模型的輸出向量；H為Q中元素個(gè)數(shù)；Q0為Q對(duì)應(yīng)的測(cè)試真值。設(shè)閾值ε=0.1%，若σ≤ε，則認(rèn)為輸出滿足要求；否則,不滿足要求。

2.2 DNN算法部署方案

當(dāng)前基于深度學(xué)習(xí)的路由算法可大致分成2種部署方案：集中式路由方案和分布式路由方案。

在集中式路由方案中，所有路由器與同一個(gè)中央控制器相連，中央控制器收集匯總?cè)W(wǎng)拓?fù)浼傲髁啃畔?，然后通過(guò)一個(gè)DNN模型做出相應(yīng)路徑計(jì)算，將路由方案下發(fā)到各個(gè)路由器，路由器收到下發(fā)信息后完成業(yè)務(wù)調(diào)度。當(dāng)前大多數(shù)集中式智能路由算法都需要以SDN為基礎(chǔ)，而SDN主要應(yīng)用在一些特定的網(wǎng)絡(luò)場(chǎng)景下，如數(shù)據(jù)中心網(wǎng)絡(luò)。因此，集中式路由方案在泛用性上較差。

在分布式路由方案中，每個(gè)路由器都有一個(gè)專有的控制器與之相連，即每個(gè)路由器都要訓(xùn)練一個(gè)DNN模型，如圖2所示。這些控制器中只包含本路由器及其相鄰路由器的路由信息，通過(guò)這些信息來(lái)選擇下一跳路由端口[17]，以此完成業(yè)務(wù)配置。當(dāng)前通信網(wǎng)仍然以分布式路由為主流的路由協(xié)議，本文采用分布式路由的部署方案，旨在與現(xiàn)有網(wǎng)絡(luò)協(xié)議之間有更強(qiáng)的兼容性。

圖2 分布式路由方案示意Fig.2 Schematic diagram of distributing type route scheme

2.3 無(wú)環(huán)路由算法流程

本文提出了一種基于DNN的LFR算法，通過(guò)逐跳趨近目標(biāo)節(jié)點(diǎn)的原理進(jìn)行路由，由上文可知，網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都需要訓(xùn)練一個(gè)DNN模型。對(duì)通信網(wǎng)的網(wǎng)絡(luò)拓?fù)溥M(jìn)行建模，由G=(V,E)表示，其中，V表示通信網(wǎng)絡(luò)中的節(jié)點(diǎn)集合，E表示鏈路集合。

DNN模型的輸入為目的節(jié)點(diǎn)和鏈路權(quán)重，模型輸出為當(dāng)前節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最短路徑長(zhǎng)度。算法流程如圖3所示。

圖3 算法流程Fig.3 Algorithm flow chart

(1) 生成網(wǎng)絡(luò)拓?fù)涞泥徑泳仃嘇，生成權(quán)重向量W。其中，A為稀疏矩陣，權(quán)重為1。A的元素aij滿足如下條件：若(i,j)∈E，則aij=1；否則，aij=0。

(2) 確定源節(jié)點(diǎn)m，目的節(jié)點(diǎn)n，當(dāng)前節(jié)點(diǎn)c。

(3) 利用DNN模型生成距離向量D，D的元素dj表示網(wǎng)絡(luò)中各節(jié)點(diǎn)到目的節(jié)點(diǎn)n的最短路徑距離。

(4) 由矩陣A得到當(dāng)前節(jié)點(diǎn)c的相鄰節(jié)點(diǎn)集合NS[18]。在鄰接矩陣A的第m列找到滿足aim=1元素，所對(duì)應(yīng)的節(jié)點(diǎn)為v1,v2,…，vk，這些點(diǎn)構(gòu)成m的相鄰節(jié)點(diǎn)集合，即NS={v1,v2,…，vk}。

查詢NS中的各個(gè)節(jié)點(diǎn)，值得注意的是，先前查詢過(guò)的節(jié)點(diǎn)，在后續(xù)的NS集合中不會(huì)再出現(xiàn)。若n∈NS，則結(jié)束路徑計(jì)算，最終路由路徑為path={m,n};否則，根據(jù)鏈路的權(quán)重向量W和距離向量D，計(jì)算當(dāng)前節(jié)點(diǎn)m、相鄰節(jié)點(diǎn)b∈NS到目的節(jié)點(diǎn)n的距離，分別記為dmn和dbn。

求距離差值δmb：

δmb=(ωmb+dbn)-dmn，

(3)

式中，ωmb為當(dāng)前節(jié)點(diǎn)m到相鄰節(jié)點(diǎn)b的權(quán)重長(zhǎng)度。設(shè)定一個(gè)合適的閾值α，其取值為：

(4)

式中，N為NS中候選下一跳節(jié)點(diǎn)b的個(gè)數(shù)；η為常系數(shù)，滿足條件：

(5)

若滿足條件(ωmb+dbn)-dmn≤α，將該相鄰節(jié)點(diǎn)b保留在NS中；否則，將該節(jié)點(diǎn)從NS中刪除。若集合NS遍歷結(jié)束后，NS中存在多個(gè)候選節(jié)點(diǎn)b，則按如下原則選取下一跳節(jié)點(diǎn)：

(6)

式中，向量K中包含的是當(dāng)前節(jié)點(diǎn)m與各候選下一跳節(jié)點(diǎn)b之間鏈路上已承載的業(yè)務(wù)數(shù)量k。比較各鏈路emb上已承載的業(yè)務(wù)數(shù)量kmb，若k值都相等，則取使得δ值最小的相鄰節(jié)點(diǎn)b作為下一跳節(jié)點(diǎn)，否則選擇K中的值最小的節(jié)點(diǎn)b。

令當(dāng)前節(jié)點(diǎn)m=NextStep,目的節(jié)點(diǎn)n保持不變，從步驟(2)重復(fù)此過(guò)程，直至n∈NS，按順序輸出最終的路由路徑，并更新向量K中相應(yīng)位置的k值。

2.4 關(guān)于LFR算法的幾點(diǎn)說(shuō)明

(1) 當(dāng)前，環(huán)路現(xiàn)象是分布式智能路由算法的一項(xiàng)不可忽視的問(wèn)題，本算法首先利用距離判定，控制距離差值δ在一個(gè)較小的范圍內(nèi)，使節(jié)點(diǎn)逐跳逼近目的節(jié)點(diǎn)；其次，每次更新相鄰節(jié)點(diǎn)集合NS時(shí)，都會(huì)自動(dòng)刪除掉上一跳節(jié)點(diǎn)。通過(guò)以上2種方式，保證了LFR算法不會(huì)產(chǎn)生路由環(huán)路。

(2) 多數(shù)基于分布式的智能路由算法的神經(jīng)網(wǎng)絡(luò)模型是以下一跳端口號(hào)為輸出，一旦模型出現(xiàn)錯(cuò)誤，極有可能產(chǎn)生環(huán)路現(xiàn)象或無(wú)法獲取到下一跳端口，導(dǎo)致路徑計(jì)算錯(cuò)誤，這在實(shí)際通信網(wǎng)中應(yīng)盡量避免。LFR算法將距離值代替端口號(hào)作為DNN模型的輸出，即使模型出錯(cuò)，算法將以次優(yōu)路徑完成路由選擇。

(3) 理論上，最短路徑算法可以準(zhǔn)確高效地解決單業(yè)務(wù)的路由問(wèn)題，然而，當(dāng)業(yè)務(wù)量較大時(shí)，勢(shì)必會(huì)造成最短路徑經(jīng)過(guò)的鏈路負(fù)載過(guò)重，甚至造成鏈路擁塞。因此，考慮到實(shí)際通信網(wǎng)中負(fù)載均衡的問(wèn)題，LFR算法每次循環(huán)到步驟(4)，通過(guò)引入閾值α，使得到的經(jīng)過(guò)節(jié)點(diǎn)b的路徑與最短路徑的距離之差在允許的范圍內(nèi)時(shí)，將b視為可選節(jié)點(diǎn)，在此基礎(chǔ)上進(jìn)一步比較鏈路上承載的業(yè)務(wù)數(shù)量，以此得到的路徑稱為可選路徑。因此，本算法得出的所有路徑并不都是最短路徑，而是在保證不產(chǎn)生環(huán)路且鏈路利用較為均衡的前提下，路由的總距離盡可能短。

2.5 算法實(shí)例

本文選擇7節(jié)點(diǎn)網(wǎng)絡(luò)拓?fù)錇樗憷f(shuō)明，如圖4所示。某一時(shí)刻，網(wǎng)絡(luò)歸一化的鏈路權(quán)重已由圖中給出。該時(shí)刻網(wǎng)絡(luò)中各條鏈路上承載的業(yè)務(wù)數(shù)量如表1所示。

圖4 算例網(wǎng)絡(luò)拓?fù)銯ig.4 Network topology of the example

表1 鏈路編號(hào)及已承載業(yè)務(wù)數(shù)量

以上圖為例說(shuō)明本文算法的執(zhí)行方式。

(1) 首先根據(jù)圖4，得出鄰接矩陣：

(2) 隨機(jī)產(chǎn)生一個(gè)業(yè)務(wù)，源節(jié)點(diǎn)為m=1，目的節(jié)點(diǎn)n=7，因此當(dāng)前節(jié)點(diǎn)c=1。

(3) 利用結(jié)果訓(xùn)練的DNN模型，計(jì)算出距離向量:

D=[1.55,1.4,0.95,1.05,0.65,0.6,0]。

(4) 由矩陣A得出當(dāng)前節(jié)點(diǎn)1的相鄰節(jié)點(diǎn)集合NS={2,3}，檢測(cè)到7?NS，繼續(xù)下一步。

(5) 遍歷NS中各個(gè)節(jié)點(diǎn)，計(jì)算：

ω12+d27=ω12+D(2)=2.3,

ω13+d37=ω13+D(3)=1.55,

經(jīng)計(jì)算,α=0.75。

ω12+d27-d17=0.75≤α，符合條件，保留;

根據(jù)擬建建筑物特點(diǎn)，結(jié)合場(chǎng)地地質(zhì)條件，可采用天然地基。考慮到場(chǎng)地含一層地下車庫(kù)，建議挖除第①層表土層、河溝魚塘處的淤泥和回填土及第②層黏土層，以第③-1層含砂姜黏土作為基礎(chǔ)持力層；基礎(chǔ)形式建議采用高層筏板基礎(chǔ)，多層可采用柱下獨(dú)立基礎(chǔ)及其他符合設(shè)計(jì)要求的基礎(chǔ)形式。

ω13+d37-d17=0≤α,符合條件，保留,

經(jīng)比較，k1>k2，因此下一跳節(jié)點(diǎn)b=3。

(6) 當(dāng)前節(jié)點(diǎn)m=3,更新集合NS中的元素，NS={4,5}，檢測(cè)到7?NS，繼續(xù)下一步。

(7) 計(jì)算(ω34+d47)-d37=0.1≤α，保留;

(ω35+d57)-d37=0≤α，保留,

經(jīng)比較，k5

(8) 更新集合NS中的元素，NS={2,5,6}，檢測(cè)到7?NS，執(zhí)行下一步。

(9) 計(jì)算得α=0.093 8。

(ω45+d57)-d47=0.1>α，NS中刪除節(jié)點(diǎn)5;

(ω46+d67)-d47=0≤α，保留。因此下一跳節(jié)點(diǎn)選擇6。

(10) 當(dāng)前節(jié)點(diǎn)m=6,更新NS，NS={2，7}，檢測(cè)到7∈NS，因此，下一跳節(jié)點(diǎn)為7。

輸出路徑path={1，3，4，6，7}

向量K中k2,k5,k8,k10各增加1。

3 實(shí)驗(yàn)驗(yàn)證

3.1 實(shí)驗(yàn)環(huán)境

本文使用Matlab編寫了NLSPR算法。該仿真環(huán)境在Ubuntu16.04系統(tǒng)上運(yùn)行，硬件系統(tǒng)為IntelXEONE5-2680V4CPU,32GBDDR4內(nèi)存和一塊2080Ti顯卡。

仿真分為2部分:首先確定合適的DNN模型并評(píng)估其性能;其次，從負(fù)載均衡和算法運(yùn)行效率2個(gè)角度將本文算法與相關(guān)方法進(jìn)行比較。

3.2 模型訓(xùn)練及評(píng)估

DNN的架構(gòu)是本文算法的重要組成部分，大多數(shù)文獻(xiàn)在設(shè)計(jì)DNN的結(jié)構(gòu)時(shí)都采用基于經(jīng)驗(yàn)的方法，本文采用實(shí)證的方法設(shè)計(jì)其結(jié)構(gòu)。DNN結(jié)構(gòu)包括神經(jīng)網(wǎng)絡(luò)層數(shù)、每層神經(jīng)元個(gè)數(shù)和優(yōu)化器等。

由前文可知，輸入特征是目的節(jié)點(diǎn)和鏈路權(quán)重,標(biāo)簽為當(dāng)前節(jié)點(diǎn)到所有目的節(jié)點(diǎn)的最短路徑長(zhǎng)度，每個(gè)節(jié)點(diǎn)都要訓(xùn)練一個(gè)DNN模型，本文利用Matlab為每個(gè)DNN模型生成數(shù)據(jù)集，每個(gè)訓(xùn)練集包含160 000個(gè)訓(xùn)練樣本(總樣本數(shù)的80%)和40 000個(gè)測(cè)試樣本(總樣本數(shù)的20%)。由于DNN的權(quán)重和偏置是通過(guò)隨機(jī)種子算法初始化的，每次訓(xùn)練結(jié)果會(huì)有所不同，因此將多次仿真結(jié)果的平均值作為最終的實(shí)驗(yàn)結(jié)果。

為了確定出合適的DNN結(jié)構(gòu)，對(duì)不同的結(jié)構(gòu)進(jìn)行仿真，圖5為主要的測(cè)試數(shù)據(jù)，描述了DNN訓(xùn)練集和測(cè)試集不同的隱藏層層數(shù)與每層神經(jīng)元個(gè)數(shù)組合下的MSE性能。由圖5可知，當(dāng)每層神經(jīng)元個(gè)數(shù)固定時(shí)，MSE隨著層數(shù)的加深，呈現(xiàn)先減小后增大的趨勢(shì)，因此，隱藏層為5層時(shí)，MSE最??；當(dāng)層數(shù)固定為5層，每層神經(jīng)元個(gè)數(shù)為20或25時(shí)，MSE達(dá)到最小，考慮到隨著隱藏層的神經(jīng)元個(gè)數(shù)增加會(huì)使模型訓(xùn)練變得復(fù)雜。因此，本文選擇5層隱藏層，每層20個(gè)神經(jīng)元的組合作為最終的模型結(jié)構(gòu)。

圖5 不同DNN結(jié)構(gòu)下的MSE性能Fig.5 MSE performance under different DNN structures

為盡可能地提高DNN訓(xùn)練集的精度，本文采用4種優(yōu)化器對(duì)DNN進(jìn)行訓(xùn)練，這4種優(yōu)化器都是基于梯度下降法演變而來(lái)，分別是隨機(jī)梯度下降(StochasticGradientDescent,SGD)、標(biāo)準(zhǔn)動(dòng)量?jī)?yōu)化(Momentum)、均方根支柱(RootMeanSquareprop,RMSprop)和自適應(yīng)矩估計(jì)(AdaptiveMomentEstimation,Adam)。圖6顯示了4種優(yōu)化器在DNN中預(yù)測(cè)出的MSE，可以看出，利用Adam優(yōu)化器在本文DNN模型訓(xùn)練中的精度優(yōu)于其他3種優(yōu)化器。

圖6 不同優(yōu)化器對(duì)DNN精度的影響Fig.6 Influence of different optimizers on DNN accuracy

3.3 算法性能評(píng)估

針對(duì)各項(xiàng)性能指標(biāo)將本文的LFR算法與文獻(xiàn)[5]算法進(jìn)行負(fù)載均衡和運(yùn)行效率兩方面對(duì)比。

文獻(xiàn)[5]提出的分布式路由算法中，將全局的網(wǎng)絡(luò)權(quán)重矩陣作為DNN模型輸入，將傳統(tǒng)最短路徑算法得到的下一跳節(jié)點(diǎn)作為輸出。

本文選取某地區(qū)真實(shí)電力通信光網(wǎng)絡(luò)拓?fù)溥M(jìn)行實(shí)驗(yàn)(包含61個(gè)節(jié)點(diǎn)、91條鏈路)，拓?fù)鋱D如圖7所示。

圖7 某地區(qū)電力通信網(wǎng)拓?fù)銯ig.7 Power communication network topology in a region

首先從負(fù)載均衡的角度進(jìn)行實(shí)驗(yàn)，定義單個(gè)鏈路的資源利用率如下：

(7)

式中，M為通過(guò)該鏈路的業(yè)務(wù)數(shù)量；qi為不同種類業(yè)務(wù)占用的帶寬容量；C為該鏈路的鏈路容量。為簡(jiǎn)化實(shí)驗(yàn)，隨機(jī)生成1 000個(gè)業(yè)務(wù)請(qǐng)求，即業(yè)務(wù)請(qǐng)求的源節(jié)點(diǎn)、目的節(jié)點(diǎn)都是隨機(jī)的。設(shè)置每條鏈路的最大容量為300，每條業(yè)務(wù)所占鏈路容量相同，設(shè)為1，對(duì)文獻(xiàn)[5]算法和LFR算法進(jìn)行仿真對(duì)比實(shí)驗(yàn)。

圖8為所有業(yè)務(wù)配置完畢后，2種算法的鏈路利用率對(duì)比圖。從仿真結(jié)果可以看出，由于文獻(xiàn)[5]算法的DNN模型是基于最短路徑算法訓(xùn)練的，所以整體鏈路負(fù)載分布并不均衡，少數(shù)鏈路的資源利用率甚至達(dá)到95%以上，而大多數(shù)鏈路的資源占用率都在20%以下，即隨著業(yè)務(wù)請(qǐng)求量的增多，該算法極有可能形成鏈路擁塞。而LFR算法的多數(shù)鏈路的資源利用率在20%～50%，最大資源利用率不超過(guò)60%。因此，LFR算法能夠有效地提高資源利用率，改善最短路徑算法在負(fù)載均衡問(wèn)題上的不足。

圖8 鏈路利用率對(duì)比Fig.8 Comparison diagram of link utilization

在算法運(yùn)行效率方面，定義業(yè)務(wù)配置完成時(shí)間為：

Tcomplete=Ta+Tl+Tq，

(8)

式中，Tcomplete為業(yè)務(wù)配置完成時(shí)間；Ta為算法進(jìn)行路徑計(jì)算的時(shí)間；Tl為路由經(jīng)過(guò)的鏈路時(shí)延之和；Tq為擁塞時(shí)業(yè)務(wù)的等待時(shí)間。設(shè)置每條鏈路的最大容量同樣為300，每條業(yè)務(wù)占用容量為1，按照實(shí)際設(shè)置該電力通信網(wǎng)鏈路長(zhǎng)度，規(guī)定數(shù)據(jù)在單位長(zhǎng)度光纖內(nèi)傳播速率為0.005 25ms[19]，業(yè)務(wù)請(qǐng)求按周期為0.01ms隨機(jī)生成，通過(guò)不斷增加業(yè)務(wù)請(qǐng)求量，統(tǒng)計(jì)業(yè)務(wù)配置的完成時(shí)間。

多次配置同樣數(shù)量的業(yè)務(wù)求得的業(yè)務(wù)配置完成時(shí)間的平均值如圖9所示。

圖9 業(yè)務(wù)配置完成時(shí)間對(duì)比Fig.9 Comparison chart of business configuration completion time

當(dāng)業(yè)務(wù)請(qǐng)求量較少時(shí)，文獻(xiàn)[5]算法與LFR算法有著相似的性能，甚至文獻(xiàn)[5]算法的運(yùn)行效率更好，這主要是由于，相比本文算法，該算法沒(méi)有多余判定條件，并且在業(yè)務(wù)請(qǐng)求量少時(shí)，鏈路資源充足。然而，隨著業(yè)務(wù)量的持續(xù)增長(zhǎng)，文獻(xiàn)[5]算法開始出現(xiàn)排隊(duì)擁塞，少數(shù)業(yè)務(wù)路由時(shí)甚至?xí)a(chǎn)生環(huán)路現(xiàn)象，導(dǎo)致業(yè)務(wù)配置時(shí)間持續(xù)增長(zhǎng)。相比之下，LFR算法在傳輸時(shí)延方面表現(xiàn)相對(duì)較好，這是由于LFR算法在保證不出現(xiàn)環(huán)路現(xiàn)象的前提下，權(quán)衡了路徑與鏈路利用率關(guān)系，在一定程度上減輕了最短路徑相關(guān)算法容易產(chǎn)生鏈路負(fù)載過(guò)重的壓力。

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

本文提出了一種基于DNN的無(wú)環(huán)路由算法，通過(guò)相關(guān)節(jié)點(diǎn)控制與距離判定的方式，逐跳趨近目標(biāo)節(jié)點(diǎn)，解決了當(dāng)前智能路由算法有可能產(chǎn)生環(huán)路現(xiàn)象的問(wèn)題。通過(guò)引入鏈路業(yè)務(wù)承載量的判定條件，使鏈路利用率較為均衡。同相關(guān)智能路由算法相比，在配置相同業(yè)務(wù)數(shù)量的情況下，本文算法在負(fù)載均衡和運(yùn)行效率方面均有良好表現(xiàn)。為真實(shí)場(chǎng)景中智能路由算法的安全性和可靠性問(wèn)題提供了重要的參考價(jià)值。

未來(lái)的工作，將考慮在更大的網(wǎng)絡(luò)規(guī)模和更多約束條件的情況下進(jìn)行研究，進(jìn)一步提升算法性能。