网络抗毁度和节点重要性评价方法_饶育萍

计 算 机 工 程 第 35 卷 第6期

Vol.35 No.6 Computer Engineering ·博士论文·

文章编号：1000—3428(2009)06—0014—03

文献标识码：A

2009年3月

March 2009

中图分类号：TN915.02

网络抗毁度和节点重要性评价方法

饶育萍，林竞羽，周东方

(解放军信息工程大学信息工程学院，郑州 450002)

摘 要：针对现有评价模型无法准确评价某些典型网络抗毁度和节点重要性的问题，提出一种基于全网平均等效最短路径数的网络抗毁评价模型，全网平均等效最短路越多，网络的抗毁能力越强。在此基础上，提出一种节点重要性评价方法，如果节点失效后网络抗毁度下降越多，则该节点在网络中的重要性越大。

关键词：网络拓扑；抗毁度；平均等效最短路；节点重要性

Method for Network Invulnerability and Node Importance Evaluation

RAO Yu-ping, LIN Jing-yu, ZHOU Dong-fang

(College of Information Engineering, PLA Information Engineering University, Zhengzhou 450002)

【Abstract 】Compared with the topology of full-connected network, a method for evaluating network invulnerability is proposed based on averageequivalent shortest way. It shows that the more the average equivalent shortest ways are, the better the network invulnerability is. Amethod toevaluate node importance is proposed based on invulnerability degradation percentage after one node being destroyed. The larger the percentage is,the more important the node is.

【Key words】network topology; invulnerability; average equivalent shortest way; node importance

网络抗毁性[1-3]和节点重要性[4-5]在通信网的可靠性分析和设计中具有重要意义。国内外有不少文献就网络拓扑结构的抗毁测度进行了论述，主要有粘聚度和连通度[6]、坚韧 度[7]、网络结构熵[8]、节点抗毁测度均方差[9]以及跳面节点 法[10]等，节点重要性的评价方法主要有基于生成树数目的方法[11]等。研究发现，上述方法不具有普遍适用性，特别是对某些特殊网络的抗毁度评价和节点重要性评价会得到不正确的评价结果，本文对此进行分析，提出一种基于全网平均等效最短路径数的网络抗毁度评价方法，以及基于网络抗毁度下降比例的节点重要性评价方法。

µ=∑

(N −2)!

t =1(N −t −1)!

k

1 基于全网平均等效最短路径数的网络抗毁度

网络节点之间进行通信的首选路是最短路，只有最短路不可用的情况下才会选择次短路或其他更长的路，在通信网可能遭受攻击和破坏的情况下，节点间的最短路越多，则在某些最短路遭到破坏后仍能以最短路进行通信的可能性就越大，因此，节点之间最短路径的数量对于通信网的可靠性或抗毁性具有重要意义。全连通网络的抗毁能力是最强的，其他任意一种网络的抗毁能力将取决于网络自身结构与全连通网络的差异。本文考察任意网络节点间的最短路径长度和条数，并与全连通网络进行比较，以此为依据来衡量网络的抗毁能力。

对于一个N 节点的全连通网络，任意节点之间长度为 k (k ≤N -1) 的路共有µ0条，且

k −1

µ0=C N −2=

对于一个N 节点网络，假设任意节点i 和j 之间最短路

长度是k 且最短路径数为x 条，如果节点之间直接相连，定有x /µ=1，否则x /µ

定义1 节点间的等效最短路径数等于节点间最短路径(假设该最短路径长度为k ) 的数量与全连通网络节点间长度不大于k 的路的数量之比，记为y =x /µ。

其中，1/µ称为最短路径数等效系数。显然，0≤y ≤1，当且仅当2个节点直接相连时，等效最短路径数y 取得最 大值1。

本文提出一种基于全网平均等效最短路径数的网络抗毁度计算方法，它反映了整个网络的紧凑程度，体现了由于与全连通网络的结构差异导致的抗毁能力降低。

定义2 网络抗毁度等于全网的平均等效最短路径数， 记为

Inv=M/L

基金项目：国家“863”计划基金资助项目(AA06002002)

