IP Mesh网络的多约束QoS选路研究

多约束QoS路由算法一直是研究重点和难点,是一个有待解决的NP完全问题。针对IP Mesh网络的特点,设计出相应的完全图,并且推出了n个节点的完全图路径总数目公式。提出了一种CBFS_MCP算法,首先用Dijsktra最短路径算法对节点和边进行删减,将完全图简化,再在简化图上用类BFS算法通过"约束条件夹逼"和不断剪枝,寻找一条从起点s到终点t的符合两个约束条件的可行路径。实验结果表明CBFS_MCP算法有着良好的算法性能。

Multiple constraints-based QoS routing algorithm in IP mesh network

Multiple constraints-based QoS routing algorithm has always been researched as a point and a difficulty, and which to be reserved as a NP-complete problem.This paper designs the completed graph for the characteristic of IP mesh network, and deduces the formula of the path total number of the completed graph with n nodes.This paper gives a CBFS_MCP algorithm.It uses the Dijkstra algorithm to delete the nodes and the edges, and then predigests the completed graph.At the foundation of the predigesting graph, the similar BFS algorithm is used by the method of ＂restrict conditions nip＂ and branch cutting, so that a feasible path with two restricting conditions from the beginning node s to the ending node t can be found.The simulations show that this algorithm can increase the performance greatly.