Design and Development of ACO Routing Protocol for MANETs

Abstract

Due to their wide applicability in wide range of application, Mobile Ad-hoc Networks (MANETs) in recent years have gained a lot of attention MANETs can operate without any existing fixed infrastructure and have rapid changes in the network topology. Preparing and maintaining the routing table in communication networks, especially in MANETs, is a challenging task. Nodes dynamics in MANETs make the management of routing tables a complex job to be carried out. There exist many solutions for the routing problem in MANETs; each one having its advantages and limitations. These existing solutions need to be improved to achieve better performance with respect to various parameters. In fact, there is a new generation of bio-inspired routing protocols that have the potential to provide better performance than traditional protocols with the help of moving agents. Agents collaborate with each other to update the routing table quickly with less delay. Ant Colony Optimization (ACO) is one of the most interesting bio inspired metaheuristics technique. It simulates ant behavior to solve complex combinatorial problems. ACO algorithms include the method of optimization and reinforcement learning. ACO algorithms are decentralized, robust and resilient. These features make ants a good choice for taking routing decisions; where not only shorter paths need to be found, but also there is a need to achieve higher performance and greater reliability over the traditional protocols. It has been observed that ant algorithms influence the performance of the network due to their self organization characteristics. The main contribution of this thesis is to design and develop new ant colony algorithms. The thesis contribution includes the blueprint and formulation of new ant-based algorithms for routing in MANETs. The presented framework has implemented using the novel ant routing algorithms in a simulated network. The experimental results show that ACO algorithms are well suited to the environment of MANETs. The proposed and implemented algorithms weave ACO properties. ACO algorithms were based on agent systems and worked with a group of ants that allow a high adaptation to the dynamic topology of MANETs. In contrast to other approaches for the formation of routing information, ACO algorithms resulted in passing of local information at a fast pace by transmitting collected information to neighbors in the network. Each node maintains a routing table with entries for all of its neighbors which are called as the pheromone table. The decision rule, to select the next node, was built on the concentration of the pheromone in pheromone table. Further to realize ACO, a modified data structure was proposed that includes the new packet format for different types of ant, memory structure, traffic format and pheromone table. The work represented in thesis compared the developed protocol with traditional and other available ant based routing algorithms of MANETs. The performance of the proposed algorithms was found better than other state of the art algorithms. Both the algorithms (ANTALG, OANTALG) are tested using simulation in NS-2.33 by creating random waypoint model. Various performance evaluation metrics such as throughput, packet loss, delivery ration, end to end delay, number of packets sent, and jitter were selected for valuation purpose. The performance of both the algorithms is compared with other state of art algorithms such as AntNet, AODV, DSR, ZRP and HOPNET. The result obtained with respect to above metrics prove the superior performance of the proposed algorithms. Specially, average throughput has been minimally increased by 2% to 37%; average jitter has been reduced by minimally 25%. Lesser number of packets were dropped which lead to better delivery ratio. At least 1.5% more number of packets was sent during communication and path length has also been reduced between 2.15% to 62% approximately. Keywords: MANET, ACO, ANTALG, OANTALG, Routing Table, Ant Routing