一種通信網絡抗毀性評價的改進模型

蔡瑾曜，吳玲達

1.裝備學院 研究生管理大隊，北京 101416 2.裝備學院 重點實驗室，北京 101416

一種通信網絡抗毀性評價的改進模型

蔡瑾曜1，吳玲達2

1.裝備學院 研究生管理大隊，北京 101416 2.裝備學院 重點實驗室，北京 101416

1 引言

現代信息化條件下的高技術戰爭已經從平臺中心站轉向網絡中心站，未來戰爭中網絡化作戰模式越來越受到重視。然而隨著信息網絡技術的發展，針對通信網絡的攻擊也急劇上升，使得網絡可靠性和安全度[1]大大下降，網絡戰爭已經成為影響戰爭勝負的關鍵[2-3]。通信網絡是網絡化戰爭中最基本、最基礎的研究內容之一，同時，通信網絡往往是敵方打擊的首選目標。因此通信網絡如何在復雜的戰場環境中滿足戰場通信要求，將在現代化戰爭中起到關鍵作用。

網絡的抗毀性是從圖論的概念中提出并發展而來的，在通信網的抗毀性分析中得到廣泛應用，尤其在軍事通信網中更是一個非常重要的概念。對于一個網絡而言，網絡抗毀性是指：當網絡中出現確定性或隨機性故障時，網絡維持或恢復性能達到可接受程度的能力。確定一種定量有效的評價方法，是實現上述分析通信網的抗毀性能的基礎。

針對現有的一些通信網抗毀性分析成果存在無法正確評價節點重要度，以及不能滿足不同節點數的網絡間的抗毀性分析與比較等不足，本文在已有的分析方法基礎上，給出了一種基于節點的網絡抗毀性評價改進方法，并驗證了該方法的有效性。

2 現有通信網抗毀性評價方法概述

網絡抗毀性能[4-6]和節點重要性[7-9]在通信網的分析和設計中具有重要意義。國內外有不少文獻就網絡拓撲結構的抗毀測度進行了論述，主要有基于割集信息、最小割集或最弱割集的全局性網絡拓撲結構抗毀性度量[4]，基于熵的網絡拓撲結構抗毀性度量[5]，基于節點的抗毀性度量值均方差的評估模型[6]和跳面節點法[7]等。節點重要性的評價方法主要有生成數目法[8]、網絡凝聚度[9]、最短路徑法等。研究發現，上述模型和方法各有其評估側重點，也各有其局限所在，不具有普遍適用性。

通過深入研究文獻[10]中抗毀性評價模型，發現利用跳面節點法來計算節點重要度不具有普遍適用性。跳面節點法只能體現跳面數、跳面節點數以及跳面間鏈路數，當這三者都相同時即認為兩個節點具有相同的重要性，但并不能完完全全反映出各節點之間連接的細節。以圖1所示的網絡為例，跳面節點法的評價結果為節點2和節點5的相對重要性相同，顯然不正確。因為節點5為網絡割點，一旦失效則導致網絡變得不連通，而節點2為非割點，即使失效全網仍保持連通，因此，節點5比節點2重要。

圖1 通信網絡拓撲結構圖

另外，該抗毀性評價模型只能對某一個網絡進行抗毀性評價或者是對節點數相同的不同網絡之間進行評價，而無法對節點數不同的通信網絡之間進行抗毀性能比較。針對上述兩方面的不足，本文首先給出了基于最短路徑數和跳面節點法節點重要性多指標評價方法，同時提出了一種基于節點的全網平均等效抗毀性測度的網絡抗毀性評價模型，對不同節點數的網絡進行抗毀性評價，全網平均等效抗毀性測度值越大，網絡的抗毀能力越強。

3 基于節點的通信網抗毀性改進模型

3.1 全網平均等效抗毀性測度

