鄭力明，李曉冬，羅建祿，韓貴杰

（1.武警警官學(xué)院 電子技術(shù)系，四川 成都 610213；2.武警警官學(xué)院 科研部，四川 成都 610213）

現(xiàn)實世界中的各種復(fù)雜網(wǎng)絡(luò)，如社會網(wǎng)絡(luò)（朋友關(guān)系網(wǎng)絡(luò)、合作網(wǎng)絡(luò)）、技術(shù)網(wǎng)絡(luò)（Internet、電力網(wǎng)）、生物網(wǎng)絡(luò)（神經(jīng)網(wǎng)絡(luò)、食物鏈網(wǎng)絡(luò)）等[1-3]，已在人類社會生活中扮演著越來越重要的角色。然而復(fù)雜網(wǎng)絡(luò)結(jié)構(gòu)屬性的不同可能在網(wǎng)絡(luò)中節(jié)點出現(xiàn)故障后引起拓撲結(jié)構(gòu)的極大變化，甚至是整個復(fù)雜網(wǎng)絡(luò)的癱瘓，因此如何提高復(fù)雜網(wǎng)絡(luò)抗毀性成為國內(nèi)外研究的重點。Albert等人[4]的研究表明，無標度網(wǎng)絡(luò)相對于隨機網(wǎng)絡(luò)，在隨機打擊條件下，前者具有更好的抗毀性，在故意打擊條件下，后者具有更好的抗毀性。盡管可以通過優(yōu)化網(wǎng)絡(luò)拓撲結(jié)構(gòu)以提高網(wǎng)絡(luò)抗毀性，但是采用此類被動防御的措施在面對頻繁密集的打擊時仍然會造成整個網(wǎng)絡(luò)的癱瘓，因此節(jié)點失效后需要盡快修復(fù)以保證網(wǎng)絡(luò)連通性。

池麗平等人[5]提出了在隨機網(wǎng)絡(luò)和無標度網(wǎng)絡(luò)中節(jié)點受到故意攻擊后的修復(fù)模型，該模型分兩步，第一步找出網(wǎng)絡(luò)中度最大的節(jié)點并將該節(jié)點與其他所有節(jié)點的連接斷開，第二步該節(jié)點以固定的概率與網(wǎng)絡(luò)中其他節(jié)點重新建立連接。通過不斷重復(fù)上述步驟以研究網(wǎng)絡(luò)的穩(wěn)定性。池麗平等人的研究結(jié)果表明在隨機網(wǎng)絡(luò)中，網(wǎng)絡(luò)的穩(wěn)定性與隨機網(wǎng)絡(luò)的平均度呈冪律分布；在無標度網(wǎng)絡(luò)中，網(wǎng)絡(luò)的穩(wěn)定性與修復(fù)概率呈指數(shù)分布。然而在實際網(wǎng)絡(luò)中，受資源限制，每個節(jié)點可被修復(fù)的概率是不同的，且總的修復(fù)能力也是有限的。

胡斌等人[6]考慮到了實際網(wǎng)絡(luò)中資源受限，并提供平均修復(fù)策略，重點修復(fù)策略和偏好修復(fù)策略以對比在不同網(wǎng)絡(luò)攻擊中的修復(fù)能力。其修復(fù)模型分兩步：第一步找出網(wǎng)絡(luò)中度最大的節(jié)點并將該節(jié)點與其他所有節(jié)點的連接斷開，第二步該節(jié)點根據(jù)修復(fù)策略所對應(yīng)的概率恢復(fù)原來的連接。對無標度網(wǎng)絡(luò)的實驗結(jié)果表明，偏好修復(fù)的魯棒性較好。然而在實際網(wǎng)絡(luò)中，節(jié)點的修復(fù)需要一定的時間，這對網(wǎng)絡(luò)的打擊效果和修復(fù)效果都會產(chǎn)生影響。

本文提出一種延遲修復(fù)的復(fù)雜網(wǎng)絡(luò)修復(fù)模型，在此基礎(chǔ)上定義了多種修復(fù)策略，最后給出在隨機打擊和故意打擊情況下各種修復(fù)策略的修復(fù)能力。

1 修復(fù)模型和修復(fù)策略

1.1 修復(fù)模型

步驟1根據(jù)打擊策略，從網(wǎng)絡(luò)中選擇一個被打擊的節(jié)點，刪除該節(jié)點與其他節(jié)點的所有連接，并對該節(jié)點的修復(fù)時間開始計時。

