Probabilistic Approach for Dynamic Traffic Assignment in Wireless Networks Using Genetic Algorithms

Probabilistic Approach for Dynamic Traffic Assignment in Wireless Networks Using Genetic Algorithms

Ch.Usha 1, T. Srinivasa Rao 2

1. Pursuing M.Tech (cse), Department of Computer Science, VVIT Nambur (V), Guntur (Dt.).AP.

2. Associate. Professor, Department of Computer Science, VVIT Nambur (V), Guntur (Dt.) AP.

ABSTRACT

Many online or local data sources provide powerful querying mechanisms but limited ranking capabilities. For instance, Pub Med allows users to submit highly expressive Boolean keyword queries, but ranks the query results by date only. However, a user would typically prefer a ranking by relevance, measured by an information retrieval (IR) ranking function. A naive approach would be to submit a disjunctive query with all query keywords, retrieve all the returned matching documents, and then re- rank them. Unfortunately, such an operation would be very expensive due to the large number of results returned by disjunctive queries. In this paper, we present algorithms that return the top results for a query, ranked according to an IR-style ranking function, while operating on top of a source with a Boolean query interface with no ranking capabilities (or a ranking capability of no interest to the end user).

The algorithms generate a series of conjunctive queries that return only documents that are candidates for being highly ranked according to relevance metric. Our approach can also be applied to other settings where the ranking is monotonic on a set of factors (query keywords in IR) and the source query interface is a Boolean expression of these factors. Our comprehensive experimental evaluation on the Pub Med database and a TREC data set show that we achieve order of magnitude improvement compared to the current baseline approaches.

Keywords: Hidden-web databases, keyword search, top-k ranking.

1. INTRODUCTION

In computer networks, such as the Internet and the Mobile Ad-hoc Networks, routing is one of the most important issues that have a significant impact on the networks performance. The routing should be done through the optimal path exists between the source node and destination node. An

ideal routing algorithm should strive to find an optimum path for packet transmission within a specified time and constraints. There are several search algorithms for the shortest path (SP) problem named as breadth-first search algorithm, the Dijkstra algorithm and the BellmanFord algorithm [1]. Since these algorithms can solve SP problems in polynomial time, they will be effective in fixed infrastructure wireless or wired networks. But, they exhibit unacceptably high computational complexity for real-time communications involving rapidly changing network topologies. We consider wireless networks with fixed nodes as target systems. Since all the nodes cooperatively maintain network connectivity without the aid of any fixed infrastructure networks, dynamic changes in network topology are possible. An optimal (shortest) path has to be computed within a very short time (i.e., a few us) in order to support time-constrained services such as voice, video, and teleconferencing [2]. The indicated algorithms do not satisfy this (real-time) requirement.

1. Dynamic Traffic Assignment (DTA)

   It is the process of assigning the traffic through the optimal path based on the internal conditions that are employed in the system. Dynamic Traffic Assignment (DTA) process can be employed to any field like, road traffic assignment, network packet traffic assignment, data traffic assignment in the circuit boards etc. In this project the entire focus is one network traffic assignment, in the network there are n number of nodes including one source and one destination. Each node has certain number of connections (links) with other nodes. The main aim is to find out the optimal path between source and destination in order to transfer the packets. But if any node in the network communication line fails

   (connection lost with other nodes), then system need to find out a new optimal path between source and destination in order to assign the traffic in the new optimal path (Dynamic traffic assignment).

2. Genetic Algorithms

   A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a particular class of evolutionary algorithms (EA) that use techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover.

   1. Selection operator

      During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate this fitness of each solution and preferentially select the best solutions. Some other methods rate only a random sample of population. Here each method has its own functional advantage based in the kind of application.

   2. Crossover operator

      Crossover is a genetic operator that combines two chromosomes to produce a new chromosome. The idea behind crossover is that the new chromosomes may be better than both of the parents if it takes the best characteristics from each of the parents. Literature studies explore different types of crossover methods like one-point crossover and two-point crossover etc. Fig 1 and Fig 2 represent one-point and two-point crossovers methods respectively.

      Fig 1: One-point Crossover

      Fig 2: Two-point crossover

   3. Mutation operator

      Mutation is a genetic operator that alters one or more gene values in a chromosome from its initial state. This can result in entirely new gene value being added to the gene pool. With this new gene values, the genetic algorithm may be able to arrive at better solution than was previously possible. Mutation is an important operator of the genetic search as it helps to prevent the population from standing in the local optimization. The general representation of one-point mutation and two-point mutation is shown in the Fig 3 and Fig 4 respectively.

      Fig 3: One-point mutation

      Fig 4: Two-point mutation

   4. Fitness operator

A fitness function is a particular type of objective function that prescribes the optimality of a solution in a genetic algorithm so that particular chromosomes may be ranked against all other chromosomes. Optimal chromosomes, or at least chromosomes which are more optimal, are allowed to breed and mix their datasets by any several techniques, producing a new generation that will be ever better.

