Study Of Ant Colony Algorithm And Application In QoS Routing

The delivery of large scale digitized audio-visual information over local or wide area networks is now becoming realistic. For traditional IP(Intnet Protocal) network, the currently deployed routing scheme is focused on constructing end-to-end connectivity which usually supports only one type of datagram service. The emerging high speed multimedia applications have different performance requirements such as bandwidth, delay, delay jitter, and loss rate etc. The notion of Quality of Service (QoS) has been proposed to describe the quality defined performance contract between the service provider and the user applications. The QoS requirement of a connection is given as a set of constraints, which can be link constraints, path constraints, or tree constraints. QoS routing is one such mechanism with two goals: selecting feasible paths or trees that meet QoS constraints and making efficient utilization of the network resources. So the QoS routing problem can be attributed to the construction of path or tree which satisfies the end-to-end QoS constraints at the same time optimizes some special cost function.Ant Colony Optimization (ACO) is a metaheuristic approach for solving hard combinatorial optimization problems. It was first proposed by Dorigo in 1991.It was first used to solve Traveling Salesman Problem.This thesis introduces the general development of ACO. Then, through using TSPLIB as the benchmark, some analyses and remarks are made to compare the performance of some typical ACO algorithms. Additionally, Two main disadvantages of ACO are also concluded, that is, stagnation and slow-convergence.It's the basic for the next research.In order to reduce the influence of those two disadvantages of ACO, this thesis firstly summarizes the already existed approaches to mitigate stagnation. Then, an adaptive ant colony system algorithm is proposed to solve the QoS routing is proposed. Through dynamically adjusting the interaction among ant colonies, the stagnation of the new algorithm is effectively mitigated. The analysis and the experimental results show that the new algorithm can achieve better performance.