基于節點冗余容量動態控制的復雜網絡魯棒性研究

張 震 劉迪洋 張 進 謝記超

①(戰略支援部隊信息工程大學 鄭州450000)

②(網絡通信與安全紫金山實驗室 南京210000)

1 引言

隨著復雜網絡在電力網絡、通信網絡、交通網絡和互聯網等領域的廣泛應用，復雜網絡的分析和研究越來越受到人們的重視，其中一個重要領域是研究網絡部分節點失效對其拓撲結構和服務功能的影響，即網絡魯棒性[1]。級聯失效場景下的網絡魯棒性是該領域的核心問題，當網絡中某個節點失效后，失效節點的負載將重新分配至其鄰居節點并引發下一輪失效，此種網絡連鎖失效反應稱為級聯失效[2]。

當前級聯失效下的網絡魯棒性研究主要從級聯失效模型和魯棒性優化策略兩方面進行。級聯失效模型方面，Motter和Lai[3]假設網絡上節點的負載和容量呈線性關系，提出了著名的ML(Motter-Lai)模型，但ML模型與真實網絡流量特征不完全相符。文獻[4]對ML模型進行改進，提出節點初始負載越大，獲得的額外冗余資源應當越多。文獻[5]進一步引入了反映節點承受額外負載能力的超載系數，以及描述負載重分配后節點所承擔負載的剩余系數和失效概率參數，建立了更接近實際網絡級聯失效的動態模型。文獻[6]引入本地分配比例系數，利用節點的度和失效節點負載分布范圍作為負載重分配參數，并提出基于節點承載能力的級聯失效模型。文獻[7]針對相依網絡的級聯失效過程，建立級聯失效模型并提出一種擇優恢復的魯棒性優化方法。魯棒性優化策略方面，主要通過調整負載重分配策略抵抗級聯失效，文獻[8]基于復雜網絡理論提出一種針對編隊電磁網絡的魯棒性優化方法。文獻[9]提出大負載節點應該承擔更多的重分配負載。文獻[10]跟蹤了節點的實時負載狀態，并將相鄰節點的狀態作為一個重要的指標來改進經典的重分配方法，文獻[11]將節點失效視為一個過程，根據當前失效容量確定節點所需冗余容量，提出將失效節點所屬的冗余容量重分配至其鄰居節點的重分配機制，并引入網絡相變的概念對級聯失效過程進行分析。

綜上，當前針對級聯失效的魯棒性優化策略研究仍主要集中在重分配策略方面，而從節點冗余容量設置的角度，由于網絡被攻擊強度的不同和級聯失效過程中網絡拓撲結構的變化，不同節點在不同時刻對冗余容量的需求是不同的。因此，針對傳統級聯失效模型中冗余參數固定不變的問題，本文建立了基于節點冗余容量動態控制的(Dynamic control of node Redundancy Capacity,DRC)級聯失效模型，與傳統模型相比，DRC模型可以根據攻擊強度和網絡拓撲的變化動態地確定節點所需的冗余容量。此外，本文引入網絡相變臨界因子的概念，用于判斷DRC模型中節點失效后在其鄰居節點處引發級聯失效的可能性，并基于網絡相變臨界因子與網絡魯棒性的關系提出了兩種網絡魯棒性優化策略。最后，通過仿真實驗驗證了DRC模型和本文所提策略對魯棒性優化的有效性。

2 DRC級聯失效模型

2.1 初始負載

節點負載是指節點在某一時刻處理的信息數量，反映了節點處理信息的能力。基于ML模型，節點j初始時刻的負載Lj是關于節點度的冪函數，定義為[3]

其中，k j是節點j的度，τ是初始負載調節參數，τ>0。節點度越大，初始負載越大。

2.2 節點容量

節點容量是指節點所能處理的最大負載。ML級聯失效模型中，節點j的容量Cj與其初始負載成正比，定義為[3]

其中，α是 節點j的冗余參數，α≥0。如前文所述，不同網絡狀態下節點對冗余容量的需求不同，因此本文設置節點冗余容量控制函數對冗余容量進行“動態控制，按需分配”。因此，DRC模型中節點容量定義為

