齊小剛，張碧雯+，劉立芳，胡紹林

1.西安電子科技大學 數(shù)學與統(tǒng)計學院，西安 710071

2.西安電子科技大學 計算機學院，西安 710071

3.航天器故障診斷與維修重點實驗室，西安 710043

4.西安理工大學 自動化與信息工程學院，西安 710048

1 引言

計算機網(wǎng)絡(luò)應用在支持各類服務(wù)上發(fā)揮著越來越關(guān)鍵的作用。事實上，這些應用已經(jīng)成為人們?nèi)粘Ｉ畹囊徊糠?。醫(yī)院、企業(yè)、學校、政府的日常運作越來越依賴于計算機網(wǎng)絡(luò)服務(wù)。這些公開可用的網(wǎng)絡(luò)服務(wù)不僅容易受到地震、颶風、海嘯等自然災害的影響，而且隨時會發(fā)生各種故障狀況以及面臨一些網(wǎng)絡(luò)攻擊，使得正常的運作和服務(wù)中斷。網(wǎng)絡(luò)彈性[1-3]指的是網(wǎng)絡(luò)在應對多種故障和挑戰(zhàn)下，提供和維持可接受水平內(nèi)的服務(wù)而正常運作的能力。因此構(gòu)建具有良好彈性的網(wǎng)絡(luò)拓撲用于應對挑戰(zhàn)并且提供可接受水平的服務(wù)，可以延長網(wǎng)絡(luò)壽命、節(jié)約網(wǎng)絡(luò)成本。

一般網(wǎng)絡(luò)，尤其是全球互聯(lián)網(wǎng)，已經(jīng)成為商業(yè)和全球經(jīng)濟的日常運作的必要內(nèi)容。因此網(wǎng)絡(luò)中斷的后果[4]也變得越來越嚴重。現(xiàn)在廣泛認為當前的許多現(xiàn)實網(wǎng)絡(luò)不具備足夠的彈性，需要相應的研究、開發(fā)和工程項目來完善基礎(chǔ)設(shè)施網(wǎng)絡(luò)和服務(wù)網(wǎng)絡(luò)[5-7]的彈性。對于彈性網(wǎng)絡(luò)結(jié)構(gòu)的研究，Kumar等人[8]從復雜網(wǎng)絡(luò)拓撲的角度提出一種DLA模型構(gòu)建彈性供應網(wǎng)絡(luò)，并且分析所提出的網(wǎng)絡(luò)構(gòu)建模型所構(gòu)造的網(wǎng)絡(luò)拓撲在應對隨機故障和惡意攻擊方面的彈性，當然網(wǎng)絡(luò)構(gòu)建過程不總是從頭開始建立，因此不能解決對于現(xiàn)有網(wǎng)絡(luò)的彈性優(yōu)化問題，同時該模型只考慮了節(jié)點最大度這一項約束，遠遠不適用于現(xiàn)實網(wǎng)絡(luò)的構(gòu)建過程。李云冀等人[9]考慮擁塞造成的網(wǎng)絡(luò)故障，對網(wǎng)絡(luò)節(jié)點和鏈路的重要性進行評估，基于網(wǎng)絡(luò)的鄰接矩陣，構(gòu)建在度約束下最小化平均距離的優(yōu)化網(wǎng)絡(luò)，提高網(wǎng)絡(luò)的可生存性。然而，相比于構(gòu)建彈性網(wǎng)絡(luò)，也有大量研究著手于網(wǎng)絡(luò)拓撲的優(yōu)化，改善現(xiàn)有網(wǎng)絡(luò)的拓撲，使其彈性應對各種挑戰(zhàn)和故障。對于真實的服務(wù)提供者骨干網(wǎng)絡(luò)拓撲，如Sprint、AT&T、GéANT2等網(wǎng)絡(luò)拓撲[10]的研究，綜合比較拓撲的結(jié)構(gòu)特性，如平均節(jié)點度、聚類系數(shù)、平均最短路徑、半徑和直徑等。相比于表征網(wǎng)絡(luò)連通性和健壯性的這些經(jīng)典的圖論指標[11]，圖譜理論度量標準是圖的健壯性指標的另一個子類，研究圖的結(jié)構(gòu)特性與相關(guān)矩陣的特征值和特征向量之間的關(guān)系。一些圖譜指標可以用于測量移除節(jié)點或者鏈路之后圖的健壯性，如代數(shù)連通度[12]、譜隙[11]、自然連通度[13]、權(quán)譜[14]、網(wǎng)絡(luò)關(guān)鍵度[15]。Alenazi和Sterbenz[11]提出中心性攻擊下的3種網(wǎng)絡(luò)彈性測度，使用經(jīng)典圖論指標和圖譜論標準，測量隨機故障和惡意攻擊下的網(wǎng)絡(luò)彈性，以基本圖和隨機圖為拓撲數(shù)據(jù)集，使用非線性相關(guān)比較各項指標預測攻擊下網(wǎng)絡(luò)彈性的準確度。

