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

Multiple constraints-based QoS routing algorithm in IP mesh network

作　　者：李敏[1,2] 陆芸婷[1] 邹粤[1,2] 

机构地区：[1]深圳信息职业技术学院,广东深圳518029 [2]深圳大学计算机与软件学院,广东深圳518060

出　　处：《计算机工程与应用》2011年第6期78-81,115,共5页Computer Engineering and Applications

基　　金：国家自然科学基金No.60672150;广东省自然科学基金(No.7008733)~~

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

关 键 词：IPMesh网络 多约束QOS路由算法 剪枝 

分 类 号：TP31[自动化与计算机技术—计算机软件与理论]