由于网络在社会生活中扮演了重要的角色, 所以网络可靠性和重要度吸引了许多学者的关注。网络一般由节点和边组成, 其中节点表示道路交叉口、控制中心等, 而边表示通讯电缆、道路等。在K-终端网络中, 一部分节点称为终端, 网络运行当且仅当所有终端被一些运行的边连通。假设节点绝对可靠, 而边以某种概率发生故障, 边故障可能导致整个网络处于故障状态。因此K-终端网络可靠性被定义为网络中所有终端彼此连通的概率^[1]。

网络可靠性分析的目的是识别网络瓶颈和量化网络边的故障(运行)对整个网络的影响程度。作为一种可靠性分析工具, 重要度提供了数值指标, 能够量化不同的边对网络可靠性(故障)的影响程度, 从而对网络的边进行排序。在二态关联系统领域, 常见的重要度包括Birnbaum-重要度^[2-3]、FV-重要度^[4-5]、贝叶斯-重要度^[6]、集成重要度^[7-8]、置换重要度^[9-10]。在网络领域, Page和Perry^[11]引进了可靠性多项式去量化网络边的相对重要性。对于一类可约网络, Hsu等人^[12]设计了一种“两阶段”算法评估网络边的重要度。该算法第一阶段执行网络化简; 第二阶段跟踪化简步骤和评估边的重要度。Hong等人^[13]提出了2条边的联合重要度。该联合重要度考虑了2条边的互动对整个网络可靠性的影响。

对于中等或大型网络, 网络重要度的理论分析和精确计算之间存在着巨大的鸿沟^[1]。因此, 一般采用数值近似的方法评估网络边的重要度。当网络中的每条边有相同的可靠性时, Gertsbak等人^[14-17]将传统的FV-重要度、Birnbaum-重要度、以及联合重要度推广到K-终端网络, 设计了基于网络谱的蒙特卡罗方法评估这些重要度。网络谱分为D-谱和C-谱, 分别与网络的割集和路集紧密相关。由于它们的值都仅依赖于网络结构, 故称为结构不变量。本文将传统的置换重要度推广到K-终端网络。在二态关联系统背景下, 传统的置换重要度通过枚举所有割集或者路集的方法评估了系统组件的重要度。然而, 由于K-终端网络结构的复杂性, 本文提出了2条边的混合C-谱的概念, 并设计了基于混合C-谱的蒙特卡罗算法评估网络边的置换重要度。研究结果表明, 当网络拥有一定的特殊结构, 或者网络边的可靠性足够大时, 基于置换重要度的网络边的排序仅依赖于网络结构, 与边的可靠性无关。

1 基本概念和定义

本文研究K-终端网络(简称网络), 该网络是一个由节点和边构成的无向图N=(V, E, K)。V是网络中节点的集合, E是网络边的集合且|E|=n, K(K⊆V)是由一些特殊节点构成的集合, 称为网络终端集合。针对由二态边组成的二态网络, 令二态变量x_i=1(0)表示边i处于运行(故障)状态。边i的可靠性为p_i, 即p_i=P(x_i=1)。结构函数φ(x)确定网络状态, 这里x=(x₁, x₂, …, x_n)。φ(x)=1(0)表示网络处于运行(故障)状态。网络运行当且仅当所有终端被一条路连通。路为若干运行边的集合, 其连通网络所有终端。网络可靠性定义为该网络处于运行状态的概率, 即R=P(φ(x)=1)=R(p₁, p₂, …, p_n)。

假设网络所有边的故障相互独立且有相同可靠性。在此背景下, 网络可靠性和重要度可利用基于C-谱的方法去评估。C-谱的定义如下^[1]:

假设网络所有边处于故障状态, 令π=(i₁, i₂, …, i_n)为网络边集E的一个随机置换。沿着该置换π, 从左到右依次“复活”各个边。当边i_j“复活”时(即该构造过程的第j步), 令f_j为网络“复活”的概率。离散概率向量f=(f₁, f₂, …, f_n)称为网络的C-谱。网络累积C-谱定义为:F(k)=f₁+f₂+…+f_k, 这里k=1, 2, …, n。令B(k)为恰包含k条边的路的数目, 则下列公式成立^[1]:

(1)

由此, 当随机的恰有k条边运行时, F(k)可解释为网络处于运行状态的概率。注意这里的C-谱仅依赖于给定网络的结构, 故称为结构不变量。固定边i, 恰含有k条边的所有路可分为2类:一类包含边i, 一类不包含边i。因而B(k)可拆成两部分, 如下

