一种最小代价组播树的快速算法

本文对KMB算法进行了改进,提出了一种快速的最小代价组播树算法,它只需使用一次PR IM算法,也不需要判断叶结点,从而快速地获得了最小代价组播树,减少了算法的运行时间。随机网络模型的仿真实验表明:该算法的计算时间远小于KMB算法,是一种快速、稳定、高效的算法。

基于网络编码的双路径组播树生成算法

为了将网络编码技术引入到全光组播网络中,提出了能够在多项式时间完成的基于网络编码的双路径组播树生成算法.该算法主要包括两大步骤:首先,从给定的组播网络中根据节点间度平衡的原则为源节点和每个目的节点之间确定一条有向路径,从而建立一棵传统有向树并保证有向树中任意节点的出度尽可能小,减少节点之间的关联性;其次,在所建立的传统有向树的基础上,从每一个目的节点到源节点根据冲突回溯原则建立源节点和每个目的节点之间的第二条路径,并保证源节点到任意目的节点间的两条路径为分离路径.算法中包含的约束原则能够保证所建立的双路径组播树包含最少的编码节点,从而使得所建立的组播树支持光域网络编码高效率实现,实现基于网络编码的全光组播并提升全光组播的性能.

一种利用双路径组播树提高应用层组播稳定性的方案

应用层组播作为IP组播的替代方案,具有简单灵活、容易部署的优点,在分布式多媒体通信领域获得了广泛的应用.但其存在组播树稳定性的问题,发展受到了限制.该文提出一种双路径组播树方案,采用两个组播树传输和转发不同内容的数据,在节点加入或者退出组播组时,不需要重新构建组播树,其它节点仍然可以接收到可接受的多媒体数据,从而减少故障恢复的时间,提高应用层组播的稳定性,改善应用层组播的性能.最后通过计算机仿真,表明该方案在节点加入和退出时减少了故障恢复时间,维护了组播树的稳定性,具有良好的性能改善和显著的优点,适合多媒体业务传输.

随机搜索组播树生成算法

本文在MPH的基础上 ,改变了端节点的加入过程 ,得到了一种新的MST算法 :RSH。在随机网络模型的基础上 ,我们进一步进行了仿真。仿真结果表明 ,RSH以相对较小的费用增加换取更快的计算速度 ,和其他组播树生成算法相比 ,RSH是一种计算速度很快的算法。

一种时延约束的多共享组播树构造算法

该文提出了一种时延约束的多共享组播树构造算法,以解决多点到多点组播路由情况下单棵共享树无法满足时延约束的问题。该算法构造覆盖所有源节点和目的节点子集的多棵共享树以满足时延约束的要求,并通过减少共享树个数降低管理开销。该算法计算以每个节点为中心的共享树所能达到的目的节点的子集,将原问题转换为集合覆盖问题,并采用基于矩阵的启发式算法进行求解。仿真实验将该算法和同类算法进行比较,结果表明该算法在不增加管理开销和中心数的情况下,有效地减少了运行时间。

基于投影矢量的双组播树高效路由数据收集

现有的节点数据收集算法复杂度高,与路由结合效果不理想,且不能满足无线传感器网络高效能量的节点数据收集,而压缩感知理论具有容错性好、编码简单的优点。基于压缩感知的特性,提出了一种传感器网络中基于投影矢量的双组播树高效路由数据收集,该算法将贝叶斯压缩感知理论与传感器路由相结合,解决现有算法不能满足传感器对能耗敏感的问题。算法的基本思想首先根据初始观测矢量来寻求能量高效并得到合适路由的最优投影。然后利用节点系数能耗最小与广义矢量的主分量作为目标节点,采用微分熵改变量最大的原则进行求解节点最佳投影系数,最后在Sink与目标节点路由问题上采用正逆向组播树进行路由构造。理论和仿真结果表明在保证能耗的条件下取得了较好的重建仿真效果,对无线传感器通信具有一定的实用价值。

P2P流媒体直播系统的组播树构建及设计

研究了P2P流媒体直播系统的特性和体系结构.对组播树的构建与设计进行了详细的说明,提出一种单播树、多播树结合的组播树构建方案,该方案结合了单组播树维护方便、多组播数节点负载均衡的优点.对节点组织策略进行了分析,对新加入节点利用及时服务策略进行了研究,提出一种及时优化策略.在新节点加入的时候就探测其服务能力,调整组播树结构,及时发挥新加入节点的优势,提升系统服务能力.

一种基于QOS约束的组播树构建算法

研究基于QoS约束的组播树构建问题.采用种群数自适应遗传算法构建组播树,该算法可以对进化种群数进行宏观调控;同时,使用个体寿命限制个体的生存期,实现对种群数的微观调控.仿真结果证明了该算法的有效性.

一种考虑延迟和丢包率的最小代价应用层组播树

针对度约束方式难以减少应用层组播树的延迟和丢包率的问题,提出了一种延迟和丢包率综合代价最小的应用层组播树构树算法.为避免度约束的局限性,给出一个包含延迟和丢包率的复合代价函数,以此来计算传输代价,进而构建了一种最小复合代价组播树的问题模型.为了求解该问题模型,提出了一种基于最大延迟路径贪婪算法的变异算法,同时在构树时对总传输代价进行优化.通过实验,给出复合代价函数的具体参数建议.对比相关算法,文中的构树算法在总传输代价方面有更好的性能.

在多协议标签交换组播中应用合并组播树

引入一种新的MPLS(多协议标签交换)组播实现方案———MPLS合并组播树,讨论了采用MPLS合并组播树在减少组播控制费用、故障恢复延迟、标签数等方面给MPLS组播带来的高效性,量化分析表明,采用MPLS合并组播树可以有效解决MPLS组播存在的标签数不足问题。

