李一剛，王向東

（沈陽工業(yè)大學 信息科學與工程學院，遼寧 沈陽110870）

持續(xù)攻擊下的無標度網(wǎng)絡修復策略研究

李一剛，王向東

（沈陽工業(yè)大學 信息科學與工程學院，遼寧 沈陽110870）

針對隨網(wǎng)絡演化的持續(xù)性攻擊，并且節(jié)點不可修復的情況，本文提出了一種加入限制參數(shù)的連邊補償修復方法。通過仿真實驗驗證了這種修復策略能夠保證網(wǎng)絡在演化過程中一直保持較好的連通性，能夠保證網(wǎng)絡中有百分之八十五以上的節(jié)點保持聯(lián)通。并且在網(wǎng)絡進行修復之后，不改變網(wǎng)絡的無標度結構特性。

復雜網(wǎng)路；無標度網(wǎng)絡；持續(xù)性攻擊；攻擊策略；修復策略

隨著復雜網(wǎng)絡的研究和發(fā)展，現(xiàn)今很多領域上的網(wǎng)絡都可以看作是復雜網(wǎng)絡。比如：internet網(wǎng)絡[1]，電力系統(tǒng)網(wǎng)絡[2]，交通網(wǎng)絡[3]，軍事網(wǎng)絡[4]，自然網(wǎng)絡[5]，社會關系網(wǎng)絡[6]，生物網(wǎng)絡[7]等。這些網(wǎng)絡在各個領域中都起著十分重要的作用，因此對這些網(wǎng)絡的研究十分必要。

在現(xiàn)實中的網(wǎng)絡，大多為無標度網(wǎng)絡。在無標度網(wǎng)絡中，大多數(shù)的節(jié)點只有少量的連接度，而少數(shù)節(jié)點擁有大量的連接度。由于這種無標度網(wǎng)絡的這種無標度特性，使得其對于隨機的攻擊有一定的抗毀性，但是對于蓄意有針對性的攻擊十分脆弱[8]。一旦針對無標度網(wǎng)絡發(fā)起了蓄意的攻擊，將會對網(wǎng)絡的連通性造成極大的損傷。因此對無標度網(wǎng)絡在蓄意攻擊下的修復策略研究十分必要。目前對復雜網(wǎng)絡的修復研究，大多都是基于被攻擊節(jié)點可修復的情況進行修復的[9-15]。這些研究將不同領域中的網(wǎng)絡抽象為復雜網(wǎng)絡，將修復人員及資源抽象為網(wǎng)絡的修復因子，并且按照一定的策略分配，得出每個節(jié)點被修復的概率，從而按照這種概率對網(wǎng)絡進行修復。其中的分配策略大致可分為平均分配策略和按照度進行重點分配的策略，并且得到了不同的修復效果。

需要注意的是，以上的修復策略都是在被攻擊節(jié)點可修復的情況下修復的。然而在實際中，有很多被攻擊節(jié)點不可被修復或者被攻擊斷掉的連邊不可修復的情況。比如：攻擊強度大，使得被攻擊節(jié)點被摧毀；資源不冗余，無法調配多余的資源對故障節(jié)點進行修復；節(jié)點的修復需要較長的修復時間周期，針對故障節(jié)點修復無法立刻恢復網(wǎng)絡連通性。在諸如此類的情況下，如果無法及時的恢復網(wǎng)絡的連通性或功能，將會造成極大的影響和危害。所以，研究被攻擊節(jié)點無法被修復的情況下的修復策略是有意義的。對網(wǎng)絡的攻擊除了一次性的攻擊以外，還可能是持續(xù)的。這種持續(xù)可以是隨著復雜網(wǎng)絡演化同時進行的，長期的攻擊。比如，對交通網(wǎng)絡進行攻擊，炸毀了其主要的交通線路，并在交通網(wǎng)絡演化了一定時間后，再次攻擊。這種攻擊顯然是持續(xù)的，并且被攻擊的目標不容易被修復。針對這種攻擊方式，本文研究了無標度網(wǎng)絡，在隨著網(wǎng)絡演化課持續(xù)的攻擊下，被攻擊節(jié)點無法進行修復時的修復策略。除此之外，本文還研究了在本文的修復策略下，修復后的網(wǎng)絡的無標度特性以判斷修復后的網(wǎng)絡是否還有攻擊前網(wǎng)絡的結構特點。

