高级检索

  • ISSN 1006-3080
  • CN 31-1691/TQ
引用本文:
Citation:

直径限定可靠性计算的冗余边的检测算法

    作者简介: 熊祥军(1982-),男,湖南省永顺县,硕士生,助理研究员,主要研究方向为无线传感器网络。E-mail:xxj@ecust.edu.cn;
    通讯作者: 邵方明, fmshao@ecust.edu.cn
  • 中图分类号: O29

An Algorithm of Detecting Innermost Irrelevant Edges

    Corresponding author: Fangming SHAO, fmshao@ecust.edu.cn ;
  • CLC number: O29

  • 摘要: 给出了路径长度的新度量方法,将st-路分类为实际路径(RP),伪路径(PP),组合路径(CP)和包含特定边(SPE)的最短st-路,明确通过测量PP,RP和CP可以计算SPE的长度;同时提出了一种检测隐藏冗余边的算法,该算法的复杂度为多项式(O(n4))。实验结果表明了该算法的有效性和效率。
  • 图 1  通讯网络G (V, E)

    Figure 1.  A communication network G (V, E)

    图 2  无法用命题2.1判断冗余边的拓扑结构

    Figure 2.  Topology with irrelevant edges not identified by Proposition 2.1

    图 3  RP和CP的示例

    Figure 3.  An example for RPs and CPs

    图 4  从PP到SPE的长度矩阵

    Figure 4.  Length matric from PP to SPE

    图 5  拓扑示意图

    Figure 5.  Illustration of four topologies

    图 6  比较不同D值的示意图

    Figure 6.  An illustration for comparison of different values of D

    表 1  路径长度的度量标准

    Table 1.  Metrics of path lengths

    Table度量Length
    G-ed*L’=|Ps, u|+|Pv, t|+1
    G-e-C1d**L’’= min{|Ps, u|+$|{P'}_{v,t}|$+1, $|{P'}_{s,u}|$+|Pv, t| +1, $|{P'}_{s,u}|$+$|{P'}_{v,t}|$+1}
    ………………
    G-e-$\sum\limits_k {{C_k}} $${d^{\overbrace {* \cdots *}^{k{\rm{+1}}}}}$L(k+1)’=min{$|P_{s,u}^{(k - 1)'}|$+$|P_{v,t}^{(k)'}|$+1, $|P_{s,u}^{(k)'}|$+$|P_{v,t}^{(k - 1)'}|$+1, $|P_{s,u}^{(k)'}|$+$|P_{v,t}^{(k)'}|$+1}
    下载: 导出CSV

    表 2  数值结果(p=0.9)

    Table 2.  Table II Numerical results with p = 0.9

    GDRst(G, D)TIE1T1 (s)IE2T2 (s)T1/ T2
    a30.972 924580.019 860.027 40.722 627 737
    b50.987 71 675172.182156.6210.329 557 469
    c50.978 3>2 days163.257156.1980.525 492 094
    c60.978 3>2 days52 153.75643 144.7560.684 872 213
    c70.978 4>2 days257 464.543257 468.7530.999 926 743
    d40.875 623150.168 640.525 30.320 959 452
    d50.949 131110.095 900.343 50.279 184 862
    d60.949 137810.096 600.347 90.277 665 996
    下载: 导出CSV

    表 3  冗余边的检测及可靠性计算时间(p=0.9)

    Table 3.  Table III Detection of irrelevant edges and computation of reliability for p = 0.9

    DRst(G, D)IE1T1 (s)IE2T2 (s)T1/ T2
    20.8100201.009 759 200.102 370 9.863 817 525
    30.8100200.078 654 200.052 092 1.509 905 552
    40.8100200.082 933 170.096 517 0.859 257 955
    50.8100200.050 252 170.073 968 0.679 375 865
    60.9283110.218 298 62.526 741 0.086 395 084
    70.934290.338 099 014.941 998 0.022 627 429
    80.934770.652 814 014.906 975 0.043 792 52
    90.9414014.945 633 014.758 551 1.012 676 177
    下载: 导出CSV
  • [1] PETINGI L, RODRIGUEZ J. Reliability of networks with delay constraints[J]. Congressus Numerantium, 2001, 152: 117-123.
    [2] CANCELA H, PETINGI L A. Polynomial-time topological reductions that preserve the diameter constrained reliability of a communication network[J]. IEEE Transaction on Reliability Sowety, 2011, 60(4): 845-851. doi: 10.1109/TR.2011.2170250
    [3] PETINGI L. Efficient evaluation of a diameter-constrained reliability measure of some families of graphs[J]. Graph Theory Notes N Y, 2013: 26-34.
    [4] CANCELA H, PETINGI L A. On the characterization of the domination of a diameter-constraint network reliability model[J]. Discrete applied mathematics, 2006, 154: 1885-1896. doi: 10.1016/j.dam.2006.03.029
    [5] MOSKOWITZ F. The analysis of redundancy networks[J]. AIEE Trans. Commun. Electron., 1958, 39: 627-632.
    [6] ALTIPARMAK F, DENGIZ B, SMITH A E. A general neural network model for estimating telecommunications network reliability[J]. IEEE Transaction on Reliability Sowety, 2009, 58(1): 2-9. doi: 10.1109/TR.2008.2011854
    [7] DIJKSTRA E W. A note on two problems in connection with graphs[J]. Numerische Math, 1959, 1: 269-271. doi: 10.1007/BF01386390
    [8] CANCELA H, PETINGI L A. Reliability of communication networks with delay constraints: Computational complexity and complete topologies[J]. International Journal of Mathematics & Mathematical Sciences, 2004, 29: 1551-1562.
  • [1] 于中宝邵方明 . 并行系统中排列图的可靠性近似算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180531001
    [2] 叶贞成王鑫梅华 . 基于改进差分进化算法的裂解反应动力学系数辨识. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190910002
    [3] 殷飞宇金晶王行愚 . 基于多相关性的导联前向搜索算法用于运动想象分类. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190901002
    [4] 解冰朱宏擎 . 一种基于选择性卷积特征和最大后验高斯混合模型的细粒度图像分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180603001
    [5] 张幸子王晓惠王泽建陈必钦李丹郭美锦储炬庄英萍 . 等离子体作用结合氧限制模型选育辅酶Q10高产菌株. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20200227002
    [6] 杨家鹏熊文莉安琦 . 滚子直径误差对双列调心轴承疲劳寿命的影响. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180411001
    [7] 赵菡诸葛晶晶林家骏 . 飞行状态敏感的关联门调节算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180622003
    [8] 吉祥虞慧群范贵生孙怀英 . 基于蚁群算法的延时感知VANET路由协议. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181116001
    [9] 王德勋虞慧群范贵生 . 基于深度学习的面部动作单元识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190107003
    [10] 宋振振陈兰岚娄晓光 . 基于时序卷积网络的情感识别算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20190508001
    [11] 高天阳虞慧群范贵生 . 基于模拟退火遗传算法的云资源调度方法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416001
    [12] 陈立皇程华房一泉 . 基于注意力机制的DGA域名检测算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180326002
    [13] 王学武闵永顾幸生 . 基于密度聚类的多目标粒子群优化算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180321005
    [14] 常青张天宇赵冰冰 . 基于机器视觉的手机异形主板非标自动化检测算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180416006
    [15] 颜建军刘章鹏刘国萍郭睿王忆勤付晶晶钱鹏 . 基于深度森林算法的慢性胃炎中医证候分类. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180410001
    [16] 高炳舒刘士荣 . 基于BoW模型的RGB-D SLAM算法的运动轨迹估计. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180419001
    [17] 曹雅茜黄海燕 . 基于代价敏感大间隔分布机的不平衡数据分类算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180515001
    [18] 孙佩袁伟娜程华 . 一种新的基于异步NOMA的串行干扰消除算法. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180412008
    [19] 张剑超杜文莉覃水 . 基于新型自适应采样算法的催化重整过程代理模型. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20180915001
    [20] 陈鹏罗娜 . 基于竞争机制差分进化算法的无分流换热网络优化. 华东理工大学学报(自然科学版), doi: 10.14135/j.cnki.1006-3080.20181015004
  • 加载中
