基于HOT理論的網(wǎng)絡(luò)抗毀性動態(tài)演化模型

劉媛妮

(重慶郵電大學(xué)通信與信息工程學(xué)院，重慶 400065)

1 概述

隨著自然災(zāi)害、惡意攻擊等事件對互聯(lián)網(wǎng)生存性構(gòu)成的威脅日益增多，提高網(wǎng)絡(luò)的抗毀性具有重要的研究意義。以往的網(wǎng)絡(luò)抗毀性研究大都建立在圖論基礎(chǔ)上，不能很好地把握Internet的拓?fù)湟?guī)律和動態(tài)行為特性，很難從根本上解決大型復(fù)雜網(wǎng)絡(luò)的抗毀性問題。Internet發(fā)展至今，其內(nèi)在規(guī)律在外部則表現(xiàn)為度分布的冪率特性[1-2]，即:()PK=CKλ-× ，其中，P(K)指節(jié)點度數(shù)為K的概率；C為常數(shù)；λ為常數(shù)。這種冪率特性并不是偶然出現(xiàn)的，而是其內(nèi)在的擇優(yōu)選擇機制所產(chǎn)生的結(jié)果:新節(jié)點加入網(wǎng)絡(luò)時總是傾向于與最“優(yōu)”的節(jié)點相連。從用戶角度來講，其加入網(wǎng)絡(luò)時將會傾向于選擇與具有較高抗攻擊能力以及自恢復(fù)能力的節(jié)點進(jìn)行連接，以保證自身的安全性；而對于網(wǎng)絡(luò)中已經(jīng)存在的節(jié)點來說，抗毀性越強的節(jié)點獲得新節(jié)點連接的概率越大。因此，對于網(wǎng)絡(luò)抗毀性問題的研究，要從網(wǎng)絡(luò)內(nèi)部的發(fā)展規(guī)律出發(fā)，通過研究節(jié)點在網(wǎng)絡(luò)中的動態(tài)演化行為建立具有抗毀性的網(wǎng)絡(luò)模型，將是網(wǎng)絡(luò)抗毀性研究的一條新途徑。

HOT[3-4]最優(yōu)化理論表明，系統(tǒng)在朝最優(yōu)化方向演化后，其外在特征將會表現(xiàn)出冪率特性。因此，當(dāng)把建立具有抗毀性的網(wǎng)絡(luò)模型作為 HOT問題進(jìn)行求解時，為了真實模擬節(jié)點在網(wǎng)絡(luò)中的演化過程，節(jié)點在進(jìn)行擇優(yōu)選擇的過程中，要根據(jù)節(jié)點的抗攻擊能力、自恢復(fù)能力、連接能力、傳輸代價以及連接范圍等因素綜合考慮最“優(yōu)”的節(jié)點進(jìn)行連接。這種擇優(yōu)選擇的過程不僅使Internet最終在外在形式上表現(xiàn)為節(jié)點度符合冪率分布、抗攻擊能力等綜合特性朝最優(yōu)化方向發(fā)展，從而可以從根本上解決網(wǎng)絡(luò)性能的優(yōu)化問題。

本文將建立具有抗毀性的網(wǎng)絡(luò)動態(tài)演化模型作為 HOT問題進(jìn)行求解，通過模擬單個節(jié)點在網(wǎng)絡(luò)中的產(chǎn)生、成長和消亡過程來建立具有抗毀性的網(wǎng)絡(luò)動態(tài)演化模型，使得建立的模型不僅在節(jié)點度分布上與互聯(lián)網(wǎng)節(jié)點度分布呈現(xiàn)冪率特性相一致，而且將抗毀性作為節(jié)點擇優(yōu)互聯(lián)的一個考慮因素，從系統(tǒng)發(fā)展的內(nèi)部演化規(guī)律使得模型的抗毀能力朝最優(yōu)化方向發(fā)展。

2 研究現(xiàn)狀

