利用重要性贡献矩阵确定通信网中最重要节点

针对已有的节点重要性评价方法,基于节点的移除可能导致网络拓扑结构变化的不足,提出了一种利用节点间关联特性的通信网络节点重要性评价方法.该方法定义的节点重要性贡献矩阵(NICM,Node Importance Contribution Matrix)考虑了网络中不同节点间的联接关系对节点重要性的影响,每个节点对其相邻节点重要程度的贡献与该节点的度有关,节点的初始重要性设为该节点的介数.利用该算法对典型网络的节点重要性进行了分析,并且与移除节点的方法进行了对比.实验结果表明,所提出的算法无须考虑网络拓扑结构的变化,结果精确并能正确评价节点对网络资源的控制能力.

不确定情形下通信网络最短路径关键点问题

在通信网络中,因突发事件造成通信路由节点毁坏或者中断的现象时有发生,传输的数据包不得不从中断处沿着最短的替代路径行进到数据包的接收节点,在这种情形下,哪个路由节点中断使得数据包实际行进的总路程最长呢?从通信网络管理的角度来看这是一个非常重要的问题。对该问题,以前的文献都是从确定情形(事先具有节点中断的完全信息)下进行研究的,本文从不确定情形(只有数据包行进到中断节点的邻接点时才获得该节点中断的信息)的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点概念,给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析,比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题,指出了不确定情形下最短路径关键点问题更具有实际意义。

寻找独立路径问题的一个关键顶点和一条关键弧

通信网络中不同的顶点和弧在多径路由中的作用具有差异性,为此,提出了独立路径问题的关键顶点和关键弧问题.若由定义来求关键顶点和关键弧,算法效率太低.对于弧独立路径数问题,文中引入关键度的概念来量化每个顶点和每条弧的关键程度,发现并证明了顶点的关键度与出度的关系,并由此设计了求关键顶点的算法.根据独立路径数问题本身的特点,提出了求弧独立路径数问题关键弧及顶点独立路径数问题关键顶点和关键弧的方法.对于K-弧独立路径问题,文中利用网络流理论构造替代路径来寻找关键顶点和关键弧.通过变换网络结构,用相似的方法求K-顶点独立路径问题的关键顶点和关键弧.