本文研究的圖健壯性指標為網(wǎng)絡(luò)的平均效率函數(shù)[16]。對網(wǎng)絡(luò)施加隨機故障和中心性攻擊，測量網(wǎng)絡(luò)的流健壯性，用該指標表示每次攻擊下可靠流的可用性。每次節(jié)點攻擊下的流健壯性作為網(wǎng)絡(luò)的彈性測度。本文提出一種迭代算法優(yōu)化網(wǎng)絡(luò)的連通性，通過對給定圖添加鏈路集來最大化網(wǎng)絡(luò)的平均效率函數(shù)，提高網(wǎng)絡(luò)彈性。將該算法用于3種復雜網(wǎng)絡(luò)拓撲并且比較算法的效益。通過采用隨機故障和基于中心性的攻擊，測試和評估原始圖和改善圖的網(wǎng)絡(luò)彈性。本文的主要工作為：提出了一種優(yōu)化算法基于網(wǎng)絡(luò)的平均效率這一健壯性指標改善給定圖；對3個復雜網(wǎng)絡(luò)使用該算法產(chǎn)生相應的改善圖；使用流健壯性函數(shù)評估隨機故障和中心性攻擊下的網(wǎng)絡(luò)彈性。

2 背景和相關(guān)工作

2.1 圖中心性度量

給定圖G=(V,E)，節(jié)點集V，邊集E。中心性指標表示圖中節(jié)點或者鏈路的重要程度。由于在不同的應用中節(jié)點或者鏈路的重要程度不同，一些指標可以基于給定的應用作為指示器來確定中心節(jié)點。

節(jié)點度中心性CD(v)定義為節(jié)點關(guān)聯(lián)的鏈路數(shù)，可以看作是節(jié)點連接的重要性。節(jié)點度是一種局部的中心性指標是由于它只依賴于局部連接的鏈路數(shù)。平均節(jié)點度表示為(v)。節(jié)點i、j之間的最短路徑dij為連接兩點之間跳數(shù)最小的路徑。平均最短路徑長度衡量網(wǎng)絡(luò)平均跳數(shù)。一些常用的圖度量標準如介數(shù)、半徑和直徑提供了所有節(jié)點對之間最短路徑的統(tǒng)計值。介數(shù)是一種可以用于節(jié)點和鏈路的中心性指標。節(jié)點介數(shù)CB(v)為經(jīng)過節(jié)點v的最短路徑的數(shù)目，而邊介數(shù)CB(l)定義為經(jīng)過鏈路l的最短路徑數(shù)。介數(shù)具有全局意義是由于介數(shù)反映的是圖的整體結(jié)構(gòu)。節(jié)點緊密性CC(v)是衡量節(jié)點v到其他節(jié)點平均距離的中心性指標。聚類系數(shù)CC(v)衡量節(jié)點v的鄰點全連接的程度。

2.2 相關(guān)圖譜理論知識

現(xiàn)有的一些研究用來量化惡意攻擊和隨機故障下圖的健壯性[3]。這里根據(jù)所提出的健壯性指標和評估方式，介紹每項指標的公式化表示及其預測中心性攻擊下網(wǎng)絡(luò)彈性的準確度等[11]相關(guān)工作。圖譜理論研究的是圖的結(jié)構(gòu)特性與圖的鄰接矩陣、關(guān)聯(lián)矩陣、拉普拉斯矩陣和標準化拉普拉斯矩陣的特征值和特征向量之間的關(guān)系[17]。

