基于復(fù)雜網(wǎng)絡(luò)分析的通信網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法*

梁德軍，宋廣寧，趙 明

（國(guó)防科技大學(xué)，安徽 合肥230037）

0 引 言

隨著信息技術(shù)的快速發(fā)展，通信網(wǎng)絡(luò)在承載信息傳輸方面的作用已日益突出。通信網(wǎng)絡(luò)是指由多個(gè)交換節(jié)點(diǎn)用傳輸鏈路以一定的拓?fù)浣Y(jié)構(gòu)互聯(lián)構(gòu)成的用于特定功能的復(fù)雜網(wǎng)絡(luò)[1］，而各個(gè)通信節(jié)點(diǎn)由于其功能作用網(wǎng)絡(luò)位置和組織關(guān)系的不同，其在網(wǎng)絡(luò)中表現(xiàn)出不同的重要程度[2］，如現(xiàn)代軍事戰(zhàn)爭(zhēng)中斬首行動(dòng)就是要在繁雜的目標(biāo)中尋找到最重要或最核心的部位進(jìn)行打擊，以起到意想不到的效果。因此，對(duì)通信網(wǎng)絡(luò)中各通信節(jié)點(diǎn)進(jìn)行重要性評(píng)估，準(zhǔn)確挖掘出網(wǎng)絡(luò)中的核心節(jié)點(diǎn)，可以為網(wǎng)絡(luò)抗毀性方面的研究提供重要的理論幫助。

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

1 通信網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估方法

通信網(wǎng)絡(luò)的鏈路連接情況可用有向圖G=(V,E)表示，其中V為節(jié)點(diǎn)，代表信息收發(fā)處理終端，E為邊，代表各終端的連接關(guān)系，并且約定任意兩個(gè)節(jié)點(diǎn)之間只有一條連邊，且不存在自環(huán)。同時(shí)注意到通信網(wǎng)絡(luò)是動(dòng)態(tài)變化的網(wǎng)絡(luò)，不斷有節(jié)點(diǎn)接入和退出，導(dǎo)致網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不斷變化。因此在分析通信網(wǎng)絡(luò)節(jié)點(diǎn)重要度時(shí)，首先從網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)入手，研究在某一時(shí)段穩(wěn)定的通信網(wǎng)絡(luò)各節(jié)點(diǎn)的重要度，再評(píng)估該時(shí)段通信網(wǎng)絡(luò)在整個(gè)通信時(shí)段的重要度，最后聚合得出全部通信節(jié)點(diǎn)在整個(gè)通信時(shí)段的重要度。通信網(wǎng)絡(luò)節(jié)點(diǎn)重要度的評(píng)估模型為：

其中g(shù)i為節(jié)點(diǎn)i在整個(gè)通信時(shí)段的重要度，hki為在第k時(shí)段的通信網(wǎng)絡(luò)中節(jié)點(diǎn)i的重要度，wk為k時(shí)段的通信網(wǎng)絡(luò)在整個(gè)通信時(shí)段的重要度，下面分別建立hki、wk的評(píng)估模型。

2 復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)重要度評(píng)估模型

建立hki的評(píng)估模型時(shí)借鑒復(fù)雜網(wǎng)絡(luò)的傳播機(jī)制，首先根據(jù)節(jié)點(diǎn)的實(shí)時(shí)負(fù)載和容量確定節(jié)點(diǎn)的實(shí)時(shí)狀態(tài)，再根據(jù)節(jié)點(diǎn)實(shí)時(shí)狀態(tài)建立節(jié)點(diǎn)失效后向臨近節(jié)點(diǎn)重分配負(fù)載的模型，最后根據(jù)節(jié)點(diǎn)負(fù)載重分配對(duì)臨近節(jié)點(diǎn)的震蕩程度評(píng)估節(jié)點(diǎn)的重要度。

2.1 節(jié)點(diǎn)狀態(tài)

節(jié)點(diǎn)狀態(tài)由可用節(jié)點(diǎn)能夠容納轉(zhuǎn)移負(fù)載的能力來(lái)表示，它由兩個(gè)方面的因素決定: 一是節(jié)點(diǎn)自身的負(fù)載剩余容納能力，二是相鄰節(jié)點(diǎn)的負(fù)載剩余容納能力。從上述描述的過(guò)程來(lái)看，它可以分為兩個(gè)階段，首先考慮節(jié)點(diǎn)剩余容納能力，假設(shè)節(jié)點(diǎn)i的實(shí)時(shí)負(fù)載為Qi，節(jié)點(diǎn)的容量為Ci，那么節(jié)點(diǎn)的負(fù)載剩余容納能力Ri可表示為：

