針對(duì)復(fù)雜多環(huán)網(wǎng)絡(luò)拓?fù)涞穆酚筛倪M(jìn)算法

荊 霞，周子韜，王永利

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

0 概述

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，一些流行網(wǎng)站的訪問量呈現(xiàn)飛速增長的趨勢(shì)，如何提供高質(zhì)量、高效率及更安全穩(wěn)定的服務(wù)已成為運(yùn)營商必須要面對(duì)的問題［1-3］。環(huán)形結(jié)構(gòu)網(wǎng)絡(luò)可以提供更好的本地網(wǎng)絡(luò)連接體驗(yàn)，能夠滿足生存性和安全性的要求，因此被應(yīng)用于很多場(chǎng)景。目前網(wǎng)絡(luò)運(yùn)營商為大用戶提供的光纖接入網(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)特點(diǎn)存在自身缺陷，環(huán)形結(jié)構(gòu)網(wǎng)絡(luò)傳輸效率低、延遲高，當(dāng)節(jié)點(diǎn)或鏈路發(fā)生故障時(shí)，會(huì)變得不可靠、可擴(kuò)展性差。許多基于環(huán)網(wǎng)結(jié)構(gòu)的拓?fù)涓倪M(jìn)也因此被提出。WILLIAM 等［8］研究了4 種增強(qiáng)的環(huán)網(wǎng)絡(luò)，這些網(wǎng)絡(luò)以環(huán)網(wǎng)結(jié)構(gòu)為基礎(chǔ)，在僅適度增加結(jié)構(gòu)復(fù)雜性的基礎(chǔ)上，顯著提高了環(huán)作為通信媒介的效率。文獻(xiàn)［9］提出了節(jié)點(diǎn)在同心多環(huán)覆蓋網(wǎng)絡(luò)上進(jìn)行邏輯互連的網(wǎng)絡(luò)模型，不僅描述了同心多環(huán)網(wǎng)絡(luò)覆蓋拓?fù)?，也提出了?jié)點(diǎn)加入和離開方案，以及路由和資源查找算法。由于基于環(huán)的網(wǎng)絡(luò)覆蓋對(duì)于組通信具有固有可靠性和單一容錯(cuò)的特點(diǎn)，文獻(xiàn)［10］提出利用改進(jìn)的多環(huán)網(wǎng)絡(luò)結(jié)構(gòu)來實(shí)現(xiàn)安全和可擴(kuò)展的群組通信。

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

上述文獻(xiàn)是對(duì)單環(huán)網(wǎng)和特定場(chǎng)景下路由算法的研究，對(duì)于規(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)的路由改進(jìn)算法PRR。通過構(gòu)建多種增強(qiáng)環(huán)網(wǎng)結(jié)構(gòu)模型，探究其增強(qiáng)的原子操作及由增強(qiáng)環(huán)網(wǎng)結(jié)構(gòu)衍生的復(fù)雜多環(huán)網(wǎng)絡(luò)定義。同時(shí)，通過分析多環(huán)網(wǎng)絡(luò)拓?fù)涞奶攸c(diǎn)，將網(wǎng)絡(luò)中節(jié)點(diǎn)劃分為通信節(jié)點(diǎn)和環(huán)內(nèi)節(jié)點(diǎn)，并令PRR 算法只在節(jié)點(diǎn)數(shù)和邊數(shù)較少的單個(gè)環(huán)以及預(yù)處理后的有向圖上進(jìn)行，從而避免算法過于復(fù)雜，提高算法運(yùn)算速度。

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

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

拓?fù)渲睆娇啥x為任意2 個(gè)節(jié)點(diǎn)之間最短距離的最大值，而平均直徑定義為任意2 個(gè)節(jié)點(diǎn)之間最短距離的平均值。在網(wǎng)絡(luò)拓?fù)溆绕涫黔h(huán)網(wǎng)中用直徑去度量傳輸延遲。

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

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

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

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

弦環(huán)網(wǎng)通過添加非直接相連的節(jié)點(diǎn)與節(jié)點(diǎn)之間的鏈路來增強(qiáng)環(huán)網(wǎng)，可以將這條新的鏈路視為環(huán)的弦。弦環(huán)是最早提出的并行架構(gòu)的成本效益互連網(wǎng)絡(luò)之一，弦環(huán)網(wǎng)的優(yōu)點(diǎn)主要在于當(dāng)環(huán)內(nèi)1 個(gè)節(jié)點(diǎn)出現(xiàn)故障時(shí)不會(huì)導(dǎo)致整個(gè)環(huán)網(wǎng)都癱瘓，且弦環(huán)網(wǎng)可以適當(dā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)的拓?fù)鋱D。

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

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

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

環(huán)與環(huán)之間通過單個(gè)節(jié)點(diǎn)連接形成分層環(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)中共享多個(gè)節(jié)點(diǎn)，而在分層環(huán)網(wǎng)中共享1 個(gè)節(jié)點(diǎn)。因此，分層環(huán)網(wǎng)也可以作為邊緣互連多環(huán)網(wǎng)的子圖。

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

1.2 多環(huán)網(wǎng)絡(luò)拓?fù)?/h3>

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

圖2 多環(huán)網(wǎng)絡(luò)拓?fù)銯ig.2 Multi-ring network topology

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

復(fù)雜多環(huán)網(wǎng)絡(luò)拓?fù)涞难芯恳饬x在于：