作者简介：饶育萍(1979－) ，女，博士研究生，主研方向：军事通信；林竞羽，讲师；周东方，教授

收稿日期：2008-08-19 E-mail ：[email protected]

(N −2)!

(N −k −1)!

任意节点之间长度不大于k 的路共有µ条，且

—14—

其中，M =∑∑y ij 表示全网所有节点之间的等效最短路径

i =1j =i +1

N −1N

数量之和；L =N (N -1)/2表示N 节点网络可建立连接的节点对数目。

对于N 节点全连通网络，L =N (N -1)/2，每对节点间的等效最短路径数为y =1，因此，M =N (N -1)/2, Inv =1，具有最强的抗毁能力；对于非全连通网络，L =N (N -1)/2，仅部分直连节点间的等效最短路径数y =1，其余y

例：8个节点16条链路的网络拓扑图G1如图1所示。

的重要性，一类是从节点失效对网络产生的破坏效果来衡量节点的重要性，即破坏性角度，如生成树数目法；另一类是从节点正常工作对网络的建设作用来衡量节点的重要性，即建设性角度，如跳面节点法和节点收缩法。经研究发现，这些方法对于某些结构的网络评价不正确，可见方法存在局限性，具体分析如下。

(1)当网络存在多个割点时，生成树数目法无法区分各个割点的相对重要性。由于任意一个割点失效，网络都将不连通，生成树数目都为0，因此该法评价所有割点的重要性都是相同的，它没有考虑到网络的坚韧度[7]，即节点失效后连通分支数具体情况。对于图3所示网络，关于割点1和割 点3的相对重要性，生成树数目法评价结果为两者的重要性相同，而实际上，当节点1失效后，网络离解成3个分支，最大连通分支的节点数为3，节点3失效后，网络只离解成 2个分支，最大连通分支的节点数为4，可见节点1比节点3失效后的破坏效果更严重，因此，节点1比节点3更重要。

图1 8个节点16条链路的网络拓扑图G1

8个节点16条链路的网络拓扑图G2如图2所示。

图3 多个节割点的网络拓扑图

图2 8个节点16条链路的网络拓扑图G2

评价图1和图2所示匀对称网络的抗毁度，用P 1, P 2分别表示节点间长度为1, 2的最短路径数矩阵，对G1有：

⎡4 0 0 2 2 2 0 0⎤⎡0 1 1 0 0 0 1 1⎤

⎢0 4 0 0 2 2 2 0⎥⎢1 0 1 1 0 0 0 1⎥

⎢⎥⎢⎥

⎢0 0 4 0 0 2 2 2⎥⎢1 1 0 1 1 0 0 0⎥

⎢⎥⎢⎥

2 0 0 4 0 0 2 2⎥0 1 1 0 1 1 0 0⎥⎢⎢k =1, µ=1,P 1=⎢; k=2, µ=7,P 2=⎢ 2 2 0 0 4 0 0 2⎥0 0 1 1 0 1 1 0⎥

⎢⎥⎢⎥

⎢2 2 2 0 0 4 0 0⎥⎢0 0 0 1 1 0 1 1⎥

⎢0 2 2 2 0 0 4 0⎥⎢1 0 0 0 1 1 0 1⎥

⎢⎥⎢⎥

⎢⎥⎢⎥0 0 2 2 2 0 0 41 1 0 0 0 1 1 0⎣⎦⎣⎦

(2)跳面节点法只能体现跳面数、跳面节点数以及跳面间

链路数，当这三者都相同时即认为2个节点具有相同的重要性，不能反映出节点之间连接的细节。以图4所示网络为例，跳面节点法评价结果为节点6和节点7的相对重要性相同，这个结论显然是不正确的，因为节点7为网络割点，一旦失效则网络变得不连通，而节点6为非割点，即使失效全网仍保持连通，因此，节点7比节点6重要。

图4 通信网络拓扑图

网络抗毁度：Inv=M/L=(1×16+2/7×12)/28=0.693 9。 对G2有：

⎤⎡0 1 0 1 0 1 01⎡4 0 0 4 4 4 0 0⎤

