《1 前言》

1 前言

网络规模日趋庞大，行为日趋复杂，网络可靠性的研究显得非常重要。对通信网链路的重要性进行评价，是通信网系统可靠性研究的方向之一。由于人为因素和自然因素，通信网链路容易发生故障，对通信网的可靠性造成影响。当多条链路同时发生故障时，需要考虑如何确定维修的先后顺序，使通信网遭受的损失最小。或者在设计网络时，需要对网络中某些链路重点维护，减少故障，以提高整个通信网的可靠性。

笔者对现有的链路重要性的评价准则进行了归纳：a. 最短路径法[1~4]；b.可靠性多项式法[5]；c. 最小路集－割集法[5]；d. 最小生成树权重法[6,7]；e. 生成树数目法[8-10]。最短路径法[1~4]固定地选取源汇节点，只能评价属于此最短路径的链路的重要性，无法进行全网范围的链路重要性评估。最小生成树权重法[6,7]在预先假定链路权重的情况下，才能进行重要性评价，因此重要性与权重密切相关，而文献[6,7]中的权重是预先任意给定的。文献[5]证明了最小路集－割集法没有可靠性多项式法准确。但可靠性多项式法[5]需要逐一进行链路重要性的两两比较，才能产生全网的链路重要性排序，并且无法获得某些链路间的重要性关系。

目前研究者提出的链路重要性评价方法都基于这样一个评价准则：最重要的链路是其删除后造成网络性能的最大衰减，如最短路径或生成树数目，等等。链路删除法的最大问题是，当链路的删除使得网络不连通或在评价串联链路时，这些链路的重要性完全相同，而从直观判断，它们的重要性存在差别。虽然生成树数目法[10]和可靠性多项式法[5]是以链路收缩法为评价准则，文献[10,11]证明了链路收缩和删除对于生成树数目法和可靠性多项式法的等价性。因此，目前的链路重要性主要评价方法都存在此问题。

为了克服上述问题，笔者提出了一种基于网络传输特性的通信网链路重要性评价方法，根据链路在网络所有节点相互通信的最短路径中的使用频度来评价链路重要性，最重要链路的使用频度最高。其充分考虑了链路对网络通信的贡献，而且不需要像其他链路重要性评价方法那样进行链路收缩和删除，直接反映了链路对网络的影响，并对重要性进行了归一化，可以判断通信网中任意两条链路的相对重要性。 通过与其他算法的比较，传输特性法更加直观合理地评价了全网范围内的链路重要性，直接有效地反映了链路对网络传输特性的影响。

《2 网络模型与符号》

2 网络模型与符号

《2.1 网络模型》

2.1 网络模型

通信网用图 G ＝（V，E） 来表示，假设 G 为无自环的无向连通图，有 n 个节点，m 条链路。V ＝｛x1 ，x2 ，…，xn ｝ 代表节点集合， E ＝｛e1 ，e2 ，…，em ｝ 代表链路集合。每条链路的距离和权重相同。所有节点的重要性相同，所有节点对间的通信重要性相同。

《2.2 网络符号》

2.2 网络符号

Rel（G） ：网络 G 的全网可靠性，即所有节点能通过可执行链路通信的概率。

p ：链路可靠性， 0 ＜ p  ＜ 1

G－ei ：网络 G 中链路 ei 删除后得到的网络

G * ei ：网络 G 中链路 ei 收缩后得到的网络

ei ＞ ej ：链路 ei 比 ej 重要

xi → xj ：节点 i 到节点 j 的最短路径

《3 基于网络传输性能的链路重要性评价方法》

3 基于网络传输性能的链路重要性评价方法

《3.1 传输特性法的提出和描述》

3.1 传输特性法的提出和描述

