荊 霞，周子韜，王永利

（1.南京審計大學(xué) 信息工程學(xué)院，南京 211899；2.南京理工大學(xué) 計算機科學(xué)與工程學(xué)院，南京 210014）

0 概述

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，一些流行網(wǎng)站的訪問量呈現(xiàn)飛速增長的趨勢，如何提供高質(zhì)量、高效率及更安全穩(wěn)定的服務(wù)已成為運營商必須要面對的問題［1-3］。環(huán)形結(jié)構(gòu)網(wǎng)絡(luò)可以提供更好的本地網(wǎng)絡(luò)連接體驗，能夠滿足生存性和安全性的要求，因此被應(yīng)用于很多場景。目前網(wǎng)絡(luò)運營商為大用戶提供的光纖接入網(wǎng)，例如電力、電信、有線電視等，其主干網(wǎng)大多以環(huán)型網(wǎng)絡(luò)的方式提供服務(wù)。此外，令牌環(huán)網(wǎng)絡(luò)（Token-Ring Network，TRN）、光同步數(shù)字傳輸網(wǎng)（Synchronous Digital Hierarchy，SDH）［4］、局域網(wǎng)（Local Area Network，LAN）［5］和波分復(fù)用（Wavelength Division Multiplexing，WDM）［6-7］光傳送網(wǎng)均離不開環(huán)網(wǎng)結(jié)構(gòu)。

環(huán)網(wǎng)因其結(jié)構(gòu)特點存在自身缺陷，環(huán)形結(jié)構(gòu)網(wǎng)絡(luò)傳輸效率低、延遲高，當節(jié)點或鏈路發(fā)生故障時，會變得不可靠、可擴展性差。許多基于環(huán)網(wǎng)結(jié)構(gòu)的拓撲改進也因此被提出。WILLIAM 等［8］研究了4 種增強的環(huán)網(wǎng)絡(luò)，這些網(wǎng)絡(luò)以環(huán)網(wǎng)結(jié)構(gòu)為基礎(chǔ)，在僅適度增加結(jié)構(gòu)復(fù)雜性的基礎(chǔ)上，顯著提高了環(huán)作為通信媒介的效率。文獻［9］提出了節(jié)點在同心多環(huán)覆蓋網(wǎng)絡(luò)上進行邏輯互連的網(wǎng)絡(luò)模型，不僅描述了同心多環(huán)網(wǎng)絡(luò)覆蓋拓撲，也提出了節(jié)點加入和離開方案，以及路由和資源查找算法。由于基于環(huán)的網(wǎng)絡(luò)覆蓋對于組通信具有固有可靠性和單一容錯的特點，文獻［10］提出利用改進的多環(huán)網(wǎng)絡(luò)結(jié)構(gòu)來實現(xiàn)安全和可擴展的群組通信。

為解決環(huán)網(wǎng)結(jié)構(gòu)網(wǎng)絡(luò)傳輸效率低、延遲高的問題，近年來，對環(huán)網(wǎng)的研究也從結(jié)構(gòu)改進轉(zhuǎn)移到在不同場景下環(huán)網(wǎng)路由算法的改進。ABRAHAM 等［4］研究了放置在環(huán)中有d個出度n個節(jié)點的貪婪路由，將路由復(fù)雜度從降低到。文獻［11］提出基于主從結(jié)構(gòu)的弦環(huán)網(wǎng)路由算法，該算法根據(jù)區(qū)域組成多個子環(huán)，在子環(huán)中推選出處理能力強的節(jié)點為超節(jié)點并讓其彼此相連構(gòu)成主環(huán)，從而減少路由跳數(shù)，提高路由延時性能。文獻［12］將增強環(huán)網(wǎng)中的弦環(huán)網(wǎng)應(yīng)用到分布式網(wǎng)絡(luò)中，提出改進路由算法，使該網(wǎng)絡(luò)結(jié)構(gòu)能更好地適應(yīng)大規(guī)模分布式系統(tǒng)。為解決如何在網(wǎng)絡(luò)的任意節(jié)點之間有效地為消息尋路的核心問題，文獻［13］提出一種基于增強環(huán)網(wǎng)的貪心路由算法。文獻［14］通過添加虛節(jié)點和虛擬弧擴充網(wǎng)絡(luò)，將原有問題轉(zhuǎn)換為混合整數(shù)規(guī)劃問題并提出一種啟發(fā)式算法，將其作為WDM 環(huán)網(wǎng)中的路由算法，實驗結(jié)果證明該算法效果顯著。

