الگوریتم کلونی مورچه مانت :مرور

Mobile ad-hoc networks (MANETs) consist of special kind of wireless mobile nodes which form a temporary network without using any infrastructure or centralized administration. MANETs can be used in wide range of future applications as they have the capability to establish networks at anytime, anywhere without aid of any established infrastructure. It is a challenging task to find most efficient routing due to the changing topology and the dynamic behavior of the nodes in MANET. It has been found that ant colony optimization (ACO) algorithms can give better results as they are having characterization of Swarm Intelligence (SI) which is highly suitable for finding the adaptive routing for such type of volatile network. ACO algorithms are inspired by a foraging behavior of group of ants which are able to find optimal path based upon some defined metric which is evaluated during the motion of ants. ACO routing algorithms use simple agents called artificial ants which establish optimum paths between source and destination that communicate indirectly with each other by means of stigmergy. Keeping in view of the above, in this paper we provide a taxonomy of various ant colony algorithms with advantages and disadvantages of each others with respect to various metrics.

Mobile ad-hoc networks (MANETs) are special kind of networks in which the mobility of the nodes is quite high. Nodes can join or leave the network at any time as there is no fixed infrastructure and centralized control in MANETs. All nodes are supposed to be equal in processing power. The network is required to have self configuration by means of the cooperation among the mobile devices: all nodes operate as routers and are capable of discovering and maintaining routes to propagate packets to their destinations. The movement of mobile nodes requires the aid of quite complex routing algorithms, as routes are not stable and need to be updated continuously (Toh, 2002 and Das et al., 2000). Due to the dynamic nature of MANETs, route maintenance is quite difficult task. Basically, Routing is the process of choosing paths in a network along which the source can send data packets towards destination. Routing is an important aspect of network communication because the characteristics like throughput, reliability and congestion depends upon the routing information. An ideal routing algorithm is one which is able to deliver the packet to its destination with minimum amount of delay and network overhead. The nodes update the routing tables by exchanging routing information between the other nodes in the network. Routing protocols for MANETs are classified into three different categories: proactive, reactive and hybrid protocols (Deepalakshmi and Radhakrishnan, 2011 and Sampath et al., 2011). The proactive protocols are derived from the static networks and require periodic advertisement and global dissemination of routing information for operation which leads to frequent system-wide broadcasts. These are also called as table-driven protocols which indicate that they maintain a routing entry for every possible destination in the network. The reactive routing protocols create routes only when the source node wants to communicate with the other nodes in the network. When a node requires a route to a destination, it initiates a route discovery process within the network. Once a route has been established, it is maintained by a route maintenance procedure until either the destination becomes inaccessible along every path from the source or until the route is no longer desired. Hybrid routing protocols uses the combination of both proactive and reactive protocols (Khosrowshahi-asl et al., 2011). Ant colony optimization (ACO) is a population-based metaheuristic approach introduced by Marco (1992). As the name suggests the technique was inspired by the behavior of “real” ants (Bonabeau et al., 1999, Gudakahriz et al., 2011 and Pavani et al., 2008). Ant colonies are able to find the shortest path between their nest and a food source by depositing and reacting to the trail of pheromone which provide help to future ants towards optimal paths to food (Paramasiven, 2011, Wankhade and Ali, 2011 and Pankajavalli and Arumugam, 2011). Figure 1(a) and (b) illustrates how, after some time, the ants on the shorter path reach the food source earlier as compare to the ants on the longer path. Ants on reaching the destination; start a new route backward towards the source nest by following the same path and biases the path by depositing more pheromone on the shorter path. As time progresses, the pheromone on non-optimal paths evaporate while the pheromone on near-optimal paths is reinforced. The basic principle of ACO algorithms can also be applied to many other combinatorial optimization problems (Al-Zurba et al., 2011, Roy et al., 2011 and Poojary and Renuka, 2011).Rest of the paper is organized as follows. Section 2 provides the categorization of various ACO based routing algorithms. Section 3 describes table driven algorithms. Section 4 describes the on demand algorithms. Section 5 describes the hybrid algorithms. Section 6 provides the detailed analysis and comparison of all the schemes with respect to various metrics. Finally Section 7 concludes the article Fig. 2

In this paper, we have addressed the application of ant colony optimization algorithms to solve the routing problem in MANETs. There are various categories of ant colony algorithms like proactive (table driven), reactive (on-demand) and hybrid (the combination of two) approaches. The agents in Ant Colony routing algorithms communicate indirectly through the stigmergy and provide positive feedback to a solution by laying pheromone on the links. Moreover, they have negative feedback through evaporation and aging mechanisms, which avoids stagnation. Finally, Ant Colony algorithms allow for direct agent-to-agent communication which makes them more suitable for MANETs. A detailed analysis of various ant based routing algorithms with advantages and disadvantages over each other has also been provided.