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

The Most Vital Node of the Shortest Path under Uncertainty in Communication Networks

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

In communication networks, data packages often travel longer than the shortest path from source node to destina- tion node due to sudden node failure caused by unexpected events. From the network management point of view, it is important to find the node whose removal results in the longest travel distance between source node and destination node in a network, The most vital node （MVN） prohlem of the shortest path in term of certainty were extensively studied in the past, This paper aims at the most vital node of the shortest path problem under uncertainty （MVN-U）, Firstly, this paper stares the concept of the most vital node of the shortest path under uncertainty, Secondly, it presents an algorithm of computing the MVN-U and analyses its time complexity, and then a numerical result of ATM networks is given, In the end, by comparing the result of MVN-U and MVN problem, we conclude that the MVN-U problem has more practical significance.