上述文獻是對單環(huán)網(wǎng)和特定場景下路由算法的研究，對于規(guī)模大、環(huán)數(shù)多、連接方式多樣化的復(fù)雜多環(huán)網(wǎng)絡(luò)仍缺乏性能優(yōu)良的路由算法。本文在弦環(huán)網(wǎng)結(jié)構(gòu)的啟發(fā)下，提出一種面向復(fù)雜多環(huán)網(wǎng)的路由改進算法PRR。通過構(gòu)建多種增強環(huán)網(wǎng)結(jié)構(gòu)模型，探究其增強的原子操作及由增強環(huán)網(wǎng)結(jié)構(gòu)衍生的復(fù)雜多環(huán)網(wǎng)絡(luò)定義。同時，通過分析多環(huán)網(wǎng)絡(luò)拓撲的特點，將網(wǎng)絡(luò)中節(jié)點劃分為通信節(jié)點和環(huán)內(nèi)節(jié)點，并令PRR 算法只在節(jié)點數(shù)和邊數(shù)較少的單個環(huán)以及預(yù)處理后的有向圖上進行，從而避免算法過于復(fù)雜，提高算法運算速度。

1 增強環(huán)網(wǎng)結(jié)構(gòu)模型

基于環(huán)型結(jié)構(gòu)的網(wǎng)絡(luò)有許多優(yōu)點，如具有優(yōu)良的可靠性及安全性、路由控制軟件簡單易操作等［20］，但也有明顯的缺點。由于信息在環(huán)路中是串行地穿過各個節(jié)點，當環(huán)中節(jié)點過多時，勢必影響信息在節(jié)點中的傳輸速率，使網(wǎng)絡(luò)的響應(yīng)時間延長。隨著環(huán)上節(jié)點數(shù)量的增加，該問題越發(fā)明顯。目前解決方法主要有2 種：一是將原有的大環(huán)拆成多個互連在一起的小環(huán)，這些環(huán)要么處于同一級，要么互連成1 個多層次結(jié)構(gòu)的環(huán)，如此可以改善伸縮性；二是在環(huán)的內(nèi)部或外部為不直接相連接的節(jié)點之間添加“弦”或者“弧”。這些方法也是增強環(huán)網(wǎng)結(jié)構(gòu)原子操作的核心。

拓撲直徑可定義為任意2 個節(jié)點之間最短距離的最大值，而平均直徑定義為任意2 個節(jié)點之間最短距離的平均值。在網(wǎng)絡(luò)拓撲尤其是環(huán)網(wǎng)中用直徑去度量傳輸延遲。

1.1 增強環(huán)網(wǎng)結(jié)構(gòu)

針對單環(huán)網(wǎng)的缺陷，研究人員提出多種改進環(huán)網(wǎng)結(jié)構(gòu)，這些改進后的環(huán)網(wǎng)也被稱為增強環(huán)網(wǎng)［8］。其中應(yīng)用廣泛的有以下3 種：

1）弦環(huán)網(wǎng)

弦環(huán)網(wǎng)指對于給定的N(N≥6)個節(jié)點的環(huán)網(wǎng)CHRm4(N，E，h1，h2)，其中：N、E分別表示節(jié)點與邊值；h1、h2表示弦的連接值，且h1、h2必須為正整數(shù)且為偶數(shù)。對于任意的偶數(shù)節(jié)點，，節(jié)點i2k={0，2，…，N-2}會額外與節(jié)點i_(2k+h1) modN和節(jié)點i_(2k-h1) modN連接形成環(huán)中的弦鏈路。對于任意的奇數(shù)節(jié)點，節(jié)點i2k+1={1，3，…，N-1}會額外與節(jié) 點i_(2k+1+h2) modN和節(jié)點i_(2k+1-h2) modN連接形成環(huán)中其余部分的弦鏈路。對于CHRm4 中的N、h1、h2有g(shù)cd(N、h1、h2)=2。

弦環(huán)網(wǎng)通過添加非直接相連的節(jié)點與節(jié)點之間的鏈路來增強環(huán)網(wǎng)，可以將這條新的鏈路視為環(huán)的弦。弦環(huán)是最早提出的并行架構(gòu)的成本效益互連網(wǎng)絡(luò)之一，弦環(huán)網(wǎng)的優(yōu)點主要在于當環(huán)內(nèi)1 個節(jié)點出現(xiàn)故障時不會導(dǎo)致整個環(huán)網(wǎng)都癱瘓，且弦環(huán)網(wǎng)可以適當減小環(huán)形網(wǎng)絡(luò)的直徑。弦環(huán)網(wǎng)在分布式網(wǎng)絡(luò)中有著重要的應(yīng)用，圖1（a）是四度弦環(huán)網(wǎng)CHRm4(10，1，2，4)的拓撲圖。

2）邊緣互連多環(huán)網(wǎng)