其中，αj是節點冗余容量控制函數。基于文獻[11]對于失效容量的定義，從外部因素考慮，節點在每次攻擊過程中受到不同程度的損壞直至失效，這一過程中節點對冗余容量的需求隨攻擊強度變化而變化；從內部因素考慮，級聯失效過程中網絡拓撲的變化，節點所承擔負載在整個網絡中的比例即發生變化。因此，將αj描述為由攻擊強度μ，初始負載與節點平均負載的比值共同決定的函數

其中，μ為攻擊強度，μ>0。

2.3 負載重分配

基于ML模型，DRC模型的負載重分配基于節點負載。節點j失效后，重分配至節點i的負載量?L i定義為

其中，Γ是節點j的功能正常的鄰居節點集合。當負載重分配發生后，如果節點i原有負載與收到的負載之和超過其容量，將導致節點i級聯失效，其負載將再次重分配。這個過程會一直重復，直至網絡中無過載節點。

3 網絡相變臨界因子與網絡魯棒性

3.1 網絡相變臨界因子θ

借鑒物理學中相變的概念，本文將部分節點失效后引發的級聯失效定義為網絡相變，網絡相變臨界狀態則是網絡在級聯失效發生前一刻，失效節點的鄰居節點所處的狀態。

假設節點i在接收失效節點j的部分負載后，網絡處于相變臨界狀態。此時節點i維持正常功能所需要的臨界容量為C ic。臨界容量的需求越大，節點i處越容易引發級聯失效。將臨界容量Cic定義為[11]

3.2 網絡相變因子與網絡魯棒性的關系

網絡魯棒性的評價指標用于量化評價網絡魯棒性的強弱。本文采用剩余網絡最大連通子圖(largest connected subgraph)規模作為網絡魯棒性評價指標，這一測度標準在網絡魯棒性研究中應用廣泛[12]，其定義為

其中，N是初始時刻網絡的總節點數，N′是級聯失效過程結束后網絡中最大連通子圖的規模。R越小，級聯失效的傳播規模越大，網絡魯棒性越弱；反之，R越大，級聯失效的傳播規模越小，網絡魯棒性越強。

根據式(6)，臨界容量C ic與 相變臨界因子θ成正比。當網絡相變因子θ逐漸減小，在節點i處引發級聯失效的可能也逐漸減小，攻擊引起的網絡拓撲變化逐漸遠離網絡相變臨界狀態，僅遭受到攻擊的部分節點會失效，剩余節點數N′增多，網絡魯棒性R逐漸增大；反之，當網絡相變因子θ逐漸增大，臨界容量C ic逐漸增大，此時在節點i處引發級聯失效的可能逐漸增大，攻擊引起的網絡拓撲變化逐漸靠近或突破網絡相變臨界狀態，從而引發網絡相變導致更多節點失效，剩余節點數N′減少，網絡魯棒性R逐漸減小直至趨近于0。因此網絡魯棒性R與網絡相變臨界因子θ負相關。

4 網絡相變臨界因子θ 解析與網絡魯棒性提升策略

4.1 BA無標度網絡模型