1 攻擊模型

1.1 初始網(wǎng)絡

文中的初始網(wǎng)絡是由n個節(jié)點構成的無標度網(wǎng)絡。該網(wǎng)絡是不斷演化的，每次演化網(wǎng)絡中加入一個新節(jié)點。這個新節(jié)點根據(jù)網(wǎng)絡中原有節(jié)點的度，擇優(yōu)建立m條連邊。式（1）表示了這種擇優(yōu)策略：

其中，P（i）為第 i個節(jié)點被選中的概率；k（i）為網(wǎng)絡中第i個節(jié)點的度；K為網(wǎng)絡中所有節(jié)點度之和。

1.2 攻擊策略

文中的攻擊策略是持續(xù)性的，蓄意的攻擊。被攻擊的節(jié)點將斷掉一部分邊，并且這些連邊無法被重新修復。對網(wǎng)絡的攻擊隨著網(wǎng)絡的演化同時進行，網(wǎng)絡每演化一步，都根據(jù)概率r來判斷是否進行攻擊。每一次攻擊會攻擊x個節(jié)點，其中x是（0，X]中的隨機整數(shù)。對于每一個被攻擊的節(jié)點，會有一個攻擊成功的概率r’。每一個被成功攻擊的節(jié)點，都會斷掉一部分邊。本文中，這個被攻擊斷的邊的比例設定在[0.5，1]，也就是說，被攻擊的節(jié)點最少斷掉其原有連邊的一半，最多則斷掉了其原有的所有連邊。

1.3 修復策略

由于本文中的攻擊是不可修復的，因此，因攻擊而斷掉的邊沒有重新連接的可能。針對這種情況，本文采用的是連邊補償?shù)姆椒ǎ幢还艄?jié)點連接的相鄰節(jié)點，與網(wǎng)絡中的其他節(jié)點建立新的連邊。本文中用網(wǎng)絡中最大子網(wǎng)絡的節(jié)點個數(shù)和整個網(wǎng)絡所有節(jié)點個數(shù)的比值來表示最大連通子圖在網(wǎng)絡中所占的比例，從而用來評價網(wǎng)絡的連通性。這里需要考慮的是，如果每一次修復，令被攻擊節(jié)點的原所有相鄰節(jié)點都建立新的連邊，會造成過度修復，在實際中可能會造成資源的浪費或者由于資源不足根本無法實現(xiàn)。因此，本文中提出了兩個體現(xiàn)網(wǎng)絡結構特征的限制參數(shù)，來作為網(wǎng)絡修復的標準。這兩個參數(shù)分別為：

1） M=Max（k）/L；

2） LCG=lcg/L；

其中，Max（k）代表在攻擊發(fā)生之前，網(wǎng)絡中最大節(jié)點度，lcg表示當前狀態(tài)下，網(wǎng)絡中最大連通圖所含有的節(jié)點個數(shù)。L表示網(wǎng)絡中所有連邊的數(shù)量。以這兩個比值作為體現(xiàn)網(wǎng)絡結構狀態(tài)的標準，并按照不超過這個標準的強度進行修復。這兩個參數(shù)分別代表了網(wǎng)絡中最大度數(shù)和最大連通圖節(jié)點個數(shù)與網(wǎng)絡中連邊數(shù)量之間的比值關系。因為本文中的修復策略是利用建立新的連邊的方法進行補償?shù)?，所以過度修復也就是說建立了過多條的新連接邊。當M或LCG較小時，說明L相對較大，即網(wǎng)絡中的連邊偏多。因此在修復時，只有在現(xiàn)在的此時的M和LCG值大于標準值時，才進行修復，用這種方法來避免過度修復。并且本文通過仿真還發(fā)現(xiàn)，加了這兩個參數(shù)的修復策略還可以使得修復后的網(wǎng)絡與原網(wǎng)絡有同樣的無標度特性。

具體的修復步驟如下：

