Ant Colony Algorithm And Application In QoS Routing

The routing optimization is one of the research hotspots in modern communication network, because the routing optimization with multi-constraints is an NP-C problem, heuristic algorithms are generally used to solve it. As a new heuristic algorithm, ant colony algorithm(ACA) does not depend on precise mathematic description and has such characteristics as global optimization, self-organization, self-learning and so on. These characteristics match well with the traits of QoS routing, such as distributed computing, random dynamic state and so on. So using ACA to optimize routing has a broad developing future. For QoS unicast routing problem under the constraints of delay and bandwidth and dynamic QoS multicast routing with multi-constraints, routing optimization tactics based on improved ACA are proposed in this dissertation, and simulation results are good. The contributions of the dissertation are outlined as follows:(1) In the initialization process of pheromone, referring to Li's thinking-food distributing smell, the process of food distributing smell is considered, and distributing rules are given in detail. In the QoS unicast routing and QoS multicast routing, the food smell takes delay and the sum of delay and delay jitter as constraints respectively. It is different from emitting food smell to the whole net by flooding way. The food smell is spread on the link nearby food source as pheromone, in order to guide ants to find the place of food quickly. This strategy is more in accordance with true ant colony.(2) Making full use of link state information. In order to prompt ants to find global optimum, the probability shift expressions are optimized according to comprehensive information of link in the QoS unicast routing and QoS multicast routing problems.(3) In the QoS unicast routing and QoS multicast routing problems,"elimination the worse"is adopted to update global pheromone, so as to strengthen the algorithm's ability of finding global optimum.