經過實驗分析，發現文獻[11]中模型對不同節點數的網絡進行抗毀性評價時不具有可操作性。因為節點數大的網絡必然比節點數小的網絡要多出它們節點數之差的CM(k)值，這樣就無法評價它們之間抗毀性的強弱。我們發現全連通網絡是結構最優的網絡，也是抗毀性最強的網絡，只是基于建設成本和運行效率等因素的考慮，現實中的網絡很少采用全連通網絡結構。本文研究發現，可以將網絡抗毀性評價的著眼點放在實際網絡與全連通網絡的結構差異上，由此，在上述模型的基礎上提出了一種基于節點的全網平均等效抗毀性測度的網絡抗毀性評價模型。

假定給定網絡節點的數量是N，那么網絡抗毀性的測度指標[11]定義式為：

CM(0)為網絡G的連通度；CM(k)為從網絡中刪除一個重要節點后所得到的網絡的連通度；n是使網絡完全失去連接（所有的節點都是孤立的，彼此沒有連接）之前必須刪除的節點的數量。CM(k)由下式給出：

其中，NCk(i，j)是網絡Gk中節點i與節點j的連通度；n-k是Gk的節點數；x是節點i與節點j之間獨立路徑的數目；JN(t)是這些路徑的跳數。將式（2）和（3）帶入式（1）計算出SM(G)的值，對網絡的抗毀性進行評價。

在此基礎上，給出網絡抗毀性測度的新指標即抗毀性測度均值和全網平均等效抗毀性測度。

定義1

P定義為網絡抗毀性測度均值，N為該網絡的結點個數，i是總共刪除節點的個數。對于一個節點數為N的全連通網絡，按照上面抗毀性測度的算法易知：

定義2全網平均等效抗毀性測度指標定義為：

由于全連通網絡的特性，所以對于確定節點數的任意結構的網絡，全連通網絡的網絡抗毀性測度是最大的，式（8）的分子就是全連通網絡的網絡抗毀性測度。因而任意非連通網絡的等效抗毀性測度0≤D＜1，D的值越大，網絡抗毀性越強。這樣任意的網絡的抗毀性都可歸結為全網平均等效抗毀性測度這一指標，就解決了節點數不同網絡之間抗毀性比較的問題。

3.2 節點重要性評價改進方法

在進行網絡抗毀性分析時，對節點重要度的評價是十分重要的一環。如果不能正確評價節點重要度，將導致上述方法計算的抗毀性值比實際偏大，影響分析結果。通常情況下把節點的度數作為衡量重要性的指標，認為與該節點直接連接的邊越多該點重要度就越大。但是這種思想往往忽略了節點和節點之間的連接情況，是不完備的。假設一個節點的度數不是所有節點中最高的，但它到其他各節點之間的路徑數都非常短，這表明該節點與其他節點聯系都很緊密，處于核心的位置，則該節點一旦被攻擊整個通信網絡就會癱瘓，此節點的重要性不言而喻。

前文已經闡述了利用跳面節點法來評價節點重要性的缺陷，這里將基于最短路徑數的方法[12]與跳面節點法結合起來，進行多指標評價。深入研究發現，最短路徑數方法雖然能解決跳面節點法對于節點之間連接細節的缺陷，但是它只考慮了最短路徑數目，舍棄了其他更長的迂回路徑，對節點數相對較多的網絡結構的判斷會失去精度；而跳面節點法則能體現跳面數、跳面節點數以及跳面間鏈路數，對節點數較大，結構較復雜的網絡分析更具有層次感，能彌補最短路徑法的不足。

下面給出了節點重要度地加權指標值的定義為：

Inv是最短路徑數的節點重要性指標；Si是跳面節點法的節點重要性指標；α和β分別是它們的權值。則節點重要度就可以用指標Mv來確定。

基于最短路徑數方法的節點重要度定義為：

其中，Ri為基于最短路徑數的節點重要度；λi為節點i的權重值。這里給出等效最短路徑數的定義：

對于一個N節點的網絡，如果節點i與節點j之間有mij條長度為kmin的最短路徑，則節點i與節點j之間的等效最短路徑數為：

