ISSN ONLINE(2319-8753)PRINT(2347-6710)

All submissions of the EM system will be redirected to Online Manuscript Submission System. Authors are requested to submit articles directly to Online Manuscript Submission System of respective journal.

Enhancing Network Performance Using Genetic Algorithm in Face Routing Protocol

D.Saravanan1 and T.Sangeetha2
  1. Associate Professor, Department of CSE Pavendar Bharathidasan college of Engg. &Tech, Tiruchirappalli, India
  2. PG Scholar, Department of CSE Pavendar Bharathidasan college of Engg. &Tech, Tiruchirappalli, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

The performance of the networks is analyzed based on the routing protocols. Usually routing protocols determine the paths based on the network topology and configuration parameters, and not depend on the traffic load on the routers and links. Routing optimization is done using Genetic Algorithm in Minimum Spanning Tree (MST). By using FACE Routing technique, each node is able to gather the location information of all neighboring nodes. Through the Ranking concept, optimal route is determined, which results efficient routing.

Keywords

Mobile Adhoc Network (MANET), FACE routing protocol, Genetic Algorithm (GA), Unit Disk Graph (UDG), Minimum Spanning Tree (MST)

INTRODUCTION

In a communication network, when two nodes are not connected directly, then their messages to each other need to be forwarded through intermediate nodes. Finding a path between two nodes on which to send messages in data communication networks is a fundamental problem, called routing. In a traditional computer network, there are nodes dedicated to the routing task, called routers, through which messages will be forwarded to their destinations.
Host and Server will be communicating when forwarding messages through routers. Whereas, in wireless ad-hoc network, nodes act as host, server and router and so it could not be distinguished. Wireless adhoc networks are also different from wireless networks with base stations, such as cellular phone systems, in which messages are relayed by the base stations. The participating nodes form a self-organized network without any centralized administration or support. Therefore, wireless ad-hoc networks are purely distributed systems.
A new family of geometric planar graphs is proposed[8], which is completely different from any known graph, and focusing on their theoretical properties. Hypocomb (Hypotenuse-comb), is the “dual” of a truncated mes h[8]. It is obtained by linking vertices that have a ray-blocking relation in Besh, and is proved to be a connected planar with unbounded degree. Then, applying constrained edge creation rule, maximum degree is reduced to 6 and the resulting Hypocomb is called Reduced Hypocomb. The degree bounded planar graph computed using 1-hop neighbor position information and has slightly larger degree 8, known as Local Hypocomb. Local Hypocomb is presented on the basis of UDG. In this paper, UDG is extracted from complete graph, and is concerned for creating LMST.
A Local MST (LMST) [5] is a connected subgraph of UDG, constructed locally as follows: at each vertex u, compute the MST of the subgraph of Vnbr(u); add incident edge uw to LMST if and only if the edge is in both MST(Vnbr(w)) and MST(Vnbr(w)). The construction is based on 2-neighborhood information of u because it needs MST(Vnbr(w)) for every UDG edge uw. LMST contains MST as subgraph and has the same degree bound 6. In [12], it is proved that LMST is planar. The notion has been extended to k-Local MST (LMSTk) where each edge is determined by the MSTs of the k-hop neighborhood of its two end vertices [13]. LMST is not a spanner.
In this paper, FACE Routing is used, which is a technique that ensures packet delivery in static connected plane graphs[15]. In FACE routing, faces are intersected by a line segment between source node and destination node, and the packet is forwarded along the boundaries of the faces.
Generally, routing algorithms work on the cost to find the routs so each path evaluated in terms of cost. OSPF (Open Shortest Path First) is an interior routing protocol which depends on the Dijkstra algorithm. This algorithm finds the shortest path between each source and destination and the cost is the first parameter to calculate the path. If the shortest path becomes overloaded, then the packets will not arrive to the desired destination or may be Delayed, a lot of queuing and processing on the routers and less service quality.
In this paper, the problems in transmitting data are considered. The idea analyzed, is to select the routes, through which IP packets travel through the network, to current traffic situations and, thus, to utilize available network resources efficiently, leading to improved Quality of Service (QoS). Every path will be rated. The possible routes towards the destination are analyzed , and the more optimal route will be selected based on the ranking concept.
Image
Genetic algorithm[14] is an optimization and evolutionary algorithm that solves optimization problems. The aim is to solve the optimization problem in IP networks using genetic algorithm. The solution starts with finding alternative paths to alternate the overloaded path using genetic algorithm.

MANET