環(huán)與環(huán)之間通過環(huán)的邊緣（即連續(xù)的多個節(jié)點）連接從而形成邊緣互連多環(huán)網(wǎng)。每個環(huán)均可與其他多個環(huán)通過該方式連接且可以遞歸發(fā)生，這樣的網(wǎng)絡(luò)可以形成“環(huán)樹”?！碍h(huán)樹”的深度（環(huán)的遞歸的級別數(shù)）決定了路由開銷的程度，深度值越大，路由的決策節(jié)點數(shù)量更多，路由開銷則更高。同時，當網(wǎng)絡(luò)結(jié)構(gòu)的深度越大時，路徑選擇則更加多樣化，該網(wǎng)絡(luò)對邊緣節(jié)點故障擁有更高的容忍度。邊緣互連多環(huán)網(wǎng)在一定程度上與網(wǎng)格狀網(wǎng)絡(luò)類似，邊緣互連多環(huán)網(wǎng)更加自由，每個節(jié)點的度數(shù)不必嚴格要求相同且可以是網(wǎng)格狀網(wǎng)絡(luò)的子圖。邊緣互連多環(huán)網(wǎng)如圖1（b）所示。在實踐中，邊緣互連多環(huán)網(wǎng)常應(yīng)用在SONET的通信中。

3）分層環(huán)網(wǎng)

環(huán)與環(huán)之間通過單個節(jié)點連接形成分層環(huán)網(wǎng)。與邊緣互連多環(huán)網(wǎng)類似，環(huán)的連接也可以遞歸發(fā)生。因此，分層環(huán)網(wǎng)也可形成“環(huán)樹”，其深度同樣是重要的結(jié)構(gòu)特征。

圖1（c）為分層環(huán)網(wǎng)的示意圖。邊緣互連多環(huán)網(wǎng)和分層環(huán)網(wǎng)之間的主要區(qū)別在于邊緣互連多環(huán)網(wǎng)中共享多個節(jié)點，而在分層環(huán)網(wǎng)中共享1 個節(jié)點。因此，分層環(huán)網(wǎng)也可以作為邊緣互連多環(huán)網(wǎng)的子圖。

圖1 不同類型增強環(huán)網(wǎng)結(jié)構(gòu)Fig.1 Different types of enhanced ring network structure

1.2 多環(huán)網(wǎng)絡(luò)拓撲

多環(huán)網(wǎng)絡(luò)是增強環(huán)網(wǎng)中重要的一部分。在拓撲上，多環(huán)網(wǎng)絡(luò)可以分為3 類：1）環(huán)共享節(jié)點，其中包括單節(jié)點和多節(jié)點，連續(xù)的多節(jié)點又可以稱為共享邊；2）橋連接環(huán)網(wǎng)，也分為單橋、多橋；3）多環(huán)混合連接。多環(huán)網(wǎng)絡(luò)拓撲如圖2 所示。

圖2 多環(huán)網(wǎng)絡(luò)拓撲Fig.2 Multi-ring network topology

本文所研究的復(fù)雜多環(huán)網(wǎng)絡(luò)拓撲，“復(fù)雜”主要表現(xiàn)在3 方面：1）網(wǎng)絡(luò)中環(huán)與環(huán)的連接方式復(fù)雜，可能通過節(jié)點、邊，也可能通過橋來連接；2）網(wǎng)絡(luò)拓撲規(guī)模復(fù)雜；3）需要解決大批量大規(guī)模不同業(yè)務(wù)需求。

復(fù)雜多環(huán)網(wǎng)絡(luò)拓撲的研究意義在于：

1）多環(huán)拓撲基于環(huán)，環(huán)可以通過帶寬進行擴展，因為節(jié)點的工作負載與節(jié)點總數(shù)無關(guān)，所以這種復(fù)雜網(wǎng)絡(luò)拓適用在某些真實網(wǎng)絡(luò)場景下。

2）單環(huán)的主要缺點是對大量節(jié)點的高度依賴性，一個節(jié)點的故障可能會導(dǎo)致所有業(yè)務(wù)丟失，且平均延遲與節(jié)點總數(shù)成比例。將單個環(huán)轉(zhuǎn)換成多環(huán)可以很好地改善這種情況，但這些都要基于一個良好的路由算法。在多環(huán)混合連接拓撲中，將功能強大的節(jié)點進行環(huán)與環(huán)之間的通信，吞吐量不再受功能較弱的節(jié)點限制。

3）環(huán)之間通過共享環(huán)上單個或多個節(jié)點連接可以滿足場景的實際需求，減少網(wǎng)絡(luò)的節(jié)點數(shù)。而通過“橋”連接可以減少環(huán)與環(huán)之間的“耦合度”，“多橋”可以在橋之間起到互相保護的作用，1 個橋出現(xiàn)故障，業(yè)務(wù)可以通過其他橋繼續(xù)正常傳輸。