即節(jié)點(diǎn)負(fù)載剩余容納能力為節(jié)點(diǎn)容量與現(xiàn)有負(fù)載的差值，當(dāng)負(fù)載超過(guò)容量時(shí)，其負(fù)載剩余容納能力為0，此時(shí)該節(jié)點(diǎn)已經(jīng)失效。節(jié)點(diǎn)負(fù)載剩余容納能力體現(xiàn)的是節(jié)點(diǎn)還能夠處理或者容納負(fù)載的能力，Ri值越大說(shuō)明其處理能力越強(qiáng)，在負(fù)載重分配時(shí)應(yīng)該占有優(yōu)勢(shì)，其分配的比例應(yīng)該越高，反之則越低，它是隨著節(jié)點(diǎn)負(fù)載的變化而不斷變化的。

考慮到相鄰節(jié)點(diǎn)負(fù)載剩余容納能力的影響，提出能夠更精確衡量節(jié)點(diǎn)負(fù)載剩余容納能力的節(jié)點(diǎn)狀態(tài)，該狀態(tài)是節(jié)點(diǎn)自身的負(fù)載剩余容納能力與相鄰節(jié)點(diǎn)負(fù)載剩余容納能力的有機(jī)結(jié)合，共同構(gòu)成了節(jié)點(diǎn)真實(shí)的負(fù)載剩余容納能力。對(duì)節(jié)點(diǎn)狀態(tài)的指標(biāo)進(jìn)行定義，如式（3）所示：

其中：Zi表示節(jié)點(diǎn)狀態(tài)；Ri表示節(jié)點(diǎn)裕度；Φi表示節(jié)點(diǎn)i的鄰接節(jié)點(diǎn)；λ為權(quán)重參數(shù)，通過(guò)調(diào)節(jié)λ的值可以調(diào)節(jié)整個(gè)節(jié)點(diǎn)狀態(tài)在負(fù)載重分配時(shí)所占的比例，當(dāng)時(shí)λ=0式（3）為局部負(fù)載均勻重分配。式（3）反映的是節(jié)點(diǎn)能夠容納負(fù)載的能力，它取自身節(jié)點(diǎn)負(fù)載剩余容納能力與相鄰節(jié)點(diǎn)負(fù)載剩余容納能力總和中的最小值，當(dāng)沒(méi)有相鄰節(jié)點(diǎn)時(shí)，節(jié)點(diǎn)負(fù)載剩余容納能力即為自身的節(jié)點(diǎn)負(fù)載剩余容納能力。

2.2 負(fù)載重分配

負(fù)載重分配方式是描述節(jié)點(diǎn)失效后其上的負(fù)載向網(wǎng)絡(luò)中其他節(jié)點(diǎn)進(jìn)行轉(zhuǎn)移的規(guī)則。負(fù)載重分配方式如圖1所示，節(jié)點(diǎn)失效后，原本通過(guò)該節(jié)點(diǎn)的負(fù)載信息流將會(huì)重新選擇通過(guò)路徑，其上的負(fù)載將會(huì)轉(zhuǎn)移到與之相鄰的節(jié)點(diǎn)，以保證整個(gè)網(wǎng)絡(luò)的有效運(yùn)行，整個(gè)網(wǎng)絡(luò)會(huì)由于節(jié)點(diǎn)的失效而進(jìn)行負(fù)載的全面更新，即Qi′=Qi+ΔQi，i∈Φf其中Qi為更新之前的負(fù)載，Qi′為更新之后的負(fù)載，ΔQi為更新時(shí)的增量，Φf為失效節(jié)點(diǎn)f的所有鄰接節(jié)點(diǎn)。

圖1 基于節(jié)點(diǎn)狀態(tài)演化的負(fù)載重分配方式

假設(shè)失效節(jié)點(diǎn)f的負(fù)載為Qf，相鄰節(jié)點(diǎn)的節(jié)點(diǎn)狀態(tài)為Zi，在相鄰節(jié)點(diǎn)上重新分配的負(fù)載增量可以用式（4）表示，它是對(duì)經(jīng)典近鄰重分配方式的改進(jìn)，它與節(jié)點(diǎn)狀態(tài)相關(guān)而不與節(jié)點(diǎn)負(fù)載相關(guān)。

2.3 節(jié)點(diǎn)重要度評(píng)估

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

