作者:王旭; 陈金阳; 阮晓莉 期刊:《湖北师范大学学报·哲学社会科学版》 2016年第02期
为研究最佳旅游线路设计问题,通过建立网络图模型,利用Dijkstra算法及哈密顿回路法,分析、计算比较得出最优解.
作者:耿海军; 尹霞 期刊:《计算机科学》 2019年第08期
学术界提出利用LFC(Loop-Free Criterion,LFC)规则来解决网络中所有可能出现的单链路故障情形,但是已有的针对LFC的实现方式的计算开销随着网络节点平均度的增加而增加,给路由器带来了大量的额外负担。针对该问题,文中研究如何降低LFC实现方式的计算开销,提出了一种基于增量最短路径优先(Incremental Shortest Path First,i-SPF)的域内高效路由保护算法(Efficient Intra-domain Routing Protection Algorithm Based on i-SPF,ERPIS...
作者:马慧慧; 卢昱; 王增光 期刊:《计算机测量与控制》 2018年第07期
网络拓扑发生变化时,利用静态Dijkstra算法重新计算最短路径树(SPT)会造成冗余计算;动态Dijkstra算法解决了这个问题,但目前动态算法一般是基于有向网络模型进行的研究;在已有的动态Dijkstra算法基础上,提出适用于无向网络的动态Dijkstra算法;算法主要解决了在无向网络中如何确定待更新节点的问题,对网络中的一条边权值增大、减小的处理方法进行了详细描述,并对已有的算法的筛选机制进行了优化;为了验证算法的正确性,用仿真实验实...
作者:程佳乐; 李伟东 期刊:《计算机工程与科学》 2018年第12期
考虑具有树和路约束的平行机排序问题,其工件集对应于无向图(有向图)的边(弧)集。目标是选取工件集的一个子集使其满足树或路的约束,将其放在平行机上处理,使得机器的最大完工时间(makespan)尽可能地小。通过分析此类问题的组合性质,得到如下结论:在K-树约束下,利用最小支撑K-树的性质可得一个有效多项式时间近似方案;在两固定点间路的约束下,通过构造辅助实例以控制边的权重,分析辅助实例的输出值与目标实例最优值之间的关系,利用...
作者:陈琳; 杨志云; 徐正全 期刊:《计算机工程》 2005年第01期
基于标签技术和最短费用路径,根据延迟约束不断调整多播路由树中部分路径以减少路径延迟,提出了一种满足延迟约束费用最小的多播路由启发式算法.仿真结果表明,该算法得到的多播路由树具有较小的费用,平均路径延迟也比较小,并且避免了其它同类算法的高复杂性.
作者:谢双双; 管有庆 期刊:《计算机技术与发展》 2018年第01期
数据聚集是无线传感器网络中的基本操作,聚集感测到的数据并发送到Sink节点。传感器网络存在能量约束,网内数据聚集技术可以减少传输的数据量,有效地节省能量。然而大部分的网内数据聚集都采用先发性(proactive)的路由协议,不能根据事件动态建立数据聚集结构。为解决这个问题,提出一种基于动态分簇路由的网内数据聚集算法(In—net’work Data Aggregation based on Dynamic—Clustering Routing,IDADCR)。该算法考虑节点...
作者:朱秀峰; 钱华林; 柴政 期刊:《微电子学与计算机》 2005年第06期
文章主要介绍IPv6组播的原理机制,当前用于实现IPv6组播的两个基本协议MLD协议与PIM-SM协议,以及MLD协议与PIM-SM协议之间的互操作.同时还详细描述了组播共享树和最短路径树的建立过程.
作者:周有; 魏文敏 期刊:《电子设计工程》 2017年第18期
针对PIM稀疏模式从共享树RPT向最短路径树SPT切换过程中.发生的组播数据流丢帧现象,根据网络拓扑结构中源S和汇聚点RP邻居、接口的相同与否。构建3种不同的仿真模型:到源S的RPF接口与到RP的RPF接口不同、到Source邻居与到RP邻居相同、到Source邻居与到RP邻居不同,并结合Wireshark网络协议分析工具进行数据包分析,结果表明:实现了PIM稀疏模式在数据切换过程中的零丢包,提高了网络服务质量。
作者:曹雪峰; 于万国; 蔡永华; 朱会卿; 陈日升 期刊:《实验技术与管理》 2016年第12期
采用GNS3中整合的IOU和VirtualBox构建虚拟网络实验环境,设计了IP多播原理实验方案。利用Wireshark协议分析软件捕获报文,通过对报文的分析阐述了IGMP协议加入、离开多播组的工作过程,PIM-SM协议共享树和最短路径树的加入、剪枝过程,多播源注册过程,共享树和最短路径树之间的切换过程。验证了IGMP和PIM-SM协议的工作过程,使学生从理论和实践两方面更好地理解IP多播的工作原理。
作者:王少华; 刘忠强 期刊:《山东广播电视大学学报》 2006年第02期
随着Intenet的迅猛发展,网络拓扑也变得错综复杂,而MPLS技术的应用,尤其是其中日趋成熟的分支如MPLSTE,给我们提出一个课题,必须借助相关工具解决网络流量工程及网络规划问题。本文针对一个Te问题的实例,给出其数学描述,并提供了利用LINDO工具的解决方案。
作者:程奕; 徐家品 期刊:《太赫兹科学与电子信息学报》 2007年第04期
为了有效利用网络资源,增强传输数据包的安全性,在优先开放最短路径(Open Shortest Path First,OSPF)协议的基础上,提出了一种改进的多路径路由算法。将寻找到的多条不相交路径添加到路径集Px中,将相交路径添加到备用路径集Cx中。当Px集中路径用完时,根据加权weight值随机地丢掉一些路径,并用Cx集中的路径来补充。根据本算法,不仅有效预防网络拥塞,而且增强了网络中的数据安全性。
作者:姚仲欢; 王高才; 孙野; 邱军林 期刊:《微电子学与计算机》 2007年第09期
借助图论中最短路径和最小生成树的原理,在无线传感器网络中构建若干棵以Sink节点为根的最短路径源路由树。与最小生成树相比,最短路径树能保证路径上大部分节点找到节点间RSSI较强的通讯路径并以较少的跳数把数据传输给Sink节点,而最小生成树中的节点则需较多跳数。因此,提出的算法在一定程度上降低了延时。算法通过事先设定最低RSSI和节点最大剩余能量MRE来构建路由树,并修改已存在的路由算法,从而保证节点通讯的可靠性和...
作者:汪维清; 汪维华; 张明义 期刊:《计算机工程与设计》 2007年第22期
低代价最短路径树是一种广泛使用的多播树,它能够在保证传送时延最小的同时尽量降低带宽消耗。快速低代价最短路径树算法FLSPT是在DDSP算法的基础上,通过改进节点的搜索过程,该算法构造的最短路径树与DDSP算法构造的树具有相同的性能,但其时间复杂度低于DDSP,其时间复杂度为O(nlog n+e)。FLSPT是利用Fibonacci堆来选择图中未计算点的最小值来计算时间复杂度的。通过对FLSPT的程序和Fibonacci堆的分析发现,用O(log(n!)+e)来...
作者:温菊屏; 胡小生; 林冬梅; 曾亚光 期刊:《计算机应用》 2016年第07期
针对k步可达性查询算法无法解决带距离约束的图可达性查询问题,提出基于参考节点嵌入的图可达性查询算法。首先,从所有节点中选出极少数有代表性的全局参考节点,预先计算所有节点与全局参考节点之间的最短路径距离;然后,采用最短路径树和范围最小值查询技术求得局部参考节点;接着,利用三角不等式关系得到查询点对距离范围;最后,根据查询条件中的距离值与查询点对距离范围上、下限值的大小关系,可快速得出可达性结论。针对社会关系...
PIM—SM(独立于协议的组播稀疏模式)具有自身的特性和优点被认为是大多数通用组播网络组播路由协议的最好选择。它更适合应用于广域网链接末端有潜在成员的组播网络中,在更多实际应用中它常常与PIM—DM、IGMP一起使用。
作者:米晓琴 卜永波 朱锋 期刊:《内蒙古农业大学学报·自然科学版》 2008年第01期
组播是1种高效的网络通信方式,可以有效的避免资源的浪费。本文全面介绍了组播技术的工作原理和实现机制;重点分析了各种组播路由协议,探讨了它们之间的联系及其优缺点。
作者:李娜 王小铭 期刊:《计算机工程与科学》 2009年第02期
距离向量路由算法和链路状态路由算法是网络中普遍应用的两种路由算法。距离向量算法交换的路由信息较少,但存在“计数到无穷”的问题,不能保证无路由环;链路状态算法需交换的路由信息多,路由开销较大。针对上述算法的缺陷,基于最短路径树交换的路由原理,本文提出轻权邻接状态路由算法,它只需交换必要的路由信息,既避免了路由环问题,又减少了所需交换的路由信息,降低了通信开销,提高了效率。
作者:尚文轩 李峭 熊华钢 期刊:《计算机工程与应用》 2011年第25期
动态SPT算法是在图的拓扑改变时,以原有SPT为基础作局部更新;SPT动态更新需要解决寻找因为该改变而需要修正最短路径的相关节点的问题。对于传统的SPT定义先扩展,使节点记录距离相等的一条或多条最短路径,称之为ESPT。提出了一种不需记录后继的ESPT动态更新算法并加以证明,通过证明还说明在ESPT定义下该算法找到的所有节点都是动态更新所必要且充分的。给出算例,列出操作过程,对不同复杂度的图进行计算实验,将其结果与经典静态算法...
作者:王仁喜 樊建席 王成 李硕 期刊:《计算机工程》 2011年第23期
针对无线传感器网络的冗余覆盖问题,在K-覆盖判定算法和部分冗余覆盖算法基础上,提出一种可调冗余覆盖算法。该算法遵循覆盖最大化原则,能降低网络能耗。在可调冗余覆盖算法处理后的高效网络中,给出结合最短路径和最小生成树的最短路径树算法,在网络中构建若干棵以Sink节点为根的最短路径树,进一步降低网络能耗。仿真结果表明,在随机部署网络中,当规定网络覆盖冗余度为2时,2种算法平均可降低能耗20.27%左右。
作者:肖乾才 李明奇 郭文强 期刊:《计算机科学》 2012年第04期
动态网络最短路径是交通、通信等系统中的重要问题。在处理多链路权值变大时,多链路权值增大的动态最短路径算法可有效地减少单链路权值增大动态最短路径算法的冗余计算。目前,多链路权值增大的动态最短路径算法的研究较少,尚未存在有效的多链路变大的动态最短路径算法。通过对现有动态最短路径算法的深入研究,提出了一种多链路权值增大的动态最短路径算法(DSPT-MLI)。算法复杂度分析和仿真结果显示,DSPT-MLI算法具有更少的节点...