基于服务质量的多媒体通信初始路由建立算法的研究  

Quality of Service Based Initial Route Setup Algorithms for Multimedia Communication

作　　者：王兴伟[1] 王志军[2] 黄敏[2] 刘积仁[3] 

机构地区：[1]东北大学计算中心,沈阳110004 [2]东北大学信息科学与工程学院,沈阳110004 [3]东北大学软件中心,沈阳110004

出　　处：《计算机学报》2001年第8期830-837,共8页Chinese Journal of Computers

基　　金：国家自然科学基金 (6 0 0 0 30 0 6 );教育部现代远程教育关键技术研究重点项目资助

摘　　要：基于服务质量的路由选择机制是从根本上提供分布式多媒体应用所需的服务质量保证的重要手段之一 .该文提出了两种基于服务质量的多媒体通信初始路由建立算法 .一种算法支持在两个通信方之间建立基于服务质量的初始路由 ,既可以作为点对点多媒体通信的基于服务质量的路由选择 /初始路由建立算法 ,也可以作为初始成员为两个的多媒体动态组通信的基于服务质量的初始路由建立算法 .另一种算法支持在多个通信方之间建立基于服务质量的初始路由 ,既可以作为多媒体静态组通信的基于服务质量的路由选择 /初始路由建立算法 ,也可以作为初始成员为多个的多媒体动态组通信的基于服务质量的初始路由建立算法 .文中还探讨了这两种算法的正确性 .QoS(Quality of Service) based network routing mechanisms are fundamental means to support QoS guarantees required by distributed multimedia applications. The QoS based routing algorithms are key components in QoS routing mechanisms. In this paper, two routing algorithms are presented, which are suitable to QoS based initial route setup for multimedia communication. The first algorithm supports the QoS based initial route setup between two participants. It can not only act as the QoS based routing (or the QoS based initial route setup algorithm if on line rerouting permitted) for point to point multimedia communication, but also act as the QoS based initial route setup algorithm for multimedia dynamic group communication in which the number of initial group members is two. It is based on Dijkstra's algorithm and belongs to hop by hop routing algorithm. It finds the minimum usage cost path from source node to destination one with certain constrains satisfied, at the same time, leads to the optimal resource (such as CPU, buffer, bandwidth) utility and guaranteeing end to end delay and end to end error rate requirements to maximum degree. The second proposed algorithm supports the QoS based initial route setup between multiple participants. It can not only act as the QoS based routing (or the QoS based initial route setup algorithm if on line rerouting permitted) for multimedia static group communication, but also act as the QoS based initial route setup algorithm for multimedia dynamic group communication in which the number of initial group members is greater than two. What to be solved is a kind of constrained Steiner tree problem, which is NP complete. By introducing a kind of heuristic cost, it is transformed into a kind of Steiner tree problem. Due to the NP completeness, GA(Genetic Algorithm) is applied to find the minimum heuristic cost Steiner tree. In addition, in order to speedup the convergence to the optimal solution, the domain knowledge based active mutation concept is presented and introduc

关 键 词：分布式多媒体 多媒体通信 服务质量 初始路由建立算法 

分 类 号：TN919.8[电子电信—通信与信息系统]