基于稳定概率的最小延时应用层组播树构建及恢复算法研究

摘要

随着互联网普及率的上升和用户规模的激增，网络正在不知不觉中悄然渗入人们的日常生活和工作当中，在诸多方面改变和改善着人们的生活和工作模式。传统的单播通讯模式需要在服务器和客户端之间建立单独的数据传输通道，该模式无法满足当下多媒体数据对传输效率的要求。IP组播的出现解决了单播通讯模式数据传输效率低下的问题，但由于IP组播改变了Internet基于单播的设计原则，需要改变现有的网络设施，致使其在全球范围内的部署进展缓慢。应用层组播不需要特殊设备的支持，具有较高的灵活性，因此，应用层组播具有广泛的发展前景。应用层组播由具有高度动态行为的端主机负责组播数据的复制、转发，由于其构成元素异于IP组播，导致了应用层组播的性能和效率都不及IP组播，且应用层组播存在诸多其他方面的问题。如何构建高稳定性低延迟的应用层组播一直是多媒体传输领域的研究热点。
　　本文主要从高稳定性低延时的应用层组播生成树构造算法和高效的应用层组播树恢复算法两个方面对应用层组播进行研究。由于应用层组播在数据的传输效率以及稳定性方面不及IP组播，因此，构建高稳定性低延时的应用层组播系统是推广应用层组播技术的关键。针对该问题，本文提出了基于稳定概率的度约束最小延时应用层组播生成树问题模型:SDMD问题模型，该模型利用节点的相对离开概率定义了节点的稳定概率的概念，并证明了SDMD问题是NP-hard问题。为了求解SDMD问题，本文提出了基于时间增益因子的近似算法，仿真实验表明，该算法能够有效减少平均接收延时、降低累积中断次数。构建高效的组播树恢复算法是提高组播效率的重要措施之一。针对该问题，本文提出了一种混合的基于分区策略的应用层组播恢复算法(HPLR)，在该算法中，将节点的服务能力定义为其子孙节点的数目与其根路径长度的比值，再根据节点的服务能力将组播树划分成中心区域和边缘区域，针对这两个区域分别提出了相应的组播恢复算法，以在系统的计算开销和时间开销方面达到平衡。最后，仿真实验表明，HPLR算法能够有效降低组播恢复时延。

目录

声明

摘要

第一章 绪论

1．1 研究背景及意义

1．2 应用层组播研究现状

1．3 本文研究工作介绍

1．4 论文组织结构

第二章 应用层组播技术

2．1 三种通讯模式介绍

2．1．1 单播

2．1．2 广播

2．1．3 组播

2．2 IP组播和应用层组播

2．3 应用层组播树生成问题

2．4 应用层组播的稳定性问题

2．4．1 问题描述

2．4．2 相关研究

2．5 本章小结

第三章 基于稳定概率的度约束最小延时应用层组播生成树问题

3．1 节点的稳定性的定义

3．1．1 节点的离开概率的评估

3．1．2 节点的稳定概率

3．2 SDMD问题模型

3．2．1 SDMD问题描述

3．2．2 问题难度分析

3．3 基于SDMD问题模型的求解算法

3．3．1 时间增益因子的定义

3．3．2 TG-S算法

3．3．3 算法复杂度分析

3．4 仿真实验

3．4．1 仿真实验环境

3．4．2 实验参数设置

3．4．3 仿真结果分析

3．5 本章小结

第四章 一种混合的基于分区策略的应用层组播恢复算法

4．1 典型的应用层组播恢复算法

4．1．1 PRM算法

4．1．2 Kusumoto算法

4．2 分区方式

4．3 基于分区的应用层组播恢复算法

4．3．1 中心区域的节点恢复策略

4．3．2 边缘区域的节点恢复策略

4．4 仿真实验

4．4．1 仿真实验环境

4．4．2 实验参数设置

4．4．3 仿真结果分析

4．5 本章小结

第五章 总结与展望

5．1 本文工作总结

5．2 未来工作展望

参考文献

在校期间发表的论文、科研成果等

致谢