(2)

式中，B(k, 1_i)(B(k, 0_i))表示恰含有k条运行边的路的数目, 其中边i运行(故障)。公式(2)代入公式(1)后, F(k)亦可拆成两部分, 如下

(3)

式中

(4)

(5)

由公式(4)~(5), 当随机恰有k条边运行时, F(k, 1_i)(F(k, 0_i))可解释为网络处于运行状态, 且边i运行(故障)的概率。称F(k, 1_i), F(k, 0_i)为网络边i的C-谱^[1]。

进一步, 记B(k, 1_i, 0_j)(B(k, 0_i, 1_j))表示恰含有k条边的路的数目, 其中边i运行(故障), 边j故障(运行)。相似于公式(4)~(5), 令

(6)

(7)

根据公式(6)和(7), 当随机恰有k条边运行时, F(k, 1_i, 0_j)(F(k, 0_i, 1_j))可解释为网络处于运行状态, 且边i运行(故障), 边j故障(运行)的概率。称F(k, 1_i, 0_j), F(k, 0_i, 1_j)为网络边i, j的混合C-谱。

在网络N中, 对于给定的一条边j, 删除边j得到子网络N-j; 收缩边j为一个新节点, 得到子网络N*j。若收缩的边j邻接的节点有网络N的终端, 则边j收缩后的新节点为子网络N*j的终端。F_N(k), F_N-j(k), F_N*j(k)分别表示网络N, 子网络N-j, 子网络N*j的累积C-谱。以此类推, 网络N、子网络N-j、以及子网络N*j的边的C-谱和两条边混合C-谱可类似表示。

下面的定理揭示了网络边的混合C-谱, 边的C-谱, 以及网络累积C-谱之间的关系。

定理1  给定一个由n条边组成的网络N, 下面的结论成立

(8)

(9)

式中，k=1, 2, …, n-1;i=1, 2, …, j-1, j+1, …, n。

证明   在网络N中, 若已知边j运行, 则收缩边j, 由路的定义, 得下面公式

(10)

(11)

式中，k=1, 2, …, n-1;i=1, 2, …, j-1, j+1, …, n。

在网络N中, 恰含有k+1条边且包含边j的所有路可分为2类:一类包含边i, 一类不包含边i。故下列公式成立

(12)

公式(10)和(11)代入(12)式, 得到下面公式

(13)

根据C-谱的定义(即公式(7), (1), (4)), 公式(13)可等价写为

(14)

从公式(14)解出F_N(k+1, 1_j, 0_i)后, 得到公式(8)。

另外, 当边j故障, 则从网络N中删除边j后, 由路的定义, 下列公式成立

(15)

根据C-谱的定义(即公式(4), (6)), 公式(15)可以等价的写为

(16)

从公式(16)解出F_N(k, 0_j, 1_i), 可得公式(9)。从而定理得证。

注意  当网络N只含有2个终端时, 如果边j本身为一条路时({j}称为网络N的单边路), 则B_N(1, 1_j, 0_i)=1;否则B_N(1, 1_j, 0_i)=0。从而根据混合C-谱的定义(见公式(7)), 有下列公式成立

(17)

2 基于混合C-谱的置换重要度

在解决关联系统的冗余分配问题时, Boland等人^[10]提出了置换重要度。对于关联系统的任意2个组件i和j, 如果R(1_i, 0_j, p)>R(0_i, 1_j, p), 则称组件i比组件j更重要, 记为ij, 其中R(1_i, 0_j, p)=P(φ(x)=1|x_i=1, x_j=0), R(0_i, 1_j, p)=P(φ(x)=1|x_i=0, x_j=1)。

给定一个由n条边构成的K-终端网络, 假设所有边有共同的可靠性p(q=1-p)。对于该网络任意的2条边i和j, 根据全概率公式, 得下面公式

(18)

公式(6)代入公式(18)后, 得下面公式

(19)

同理, 由全概率公式, 下列公式成立

(20)

公式(7)代入公式(20)后, 得下面公式

(21)

比较公式(19)和(21), 得下面定理。

定理2  给定一个由n条边组成的K-终端网络。对于该网络任意的2条边i和j, 下面的结论成立:

1) 若F(k, 1_i, 0_j)≥F(k, 0_i, 1_j)(F(k, 1_i, 0_j)≤F(k, 0_i, 1_j))对一切k=1, 2, …, n-2成立, 且对某个k, 不等式严格成立, 则ij(ij)对一切p∈(0, 1)成立。

