筛选:  算法设计论文题目 递归算法论文 排序算法论文 论文中算法描述 分布式存储论文 交换机论文 贪婪算法论文 有关遗传算法的论文 计算机算法论文 计算机算法分析论文

【函授论文】有关基于匈牙利算法评估路由算法中网络负载的方法(论文材料)

星级: ★★★★ 期刊: 学报作者:张方爽 段新明 浏览量:6111 论文级别:经典本章主题:算法路由原创论文: 5156论文网更新时间:审核稿件编辑:Yves本文版权归属:www.5156chinese.cn 分享次数:2054 评论次数: 3676

导读:现在请大家一起欣赏本篇文章算法路由专业方面的毕业论文范文,为广大学生们写作毕业论文是提供参考帮助。

摘要:最坏情况的吞吐率是衡量路由算法性能的重要因素之一.负载最重的地方是最坏情况吞吐率的体现,因此最坏情况的吞吐率在路由算法中很关键.在此基础上本文提出了通过利用匈牙利算法来评估网络负载的方法并且通过实验仿真进行比较.将匈牙利算法和穷举法运用到Oblivious路由中的O1TURN、VAL等算法中进行比较.实验结果表明运用该方法与利用传统的穷举法相比,可以大大减少计算量、降低时间复杂度,实验结果证明了方法的可行性和有效性.

关键词:匈牙利算法;最坏情况吞吐率;Oblivious路由;穷举法

中图分类号:TP393文献标识码:A

1引言(Introduction)

路由算法是决定网络性能重要因素之一,最坏情况的吞吐率是衡量路由算法的重要指标.通过随机选择路由路径网络传输过程中故障节点绕道路由问题,以及自适应网络选择路由的路径问题,负载最重的地方是最坏情况吞吐率的体现,因此最坏情况的吞吐率在路由算法中很关键[1,2].本文通过利用匈牙利算法的思想计算网络吞吐率的负载.利用Oblivious路由功能的线性,找到最坏情况的流量模式被视为二分图的最大权重匹配.使用这种结构,问题通常在多项式时间内解决,快速产生确切的最坏情况结果.使用最坏情况来确定特定系统的最坏情况吞吐.WilliamJ。Dally等人提出将匈牙利算法运用到Oblivious路由中的DOR和ROMM中评估吞吐率[3],在此基礎上本文引入扩展到Oblivious路由的O1TURN等算法中[1,4].

2相关知识(Relatedinformation)

匈牙利算法是由匈牙利数学家Edmonds于1965年提出,因而得名.匈牙利算法是基于Hall定理中充分性证明的思想,它是二分图匹配最常见的算法,该算法的核心就是寻找增广路径,它是一种用增广路径求二分图最大匹配的算法.用于为任意网络拓扑上的路由功能找到确切的最坏情况模式.

网络负载对性能有很大的影响.一般而言,对于给定目的节点的分布,网络负载对网络平均消息延迟的影响比其他设计参数的影响大很多,因此需要合理的选择这些参数.而且,吞吐率主要受通信模式也就是目的节点的影响.因此,计算网络负载时非常重要.

由于网络通道不饱和,可以利用通道负载的线性相关.线性意味着特定通道上的负载仅仅是每对源节点到目的节点引起的负载的总和.实际上这个可以将最坏情况模式搜索限制为置换矩阵.然后,通过将所有置换矩阵表示为单个二分图内的匹配,并且用源节点到目的节点通道负载的边进行加权,则最大权重匹配产生特定通道及其相应负载的确定最坏情况的置换排列.最后,在网络中所有通道的集合上重复以找到最差情况下,最大权重匹配的理想吞吐量[1,3].

基于匈牙利算法评估路由算法中网络负载的方法
算法路由毕业论文提纲范文

Oblivious路由算法是一种在进行路由决策时,不考虑网络的状态,具有较高的灵活性.评估Oblivious路由算法的最坏情况吞吐率的关键是利用算法通道负载线性的特性.也就是说,只要网络的通道不饱和,特定通道c上的负载就是每对源节点到目的节点在流量模式中的所有负载的总和[3]:

本篇有关基于匈牙利算法评估路由算法中网络负载的方法论文范文综合参考评定如下
有关论文范文主题研究:算法方面的毕业论文提纲范文大学生适用:毕业论文8000字
相关参考文献下载数量:664写作解决问题:如何写毕业论文提纲范文
毕业论文开题报告:写作论文任务书职称论文适用:职称论文写作,职称评中级
所属大学生专业类别:算法专业毕业论文提纲范文论文题目推荐度:优质标题

其中,流量矩阵(Λ):任意双随机矩阵,其中入口λi,j表示从源i到目的j的通道流量;遗忘路由算法(π):一种路由算法;通道负载(γc(π,Λ)):流量矩阵Λ和路由选择函数π在每个周期信道c的分组数量.