研究表明，Internet的節(jié)點度分布符合冪率分布(power law)，在這種分布下，網(wǎng)絡(luò)中大部分節(jié)點只有少數(shù)連接，而少數(shù)節(jié)點則擁有大量的連接。HOT理論從系統(tǒng)優(yōu)化設(shè)計的角度說明了冪率特性產(chǎn)生的原因:即全局性的優(yōu)化過程可導(dǎo)致冪率分布。HOT理論建模是使用一種優(yōu)化框架來模擬節(jié)點在網(wǎng)絡(luò)中的發(fā)展過程，并且以一種增量式優(yōu)化的方法使系統(tǒng)不斷朝最優(yōu)的方向發(fā)展，這種方式是按照網(wǎng)絡(luò)發(fā)展的內(nèi)部誘因來建模，當(dāng)網(wǎng)絡(luò)朝最優(yōu)化方向發(fā)展的過程中，一些外部表現(xiàn)如power law等特征會自然地表現(xiàn)出來，而不是僅關(guān)注一些統(tǒng)計特性的顯式表現(xiàn)，如節(jié)點的層次性、節(jié)點度分布等。HOT系統(tǒng)是伴隨著使系統(tǒng)故意朝向魯棒性設(shè)置的過程出現(xiàn)的，目的是使系統(tǒng)對不確定性有一定的容忍度(Tolerance)。產(chǎn)量的最優(yōu)化將會產(chǎn)生高性能以及高的吞吐量以及事件規(guī)模的冪率分布和對于不確定性事件的高敏感性。

HOT系統(tǒng)對于系統(tǒng)在設(shè)計過程中實現(xiàn)考慮到的因素，具有很強的魯棒性(high-robust)，但是對于考慮到的因素，有著很強的敏感性(fragile)，也反映了當(dāng)前復(fù)雜系統(tǒng)的 Robust-yet-fragile特性。當(dāng)前針對HOT理論的應(yīng)用主要集中于 2個方面:(1)PLR(Probability-Loss-Resource)問題的優(yōu)化[2]；(2)網(wǎng)絡(luò)優(yōu)化建模[5-6]。

文獻(xiàn)[5]最先嘗試將 Internet建模作為 HOT問題求解。新節(jié)點i連接到一個已存在的節(jié)點j的依據(jù)是2個目標(biāo)的權(quán)重最小，即:

其中，dij為i到j(luò)的歐幾里德距離；hj是從j到其他所有節(jié)點的平均跳數(shù)。當(dāng)α在不同范圍內(nèi)取值時，可以得到星形、指數(shù)度分布和冪率度分布3種類型的拓?fù)鋄1]。文獻(xiàn)[6]等開始嘗試應(yīng)用 HOT理論對 Internet的AS級拓?fù)溥M(jìn)行建模，他們在不同程度上考慮了AS的連接能力、商業(yè)關(guān)系、連接代價等直觀因素，生成的模型在某些特性上與真實拓?fù)湎喾稀?/p>

3 動態(tài)演化模型

3.1 基本定義

通過研究，將網(wǎng)絡(luò)中的每個節(jié)點抽象為一個8元組(i, Ipi, Cci, Cri, Rdi, Sri, Aai, (xi, yi))，其中:

(1)i:區(qū)分不同節(jié)點的唯一標(biāo)識。

(2)Ipi:節(jié)點的重要性，用于衡量節(jié)點在網(wǎng)絡(luò)中的重要程度。節(jié)點i在加入網(wǎng)絡(luò)時，首先要根據(jù)其重要性以確定其連接能力、連接范圍等屬性，另外節(jié)點在網(wǎng)絡(luò)的動態(tài)演化過程中，其重要性將會發(fā)生改變。因此，節(jié)點i的重要性可以表示為:

其中，Ci為節(jié)點 i重要性的常量部分；Bi為節(jié)點 i重要性的變量部分；由該節(jié)點加入網(wǎng)絡(luò)后的介數(shù)[7-8]決定，α為Ci與Bi之間的調(diào)節(jié)因子。

(3)Cci:節(jié)點的連接能力。節(jié)點受其性能限制所能連接的最大數(shù)目。重要性越高的節(jié)點其連接能力也越高，反之亦然。

(4)Cri:節(jié)點的連接半徑。在實際情況中，需要考慮連接的可行性，過長的連接需要極高的連接代價，不具備實際意義。因此，節(jié)點i的連接范圍是以其自身坐標(biāo)為原點，Cri為半徑的圓。