其中，|Φf|為故障節(jié)點(diǎn)的所有近鄰節(jié)點(diǎn)數(shù)目。

3 通信網(wǎng)絡(luò)重要度評(píng)估模型

從時(shí)域的角度出發(fā)，某一拓?fù)浣Y(jié)構(gòu)通信網(wǎng)絡(luò)的重要度主要取決于以下兩點(diǎn)，一是該網(wǎng)絡(luò)所處的時(shí)間段在整個(gè)通信時(shí)段中的重要程度，如軍事通信中發(fā)起進(jìn)攻階段的通信網(wǎng)絡(luò)要比預(yù)先偵察階段的通信網(wǎng)絡(luò)重要；二是該網(wǎng)絡(luò)相對(duì)整個(gè)通信時(shí)段占據(jù)的時(shí)長(zhǎng)比例，如在通信網(wǎng)絡(luò)中經(jīng)常活躍的節(jié)點(diǎn)所承擔(dān)的信息處理任務(wù)較多，由這些節(jié)點(diǎn)構(gòu)成的網(wǎng)絡(luò)重要度較高，而活躍度較低的節(jié)點(diǎn)往往是備用節(jié)點(diǎn)或偏遠(yuǎn)節(jié)點(diǎn)，其重要度相對(duì)不高。以上述理論為依據(jù)提出通信網(wǎng)絡(luò)重要度評(píng)估模型，將通信時(shí)段劃分成不重疊的若干個(gè)時(shí)間片[9］，在每個(gè)時(shí)間片內(nèi)通信網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)不變，則將時(shí)段內(nèi)變化的通信網(wǎng)絡(luò)分解成基于多個(gè)時(shí)間片的靜態(tài)通信網(wǎng)絡(luò)，每個(gè)時(shí)間片對(duì)應(yīng)一個(gè)靜態(tài)的通信網(wǎng)絡(luò)結(jié)構(gòu)，且不同于前一時(shí)間片或后一時(shí)間片對(duì)應(yīng)的靜態(tài)通信網(wǎng)絡(luò)結(jié)構(gòu)，建立起時(shí)間片與某一拓?fù)浣Y(jié)構(gòu)通信網(wǎng)絡(luò)的對(duì)應(yīng)關(guān)系，并以時(shí)間片在通信時(shí)段內(nèi)的重要度和相對(duì)時(shí)長(zhǎng)作為片上通信網(wǎng)絡(luò)的重要度。

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

其中Tp≤bk＜Tp+1，Tp+X-1≤ek＜Tp+X，再進(jìn)行歸一化處理得出時(shí)間片k對(duì)應(yīng)的通信網(wǎng)絡(luò)重要度為

圖2 不同時(shí)間片對(duì)應(yīng)的通信網(wǎng)絡(luò)示意圖

4 網(wǎng)絡(luò)的構(gòu)建及節(jié)點(diǎn)重要性評(píng)估仿真實(shí)驗(yàn)

4.1 通信網(wǎng)絡(luò)構(gòu)建

本文在構(gòu)建實(shí)例分析所需的通信網(wǎng)絡(luò)時(shí)主要考慮到通信網(wǎng)絡(luò)的以下兩個(gè)特點(diǎn)，一是網(wǎng)絡(luò)的時(shí)變性，不斷有新節(jié)點(diǎn)接入和老節(jié)點(diǎn)退出；二是新節(jié)點(diǎn)往往選擇度值較大的數(shù)個(gè)老節(jié)點(diǎn)建立連接，退出的多是度值較低的節(jié)點(diǎn)。因此本文提出一種時(shí)變的隨機(jī)網(wǎng)絡(luò)模型，該模型的算法如下：

Step 1初始設(shè)定：首先建立一個(gè)具有j0個(gè)節(jié)點(diǎn)，鏈路節(jié)點(diǎn)比為S0的隨機(jī)網(wǎng)絡(luò)，并為每個(gè)節(jié)點(diǎn)按照1至j0編號(hào)。

Step 2增長(zhǎng)節(jié)點(diǎn)：每間隔B時(shí)間增加一個(gè)新節(jié)點(diǎn)O，在原節(jié)點(diǎn)最大編號(hào)上加1作為新節(jié)點(diǎn)的編號(hào)，并引出m≤j0條邊與之前網(wǎng)絡(luò)的m個(gè)節(jié)點(diǎn)相連，其中B～N(B0,σ21)，m～N(m0,σ22)。