給定圖G=(V,E)，節(jié)點集V,邊集E，節(jié)點數(shù)為N，邊數(shù)為K。A=(Aij)N×N為圖G的鄰接矩陣，其中：

特征值μ為特征多項式det(A-μI)=0的根。{μ1,μ2,…,μN}為鄰接矩陣的特征值集合，元素呈遞增排列。譜隙定義為Δμ=μN-μN-1，為鄰接矩陣的最大特征值與第二大特征值之間的差，是衡量惡意攻擊下圖健壯性的一個圖譜指標[11]。自然連通度定義為，其中μi為鄰接矩陣的第i個特征值。自然連通度的值越大，網(wǎng)絡(luò)應對節(jié)點或者鏈路移除的健壯性越強。相比于平均節(jié)點度，自然連通度[13,18]在描述網(wǎng)絡(luò)彈性時更加準確。

3 網(wǎng)絡(luò)彈性優(yōu)化算法

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

一般的，將網(wǎng)絡(luò)表示為具有N個節(jié)點、K條邊的無向加權(quán)圖G=(V,E)，V={v1,v2,…,vN}為節(jié)點集合，E為邊的集合，eij∈E表示節(jié)點vi,vj∈V之間的鏈路。A=(Aij)N×N為圖的鄰接矩陣。假設(shè)節(jié)點對之間的網(wǎng)絡(luò)流選擇兩點之間的最短路徑通信。εij表示節(jié)點vi和vj之間使用最短路徑通信的效率，定義為節(jié)點對之間最短距離的倒數(shù)，表示為εij=1/dij，其中dij表示節(jié)點間最短距離。這里假設(shè)效率與距離之間成反比，當圖中節(jié)點vi和vj之間不存在路徑時dij=+∞，相應的εij=0。那么網(wǎng)絡(luò)的平均效率定義為：

即節(jié)點對之間最短距離倒數(shù)之和的平均值，用于測量G的效率或者性能，表示網(wǎng)絡(luò)平均通信的容易程度。E(G)的值越大，表示網(wǎng)絡(luò)的連通性越強。優(yōu)化網(wǎng)絡(luò)的平均效率改善網(wǎng)絡(luò)拓撲，可以提高網(wǎng)絡(luò)的運作效益和穩(wěn)定性，提升網(wǎng)絡(luò)應對隨機故障和惡意攻擊下的彈性[19-20]。

進一步，對于無向加權(quán)網(wǎng)絡(luò)G=(V,E,W)，W=(wij)N×N為考慮邊權(quán)之后的鄰接矩陣，當節(jié)點vi、vj之間有邊相連時wij為邊eij的權(quán)值，否則wij=∞。wij的值可以認為是從節(jié)點vi到節(jié)點vj的距離或者成本。設(shè)p(i,j)是加權(quán)圖中節(jié)點vi到節(jié)點vj的路徑，則，其中w(e)為邊e的權(quán)值，E(p)表示路徑p上邊的集合。那么節(jié)點vi、vj之間的最短距離，P為節(jié)點vi、vj之間所有路徑的集合。同理，可以定義加權(quán)網(wǎng)絡(luò)中的網(wǎng)絡(luò)平均效率。

3.2 優(yōu)化算法

本文使用一種啟發(fā)式算法，對給定圖Gi添加鏈路集。優(yōu)化算法的目標是選擇Lr條鏈路的集合最大化網(wǎng)絡(luò)的平均效率這一健壯性指標，即maxE(G)。算法迭代地選擇滿足目標函數(shù)的鏈路加入網(wǎng)絡(luò)改善網(wǎng)絡(luò)彈性。如下為拓撲優(yōu)化算法的偽代碼。

