吳嫣媛，劉向軍

(華北電力大學 電氣與電子工程學院，北京 102206)

0 引 言

目前對復雜網絡節(jié)點重要性判斷方法都是針對具體問題提出的，存在一定的片面性和局限性，且會隨著網絡結構的變化使識別結果存在一定誤差[1,3]。文獻[4,5]指出了這種缺點，進而引入優(yōu)化理論來進行關鍵節(jié)點識別，從攻擊的角度通過節(jié)點失效后網絡性能下降的方法來確定節(jié)點的重要性，以網絡性能最小為目標采用禁忌搜索算法得到節(jié)點排序，使得識別方法適用于不同結構與類型的網絡。但文獻[4,5]在構建網絡抗毀性測度衡量網絡性能時，假設一個節(jié)點的失效不會影響其它節(jié)點，沒有考慮拓撲結構的改變導致網絡中物質流的變化，不能很好地反映真實的節(jié)點重要程度。文獻[6-8]在計算節(jié)點失效后的網絡性能測度時引入了級聯失效過程，很好地切合了實際網絡的這種動態(tài)特征。因此在關鍵節(jié)點識別過程中計算魯棒性測度衡量網絡性能時，應當考慮網絡級聯失效過程。同時文獻[4,5]采用的禁忌搜索算法是一種基于單點搜索的元啟發(fā)式算法，且具有對初始解依賴性較強、多樣性不足等缺 點。

本文采用優(yōu)化算法進行復雜網絡的關鍵節(jié)點識別，在此基礎上，考慮網絡的動態(tài)性引入級聯失效模型改進網絡魯棒性測度，并針對禁忌搜索算法的缺點，改進人工魚群算法作為節(jié)點序列構造模型的求解算法，最后對比攻擊不同策略識別的關鍵節(jié)點在模擬網絡上的效果，驗證本文策略的有效性和優(yōu)越性。

1 級聯失效模型

受制于硬件成本，每個節(jié)點都具有給定的負載容納能力。最初，網絡處于穩(wěn)定狀態(tài)，其中每個節(jié)點的負載小于其容量。由于節(jié)點的故障，網絡受到了干擾，故障改變網絡中流量的平衡，負載將重新分配給其它節(jié)點，并可能進一步導致其余節(jié)點過載，并足以引起整個系統故障。級聯失效反映的是網絡的動態(tài)特性，網絡拓撲結構的改變造成網絡數據流的重新分配，此過程描述如下[9,10]：

任何一個網絡可由圖G=(V,E)作抽象表示。V(G)是有限非空集，V中元素稱為G的頂點，N=|V|表示網絡中的節(jié)點數，E(G)是V(G)中頂點之間的邊的集合。在很多情況下，常直接用介數或對介數稍加修正作為真實流量的近似值，網絡的實時流量如下

(1)

B(x)用于表示節(jié)點的流量。gij(x)定義為從節(jié)點i到j經過節(jié)點x的最短路徑的數量。gij是從節(jié)點i到j的所有最短路徑數。此外，節(jié)點自身的數據量L也是總負載的重要組成部分。因此，節(jié)點x在時間t的負載可以表示為

(2)

其中，Lx(t)表示在時間t節(jié)點x的總負載，L為節(jié)點x的自身負載。由于大多數網絡節(jié)點的承載有限，將節(jié)點負載的上限定義為容量Cp，是節(jié)點過載和性能降低之前可以處理的最大負載，用時間t=0時的負載Lx(t)乘以容忍系數T表示

Cp=T·Lx(0),x=1,2,…,N

(3)

其中，T≥1。當在時間t-1處節(jié)點x的流量負載超過Cp時，在時間t處節(jié)點將過載。以一簡單的隨機網絡為例說明這個過程，令N=100，隨機移除10個節(jié)點，負載變化如圖1所示。以44號節(jié)點為例，網絡結構發(fā)生變化后負載約為原始的1.597倍，倘若T小于這個數目，此節(jié)點過載失效，其余負載增大的節(jié)點同理，從而引發(fā)新一輪負載的變化。

圖1 隨機網絡中移除10個節(jié)點負載變化

2 基于級聯失效的魯棒性測度