图(6)表(3)
计量
  • 文章访问数:  1116
  • HTML全文浏览量:  341
  • PDF下载量:  5
  • 被引次数: 0
出版历程
  • 收稿日期:  2019-05-05
  • 网络出版日期:  2020-04-04

直径限定可靠性计算的冗余边的检测算法

    作者简介:熊祥军(1982-),男,湖南省永顺县,硕士生,助理研究员,主要研究方向为无线传感器网络。E-mail:xxj@ecust.edu.cn
    通讯作者: 邵方明, fmshao@ecust.edu.cn
  • 1. 华东理工大学理学院,数学系,上海 200237
  • 2. 长春财经学院

摘要: 给出了路径长度的新度量方法,将st-路分类为实际路径(RP),伪路径(PP),组合路径(CP)和包含特定边(SPE)的最短st-路,明确通过测量PP,RP和CP可以计算SPE的长度;同时提出了一种检测隐藏冗余边的算法,该算法的复杂度为多项式(O(n4))。实验结果表明了该算法的有效性和效率。

English Abstract

  • 经典的二终端网络可靠性是是指源节点s和终端节点t之间存在至少一个操作路径的概率,但是不考虑对st-路长度的限制。通过限制所有st-路的长度不超过给定正整数D,Petingi等[1]最初将直径限制引入网络可靠性(DCR)。Cancela等[2]研究了通信网络的直径限制可靠性模型,并提出了一种多项式时间算法,用于检测和删除冗余边,以计算具有直径限制的简单无向图的二终端可靠性。在DCR模型中,检测冗余边的必要条件尚未得到解决。此外,文献[3]中做了进一步的工作。文献[4]中将sK-直径定义为源节点sK中任何节点之间的最大距离,使用控制以提出一种简单的方法来计算sK-直径不大于给定值D时的可靠性。然而,检测冗余边的必要条件仍然是一个悬而未决的问题。

    计算二终端靠性的问题是NP-难的问题。因子分解算法[5]是评估可靠性的有效方法。通过使用这种算法,Cancela等人[2]研究了文献[6]中网络的结果,这些结果也用于本文。

    多项式时间拓扑归约在直径限制可靠性的计算中起重要作用,因为许多冗余边能够被删除并且可靠性保持不变。然而,以往对冗余边的研究并不全面。检测冗余边的必要条件是所谓的开放问题。在本文中,我们基于文献[7]定义路径长度的新度量方法,将st路径分类为实际路径(RP),伪路径(PP),组合路径(CP),包含特定边的最短st路径(SPE)并明确指出通过测量PP,RP和CP可以得出SPE的长度。此外,我们提出了一种检测隐藏冗余边的算法,该算法的复杂度是多项式的(O(n4))。实验结果表明了该算法的有效性和效率。

    • 通信网络可以通过概率图GVE)在数学上建模,其中V是节点集合,E是边的集合。每个节点vV是完全可靠的,而每个边eE独立地失效并且与操作概率pe(失效概率qe=1-pe)相关联。图1代表具有节点集V={sabcdt}的通信网络G,其中源节点和终端节点分别是st,边集E={e1e2,...,e11}。

      图  1  通讯网络G (V, E)

      Figure 1.  A communication network G (V, E)

      定义1.1[1]:由Rst(G)表示的st可靠性是指源点s和汇点t之间至少存在一条连通路径的概率。

      文献[5]提出了因子分解算法来计算st可靠性,这被认为是NP-难问题。可靠性计算的因子定理:

      其中Rst($G*e $)是指通过固定边e的状态得到的图$G*e $的可靠性(边e的可靠性设为1),Rst(G-e)是指通过设定可靠性边e的状态为失效得到的图G-e的可靠性(边e的可靠性固定为0)。

      在许多实际应用中,经由长st路径的传输可能增加网络节点上的负载。因此,这些网络中通常存在跳数约束。在数学上,跳数约束可以被认为是限制所有st路径的长度不超过给定整数DZ+的的参数,即直径限制,其可以在网络中生成冗余边。

      定义1.2[2]对于有固定顶点st的给定图G,如果边e包含在无st路径中,或者它只属于长度大于Dst路径,则边e是冗余紧要的。

      为避免混淆,以下表述中的冗余边指的是后者。

    • 定义1.3:直径限制下的二终端可靠性是指至少存在一条长度小于Dst路径,记为Rst(G, D)。

      通过因子分解定理计算,

      值得注意的是,收缩边e得到图$G*e $的过程可能会使原来经过边e的长度为D+1的路的长度减少到D,从而导致计算Rst($G*e $, D)时将多余的路径计算在内的情况。因此,我们设定固定边e的状态为1并保留边e在图中的位置不收缩。

    • Petingi等[3]提出检测冗余边的充分条件。

      命题1.1:e=uv是存在于图G某个st-路上的边。如果dG-e(s, u)+dG-e(v, t)≥D and dG-e(s, v)+dG-e(u, t)≥D,则边e是冗余边。

      与[2]中结果相比,命题1.1可以被认为是路径长度的新的度量方法,但它仍然不能完全找到冗余边。比如在图2中,给定D=5,冗余边e=bc。从命题1.1,dG-e(s, b)+dG-e(c, t)=4<D并且dG-e(s, c)+dG-e (b, t)=4<D可知e=bc并非冗余边。

      图  2  无法用命题2.1判断冗余边的拓扑结构

      Figure 2.  Topology with irrelevant edges not identified by Proposition 2.1

      造成这种现象的原因是该度量仅考虑路径长度,但忽略了从源点s到点u和点v到汇点t(从svut)的路径的具体信息以及路径的组合是否可以包含给定边uv。因此,dG-e(s, u)+dG-e(v, t) and dG-e(s, v)+dG-e(u, t)的度量仍然需要进一步改进。

    • 设定P1, P2, …, Pm都为包含边est-路,

      定理3.1:如果min1≤i≤m |Pi|>D,则e为不相关边。

      显而易见,min1≤im |Pi|>D意味着所有包含边est-路的长度大于D,因此边e必然为冗余边。反之,如果边e为冗余边,则所有包含边est-路的长度大于D,例如,min1im|Pi|>D

      为了更有效地检测冗余边,我们考虑包含边eSPE)的最短st-路[3]。如果找到SPE,则肯定会完全检测到所有冗余边。但是,Petingi等[3]证明找到SPE的问题是NP-难的。我们希望在多项式时间内找到接近SPE长度的值,并使用该值与D进行比较以确定冗余边。

      对于节点xyPx, y表示从x到y的最短路径之一。对于边e=uv,我们称Ps, u∪(u, v)∪Pv, tPs, v∪(v, u)∪Pu, t分别为uv-path和v,u-path。为方便起见,我们只讨论如何处理uv-paths并对vu-paths进行相同的操作。

      推论2.1:包含边uv的最短路径然必然是包含uv-paths和vu-paths中最短的路径。

      定义2.1:如果Ps, uPv, t$\emptyset $u, v-path被称作u, v-伪路径 (u, v-PP)。

      显而易见,u, v-PP并非路径。因为Ps, uPv, t$\emptyset $,一些节点重复出现在u, v-PP中。

      例2.1:如图2边bc,Ps, b=(s, a, b)及Pc, t=(c, a, t)说明Ps, bPc, t={a}。则Ps, b∪(b, c)∪Pc, t不仅经过边bc,而且经过节点a两次。因此,(s, a, b, c, a, t)是b, c-PP。

      定义2.2:如果Ps, uPv, t=$\emptyset $,则u, v-path为u, v-实际路径(u, v-RP)。

      例2.2:图2边cd,Ps, c=(s, a, c), Pd, t=(d, e, t)。因为Ps, cPd, t=$\emptyset $,(s, a, c, d, e, t)路既是c, d-RP,也是c, d-SPE。可是,SPE可能不是RP。设图3e=(3, 7),(s, 6, 5, 4, 3, 7, 2, 1, t)路是包含边(3, 7)(SPE)最短的st-路,由于Ps, 3P7, t=(1, 2),Ps, 3∪(3, 7)∪P7, t并非 3, 7-RP。

      图  3  RP和CP的示例

      Figure 3.  An example for RPs and CPs

      因此,命题2.1的度量任然有改进空间。为方便起见,我们将G-e中的节点x和节点y之间的距离表示为d*(x, y),例如,d*(x, y)=dG-e (x, y)。设定C1=Ps, uPv, t,如果C1$\emptyset $,将C1G-e中移除,由此得出:

      定义2.3d**(x, y)是指G-e-C1中节点x与节点y之间的距离,即d**(x, y)=dG-e-C1 (x, y).

      设定${P'}_{s,u}$ ${P'}_{v,t}$分别为G-e-C1源点s到点u以及点v到汇点t的最短路径。如果${P'}_{s,u} \cap {P'}_{v,t}{\rm{ = }}\emptyset $${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$G-e-C1u, v-RP。

      定义2.4:设定Ps, uPv, t为G-e中最短路径,${P'}_{s,u}$${P'}_{v,t}$G-e-C1中最短路径,$P_{s,u}^{} \cup (u,v) \cup {P'}_{v,t}$${P'}_{s,u} \cup (u,v) \cup P_{v,t}^{}$被称作u, v-组合路径,即u, v-CP。

      例2.3:对于图3中的边e=(3, 7),当C1=Ps, 3P7, t=(1, 2) ≠$\emptyset $时,我们考虑具有Ps, 3P7, t的CPs。在G-e-C1中,$P'_{s,3}$= (s, 6, 5, 4, 3),$P'_{{\rm{7}},t}$=(7, 8, 9, 10, 11, t),3, 7-CPs为$P'_{s,{\rm{3}}} \cup ({\rm{3}},{\rm{7}}) \cup P_{{\rm{7}},t}^{}$=(s, 6, 5, 4, 3, 7, 2, 1, t)以及$P_{s,{\rm{3}}}^{} \cup ({\rm{3}},{\rm{7}}) \cup P'_{{\rm{7}},t}$=(s, 1, 2, 3, 7, 8, 9, 10, 11, t)。因为$P_{s',{\rm{3}}} \cap P_{{\rm{7}},t}^{}{\rm{ = }}\emptyset $并且$P_{s,{\rm{3}}}^{} \cap P'_{{\rm{7}},t}{\rm{ = }}\emptyset $,最短的CP为$P'_{s,{\rm{3}}} \cup ({\rm{3}},{\rm{7}}) \cup P_{{\rm{7}},t}^{}$。实际上,如果G-e-C1最短的组合路径是SPE的话,那么SPE不仅经过e,也经过C1

      通过d*; d**甚至是d***; …, ${d^{\overbrace {* \cdots *}^k}}$的度量,我们总能发现包含C1, C2, …, Ck,的RP或CP,其中Ck通过${d^{\overbrace {* \cdots *}^k}}$度量得出。比对这些路径长度可以确定SPE。

      定理2.2:如果 Ps, u∪(u, v)∪Pv, tu, v-RP,则u, v-RP为u, v-SPE。

      证明Ps, u∪(u, v)∪Pv, t路径是u, v-RP意味着Ps, uPv, t=$\emptyset $。因此,P1=Ps, u∪(u, v)∪Pv, t为包含满足d(s, u)=|Ps, u|, d(v, t)=|Pv, t| and |P1|=|Ps, u|+|Pv, t|+1的边(u, v)的st-路。

      假设路径P2=${\tilde P_{s,u}} \cup (u,v) \cup {\tilde P_{v,t}}$ 是包含边(u, v)的最短st-路。那么,|P1|≥|P2|。在P2d(s, u)=|${\tilde P_{s,u}}$|, d(v, t)=|${\tilde P_{v,t}}$|。由于Ps, u是源点s到点u的最短路径,则|Ps, u|≤|${\tilde P_{s,u}}$|。同理,|Pv, t|≤|${\tilde P_{v,t}}$|。因此,|P2|=|${\tilde P_{s,u}}$|+|${\tilde P_{v,t}}$|+1≥|Ps, u|+|Pv, t|+1=|P1|, 即|P1|=|P2|。Ps, u∪(u, v)∪Pv, tu, v-SPE。

      在例2.2中,因为路径Ps, c∪(c, d)∪Pd, t=(s, a, c, d, e, t)是c, d-RP,所以是c, d-SPE。图3中的另一个例子,因为边缘(7,8)只存在7,8-RP,所以7,8-SPE是(s,1,2,7,8,9,10,11,t)。

      定理2.3:在G-e-C1中,如果${P'}_{s,u} \cap {P'}_{v,t}{\rm{ = }}\emptyset $, ${P'}_{s,u} \cap P_{v,t}^{}{\rm{ = }}\emptyset $ 并且 $P_{s,u}^{} \cap {P'}_{v,t}{\rm{ = }}\emptyset $u, v-SPE是${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$, ${P'}_{s,u} \cup (u,v) \cup P_{v,t}^{}$$P_{s,u}^{} \cup (u,v) \cup {P'}_{v,t}$中的最短路径。

      证明. 在G-e-C1中,${P'}_{s,u} \cap {P'}_{v,t}{\rm{ = }}\emptyset $ 说明${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$u, v-RP。根据3.2定理${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$u, v-SPE。在图G中,${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$是经过(u, v)但不经过C1的最短st-路。$P_{s,u}^{} \cap {P'}_{v,t}{\rm{ = }}\emptyset $${P'}_{s,u} \cap P_{v,t}^{}{\rm{ = }}\emptyset $时,Ps, u∪(u, v)∪${P'}_{v,t}$${P'}_{s,u}$∪ (u, v)∪Pv, tu, v-CPs。两条路径中较短的路径是不仅经过图G中(u, v)也经过C1的最短路径。

      因此,利用d*和d**的度量,我们发现最短的st-路不通过C1。${P'}_{s,u} \cup (u,v) \cup {P'}_{v,t}$, ${P'}_{s,u} \cup (u,v) \cup P_{v,t}^{}$ and $P_{s,u}^{} \cup (u,v) \cup {P'}_{v,t}$中最短的为u, v-SPE。

      观察:C1对应于检测到的边缘并随检测到的边缘而变化。

      推论2.1:存在一个子图G'$ \subset $G,使得G'的最短u, v-RP是u,v的G-SPE。

      证明是显而易见的,因为u, v-SPE本身是G的子图。

      表1显示了路径长度指标的归纳,由此可见:

      Table度量Length
      G-ed*L’=|Ps, u|+|Pv, t|+1
      G-e-C1d**L’’= min{|Ps, u|+$|{P'}_{v,t}|$+1, $|{P'}_{s,u}|$+|Pv, t| +1, $|{P'}_{s,u}|$+$|{P'}_{v,t}|$+1}
      ………………
      G-e-$\sum\limits_k {{C_k}} $${d^{\overbrace {* \cdots *}^{k{\rm{+1}}}}}$L(k+1)’=min{$|P_{s,u}^{(k - 1)'}|$+$|P_{v,t}^{(k)'}|$+1, $|P_{s,u}^{(k)'}|$+$|P_{v,t}^{(k - 1)'}|$+1, $|P_{s,u}^{(k)'}|$+$|P_{v,t}^{(k)'}|$+1}

      表 1  路径长度的度量标准

      Table 1.  Metrics of path lengths

      推论2.2:d*的度量中,如果Ps,u∩Pv,t≠$\emptyset $,则L'≤|SPE|。

      根据定理3.2,很明显如果Ps, uPv, t=$\emptyset $,在d*的度量中,L’=|SPE|;否则,如果Ps, uPv, t$\emptyset $,则L’≤|SPE|。因此,L’≤|SPE|。同理,对于每一个度量,d(s, u)≤d*(s, u)≤d**(s, u)≤…并且d(v, t)≤d*(v, t)≤d**(v, t)≤…。因而L’≤L’’≤…≤|SPE|。

      图4中,我们可以看到每个步骤都对上一步进行进一步度量。事实上,检测所有冗余边是基于SPE的值,而不是SPE本身。在我们的算法设计中,我们并没有尝试寻找SPE,而是使用SPE的长度或其近似值。

      图  4  从PP到SPE的长度矩阵

      Figure 4.  Length matric from PP to SPE

      以上分析侧重于有向边(u, v)。对于边(vu),操作是相同的。不可否认,存在最短路径不唯一的情况,实际上这并不会影响冗余边的检测,因为PP,RP和CP重复检查两个节点之间的最短路径。更明确地,如果通过删除Ck损坏了最短路径之一,则度量将测量其他最短路径。 

    • 为了检测一条边边是否冗余,我们只需要得到SPE长度的近似值。主要是在d*, d**, d***, …, ${d^{\overbrace {* \cdots *}^k}}$中找到RP,直到节点st没有连接或者在G-e-∑kCk中找到RP(包括同时为CP和RP的路径)。根据定理3.2和3.3,推论3.1和3.2,SPE必须是RP和CP中最短的一个。用于检测冗余边的算法细节如下所示

      网络归约程序(NRP):

      输入:G (V, E),源点s,汇点t,边uv,直径限制D

      输出:边uv有/无关

      步1:运行sub 2得到关于边(u,v)的DT1=DT;

      步2:运行sub 2得到关于边(u,v)的DT2=DT;

      步3:如果 min {DT1, DT2}≥D,边uv为冗余边,反之,则边uv为有关边。

      子程序1: (Sub 1) Dijstra的算法[7]

      输入:图G (V, E),节点x,y

      输出:节点x至节点y的最短路径Px, y

      子程序2: (Sub 2) 冗余边检测

      输入:G (V, E),源点s,汇点t,边(u, v),直径限制D

      输出:DT

      步1: G=G-uv,如果|Ps, u|+|Pv, t|≥D, DT=∞,返回;如果Ps, uPv, t=$\emptyset $, DT=|Ps, u|+|Pv, t|,返回;否则执行步2;

      步2:C=Ps, uPv, t, G=G-C,执行Sub1获得Ps, uPv, t

      步3:如果Ps, uPv, t=$\emptyset $,执行步4;否则执行步2;

      步4:取消上个路径,比方说${P'}_{s,u}$${P'}_{v,t}$,设定P1 = $P_{s,u}^{} \cup (u,v) \cup {P'}_{v,t}$并且P2 =${P'}_{s,u} \cup (u,v) \cup P_{v,t}^{}$,如果P1P2都是RP,则DT=min{|Ps, u|+|Pv, t|, |Ps, u|+|${P'}_{v,t}$|, |${P'}_{s,u}$|+|Pv, t|};否则,执行步5;

      步5:取消之前所有路径,比方说{${P'}_{s,u}$, ${P''_{s,u}}$, …} 以及{${P'}_{v,t}$, ${P''}_{v,t}$, …},DT=min{|Ps, u|+|Pv, t|, |Ps, u|+|${P'}_{v,t}$|, |Ps, u|+|${P''}_{v,t}$|, …, |${P'}_{s,u}$|+|Pv, t|,|${P''_{s,u}}$|+|Pv, t|, …}.//*步5旨在完全检测冗余边。

      复杂性分析:

      Dijkstra’s的最短路径算法的时间复杂度在子程序1中是O(n2)[7]。为了执行子程序2,我们删除了Ci (i=1, 2, …, k)。对于Ci$\emptyset $E,在子程序2中最多检测到|E|条边。因为n-1≤|E|≤n (n-1)/2,我们执行Dijstra算法最多n(n-1)/ 2次,因此所提算法(步骤1~4)的时间复杂度为O(n2) ∙ n2=O(n4)。

      将归约过程整合到因子分解定理中,我们得到:

      可靠性计算程序(RCP)

      输入:G (V, E),源点s,汇点t,p,直径限制D

      输出:Rst(G, D)

      步1:如果G直径小于或等于D,执行步3;否则执行步2;

      步2:执行NRP以获得新网络G0

      步3:G0中随机选择边e;

      步4:递归计算Rst(G*e, D);

      步5:递归计算Rst(G-e, D);

      步6:Rst(G, D)=pRst(G*e, D)+qRst(G-e, D)。

      复杂性分析:文献[8]表明,对于D=2,Rst(G, D)可以在多项式时间内确定,并且计算D, D≥3的固定值的Rst(G, D)是NP-难问题。

    • 在本节中,我们将说明检测冗余边的不同拓扑,并显示Petingi算法与我们算法之间的比较。图5说明了四个图a)循环C [6]; b)Arpanet [6]; c)欧洲光网络[6]; d)加齐大学网络[6]。该算法被编码为MATLAB程序,并在PC(Intel Core i5; 2 450 M; 2.5 GHz CPU)上实现。

      图  5  拓扑示意图

      Figure 5.  Illustration of four topologies

      表2显示了所提算法和Petingi算法[2]之间冗余边数和CPU时间的比较,其中,*IE1, T1:我们算法的冗余边数量和CPU时间;IE2, T2:Petingi算法冗余边数量和CPU时间[2];T:未减少计算可靠性的CPU时间。当D=3时,在(a)中检测到两个冗余边,并且CPU时间节省0.0076 s。当D=5时,我们在(b)中找到两个冗余边,CPU时间节省4.439 s。在许多例中,通过使用我们的算法可以完全找到冗余边。通常,冗余边的数量与直径限制D密切相关。例如,在图5(c)表2中,D越小,冗余边越多,CPU时间越少。当D<7时,我们的算法检测到的冗余边比Petingi算法更多。然而,当D=7时,Petingi算法的冗余边数与我们的相同,并且CPU时间相近。

      GDRst(G, D)TIE1T1 (s)IE2T2 (s)T1/ T2
      a30.972 924580.019 860.027 40.722 627 737
      b50.987 71 675172.182156.6210.329 557 469
      c50.978 3>2 days163.257156.1980.525 492 094
      c60.978 3>2 days52 153.75643 144.7560.684 872 213
      c70.978 4>2 days257 464.543257 468.7530.999 926 743
      d40.875 623150.168 640.525 30.320 959 452
      d50.949 131110.095 900.343 50.279 184 862
      d60.949 137810.096 600.347 90.277 665 996

      表 2  数值结果(p=0.9)

      Table 2.  Table II Numerical results with p = 0.9

      图  6  比较不同D值的示意图

      Figure 6.  An illustration for comparison of different values of D

      表3显示了我们的算法和Petingi算法之间冗余边数和CPU时间的比较,其中,IE1, T1:我们算法的冗余边数量和CPU时间;IE2T2:Petingi算法冗余边数量和CPU时间[2]。总的来讲,Petingi的算法和我们的算法都能有效地检测不相关的边缘。如果D的值太小,则Peting的算法更快,因为相关边的数量很小。例如,由于网络没有长度为3,4和5的路径,因此在D=2,3的网络中有20个冗余边(只有边s1和1t是相关的)。但是,我们的算法的优点在D=4, 5, 6, 7和8时通过事实凸显出来。原因是我们的算法能够在检测冗余边时清楚地找到PP,从而找到最内部冗余边。因此,计算可靠性的相应CPU时间进一步减少。最后,从st的最大距离是9,此时,我们的算法和Petingi算法的CPU时间接近。

      DRst(G, D)IE1T1 (s)IE2T2 (s)T1/ T2
      20.8100201.009 759 200.102 370 9.863 817 525
      30.8100200.078 654 200.052 092 1.509 905 552
      40.8100200.082 933 170.096 517 0.859 257 955
      50.8100200.050 252 170.073 968 0.679 375 865
      60.9283110.218 298 62.526 741 0.086 395 084
      70.934290.338 099 014.941 998 0.022 627 429
      80.934770.652 814 014.906 975 0.043 792 52
      90.9414014.945 633 014.758 551 1.012 676 177

      表 3  冗余边的检测及可靠性计算时间(p=0.9)

      Table 3.  Table III Detection of irrelevant edges and computation of reliability for p = 0.9

    • 我们在检测直径限制可靠性的冗余边方面做了进一步的工作。提出的一些路径长度度量来改进检测隐藏的冗余边的方法。实例分析结构表面所提出的算法能够在多项式时间(O(n4))中识别更多冗余边。

(6)  表(3) 参考文献 (8) 相关文章 (20)

目录

    /

    返回文章