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

基于服务质量的路由选择机制是从根本上提供分布式多媒体应用所需的服务质量保证的重要手段之一。该文提出了两种基于服务质量的多媒体通信初始路由建立算法。一种算法支持在两个通信方之间建立基于服务质量的初始路由，既可以作为点对点多媒体通信的基于服务质量的路由选择／初始路由建立算法，也可以作为初始成员为两个的多媒体动态组通信的基于服务质量的初始路由建立算法，另一种算法支持在多个通信方之间建立基于服务质量的初始路由，既可以作为多媒体静态组通信的基于服务质量的路由选择／初始路由建立算法，也可以作为初始成员为多个的多媒体动态组通信的基于服务质量的初始路由建立算法，文中还探讨了这两种算法的正确性。

Quality of Service Based Initial Route Setup Algorithms for Multimedia Communication

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 introduced into the second proposed algorithm. The defined heuristic cost is proportional to the available CPU capability and buffer capacity of the nodes and the available bandwidth of the edges along the route inversely, thus, the second proposed algorithm tends to setup route along the light loaded nodes and edges, helping application QoS requirements satisfied and network load balanced.The correctness of the proposed algorithms is also discussed. Simulation results show that they are effective and efficient.