基于多个QoS约束的路径选择算法

An Algorithm for Finding Paths with Multiple QoS Constraints

寻找同时满足多个独立的QoS约束的路径是一个NP完全问题。提出一种解决多约束路径问题的有效算法———多约束最小跳路径算法(MHMCA),该算法首先利用Bellman Ford最短路径算法进行标记,并删除图中的无用链路,在简化后的图中使用基于堆栈的深度优先搜索算法寻找所有满足约束的最小跳可行路径。最坏情况下,算法的时间复杂度为O(n3)。仿真结果表明,该算法寻找具有最小跳可行路径的成功率高,接近于最优算法。

Finding a path with multiple independent QoS constraints is an NP-complete problem.An efficient algorithm called Multi-Constrained Minimum-Hop Path Selection Algorithm (MHMCA) is put forward to solve multi-constrained path.First uses Bellman-Ford shortest path algorithm to label and deletes those useless links in graph, so that the graph can be reduced. Then in the reduced graph, all feasible minimum hop paths with multiple constraints can be found by using stack-based depth first search algorithm. The worst-cast computational complexity of our algorithm is O (n^3). A large number of simulations demonstrate that the algorithm has highly success rate in finding feasible paths with minimum-hop count, and is close to the optimum algorithm.