4）不同結(jié)構(gòu)的增強環(huán)網(wǎng)可轉(zhuǎn)化成相應(yīng)的多環(huán)結(jié)構(gòu)。文獻［2］中給出了詳細的證明。因此，本文研究復(fù)雜多環(huán)網(wǎng)絡(luò)拓撲下的路由算法對其他結(jié)構(gòu)的環(huán)網(wǎng)路由算法均有借鑒作用，甚至可以應(yīng)用在環(huán)網(wǎng)中。

1.3 多環(huán)網(wǎng)絡(luò)拓撲定義

為更準確、清晰地描述本文算法，對本文所研究的多環(huán)網(wǎng)絡(luò)拓撲給出以下定義：

1）多環(huán)網(wǎng)絡(luò)。由N個節(jié)點所構(gòu)成的多環(huán)網(wǎng)絡(luò)MR(ZN，EN，RD，BC)，節(jié)點集ZN={0，1，…，N-1}，邊集EN={{(i，i+1modN)|i∈ZN}∪BC}。RD={R1，R2，…，Rd}表示MR中包含的d個環(huán)，BC表示網(wǎng)絡(luò)中的橋，以邊的形式存儲，表現(xiàn)為

2）環(huán)連接。環(huán)Ri(ZV，EV，CR) 由節(jié)點集ZV、邊集EV和與這個環(huán)通過共享節(jié)點連接的環(huán)CR。對于含有j個節(jié)點的環(huán)，環(huán)上的邊為，每一組數(shù)據(jù)表示與該環(huán)Vi連接的環(huán)信息，m、n分別表示與之相連的環(huán)為Rm、Rn，共享的節(jié)點為。

3）通信節(jié)點。環(huán)與環(huán)之間的共享節(jié)點以及橋上的節(jié)點稱為通信節(jié)點。環(huán)內(nèi)的其他節(jié)點，及不參與到與其他環(huán)交互和通信的節(jié)點，統(tǒng)稱為非通信節(jié)點或環(huán)內(nèi)節(jié)點。

增強環(huán)網(wǎng)的提出，使環(huán)網(wǎng)結(jié)構(gòu)的網(wǎng)絡(luò)更加靈活，擁有更好的伸縮性，在響應(yīng)時間和網(wǎng)絡(luò)延遲上也有一定程度的改善。然而，環(huán)網(wǎng)結(jié)構(gòu)本身的傳輸效率低的缺點仍有待解決，如何針對不同結(jié)構(gòu)的環(huán)網(wǎng)提出相應(yīng)的路由算法，從而提升傳輸效率仍是一個重要的課題，也是本文的研究主題。

2 PRR 路由改進算法

環(huán)網(wǎng)拓撲在搜尋節(jié)點過程中每次都必須從當前節(jié)點沿著順時針或逆時針遍歷環(huán)上的其余節(jié)點，直到遇到通信節(jié)點才可以進入下一個環(huán)中進行遍歷。因此，搜索空間和時間往往很大，延遲和延遲抖動更高。本算法的思想核心是“分而治之”，在原有的拓撲識別通信節(jié)點基礎(chǔ)上構(gòu)建新的拓撲，并在該拓撲中執(zhí)行還原算法以保證網(wǎng)絡(luò)不失真。算法流程如圖3所示。

圖3 改進路由算法的流程Fig.3 Procedure of improved routing algorithm

2.1 預(yù)處理

環(huán)網(wǎng)中傳統(tǒng)路由算法先從當前節(jié)點搜尋到該環(huán)上的通信節(jié)點，之后從其節(jié)點搜尋到其他環(huán)，直到搜尋到包含目標節(jié)點的環(huán)，在該環(huán)上搜尋到目標節(jié)點。其過程由3 部分組成：從環(huán)上的環(huán)內(nèi)節(jié)點到通信節(jié)點，從一個環(huán)搜尋到另一個環(huán)即通信節(jié)點到通信節(jié)點，以及從一個環(huán)上的通信節(jié)點到環(huán)內(nèi)節(jié)點。在復(fù)雜多環(huán)網(wǎng)中，第2 部分的內(nèi)容占據(jù)路由主要部分。因此，本文算法將通信節(jié)點到通信節(jié)點的路徑通過預(yù)處理作為緩存，從而避免每次業(yè)務(wù)都需重新計算一次。

預(yù)處理算法的目的是除去整個網(wǎng)絡(luò)拓撲圖的冗余節(jié)點，主要操作是將環(huán)內(nèi)節(jié)點剝離，同時構(gòu)建一個新的預(yù)處理拓撲圖G′并緩存下來以便后續(xù)調(diào)用數(shù)據(jù)，步驟如下：

1）遍歷所有環(huán)的節(jié)點度數(shù)，如果節(jié)點的度數(shù)大于2，那么可以認定其為非環(huán)內(nèi)節(jié)點（通信節(jié)點）。將每個環(huán)的通信節(jié)點加入到通信節(jié)點集（CNi→CN）

