一种基于非线性长度的多约束路由算法*

满足多个约束的QoS路由问题已经被证明是NP完全问题。在分析了多种路由算法的基础上，设计了一种高效的多约束路由算法。该算法采用非线性路径长度计算方法。为提高算法的成功率，在节点的松弛过程中设计了节点动态路径长度计算，允许节点作多次松弛。为提高算法的执行效率，在节点正向松弛和反向估计过程中引入了受控路径的思想，使算法得到了优化。大量仿真表明，该算法在最短路径获取和路由发现成功率方面都有高效的表现。

Algorithm for multi constrained routing based on nonlinear path length

The problem of finding a path that satisfies multiple constraints has been proved a NP-complete problem.Based on the analysis of some algorithms in this field,proposed an efficient multi-constrained routing algorithm.The new algorithm adopted the idea of nonlinear path length.In order to improve the success ratio,designed a dynamic path selection method for nodes,which demanded that nodes be relaxed for more times.For the reason of improving algorithm efficiently,added the concept of dominated path to the process of selecting more weights sum for path calculation.Large simulations prove that the new algorithm has high efficiency in success ratio and finding the shorter path.