基于组播树的改进一致性数据融合算法

提出了一种结合路由的基于组播树的数据融合算法.该算法由3个阶段构成:组播树的构造阶段、兴趣散布阶段和数据融合阶段.算法构造了一棵以汇节点为根的组播树,在汇节点进行兴趣散布阶段,通过一种基于被动分簇的优化定向扩散路由协议进行路由扩散;数据融合阶段,借鉴多传感器中的一致性融合算法,通过重新定义其置信距离避免人为定义阈值而产生的主观误差.数值算例证明此方法可获得较好的融合结果,同时能耗低,实时性好.

应用层组播树性能的测量研究

针对应用层组播中构建组播树的三种不同算法对组播树性能影响进行了研究,包括各节点的吞吐量和组播树的稳定性,在PlanetLab分布式实验床上进行了实际的测量和分析。结果表明最大带宽组播树算法构建的组播树有最好的吞吐量和稳定性;最短路径树算法也有很高的稳定性,其吞吐量比随机组播树算法有所提高,但差于最大带宽组播树算法。

广域网中的快速组播树生成算法

在组播树生成算法中 ,MPH(m inim um path cost heuristic)的费用性能几乎是最好的 ,但它的计算时间相对较长 .提出了两种新的组播树生成算法 :TNS- MPH(tree- node started minim um- cost path heuristic)和 NTDS-MPH(non- tree- destination started m inimum- cost path heuristic) .同时提出了一种使节点平均度非常精确的随机网络产生模型 .新算法的仿真结果表明 ,新算法能用较少的费用性能恶化来换取更快的计算速度 .新算法比SCTF(selective closest terminal first)

QoS约束下新成员加入组播树方式的研究

QoS组播路由是一种解决有QoS要求的组播应用的有效方式,其中QoS约束下新成员加入组播树的方式和性能是一重要研究内容。主要介绍了QoS约束下新成员加入组播树的几种方式,并比较和分析了其各自的优缺点,在此基础上提出了对其进行改进的几点建议,指出了其未来的发展方向。

传感器网络中基于反向组播树的数据融合路由算法

传感节点有限的能量使得能耗成为路由算法设计要考虑的首要因素。数据融合可以通过合并冗余数据而有效地节约能耗,本文据此提出了一种基于反向组播树的路由算法,算法通过构造一个组播树形成一个以Sink为根的树,其后节点只需将数据发送到一个树上的节点即可,数据经过融合反向转发到Sink。算法具有较好的节能性,而且延时较小,理论分析和仿真实验也表明算法具有好的性能。

面向多描述编码的应用层组播树系统的设计与实现

多描述编码[1-2](MDC)在提高P2P流媒体系统的服务质量方面起着重要作用,作为其传输平台的应用层组播树系统[3]的构建及其在高动态网络中的性能研究是目前互联网研究领域中的重要问题.本文针对多描述编码的特点,设计实现了采用确定性组播树管理算法的多组播树系统,并基于PlanetLab[4]分布式实验床分析了系统在P2P流媒体系统中应用的性能.实验结果表明,在节点非正常退出时,采用确定性算法构建的多组播树比单组播树和采用随机性算法构建的多组播树具有更好的数据传输连续性,而系统的恢复能力和数据传输连续性随着系统中组播树数量的增加而增强.

基于受限时延和时延抖动的最小代价组播树算法研究

随着高速分组交换网络和因特网的高速发展 ,越来越多的应用 (如视听电视会议、远程教学、资源发现、计算机协同工作等 )需要多媒体信息的传输和多点连接 ,这就需要研究如何构造有效组播通信树的问题。本文首先给出基于受限时延和时延抖动的最小代价组播树问题的网络模型及其数学描述 ,并确定寻求这样的受限树是NPC问题。然后提出一个启发式算法来求解该问题 ,并分析了算法的复杂度。最后 ,显示了目的地动态变化时 。

延迟变化紧密的多核心组播树快速构建算法

为了解决在具有延迟及延迟变化约束组播树的构建问题中存在的算法实用性差、复杂度高和重构代价大等问题,提出基于扁平多核心树结构的、采用基于延迟变化过滤窗口的多核心节点选取机制的组播树快速构建算法.该算法极大地拓展了初始组播树的寻解空间,且能够找到具有最严格的延迟变化约束的目标树.该算法实用性强,目标树的可维护性好且局部恢复代价小.理论上,该算法在时间复杂度上与该项性能最好的延迟及延迟变化约束算法(DDVCA)相同.模拟实验中,在相同的延迟及延迟变化约束条件下构建大规模组播树,该算法相比延迟及延迟变化约束算法最多能够节省60%的执行时间.模拟实验还表明,随着延迟变化约束越来越小,与延迟变化约束性能最好的链式算法相比,该算法能够以更大的概率找到合适的组播树;该算法能够获得最紧密的延迟变化约束性能.

一种新的基于Dijkstra算法的QoS组播树启发式算法

基于Dijkstra算法和MCP_IA算法,提出了一种耗费受限的最短时延路径算法(CCLDA),并将其应用于时延和时延差异受限的算法(DDVCA),并给出了算法实现的伪代码,不仅满足了时延和时延差异限制,而且降低了最终所得的组播树的耗费,更能满足现实需要。

一种新的基于Dijstra算法的QoS组播树启发式算法

基于Dijstra算法和MCP_IA算法1,该文提出了一种耗费受限的的最短时延路径CCLDA算法,并将其应用于时延和时延差异受限DDVCA算法,不仅满足了时延和时延差异限制,而且降低了最终所得组播树的耗费。