拓撲優(yōu)化算法的兩個輸入：初始圖Ai和所需鏈路數(shù)Lr。輸入圖Ai的節(jié)點數(shù)為Ni，鏈路數(shù)為Ki。所需鏈路數(shù)Lr為網(wǎng)絡(luò)圖中所需添加的鏈路數(shù)，由于現(xiàn)實中較少出現(xiàn)全連通網(wǎng)絡(luò)，考慮到網(wǎng)絡(luò)成本的約束，對網(wǎng)絡(luò)常見失效模式的防御和對于網(wǎng)絡(luò)性能的要求等因素可能只需要該網(wǎng)絡(luò)達到一定水平的健壯性而不一定需要百分之百可靠的網(wǎng)絡(luò)，因此只需要添加特定數(shù)量的鏈路，或者出于對現(xiàn)實中預算資金和現(xiàn)實網(wǎng)絡(luò)環(huán)境的考慮需要添加與約束相關(guān)的相應數(shù)量的鏈路，因此本文使用所需鏈路數(shù)這一參數(shù)作為算法輸入，并且鏈路數(shù)量由現(xiàn)實成本或者備選鏈路集合中鏈路的數(shù)量等決定。為了記錄迭代過程所選定的鏈路，算法將鏈路加入selectedLinks列表。每次迭代開始于上一次迭代所得圖，并對其添加鏈路。算法使用3個主函數(shù)：efficience(G)、candidate(G)和improvedLink(L)。平均效率函數(shù)efficience(G)返回給定圖的平均效率值，為該優(yōu)化算法的目標函數(shù)，根據(jù)3.1節(jié)的定義和公式，需要根據(jù)網(wǎng)絡(luò)的最短路徑算法求出節(jié)點對之間的最短路徑矩陣，計算網(wǎng)絡(luò)相應的效率矩陣，最后返回網(wǎng)絡(luò)的平均效率。備選鏈路函數(shù)candidate(G)以圖G為輸入，返回備選鏈路的集合，該鏈路集合由當前圖G中節(jié)點間不存在的邊組成。當前圖Ai中不存在的鏈路的數(shù)目為為圖Ai中的節(jié)點全連接狀態(tài)下的鏈路數(shù)減去當前圖Ai中的鏈路數(shù)。隨著ni的增大，其計算復雜度不斷增加。優(yōu)化算法不斷產(chǎn)生新解，于是需要在所有可行解中找出相對最優(yōu)解，使用improvedLink(L)函數(shù)，可以從candidate(G)函數(shù)選出的備選鏈路集合中選出最大程度上將圖的平均效率值改善的鏈路，添加到鏈路集合selectedLinks中。算法重復迭代直到選出足夠的鏈路，并且添加到初始圖中，得到最后的改善圖G。

拓撲優(yōu)化算法的具體步驟為：第一步，執(zhí)行偽代碼第1行到第3行，初始化鏈路集合selectedLinks和迭代鏈路iterationList列表；第二步，執(zhí)行第7行到第9行的for循環(huán)，對于圖G的候選鏈路集合candidate(G)中的鏈路l，計算添加鏈路l后圖G的平均效率函數(shù)efficience(G)賦值給中間變量improvement，同時將鏈路l和函數(shù)值記錄到iterationList列表；第三步，執(zhí)行算法偽代碼10到12行，對列表iterationList中記錄的鏈路施加函數(shù)improvedLink(L)選擇出使得平均效率函數(shù)改善效果最大的鏈路，并添加到selectedLinks鏈路列表，同時在圖G上添加該鏈路得到該迭代過程的新圖；第四步，執(zhí)行第4行的While循環(huán)，如果selectedLinks列表中的鏈路數(shù)小于所需添加鏈路數(shù)Lr，轉(zhuǎn)到第二步，否則，返回selectedLinks和圖G，算法結(jié)束。

4 彈性測量

本章首先介紹如何使用圖的流健壯性[10,16]度量標準衡量網(wǎng)絡(luò)彈性。然后，給出用于彈性評估的攻擊模型，以及所研究的3種復雜網(wǎng)絡(luò)拓撲。最后，使用流健壯性指標量化節(jié)點攻擊下的網(wǎng)絡(luò)彈性。

4.1 流健壯性