其中，μ(kmin)是相應N節點全連通網絡中節點間不大于kmin步的路徑數。顯然，0＜imij≤1，當且僅當兩節點之間有直連邊時，imij=1。對于任意的i與j，若imij=1，則為全連通網絡。

跳面節點法的節點重要度定義為：

式中，n為第m跳面上的節點數目；第(m+1)跳面上的節點數目為n(m+1)，2跳面的連接鏈路數為lm。

對于α和β值的確定，給出如下處理方法：

網絡節點數N＜10，α=0.7；相反α=0.3。

3.3 基于節點的通信網改進模型標準和流程

本文將通信網的攻擊看成是通信網絡節點和鏈路逐步失效的過程。對通信網抗毀性能的分析除了考慮網絡節點完整時的抗毀性能，還包括了節點逐個失效時它們的抗毀性能，并將節點完整和節點逐步失效時的連通性能之和作為整個網絡抗毀性的度量值，從而得出全網平均等效抗毀性測度D，D越大則認為抗毀性越強。

為了便于計算仿真，假設通信網絡中的節點只有兩種工作狀態，即工作和失效。網絡中節點工作狀態也是相互獨立的，彼此不受影響。通信網抗毀性分析程序步驟如下：

（1）根據網絡拓撲圖，輸入當時拓撲結構中N個節點的網絡鄰接矩陣R。

（2）計算任意節點對之間的最短路長k和等效最短路徑數。

（3）計算此時通信網絡的連通性能（連通度）。

（4）計算通信網絡各節點的重要度，并刪除最重要的一個節點。

（5）判斷是否所有節點都孤立，若不是，轉到步驟1；若是，轉到步驟（6）。

（6）計算所有連通度之和。

（7）得出全網平均等效抗毀性測度D。

圖2給出了基于節點的通信網改進模型的流程圖。

圖2 改進模型流程圖

4 實驗分析

現有兩個實際電力通信網絡G1和G2，拓撲結構如圖3、4所示，分別對它們進行網絡的抗毀性計算。為了便于仿真實現，限定本文所有節點和鏈路的權重λi為1，同時在節點刪除過程中，與之相連的鏈路也隨之失效。

圖3 G1網絡拓撲結構圖

圖4 G2網絡拓撲結構圖

利用3.3節中的計算流程對G1、G2的分析結果，分別如表1和表2所示。

從實驗分析結果中可以看出網絡G1抗毀性比G2強，這是由于G2中節點4、5是處于上下層中間的兩個關鍵節點，一旦被攻擊，整個拓撲結構就會上下不能兼顧，網絡就會陷入癱瘓，G2的抗毀性很差。顯然G1抗毀性比G2強，符合實際情況。

在這里對圖1所示通信網絡進行節點重要度評價，利用本文描述的方法得出節點5的重要度比節點2高，這顯然是與實際相符的。如果利用跳面節點法來評價節點重要度，則會認為節點2和5重要度一樣，再對其抗毀性測度計算時，會出現很大偏差，因為如果第一次刪除的節點不是最重要的節點，那么最終計算得到的抗毀性測度會偏大與實際不符。如圖1網絡所示，因節點重要度評價不準而先刪除了節點2最終得到網絡抗毀測度SM=55.716 7；而利用改進的節點重要度評價算法最終計算得到的抗毀性測度SM*=51.933 3。顯然，原方法夸大了通信網路的抗毀性，給實驗分析帶來了誤差。

表1 G1網絡抗毀性測度計算

表2 G2網絡抗毀性測度計算

5 結束語

本文在以網絡抗毀性測度分析模型的基礎上，指出了現在此模型中利用跳面節點法評價節點重要度的缺陷和不足，結合基于最短路徑數的方法對該模型進行完善；同時提出了一種基于節點的全網平均等效抗毀性測度的網絡抗毀性評價模型，可以較有效地對不同節點數目的網絡進行抗毀性分析和相互比較，為評價通信網絡的抗毀性提供了一個可靠的定量標準和簡單有效的計算方法。本文提出的方法全都是基于無權網絡，而實際的網絡往往涉及很多其他因素，下一步可以結合節點本身重要度和抗毀性以及鏈路傳輸寬帶和速度等因素，綜合評價網絡抗毀性。