Mobile Ad-hoc Networks is a collection of mobile nodes without any central coordination and fixed infrastructure. The nodes in the network can act as server, hosts and router; they can forward data throughout the network. These nodes can transmit data with other nodes within inside or outside their radio range. Since, Adhoc Network do not have gateway, nodes can even act as gateway.
Image
MANET poses two major challenges such as:
a. In wireless adhoc network, no nodes will be devoted as router, server or database and therefore, network needs routing protocols.
b. Since, Adhoc undergoes frequent topology changes; the routing protocol selected should be more adaptable to the topology changes.
A large variety of ad-hoc routing protocols have been proposed, ranging from modifications and optimizations of traditional routing approaches for static networks to innovative methods for ad-hoc networks that utilize geographic location information about nodes. One approach to ad-hoc routing is to modify traditional routing algorithms by maintaining up-to-date topology information. This is done by periodically broadcasting updates to routing information throughout the network. However, this involves large communication overhead. To avoid periodically exchanging routing information, another approach is to establish a route only when it is needed by flooding a route request throughout the network. Both approaches are efficient only in small and moderate sized networks.

GENETIC ALGORITHM

Genetic Algorithm[15] is an optimization and evolutionary algorithm that solves optimization problems. The aim is to solve the optimization problem in IP networks using genetic algorithm. The solution starts with finding alternative paths to alternate the overloaded path using genetic algorithm.
Genetic algorithms are different from other heuristic methods. The most important difference is that:
1) A genetic algorithm works on a population of possible solutions, while other heuristic methods use a single solution in their iterations.
2) Another difference is that genetic algorithm is stochastic, not deterministic. Each individual in the genetic algorithm population represents a possible solution. Some individuals are selected based on the fitness value. And then, genetic algorithm imitates the nature genetic process, crossover, to exchange some of these individual genetic data randomly to generate the offspring.
The main operations of genetic algorithm are encoding, initial population, and evaluating fitness value, reproduction, crossover and mutation.
Image
Genetic Algorithm uses several genetic operations such as selection, crossover, and mutation in order to generate a new generation of population, which represents a set of solutions (routes) to the current problem. Each individual or path within the population will be assigned a fitness value, which is calculated based on a pre-determined fitness function that measures how optimal its solution is in solving the current problem. In order to solve the shortest path problem using the GA , we need to generate a number of solutions, and then choose the most optimal one among the provided set of possible solutions. In order to solve the problem, an initial population that forms the first set of paths to be used in the GA is randomly created. Each path represents one possible solution to the current problem at hand. After that, they (path) are estimated using certain fitness function, which determines how well the solutions are. Taking into account the fitness value of each solution or path, some paths or individuals will be selected (selection operation), and the basic genetic operations such as crossover and mutation are applied on these paths. Then, the fitness value of each path is re-calculated, and the best solutions are selected to be considered for the next generation.

FACE ROUTING PROTOCOL

This paper uses FACE routing, which is the first geometric routing algorithm that guaranteed message Delivery without flooding[1]. Several variants of face routing protocols were subsequently proposed. FACE routing is applied on a plane subgraph of the network graph. A plane graph divides the plane into faces. The line segment between the source node and the destination node intersects some faces. In face routing, the packet is forwarded along the boundaries of these faces. A specific face routing protocol provides a set of rules for each node to decide where to send a packet using only the local information about its neighbors and the information in the packet header.
Image
When face routing starts, the packet is forwarded along the boundary of the first face intersected by the line segment from the starting point to the destination. The first edge of the traversal of a face is the first edge in clockwise order around the starting point from the line segment to the destination. After the traversal of an edge (u, v), the next edge of the face traversal is the first edge after (v, u) in clockwise order around v. In this way, the packet traverses the edges on the boundary of the face in the counterclockwise direction. The traversal in this way is called using the right-hand rule[3]. When the traversal reaches an edge that intersects the line segment from the starting point to the destination at a point closer to the destination than the starting point is, that point becomes the new starting point and the traversal switches to the next face. This procedure repeats until the destination is reached.

SYSTEM ARCHITECTURE

This paper deals about improving network performance and providing efficient routing to the network.
For entering into the network, the new node will be challenging to the existing node for connection. Then, through the Random Key Generation, the new node will get authenticated. The node after getting authenticated, will become a member in the network, and can start its data session. The data will be transferred, in the most optimal path, which is determined using Genetic Algorithm and through the ranking concepts (as in fig. 5).
Image
A. Authentication
Authentication is any process by which a system verifies the identity of a User who wishes to access it. Since Access Control is normally based on the identity of the User who requests access to a resource, Authentication is essential to effective Security. Each and every node in the network should be an authorized node. Every new node which entering into the network, will get authenticated by the existing node
For instance, consider a node A and B are the existing nodes, and C is the new node requesting the node A for getting connection in the network. Through Random Key Generation, the new node will get authenticated and it will be added to the network.
B. Ranking
Ranking defined as the rating of friends i.e., Friends are rated on a scale of zero to ten. Initially each node will be having the nodes, which have been connected in the network, known as Friend list. Friends of friends will be joining to the network. There are three classes of ratings such as Data Rating, Net Rating and Friend Rating.
Data Rating, is based on the amount of data transferred. Friend Rating, is based on the opinion of the friends about a node. And, the Net Rating is defined as the combination of Data Rating and Friend Rating.
C. Security
The friend list of each node has to be shared in a secure manner. To accomplish friend sharing, the control packet FREQ(Friend sharing REQuest) is used. The nodes which receiving the FREQ will be replying with the nodes in its friend list, unauthenticated list and the question mark list. Any node can request for the FREQ. After sharing the friends, the nodes which are not in the friend list, will get authenticated. Then, the nodes may start its data session.
D. Routing
This section deals with the Genetic Algorithm. By this, the effective route can be determined. That is, the number of possible paths are determined, and from that the efficient route will be determined. And so, the data can be transferred in minimum time, which in turn increases the data rate and net rate.