Step 3擇優(yōu)連接：連接節(jié)點(diǎn)的選擇按照度值優(yōu)先原則進(jìn)行，選擇老節(jié)點(diǎn)i作為新邊連接節(jié)點(diǎn)的概率為:其中D(·)為節(jié)點(diǎn)度值。

Step 4退出節(jié)點(diǎn)：選擇度值最小的節(jié)點(diǎn)退出網(wǎng)絡(luò)，若度值最小的節(jié)點(diǎn)有多個(gè)則隨機(jī)選擇一個(gè)，節(jié)點(diǎn)退出后與其相連的鏈路全部斷開(kāi)。

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

4.2 實(shí)例分析

取上述時(shí)變隨機(jī)網(wǎng)絡(luò)模型中的參數(shù)j0=200，S0=3，B0=100s，m0=3，σ1=10s，σ2=1，σ3=60s，N=6，T1=0s，TN+1=3 600s，并設(shè)定每個(gè)節(jié)點(diǎn)的初始負(fù)載為Q0i=akγi，ki為節(jié)點(diǎn)的度a、γ為可調(diào)節(jié)參數(shù)控制初始負(fù)載的大小，為簡(jiǎn)化計(jì)算所有節(jié)點(diǎn)的a=1，γ=1，節(jié)點(diǎn)容量模型中η=0.07?；谇笆龅墓?jié)點(diǎn)重要度評(píng)價(jià)方法，排序結(jié)果見(jiàn)表1，表1僅展示排序前30位的節(jié)點(diǎn)。

表1 各時(shí)間片內(nèi)節(jié)點(diǎn)重要度

根據(jù)節(jié)點(diǎn)重要度排序結(jié)果，按照節(jié)點(diǎn)重要度從高到低依次從網(wǎng)絡(luò)中使該節(jié)點(diǎn)失效，并提出以失效影響度Ω(i)作為指標(biāo)，評(píng)估節(jié)點(diǎn)i失效后對(duì)整個(gè)通信時(shí)段網(wǎng)絡(luò)的影響程度，網(wǎng)絡(luò)失效結(jié)果如圖3所示。

圖3 通信網(wǎng)絡(luò)失效效果

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

其中ψi,j/200表示在時(shí)間片j對(duì)應(yīng)的網(wǎng)絡(luò)上節(jié)點(diǎn)i失效后所級(jí)聯(lián)失效的節(jié)點(diǎn)數(shù)量比例。該式綜合考慮了節(jié)點(diǎn)失效后在單個(gè)時(shí)間片上照成的影響，時(shí)間片在整個(gè)通信時(shí)段的重要性以及影響持續(xù)的時(shí)間，較為真實(shí)的反映節(jié)點(diǎn)失效后對(duì)整個(gè)通信的影響程度。

圖3中的橫坐標(biāo)為按照節(jié)點(diǎn)重要度排序的結(jié)果，從1到30依次失效，縱坐標(biāo)表示失效影響度。從圖中可以看出排序靠前的節(jié)點(diǎn)失效所引起的影響要明顯大于排序靠后的節(jié)點(diǎn)。對(duì)于該通信網(wǎng)絡(luò)來(lái)說(shuō)，此排序結(jié)果的失效效果很好，排序最靠前的10個(gè)節(jié)點(diǎn)，均表現(xiàn)出來(lái)在此網(wǎng)絡(luò)參數(shù)和節(jié)點(diǎn)參數(shù)下的良好失效效果; 而排序靠后的其余節(jié)點(diǎn)失效效果較差。以此證明，對(duì)于這種網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，本文的排序方法較為適合。

5 結(jié) 語(yǔ)

本文提出的通信網(wǎng)絡(luò)節(jié)點(diǎn)重要程度評(píng)估模型，在傳統(tǒng)評(píng)估模型的基礎(chǔ)上，考慮了不同通信時(shí)段重要程度及時(shí)長(zhǎng)對(duì)節(jié)點(diǎn)重要程度的影響，同時(shí)兼顧考慮了節(jié)點(diǎn)在網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)中位置重要程度，節(jié)點(diǎn)在網(wǎng)絡(luò)傳播中的重要程度，相對(duì)較為真實(shí)的定量反映節(jié)點(diǎn)的重要度，為通信網(wǎng)絡(luò)關(guān)鍵節(jié)點(diǎn)的發(fā)現(xiàn)和保護(hù)提供一定幫助。但是在評(píng)估模型中對(duì)各節(jié)點(diǎn)的功能和業(yè)務(wù)并未進(jìn)行區(qū)分，這將是下一步研究的重點(diǎn)。