流健壯性是一種圖論度量標準，測量可靠流的數(shù)量占網(wǎng)絡(luò)中總的網(wǎng)絡(luò)流數(shù)量的比率。網(wǎng)絡(luò)流稱為可靠流，如果存在節(jié)點或鏈路故障時節(jié)點對之間至少有一條路徑保持正常?？偟木W(wǎng)絡(luò)流數(shù)量為網(wǎng)絡(luò)中可能存在流的最大數(shù)量，對于N個節(jié)點的網(wǎng)絡(luò)，總的流數(shù)為N(N-1)/2。該標準衡量移除節(jié)點或鏈路之后，網(wǎng)絡(luò)節(jié)點與其他節(jié)點通信的能力。流健壯性的取值范圍為[0,1]，1表示網(wǎng)絡(luò)中的任意節(jié)點對之間可以通信，即網(wǎng)絡(luò)為連通圖；0表示整個網(wǎng)絡(luò)中不存在可以通信的節(jié)點對，即網(wǎng)絡(luò)中不存在鏈路。給定網(wǎng)絡(luò)圖G=(V,E)，集合{Ci;1＜i＜k}表示圖G的連通分支。網(wǎng)絡(luò)的流健壯性表示為：

計算FR的算法復雜度取決于給定圖中尋找連通分支的復雜度，為O(|V|+|E|)。由于k的最大值可能取為|V|，最壞情況的復雜度可能為|V|。因此計算流健壯性的算法復雜度為O(|V|+|E|+|V|)，簡化為O(|V|+|E|)。本文使用流健壯性指標是因為：第一，它與網(wǎng)絡(luò)仿真中對于所有的節(jié)點對之間以給定的比特率通信的包遞交率結(jié)果匹配；第二，它能有效地評估網(wǎng)絡(luò)的連通性。

下面以一個9個節(jié)點的車輪形拓撲為例，通過計算介數(shù)攻擊下的流健壯性值，說明如何測量網(wǎng)絡(luò)彈性。在每次迭代中，移除一個節(jié)點并且計算流健壯性值。節(jié)點刪除列表可以由節(jié)點攻擊的任何可能方式定義。例如基于最高的介數(shù)值依次攻擊節(jié)點，產(chǎn)生節(jié)點列表{0,1,5,3,7,8,2,4,6}。圖1描述了連續(xù)攻擊下的網(wǎng)絡(luò)拓撲。其中淺綠色節(jié)點表示節(jié)點未被攻擊處于連通狀態(tài)，深紅色節(jié)點為攻擊節(jié)點表示不連通狀態(tài)的節(jié)點。節(jié)點一旦被攻擊，連接該節(jié)點的所有鏈路將被移除。每次迭代過程的健壯性值如表1。Step 2中，刪除節(jié)點0之后將移除8條鏈路，而流健壯性值減少0.22，此時其他節(jié)點可以使用備選路徑通信。然而Step 4中，流健壯性值減少0.58-0.17=0.41，由于圖被分割為兩個分支造成了流健壯性的減少量最大。在Step 6之后結(jié)束，此時圖中無剩余鏈路。

Table 1 Flow robustness values of wheel topology表1 車輪形拓撲的流健壯性測量

4.2 圖的攻擊模型

本文使用圖論模型攻擊給定的網(wǎng)絡(luò)，說明每次節(jié)點移除后網(wǎng)絡(luò)的流健壯性如何變化。使用隨機故障模型和3種中心性測量標準：節(jié)點介數(shù)、節(jié)點緊密度和節(jié)點度。針對3種中心性測度[6]分別使用3種攻擊模型，移除中心性值最高的節(jié)點。節(jié)點介數(shù)攻擊的目標是最短路徑經(jīng)過次數(shù)最多的節(jié)點。節(jié)點緊密性攻擊的目標是與其他節(jié)點跳數(shù)最近的節(jié)點。節(jié)點度攻擊移除的是具有最多鄰點的節(jié)點。節(jié)點移除列表根據(jù)不同的攻擊模式自適應地產(chǎn)生。自適應節(jié)點移除與非適應性移除相比，每次移除當前網(wǎng)絡(luò)中中心性最高的節(jié)點。

Fig.1 Wheel topology under betweenness attack圖1 介數(shù)攻擊下的車輪形拓撲

4.3 數(shù)據(jù)集

