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

( ) 第24卷第9期 总第153期 　　　　 　 　系　统　工　程 Vol.24,No .9 2006 年9月　　　　　　　　　 　 　 　 Systems Engineering Sept.,2006 　 文章编号:1001 4098 (2006) 不确定情形下通信网络最短路径关键点问题 1 1,2 1 闫化海 , 徐寅峰 , 刘　明 ( 1. 西安交通大学 管理学院, 西安 陕西　710049; 2. 机械制造系统工程国家重点实验室, 西安 陕西　710049 ) 摘　要: 在通信网络中, 因突发事件造成通信路由节点毁坏或者中断的现象时有发生, 传输的数据包不得不从 中断处沿着最短的替代路径行进到数据包的接收节点, 在这种情形下, 哪个路由节点中断使得数据包实际行 进的总路程最长呢? 从通信网络管理的角度来看这是一个非常重要的问题。对该问题, 以前的文献都是从确定 ( ) ( 情形 事先具有节点中断的完全信息 下进行研究的, 本文从不确定情形 只有数据包行进到中断节点的邻接 ) 点时才获得该节点中断的信息 的角度重新考虑这个问题。本文首先定义了不确定情形下的最短路径关键点 概念, 给出了计算不确定情形下最短路径关键点的算法及其时间复杂性分析。结合实际通信网络的算例分析, 比较了确定情形下最短路径关键点和不确定情形下最短路径关键点问题, 指出了不确定情形下最短路径关 键点问题更具有实际意义。 关键词: 关键点; 不确定情形; 最短路径; 算法 中图分类号: C 931; O 221　　　文献标识码: A . 和 . 给出了时 间复杂性为 ( + G Proietti P Widmyer O m 1　引言 [2] ) 的算法 ; . 等证明了对于任意的 , 最短 n logn A Bar Noy k [3] 路径 关键边问题是 问题 。国内研究方面, 李 在通信网络中, 因突发事件造成通信路由节点毁坏或 k NP Hard 者中断的现象时有发生, 传输的数据包不得不从中断处沿