復雜信息網絡的彈性評估和優化方法研究*

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

1.西安電子科技大學 數學與統計學院，西安 710071

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

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

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

1 引言

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

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

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

2 背景和相關工作

2.1 圖中心性度量

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

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

2.2 相關圖譜理論知識

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

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

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

3 網絡彈性優化算法

3.1 網絡模型

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

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

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

3.2 優化算法

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

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

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

4 彈性測量

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

4.1 流健壯性

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

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

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

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

4.2 圖的攻擊模型

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

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

4.3 數據集

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

5 仿真及分析

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

Table 2 Dateset of topology表2 拓撲數據集

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

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

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

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

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

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

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

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

Fig.3 Flow robustness analysis of ER random network圖3 ER隨機網絡的流健壯性分析

Fig.4 Flow robustness analysis of BAscale-free network圖4 BA無標度網絡的流健壯性分析

Fig.5 Flow robustness analysis ofAD connected network圖5 AD連通網絡的流健壯性分析

6 結論

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