A Load Balancing Routing Mechanism Based on Ant Colony Optimization Algorithm for Vehicular Adhoc Network
Vehicular Adhoc network has gained enormous attention in recent years because of its usage in intelligent transportation and mobile communication. VANET is special form of MANET with unique characteristics like high speed, fast topology changing and difficult communication environment. Due to these features, routing has been considered as a challenging problem in VANET. Different approaches have been proposed to improve efficiency of routing in VANET but very less has paid attention to the area of load balancing. Load balancing can influence throughput and performance of network. In this paper, we proposed a novel load balancing routing mechanism which is based on ant colony optimization algorithm. Ant colony optimization algorithm is meta heuristic algorithm that is inspired by natural behavior of ants. Also it has been widely studied in optimization problems. The proposed method was simulated in NS2 and experimental results proved that the proposed mechanism outperforms other well known approaches like AODV. Keywords Ant colony optimization algorithm, Vehicular Ad hoc Network, Load Balancing, Introduction Vehicular ad hoc networks (VANETs) are an emerging networking technology for supporting intelligent transportation systems (ITS) [1] A VANET is a special type of 2 Alireza Mohammadnia et al mobile ad hoc networks (MANETs) It has some characteristics similar to those of MANETs, such as self organization, self management and short range radio transmission. In addition to these similar characteristics, a VANET also has some unique characteristics, such as highly dynamic topology, sufficient energy capacity and predictable mobility model. The network architecture of VANET can be classified into three categories: pure cellular/WLAN, pure ad hoc, and hybrid [2] There are many research projects around the world which are related with VANET such as COMCAR [3] DRIVE [4] FleetNet [5] and NoW (Network on Wheels) [6] CarTALK 2000 [7] CarNet [8] There are several VANET applications such as Vehicle collision warning, Security distance warning, Driver assistance, Cooperative driving, cooperative cruise control, Dissemination of road information, Internet access, Map location, Automatic parking, and Driverless vehicles. In a VANET, communication occurs from vehicle to vehicle (V2V) or from vehicle to infrastructure (V2I) A vehicle needs to transmit its data to other vehicles or roadside units to provide a variety of applications, such as traffic control, environment monitoring, and inter vehicle communication. For this purpose, a path needs to be established between a source and its destination or roadside unit before data transmission, and routing therefore becomes a critical issue in the design of a VANET. Routing problem is one of major issues in VANETs. Routing is in conjunction with the admission, flow and congestion control components, determines the overall network performance in terms of both quality and quantity of delivered service. A variety of routing algorithms have been proposed in the literature, which can be classified into five categories: ad hoc routing position based routing cluster based routing broadcasting geocast routing[9] Routing algorithms can also be classified as minimal or non minimal. Minimal routing allows packets to follow only minimal cost paths, while non minimal routing allows more flexibility in choosing the path by utilizing other heuristics. Minimal routing can further be subdivided into optimal routing and shortest path routing. In the former, the objective is to optimize the mean flow of the entire network; while in shortest path routing the goal is to find the minimum cost path between two nodes. Another class of routing algorithms is one where the routing scheme guarantees specified QoS requirements pertaining to delay and bandwidth. These algorithms are usually message based, i.e. they find a feasible path satisfying the QoS constraints based on an exchange of messages between the nodes [10] These algorithms have the tendency to temporarily overuse network resources until they find the appropriate path. The Dijkstra and Bellman Ford algorithms are examples. Yet another form of network control, which relies heavily on routing, is that of load balancing [11, 12] Here the goal is to propose a routing algorithm which is optimized for using in real A Load Balancing Routing Mechanism Based on Ant Colony 3 3 VANET applications. Our main focus was accuracy and execution time of routing algorithm. RELATED WORK A variety of routing protocols have recently been proposed for different network scenarios, such as AODV (Ad hoc On demand Distance Vector) [13] and DSR (Dynamic Source Routing) [14] which were originally proposed for MANETs but can also be used for VANETs with lower throughput [15] Moreover, GPSR (Greedy Perimeter Stateless Routing) [16] is a well known routing protocol proposed particularly for VANETs, which can achieve a better performance than AODV and DSR in a suburban scenario. GPCR (Greedy Perimeter Coordinator Routing) [17] is another routing protocol proposed particularly for VANETs, which is based on GPSR and does not use any street map. Although these routing protocols have been proposed for VANETs, all of them have this or that limitation in achieving network performance or addressing different network scenarios. Temporally Ordered Routing Protocol [18] is based on the link reversal algorithm that creates a direct acyclic graph towards the destination where source node acts as a root of the tree. In TORA packet is broadcasted by sending node, by receiving the packet neighbor nodes rebroadcast the packet based on the DAG if it is the sending node"s downward link. Vehicle Assisted Data Delivery [19] focused on multihop data delivery through vehicular ad hoc networks which is a complicated problem. The method is based on the idea of carry forward approach by using predicable vehicle mobility. Huang et al.[20] studied movement characteristics of vehicle nodes in VANET and proposed a GPSR based routing algorithm. Also this paper considered circle changing trends angle in vehicle speed fluctuation curve and the movement domain MEDAL [21] is a routing algorithm for both vehicle to vehicle (V2V) and vehicle to infrastructure (V2I) communications in VANETs. MEDAL takes advantage of both the moving directions of vehicles and the destination location to select a neighbor vehicle as the next hop for forwarding data. R.K. Chauhan et al.[22] proposed a novel method for load balancing which is based on AODV. They used a parameter called "local delay" to measure load optimization. The authors of [23] developed a new load balancing and congestion avoidance routing mechanism for real time traffic in VANET. The routing mechanism must satisfy QOS requirements of real trafficin vehicular adhoc network. Fuzzy logic systems are used to select intermediate nodes and adapt the volatile characteristics of the vehicular networks. Metaheuristic algorithms are another approach which has been widely used in routing problem. Ant colony optimization [24] is a metaheuristic algorithm which is inspired by the behavior of a real ant colony. AntNet[25] is a novel approach to the adaptive learning of routing tables in communications networks. AntNet is a distributed, mobile agents based on Monte Carlo systems. 4 Alireza Mohammadnia et al Correia et al.[26] proposed Ant Colony Optimization (ACO) algorithm which uses information available in vehicular networks such as the vehicles" position and speed in order to design an ant based algorithm that performs well in the dynamics of such networks. The authors have also adapted the Dynamic MANET On demand (DYMO) routing protocol [27] to make use of the ACO procedures. Ant Colony Optimization algorithm Biologically inspired computing is a field of study which is related to biology, computer science and mathematics. It uses computers to model nature, and parallel study of nature to improve the usage of computers. Bio inspired computing is a major part of natural computation. It takes bottom up and decentralized approach. Bioinspired techniques involve the methods of specifying a set of simple rules, a set of simple organisms which follows those rules, and a iterative method applies to those rules [28] Bio Inspired Algorithms can be divided into two classes, namely, Evolutionary Algorithms and Swarm based Algorithms which are inspired by the natural evolution and collective behavior in animals respectively. Swarm Intelligence appears in biological swarms of certain insect species. It gives rise to complex and often intelligent behavior through complex interaction of thousands of autonomous swarm members. Interaction is based on primitive instincts with no supervision. The end result is accomplishment of very complex forms of social behavior and fulfillment of a number of optimization and other tasks. The main principle behind these interactions is called stigmergy, or communication through the environment. An example is pheromone laying on trails followed by ants in ant colony optimization algorithm. Ant colony optimization algorithm is a metaheuristic[24] algorithm which is inspired by foraging behavior of ants. Pheromone is a potent form of hormone that can be sensed by ants as they travel along trails. It attracts ants and therefore ants tend to follow trails that have high pheromone concentrations. Ants attracted by the pheromone will lay more pheromone on the same trail, causing even more ants to be attracted. Ant colony optimization algorithm has advantages like: Scalability: Population of the agents can be adapted according to the network size. Scalability is also promoted by local and distributed agent interactions Fault tolerance: Ant colony optimization processes do not rely on a centralized control mechanism. Therefore the loss of a few nodes or links does not result in catastrophic failure, but rather leads to graceful, scal