Research On QoS Multicast Routing Algorithm Based On Genetic Algorithm

With the development of Internet and broad band technology, traditional services for word and picture can not satisfy the need of users, media services with video and audio become main stream. In recent years, embedded network digital video monitor system is widely used. Because of large data and limit system resource, unicast will enhance the burden of server and lead to congestion. But multicast can transmit the same data from embedded network video server to the receivers parallelly so that it can save broad band and reduce data redundancy. At the same time, video monitor system has the strict request for delay and delay-jitter. The transmitted data must reach all receivers in limited time, and the delay difference between receivers also needs to be in a limited range, that is to say, satisfy the demand of QoS. Therefore we need to solve QoS multicast routing question in embedded network digital video monitor system. The goal of the question is to find a multicast tree satisfying the demand of QoS that overlay all group numbers and make the cost minimum.Genetic algorithm is a new global optimal algorithm simulating evolution and widely used to solve all kinds of NP-hard problems. In recent years some scholars have used genetic algorithm to solve QoS multicast routing question. This thesis analyses exist genetic algorithms and provides two kinds of improved genetic algorithm. The first improved algorithm analyses that the standard genetic algorithm is easy to get into prematurity, and at the end of the algorithm, it runs slowly. In order to overcome the phenomenon, we adopt initial population uniform building method and self-adaptive mutation to restrain prematurity and introduce ordering to scale fitness to improve convergence speed. Simulation shows that the improved algorithm is efficient and effective, and can find the best solution quickly. It can satisfy limited resource and real-time the system requests. The second improved algorithm mixes this two algorithms based on the strength and shortcoming of genetic algorithm and ant-colony algorithm to solve QoS multicast routing question. The first phase of the mixed algorithm makes use of the quickness, random and global convergence of genetic algorithm to produce the initial pheromone that is needed by the second phase of the mixed algorithm. The mixed algorithm is better than ant-colony algorithm in time efficiency and better than genetic algorithm in solution efficiency.Because of unicast problem in the existing video monitor system, this paper applies multicast technology to network video monitor system. By this way, we can save network resource effectively, reduce delay and decrease the probability of network congests to ensure real-time and quality of service of digital video transmission.