基于多约束QoS问题的启发式算法

• 作者: 张军 熊李军 谢政 陈挚
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: QoS路由 路径选择 多约束条件 启发式算法 MCP
• 年，卷（期）: 2011,（9）
• 所属期刊栏目: 计算机网络与信息安全
• 页码范围: 19-23
• 分类号: TN915.1
• 字数: 4682字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2011.09.004

摘要

由于多媒体通信的需要,QoS路由技术已成为通信网络中研究的热点.通常情况下,在网络中寻找同时满足多个独立加性约束条件的路由是一个NP完全问题.本文探讨了多约束条件下的路径选择(MCP)问题,通过将MCP问题转化为离散化的动态网络,得到了一个性能更好的启发式QoS路由算法,复杂度从O(Tmn)降低为O( Tm),其中m、n分别是节点数和边数,T是算法定义的正整数,并在理论上证明了算法的正确性.最后给出实验举例,并通过与现有算法性能比较,表明改进的启发式算法能快速、有效地解决MCP问题,且适用于大规模的网络系统.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	张军	北京航空航天大学电子信息工程学院	187	1353	20.0	28.0
2	陈挚	国防科学技术大学理学院	11	35	3.0	5.0
3	谢政	国防科学技术大学理学院	15	51	4.0	6.0