时延受限的多播路由算法研究

摘要

随着计算机和网络技术的快速发展，通过网络传输的数据急剧增加，许多新的多媒体业务正成为信息传送的重要组成部分。而传统的单播通信方式满足不了新业务的需求，多播技术的出现解决了上述问题。多播是一种点到多点（多点到多点）的通信方式，它可以有效地利用网络资源，提高效率。多播技术最有效的实现方法是通过一棵多播路由树来进行信息的传递。很多实时性较强的多媒体应用对时延的要求越来越高，因此，时延受限的多播路由问题成为该领域研究的一个重要课题。
　　 本文首先介绍了多播产生的背景，多播路由算法的研究现状，对目前多播路由算法的研究成果进行了分类和分析;介绍了时延约束的多播路由模型，分析了几种经典的算法。在此基础上提出了一种改进的时延受限Steiner树启发式算法DCMPH_1，该算法通过改进节点的搜索路径，进而产生一棵满足时延受限的最小代价多播树。仿真结果表明DCMPH_1算法在性能、空间复杂度方面均优于DCMPH算法。
　　 其次，在DCMPH_1算法中，从最小时延路径集合中选择的路径虽然满足时延约束，但是代价未必是最优的，因此会影响整棵树的代价性能。针对此问题，提出了改进算法DCMPH_2。仿真结果表明DCMPH_2算法生成的多播树的代价性能优于DCMPH_1算法。
　　 此外，改进了KPP算法，设计了新的代价和时延动态优化的链路选择函数，并引入共享边的思想，提出了一种基于共享边和链路选择优化的时延约束多播路由算法ESOKPP。在选择路径时，该算法综合考虑了代价和时延两个参数，保证了多播村的性能。仿真结果表明该算法生成的多播树性能优越，同时具有相对较低的计算复杂度。
　　 最后对本文做了总结以及给出了未来的工作方向。

目录

声明

摘要

第一章 绪论

1．1 论文选题背景

1．2 多播路由算法研究现状

1．3 论文主要工作

1．4 论文组织结构

第二章 时延受限的多播路由问题

2．1 引言

2．2 时延约束的多播路由问题数学模型

2．2．1 时延约束Steiner树问题的定义

2．2．2 典型的时延约束Steiner树启发式算法

2．2．3 典型时延约束Steiner树算法的比较

2．3 多播路由算法的评价标准

2．4 本章小结

第三章 改进的时延受限Steiner树启发式算法

3．1 引言

3．2 DCMPH_1算法设计分析及描述

3．2．1 DCMPH_1算法设计分析

3．2．2 DCMPH_1算法描述

3．3 算法举例分析

3．4 DCMPH_1算法复杂度及性能分析

3．5 计算机仿真模型和结果

3．5．1 随机网络模型

3．5．2 仿真实验及其分析

3．6 DCMPH_2算法描述及分析

3．7 DCMPH_2算法复杂度与性能分析

3．8 DCMPH_2算法实验仿真及分析

3．9 本章小结

第四章 链路选择优化的时延约束多播路由算法ESOKPP

4．1 引言

4．2 算法设计分析与算法描述

4．2．1 算法设计分析

4．2．3 算法描述

4．3 算法举例分析

4．4 算法复杂度及性能分析

4．5 算法实验仿真及分析

4．6 本章小结

第五章 总结与未来的工作

5．1 工作总结

5．2 未来的工作

致谢

攻硕期间从事的科研工作及取得的研究成果

参考文献