1）由10個全連通的初始節(jié)點，按照無標度網(wǎng)絡的演化機制，生成初始的無標度·1網(wǎng)絡，含有n個節(jié)點，并計算此時的M值。網(wǎng)絡如果在不受到攻擊的情況下，LCG會趨于一個定值，因為在不受攻擊的情況下，根據(jù)無標度網(wǎng)絡的擇優(yōu)演化機制，網(wǎng)絡在節(jié)點數(shù)足夠多時，會達到全連通的狀態(tài)。設每次網(wǎng)絡增加m條邊，則當演化到節(jié)點數(shù)足夠多時，因此，LCG會隨著網(wǎng)絡演化趨于一個定值。這里將所研究的網(wǎng)絡中的這個定值記作LCG。將M和LCG作為之后網(wǎng)絡修復的標準；

2）網(wǎng)絡開始演化，每次演化增加一個新的節(jié)點，并根據(jù)網(wǎng)絡中節(jié)點的度擇優(yōu)建立m條新的連邊，設網(wǎng)絡中第i個節(jié)點度為k（i），K為網(wǎng)絡中所有節(jié)點度之和，則節(jié)點被選中建立新連邊的概率為P（i）=k（i）/k；

3）在演化的同時，按照概率r來判斷是否發(fā)生攻擊。若發(fā)生攻擊，則在（0，X]區(qū)間內選取隨機整數(shù)x，并按照節(jié)點度由高到低選取x個節(jié)點進行攻擊。對每個節(jié)點的攻擊會按照概率r’來判斷攻擊是否成功。若攻擊成功，被選中的節(jié)點會被攻擊斷掉一部分比例的邊并且無法修復，這個比例本文中選取[0.5，1]之間的隨機值；

4）當攻擊發(fā)生時，立即進行修復。修復時，被攻擊節(jié)點的相鄰節(jié)點中，失去邊的相鄰節(jié)點依次進行修復。 比如，被攻擊節(jié)點為 N（i），其相鄰節(jié)點為 N（1），N（2），N（3）…，攻擊后，N（1），N（2），N（3）與 N（i）的連邊被切斷，此時對 N（1），N（2），N（3）依次進行修復。每次修復前計算當前的M值記作M’，以及當前網(wǎng)絡的LCG值，記作LCG’。當此時的網(wǎng)絡同時滿足M’＞M和LCG’＞LCG時，給被修復節(jié)點擇優(yōu)建立一條新的連邊，擇優(yōu)策略同上文提到的已節(jié)點度高低作為標準的擇優(yōu)策略。該節(jié)點修復完成后，對下一個失去邊的相鄰節(jié)點進行同樣的判斷和修復過程，直至所有失去變得相鄰節(jié)點都判斷和修復完成；

5）網(wǎng)絡每次演化都會判斷是否進行攻擊，以及攻擊后是否進行修復，當網(wǎng)絡演化為N個節(jié)點的網(wǎng)絡時，演化結束。

1.4 網(wǎng)絡結構特性研究

文中的無標度網(wǎng)絡修復策略研究，在以提高網(wǎng)絡連通性為目標的同時，還兼顧了網(wǎng)絡的結構特征。無標度網(wǎng)絡的度分布對于高度數(shù)服從冪律分布，即：p（k）=λk-α。 其中 λ 為比值系數(shù)，k 為節(jié)點的度，α 為冪律分布指數(shù)，p（k）為節(jié)點度為k的概率?？梢钥闯?，無標度網(wǎng)絡的冪律分布中，α是網(wǎng)絡結構特性的表征，現(xiàn)實網(wǎng)絡中，不同的無標度網(wǎng)絡因其現(xiàn)實意義不同，α值也不完全相同。本文的研究為保證該修復在提高網(wǎng)絡連通性的同時還可以保證網(wǎng)絡的結構特征還符合修復前的網(wǎng)絡。因此研究了在這種修復策略下，α值是否與原網(wǎng)絡α值相近。

2 仿真分析

文中以演化的無標度網(wǎng)絡為研究對象，對網(wǎng)絡進行與網(wǎng)絡演化同時的持續(xù)性蓄意攻擊，使用連邊補償?shù)男迯筒呗赃M行了仿真實驗。