1. Solving problem using Genetic Algorithm:

   In the target problem a computer network has been considered which has 20 nodes. Connections and connection weights (distances) are represented in the network. The final goal is finding out the optimal solution from source to destination.

   Fig 5: Target network

   GA Control info:

   Number of nodes: 20.

   Read connection link values and distance values from the user or from the file.

   Enter the number of iterations: 10000.

   Maximum size of the population: 20 (number of nodes)

   Initial population:

   Initial population (two chromosomes) can be given by the user or by the system.

   Do you want the random input: Y (System will generate the initial population).

   Generate chromosomes:

   1. 15114937612131718

   20 length(13) distance(989) 2. 143713141520

   length(8) distance(842) Population size: 2

   Selection:

   Two chromosomes need to be selected from the population

   Selected parent chromosomes using hybrid selection method:

   1. 15114937612131718

   20 length(13) distance(989) 2. 143713141520

   length(8) distance(842)

   Crossover:

   Crossover is applied on the selected chromosomes and two new child chromosomes are generated. Here crossing check for the selected parent chromosomes is 7

   Generated child chromosomes:

   1. 1511493713141520

   length(11) distance(1070)

   2. 143761213171820

   length(10) distance(756)

   Fitness Check:

   Both generated children satisfy the fitness condition. Hence these are added to the population.

   Population size: 4

   Mutation:

   Mutation is applied on the children, which are generated from the crossover operator.

   1. 151149151920

   length(7) distance(438)

   2. 14381420 length(6)

   distance(165)

   Fitness Check:

   Both generated children satisfy the fitness condition. Hence these are added to the population.

   Population size: 6

   Repeat the process from selection function until termination condition is satisfied (Number of iterations are completed). In this process if the population size exceeds the original value (number of nodes) then the new chromosomes should replace the old chromosomes which have maximum distance value (low fitness value) in the population.

   The final population is (Top 10 solutions): 1. 1381420 length(5)

   distance(142)

   2. 1491420 length(5)

   distance(234)

   3. 1491520 length(5)

   distance(342)

   4. 13891420

   length(6) distance(392)

   5. 1378141820 length(7)

   distance(455)

   6. 1511491420 length(7)

   distance(464)

   7. 13271213171820

   length(9) distance(467)

   8. 1541011161920

   length(8) distance(483) 9. 14389101920

   length(8) distance(486) 10. 13891520

   length(6) distance(500)

2. Experimental results graph:

   In this section, proposed GA is compared with Munetomos, and Inagakis algorithms and the existing algorithm through computer simulations. Even with the reduction of functional constraints on the existing system with the addition of new selection method with inclusion of probability analysis, provides same results along with the enhancement of DTA. Here a target problem is considered to test the proposed GA with existed algorithms. The target problem is represented in Fig 15.

   The proposed algorithm attains the same graph with chang wooks algorithm with reduction of number constraints on the genetic operator. In addition to the optimal path calculation, DTA has been implemented. The experimental analysis is shown in the Fig16

   Fig 06: Convergence property of each algorithm

3. CONCLUSION

   In this project a new probabilistic selection approach is presented for dynamic traffic assignment using genetic algorithms. Crossover and the mutation operations work on variable-length chromosomes. The crossover is simple and independent of the location of crossing site. Consequently, the algorithm can search the solution space in a very effective manner. The mutation helps to maintain the diversity of population thereby avoiding local optimization. A special treatment is meant for infeasible solutions by developing an effective fitness evolution function. Simulation studies show that the algorithm is indeed insensitive to variations in network topologies in respect of both route optimality (quality of solution) and convergence speed. The quality of solution has empirically been found to be better than that of other algorithms.

4. REFERENCES

   1. Runmei Li and Wei Li, The Application of Genetic algorithm to Dynamic Traffic Assignment, 0-7803-896-11 /05/$20.00

      @005 IEEE.

   2. C. Chitra and P. Subbaraj, A Nondominated Sorting Genetic Algorithm for Shortest Path Routing Problem, International Journal of Electrical and Computer Engineering 5:1 2010

   3. Yousra Ahmed Fadil, Routing using genetic algorithm for large networks, Diyala Journal of Engineering Sciences Vol. 03 , No. 02 , pp. 53 -70 , December 2010

   4. Shubhra Sankar Ray, Sanghamitra Bandyopadhyay and Sankar K. Pal, New Operators of Genetic Algorithms for

      Traveling Salesman Problem, 0-7695- 2128-2/04 $20.00 (C) 2004 IEEE

   5. Aqeel Mumtaz, Abdul Majid, Adeel Mumtaz, Genetic Algorithms and its Application to Image Fusion, 978-1-4244- 2211-1/08/$25.00 ©2008 IEEE

   6. Chen GUO, Ming HUANG, Xu LIANG, An Improvement Diploid Genetic Algorithm for Job-shop Scheduling Problem, 978-1-61284-449-7/11/$26.00

      ©2011 IEEE

   7. Milena Karova Vassil Smarkov Stoyan Penev, Genetic operators crossover and mutation in solving the TSP problem, International Conference on Computer Systems and Technologies – CompSysTech 2005

   8. R.sivaraj, Dr.T.Ravichandran, A review of selection methods In genetic algorithm, International Journal of Engineering Science and Technology (IJEST), ISSN:0975-5462 Vol. 3 No. 5 May 2011.

   9. Pratibha Bajpai, Dr. Manoj Kumar, Genetic Algorithm-an Approach to Solve Global Optimization Problem, Indian Journal of Computer Science and Engineering Vol 1 No 3 199-206.

   10. The C programming language by W.Kernighan and Dennis M.Ritchie, Prentice Hall of India.

   11. Software engineering- A Practioners approach, Roger S Pressman, Tata McGraw hill publication.

   12. Data structures by Trumbley & Sorrenson