在实际网络通信中，数据包通常优先选择最短路径进行数据传输，最短路径中包含的链路对数据传输的延时等性能有着重要影响，链路在网络中节点相互通信的最短路径中使用的频度越高，说明这条链路对网络的传输性能影响也越大，重要性也越高。笔者提出了一种基于网络传输特性的通信网链路重要性评价方法，根据链路在网络所有节点相互通信的最短路径中的使用频度来评价链路重要性。该方法不需要对链路进行删除和收缩，可以反映链路对网络传输性能直接影响的大小，并且有效地解决了目前算法无法比较串联链路和删除后使得网络不连通的链路的重要性的问题。

传输特性法首先需要获得网络 G 中所有节点相互通信的最短路径，已经有很多研究者致力于最短路径获得的研究，其中 Moffat 和 Takaoka 提出的最短路径算法[12]是适用于笔者提出的网络模型的最有效算法。 使用该算法获得所有的最短路径 pathj （j ＝1，2，…，K），其中 K ＝ ，K 表示网络 G 中最短路径数目，n 为网络的节点数。

分别统计每条链路在所有最短路径中使用的频度 fi ，当某两个节点间只有一条最短路径时，此最短路径中包含的链路的使用频度加 1；当某两个节点间存在 n（n  2） 条可能的最短路径时，各最短路径中包含的链路的使用频度加 1/n 。

链路的使用频度反映了其在网络通信中的作用和重要性，通过比较每条链路的使用频度 fi ，可以评价通信网中任意两条链路的相对重要性。链路对应的链路使用频度越大，表明该链路越重要，使用频度相同的链路具有相同的重要性。为了直观的评价重要性，笔者对指标归一化，令

其中，K ＝ ，ti  为链路 ei 的归一化重要性，ti  越大，该链路越重要。

《3.2 算法示例》

3.2 算法示例

利用图 1 的无向网络对传输特性法进行说明。首先获得网络 G1 中所有节点相互通信的最短路径如下：

path1 ＝ x1 → x2：e1

path2 ＝ x1 → x3 ：e2

path3 ＝ x1 → x4 ：e1e4 ，e2e5

path4 ＝ x2 → x3 ：e3

path5 ＝ x2 → x4 ：e4

path6 = x3 → x4 ：e5

《图1》

图1 无向网络 G1[13]

Fig.1 The undirected network G1[13]

分别统计每条链路在最短路径中的使用频度 fi ，并归一化重要性，结果如表 1 。其中 path3 包含两条最短路径，统计链路时频度加 1/2 。

《表1》

表1 G1 的链路重要性结果

Table1 The link importance result of G1

从表 1 可知，图 1 网络 G1 的链路重要性排序为 e1 ＝e2 ＝e4 ＝e5 ＞e3 ，简写为 e1 ，e2 ，e4 ，e5 ＞e3 。

《3.3 计算复杂度分析》

3.3 计算复杂度分析

对于 n 个节点，m 条链路的连通图 G，可靠性多项式法使用了文献[14]中的因子分解方法获得可靠性多项式。对于每条链路，需要分别计算其删除和收缩后的可靠性多项式，对于每个可靠性多项式的获得，需要进行 2m-1 次分解，因此可靠性多项式法的计算时间复杂度为 O（m · 2m）。生成树数目法需要计算每条链路删除后的生成树数目，由文献[8]可知，算法的计算时间复杂度为 O（m · n2.376）。传输特性法的计算时间复杂度主要来自所有节点间最短路径的求解，由于采用文献[12]的最短路径算法，传输特性法的计算时间复杂度为 O（log2n · n2）。三种算法的计算时间复杂度比较结果如表 2 所示。

《表2》

表2 几种算法的计算时间复杂度比较结果

Table2 The time complexity comparison of the algorithms

《4 性能仿真》

4 性能仿真

利用图 2 的无向串联网络 G2 对算法进行说明。将传输特性法、可靠性多项式法[5]和生成树数目法[10]用于图 2，算法采用 Matlab（版本 7.0.0）语言编写，在 1.85 GHz 主频的 AMD 处理器微机上运行，结果见表 3 。

《图2》

图2 6 个节点 5 条链路的串联网络 G2

Fig.2 The serial network G2 with 5 edges and 6 nodes

《表3》

表3 通信网 G2 中不同方法的链路重要性结果比较

