基于有向通信网络的中间节点重要性评价方法-昆明理工大学学报.PDF

第４２卷 第１期 昆明理工大学学报（自然科学版） Ｖｏｌ．４２　Ｎｏ１ 　 ２０１７年２月　 ＪｏｕｒｎａｌｏｆＫｕｎｍｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅＥｄｉｔｉｏｎ） 　 Ｆｅｂ．２０１７  ｄｏｉ：１０．１６１１２／ｊ．ｃｎｋｉ．５３－１２２３／ｎ．２０１７．０１．００９ 基于有向通信网络的中间节点重要性评价方法 张　强，龙　华，高　杰，杜庆治，邵玉斌 （昆明理工大学 信息工程与自动化学院，云南 昆明６５０５００） 摘要：为了分析有向通信网络的中间节点的重要性，本文提出一种以节点表示端到端路由的快 速寻找算法，该算法通过删除不同的中间节点后对端到端之间传输路由数量的影响，判断不同的 中间节点对端到端通信网络的重要程度，某一中间节点的删除导致端到端路由数量越多，则表示 该中间节点越重要．计算实例表明，该方法运算简单，具有一定的实用性． 关键词：中间节点；有向网络；节点删除；路由 中图分类号：ＴＮ９１５．０２ 文献标志码：Ａ 文章编号：１００７－８５５Ｘ（２０１７）０１－００５３－０４ ＥｖａｌｕａｔｉｏｎＭｅｔｈｏｄｆｏｒＩｎｔｅｒｍｅｄｉａｔｅＮｏｄｅＩｍｐｏｒｔａｎｃｅ ＢａｓｅｄｏｎＤｉｒｅｃｔｅｄＣｏｍｍｕｎｉｃａｔｉｏｎＮｅｔｗｏｒｋｓ ＺＨＡＮＧＱｉａｎｇ，ＬＯＮＧＨｕａ，ＧＡＯＪｉｅ，ＤＵＱｉｎｇｚｈｉ，ＳＨＡＯＹｕｂｉｎ （ＦａｃｕｌｔｙｏｆＩｎｆｏｒｍａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇａｎｄＡｕｔｏｍａｔｉｏｎ，ＫｕｎｍｉｎｇＵｎｉｖｅｒｓｉｔｙｏｆＳｃｉｅｎｃｅａｎｄＴｅｃｈｎｏｌｏｇｙ，Ｋｕｎｍｉｎｇ６５０５００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎｏｒｄｅｒｔｏａｎａｌｙｚｅｔｈｅｉｎｔｅｒｍｅｄｉａｔｅｎｏｄｅｉｍｐｏｒｔａｎｃｅｉｎｄｉｒｅｃｔｅｄｃｏｍｍｕｎｉｃａｔｉｏｎｎｅｔｗｏｒｋｓ，ｔｈｉｓｐａｐｅｒ ｐｒｏｐｏｓｅｓａｆａｓｔｓｅａｒｃｈａｌｇｏｒｉｔｈｍｏｆｎｏｄｅｒｅｐｒｅｓｅｎｔｉｎｇｔｈｅｅｎｄ－ｔｏ－ｅｎｄｒｏｕｔｉｎｇ．Ｉｎｔｈｉｓａｌｇｏｒｉｔｈｍ，ｔｈｅｉｍｐｏｒ ｔａｎｃｅｏｆｄｉｆｆｅｒｅｎｔｉｎｔｅｒｍｅｄｉａｔｅｎｏｄｅｓｔｏｔｈｅｅｎｄ－ｔｏ－ｅｎｄｃｏｍｍｕｎｉｃａｔｉｏｎｎｅｔｗｏｒｋｃａｎｂｅｄｅｔｅｒｍｉｎｅｄｂｙｄｅｌｅｔｉｎｇ ｅｎｄ－ｔｏ－ｅｎｄｒｏｕｔｅｓ．Ｔｈｅｉｍｐｏｒｔａｎｃｅｏｆａｎｉｎｔｅｒｍｅｄｉａｔｅｎｏｄｅｉｓｉｎｐｒｏｐｏｒｔｉｏｎｔｏｔｈｅｉｎｃｒｅａｓｉｎｇｑｕａｎｔｉｔｙｏｆｅｎｄ－ ｔｏ－ｅｎｄｒｏｕｔｅｓｄｕｅｔｏｔｈｅｄｅｌｅｔｉｏｎ．Ｆｉｎａｌｌｙ，ｔｈｅｐｒａｃｔｉｃａｌｃａｌｃｕｌａｔｉｏｎｉｎｄｉｃａｔｅｓｔｈａｔｔｈｉｓｍｅｔｈｏｄｉｓｐｒａｃｔｉｃａｌａｎｄ ｅａｓｙｔｏｏｐｅｒａｔｅ． Ｋｅｙｗｏｒｄｓ：ｉｎｔｅｒｍｅｄｉａｔｅｎｏｄｅ，ｄｉｒｅｃｔｅｄｎｅｔｗｏｒｋ，ｎｏｄｅｄｅｌｅｔｉｏｎ，ｒｏｕｔｉｎｇ ０引 言 准确地评估通信网络中节点的重要性对于提高整个通信网络的可靠性有着重大的理论指导和实际应 用意义［１－３］．文献［４］～［６］提出的基于最短路径的节点重要度的计算问题，但实际中通信网络中信息的 传输不是沿着最短路径，而是随机地进行传输，因此在某些网络中利用此种方式对通信网络节点进行重要 ［７］ 度评估并不适用 ．文献［８］提出的生成树法和文献［９］提出的性能梯度法对通信网络节点进行重要性评 价，其不足之处是往往导致通信网络拓扑的结构分割．本文提出一种适用于有向通信网络的端到端的全部 路由以节点形式表示的快速寻找计算方法，该方法可以对有向通信网络中的所有中间节点进行重要性 评价． １端到端全部传输路由计算 有向通信网络一般用一个连通图Ｇ＝（Ｖ，Ｅ）表示，假定其有ｍ个顶点、ｎ条边，其中Ｖ＝｛ｖ，ｖ，ｖ， １ ２ ３ 收稿日期：２０１６－０４－０５．基金项