CONCLUSION

In this paper, we have proposed an efficient routing scheme, using FACE routing with Genetic Algorithm. In FACE Routing, the location information about nodes is gathered and the combined usage of Genetic Algorithm and FACE routing, reduces the routing overhead such as time delay, packet loss and improves the network performance. In the future work of this paper, Energy Consumption is reduced, while retransmitting the packet.

References

  1. Bose p., Morin p., Stojmenovic. And Urrutia J. (2001) “Routing with Guaranteed Delivery in Ad Hoc Wireless Networks,” W ireless Networks, vol.no7, no.6, pp.609-616.
  2. Bose p., Devroye L., Evans W. And Kirkpatrick D. (2002) “On the Spanning Ratio of Gabriel Graphs and Beta- Skeletons,” Proc.Latin Am. Symp. Theoretical Informatics(LATIN)
  3. Frey H. and Stojmenoic I. (2006) “On Delivery G uarantees of Face and Combined Greedy-Face Routing Algorithms in Ad Hoc and Sensor Networks,” Proc.ACM MobiCom, pp.390-401
  4. Gao J., Guibas L.J., Hershberger J., Zhang L. and Zhu A., (2001) “Geometric Spanner for Routing in Mobile Networks,” Proc. ACM MobiHoc, pp.45-55.
  5. Li N., Hou J.C. and Sha L., (2003) “Design and Analysis of a MST Based Topology Control Algorithm,” Proc.IEEE INFOCO M.
  6. Li X., Santaro N. and Stojmenovic I. (September 2009) “Localized Distance-Sensitive Service Discovery in Wireless Sensor and Actor Networks,” IEEE Trans.Computers, vol.58, no.9, pp.1 275-1288.
  7. Li X., Mitton N., Simplot Ryl I. and Simplot-Ryl D. (August 2002), “Dynamic Beacon Mobility Scheduling for Sensor Loca lization,” IEEE Trans. Parallel and Distributed Systems, vol.23, no.8, pp.1439-1452.
  8. Li X., Mitton N., Simplot Ryl I. and Simplot-Ryl D. (July 2013) “Hypocomb: Bouded-Degree Localized Geometric Planar Graphs for Wireless Ad Hoc Networks,” IEEE Trans. Parallel and Distributed Systems, vol.24, no.7.
  9. Li X., Mitton N., and Simplot-Ryl D. (2011), “M obility Prediction Based Neighborhood Discovery for Mobile Ad Hoc Networks,” Proc. 10th Int’l IFTP TC 6 Conf. Networking IFIP (NETWORKING ‘ 11), pp.138-151.
  10. Li X.Y., (2003) “Approximate MST for UDG Local ly,” Proc.Ninth Ann. Int’l Conf.Computing and Combinatorics (COCOON), pp .364-37.
  11. Li X.Y., Calinescu G., Wan P. And Wang Y (October 2003), “Localized Delanauy Triangulation with Application in Ad Hoc Wireless Networks,” IEEE Trans.Parallel and Distributed Syst ems,vol.14, pp.1035-1047.
  12. Li.X.Y., Wang Y., Wang P.J., Song W.Z. and Frieder O., (2004) “Localized Low Weight Graph and its Applications in Wireless Ad Hoc Networks,” Proc.IEEE INFCOM.
  13. Li X.Y., Wang Y. and Song W. (December 2004) “ Applications of k-Local MST for Topology Control and Broadcasting inWireless Ad Hoc Networks,” IEEE Trans.Parallel and Distributed Syst ems, vol.1 5, no.12, pp.1057-1069.
  14. Wang Y. and Li X.Y. (2006) “Localized Construc tion of Bounded Degree Planar Spanner for Wireless Networks,” Mobil e Networks and Applications, vol.11, pp. 161-175.
  15. Yousra Ahmed Fadil (December 2010) “Routing us ing Genetic Algorithm for Large Networks,” vol.03 , no.02, pp. 53-70.
  16. Xiaoyang Guan (2009) “Face Routing in Wirele ss Networks”.