An Improved Algorithm for Multi-constrained Routing

摘要

The research on multi-constrained QoS routing is always challenging. The problem of finding a path that satisfies multiple constraints has been proved a NP-complete problem. Hence, several heuristic routing algorithms were proposed to find the solution. Based on the analysis of these algorithms, an improved multi-constrained routing algorithm, enhanced H_MCOP (EH_MCOP), is proposed. The new algorithm adopts the idea of nodes relaxation in the HJVICOP algorithm, but is improved in the method of calculating the shortest path length through a node. In order to improve the performance of the new algorithm, the concept of dominated path is added to the process of selecting more weights sum for path calculation. Large simulations prove that the improved algorithm has better performance in the success ratio and finding the shortest path than the HJVICOP algorithm.