(5)Rdi:節(jié)點的度增長率。反映了節(jié)點在網(wǎng)絡(luò)中的增長速度的快慢。在網(wǎng)絡(luò)中，節(jié)點的增長速度并不相同，有些新加入節(jié)點在很短時間內(nèi)即變?yōu)槎葦?shù)較大的節(jié)點，引入度增長率就是為了正確再現(xiàn)這一現(xiàn)象。在模型中以隨機分布的方式為節(jié)點設(shè)置度增長率。

(6)(xi, yi):節(jié)點坐標(biāo)。節(jié)點i在模擬范圍內(nèi)的坐標(biāo)值。

(7)Sri:節(jié)點的自恢復(fù)能力。衡量節(jié)點在受到攻擊后從脫離網(wǎng)絡(luò)到成功恢復(fù)這一能力的大小。在通常情況下，關(guān)鍵節(jié)點具有更好的備份措施，因此，重要性越大的節(jié)點自恢復(fù)的能力更高。

(8)Aai:節(jié)點的抗攻擊能力。衡量節(jié)點對于攻擊的抵御能力，通常對于網(wǎng)絡(luò)中的關(guān)鍵節(jié)點，其周圍部署的安全工具較之普通節(jié)點要多得多，對于一般的攻擊抵抗能力也會增高。

3.2 模型建立過程

模型在建立的最初階段需要在網(wǎng)絡(luò)中一次性加入m0個節(jié)點，隨后將以這m0個節(jié)點為基礎(chǔ)，每一步隨機地進(jìn)行如下的一個操作:

(1)以概率p1加入一個新的節(jié)點i，該操作主要分為4步:

1)配置節(jié)點i的各種屬性。

2)根據(jù) i坐標(biāo)信息，在其連接范圍 Cri內(nèi)選擇一節(jié)點j進(jìn)行連接。新節(jié)點j選擇與網(wǎng)絡(luò)中已存在的節(jié)點i連接的規(guī)則如下:若在節(jié)點i的連接范圍內(nèi)不存在這樣的節(jié)點j，則取消該操作；若存在節(jié)點j，則節(jié)點j被選擇的概率:

3)將節(jié)點 i與被選中的節(jié)點 j連接，即加入一條新邊 i?j。

4)更新網(wǎng)絡(luò)信息。由于新加入了節(jié)點和邊，需對網(wǎng)絡(luò)中受影響的節(jié)點重新計算其各屬性值。

(2)以概率 p2加入一條新邊:在節(jié)點 i和節(jié)點 j之間加入新的連接邊，主要分為2步:

1)在所有節(jié)點中隨機選擇一節(jié)點 i，且滿足Ki＜Cci，其中Ki為節(jié)點i當(dāng)前的度數(shù)，即在添加邊的過程中要保證節(jié)點的度數(shù)不超過其連接能力。

2)在節(jié)點i的連接范圍內(nèi)選擇一節(jié)點j進(jìn)行連接。選擇j時應(yīng)滿足Ccj＞Cci，同時，節(jié)點j被選擇的概率應(yīng)為Pnj。若在i的連接范圍內(nèi)不存在這樣的節(jié)點j，則操作到此結(jié)束。

(3)以概率 p3刪除一個已存在的節(jié)點，包括 2種情況:

1)永久性刪除節(jié)點，即節(jié)點的正常更替:此操作主要分成2步:

①重要性越小的節(jié)點被更替的概率越大。則節(jié)點j被刪除的概率為:

②更新網(wǎng)絡(luò)信息:對網(wǎng)絡(luò)中受影響的節(jié)點重新計算其各屬性值。

2)攻擊性刪除節(jié)點:網(wǎng)絡(luò)中節(jié)點受到攻擊，使得節(jié)點暫時失效，在這種情況下，節(jié)點經(jīng)過一段時間的自恢復(fù)后還會重新加入到網(wǎng)絡(luò)中。此操作主要分為3步:

①重要性越大的節(jié)點被刪除的概率越大。則節(jié)點j被選擇的概率為:

②節(jié)點j被選擇后，則以概率P判定該次攻擊能否成功，若成功，則將節(jié)點j以及與其連接的所有邊一并刪除；若失敗，說明節(jié)點足以抵御這一次攻擊，則操作到此取消。