2）構(gòu)建新的預(yù)處理拓撲圖G′，將通信節(jié)點集中的節(jié)點加入G′，即CN→G′。

3）對于同一環(huán)內(nèi)的通信節(jié)點，兩兩節(jié)點構(gòu)成邊，利用Dijkstra 算法計算他們之間的最短距離并將邊加入到G′。算法過程如算法1 所示。

算法1Create new Preprocessing topologyG′（CPG）

“最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)”指對于G中的路由ρ由函數(shù)ρ=V×V→E*，其中E*表示圖G中所有可能的路徑集合。當對于任意的x∈V，y∈V，且ρ(x，y)是最短路徑時，則稱ρ是最短路徑的路由。如果圖中的路由是連續(xù)的，對于路由ρ(x，y)=x…u1…um…y是節(jié)點對(x，y)最短路徑的路由，那么ρ(u1，um)=u1，u2，…，um也是節(jié)點對(u1，um)的最短路徑路由。

“最短路徑代價不失真”指在線性時間內(nèi)，如果原拓撲與預(yù)處理后的拓撲得到的兩通信節(jié)點間的最短路徑分別為p1、p2，其代價分別為c1、c2，那么有c1=c2且對于任意節(jié)點ν，若ν∈p1則ν∈p2。

證明如下：設(shè)在原拓撲中路由獲得的最短路徑p1由節(jié)點集{ν1，ν2，…，νi}組成，其中存在通信節(jié)點集{ν1，νj，…，νi}，源溯節(jié)點必為通信節(jié)點。若路徑中不存在除源溯節(jié)點外其他通信節(jié)點，那么源溯節(jié)點必屬于同一個環(huán)，此時p2={ν1，νi}，根據(jù)預(yù)處理步驟可得最短路徑代價不失真理論；若路徑中存在其他通信節(jié)點，根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)可得相鄰的兩個通信節(jié)點（νj，νj+1)的路徑{νj，…，νj+1}必定也是最短路徑。而預(yù)處理的過程即將{νj，…，νj+1}簡化為{νj，νj+1}，因此c1=c2，且p2中的通信節(jié)點都存在于p1中，否則p1、p2必定有一條不為最短路徑。

2.2 源溯節(jié)點還原

新的拓撲圖G′存在的問題可能是不包含業(yè)務(wù)需求中的源溯節(jié)點s、t，通過節(jié)點還原算法（RN）將原拓撲中的這部分節(jié)點和邊信息還原到拓撲圖G′中，步驟如下：

1）判斷源溯節(jié)點s、t是否為通信節(jié)點，如果是則不需要下列步驟，否則執(zhí)行下列操作。

2）遍歷環(huán)內(nèi)節(jié)點，尋找節(jié)點s、t所在的環(huán)。如果存儲空間允許，且可在拓撲生成構(gòu)建節(jié)點時存儲節(jié)點所在環(huán)的信息，則不需要此步驟。

3）計算節(jié)點s、t到所在環(huán)的所有通信節(jié)點的距離。并對每個節(jié)點對構(gòu)建邊，并加入到新的拓撲圖G′中。算法過程如算法2 所示。

算法2Recover Nodes，tinG'（RN）

圖4 所示為預(yù)處理及源溯節(jié)點還原過程示意圖。圖4（a）為初始多環(huán)網(wǎng)絡(luò)拓撲圖，標黑節(jié)點s、t為源溯節(jié)點。圖4（b）為預(yù)處理后的拓撲圖，圖中網(wǎng)格節(jié)點為保留的通信節(jié)點，加粗黑實線是預(yù)處理后拓撲中通信節(jié)點間形成的新邊，黑色未加粗實線為源溯節(jié)點還原過程中形成的邊。

圖4 預(yù)處理及源溯節(jié)點還原過程Fig.4 Restoration process of preprocessing and source tracing nodes

2.3 路徑還原

在預(yù)處理的拓撲中執(zhí)行選路算法所獲得的路徑為只包括通信節(jié)點源溯節(jié)點的路徑，路徑還原算法RP 可以將同一環(huán)內(nèi)通信節(jié)點間的路徑還原為完整的最短路徑。該算法還會刪除RN 算法中添加的源溯節(jié)點及包含該節(jié)點的邊從而還原為最初的預(yù)處理拓撲。實現(xiàn)步驟如下：

1）在拓撲圖G′中獲得初步的路徑path，判斷path 中所有邊的端節(jié)點和末節(jié)點是否為同一個環(huán)中的節(jié)點。若不同，則不執(zhí)行操作。

