基于HOT理論的網絡抗毀性動態演化模型

劉媛妮

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

1 概述

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

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

本文將建立具有抗毀性的網絡動態演化模型作為 HOT問題進行求解，通過模擬單個節點在網絡中的產生、成長和消亡過程來建立具有抗毀性的網絡動態演化模型，使得建立的模型不僅在節點度分布上與互聯網節點度分布呈現冪率特性相一致，而且將抗毀性作為節點擇優互聯的一個考慮因素，從系統發展的內部演化規律使得模型的抗毀能力朝最優化方向發展。

2 研究現狀

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

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

文獻[5]最先嘗試將 Internet建模作為 HOT問題求解。新節點i連接到一個已存在的節點j的依據是2個目標的權重最小，即:

其中，dij為i到j的歐幾里德距離；hj是從j到其他所有節點的平均跳數。當α在不同范圍內取值時，可以得到星形、指數度分布和冪率度分布3種類型的拓撲[1]。文獻[6]等開始嘗試應用 HOT理論對 Internet的AS級拓撲進行建模，他們在不同程度上考慮了AS的連接能力、商業關系、連接代價等直觀因素，生成的模型在某些特性上與真實拓撲相符合。

3 動態演化模型

3.1 基本定義

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

(1)i:區分不同節點的唯一標識。

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

其中，Ci為節點 i重要性的常量部分；Bi為節點 i重要性的變量部分；由該節點加入網絡后的介數[7-8]決定，α為Ci與Bi之間的調節因子。

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

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

(5)Rdi:節點的度增長率。反映了節點在網絡中的增長速度的快慢。在網絡中，節點的增長速度并不相同，有些新加入節點在很短時間內即變為度數較大的節點，引入度增長率就是為了正確再現這一現象。在模型中以隨機分布的方式為節點設置度增長率。

(6)(xi, yi):節點坐標。節點i在模擬范圍內的坐標值。

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

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

3.2 模型建立過程

模型在建立的最初階段需要在網絡中一次性加入m0個節點，隨后將以這m0個節點為基礎，每一步隨機地進行如下的一個操作:

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

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

2)根據 i坐標信息，在其連接范圍 Cri內選擇一節點j進行連接。新節點j選擇與網絡中已存在的節點i連接的規則如下:若在節點i的連接范圍內不存在這樣的節點j，則取消該操作；若存在節點j，則節點j被選擇的概率:

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

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

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

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

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

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

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

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

②更新網絡信息:對網絡中受影響的節點重新計算其各屬性值。

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

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

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

③若上述攻擊成功，則更新網絡信息。需對網絡中受影響的節點重新計算其各屬性值。

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

1)在全部節點中隨機選擇一節點作為 i，設網絡全部節點數為x，則i被選中的概率為1/x。在i的所有邊中，選擇連接的j重要性最小的邊進行刪除。節點j被選擇的概率為Pdj。

2)若刪除掉該邊之后，i的度變為0，脫離整個網絡，則再執行邊重連的操作。

4 網絡抗毀性動態演化模型分析

本節首先對建立的網絡模型的度分布進行分析，然后研究節點的度分布情況，以及在何種情況下會產生節點度符合冪率分布的模型。

4.1 節點度分布分析

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

設函數 p(K,ti,t)表示節點i在ti時刻加入域間路由系統，在t時刻節點度數變為K的概率，則:

由連續演化定理，節點度數分布概率為:

只有在執行了刪除節點的操作之后，節點的度數可能變為0，所以:

根據概率和為1，即:

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

4.2 冪律特性產生條件分析

將式(2)～式(4)代入P(K)的表達式(10)內化簡進行分析可得:

節點度數服從冪指數為3的冪率分布。節點度服從指數分布。

5 仿真分析

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

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

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

圖1 N=1000時的HOT模型節點度分布

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

圖2 受到不同類型攻擊時的網絡效率變化曲線

6 結束語

本文以一種優化驅動的方式建立了基于 HOT理論的抗毀性網絡動態演化模型，為進行網絡抗毀性研究打下了基礎。該模型不僅優于傳統的圖論的建模方法，而且更具真實性。在利用內在規律研究抗毀性網絡模型的過程中，可以得出以下結論:網絡中各個節點作為獨立的系統自主決策，并具有相同的目標，即使自身利益最大化，因此在宏觀上具有一致性和可預測性。網絡的外在表現是可以調節的，這與其本身的特性并不矛盾；可以通過激勵措施引導各個節點進行決策，通過調節節點的不同屬性值，可以使系統在整體上表現出期望的特征。

[1]周 苗, 楊家海, 劉洪波, 等.Internet網絡拓撲建模[J].軟件學報, 2009, 20(1)∶ 109-123.

[2]張 昕, 趙 海, 王莉菲, 等.AS級Internet拓撲分析[J].通信學報, 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.