③若上述攻擊成功，則更新網(wǎng)絡(luò)信息。需對網(wǎng)絡(luò)中受影響的節(jié)點重新計算其各屬性值。

(4)以概率p4刪除一條已存在的邊。

1)在全部節(jié)點中隨機選擇一節(jié)點作為 i，設(shè)網(wǎng)絡(luò)全部節(jié)點數(shù)為x，則i被選中的概率為1/x。在i的所有邊中，選擇連接的j重要性最小的邊進(jìn)行刪除。節(jié)點j被選擇的概率為Pdj。

2)若刪除掉該邊之后，i的度變?yōu)?，脫離整個網(wǎng)絡(luò)，則再執(zhí)行邊重連的操作。

4 網(wǎng)絡(luò)抗毀性動態(tài)演化模型分析

本節(jié)首先對建立的網(wǎng)絡(luò)模型的度分布進(jìn)行分析，然后研究節(jié)點的度分布情況，以及在何種情況下會產(chǎn)生節(jié)點度符合冪率分布的模型。

4.1 節(jié)點度分布分析

在建模時，執(zhí)行完初始化操作之后，假設(shè)余下的4種操作在一個時間步內(nèi)被執(zhí)行的概率分別為P1、P2、P3、P4，在刪除已有邊的過程中又分為以概率 P31永久性刪除或者以概率 P32進(jìn)行攻擊性刪除，其中，P3=P31+P32。設(shè)節(jié)點 i加入網(wǎng)絡(luò)過程中選擇節(jié)點 j進(jìn)行連接的概率為 Pnj，永久性刪除特定節(jié)點 j的概率為Pdj，攻擊性刪除特定節(jié)點 j的概率為Paj，節(jié)點 j被攻擊成功的概率為p，刪除特定邊中選擇的概率為在網(wǎng)絡(luò)中全部節(jié)點隨機選擇，即 1/x(x為當(dāng)前網(wǎng)絡(luò)中全部節(jié)點的個數(shù))，選擇j的概率是Pdj，即刪除邊i?j的概率為 Pdj×(1/x)。

設(shè)函數(shù) p(K,ti,t)表示節(jié)點i在ti時刻加入域間路由系統(tǒng)，在t時刻節(jié)點度數(shù)變?yōu)镵的概率，則:

由連續(xù)演化定理，節(jié)點度數(shù)分布概率為:

只有在執(zhí)行了刪除節(jié)點的操作之后，節(jié)點的度數(shù)可能變?yōu)?，所以:

根據(jù)概率和為1，即:

由式(7)～式(9)可計算出P(K)的遞推公式:

4.2 冪律特性產(chǎn)生條件分析

將式(2)～式(4)代入P(K)的表達(dá)式(10)內(nèi)化簡進(jìn)行分析可得:

節(jié)點度數(shù)服從冪指數(shù)為3的冪率分布。節(jié)點度服從指數(shù)分布。

5 仿真分析

本文仿真實驗使用負(fù)荷-容量模型[9-10]，基于Matlab6.5環(huán)境，研究在網(wǎng)絡(luò)規(guī)模同為 1000個節(jié)點4413條邊，HOT模型和BA模型在發(fā)生相繼失效的情況下，網(wǎng)絡(luò)效率E隨失效節(jié)點數(shù)目所占比例P增多時的變化情況。其中，HOT模型中各參數(shù)設(shè)置如表1所示。

表1 HOT模型各參數(shù)值 (%)

通過仿真實驗，得到1000個節(jié)點的HOT網(wǎng)絡(luò)模型的節(jié)點度分布如圖 1所示，其中，直線是P(K )= C× K-3(C為常數(shù))的曲線，散點為HOT模型中節(jié)點度的概率分布，由圖 1可以看出，HOT模型的度分布與 P(K )= C× K-3的曲線十分接近。

圖1 N=1000時的HOT模型節(jié)點度分布