定理1:对于任何Oblivious的路由算法,置换矩阵总能实现理想的最坏情况吞吐量.在论文[3]中已得到了证明.

在穷举法中找到最坏情况的负载,就要考虑所有的置换排列.时间复杂度为O(N!),是一个NP难问题,计算量很大.为此文本利用匈牙利算法计算最坏情况的吞吐率.大大降低了时间复杂度,提高算法的效率[2].

算法专业函授论文撰写
观看次数:2491 点评人数:664

3算法模式(Algorithmmode)

3。1穷举法算法模式

(1)初始化数组;

(2)利用递归找出所有情况的排列;

(3)找到最后的结果.

3。2匈牙利算法的基本模式

由于任何特定的置换,使用Oblivious路由算法的线性特性,二分图可用于表示单个通道上的负载.二分图匹配的最大流算法的核心算法是找增广路径(augmentpath)其基本模式如下:

(1)初始时最大匹配为空;

(2)while找得到增广路径.

do把增广路径加入到最大匹配中.

引理1:如果从一个点A出发,没有找到增广路径,那么无论再从别的点出发找到多少增广路径来改变现在的匹配,从A出发都永远找不到增广路径.

匈牙利算法和最大流算法很相似.不同之处在于增广路径就有它一定的特殊性,虽然根本上是最大流算法,但是它不需要建构网络模型.二分图最大流的核心算法中找增广路径的基本模式及相关定理,引出匈牙利算法基本模式,其基本模式如下:

(1)初始时最大匹配为空;

(2)for二分图左半边的每个点i;

(3)do从点i出发寻找增广路径.如果找到,则把它取反(即增加了总了匹配数).

如果二分图的左半边一共有n个点,那么最多找n条增广路径.如果二分图 有m条边,那么每找一条增广路径(DFS或BFS)时最多把所有边遍历一遍,所花时间也就是m.所以总的时间复杂度大概是O(n*m).

KM(Kuhn-Munkras)算法用来解决最大权匹配问题的算法.其基本原理:KM算法是通过给每个顶点一个标号(叫做顶标)来把求最大权匹配的问题转化为求完备匹配的问题.设顶点Xi的顶标为A[i],顶点Yj的顶标为B[j],顶点Xi与Yj之间的边权为w[i,j].在算法执行过程中的任一时刻,对于任一条边(i,j),A[i]+B[j]>=w[i,j]始终成立.KM算法基本模式:

(1)初始化可行顶标的值;

(2)用匈牙利算法寻找完备匹配;

(3)若未找到完备匹配则修改可行顶标值;

(4)重复(2)(3)直到找到相等子图完备匹配为止.

4网络吞吐率评估(Networkthroughputevaluation)

使用Oblivious路由算法,对于任何特定的置换排列,二分图可用于表示单个通道上的负载.如图1所示,第一组N个节点用于表示数据的源节点,第二组N个节点表示数据的目的节点.在每对源节点和目标节点之间添加边,从而获得总共N2个边[3].排列矩阵与二分图的完美匹配之间存在一对一对应的关系.需要注意的是,二分图的结构与底层互连网络的拓扑结构无关.

源节点s到目的节点d的每条边进行加权,使得负载量给一个特定的通道c,即.这些权重由置换引起的负载量仅为其相应二分图匹配中边权重的总和[3-5]如图1所示.对于源到目的对(s,d),用穷举法列举出路由算法生成的从s到d的所有路径,以及包含通道c的每条路径计算边缘权重,是NP问题,时间复杂度是O(N!).

根据二分图的构造,可以找到该图的最大权重匹配.从匹配和排列之间的对应关系来看,找到一个最大权重匹配就相当于评估:其中P是所有置换矩阵的集合.通过在所有通道上重复该操作,可以确定理想的最差情况吞吐量为[3]:

最大权重匹配算法存在.穷举法的时间复杂度O(N!),而利用匈牙利算法计算的时间复杂度O(N3).穷举法和匈牙利算法在效率上的差别,可以看出,利用匈牙利算法求吞吐率算法的性能是相当好的.

5仿真与分析(Simulationandanalysis)

在Mesh网络中,对于Oblivious路由算法论文[3]中对DOR和ROMM算法进行了仿真实验,本文在此基础上扩展了Oblivious中的O1TURN,以及VAL[3,6]算法中.与DOR相比,源节点到目的节点之间的所有流量都集中在单一路径上.ROMM更均匀地将源节点到目的节点流量分布在更多数量的通道上,ROMM选取节点时比较灵活.ROMM和VAL与DOR路由算法不同.ROMM和VAL路由算法是将路由路径分为两个阶段,第一阶段消息从源节点传输到中间节点,在第二阶段消息在由中间节点到达目的地,它们的区别在于选取中间节点方法不同.O1TURN路由算法[1]具有非常结构简单,其随机使用XY或YX路由算法.O1TURN和VAL路由算法都具有良好的最坏情况网路的吞吐率.基于Oblivious的几种通讯模式[1],进行了仿真实验的比较,如表1所示.