Table3 The link importance result of different algorithms in G2

从表 3 可以看出，可靠性多项式法在任一条链路删除和收缩后产生的可靠性表达式相同，因此，各链路的重要性完全相同；生成树数目法在任一条链路收缩后产生的生成树数目相同，则各链路的重要性相同；传输特性法的结果根据 ti 判断，ti  越大则链路越重要，因此传输特性法得到的重要性从高到低的顺序为 e3 ＞e2 ，e4 ＞e1 ，e5 。 从直观上看， e3 是网络 G2 最重要的链路，而 e1 和 e5 是此网络中最不重要的链路。 因此传输特性法获得的链路重要性结果比其他两种方法更符合直观评价。

将上述三种算法用于图 1，三种方法获得了同样的链路重要性的结果， e1 ，e2 ，e4 ，e5 ＞e3 ，验证了传输特性法的有效性。

对图 3 无向网络 G3 分别运用三种算法，传输特性法的重要性评价结果见表 4 。

《图3》

图3 无向图 G3

Fig.3 The undirected network G3

《表4》

表4 G3 的链路重要性结果

Table4 The link importance result of G3

从表 4 可得传输特性法的链路重要性排序：e4 ，e5 ＞e2  ，e3，e6 ，e7 ＞e1 ，e8 。可靠性多项式法和生成树数目法得到的重要性排序均为 e4 ，e5 ＞e2 ，e3 ，e6 ，e7 ，e1 ，e8 。3 个方法评价的重要性差别在于 e1 和 e8 ，由于 G3 中 e1 和 e2 ，e3 串联， e ８ 和 e6 ，e7 串联，根据以上分析，可靠性多项式法和生成树数目法得出的 e1 的重要性和 e2 ，e3 相同， e8 同理。又因 G3 中 e1 ，e2 ，e3 和 e6 ，e7 ，e8  完全对称，因此这六条链路的重要性相同，但是文献[5,10]对这些链路的重要性评价并不符合直观判断。

从图 3 可以看出，链路 e2 ，e3 ，e6 ，e7 是完全对称的，因此它们的重要性相同，e1 ，e8 同样如此，但是还需要获得这两组链路之间的重要性关系。G3 中的链路 e1 连接节点 x1 和 x2 ，x1 和 x2 间的数据通过链路 e1 传输，当 e1 断开后，原来通过 e1 传输的数据需要 e2 ，e3 迂回，只是影响了 x1 ，x2 间的通信；当链路 e2 断开后， x1 和 x3 ，x4 ，x5 ，x6 ，x7 的通信数据全部需要通过链路 e1 ，e3 迂回，大大增加了链路 e1 ，e3 的通信负担，降低了它们的可靠性。因此，链路 e2 对网络传输性能的影响远大于链路 e1 ， e2 的重要性要高于 e1 。因此，文献[5,10]的两种方法仅考虑网络连通性获得的链路重要性评价是不准确的，而传输特性法是基于网络传输特性的对 G3 中链路重要性的一种直观合理的评价。

《5 结语》

5 结语

提出了一种基于网络传输特性的通信网链路重要性评价方法，根据链路在网络所有节点相互通信的最短路径中的使用频度来评价链路重要性，最重要链路的使用频度最高，其充分考虑了链路对网络通信的贡献，并且不需要像其他链路重要性评价方法那样进行链路收缩和删除，能够直接反映链路对网络的影响，并对重要性进行了归一化，可以判断通信网中任意两条链路的相对重要性。目前提出的链路重要性的评价方法都是基于链路删除法或其等价准则链路收缩法，这类方法在评价串联链路和删除后造成网络不连通的链路时，会获得同样的重要性结果，而从直观判断，这些链路的重要性并不相同。串联链路作为通信网中最普遍的拓扑结构，为现有的评价方法在分析通信网络链路重要性时产生了很大的障碍。 算法分析和实验仿真表明，传输特性法在保持现有算法有效性的同时，克服了它们存在的问题，给出了更直观合理的通信网链路重要性评价准则。