2) 令m=max{k|F(k, 1_i, 0_j)≠F(k, 0_i, 1_j)}。若F(m, 1_i, 0_j)>F(m, 0_i, 1_j), 则对于充分大的p, ij成立。

证明

1) 由置换重要度定义, ij当且仅当R(1_i, 0_j, p)>R(0_i, 1_j, p), 即R(1_i, 0_j, p)-R(0_i, 1_j, p)>0。将公式(19)与公式(21)作差相减后, 只须证明下列不等式成立

(22)

由于F(k, 1_i, 0_j)≥F(k, 0_i, 1_j)对一切k=1, 2, …, n-2成立, 故公式(22)对一切p∈(0, 1)成立。从而得证。

2) 根据m的定义和公式(22), ij当且仅当下列不等式成立

(23)

注意当p→1(即q→0)时, 单项式(F(k, 1_i, 0_j)-F(k, 0_i, 1_j))p^kq^n-k-2→0。(n-k-2)越大(即k越小), 该单项式趋向于0越快。故由m定义, 当q→0时, 公式(23)成立当且仅当单项式(F(m, 1_i, 0_j)-F(m, 0_i, 1_j))p^mq^n-m-2>0(忽略高阶无穷小)。结合已知条件F(m, 1_i, 0_j)>F(m, 0_i, 1_j), 故对于充分大的p, ij成立。从而定理得证。

注意   根据置换重要度的定义, 对于网络中任意2条边i和j, ij依赖于网络的结构和网络边的可靠性p。定理2说明, 当网络拥有特殊的结构, 即F(k, 1_i, 0_j)≥F(k, 0_i, 1_j)对一切k=1, 2, …, n-2成立, 则网络边的置换重要度排序与边的可靠性无关; 另外, 当网络边的可靠性足够大时, 网络边的置换重要度排序亦仅依赖于网络结构。

3 算例分析

这里通过一个算例演示如何利用传统置换重要度评估K-终端网络边的重要程度。给定立方体网络H₃, 节点1, 3, 6为终端节点, 如图 1所示。基于置换重要度, 本节对该网络所有边的重要性进行排序。网络的累积C-谱以及边的C-谱的数值估计借助Gertsbakh等人^[1]设计的蒙特卡罗方法。然后, 根据公式(8)~(9), 得到2条边的混合C-谱。表 1(表 2)提供了网络H₃边3, i的混合C-谱F(k, 0₃, 1_i)(F(k, 1₃, 0_i)), i=1, 2, 4, 5, …, 12, F(k, 0₃, 1_i) (F(k, 1₃, 0_i))缩写为0₃, 1_i(1₃, 0_i)。

根据定理2, 为了比较2条边的置换重要度, 只须比较它们相应的混合C-谱。由表 1, 表 2得知, F(k, 1₃, 0₈)≥F(k, 0₃, 1₈), 且F(k, 1₃, 0₁)≤F(k, 0₃, 1₁)对于所有的k=1, 2, …, 11成立。故138对于所有的p∈(0, 1)成立。同理, 分析H₃网络12条边所有混合C-谱, 发现这些边可分为3组, 每组有相同的重要性。第一组为{1, 4, 5}, 第二组为{2, 3, 6, 7, 9, 11}, 第三组为{8, 10, 12}。基于置换重要度, 第一组最重要, 其余类推。

对于其他任意网络结构, 亦可采用同样方法求得其混合C-谱。从而根据定理2的结论对网络边进行排序。

事实上, 第一组边{1, 4, 5}有一个共同的特性:与这些边邻接的一个节点为终端, 而相邻的另外一个节点距离其他2个终端的距离都为1。第二组边{2, 3, 6, 7, 9, 11}的共同特性:与这些边邻接的一个节点为终端, 而相邻的另外一个节点距离其他某一个终端的距离为1。其余为第三组边{8, 10, 12}。

4 结论

本文将二态关联系统的置换重要度推广到K-终端网络。假设每条边的可靠性相同, 本文提出混合C-谱的概念, 给出K-终端网络的边的置换重要度的计算方法。理论分析认为, 当网络具有某种特殊结构或者边的可靠性足够大时, 网络边的置换重要度排序仅依赖于网络结构。数值计算结果表明, 基于混合C-谱的计算方法能有效评估网络边的置换重要度。本文结果有助于进一步理解K-终端网络, 并为网络可靠性优化提供了基础。