Researches On Ant Colony Optimization-Based Network Routing

Ant colony algorithm is a novel bionic approach which has the characters of robustness, distributed computing and easy to implement, and it has been applied to many problems. The dissertation focuses on the network optimization applications of ant colony optimization (ACO) algorithm, especially, an in-deep and systemic research on how to solve the problem of wireless sensor network clustering, wireless sensor network mobile agent routing, multi-layer network (two-layer and three layer) routing and path protection in WDM network. The main works can be summarized as follows:1. To make efficiently use of the limited energy resource of the wireless sensor network (WSN) and prolong the lifetime is an important problem in the study of the WSN. A novel Clustering Hierarchy based on Modularity Measure (CHMM) algorithm for clustering nodes in wireless sensor network is presented. The algorithm forms a clustering structure based on real network structure of wireless sensor network first and we use a new parameter-Modularity Measure to evaluate whether the clustering fits for the real network structure. Based on the above steady cluster structure, when we select the cluster head in each cluster, the residual energy of the nodes and the energy distributing in the cluster are both considered. And then, we use ACO to form a path from cluster heads to base station. Simulation results show that compared with other algorithms, our approach is able to obtain a more reasonable and steady distribution of clustering, and can effectively prolong the sensor network lifetime.2. An ant colony optimization-based dynamic energy efficient mobile agent routing algorithm (ADEEMA) is presented in this paper to solve the problem of routing in event-driven sensor network. In this algorithm, a novel probabilistic model is constructed to make mobile agent can find an energy efficient route from processing node to target nodes. The route considers both the energy consumption on it and the node residual energy. In order to adapt to the topology changes in dynamic sensor network, a new local pheromone re-initialization rule is presented, the new optimization route can be renewed fast by this rule. The simulation shows that comparing to other algorithms, our method can obtain a route with the least overhead on it and the residual energy of the node is considered.3. An ACO-based differentiated integrated routing (ADIR) algorithm is presented to investigate the problem of dynamic differentiated two-layer (IP over WDM) integrated routing. Firstly, the algorithm simplifies the RWA problem into routing problem with layered-graph model. Then, we search routes for the routing problem. The ants used in our algorithm are transported in control plane, so we can search routes in control plane and transport traffic in data plane synchronously. And the route for a connection request can be determined real-time. The hops and congestion of routes are also considered in our algorithm so the blocking probability is reduced. Finally, we use different kinds of ants with the motivation of bandwidth differentiation so as to the low bandwidth request traffic can use the key link and the high bandwidth request traffic selects a detour path, so the blocking probability can be also reduced. Simulation results show that ADIR performs better than other routing approaches in terms of traffic blocking probability and traffic blocking fairness.4. Three-layer dynamic network (IP over SDH over SDH) is investigated. IP/MPLS over WDM is considered as the best solution for NGN (Next Generation Network), but recently and long after now, network architecture is still IP/MPLS over SDH over WDM. In this paper, integrated optimal routing algorithm in three-layer dynamic network is proposed to reduce the blocking probability in three layer network. There are two modes in our algorithm:in Mode 1, the service blocked in upper layer can use idle resource in lower layer; in Mode 2, three layer networks are integrated into a network, and searching route for each traffic in the integrated network. In order to transmit each dynamic request in synchronous manner, an ACO-based routing approach is used in these two modes. In the approach, a novel probabilistic model is constructed, so the link usage and route hops can both be considered. The simulation shows that comparing to other algorithms, our algorithm performs better than other routing approaches in terms of traffic blocking probability.5. A new survivable algorithm called Self-organizing Shared-Path Protection (SSPP) is proposed to tolerate multi-link failures in WDM optical networks. In SSPP, ant agents are used to search primary paths, and load balancing is considered in this approach to reduce blocking probability. In the approach of search backup paths, different backup path ant agents use a same kind pheromone and these ant agents are attracted by each other, so different backup paths share more backup resources. In order to tolerate multi-link failures, self-organizing ant agents search new routes for carrying the traffic affected by the failures. Simulation results show that compared with other algorithms, SSPP has lower blocking probability, better resource utilization ratio, and higher protection ability.