The Research On Ant Colony Based Routing Algorithms For Ad Hoc Networks

Mobile ad hoc networks (MANET) are one of the categories of wireless networks which composed by self-organized nodes that have high mobility and can move arbitrarily. If two nodes in mobile ad hoc networks need communicate with each other, there is constantly no direct link between them and data packets must be forwarded by other intermediate nodes, so MANET are also named"multi-hop network". Mobile ad hoc networks are flexible and can be deployed in most even critical environments, and there is no high performance requirement for endpoints to join the network. MANET does not need any support of fixed infrastructure. So it is very robust and effective. But, MANET's characters also challenge routing algorithms for MANET. Nodes mobility causes the network's topology dynamically changing, endpoints are of finite energy power, and the bandwidth of wireless transmission is also narrow. Routing in mobile ad hoc networks is a real challenge.Ant colony algorithm is a kind of swarm intelligence heuristic approach that inspired from social insects in nature. Swarm intelligence refers that one agent can only do some easy jobs, and very complicate tasks must accomplished by the cooperation of each agent in a whole colony. A typical example of swarm intelligence is ants finding foods.Ant colony algorithms have widely applied to solve many combinatory problems. Ant colony algorithms support distributed computing and multi-path, the agents are also easy to implement. So ant colony algorithms just meet the need of mobile ad hoc network routing. Now there are many kinds of ant based routing algorithms for MANET. However, during using ant colony algorithm, people found that positive pheromone feedback mechanism can lead stagnation, that is, in several effective paths, only one path has absolute dominant pheromone trail thickness and most data packets are forwarded by this path, which substantially reduces the network's performance. Even there is another more effective path, data packets will less probably choose it. So, stagnation will cause the algorithm plunge into less optimal solutions. There are some approaches to rigidly restrain pheromone trail thickness in every path from getting an excessive high or low value. But this kind of restriction may cause algorithm converge slowly, which also will get a lower performance in dynamic topology networks.This paper gives a detail research on convergence of ant colony algorithms, included in the cost-symmetric and cost-asymmetric network environments. We prove two theorems which depict the cause of stagnation. We investigate and compare several pheromone restriction approaches'effect on ant colony algorithm, based on this, we improve ant colony algorithm. Because ants utilize a probability approach to choose paths, we propose information entropy to improve ant colony algorithms. Information entropy is the best measure for uncertainty, and can adaptively control choosing probability differences of different paths. So using information entropy we can avoid stagnation with high network resource assignment. What's more, we can use information entropy value of the system to control pheromone update value, which can lead a quick convergence.After lots of analysis and simulation, this paper depicts the entropy based ant colony algorithm, EACRA. This algorithm can assign network resources effectively and reasonably, and ensure multi-path effective coexist with highest utilization ratio of the best optimal path. EACRA is more adaptive than some other ant colony algorithms, and can avoid stagnation effectively. We have simulations on MatLab and ns-2, all the results show excellent performance of EACRA.