步驟2遍歷所有被打擊的節(jié)點，如果節(jié)點的修復(fù)時間到達T，則根據(jù)該節(jié)點的修復(fù)概率進行修復(fù)，節(jié)點修復(fù)后恢復(fù)原來的連接。

步驟3重復(fù)步驟1和步驟2。

1.2 修復(fù)策略

復(fù)雜網(wǎng)絡(luò)的修復(fù)策略事實上是指各個節(jié)點的修復(fù)因子的分配策略，由于網(wǎng)絡(luò)中的總修復(fù)因子受限，而各個節(jié)點的重要程度各不相同，在不同的打擊環(huán)境下受關(guān)注的程度也各不相同，因此通過分配有限的修復(fù)因子以提高網(wǎng)絡(luò)的抗毀性。其主要的修復(fù)策略包括：

1）平均修復(fù)（uniform strategy）：各個節(jié)點的修復(fù)因子P都相同，即P=M/N。

2 模擬測試

為了驗證各種修復(fù)策略在不同的網(wǎng)絡(luò)拓撲下的修復(fù)能力，實驗中模擬實現(xiàn)了規(guī)模為1000的隨機網(wǎng)絡(luò)和BA網(wǎng)絡(luò)兩種網(wǎng)絡(luò)拓撲，為了驗證各種修復(fù)策略應(yīng)對多種打擊情況下的修復(fù)能力，實驗中實現(xiàn)了隨機打擊和故意打擊兩種模式。另外，修復(fù)策略的修復(fù)能力以網(wǎng)絡(luò)的最大連通圖的大小為依據(jù)。實驗中，設(shè)置總的修復(fù)因子M=10，最大修復(fù)因子Pmax=1，修復(fù)時間T=10。

2.1 隨機網(wǎng)絡(luò)

圖1顯示了隨機網(wǎng)絡(luò)中對節(jié)點進行連續(xù)隨機打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強到弱依次為：均勻修復(fù)、平方根修復(fù)、比例修復(fù)、平方修復(fù)。在隨機打擊中，由于節(jié)點是隨機選擇的，因此均勻修復(fù)能夠很好的照顧到每個節(jié)點，實驗顯示網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在91%以上；在隨機網(wǎng)絡(luò)中各個節(jié)點的度服從泊松分布，因此比例修復(fù)下各個節(jié)點的修復(fù)概率差別不大，實驗顯示網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在88%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，一方面考慮了節(jié)點度對修復(fù)概率的影響，另一方面也照顧到節(jié)點的公平性，其最大強連通圖的比例穩(wěn)定在90%以上；最后平方修復(fù)是在盡量擴大節(jié)點度對修復(fù)概率的影響程度，因此在隨機選擇度較小的節(jié)點后，其修復(fù)的概率也較小，其最大強連通圖的比例穩(wěn)定在85%以上。

圖2顯示了隨機網(wǎng)絡(luò)中對節(jié)點進行連續(xù)故意打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強到弱依次為：平方修復(fù)、比例修復(fù)、平方根修復(fù)、均勻修復(fù)。在故意打擊中，每次選擇系統(tǒng)中度最高的節(jié)點，這樣均勻修復(fù)中度高的節(jié)點被修復(fù)的概率就相對較小，實驗顯示網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在86%以上；比例修復(fù)考慮了節(jié)點度對修復(fù)概率的影響，因此度高的節(jié)點被修復(fù)的概率較大，網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在92%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，其最大強連通圖的比例穩(wěn)定在89%以上；最后平方修復(fù)是在盡量擴大節(jié)點度對修復(fù)概率的影響程度，因此能夠重點保護度較高的節(jié)點，其最大強連通圖的比例穩(wěn)定在94%以上。

綜上可以看出，對于隨機網(wǎng)絡(luò)，在不確定對方的打擊模式的情況下，采用比例修復(fù)或者平方根修復(fù)能夠達到較好的修復(fù)效果，而均勻修復(fù)和平方修復(fù)則只能針對特定的一種打擊模式具有較好效果。

圖1 隨機網(wǎng)絡(luò)隨機打擊下的修復(fù)效果Fig.1 Random attack by random network repairing effect

圖2 隨機網(wǎng)絡(luò)故意打擊下的修復(fù)效果Fig.2 Intentional attack by random network repairing effect

2.2 無標度網(wǎng)絡(luò)

