Journal of Global Research in Computer Sciences
MenuISSN: 2229-371X
ISSN: 2229-371X
S.Aravindh*1 and Mr.G.Michael2
|
| Corresponding Author: S.Aravindh, E-mail: aravindhgojan@gmail.com |
| Related article at Pubmed, Scholar Google |
Visit for more related articles at Journal of Global Research in Computer Sciences
Routing in dynamic network is a challenging one, because the topology of the network is not fixed. This issue is addressed in this presentation using ant algorithm to explore the network using intelligent packets. The paths generated by ants are given as input to genetic algorithm. The genetic algorithm finds the set of optimal routes. The importance of using ant algorithm is to reduce the size of routing table. The significance of genetic algorithm is based on the principle evolution of routes rather than storing the precomputed routes.
Keywords |
| Routing, Data mining ant colony optimization, genetic algorithm(crossover, Mutation). |
INTRODUCTION |
| Data mining (sometimes called data or knowledge discovery) is the process of analyzing data from different perspectives and summarizing it into useful information.[1] Data mining software is one of a number of analytical tools for analyzing data. Some of the parameters of data mining’s are, association, sequence, classification ,clustering, forecasting and etc., Data classification is the categorization of data for its most effective and efficient use.[2] For this purpose the classification tools is mainly used. This paper deals with the meta heuristic optimization, which is used to find shortest path in Wireless Mesh Networks. The metaheuristics is the high level strategies which guide other heuristics to search for the optimal solution. It is very effective and flexible.[3] |
| The ant colony optimization is the popular framework based on the original notion of swarm intelligence (SI).[3] The SI is the process of computation for problem solving and obtain the accurate solution based on the natural collection. For example consider the birds flocked like a V-shaped on the sky the birds flocking on the sky is the natural one, but the SI is deals with how they are flocking in certain shape (like v-shape, curve shape, line, etc.,) and apply this technique or concept to the problem to get the solution[6]. |
| The ant colony optimization is also the natural metaphor[4]. It is one of the main techniques in the SI. The SI of ACO can explain by ant chain and ant wall. |
 |
| The (figure 1.1) show the ant chain, that the one ant is act as a initiator and other ants are like the follower [3]. |
| The (figure 1.2) show the ant wall, in that the ant did not give the way to other insects or any other obstacles [3]. |
| From these two, the ant chain is best for finding the shortest path. In this paper we use the ant chain for transfer the message after it find the path. |
| The Genetic Algorithm is optimization technique based on variations and selections. Once you encode the solution for the problem in the form of chromosomes in GA then it can compare the relative performance of solution [11]. |
ANT COLONY OPTIMIZATION |
| Ant colony optimization is a meta-heuristic technique that uses artificial ants to find solutions to combinatorial optimization problems. ACO is based on the behaviour of real ants and possesses enhanced abilities such as memory of past actions and knowledge about the distance to other locations. In nature, an individual ant is unable to communicate or effectively hunt for food, but as a group, ants possess the ability to solve complex problems and successfully find and collect food for their colony. Ants communicate using a chemical substance called pheromone. As an ant travels, it deposits a constant amount of pheromone that other ants can follow. Each ant moves in a somewhat random fashion, but when an ant encounters a pheromone trail, it must decide whether to follow it. If it follows the trail, the ant’s own pheromone reinforces the existing trail, and the increase in pheromone increases the probability of the next ant selecting the path. Therefore, the more ants that travel on a path, the more attractive the path becomes for subsequent ants. Additionally, an ant using a short route to a food source will return to the nest sooner and therefore, mark its path twice, before other ants return. This directly influences the selection probability for the next ant leaving the nest. |
 |
| This diagram shows the total amount of the enzymes level (call as pheromone). The large value of pheromone path is considered as a shortest path. |
| In our work, the ACO is used for finding the shortest path using the distance value assign to the each node[5]. The host of the ant is considering as the source node and their food is representing as the destination. The current node is act as a ant in routing process for finding the next shortest nodes in the wireless mesh network. |
| In general the ACO assign two ants such as forward and backward ant. The forward ant is used while searching the food and the backward ant is used when the ant get back to host. |
| But in transferring the information, only the forward ant can be used. There is no use of backward ant in the transferring process, but it can be used for the acknowledgement purpose. Here the current node is assign as a forward ant during the transformation; it can be also act as backward ant during the acknowledgement. |
| Now consider the general pseudo code for the ACO. |
 |
| If the data’s are send from source to destination, then it follow the pseudo code of the forward ant. The steps of the forward ant as follow: |
| a. Get the next node based on the distance value. Which node have the less distance is consider. |
| b. Once it find the next node, update the data storage of the router(simply the routing table) and send the data packets to the certain node. |
| c. If there is no path or link or node are available then keep the record of the data packet as it is, and discard it. Find any other path. |
| In general the forward node (source to destination) use the stack (LIFO) order to store the data in the routing table. Similarly the backward node (destination to source) use the queue (FIFO) order to store the data in routing table [4]. |
| If the distance of the path is different, then it is very easy to find the shortest distance using this algorithm. If the nodes have same distance then the ACO can’t to find the optimal solution, to overcome this we use the GA for finding the fitness value for each and every node based on the cost value of the node. Even though the ACO can find the shortest distance, but it not be the optimal solution, for this reason only we use both ACO and GA for produce the optimal solution. |
GENETIC ALGORITHM |
| A way to employ evolution in the computer. In GA, the searching and optimization techniques are based on variation and selection [7]. Once you can encode solutions of a give problem to chromosomes in GA, and it can compare the relative performance (fitness) of solutions. The flow chart for genetic algorithm is shown: |
 |