1）多環(huán)拓?fù)浠诃h(huán)，環(huán)可以通過帶寬進(jìn)行擴(kuò)展，因?yàn)楣?jié)點(diǎn)的工作負(fù)載與節(jié)點(diǎn)總數(shù)無關(guān)，所以這種復(fù)雜網(wǎng)絡(luò)拓適用在某些真實(shí)網(wǎng)絡(luò)場(chǎng)景下。

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

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

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

1.3 多環(huán)網(wǎng)絡(luò)拓?fù)涠x

為更準(zhǔn)確、清晰地描述本文算法，對(duì)本文所研究的多環(huán)網(wǎng)絡(luò)拓?fù)浣o出以下定義：

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

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

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

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

2 PRR 路由改進(jìn)算法

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

圖3 改進(jìn)路由算法的流程Fig.3 Procedure of improved routing algorithm

2.1 預(yù)處理

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

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

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

2）構(gòu)建新的預(yù)處理拓?fù)鋱DG′，將通信節(jié)點(diǎn)集中的節(jié)點(diǎn)加入G′，即CN→G′。

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

算法1Create new Preprocessing topologyG′（CPG）

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

“最短路徑代價(jià)不失真”指在線性時(shí)間內(nèi)，如果原拓?fù)渑c預(yù)處理后的拓?fù)涞玫降膬赏ㄐ殴?jié)點(diǎn)間的最短路徑分別為p1、p2，其代價(jià)分別為c1、c2，那么有c1=c2且對(duì)于任意節(jié)點(diǎn)ν，若ν∈p1則ν∈p2。

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

2.2 源溯節(jié)點(diǎn)還原

新的拓?fù)鋱DG′存在的問題可能是不包含業(yè)務(wù)需求中的源溯節(jié)點(diǎn)s、t，通過節(jié)點(diǎn)還原算法（RN）將原拓?fù)渲械倪@部分節(jié)點(diǎn)和邊信息還原到拓?fù)鋱DG′中，步驟如下：

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

2）遍歷環(huán)內(nèi)節(jié)點(diǎn)，尋找節(jié)點(diǎn)s、t所在的環(huán)。如果存儲(chǔ)空間允許，且可在拓?fù)渖蓸?gòu)建節(jié)點(diǎn)時(shí)存儲(chǔ)節(jié)點(diǎn)所在環(huán)的信息，則不需要此步驟。

3）計(jì)算節(jié)點(diǎn)s、t到所在環(huán)的所有通信節(jié)點(diǎn)的距離。并對(duì)每個(gè)節(jié)點(diǎn)對(duì)構(gòu)建邊，并加入到新的拓?fù)鋱DG′中。算法過程如算法2 所示。

算法2Recover Nodes，tinG'（RN）

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

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

2.3 路徑還原

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

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

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

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

4）刪除拓?fù)鋱DG′的源溯節(jié)點(diǎn)及包含該節(jié)點(diǎn)的邊。算法過程如算法3 所示。

算法3Recover Path in topology（RP）

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

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

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

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

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

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

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

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

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

2 個(gè)算法的時(shí)間復(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é)點(diǎn)個(gè)數(shù)，后者為所有的通信節(jié)點(diǎn)個(gè)數(shù)，因此改進(jìn)后的算法時(shí)間復(fù)雜度更優(yōu)。當(dāng)環(huán)的個(gè)數(shù)為1 時(shí)，算法的時(shí)間復(fù)雜度退化為Dijkstra 算法的時(shí)間復(fù)雜度。時(shí)間復(fù)雜度的減小無可避免地伴隨著空間復(fù)雜度的增加，算法需要額外存儲(chǔ)一個(gè)由m×j個(gè)節(jié)點(diǎn)和3(m×j)條邊組成的新拓?fù)鋱D，以及通信節(jié)點(diǎn)之間路徑的數(shù)據(jù)，但是通信節(jié)點(diǎn)在實(shí)際拓?fù)渲型急群苄。虼瞬恍枰嫶蟮拇鎯?chǔ)空間，算法具有應(yīng)用的價(jià)值。

3 實(shí)驗(yàn)分析

3.1 實(shí)驗(yàn)數(shù)據(jù)和實(shí)驗(yàn)配置

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

3.2 實(shí)驗(yàn)結(jié)果和分析

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

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

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

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

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

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

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

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

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

4 結(jié)束語

本文提出一種針對(duì)復(fù)雜多環(huán)網(wǎng)絡(luò)拓?fù)涞穆酚筛倪M(jìn)算法PRR，采用分治法將一個(gè)大網(wǎng)絡(luò)拓?fù)渎酚蓡栴}劃分為多個(gè)小網(wǎng)絡(luò)拓?fù)渎酚蓡栴}。PRR 算法只在節(jié)點(diǎn)數(shù)和邊數(shù)較少的單個(gè)環(huán)以及預(yù)處理后的有向圖上執(zhí)行，可避免原有算法在復(fù)雜多環(huán)網(wǎng)絡(luò)中由于節(jié)點(diǎn)和邊數(shù)的數(shù)量較多而導(dǎo)致復(fù)雜度激增，同時(shí)PRR算法在將原有拓?fù)溥M(jìn)行預(yù)處理后，通過還原算法保證尋路結(jié)果的正確性。實(shí)驗(yàn)結(jié)果表明，該路由算法與Dijkstra 算法相比，在復(fù)雜多環(huán)網(wǎng)絡(luò)拓?fù)渲芯哂懈玫男ЧＯ乱徊綄⑼ㄟ^業(yè)務(wù)摘要生成、近似計(jì)算等方法，縮短PRR 的耗時(shí)，提升其在批量業(yè)務(wù)下的性能表現(xiàn)。