基于QoS约束的组播路由算法研究

作     者：甄成方 

作者单位：中北大学 

学位级别：硕士

导师姓名：杨秋翔

授予年度：2008年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 08[工学] 081201[工学-计算机系统结构] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

主      题：QOS路由 多约束组播路由 多约束最小Steiner树 多路径约束问题 

摘      要：近来Internet上有越来越多的QoS要求的组播应用的涌现,如视频会议、网络音频/视频广播、远程教育、软件更新等,这加速了网络对可扩展的有效的组播通信方式支持的需要。与单播通信方式比较起来,组播在点到多点的数据传输方面更有效,在传统的单播通信方式中,源需要向每个接收者单独传送一份数据的拷贝,一个数据流就有可能占用了不必要的很大一部分的带宽,如果接收者成千上万,网络拥塞发生的可能性就大大增高。而在组播通信方式中,主干链路上只有一个数据的拷贝,路由器只在分枝处进行数据包的复制,所以大大节省了带宽。 实现组播重要的一环是组播路径的确立,与单播传输路径不同的是组播数据传输的拓扑是一棵组播树,而构建组播树是组播路由的任务,考虑到现在越来越多的多媒体应用要求有QoS保证,所以如何构建一棵组播树使其满足相应用户的QoS要求成为组播研究领域的一个很大的挑战。许多研究者正致力于QoS组播路由算法和协议的研究和设计,QoS组播路由已经成为近年来的一个热点研究领域。 在QoS组播路由中,寻找多约束可行路径问题已经被证明是NP完全问题。CMST问题使服务路径领域受到越来越多的关注,但是针对多重附加约束的多点路由却没有得到太多的进展,尽管大量正在形成的应运软件对此提出了需求。在这篇论文中,我们提出了一种构建组播树的启发式算法,HMCMC来解决这个问题。HMCMC有着低时间复杂度,它的基本思路就是逐步建立一种多点路由,这需要建立在关于多约束组播路由最新研究的基础上。仿真结果表明,与以往算法相比,该算法在消息开销、连接成功率和连接建立时间等性能指标方面都有较好的改善。