Flow chart for GA: |
| The shortest path which is found by ACO, is given as a input to the GA. The initialise population (shown in flow chart[8]) contain the path input which is going to evaluate a fitness for each path. GA consists of three process (Selection, Crossover, Mutation). The selection is used to find optimal fitness path. Crossover is used to obtain a new path. Mutation is used to modify or recombine a new path which gives accurate shortest path. |
Pseudo code for GA: |
 |
| The general pseudo code of the genetic algorithm [7] is shown. It start the process with the initial population, it is refer as a set of path (in our paper). Then it evaluate the fitness for each path. It is evaluate based on the cost of each node in the randomly selected path. |
| The prune population is nothing but the removal of worst shortest path based on the fitness value. It calculate the fitness value for all the path in the set. Then it remove the worst, finally it have the pairs of paths with the best fitness value. |
| After select the pairs of path it applies the cross over operator. The pairs of path is consider as a parents, in cross over it produce the children that is refer as a new path. |
| Once it obtains the new path then it moves mutation operator to modify the new path, so that, it can find the optimal path. Following can briefly explain the genetic operators. |
Selection of parents (path): |
| There are many different selection method, such as elitist selection, rank selection and roulette wheel selection. In this paper, the roulette wheel selection method is used. |
| In roulette wheel selection, the individual is selected based on the relative fitness with its competitors. This is similar to dividing the wheel into a number of slices. More path get larger slice. For selecting the path for new path. |
Cross over: |
| Crossover or recombination operator combines sub parts of two parent chromosomes and produces offspring that contains some part of both the parent genetic material. Crossover is mainly of two types namely single point crossover and multipoint crossover[9]. In single point crossover, there is one cross over site and in multipoint crossover there is more than one crossover site. In single point crossover, one offspring consists of part before crossover site of parent 1 and part after crossover site of parent 2, another offspring consists of part before crossover site of parent 2 and part after crossover site of parent 1. Following shows the example for single point crossover. The parents are paths from source 1 to destination 6 and the crossover site is 4. |
| Parent 1: 1 2 3 4 | 5 6 |
| Parent 2: 1 5 4 2 | 3 6 |
| Offspring 1: 1 2 3 4 3 6 |
| Offspring 2: 1 5 4 2 5 6 |
| Here the paths are act as a parent 1 and 2, the offspring is a new path which is obtaining. The offspring have the repeated node, for modify that node we use the mutation. |
Mutation: |
| It may be possible that crossover operation may produce degenerate population. In order to undo this, mutation operation is performed[9]. Mutation operation can be inversion, insertion, reciprocal exchange or others. In case of inversion two random points are selected and the string between them is reversed. In case of insertion a node is inserted at random position in the string. In reciprocal exchange, nodes at two random positions are exchanged. |
| Consider the above offspring 1 and 2 for the mutation(insertion method). |
| Offspring 1(path 1): 1 2 3 4 3 6, in this new path, the node number is repeated for two time, instead of any one 3, using insertion method in mutation we can insert a node number 5(which is the missing node in the new path) |
| Offspring 2(path 2): 1 5 4 2 5 6,this is also similarly like the path1. Her instead of 5 we can insert 3, which is the missing node. |
| After performing this process in GA, the obtain solution is always optimal[9]. |
Hybrid of ACO and GA: |
| In this phase, the ACO is used to find the shortest path with help of distance value, the output of the ACO is given as a input to the GA. The set of paths are obtained during the ACO process are inputs to the GA. The genetic algorithm undergoes the selection, crossover and mutation process and it gives the result. The result contain only one path which is optimal among the shortest path. This is the process going to proceed in our paper. |
| The pseudo code for the hybrid is start with the current node, it whether the current node is the destination node, if it is a destination then save the path, otherwise check for other neighbouring node with the distance value and find fitness. |
| Here note one thing that every node have a certain value, this values are refer as a distance in ACO at a same time it is used as a cost in GA. |
| For finding a path we used a ACO and to find the fitness, optimal path among these can found by GA. Tha ACO is used not only to find the path but it is also used to maintain the routing table as very simple and it is easy to understand. The reason for using a genetic algorithms are[11]: |
| They are parallel in nature. They explore solution space in multiple directions at once. GA is well suited for solving problems where the solution space is huge and time taken to search exhaustively is very high. |
| They perform well in problems with complex fitness. If the function is discontinuous, noisy, changes over time or has many local optima, then GA gives better results [10]. |
| Genetic algorithm has ability to solve problems with no previous knowledge (blind). |
| For this reason we hybrid the ACO with GA to find the shortest path. |
| Following pseudo code can easily explain remaining steps in hybrid of ACO and GA. |
 |
| The function RandomSelectNode () is used to get path randomly from the saved path. |
| The RouletteWheelSelection () method which is like cyclic process. This selection process have a connection with all the nodes in network, for that this method is widely used in WMNs. |
| RandomlyChooseMutationPoint () is used when the new path is obtained. The new path having two node as same. Using this method node can be modified by the missing nodes. |
| Using this pseudo code we can easily hybrid and find the shortest path. |
CONCLUSION |
| In this paper ant algorithm and genetic algorithm are used for routing in packet switched data networks. Ant algorithm, is found to reduce the size of routing table. Genetic algorithm cannot use global information of the network. Hence, the combination of these two algorithms, which makes the packets to explore the wireless mesh network independently, helps in finding path between pair of nodes effectively. The proposed algorithm creates initial population, forwards current node, access fitness, generate new population using genetic operators and update routing table. |
References |
|