多约束最短链路分离路径精确算法

• 作者: 张宏科 熊轲 秦雅娟 裘正定 郭宇春
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 服务质量路由 网络可靠性 链路分离路径 多约束路由 最优解
• 年，卷（期）: 2010,（7）
• 页码范围: 1744-1757
• 分类号: TP393
• 字数: 11011字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2010.3589

摘要

在通信的源和目的间寻找两条(主用和备用)链路分离的QoS路径是提供可靠QoS路由的重要途径.现有求解多约束链路分离路径对(multi-constrained link-disjoint path pair,简称MCLPP)的算法难以保证求得存在于任意网络中的可行解和最优解.为解决这一问题,分析了MCLPP问题最优解的性质,提出了精确算法的设计原则,在此基础上给出了求解MCLPP问题的精确算法(link-disjoint optimal multi-constrained paths algorithm,简称LIDOMPA算法),可对任意网络求解客观存在的多约束最短链路分离路径对.为了降低算法的复杂性,引入了候选最优解、紧缩的约束向量和结构化的路径支配3种关键方法,在保障算法精确性的同时,有效地降低了LIDOMPA的搜索空间.大量的实验结果表明,LIDOMPA的求解能力优于现有算法,同时可以实现较低的算法执行时间开销.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	秦雅娟	北京交通大学下一代互联网互联设备国家工程实验室	65	477	10.0	19.0
2	张宏科	北京交通大学下一代互联网互联设备国家工程实验室	231	3247	25.0	51.0
3	裘正定	北京交通大学信息科学研究所	90	1146	16.0	30.0
4	熊轲	北京交通大学信息科学研究所	24	115	6.0	10.0
8	郭宇春	北京交通大学电子信息工程学院	14	468	6.0	14.0