初始網(wǎng)絡為n=100的無標度網(wǎng)絡，每演化一次，加入一個新節(jié)點并擇優(yōu)建立兩條新的連邊，即m=2，因此LCG=1/m=0.5。發(fā)生攻擊的概率為r=0.5，每次攻擊節(jié)點的個數(shù)x為（0，5]的隨機整數(shù)，對每個目標節(jié)點攻擊的成功概率r’設為0.4。每一個被成功攻擊的目標節(jié)點都會按照隨機比例切斷一些連邊，這個比例是在[0.5，1]內隨機選取。修復策略則與上文所述相同。用網(wǎng)絡最大連通圖即最大連通圖的節(jié)點個數(shù)與網(wǎng)絡中總節(jié)點個數(shù)的比值來描述修復的效果。圖1為不加修復策略，網(wǎng)絡演化受到攻擊時的仿真結果圖。

圖1 無修復策略網(wǎng)絡連通性仿真圖

其中，橫坐標為隨著網(wǎng)絡演化，網(wǎng)絡的總節(jié)點的個數(shù)，縱坐標為最大連通圖所含節(jié)點個數(shù)與總節(jié)點個數(shù)的比值。

圖2為加入本文的修復策略之后，修復效果圖。

圖2 有修復策略的網(wǎng)絡修復效果圖

可以看出，在不加修復的情況下，這種攻擊會是網(wǎng)絡的連通性受到較大的破壞，并且有較大的波動；但是在本文的修復策略下，網(wǎng)絡的連通性得到了較大的提升，并且相對穩(wěn)定。

無標度網(wǎng)絡的度分布對于高度數(shù)的節(jié)點滿足冪律分布，即 p（k）=λk-α。 現(xiàn)將其兩邊取對數(shù)，得：lnp=lnλ-αlnk。這表明，將p作為縱坐標，k作為橫坐標，在雙對數(shù)坐標系下，高度數(shù)節(jié)點的度分布曲線應該是近似一條直線的。其中-α為其斜率。因此，我們對網(wǎng)絡在遭受的攻擊前的度分布曲線和在遭受攻擊并按照文中的修復策略進行修復后的度分布曲線進行了仿真分析，得出圖3；對網(wǎng)絡在遭對網(wǎng)絡在遭受的攻擊前的度分布曲線和在遭受攻擊但是修復策略中沒有引入兩個限制參數(shù)（L和LCG）的度分布曲線進行仿真分析，得出圖4。

圖3 含限制參數(shù)的度分布曲線

圖4 無限制參數(shù)的度分布曲線

其中，橫坐標為k，縱坐標為p（k）。因為對于高度數(shù)的節(jié)點，這種冪律分布是近似的，所以在雙對數(shù)坐標下的曲線也只能是近似直線。曲線1為在攻擊發(fā)生前，原初始無標度網(wǎng)絡的度分布曲線，圖3中的曲線2為在網(wǎng)絡隨著演化承受攻擊并按照本文的策略修復下的度分布曲線，圖4中的曲線2為在網(wǎng)絡隨著演化承受攻擊但是修復策略中沒有引入限制參數(shù)（M和LCG）的度分布曲線。

圖3中，若將量曲線高度數(shù)的部分近似看作直線，則兩條曲線的斜率很接近，可以認為網(wǎng)絡的結構特性沒有改變；圖4中，兩條近似直線的斜率則相差很多，可以認為網(wǎng)絡的結構特性發(fā)生了變化?？芍?，加入了兩種限制參數(shù)，除了可以避免過修復，還可以保證修復后的網(wǎng)絡與原網(wǎng)絡具有幾乎同樣的無標度特性。

3 結 論

文中提出了在演化的蓄意攻擊下，利用連邊補償并引入限制參數(shù)的修復策略通過仿真實驗，可知該策略可以有效的提高網(wǎng)絡的連通性并且不改變原網(wǎng)絡的無標度特性。在不加修復的情況下，網(wǎng)絡的連通性可被攻擊最低達到0.4左右，并且最大連通圖比值不穩(wěn)定；在加入修復后，可使網(wǎng)絡的連通性提升，使其最低也可達到0.85左右，并且可以保證整個過程網(wǎng)絡連通的穩(wěn)定性。另外在修復后，通過雙對數(shù)坐標下的度分布曲線可看出，該加入了限制參數(shù)M和LCG的修復策略不改變網(wǎng)絡的無標度結構特點。這表明這種修復策略不僅有理論意義，還有一定的實際價值。