当网络规模比较低的情况下利用传统的穷举法和匈牙利算法进行实验仿真得到结果是一样的.如表2所示,采用4×4網络规模进行实验,理论和实验结果证明了利用穷举法和匈牙利算法得到结果是一样的.但是当网络的规模越大时穷举法复杂度成指数级增长,速度很慢,所以无法验证.

实验采用以1000为周期的前提下,利用穷举法和匈牙利算法在不同的网络模式时间效率的比值(运行时间单位:ms).实验以网络模式为2×2、3×3,以及4×4进行比较,如表3结果所示.

表3的结果分析可知,网络模式越大时,传统的穷举法与匈牙利算法的时间效率比值成指数级别增长.从实验结果可知很明显利用匈牙利算法极大的改善了运行时间的效率.采用穷举法的时间复杂度是O(N!),而采用匈牙利算法的时间复杂度是O(N3).当随着网络规模增加时传统的穷举法复杂度会越来越高,速度很慢.利用匈牙利算法评估网络吞吐率可以有效的改善计算的运行速度、提高效率.

6结论(Conclusion)

利用匈牙利算法我们可以在多项式时间内找到Oblivious的路由算法的最坏情况吞吐量,这使得最坏情况的分析变得易于处理.二分图构造来分析Oblivious路由算法是评估最坏情况下网络吞吐率的一个方法.对比穷举法,计算最坏情况下的吞吐率时间效率得到很大改善;在时间复杂度上,穷举法的时间复杂度是O(N!),而利用匈牙利算法的时间复杂度是O(N3).实验通过利用Oblivious路由算法中O1TURN等算法,以及运行时间的对比,证明了利用匈牙利算法评估网络吞吐率的可行性和有效性.

参考文献(References)

[1]SeoD,AliA。Near-OptimalWorst-CaseThroughputRoutingforTwo-DimensionalMeshNetworks[C]。InternationalSymposiumonComputerArchitecture,ProceedingsIEEE,2005,33(2):432-443。

[2]张立,戴一奇。随机Oblivious路由算法中随机性与时间代价的研究[J]。计算机学报,1996,19(5):388-397。

[3]TowlesB,DallyWJ。Worst-casetrafficforobliviousroutingfunctions[C]。FourteenthACMSymposiumonParallelAlgorithmsandArchitectures,ACM,2002,1(1):1-8。

[4]Sullivan,Herbert。Alargescale,homogeneous,fullydistributedparallelmachine,I。[C]。ProcFourthSymposiumonComputerArchitectureACM,1977,5(7):105-117。

[5]J。Upadhyay,V。Varavithya,P。Mohapatra。ATrafficBalancedAdaptiveWormholeRoutingSchemeforTwo-DimensionalMeshes[J]。TransactionsonComputers,1997,46(2):190-197。

[6]RajasekaranS,OverholtR。Constantqueueroutingonamesh[J]。JournalofParallel&DistributedComputing,1991,15(15):

160-166。

[ 参考文献 ]

1、网络拓扑发现算法的研究
(吉林铁道职业技术学院)本文主要针对目前比较常用的网络拓扑发现算法,进行了较深入的理论分析和研究。分析了拓扑发现在网络管理中的重要性,并总结出各算法的优缺点,并提出可以根据应用的实际环境,将

2、ZigBee网络的路由算法分析
王惠清1,周 雷2,王静1 Wang Huiqing´,Zhou Lej2,Wang Jingl (1.泸州医学院现代教育技术中心泸州646000;2中南大学信息科学与工程

3、基于ProE 的复杂尺寸链算法研究
孙春艳张谋 陕西法士特齿轮有限责任公司陕西省西安市710119 随着科技水平进步和对产品性能要求的提高,变速器产品制造装配精度也随之提高;本文基于ProE草绘环境下提出了一种

递归算法论文排序算法论文论文中算法描述


本篇文章浏览概括:本文归纳了怎样写算法毕业论文的开题报告范文和论文标准格式模版规范以及函授算法路由论文轻松写作技巧是为让学生们阅读训练提升写作能力。

本篇有关算法路由毕业论文范文免费供大学生阅读参考-点击更多240787篇算法路由相关论文开题报告格式范文模版供阅读下载
延伸阅读: 基因遗传算法论文算法本科毕业论文遗传算法期刊论文有关算法论文遗传算法毕业论文有关算法的论文人工智能遗传算法论文模糊算法论文数学算法论文算法理论论文
本科论文相似度要求 论文答辩资料 放射论文 国际工程招投标论文 论文研究思路和方法 数学毕业论文范文 建筑节能环保论文 食品营养学毕业论文 环境毕业论文 写自考论文