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

计算机工程与应用 ›› 2011, Vol. 47 ›› Issue (6): 78-81.

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

李敏^1，2，陆芸婷¹，邹粤^1，2

1.深圳信息职业技术学院，广东深圳 518029
2.深圳大学计算机与软件学院，广东深圳 518060

收稿日期:1900-01-01 修回日期:1900-01-01 出版日期:2011-02-21 发布日期:2011-02-21

Multiple constraints-based QoS routing algorithm in IP mesh network

LI Min^1，2，LU Yunting¹，ZOU Yue^1，2

1.Shenzhen Institute of Information Technology，Shenzhen，Guangdong 518029，China
2.Shenzhen University，Shenzhen，Guangdong 518060，China

Received:1900-01-01 Revised:1900-01-01 Online:2011-02-21 Published:2011-02-21

摘要/Abstract

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

关键词: IP Mesh网络, 多约束QoS路由算法, 剪枝

Abstract: 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.

Key words: IP mesh network, multiple constraints-based QoS routing algorithm, branch cut

李敏^1，2，陆芸婷¹，邹粤^1，2. IP Mesh网络的多约束QoS选路研究[J]. 计算机工程与应用, 2011, 47(6): 78-81.

LI Min^1，2，LU Yunting¹，ZOU Yue^1，2. Multiple constraints-based QoS routing algorithm in IP mesh network[J]. Computer Engineering and Applications, 2011, 47(6): 78-81.

[1]	张良，张增，舒伟华，梅魁志. 基于YOLOv3的卷积层结构化剪枝[J]. 计算机工程与应用, 2021, 57(6): 131-137.
[2]	徐晓东，王俊杰. 面向边缘端的施工人员实时检测方法[J]. 计算机工程与应用, 2021, 57(23): 280-286.
[3]	黄文斌，陈仁文，袁婷婷. 改进YOLOv3-SPP的无人机目标检测模型压缩方案[J]. 计算机工程与应用, 2021, 57(21): 165-173.
[4]	蒋润熙，阿里甫·库尔班，耿丽婷. 面向轻量化网络的安全帽检测算法[J]. 计算机工程与应用, 2021, 57(20): 263-270.
[5]	张宏丽，白翔宇. 利用优化剪枝GoogLeNet的人脸表情识别方法[J]. 计算机工程与应用, 2021, 57(19): 179-188.
[6]	顾军华，苏鸣，张亚娟，张丹红. 基于位编码链表的快速频繁模式挖掘算法研究[J]. 计算机工程与应用, 2020, 56(19): 86-93.
[7]	付佐毅，周世杰，李顶根. 轻量级目标识别深度神经网络及其应用[J]. 计算机工程与应用, 2020, 56(18): 131-136.
[8]	高曼，韩萌，雷冰冰. 高效用模式产生策略综述[J]. 计算机工程与应用, 2020, 56(16): 1-12.
[9]	李艳，王阳阳，张红岩，武优西. 不可达顶点剪枝算法及其在最短路径中的应用[J]. 计算机工程与应用, 2020, 56(15): 51-57.
[10]	杨静雅，孙林夫，吴奇石. 基于汽车售后故障数据的关联分析[J]. 计算机工程与应用, 2019, 55(22): 219-224.
[11]	李智翔，李赟，贺亮. 一类特殊的非抢占式周期任务的调度方法[J]. 计算机工程与应用, 2018, 54(9): 22-27.
[12]	李光早，王士同. 基于骨干粒子群的弹性稀疏人脸识别[J]. 计算机工程与应用, 2017, 53(17): 143-148.
[13]	姚博1，冯宏伟1，高原2，马佳丽1，冯筠1. 过必经节点集的动态剪枝搜索算法[J]. 计算机工程与应用, 2017, 53(15): 57-62.
[14]	毛燠锋1，钱振兴2，万定生1，朱跃龙1. 基于条件函数依赖的CTANE算法研究与应用[J]. 计算机工程与应用, 2017, 53(11): 85-89.
[15]	任建华，高立明. 基于聚类的两段式孤立点检测算法[J]. 计算机工程与应用, 2016, 52(20): 98-102.