[1]Gan C，Yang X，Liu W，et al.Propagation of computervirusboth acrossthe Internetand external computers:A complex-network approach[J]. Communications in Nonlinear Science&Numerical Simulation，2014，19（8）:2785-2792.

[2]TIAN Xu，JIE Chen，YUE He，etal，Complex network propertiesofchinese powergrid[J].International Journal of Modern Physics B，2012，18（17-19）:2599-2603.

[3]Hu MB，Ling X，Jiang R，et al.Dynamical hysteresis phenomena in complex network traffic[J].Physical Review E Statistical Nonlinear&Soft Matter Physics，2009，79（4 Pt 2）.

[4]XU Yu-Zhang，L Zhu，L Zhang.Information diffusion model of military communication network based on complex network theory[J].Journal of Military Communications Technology，2015.

[5]SM Shekatkar，G Ambika.Complex networks with scale-free nature and hierarchical modularity[J].European Physical Journal B，2015，88（9）:1-7.

[6]M Williams，J Burry，A Rao.Understanding social behaviors in the indoor environment:a complex network approach[J].Acadia Design Agency，2014:671-680.

[7]Yeh，Trai-Ming，Chuang，Yung-Chun.Multiobjective identification of controlling areas in neuronal Networks[J].IEEE/ACM Transactions on Computational Biology&Bioinformatics，2013，10（3）:708-720.

[8]劉滌塵，冀星沛，王波，等.基于復雜網(wǎng)絡理論的電力通信網(wǎng)拓撲脆弱性分析及對策 [J].電網(wǎng)技術，2015，39（12）:3615-3621.

[9]胡斌，黎放.多種攻擊策略下無標度網(wǎng)絡修復策略[J].系統(tǒng)工程與電子技術，2010，32（1）:86-89.

[10]劉中華，胡兵，吳榮華.基于修復策略的艦艇編隊復雜網(wǎng)絡系統(tǒng)可靠性研究 [J].計算機科學，2012，39（6A）：139-141.

[11]狄鵬，黎放，胡斌.網(wǎng)絡中心戰(zhàn)模型修復策略研究[C]//Proceedings of International Conference on Broadcast Technology&Multimedia Communication，2010.

[12]王甲生，吳曉平，陳澤茂，等.修復策略下典型拓撲結構復雜網(wǎng)絡抗毀性研究[J].海軍工程大學學報，2015，27（4）：75-79.

[13]蔣勇，趙作鵬.多屬性加權模糊貝葉斯的復雜網(wǎng)絡故障自修復技術[J].計算機應用研究，2015，32（8）:2378-2381.

[14]王正武，周振宇，胡靜.基于節(jié)點修復效果的故障路網(wǎng)修復策略[J].長沙理工大學學報：自然科學版，2014，11（4）:25-31.

[15]鄭力明，李曉冬，羅建祿，等.復雜網(wǎng)絡中修復策略研究[J].電子設計工程，2014，22（2）:140-142.

A repair strategy for scale-free network under the progressive intentional attack

LI Yi-gang，WANG Xiang-dong
（School of Information Science and Engineering，Shenyang University of Technology，Shenyang 110870，China）

To repair the scale-free network under the progressive and intentional attack which the attacked nodes and links couldn't be repaired，in this paper we propose a repair strategy base on the link compensation method with the limit parameters.We show this kind of repair strategy could keep the network has a stable connectivity.It could keep over 85%of the network nodes connected.Beyond that，this kind of repaired strategy won't change the scale-free structural characteristic of the primary network before attack and repair.

complex networks； scale-free networks； progressive attack； repair strategies

TN91

A

1674－6236（2017）17-0181-04

2016-07-16稿件編號：201607120

李一剛（1992—），男，朝鮮族，朝鮮人，碩士研究生。研究方向：復雜網(wǎng)絡。