為了驗證HOT模型的抗毀性，本文在HOT模型以及BA模型上(其中，BA模型的冪指數(shù)為?3)研究網(wǎng)絡(luò)在受到2種不同類型的節(jié)點失效后，網(wǎng)絡(luò)效率E和其初始效率E1之比隨著失效節(jié)點數(shù)目增多時的變化情況，仿真結(jié)果如圖2所示。圖2(a)和圖2(b)分別為同等規(guī)模的BA和HOT模型在發(fā)生相繼失效情況下，網(wǎng)絡(luò)效率E與初始網(wǎng)絡(luò)效率E1的比值在基于節(jié)點度攻擊和節(jié)點隨機失效的情況下隨著節(jié)點失效數(shù)目增多的變化曲線。由圖2可以看出，隨著節(jié)點失效數(shù)目的增多，網(wǎng)絡(luò)效率E不斷下降，但是基于HOT模型的網(wǎng)絡(luò)始終比BA模型具有更高的網(wǎng)絡(luò)效率比。這說明在同等網(wǎng)絡(luò)規(guī)模、網(wǎng)絡(luò)受到同等打擊的情況下，HOT模型比BA模型的網(wǎng)絡(luò)效率下降得少，具有更高的抗毀性。

圖2 受到不同類型攻擊時的網(wǎng)絡(luò)效率變化曲線

6 結(jié)束語

本文以一種優(yōu)化驅(qū)動的方式建立了基于 HOT理論的抗毀性網(wǎng)絡(luò)動態(tài)演化模型，為進(jìn)行網(wǎng)絡(luò)抗毀性研究打下了基礎(chǔ)。該模型不僅優(yōu)于傳統(tǒng)的圖論的建模方法，而且更具真實性。在利用內(nèi)在規(guī)律研究抗毀性網(wǎng)絡(luò)模型的過程中，可以得出以下結(jié)論:網(wǎng)絡(luò)中各個節(jié)點作為獨立的系統(tǒng)自主決策，并具有相同的目標(biāo)，即使自身利益最大化，因此在宏觀上具有一致性和可預(yù)測性。網(wǎng)絡(luò)的外在表現(xiàn)是可以調(diào)節(jié)的，這與其本身的特性并不矛盾；可以通過激勵措施引導(dǎo)各個節(jié)點進(jìn)行決策，通過調(diào)節(jié)節(jié)點的不同屬性值，可以使系統(tǒng)在整體上表現(xiàn)出期望的特征。

[1]周 苗, 楊家海, 劉洪波, 等.Internet網(wǎng)絡(luò)拓?fù)浣J].軟件學(xué)報, 2009, 20(1)∶ 109-123.

[2]張 昕, 趙 海, 王莉菲, 等.AS級Internet拓?fù)浞治鯷J].通信學(xué)報, 2008, 29(7)∶ 50-61.

[3]Carlson J M, Doyle J.Highly Optimized Tolerance∶ A Mechanism for Power Laws in Designed Systems[J].Physical Review E, 1999, 60(2)∶ 1412-1427.

[4]Doyle J, Carlson J M, Law P.High Optimized Tolerance,and Generalized Source Coding[J].Physical Review Letters, 2000, 84(24)∶ 5656-5659.

[5]Fabrikant A, Koutsoupias E, Papadimitriou C.Heuristically Optimized Trade-offs∶ A New Paradigm for Power-laws in the Internet[C]//Proc.of ICALP’02.[S.1.]∶IEEE Press, 2002∶ 110-122.

[6]Alderson D, Doyle J, Willinger W.Internet Connectivity at the AS Level∶ An Optimization Driven Modeling Approach[C]//Proc.of ACM SIGCOMM’03.Karlsruhe,Germany∶ ACM Press, 2003.

[7]Freeman L C.A Set of Measures of Centrality Based on Betweenness[J].Sociometry, 1997, 40(1)∶ 35-41.

[8]Brandes U.A Faster Algorithm for Betweenness Centrality[J].Journal of Mathematical Socialogy, 2001,25(2)∶ 163-177.

[9]Kinney R, Crucitti P, Albert R, et al.Modeling Cascading Failures in the North American Power Grid[EB/OL].(2010-10-20).http∶//arXiv∶cond-mat/0410318.

[10]Kinney R, Crucitti P, Albert R, et al.Modeling Cascading Failures in the North American Power Grid[J].European Physical Journal, 2005, 46(1)∶ 101-107.