Barabasi和Albert基于冪率分布產生的增長和優先連接特征提出BA(Barabasi-Albert)無標度網絡[13]。BA模型中，初始連通網絡中包含m0個節點，每次向網絡中添加一個新的節點并以一定概率連接到m個已存在的節點上(m

為了更普遍地反映無標度網絡的拓撲特性，其度分布函數可寫成

其中，c,λ為常數。

4.2 BA模型網絡中相變臨界因子θ 解析

為分析不同網絡參數與相變臨界因子θ的關系，結合BA網絡的度分布函數對θ進行解析。由文獻[11]有

將式(14)、式(16)代入式(9)，在BA網絡中采用DRC模型時有

根據式(17)、式(18)，目標網絡中，拓撲參數λ，網絡規模N和節點最小度m為確定參數，因此ML模型下決定節點失效是否會引發級聯失效的因素包括冗余參數α，被攻擊節點的度kj和初始負載參數τ,DRC模型下則為攻擊強度μ，被攻擊節點度k j和初始負載參數τ。

4.3 網絡魯棒性提升策略

由3.2節分析，網絡魯棒性R與網絡相變臨界因子θ為負相關關系，則θ與τ正相關時，魯棒性R與τ負相關；當θ與τ負相關時，魯棒性R與τ正相關。因此，本文考慮通過調整參數τ減小網絡相變臨界因子θ即網絡發生級聯失效的可能性，從而達到提升網絡魯棒性的目的。因此，本文提出兩種情況下的網絡魯棒性提升策略：

θ與τ正相關：減小參數τ減小級聯失效可能性。

θ與τ負相關：增加參數τ減小級聯失效可能性。

下面對本節所提的魯棒性提升策略的可行性進行分析：

理論可行性：根據式(17)、式(18)，根據被攻擊節點度k j不同，θ與τ存在正相關區間也存在負相關區間。因此，本文所提通過調整參數τ控制網絡相變臨界因子θ的變化，從而提升網絡魯棒性的策略理論上是可行的。

技術可行性：傳統網絡中難以實現冗余動態分配，而虛擬化技術的出現使動態冗余成為可能，虛擬化技術能夠動態組織多種計算資源，隔離硬件體系結構和軟件系統之間的緊密依賴關系，實現透明化的可伸縮計算系統架構，為實現不同時刻根據不同節點的冗余資源需要進行重新規劃與分配提供了技術基礎。因此，本文所提魯棒性提升策略在技術上是可行的。

5 實驗驗證

為了驗證本文所提的DRC模型及魯棒性提升策略對網絡魯棒性提升的有效性，分別在BA網絡和ARPA網絡中進行仿真實驗。本文實驗平臺為Intel(R)Core(TM)i7-4790 CPU@3.60 GHz計算機和PyCharm 2019 Community。

5.1 BA網絡

利用BA網絡模型生成實驗網絡，相關參數設置為：網絡規模N=100，初始網絡包含節點數m0=10，每次新增連邊的數目m=2。

首先分析BA網絡中相變臨界因子θ與初始負載參數τ之間的關系。采用ML模型時如圖1(a)所示，所有曲線相交于(1,1.25)，當0 <τ<1，θ隨kj增大而減小；當1<τ<10，θ隨kj增大而增大。采用DRC模型時如圖1(b)所示，隨著τ的增加，θ逐漸收斂至1。所有曲線相交于(0.7,1.18)，當0 <τ<0.7,θ隨kj增大而減小；當 0.7<τ<10,θ隨kj增大而增大。兩種模型下，當被攻擊節點的度k j較大時，θ會先增加再減少；當被攻擊節點度kj較小，θ單調減少。實驗結果表明，根據被攻擊節點度k j的不同，增加或減小負載強度τ可以控制網絡相變臨界參數θ的魯棒性優化策略是可行的。

BA網絡采用ML模型時，網絡相變臨界因子θ與冗余參數α之間的關系如圖2所示，隨著α的增加，θ不斷增加；當α相同時，θ隨kj增大而減小。實驗結果表明，為網絡中所有節點增加冗余容量的策略并不能很好地抵抗級聯失效。采用DRC模型時，θ與攻擊強度μ之間的關系如圖3所示，當0<μ<2.2時 被攻擊節點度kj越大，θ越大；μ>2.2時被攻擊節點的度k j越小，網絡相變臨界因子θ越大。隨著攻擊強度μ增加，θ逐漸增加，實驗結果表明本文對于動態控制函數αj的設置是完全合理的。

圖1 BA網絡中θ 隨τ 變化圖

圖2 BA網絡ML模型中θ 隨α 變化圖

最后分析BA網絡中魯棒性R與θ之間的關系，ML模型和DRC模型下實驗結果分別如圖4(a)、圖4(b)所示，當θ相同時，被攻擊節點度kj越大，網絡魯棒性越弱，這是因為BA網絡的無標度特性，移除高度關鍵節點后對網絡破壞較大。對比圖4(a)與圖4(b)，被攻擊節點度kj相同時ML模型下R值較小，表明DRC模型對于網絡魯棒性的提升是有效的。

圖3 BA網絡DRC模型中θ 隨μ 變化圖

當網絡規模N=50，其余參數不變時，當節點10失效后，不同模型下的級聯失效的傳播范圍如圖5所示，其中灰色節點表示失效節點，β=1,τ=0.2,α=0.25。

由圖5可知，ML模型下級聯失效過程結束后最終失效節點數量為23，而DRC模型下最終失效節點數量為16，失效節點數量減少30.43%。因此，DRC模型對于減小級聯失效傳播范圍，提升網絡魯棒性是有效的。

圖4 BA網絡中R 隨θ 變化圖

圖5 BA網絡ML模型與DRC模型失效傳播對比圖

5.2 ARPA網絡

ARPA網絡是一種主干網絡拓撲，由21個節點和23條連接組成。其網絡拓撲如圖6所示。

首先分析ARPA網絡中θ與τ之間的關系。采用M L 模型時如圖7(a)所示，所有曲線相交于(1.05,1.5)，當0 <τ<1.05，θ隨kj增大而減小；當1.05<τ<5，θ隨kj增大而增大。采用DRC模型時如圖7(b)所示，所有曲線相交于(0.9,1.75)，當0<τ<0.9，θ隨kj增大而減小；當 0.9<τ<5，θ隨k j增大而增大。兩種模型下，當被kj為3或4時θ單調增大，當kj=2時θ單調減小。與圖1相比，θ的值均較大，這是因為ARPA網絡中度為3或4的節點占了相當的比例并且分布在拓撲中的重要位置，失效后引發級聯失效的概率更高。

圖6 ARPA網絡拓撲

圖7 ARPA網絡中θ 隨τ 變化圖

ARPA網絡采用ML模型時，相變臨界因子θ與冗余參數α之間的關系如圖8所示，實驗結論與BA網絡中相同。采用DRC模型時，θ與攻擊強度μ之間的關系如圖9所示，當0 <μ<0.79時，kj隨網絡相變臨界因子θ增大而增大；當μ>0.79時，k j越大，θ越小。這些結論與BA模型網絡中的表現是一致的，也進一步驗證了本文所提模型的正確性。

最后分析ARPA網絡中魯棒性R與θ之間的關系。ML模型和DRC模型下實驗結果分別如圖10(a)、圖10(b)所示，網絡相變臨界因子θ與網絡魯棒R負相關。相同θ條件下，被攻擊節點度kj越大，網絡魯棒性越差。對比圖6(a)與圖6(b)，被攻擊節點度相同時，ML模型下網絡魯棒性值較小。ARPA網絡魯棒性R與θ之間的關系與圖7中BA網絡魯棒性R與θ之間的關系一致，進一步驗證了DRC模型在真實網絡中的有效性。

在ARPA網絡拓撲下，當節點3失效后，不同模型下的級聯失效的傳播范圍如圖11所示，其中，τ=0.2,α=0.2。由圖11可知，ML模型下級聯失效導致網絡中全部節點失效，而DRC下最終失效節點數量為8，失效節點數量減少61.9%。因此，進一步驗證了DRC模型在真實網絡中減小級聯失效傳播范圍，提升網絡魯棒性的有效性。

6 結束語

研究外部攻擊條件下網絡拓撲的動態演化過程，提出復雜網絡魯棒性提升策略，具有重要的理論和現實意義。本文針對傳統的級聯失效模型冗余參數固定的問題，提出了節點冗余容量動態控制的思路，主要工作有：

(1)考慮網絡攻擊強度與失效過程中網絡拓撲的動態變化提出節點冗余容量控制函數，通過這一方法動態地確定節點所需冗余容量，并建立了DRC級聯失效模型。

圖8 ARPA網絡ML模型中θ 隨α 變化圖

圖9 ARPA網絡DRC模型中θ 隨μ 變化圖

圖10 ARPA網絡中R 隨θ 變化圖

圖11 APRA網絡ML模型與DRC模型失效傳播對比圖

(2)引入網絡相變臨界因子θ，可衡量節點失效后在其鄰居節點處引發級聯失效的概率，根據無標度網絡的度分布函數分別推導了ML模型和DRC模型下中網絡相變臨界因子表達式，并給出相應網絡魯棒性提升策略。

(3)針對模型網絡與真實網絡進行了級聯失效仿真實驗，分析了攻擊強度和節點負載等參數對網絡相變臨界因子和網絡魯棒性的影響，驗證了本文所提網絡魯棒性提升策略和DRC模型應對級聯失效的有效性。

下一步的工作是研究邊增加動態控制下網絡拓撲變化過程與網絡魯棒性。