[1]譚小彬.基于多層次多角度分析的網絡安全態勢分析[J].信息網絡安，2008（11）：56-63.

[2]葉征.淺析網絡戰爭[J].國際電子戰，2009（6）：12-13.

[3]陶陶.未來戰爭網絡決定勝負[J].科學之友，2009（3）：90-91.

[4]Lin W，Varshney P K.On survivability measures for military networks[C]//Proceedings of the IEEE Communications Conference.[S.l.]：IEEE Press，1990：1120-1124.

[5]Schroeder M A，Newport K T.Tactical network survivability through connectivity optimization[C]//Proceedings of the IEEE Military Communications Conference.[S.l.]：IEEE Press，1987：590-597.

[6]陳建國，張永靜.通信網絡拓撲抗毀性評估算法研究[J].通信系統與網絡技術，2006，32（1）：6-7.

[7]郭偉.野戰地域通信網可靠性的評價方法[J].電子學報，2000，28（1）：3-6.

[8]陳勇，胡愛群，胡嘯.通信網絡中節點重要性的評價方法[J].通信學報，2004，25（8）：129-134.

[9]譚躍進，吳俊，鄧宏鐘.復雜網絡中節點重要度評估的收縮方法[J].系統工程理論與實踐，2006（11）：79-83.

[10]唐新強.基于節點的地域通信網抗毀性評價及應用[J].通信系統與網絡技術，2008，34（2）：11-15.

[11]Kang H，Butler C，Yang Q.A new survivability measure for military communication networks[C]//Proceedings of IEEE MILCOM’98，Boston，MA，USA，1998：71-75.

[12]繞育萍，林競羽，侯德亭.基于最短路徑數的網絡抗毀性評價方法[J].通信學報，2009，30（4）：113-118.

[13]張琨，談革新，莊克琛.復雜網絡抗毀性測度研究綜述[J].計算機時代，2010（5）：5-7.

CAI Jinyao1,WU Lingda2

1.Graduate Management Team,Academy of Equipment,Beijing 101416,China
2.The Key Laboratory,Academy of Equipment,Beijing 101416,China

Deeply analyzing the requirements of invulnerability evaluation on communication network,and according to the problem that the existing invulnerability evaluation model is unable to evaluate invulnerability measure node importance and the invulnerability on networks of different numbers of nodes,an improvement is made combined with the evaluation method of node importance with respect to multiple performance measures based on the shortest route number.In addition,an invulnerability measure evaluation model of whole network average equivalent based on nodes is proposed with it,which is validated to be effective.

network topology;node importance;shortest route;invulnerability measure

分析了現代戰場通信網抗毀性評價的需求，針對現有通信網抗毀性測度評價模型無法準確評價網絡抗毀性測度和節點重要性，以及不同節點數的網絡間抗毀性的問題，利用基于最短路徑數和跳面節點法節點重要性多指標評價方法對該模型進行改進。在此基礎上，提出一種基于節點的全網平均等效抗毀性測度的網絡抗毀性評價模型，并驗證了模型的有效性。

網絡拓撲；節點重要性；最短路徑；抗毀性測度

A

TN915.02

10.3778/j.issn.1002-8331.1112-0611

CAI Jinyao,WU Lingda.Improved invulnerability evaluation model on communication network.Computer Engineering and Applications,2013,49（13）：85-88.

蔡瑾曜（1988—），男，碩士研究生，主要研究領域為：天基通信網抗毀性。E-mail：caijinyao_52@163.com

2012-01-09

2012-04-09

1002-8331（2013）13-0085-04

CNKI出版日期：2012-05-21http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1137.008.html