網絡性能常用抗毀性測度衡量，通常被定義為i個節(jié)點被移除后，其最大連通分量的規(guī)模的變化[5]。文獻[11]考慮網絡級聯失效特點，采用級聯失效前后，最大連通分量節(jié)點數之比衡量網絡受損性能。本文結合級聯失效改進網絡魯棒性測度。假使網絡G中有n個節(jié)點，標號分別為1～n，則一個節(jié)點序列可表示為(k1,k2,…,kn)，是節(jié)點的一個排序。按照節(jié)點排序K={k1,k2,…,kn}去逐個攻擊網絡G中的節(jié)點，當節(jié)點失效，執(zhí)行上一節(jié)模型描述的級聯失效過程。隨著節(jié)點的失效，該網絡在節(jié)點失效后的魯棒性R可以定義為

(4)

其中，C(i)表示網絡G中i個節(jié)點遭到攻擊，網絡負載重分配完畢或級聯失效過程完全完成后網絡的最大連通分量規(guī)模。R(G,K)越小，隨著節(jié)點失效下降得越快，說明網絡在這些節(jié)點失效后越容易遭到破壞，節(jié)點越重要，識別方法越準確。

3 基于改進人工魚群算法的關鍵節(jié)點識別

3.1 求解模型與基本人工魚群算法

基于優(yōu)化理論進行關鍵節(jié)點識別，目標是構造出節(jié)點失效后網絡魯棒性R(G,K)下降最嚴重的節(jié)點序列K,R(G,K)越小，說明當節(jié)點序列K失效時網絡越容易崩潰。因此其構造方式可以視為一個優(yōu)化問題[4,5]。表示如下

(5)

其中，Set_K是所有節(jié)點序列構成的集合。

(1)覓食行為：人工魚的感知距離范圍Visual內隨機選擇一個新位置，向著對應適應度值更小的新位置移動。如果到達嘗試次數后仍不滿足前進條件，執(zhí)行隨機行為。

(2)聚群行為：聚群行為是指每條魚在移動過程中趨向于相鄰伙伴的中心以避免過度擁擠的行為。當前位置和中心位置對應適應度值Yi和Yc，nf為中心位置附近視野中的人工魚的數量，δ為擁擠因子；Yc值更小且Yc/nf<δYi，則前進到中心位置。不滿足條件則執(zhí)行覓食行為。

(3)追尾行為：追尾行為表示每條人工魚在視覺范圍內都朝著當前的最佳方向移動。假設Xmin是當前狀態(tài)Xi的鄰域內最優(yōu)鄰居。如果Ymin

(4)隨機行為：隨機行為是在其視野中隨機選擇一個新狀態(tài)Xnext，然后在該方向上移動一步。實際上這是默認行為。

(5)公告板：公告板用于記錄魚群中的最佳狀態(tài)Xnext。

算法完成后，最終公告板的值是系統的最佳解決方案。

3.2 算法性能改進

AFSA存在一些缺陷，例如更容易陷入局部最優(yōu)值和缺乏多樣性等。為了彌補這一不足，對AFSA進行改進。

(1)初始解的構造：本文通過引入佳點集的方法，優(yōu)化AFSA算法的初始人工魚群分布，提高AFSA算法的全局搜索性能。本質上，優(yōu)化人工魚群的初始分布是為了更科學地表征解空間的特征，人工魚群體在解空間中的均勻分布是一種有效的策略，而隨機產生的人工魚群體在大多數情況下不能覆蓋解空間的所有狀況。由數論中的佳點集理論可知，佳點集的精度與空間維度無關，可以較好地適用于高維空間中的計算，同時，對于未知分布的對象，通過佳點集理論獲得的佳點集Ps(i)的偏差遠遠優(yōu)于通過隨機方法獲得的集合。因此，基于佳點集的特征，可以為群體智能算法中的群體分布提供更好的初始分布方案[14]。假設初始人工魚群數為s，在n維空間中選擇s點作為人工魚位置，作佳點集

Ps(i)={({r1*i},{r2*i},…,{rn*i}),i=1,2,…,s}

(6)

r稱為佳點，可由下式計算

(7)