2）若該邊的端節(jié)點和末節(jié)點屬于同一個環(huán)中的節(jié)點，在該環(huán)中執(zhí)行尋路算法，獲得端節(jié)點到末節(jié)點的路徑path'。

3）刪除路徑path 中該邊，在path 中從節(jié)點p到q添加path′。

4）刪除拓撲圖G′的源溯節(jié)點及包含該節(jié)點的邊。算法過程如算法3 所示。

算法3Recover Path in topology（RP）

路徑還原算法過程在大多數(shù)情況下可以避免每次都運行。路徑還原算法是為了還原同一環(huán)中通信節(jié)點的路徑，而一個環(huán)中的通信節(jié)點的最短路徑只有兩種可能，順時針或者逆時針。而通信節(jié)點的數(shù)量往往不多，因此，完全可以將路徑還原所需要的數(shù)據(jù)預(yù)先計算好并存儲下來。存儲方式以path(s，t)=(s，t，0(or1))，其中s、t表示2個通信節(jié)點，0 和1表示順時針或者逆時針獲得路徑。

“最短路徑不失真”理論指的是在線性時間內(nèi)，若網(wǎng)絡(luò)拓撲直接執(zhí)行路由算法和經(jīng)過改進算法獲得的非同一環(huán)內(nèi)的節(jié)點間的最短路徑分別為p1、p2，則p1=p2。

證明如下：對于節(jié)點對(s，t)，節(jié)點s、t不在一個環(huán)內(nèi)。若p1≠p2，設(shè)p1由節(jié)點集{s，ν1，…，νi，t}構(gòu)成，p2由節(jié)點集{s，u1，…，ui，t}構(gòu)成。由于p1≠p2，設(shè)p1與p2路徑中相異節(jié)點為{n1，n2，…，ni}，節(jié)點ni可能存在于{s，…，Ccn1}，{Ccni，Ccni+1，…，Ccni+n}或{Ccnj，…，t}路徑中，其中Ccni表示路徑中的通信節(jié)點。{s，…，Ccn1}，{Ccnj，…，t}由2.2 節(jié)可知均為最短路徑算法獲得，因此必定相同；若節(jié)點ni存在于{Ccni，…，Ccni+1}中，根據(jù)最短路徑的最優(yōu)子結(jié)構(gòu)性質(zhì)可得最短路徑中的任意一段路徑均為最短路徑，由于ni在另一條路徑中不存在，因此該路徑上必定不同時存在Ccni和Ccni+1，說明p1、p2中通信節(jié)點存在不同，與最短路徑代價不失真理論相悖，因此p1=p2。

2.4 算法復(fù)雜度分析

多環(huán)網(wǎng)絡(luò)中的路由問題很顯然也是一個NPHard 問題，因此有必要對算法進行復(fù)雜度分析。假設(shè)該多環(huán)網(wǎng)絡(luò)是雙向網(wǎng)絡(luò)，共有j個環(huán)，每個小環(huán)平均由g個節(jié)點構(gòu)成，其中每個小環(huán)上平均有m個節(jié)點為通信節(jié)點。默認每個通信節(jié)點只與一個通信節(jié)點相連接，即不存在多對多、一對多、多對一的情況。那么該網(wǎng)絡(luò)拓撲結(jié)果的總結(jié)點數(shù)為：|V|=j×g，邊數(shù)為|E|=2j×g+mj。路由過程的底層算法均采用Dijkstra 算法，并以優(yōu)先隊列的方式存儲。若不經(jīng)處理直接在原始網(wǎng)絡(luò)拓撲中執(zhí)行路由算法，算法時間復(fù)雜度如下：

PRR 算法由3 部分組成。預(yù)處理部分首先判斷所有的節(jié)點度數(shù)并標記其是否為通信節(jié)點，時間復(fù)雜度為O(j×g)；將所有的通信節(jié)點標記后，需要計算同一環(huán)內(nèi)通信節(jié)點之間的代價值。即在每一個環(huán)內(nèi)執(zhí)行一次 Dijkstra 算法，時間復(fù)雜度為O(2g×lbg)。該步可以在不同環(huán)內(nèi)并行進行，若串行執(zhí)行該步驟，則算法復(fù)雜度為O(2j×g×lbg)。此步時間復(fù)雜度共為O(2j×g×lbg)+O(j×g)。

預(yù)處理后的拓撲為由m×j個節(jié)點構(gòu)成的有向圖。RN 算法將節(jié)點s與節(jié)點t加入到改進后的網(wǎng)絡(luò)拓撲中，每執(zhí)行一次，時間復(fù)雜度為O(2g×lbg)，因此時間復(fù)雜度為O(4g×lbg)。

