基于復雜網絡分析的通信網絡節點重要度評估方法*

梁德軍，宋廣寧，趙 明

（國防科技大學，安徽 合肥230037）

0 引 言

隨著信息技術的快速發展，通信網絡在承載信息傳輸方面的作用已日益突出。通信網絡是指由多個交換節點用傳輸鏈路以一定的拓撲結構互聯構成的用于特定功能的復雜網絡[1］，而各個通信節點由于其功能作用網絡位置和組織關系的不同，其在網絡中表現出不同的重要程度[2］，如現代軍事戰爭中斬首行動就是要在繁雜的目標中尋找到最重要或最核心的部位進行打擊，以起到意想不到的效果。因此，對通信網絡中各通信節點進行重要性評估，準確挖掘出網絡中的核心節點，可以為網絡抗毀性方面的研究提供重要的理論幫助。

現有關于節點重要性的度量方法可分為兩類:第一類方法為在網絡的整體能力健全的前提下反映節點的顯著程度，一般通過節點在網絡拓撲中的中心性程度進行評估，即節點的中心性越強，顯著性越明顯，節點越重要，典型的指標有度中心介數、子圖、緊密性等; 第二類方法為去除掉節點之后分析網絡的性能毀壞程度，一般通過網絡降低的性能指標來衡量，即去除掉該節點之后，網絡性能下降得越多，則該節點越重要，經典方法有節點刪除法、收縮法[3］，通過網絡中的最短路徑、網絡效率[4］以及生成數目的下降程度來衡量。最近的研究成果提出了網絡中的節點重要性不僅與網絡拓撲結構有關，還受傳播機制以及節點自身屬性影響[5］[6］，然而上述節點重要性的評估方法僅考慮了網絡的靜態特性，忽略了網絡中存在的物質流動給網絡帶來的影響，并不能很好地反映真實的節點重要程度。而且通信網絡存在時變性，隨著網絡節點的接入和退出拓撲結構發生變化，各個節點在整個通信時段中接入的時段也影響節點的重要度。因此本文提出一種基于局部負載重分配[7］后對近鄰節點負載震蕩程度的節點重要度評估模型，研究某一時段固定網絡拓撲結構的節點重要度，并根據該結構網絡在整個通信時段中所處的位置確定其網絡的重要度，結合上述兩個指標最終得出節點在整個通信時段的重要度。該方法是對傳統僅考慮網絡結構評估節點重要程度的一種改進，增加了通信時段的重要程度，使評估結果更加真實。

1 通信網絡節點重要度評估方法

通信網絡的鏈路連接情況可用有向圖G=(V,E)表示，其中V為節點，代表信息收發處理終端，E為邊，代表各終端的連接關系，并且約定任意兩個節點之間只有一條連邊，且不存在自環。同時注意到通信網絡是動態變化的網絡，不斷有節點接入和退出，導致網絡的拓撲結構不斷變化。因此在分析通信網絡節點重要度時，首先從網絡拓撲結構入手，研究在某一時段穩定的通信網絡各節點的重要度，再評估該時段通信網絡在整個通信時段的重要度，最后聚合得出全部通信節點在整個通信時段的重要度。通信網絡節點重要度的評估模型為：

其中gi為節點i在整個通信時段的重要度，hki為在第k時段的通信網絡中節點i的重要度，wk為k時段的通信網絡在整個通信時段的重要度，下面分別建立hki、wk的評估模型。

2 復雜網絡節點重要度評估模型

建立hki的評估模型時借鑒復雜網絡的傳播機制，首先根據節點的實時負載和容量確定節點的實時狀態，再根據節點實時狀態建立節點失效后向臨近節點重分配負載的模型，最后根據節點負載重分配對臨近節點的震蕩程度評估節點的重要度。

2.1 節點狀態

節點狀態由可用節點能夠容納轉移負載的能力來表示，它由兩個方面的因素決定: 一是節點自身的負載剩余容納能力，二是相鄰節點的負載剩余容納能力。從上述描述的過程來看，它可以分為兩個階段，首先考慮節點剩余容納能力，假設節點i的實時負載為Qi，節點的容量為Ci，那么節點的負載剩余容納能力Ri可表示為：

即節點負載剩余容納能力為節點容量與現有負載的差值，當負載超過容量時，其負載剩余容納能力為0，此時該節點已經失效。節點負載剩余容納能力體現的是節點還能夠處理或者容納負載的能力，Ri值越大說明其處理能力越強，在負載重分配時應該占有優勢，其分配的比例應該越高，反之則越低，它是隨著節點負載的變化而不斷變化的。

考慮到相鄰節點負載剩余容納能力的影響，提出能夠更精確衡量節點負載剩余容納能力的節點狀態，該狀態是節點自身的負載剩余容納能力與相鄰節點負載剩余容納能力的有機結合，共同構成了節點真實的負載剩余容納能力。對節點狀態的指標進行定義，如式（3）所示：

其中：Zi表示節點狀態；Ri表示節點裕度；Φi表示節點i的鄰接節點；λ為權重參數，通過調節λ的值可以調節整個節點狀態在負載重分配時所占的比例，當時λ=0式（3）為局部負載均勻重分配。式（3）反映的是節點能夠容納負載的能力，它取自身節點負載剩余容納能力與相鄰節點負載剩余容納能力總和中的最小值，當沒有相鄰節點時，節點負載剩余容納能力即為自身的節點負載剩余容納能力。

2.2 負載重分配

負載重分配方式是描述節點失效后其上的負載向網絡中其他節點進行轉移的規則。負載重分配方式如圖1所示，節點失效后，原本通過該節點的負載信息流將會重新選擇通過路徑，其上的負載將會轉移到與之相鄰的節點，以保證整個網絡的有效運行，整個網絡會由于節點的失效而進行負載的全面更新，即Qi′=Qi+ΔQi，i∈Φf其中Qi為更新之前的負載，Qi′為更新之后的負載，ΔQi為更新時的增量，Φf為失效節點f的所有鄰接節點。

圖1 基于節點狀態演化的負載重分配方式

假設失效節點f的負載為Qf，相鄰節點的節點狀態為Zi，在相鄰節點上重新分配的負載增量可以用式（4）表示，它是對經典近鄰重分配方式的改進，它與節點狀態相關而不與節點負載相關。

2.3 節點重要度評估

依據上述負載重分配模型，參照文獻[8］提出的節點重要度評估指標，可以用節點f故障后由于其自身負載向近鄰節點轉移而引起近鄰節點向失效狀態轉移的程度來衡量節點引發網絡級聯故障的能力即節點的重要度。為了避免觸發進一步的級聯故障發生，節點i經重分配后的負載受到其容量Ci的限制，Ci=(1+η)Q0i其中常數η為網絡的最大忍受度，表示處理額外負荷的能力，Q0i為節點初始負載，因此重分配的負載將滿足式（5）。

其中，|Φf|為故障節點的所有近鄰節點數目。

3 通信網絡重要度評估模型

從時域的角度出發，某一拓撲結構通信網絡的重要度主要取決于以下兩點，一是該網絡所處的時間段在整個通信時段中的重要程度，如軍事通信中發起進攻階段的通信網絡要比預先偵察階段的通信網絡重要；二是該網絡相對整個通信時段占據的時長比例，如在通信網絡中經常活躍的節點所承擔的信息處理任務較多，由這些節點構成的網絡重要度較高，而活躍度較低的節點往往是備用節點或偏遠節點，其重要度相對不高。以上述理論為依據提出通信網絡重要度評估模型，將通信時段劃分成不重疊的若干個時間片[9］，在每個時間片內通信網絡的拓撲結構不變，則將時段內變化的通信網絡分解成基于多個時間片的靜態通信網絡，每個時間片對應一個靜態的通信網絡結構，且不同于前一時間片或后一時間片對應的靜態通信網絡結構，建立起時間片與某一拓撲結構通信網絡的對應關系，并以時間片在通信時段內的重要度和相對時長作為片上通信網絡的重要度。

根據上述思路建立通信網絡重要度評估模型。首先將整個通信時間段U劃分為L個不重疊的時間片，得{[b1,e1］;[b2,e2］;…;[bL,eL］}，其中b表示時間片開始時刻，e表示時間片結束時刻。再由通信決策者將整個通信時段劃分為N個子段{[T1,T2］;[T2,T3］;…;[TN,TN+1］}，并根據子段在整個通信時間段上的位置，以及該子段所承載的通信任務等，采用專家打分的方法確定各子段的重要度為 {θ1;θ2;……;θN}，且如圖2所示。則時間片k的重要度rk的計算模型為：

其中Tp≤bk＜Tp+1，Tp+X-1≤ek＜Tp+X，再進行歸一化處理得出時間片k對應的通信網絡重要度為

圖2 不同時間片對應的通信網絡示意圖

4 網絡的構建及節點重要性評估仿真實驗

4.1 通信網絡構建

本文在構建實例分析所需的通信網絡時主要考慮到通信網絡的以下兩個特點，一是網絡的時變性，不斷有新節點接入和老節點退出；二是新節點往往選擇度值較大的數個老節點建立連接，退出的多是度值較低的節點。因此本文提出一種時變的隨機網絡模型，該模型的算法如下：

Step 1初始設定：首先建立一個具有j0個節點，鏈路節點比為S0的隨機網絡，并為每個節點按照1至j0編號。

Step 2增長節點：每間隔B時間增加一個新節點O，在原節點最大編號上加1作為新節點的編號，并引出m≤j0條邊與之前網絡的m個節點相連，其中B～N(B0,σ21)，m～N(m0,σ22)。

Step 3擇優連接：連接節點的選擇按照度值優先原則進行，選擇老節點i作為新邊連接節點的概率為:其中D(·)為節點度值。

Step 4退出節點：選擇度值最小的節點退出網絡，若度值最小的節點有多個則隨機選擇一個，節點退出后與其相連的鏈路全部斷開。

Step 5通信子段重要度賦值：真實情況下通信子段應由決策者考慮主觀判斷、客觀實際進行劃分并賦予重要度，通常靠近整個時段中間的子段承擔較多的信息傳遞任務，相應的重要度較高，兩邊的子段重要度逐漸降低。仿真中為簡化該過程，將整個通信時段均勻劃分為N個子段{[T1,T2］;[T2,T3］;…;[TN,TN+1］}，并用正太分布近似為各子段賦予重要度，則第i個子段的重要度為：

4.2 實例分析

取上述時變隨機網絡模型中的參數j0=200，S0=3，B0=100s，m0=3，σ1=10s，σ2=1，σ3=60s，N=6，T1=0s，TN+1=3 600s，并設定每個節點的初始負載為Q0i=akγi，ki為節點的度a、γ為可調節參數控制初始負載的大小，為簡化計算所有節點的a=1，γ=1，節點容量模型中η=0.07。基于前述的節點重要度評價方法，排序結果見表1，表1僅展示排序前30位的節點。

表1 各時間片內節點重要度

根據節點重要度排序結果，按照節點重要度從高到低依次從網絡中使該節點失效，并提出以失效影響度Ω(i)作為指標，評估節點i失效后對整個通信時段網絡的影響程度，網絡失效結果如圖3所示。

圖3 通信網絡失效效果

其中失效影響度的定義式如式（9）所示：

其中ψi,j/200表示在時間片j對應的網絡上節點i失效后所級聯失效的節點數量比例。該式綜合考慮了節點失效后在單個時間片上照成的影響，時間片在整個通信時段的重要性以及影響持續的時間，較為真實的反映節點失效后對整個通信的影響程度。

圖3中的橫坐標為按照節點重要度排序的結果，從1到30依次失效，縱坐標表示失效影響度。從圖中可以看出排序靠前的節點失效所引起的影響要明顯大于排序靠后的節點。對于該通信網絡來說，此排序結果的失效效果很好，排序最靠前的10個節點，均表現出來在此網絡參數和節點參數下的良好失效效果; 而排序靠后的其余節點失效效果較差。以此證明，對于這種網絡拓撲結構，本文的排序方法較為適合。

5 結 語

本文提出的通信網絡節點重要程度評估模型，在傳統評估模型的基礎上，考慮了不同通信時段重要程度及時長對節點重要程度的影響，同時兼顧考慮了節點在網絡拓撲結構中位置重要程度，節點在網絡傳播中的重要程度，相對較為真實的定量反映節點的重要度，為通信網絡關鍵節點的發現和保護提供一定幫助。但是在評估模型中對各節點的功能和業務并未進行區分，這將是下一步研究的重點。