计算机工程与科学2011，Vol.33Issue(9)：19-23,5.DOI:10.3969/j.issn.1007-130X.2011.09.004
基于多约束QoS问题的启发式算法
A Heuristic Algorithm for the QoS Problem Based on Multi-Constraints
摘要
Abstract
On the communication network, QoS-based routing has become the hot technique in order to fulfill the requirements of multimedia communications. Generally, finding a path in the network that satisfies multiple independent constraints is known to be NP-complete. In this paper, we discuss the multi-constrained path (MCP) problem. By transforming the problem to discrete dynamic networks, which is acyclic, we propose a more efficient heuristic algorithm for QoS routing. The running time complexity is reduced from O(Tmn) to OiTm), where m is the number of edges and n is the number of nodes, T is an integer defined by the algorithm. Further more, we theoretically prove the correctness of the algorithm. In the end, some experimental results are presented to show that the proposed algorithm performs better than other algorithms when used to solve the MCP problem. This improved heuristic algorithm can also be used in large-scale networks.关键词
QoS路由/路径选择/多约束条件/启发式算法/MCPKey words
QoS routing/path selection/multi-constraints/heuristic algorithm/MCP分类
信息技术与安全科学引用本文复制引用
熊李军,谢政,陈挚,张军..基于多约束QoS问题的启发式算法[J].计算机工程与科学,2011,33(9):19-23,5.基金项目
国家973计划资助项目(613610202) （613610202）
