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

摘要

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