其中，p為滿足(p-n)/2≥n的最小質數，符號{a}表示數a的小數部分。由于本算法的解空間是節(jié)點序列的集合，將此佳點集映射到問題的可行域中，則第i個可行解的第k維的值為K(k,i)=[1+Ps(i)k(s-1)],i=1,2,…,s，符號[a]表示數a的整數部分。

(2)覓食行為的改進：在迭代過程中，標準AFSA算法通過覓食行為來實現全局搜索。當適應度值提高時，算法的收斂速度降低。細菌覓食優(yōu)化算法(BFOA)中的趨化行為通過翻轉與游泳操作使細菌聚集在一個更有利的環(huán)境中，能增強覓食行為，進入更大的搜索空間，并避免陷入局部最優(yōu)狀態(tài)。因此，采用BFOA算法的趨化行為對覓食行為進行改進[15]。與標準AFSA算法相比，趨化行為在處理覓食行為時增加了鄰域搜索的頻率和范圍。適應度值在翻轉操作完成后進行計算。當得到的適應度值更優(yōu)，人工魚將向該方向移動幾步，直到游泳步數Ns達到極限值Nsmax或適應度值重合，否則執(zhí)行隨機行為。覓食行為在當前位置停止覓食，并翻轉為另一條人工魚，當所有人工魚完成翻轉，該過程完成。改進的覓食行為可以加快收斂速度并增加潛在解。人工魚的位置i可以更新如下

(8)

其中，Step為實數。

(3)隨機行為的改進：列維飛行是一種隨機游走策略，是一種典型的飛行、跳躍的步長可進行變化的策略，從而使得搜索空間的結果更有效。因此，將列維飛行添加到自然啟發(fā)算法中，可確保算法的改進。在AFSA中，隨機行為是一種變異策略，可以防止算法陷入局部最優(yōu)。在本節(jié)中，將列維飛行引入AFSA隨機行為。列維飛行可簡單近似為冪律行為，滿足此分布的隨機步長S可以通過Mantegna方法計算為

(9)

其中，u和v服從正態(tài)分布如下

u=N(0,σ2),v=N(0,1)

(10)

(11)

(12)

4 實驗仿真與分析

為驗證本文所提的關鍵節(jié)點識別方法的準確性，本節(jié)在3種不同拓撲結構的典型復雜網絡及真實網絡中進行仿真實驗，包括本文所改進的優(yōu)化算法與文獻[5]中該領域已采用的優(yōu)化算法、標準AFSA算法對比，及不同節(jié)點識別方法的對比。改進人工魚群算法最大嘗試次數50，最大迭代次數100，Nsmax取4，δ為0.618，人工魚每次移動的最大步長step取1，visual取0.1。標準AFSA相同參數取相同值。整體關鍵節(jié)點識別方法與傳統采用的基于度的衡量方法、文獻[16]綜合評價方法、文獻[17]方法在不同網絡結構上進行分析比較。3種典型網絡的生成參照文獻[18]。美國航空網絡是研究負載變化的重要網絡[8]，本文用于實驗的真實網絡采用美國航空網絡數據集[19]。復雜網絡的建立及后續(xù)的實驗均采用Matlab R2012a在Intel Core i7處理器配置下完成。

4.1 不同容忍系數下保護關鍵節(jié)點的網絡性能比較