圖3顯示了BA網(wǎng)絡(luò)中對節(jié)點進行連續(xù)隨機打擊后各種修復(fù)策略的修復(fù)效果，其中均勻修復(fù)和平方根修復(fù)幾乎具有同樣好的修復(fù)效果，其次為比例修復(fù)，最差的是平方修復(fù)。在隨機打擊中，由于節(jié)點是隨機選擇的，因此均勻修復(fù)很好的照顧到每個節(jié)點，其最大強連通圖的比例穩(wěn)定在88%以上；在BA網(wǎng)絡(luò)中各個節(jié)點的度服從冪律分布，因此比例修復(fù)下各個節(jié)點的修復(fù)概率差別較大，實驗顯示網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在85%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，一方面考慮了節(jié)點度對修復(fù)概率的影響，另一方面也照顧到節(jié)點的公平性，其最大強連通圖的比例穩(wěn)定在87%以上；最后平方修復(fù)是在盡量擴大節(jié)點度對修復(fù)概率的影響程度，因此在隨機選擇度較小的節(jié)點后，其修復(fù)的概率會非常小，其最大強連通圖的比例隨時間一直減小。

圖4顯示了BA網(wǎng)絡(luò)中對節(jié)點進行連續(xù)故意打擊后各種修復(fù)策略的修復(fù)效果，其修復(fù)效果由強到弱依次為：平方修復(fù)、比例修復(fù)、平方根修復(fù)、均勻修復(fù)。在故意打擊中，每次選擇系統(tǒng)中度最高的節(jié)點，這樣均勻修復(fù)中度高的節(jié)點被修復(fù)的概率就相對較小，另外BA網(wǎng)絡(luò)中度高的節(jié)點對網(wǎng)絡(luò)的連通性影響很大，實驗顯示網(wǎng)絡(luò)的最大強連通圖的比例隨時間急劇減小；比例修復(fù)考慮了節(jié)點度對修復(fù)概率的影響，因此度高的節(jié)點被修復(fù)的概率較大，網(wǎng)絡(luò)的最大強連通圖的比例穩(wěn)定在88%以上；而平方根修復(fù)則是對比例修復(fù)和均勻分布的折中效果，其最大強連通圖的比例穩(wěn)定在92%以上；最后平方修復(fù)是在盡量擴大節(jié)點度對修復(fù)概率的影響程度，因此能夠重點保護度較高的節(jié)點，其最大強連通圖的比例穩(wěn)定在94%以上。

綜上可以看出，對于BA網(wǎng)絡(luò)，在不確定對方的打擊模式的情況下，采用平方根修復(fù)能夠達到較好的修復(fù)效果，其次為比例修復(fù)，而均勻修復(fù)和平方修復(fù)則只能針對特定的一種打擊模式具有較好效果。

圖3 無標度網(wǎng)絡(luò)隨機打擊下的修復(fù)效果Fig.3 Random attack by scale-free network repairing effect

圖4 無標度網(wǎng)絡(luò)故意打擊下的修復(fù)效果Fig.4 Intentional attack by scale-free network repairing effect

3 結(jié)束語

文中針對復(fù)雜網(wǎng)絡(luò)修復(fù)問題，首先提出了一種延遲修復(fù)的網(wǎng)絡(luò)修復(fù)模型，并在不同復(fù)雜網(wǎng)絡(luò)拓撲下針對隨機打擊和故意打擊提出了四種不同的修復(fù)策略，模擬實驗結(jié)果顯示在隨機網(wǎng)絡(luò)下，采用比例修復(fù)或者平方根修復(fù)能夠達到較好的修復(fù)效果；而在無標度網(wǎng)絡(luò)下，采用平方根修復(fù)能夠達到較好的修復(fù)效果。

[1]Albert R，Barabasi A L.Statistical mechanics of complex network[J].Review of Modern Physics，2002，74（1）:47-97.

[2]S.Ratnasamy， P.Francis， M.Handley EA.A Scalable Content-Addressable Network [C]//In: Proc. of ACM SIGCOMM.New York，USA:2001.149-160.

[3]Watts D J，Strogatz S H.Collective dynamics of small-world networks[J].Nature，1998，393（4537）:440-448.

[4]Albert R，Jeong H，Barabasi A L.Error and attack tolerance of complex networks[J].Nature，2000，406（6794）:378-382.

[5]Chi L P，Yang C B，Cai X.Stability of random networks under evolution of attack and repair[J].Chinese Physics Letters，2006，23（1）:263-266.

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

HU Bin，LI Fang.Multiple attack strategy scale-free network repair strategy[J].Systems Engineering and Electronics，2010，32（1）:43-47.