⎢1 0 1 0 1 0 1 0⎥⎢0 4 0 0 4 4 4 0⎥⎢⎥⎢⎥⎢0 1 0 1 0 1 0 1⎥⎢0 0 4 0 0 4 4 4⎥⎢⎥⎢⎥1 0 1 0 1 0 1 0⎥4 0 0 4 0 0 4 4⎥⎢⎢k =1, µ=1, P ; k =2, µ=7,P 2=⎢ 1=⎢

0 1 0 1 0 1 0 1⎥4 4 0 0 4 0 0 4⎥⎢⎥⎢⎥⎢1 0 1 0 1 0 1 0⎥⎢4 4 4 0 0 4 0 0⎥⎢0 1 0 1 0 1 0 1⎥⎢0 4 4 4 0 0 4 0⎥⎢⎥⎢⎥⎢⎥⎢⎥1 0 1 0 1 0 1 00 0 4 4 4 0 0 4⎣⎦⎣⎦

(3)节点收缩法、生成树数目法和跳面节点法只适用于连

通网络，不能在非连通网络中评价节点重要性。如图5所示，节点1被破坏后，仍须对剩余7个节点的相对重要性进行评估。节点收缩法、生成树数目法和跳面节点法的计算方法都要求网络是连通的，因此，只能分别对每个连通子网各自的节点重要性作出评价，而不能区分处于不同子网中节点的相对重要性，例如无法评价节点2和节点3的相对重要性。

网络抗毁度：Inv=M/L =(1×16+4/7×12)/28=0.816 3。 结论：网络G2的抗毁能力强于G1，结论与利用文献[10]方法的计算结果相同。

图5 非连通网络拓扑图

2 节点重要性评价方法

2.1 现有节点重要性评价方法缺陷分析

现有节点重要性评价方法分别从不同的角度衡量了节点

2.2 节点重要性评价新方法

在衡量节点重要性时，通常考察的是节点失效后对网络造成的破坏程度，按破坏程度大小衡量节点的重要性，这样的评价思想是科学合理的。节点失效对网络拓扑造成的破坏

—15—

效果可以从多个方面来衡量，如生成树数目法体现了节点失效造成网络生成树数目的减少，节点收缩法虽然从建设性角度评估节点重要性，但它隐含了某些重要节点失效会造成节点间距离(跳数) 增大的事实。实际上还有一种破坏效果值得考虑，即节点间最短路径数的减少以及由此造成的网络抗毁能力下降，本文的评价方法就是从这种破坏角度出发，将节点失效后的网络抗毁度与原网络抗毁度进行比较，抗毁度下降越多的节点其重要性越大。程序步骤如下：

(1)根据网络拓扑图，输入N 个节点的网络邻接矩阵R ； (2)计算任意节点对之间的最短路长k 和等效最短路径数µij ； (3)计算任意节点的等效最短路径数µi ； (4)计算网络抗毁度Inv ； (5)令失效节点序数h=1；

即删除该节点的所有链路，(6)将邻接阵的第h 行h 列元素置零，重复(2)~(4)；

(7)h=h+1，重复(6)，直至h=N；

即节点重要性排序。 (8)各节点失效后网络抗毁度下降比例排序，

网络仍有2个连通分支，只有1个节点被孤立，显然节点2

失效后的破坏效果大。

3 结束语

本文对国内外已有的网络抗毁评价方法和节点重要性评价方法的不足之处进行分析，提出基于全网平均等效最短路径数的网络抗毁评估模型，该模型反映了由于与全连通网络的拓扑结构差异导致的网络抗毁能力下降，能准确评价网络的抗毁性能。从破坏性的角度建立了网络节点重要性的评价模型，将节点失效等效为保留节点删除链路，如果节点失效后网络抗毁度下降比例越大，则认为该节点越重要，该方法能准确反映节点之间连接的细节，具有普遍适用性。

参考文献

[1] 钟联炯. 通信网络拓扑抗毁性算法[J]. 火力与控制指挥, 2003,

28(3): 113-114.

[2] 吴 俊. 复杂网络抗毁性测度研究[J]. 系统工程学报, 2005,

