The Research Of QoS Multicast Routing Problem Based On The Advanced Ant Colony Algorithm

Ant colony optimization(ACO) was introduced by M.Dorigo and colleagues as a novel nature-inspired meta-heuristic based on the phenomenon of real ants can find the shortest routing path from their nest to food source behavior in the early 1990s.It initial be used to solve TSP(Traveling Salesman Problem),boasts a number of attractive features,including adaptation,robustness and distributed,decentralized nature,Many scholars are attracted to study ACO and in the past ten years than more the algorithm has been widely applied to the fields of combinatorial optimization, function optimization,system identification,network routing,path planning of robot, data mining and premises distribution of large scale integrated circuit etc,and good effects of application are gained.Multicast routing problem is one of a series of questions with the rapid development of the Internet.With the wide applications of the group communication in many fields,such as network video conference,video on demand,stock information distribution and remote education,multicast technology has become an important foundation for supporting these applications.As these real-time operations are sensitive to delay,bandwidth and cost in the network transmission,it is liable for the real-time operations to be affected by the operation portfolios of multimedia business.So it demands QoS to assure real-time communications.Traditional "best effect" service can not meet the need of net users.Multicast QoS routing is how to select multicast routes trees with sufficient resources to meet the requirement of QoS parameters.It is proved to be a NP complete problem.Although many solutions have been proposed to solve QoS problem,there still exists many disadvantages.For example,the algorithms are too difficult to realize and can not fit the specialty of multicasting applications.That requires by using heuristic algorithms.In this thesis,first we summarized multicast routing protocol and algorithm's classification.Analyzed QoS measure,supply mechanism,QoS multicast routing model and classifies.Enumerated research development,thought origin and advantages and disadvantages of ACO algorithm.And then integrated the features of simulated annealing(SA) algorithm that accepted the poor solution by certain probability when searching optimal solutions.Adapted exploitation strategy in ACO algorithm's iteration and made searching more,can avoid falling into local optimum. And generated the converse ants based on simulated annealing strategy.The converse ants according to the rules that the higher pheromone path with the smaller probability to be selected.When using the converse ants algorithm based on simulated annealing strategy to solved QoS multicast routing problem,at the initial iteration introduced converse ants to enhance searching randomness,to avoid algorithm premature convergence into stagnation.Afterward,generated simulated random network by using improved Waxman random network production method,and using the network for simulation experiment.Compared experimental results with basic ACO algorithm and converse ants algorithm,analyzed that converse ants algorithm have better effects at convergence,stability,robustness and the cost of network performance.Finally,gave some advices for the research of QoS multicast routing problem.