拓撲還原后，原有的多環(huán)混合網(wǎng)絡(luò)轉(zhuǎn)換為有向圖，執(zhí)行尋路算法。有向圖最多由m×j個通信節(jié)點和2 個源溯節(jié)點構(gòu)成。而在這其中，同一環(huán)內(nèi)形成的邊數(shù)為2m條，不同環(huán)之間形成的邊數(shù)為m×j，因此新的拓撲圖總共有2m×j+m×j=3(m×j)條邊。此步的算法時間復(fù)雜度為O(3(m+j)×lb(m×j+2))。

由此，算法時間復(fù)雜度如下：

2 個算法的時間復(fù)雜度都含有O((j×g)×lbg)部分。因此，需要比較的部分為：O((j×g)×lbj+(m×j)×lb(j×g))與O((m×j)×lb(m×j)，其底數(shù)分別為j×g，m×j，即前者為所有的節(jié)點個數(shù)，后者為所有的通信節(jié)點個數(shù)，因此改進后的算法時間復(fù)雜度更優(yōu)。當環(huán)的個數(shù)為1 時，算法的時間復(fù)雜度退化為Dijkstra 算法的時間復(fù)雜度。時間復(fù)雜度的減小無可避免地伴隨著空間復(fù)雜度的增加，算法需要額外存儲一個由m×j個節(jié)點和3(m×j)條邊組成的新拓撲圖，以及通信節(jié)點之間路徑的數(shù)據(jù)，但是通信節(jié)點在實際拓撲中往往占比很小，因此不需要龐大的存儲空間，算法具有應(yīng)用的價值。

3 實驗分析

3.1 實驗數(shù)據(jù)和實驗配置

仿真實驗的硬件環(huán)境為Intel?CoreTMi5-4570 CPU@3.20 GHz，內(nèi)存4.0 GB，操作系統(tǒng)Windows 10。在NS2 網(wǎng)絡(luò)節(jié)點仿真軟件上進行網(wǎng)絡(luò)拓撲仿真，在Intellij idea 上進行算法的實現(xiàn)和實驗對比。實驗通過設(shè)置網(wǎng)絡(luò)節(jié)點個數(shù)、環(huán)的個數(shù)、通信節(jié)點個數(shù)、節(jié)點間的平均度數(shù)（代價）、“橋”的平均度數(shù)來構(gòu)建網(wǎng)絡(luò)拓撲。通過搜索空間比、改進比以及算法執(zhí)行時間作為實驗結(jié)果參考數(shù)據(jù)。其中，搜索空間表示最短路徑節(jié)點數(shù)和算法搜索總結(jié)點數(shù)的比值，搜索空間越接近1，說明算法效果越好。改進比表示兩個算法的搜索空間的比值，改進比越大，說明算法相應(yīng)的改進效果越明顯。

3.2 實驗結(jié)果和分析

復(fù)雜多環(huán)網(wǎng)絡(luò)的路由算法測試實驗的影響參數(shù)主要有環(huán)的節(jié)點個數(shù)、環(huán)的個數(shù)、環(huán)的通信節(jié)點個數(shù)（即每個環(huán)可與其他環(huán)連接個數(shù)）。在本實驗中，網(wǎng)絡(luò)規(guī)模大?。偣?jié)點個數(shù)）、環(huán)的個數(shù)和通信節(jié)點個數(shù)均可調(diào)整。原算法與PRR 算法的底層尋路算法采用Dijkstra算法，其中PRR 算法運行時間不包括生成緩存數(shù)據(jù)（同一環(huán)內(nèi)通信節(jié)點代價及路徑）的算法運行時間，每行數(shù)據(jù)由20 組不同源溯節(jié)點數(shù)據(jù)取平均值所得。實驗主要分為3 部分，分別是同等規(guī)模下不同影響參數(shù)下的算法性能比較、不同規(guī)模下的算法性能比較以及批量業(yè)務(wù)下的算法性能比較。

1）同等規(guī)模不同影響參數(shù)下的算法性能對比結(jié)果如表1 所示。網(wǎng)絡(luò)規(guī)模的節(jié)點總個數(shù)皆為10 000，當環(huán)個數(shù)為20、50 和100 時，PRR 相比于原方法的改進比為1.26～2.62，PRR 算法具有更好的表現(xiàn)效果。

表1 不同參數(shù)下實驗結(jié)果Table 1 Experimental results under different parameters

令ρ=通信節(jié)點個數(shù)/環(huán)個數(shù)，從實驗數(shù)據(jù)對比可發(fā)現(xiàn)，在一定程度內(nèi)，隨著ρ的不斷增加，PRR 算法效果表現(xiàn)得越好。ρ也可以理解為每個環(huán)與其他環(huán)連接的個數(shù)占所有環(huán)個數(shù)比。所以，當ρ較大時，環(huán)與環(huán)之間的連接較為復(fù)雜，每個環(huán)可連接的環(huán)增加，而PRR 算法簡化了此步的搜索。但并不是ρ越大，實驗效果越好，對比表1 中實驗序號2 和3 可知，出現(xiàn)這種結(jié)果的原因是此時的ρ太小，環(huán)與環(huán)之間連通性太高，導(dǎo)致節(jié)點與節(jié)點間路徑大幅減小，效果不明顯。后續(xù)實驗發(fā)現(xiàn)當ρ<0.35 該結(jié)果成立。