20(2): 128-131.

[3] Kang Haizhuang, Butler C, Yang Qingping. A New Survivability

Measure for Military Communication Networks[C]//Proceedings of IEEE MILCOM’98. Boston, MA, USA: [s. n.], 1998.

[4] 李鹏翔. 网络节点(集) 重要性的一种度量指标[J]. 系统工程,

2004, 22(4): 13-20.

[5] Newport K T, Schroeder M A, Whittaker G M. Techniques for

Evaluating the Nodal Survivability of Large Networks[C]//Proc. of IEEE MILCOM’90. Monterey, California, USA: [s. n.], 1990. [6] Frank H, Frisch I. Analysis and Design of Survivable Network[J].

IEEE Trans. on Communication Technology, 1970, 18(5): 567-662. [7] Chvatal V. Tough Graphs and Hamiltonian Circuits[J]. Discrete

Mathematics, 1973, (5): 215-228.

[8] Lin W, Varshney P K. On Survivability Measures for Military

Networks[C]//Proc. of IEEE MILCOM’90. Monterey, California, USA: [s. n.], 1990.

[9] 陈建国. 通信网络拓扑抗毁性评估算法研究[J]. 通信系统与网

络技术, 2006, 32(1): 6-7.

[10] 郭 伟. 野战地域通信网可靠性的评价方法[J]. 电子学报,

2000, 28(1): 3-6.

[11] 陈 勇. 通信网中节点重要性的评价方法[J]. 通信学报, 2004,

25(8): 129-134.

特别注意步骤(6)，节点失效后并非将该节点删除，而是将其保留在网络中而将其所有链路删除，由于保留了节点，在相同节点数的条件下与原网络的抗毁度进行比较，保证了节点失效会导致网络抗毁度计算值下降，这样就可以用节点失效后网络抗毁度的下降程度来评价节点的重要性。

相对生成树数目法，该评价方法能对多个割点的重要性加以区分，例如对图3所示网络节点重要性的评价结果见 表1，节点1失效后网络抗毁度下降72.60%，节点3失效后网络抗毁度仅下降55.16%，准确评价出节点1比节点3重要。

表1 对图3所示网络的节点重要性排序

失效节点 13 6 4 5 2

网络抗毁度下降比例/(%)

72.6055.16 38.74 27.02 27.02 25.26

相对跳面节点法，抗毁度下降比例法能够反映节点连接的细节，例如，对图4所示网络，该方法准确评价出节点7为全网最重要的节点；该方法还可以对非连通网络的节点重要性进行准确评价，例如对图5所示网络，该方法准确评价出节点2比节点3重要，这是因为节点2失效后网络只剩下一个连通分支，有4个节点被孤立，而节点3(7或8) 失效后

编辑 顾姣健

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

(上接第13页)

参考文献

[1] Schilit B, Theimer M. Disseminating Active Map Information to

Mobile Hosts[J]. IEEE Network, 1994, 8(5): 22-32.

[2] Ryan N, Pascoe J, Morse D. Enhanced Reality Fieldwork: The

Context-aware Archeological Assistant[M]//Gaffney V, Leusen M, Exxon S. Computer Applications in Archeology. Oxford, UK: British Archaelogical Reports, 1997.

[3] Dey A, Abowd G D, Salber D. A Context-based Infrastructure for

Smart Environments[C]//Proc. of MANSE’99. Dublin, Ireland: Springer Verlag, 1999.

[4] Petzold F, Trumler B W, Ungerer T. Context Prediction Based on

Branch Prediction Methods[EB/OL]. (2003-07-20). http://www. informatik.uni-augsburg.de/skripts/techreports/.

[5] Mayrhofer R, Radi H, Ferscha A. Recognizing and Predicting

Context by Learning from User Behaviour[C]//Proc. of MoMM’03. [S. l.]: IEEE Computer Society, 2003.

[6] Sigg S, Haseloff S, Klaus D. Context Prediction by Alignment

Methods[C]//Proc. of MOBISYS’06. Uppsala, Sweden: [s. n.], 2006.

编辑 张 帆

—16—