Research On Wired Network Routing QoS Based On Improved Ant Colony Algorithm

With the development of computer network and application, the traditional Best-Effort Service model could not satisfy the requirements of many multimedia users. Quality of Service(QoS) of computer networks has been the focus of recent network research. Quality of Service routing problem is to search the path, which meets various constraints. Researchers have proved that multi-constrained optimal routing problem is a NPC problem, which cannot be solved within polynomial time by traditional methods.As a heuristic method, ant colony optimization could effectively solve the NPC problem.Ant colony optimization has some advantages, such as parallelism, robustness, ease of combining with other algorithms, but also has shortcomings like slow convergence and easy to stagnation. In Chapter 2 principles of network QoS are reviewed in detail, and in Chapter 3principle of ant colony optimization is discussed briefly. In Chapter 4 a modification of ant colony optimization based on freshness degree is introduced and evaluated. Ant colony is divided into two different functioning groups according to search conditions. The ants in one group choose edge in accordance with the freshness of edge, in order to weaken strong positive feedback, and reduce chance of falling into standstill; the ants in another group choose edge according to pheromone, to strengthen exchange of ant colony searching experiences.When the pheromone updates, strengthen path for better solutions, so the algorithm evolves towards optimal direction.Improved ant colony optimization based on independent behavior will be introduced in Chapter 5. Each ant will save the best solution and the worst solution that they have searched.When beginning to transfer state, the new algorithm will determine the ant strategy of searching in current cycle by comparing the best solution and the worst solution with results in the previous cycle. When result of the previous cycle is better than the optimal solution, ant's searching area will be concentrated in the vicinity of the optimal solution in current and the next several cycle, trying to get a better solution. When result of the previous cycle search is worse than the worst solution,ants will avoid the edge that composes worst solution in the current search cycle,to improve the quality of the solution.When result of the previous cycle is between the best solution and the worst solution, ants select edge in accordance with the traditional ACO way of probability. According to the MMAS, pheromone on the edge is within a certain range of the upper and lower limits. Upper and lower limits will dynamically change in accordance with the searching condition, to prevent the algorithm from a premature standstill.Both of the improved ant colony optimization are applied to a wired network QoS routing problem. Simulation experiments are done with data from a Salama network topology. When solving QoS routing problem, various results have proved that better searching performances are achieved, often superior to the basic ant colony optimization and max- min ant system.