本文采用3種拓撲結(jié)構(gòu)測量所提出算法的有效性，評估它們在隨機故障和惡意攻擊下的網(wǎng)絡(luò)彈性。包括典型的復雜網(wǎng)絡(luò)模型如ER隨機網(wǎng)絡(luò)模型和BA無標度網(wǎng)絡(luò)模型，以及一種保證節(jié)點數(shù)和平均節(jié)點度的拓撲產(chǎn)生模型，簡單記為AD連通網(wǎng)絡(luò)。為了方便了解本文所提出算法對網(wǎng)絡(luò)的優(yōu)化狀況，文中以車輪形網(wǎng)絡(luò)拓撲為例說明所提出的優(yōu)化算法如何實現(xiàn)對網(wǎng)絡(luò)拓撲健壯性的改善，因此所研究的重點還是復雜網(wǎng)絡(luò)拓撲模型。另外，列出每種拓撲的經(jīng)典圖論指標表現(xiàn)圖的拓撲特性，包括節(jié)點數(shù)、邊數(shù)、平均度和平均跳數(shù)，如表2所示。然后，將本文所提出的最優(yōu)化算法應用于這4種網(wǎng)絡(luò)拓撲，對每種網(wǎng)絡(luò)拓撲運用提出的最優(yōu)化算法改善拓撲，評估網(wǎng)絡(luò)彈性。

5 仿真及分析

本文使用流健壯性指標量化網(wǎng)絡(luò)彈性，使用圖的平均效率這一最優(yōu)化目標函數(shù)，采用加邊策略實現(xiàn)對于網(wǎng)絡(luò)拓撲的優(yōu)化，提升網(wǎng)絡(luò)應對隨機故障和惡意攻擊下的網(wǎng)絡(luò)健壯性。本章執(zhí)行前面提出的彈性優(yōu)化算法，對規(guī)則的車輪形網(wǎng)絡(luò)和3種復雜網(wǎng)絡(luò)分別添加與該網(wǎng)絡(luò)節(jié)點數(shù)相同數(shù)目的鏈路，即對9個節(jié)點的車輪形網(wǎng)絡(luò)拓撲添加9條鏈路，對節(jié)點數(shù)為50的ER隨機網(wǎng)絡(luò)添加50條鏈路，優(yōu)化算法中的輸入Lr設(shè)置為50，同理對于BA無標度網(wǎng)絡(luò)和AD連通網(wǎng)絡(luò)分別添加75和50條鏈路，使得網(wǎng)絡(luò)的平均效率函數(shù)最大化。對于上述4種網(wǎng)絡(luò)拓撲，算法輸入的初始圖的網(wǎng)絡(luò)平均效率值non-improvedAE（average efficiency）和使用該算法改善后優(yōu)化網(wǎng)絡(luò)的平均效率值improved AE由表3的第三列和第四列給出。

Table 2 Dateset of topology表2 拓撲數(shù)據(jù)集

上述拓撲是本文仿真實驗使用的主要網(wǎng)絡(luò)拓撲，在實驗中先使用選定的網(wǎng)絡(luò)拓撲模型生成相應的初始網(wǎng)絡(luò)拓撲，每種網(wǎng)絡(luò)拓撲模型生成10種具體網(wǎng)絡(luò)拓撲，然后使用彈性優(yōu)化算法得到網(wǎng)絡(luò)改善圖，對每種拓撲模型中生成的每一個網(wǎng)絡(luò)拓撲進行20次優(yōu)化實驗，并對每一次優(yōu)化網(wǎng)絡(luò)施加隨機故障和3種惡意攻擊，記錄每個網(wǎng)絡(luò)的性能衰落表現(xiàn)，最后將每一個網(wǎng)絡(luò)拓撲多次性能衰落數(shù)據(jù)相應取平均作為該拓撲的性能表現(xiàn)，對同一類型下的多個網(wǎng)絡(luò)拓撲進行統(tǒng)計作為每一種拓撲模型的性能表現(xiàn)，從而進行彈性性能對比，評估所提出算法的性能。使用的操作系統(tǒng)為Windows 7，實驗編程硬件環(huán)境：處理器為Pentium III 933 MHz或以上級別，內(nèi)存128 MB或以上，硬盤可用空間100 GB或以上，軟件環(huán)境Matlab 7.1或以上。