本小節(jié)主要探討級聯失效模型所涉及的關鍵參數T下保護不同方法識別的關鍵節(jié)點對網絡抗毀性能的影響，具體關鍵節(jié)點識別方法的性能在后述小節(jié)進行對比，本小節(jié)不作詳細敘述。采用不同方法在不同的容忍系數T下識別的節(jié)點序列中，保護前10%個節(jié)點，面對隨機攻擊的網絡性能如圖2所示。由網絡級聯失效模型可知，容忍系數T越大，則網絡承載級聯失效的能力越強。在4種網絡中比較總體性能，當T不斷增大，由級聯失效引發(fā)的節(jié)點故障越少，網絡性能都有所提高。不保護任何節(jié)點的網絡性能曲線波動最大，基于優(yōu)化算法的曲線性能值最高，曲線最平穩(wěn)。這是由于不對任何節(jié)點進行保護，當隨機打擊的節(jié)點重要性較低，則對網絡的影響較小，否則網絡性能則受到較大影響，代表網絡性能的魯棒性值也就有所波動。使用優(yōu)化算法識別關鍵節(jié)點過程中考慮了級聯失效過程，保護對網絡影響較大的關鍵節(jié)點，也相當于把引發(fā)較大級聯失效的節(jié)點保護起來，每一個T下達到的性能最高。文獻[17]方法雖然在仿真實驗中考慮了級聯失效動態(tài)特性，但關鍵節(jié)點識別仍是傳統方法，與其它方法一樣識別過程中不考慮級聯失效的影響，而忽略一些會引發(fā)較大級聯失效的關鍵節(jié)點，在隨機打擊下實驗曲線有所波動，小世界網絡中尤為明顯。無標度網絡各曲線起點值明顯較高，對節(jié)點加以保護的各曲線均較為平穩(wěn)，也說明了當無標度網絡的少數關鍵節(jié)點保護起來以后，對隨機失效有較強的抗毀性。美國航空網絡的實驗曲線變化與無標度網絡類似，曲線起點值高且曲線平穩(wěn)，面對隨機失效具有較強的魯棒性。

圖2 不同容忍系數T下保護關鍵節(jié)點的網絡性能比較

當T到達一定值，級聯失效消失，而只有隨機攻擊引發(fā)的節(jié)點故障。以波動最大的小世界網絡為例進行對比分析，基于優(yōu)化算法和文獻[16]綜合評價方法的曲線在T達到一定值時趨于穩(wěn)定，其它曲線波動較大，基于優(yōu)化算法的曲線值仍然最高，說明基于優(yōu)化算法的識別方法仍然比其它方法準確；其次為文獻[16]的綜合評價方法，當不考慮網絡級聯失效的特性，此種方法較為準確。文獻[17]采用的評價指標實質計算上只涉及了度和介數兩種指標，與基于度方法一樣曲線值波動較大，說明保護關鍵節(jié)點后的網絡性能得不到有效改善，識別的關鍵節(jié)點不太準確。對性能最好的本文方法，和采用的傳統識別方法中性能最好的文獻[16]方法進行詳細分析，要達到穩(wěn)定所需的T值，本文方法在隨機網絡中約為T=1.4，無標度網絡中約為T=1.3，小世界網絡中約為T=1.5，美國航空網絡中約為T=1.3 達到的穩(wěn)定值分別約為0.75，0.85，0.8，0.9；文獻[16]方法對應T值分別為1.5，1.35，1.6，1.5，穩(wěn)定值分別約為0.7，0.8，0.67，0.85，本文方法的網絡性能分別優(yōu)7.14%、6.25%、19.4%，5.88%；達到穩(wěn)定值所需T值越小，亦即要排除級聯失效影響需要對節(jié)點擴充的容量較小，節(jié)省成本，保護關鍵節(jié)點能有效改善網絡性能。

4.2 改進優(yōu)化算法性能分析

將本文改進的AFSA算法與標準AFSA算法、文獻[5]的禁忌搜索算法于4種網絡中進行關鍵節(jié)點識別，本小節(jié)主要通過對比比較算法的優(yōu)劣，驗證本方法改進策略的有效性。在隨機網絡中選取T=1.3，無標度網絡中選取T=1.2，小世界網絡中選取T=1.4，美國航空網絡中取T=1.2。在分析比較中，以第2節(jié)中魯棒性函數R為目標函數進行搜索識別。由于所用于實驗的網絡及算法的目標函數是相同的，因而識別結果的差異主要受算法性能的影響。由圖3可以看出，基于3種優(yōu)化算法的識別結果有一定的相似度，在無標度網絡中較為接近。在4種網絡結構中基于改進人工魚群算法的網絡性能下降最快，移除相同數目的節(jié)點網絡性能最低。其次為文獻[5]方法。本文方法的結果優(yōu)勢是明顯的，尤其是相較于標準AFSA算法而言。從優(yōu)化算法尋優(yōu)過程可知，各算法根據不同的節(jié)點序列排序使節(jié)點失效，依據適應度值最小判斷出最優(yōu)的序列，因此最后得到的節(jié)點序列應是失效后使網絡性能值最低的序列，但優(yōu)化算法不能遍歷所有情況，因此需要不斷尋求性能最佳的優(yōu)化算法。本文算法在這個過程中尋找的序列最為準確，性能最好，這是由于AFSA算法相比于禁忌搜索算法而言具有并行處理能力，加之本文采用佳點集、趨化行為和列維飛行等改進策略，得到了較好的搜索效果。標準AFSA算法識別的關鍵節(jié)點失效對網絡性能的影響比前兩種算法弱，在搜索次數相同的情況下，標準AFSA算法還得不到較優(yōu)的結果序列，作為相比于禁忌搜索算法本具有的優(yōu)勢也沒有體現出來，也說明了本文改進策略的有效性。