當環(huán)個數(shù)不變時，通信節(jié)點個數(shù)增加，改進比雖然有較小提升，但原算法時間有明顯減小，而PRR 算法運行時間明顯增加。出現(xiàn)這種結(jié)果的主要原因是通信節(jié)點個數(shù)增加后，環(huán)與環(huán)之間連通性增強了，節(jié)點到節(jié)點間路徑更短了，因此原算法運行時間減少，而改進算法由于通信節(jié)點的增加，構(gòu)建新拓撲圖復(fù)雜度則提升。

2）不同規(guī)模下的算法性能對比結(jié)果如表2 所示。從數(shù)據(jù)中可以觀察，改進比均值為2.10，說明PRR 算法具有一定的優(yōu)越性。網(wǎng)絡(luò)中通信節(jié)點的個數(shù)設(shè)置為5，當環(huán)個數(shù)固定，隨著每個環(huán)中節(jié)點個數(shù)增加，PRR 算法的表現(xiàn)越來越優(yōu)于原算法；而當每個環(huán)中節(jié)點個數(shù)一定時，隨著環(huán)個數(shù)增加，PRR 算法的表現(xiàn)也更加優(yōu)良。因此可以得出當網(wǎng)絡(luò)規(guī)模越大時，PRR 算法的效果越好。從表2 的實驗數(shù)據(jù)1 可以看出，當網(wǎng)絡(luò)規(guī)模較小時，PRR 算法運行時間甚至比原算法執(zhí)行時間更長，主要原因是當網(wǎng)絡(luò)規(guī)模較小時，尋路所用時間占比重較小。

表2 不同規(guī)模下實驗結(jié)果Table 2 Experimental results at different scales

3）批量業(yè)務(wù)下算法性能對比結(jié)果如圖5 所示，其中，（6，DJS 算法）中6 表示通信節(jié)點個數(shù)。前2 個實驗的PRR 算法執(zhí)行時間不包括生成緩存數(shù)據(jù)的執(zhí)行時間，因為在實際情況下，一個網(wǎng)絡(luò)往往需要處理成千上百萬個業(yè)務(wù)，因此預(yù)處理的時間往往可以忽略不計。本次實驗在10 000 個節(jié)點、100 個環(huán)的網(wǎng)絡(luò)中測試不同通信節(jié)點個數(shù)下Dijkstra 算法和PRR 算法的性能表現(xiàn)。由圖5 可知當業(yè)務(wù)數(shù)不超過20 時，改進算法的效果已經(jīng)優(yōu)于傳統(tǒng)算法；當通信節(jié)點個數(shù)減少時，相交點來的更快。從圖中可以看出，Dijkstra 算法處理批量業(yè)務(wù)的執(zhí)行時間隨著業(yè)務(wù)量的增加呈線性增長，而PRR 算法隨著業(yè)務(wù)量的增長，算法執(zhí)行時間不斷增長，且速度較為平穩(wěn)與緩慢。但PRR 在業(yè)務(wù)數(shù)量較小時，耗時較長。這是因為分治劃分導(dǎo)致了額外開銷，這是PRR 的不足之處。

圖5 批量業(yè)務(wù)下算法的執(zhí)行時間Fig.5 Algorithm execution time under batch business

4 結(jié)束語

本文提出一種針對復(fù)雜多環(huán)網(wǎng)絡(luò)拓撲的路由改進算法PRR，采用分治法將一個大網(wǎng)絡(luò)拓撲路由問題劃分為多個小網(wǎng)絡(luò)拓撲路由問題。PRR 算法只在節(jié)點數(shù)和邊數(shù)較少的單個環(huán)以及預(yù)處理后的有向圖上執(zhí)行，可避免原有算法在復(fù)雜多環(huán)網(wǎng)絡(luò)中由于節(jié)點和邊數(shù)的數(shù)量較多而導(dǎo)致復(fù)雜度激增，同時PRR算法在將原有拓撲進行預(yù)處理后，通過還原算法保證尋路結(jié)果的正確性。實驗結(jié)果表明，該路由算法與Dijkstra 算法相比，在復(fù)雜多環(huán)網(wǎng)絡(luò)拓撲中具有更好的效果。下一步將通過業(yè)務(wù)摘要生成、近似計算等方法，縮短PRR 的耗時，提升其在批量業(yè)務(wù)下的性能表現(xiàn)。