Table 3 Average efficiency of non-improved and improved graphs表3 初始圖和改善圖的平均效率

仿真過程使用圖論模型攻擊給定圖，并且給出網(wǎng)絡(luò)的流健壯性隨每次攻擊的改變情況。分別使用隨機故障模型和3種中心性（介數(shù)、緊密度和節(jié)點度）攻擊模型，每次迭代刪除中心性值最高的節(jié)點，節(jié)點的刪除列表隨著攻擊模型的不同而改變。

對于本文提出的以平均效率為優(yōu)化函數(shù)（AE-improved）的拓撲改善算法，使用兩種優(yōu)化算法進行對比，比較算法的改善效果。一種為參考文獻[13]中使用的網(wǎng)絡(luò)自然連通度改善算法（NC-improved），即選擇自然連通度作為健壯性指標對網(wǎng)絡(luò)拓撲進行加邊優(yōu)化，輸出網(wǎng)絡(luò)的改善圖。另一種為參考文獻[11]中出現(xiàn)的網(wǎng)絡(luò)譜隙優(yōu)化算法（SG-improved），以初始網(wǎng)絡(luò)拓撲（non-improved）作為輸入，圖譜理論中的譜隙標準作為優(yōu)化函數(shù)，對網(wǎng)絡(luò)迭代地添加指定數(shù)量的鏈路以改善網(wǎng)絡(luò)的連通性，輸出改善圖。

對于每種網(wǎng)絡(luò)拓撲，給出相應的網(wǎng)絡(luò)初始圖（non-improved）、本文提出的平均效率改善拓撲（AE-improved）、兩種對比算法的自然連通度改善拓撲（NC-improved）和譜隙改善拓撲（SG-improved），采用隨機故障和3種攻擊模型刪除對應網(wǎng)絡(luò)中半數(shù)以上的節(jié)點，在攻擊模型下各種拓撲的健壯性表現(xiàn)不同，采用流健壯性指標評估網(wǎng)絡(luò)彈性，仿真結(jié)果如圖2～圖5。

以車輪形拓撲為例，圖2（a）～圖2（d）分別表示的是該拓撲在隨機故障和3種中心性攻擊下網(wǎng)絡(luò)的健壯性變化情況。圖2（a）中，在隨機故障模型下，每刪除一個節(jié)點，剩余的節(jié)點在同一個連通分支中，相互保持連通，因此對于初始圖和3種改善圖網(wǎng)絡(luò)的健壯性表現(xiàn)一致。圖2（b）與圖2（c），由于車輪形拓撲的特殊性，介數(shù)攻擊和緊密度攻擊產(chǎn)生相同的節(jié)點刪除列表，此時3種網(wǎng)絡(luò)改善圖相比于初始圖健壯性有所增強，同樣的現(xiàn)象出現(xiàn)在圖2（d）中。在車輪形網(wǎng)絡(luò)拓撲中，所提出的平均效率改善算法的改善效果與兩種對比算法無明顯差別，這是由于車輪形網(wǎng)絡(luò)節(jié)點之間最多兩跳可達，加邊過程實際上是增加一跳可達的節(jié)點對的數(shù)目。當網(wǎng)絡(luò)中增加9條鏈路時，基本可以保證每刪除一個節(jié)點，其他節(jié)點保持相互連通的狀態(tài)，即網(wǎng)絡(luò)的流健壯性在刪除節(jié)點后保持所能維持的最佳狀態(tài)。而對于3種典型的復雜網(wǎng)絡(luò)而言，不同的拓撲優(yōu)化算法所表現(xiàn)出的網(wǎng)絡(luò)健壯性明顯不同。