圖3 移除不同優(yōu)化算法識別的關鍵節(jié)點后網絡性能比較

4.3 整體識別算法性能分析

為分析整體關鍵節(jié)點識別方法性能，采用移除排序靠前節(jié)點來分析網絡性能的變化。如圖4所示，由網絡性能的變化可以看出本文方法的前10%至20%左右的節(jié)點移除后，網絡連通性急劇下降，網絡效率下降明顯，3種典型拓撲結構網絡中，隨機網絡模型中移除27%節(jié)點，無標度網絡中移除17%節(jié)點，小世界網絡中移除36%的節(jié)點，網絡性能即降低到0.1以下，其次為文獻[16]方法，使網絡性能即降低到0.1以下需分別移除41%、32%、52%節(jié)點，說明本文算法較為優(yōu)越。以無標度網絡為例列出各方法得到的節(jié)點序列前10%的結果見表1，可以看出本文方法與其它方法識別結果差異較大。由于本文利用優(yōu)化算法進行關鍵節(jié)點識別的過程中考慮了級聯失效的影響，所識別的引發(fā)較大級聯失效的幾個節(jié)點，在其它方法序列前10%節(jié)點中基本都不含有，當這些重要節(jié)點被攻擊，同時引發(fā)級聯失效以最大化地破壞網絡，網絡性能急劇下降，其它3種傳統關鍵節(jié)點識別方法則沒有考慮網絡的這種動態(tài)特性。3種傳統方法中網絡性能下降最快的是文獻[16]方法，在隨機網絡和小世界網絡中較為明顯，在無標度網絡中3種傳統方法效果差別不大。這是由于文獻[16]方法考慮的多個指標中包括網絡的整體連通性，更為全面，另兩種方法評價節(jié)點重要性時則沒有考慮。無標度網絡少數關鍵節(jié)點往往也是度最大的節(jié)點，由表1可看出，3種方法識別的節(jié)點較為接近。

圖4 移除不同方法識別的關鍵節(jié)點后網絡性能比較

表1 各方法對無標度網絡的節(jié)點識別排序部分結果

在美國航空網絡的實驗中，本文方法仍取得最優(yōu)的結果，使網絡性能降低至0.1以下，本文方法、文獻[16]、文獻[17]、基于度方法識別的關鍵節(jié)點需分別移除36%，57%，66%，71%的節(jié)點，對網絡造成崩潰，對關鍵節(jié)點的攻擊強度本文比其它方法分別要低36.8%，45.5%，49.3%，本文方法最為優(yōu)越，對關鍵節(jié)點識別也最為準確。綜合上述分析，本文方法考慮網絡級聯效應影響進行關鍵節(jié)點識別，較其它傳統不考慮級聯效應影響的方法更為準確，更為貼合網絡實際情況，本文的關鍵節(jié)點識別方法在不同拓撲結構網絡中均具有較高的準確性，能較好地適用，本文改進人工魚群算法的策略也有效地提高了算法的性能。

5 結束語

如何更準確地尋找網絡關鍵節(jié)點，對提高網絡穩(wěn)定性，預防網絡大規(guī)模故障至關重要。本文一方面引入網絡級聯失效模型，在分析網絡性能時，考慮節(jié)點級聯失效以貼近網絡的實際情況；另一方面改進人工魚群算法，使得采用優(yōu)化理論進行關鍵節(jié)點識別時更為高效準確。通過在不同類型拓撲結構網絡與實際網絡上進行實驗與分析，驗證了本文關鍵節(jié)點識別方法的有效性和優(yōu)越性。