ER隨機網(wǎng)絡(luò)在隨機故障模型下的網(wǎng)絡(luò)健壯性如圖3（a）所示。在節(jié)點攻擊模型下，本文所提出優(yōu)化算法，即平均效率改善拓撲的流健壯性隨節(jié)點移除數(shù)量的變化用黑色帶星號的曲線表示。在ER隨機網(wǎng)絡(luò)的流健壯性分析仿真圖3中，自然連通度改善圖、譜隙改善圖、初始圖在故障模型下的流健壯性隨刪除節(jié)點數(shù)的變化分別為藍色、品紅和紅色曲線。介數(shù)、緊密度和節(jié)點度攻擊模型下的網(wǎng)絡(luò)彈性分析分別如圖3（b）、圖3（c）、圖3（d）所示。從仿真結(jié)果可以看出，對于ER隨機網(wǎng)絡(luò)，本文所提出的算法改善網(wǎng)絡(luò)拓撲的效果最好，應對隨機故障和惡意攻擊具有較高的網(wǎng)絡(luò)彈性。該結(jié)論在BA無標度網(wǎng)絡(luò)模型和AD連通網(wǎng)絡(luò)模型中同樣成立。BA網(wǎng)絡(luò)和AD網(wǎng)絡(luò)在隨機故障和惡意攻擊下的流健壯性仿真結(jié)果如圖4、圖5所示。代表網(wǎng)絡(luò)平均效率改善算法的黑色曲線整體處在其他曲線的上方，具有較高的流健壯性值。雖然圖5（c）中BA網(wǎng)絡(luò)處于節(jié)點度攻擊下黑色曲線少量點的流健壯性值低于品紅色曲線，實驗分析不排除出現(xiàn)這種情況的可能性，但是整體的仿真結(jié)果說明本文的優(yōu)化算法較其他算法而言具有明顯的優(yōu)勢。由于網(wǎng)絡(luò)彈性量化為刪除節(jié)點下的流健壯性值，值越大，網(wǎng)絡(luò)應對攻擊下的彈性越強。通過研究表2中的網(wǎng)絡(luò)模型，結(jié)果表明本文提出的加邊優(yōu)化算法，相比于另外兩種對比算法，應對節(jié)點攻擊方面表現(xiàn)出更好的網(wǎng)絡(luò)彈性。

Fig.2 Flow robustness analysis of wheel topology圖2 車輪形拓撲的流健壯性分析

Fig.3 Flow robustness analysis of ER random network圖3 ER隨機網(wǎng)絡(luò)的流健壯性分析

Fig.4 Flow robustness analysis of BAscale-free network圖4 BA無標度網(wǎng)絡(luò)的流健壯性分析

Fig.5 Flow robustness analysis ofAD connected network圖5 AD連通網(wǎng)絡(luò)的流健壯性分析

6 結(jié)論

網(wǎng)絡(luò)設(shè)計和優(yōu)化是復雜網(wǎng)絡(luò)科學研究的一個重要領(lǐng)域，提出改善已有網(wǎng)絡(luò)性能的有效算法，是復雜網(wǎng)絡(luò)彈性研究的根本目的。本文提出一種迭代算法優(yōu)化網(wǎng)絡(luò)拓撲，對給定圖添加鏈路改善網(wǎng)絡(luò)的平均效率函數(shù)，提高網(wǎng)絡(luò)彈性。將該算法用于3種復雜網(wǎng)絡(luò)拓撲并且比較算法的效益。通過采用隨機故障和基于中心性的攻擊，測試和評估原始圖和改善圖的網(wǎng)絡(luò)彈性。與圖譜理論的一些健壯性優(yōu)化算法進行對比，仿真結(jié)果表明在所研究的健壯性指標中，本文提出的啟發(fā)式算法可以優(yōu)化網(wǎng)絡(luò)拓撲，相比于其他的改進算法在應對隨機故障和中心性攻擊方面更加具有彈性。人們逐漸加重的對互聯(lián)網(wǎng)的依賴性以及服務(wù)的復雜化使得網(wǎng)絡(luò)易于受到攻擊，由于現(xiàn)實網(wǎng)絡(luò)所面臨挑戰(zhàn)的多樣性，使得未來網(wǎng)絡(luò)的彈性設(shè)計以及現(xiàn)有網(wǎng)絡(luò)的彈性改善變得尤為重要，因此，該算法在完善基礎(chǔ)設(shè)施網(wǎng)絡(luò)和服務(wù)網(wǎng)絡(luò)的彈性性能方面具有實際應用價值。