“Swarm Intelligence Based Route Determination in MANET using DSR algorithm

Swarm Intelligence Based Route Determination in MANET using DSR algorithm

Sumalatha1 ,

1Mtech Student, Dept.of ECE Engg., SJBIT

Uttarahalli Main Road,Kengeri, Bangalore-60,Kranataka

Shakuntala C H 2

2Asst .Prof.,

Dept. of ECE Engg., SJBIT Uttarahalli Main Road,Kengeri,

Bangalore-60,Kranataka

Abstract- A MANET is a type of ad hoc network that can change location and configure itself on the fly. Because MANETS are mobile, they use wireless connection to interact with various networks. Routing is the process of selecting best path in a network. In this paper we propound a algorithm to detect the misbehaving of nodes within the MANET and also to establish optimal path between a pair of nodes. Dynamic Source Routing (DSR) protocol in ad hoc networks, which forms a route upon the request from the transmitting node. It relies on source routing rather than relying on routing table which adds to its felicity. For the better performance of the proposed algorithm we employ Ant Optimization & Genetic algorithm. Swarm Intelligence is the collective behavior of decentralized, self organized systems, natural or artificial which helps to provide best solutions to solve routing issues. Genetic algorithms (GA) are meant to design computational structures and solve combinatorial optimization problem . In order to doubly ensure the maximum optimality of the routes found via GA, ACO (Ant Colony Optimization) has been implemented.

Keywords: MANET, DSR protocol, Genetic algorithm, fitness function, Ant colony optimization.

I.INTRODUCTION

A MANET is mobile ad hoc NETwork which established by wireless technology like Bluetooth .It connect dynamically through the wireless medium without any centralized structure. MANET is one of the type of wireless network, infrastructure less network. These networks have no fixed access points while every node could be host or router. These networks are self- configurable and autonomous systems consisting of routers and hosts. MANETs lack central supervision and prior organization,so the surety egress are different and thus requires different surety mechanisms than in ceremonious networks.

The Dynamic Source Routing protocol (DSR) is a simple and efficient routing protocol designed specifically for use in multi-hop wireless ad hoc networks of mobile nodes. DSR allows the network to be completely self- organizing and self-configuring, without the need for any existing network infrastructure or administration. The protocol is composed of the two mechanisms of Route

Discovery and Route Maintenance, which work together to allow nodes to discover and maintain source routes to arbitrary destinations in the ad hoc network.

Genetic Algorithms (GA) have been used to evolve computer programs for specific tasks ACO algorithms are the most successful of swarm intelligence. Swarm intelligences goal is inspired by the collective behavior of social insects like bees, termites, wasps, ants, and other animal societies like flocks of birds or fish schools to design an intelligent multi-agent system.

1. EXISTING SYSTEM

   Mobile Ad hoc Networks (MANETs) introduce a new communication paradigm, which does not require a fixed infrastructure – they rely on wireless terminals for routing and transport services. Nodes rely on each other to keep the network connected and to move information. The act of moving information from source node to destination node is called Routing. The routing concept basically involves two steps. First, detuning the optimal routing path and then transfer the information packets through the network. Routing protocols use several metrics to calculate the best path for routing the packet to its destination. These metrics are a standard measurement that could be, for example, number of hops, which is used by routing algorithm to detuning the optimal path for the packet to its destination. Routing is mainly classified into static routing and dynamic routing. Static routing maintains a routing table. Dynamic routing refers to the routing strategy that is being learnt by an interior and exterior routing. In the previous approach DSR algorithm was used which finds the multiple paths from source to destination based on rules and then choose one of the path as the best path which has the lowest end to end delay.

2. CURRENT APPROACH

In the current approach Ant Optimization & Genetic algorithm is used and applied on top of the DSR algorithm. First the multiple routes are obtained using a low delay and low hop approach. For each of the routes obtained we compute fitness function. The fitness function Routing Load (RL) MAC Load (ML), Packet Delivery Ratio ( PDR), End-to-End Delay (D), and number of packets dropped, After that higher path preference

probability will be considered as the best path and the data transmission can be started along that path. The DSR algorithm is compared with Genetic Ant Optimization

Dynamic Source Routing (GAODSR) for various entities namely Packet Delivery Ratio, Average End to End Delay

1. PROPOSED METHODOLOGY:

   Node deployment

   Multiple route

   and Routing Load. Also Fitness function, Routing paths graphs are also obtained.

   IV.LITERATURE SURVEY

   Mobile Ad Hoc Networking Imperatives and Challenges: [1] In this Paper the author tried to ensure a comprehensive overview of this field by first explaining important roles that MANETs play in wireless technology evolution.

   Performance Evaluation Of Aodv And Dsr Routing Protocols In Manet Networks : [2]

   In a Mobile Ad Hoc Network (MANET), some nodes may join the network while others may leave. In this

   1. Packet Delivery Ratio

   2. End to End Delay

   3. Routing Load

   4. Packet Dropped Ratio

   Compare DSR with GAODSR

   DSR

   Best Route using Ant Algorithm

   algorithm

   GAODSR

   Two Best Routes using Genetic Algorithm

   paper, we analyze a MANETs performance for two proactive protocols; Ad Hoc On-Demand Distance Vector (AODV) Protocol, and Dynamic Source Routing (DSR) Protocol. By using network simulator NS2, we setup and evaluate the performance of AODV and DSR protocols with respect to the packetssize.

   Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization : [3]

   This paper proposes an improved ant colony optimization algorithm with two highlights. First, candidate set strategy is adopted to rapid convergence speed. Second, a dynamic updating rule for heuristic parameter based on entropy to improve the performance in solving TSP. Algorithms are tested on benchmark problems from TSPLIB and test results are presented.

   Performance Evolution of AODV and DSR Routing Protocols in MANET Using NS2: [4]

   In this paper an attempt has been made to compare the performance of two prominent on demand reactive routing protocols for MANET: – Ad hoc On De-mand Distance Vector (AODV), Dynamic Source Routing (DSR) protocols. DSR and AODV is a reactive gateway discovery algorithms where a mobile device of MANET connects by gateway only when it is needed. The differences in the protocol mechanics lead to significant perfor-mance differentials for both of these protocols. The performance differentials are analyzed using varying metrices. These simulations are carried out using the ns-2.

   Fig: 1 Basic System Architecture

   Node Deployment- This algorithm is responsible for deploying the nodes in the network. It takes minimum x area, maximum x area, minimum y area, maximum y area as input and generates the random positins for each node along with there node id and places them in the network.

   DSR Algorithm

   The Dynamic Source Routing protocol (DSR) is based on source routing, which means that the originator of each packet determines an ordered list of nodes through which the packet must pass while traveling to the destination. The key advantage of a source routing design is that intermediate nodes do not need to maintain up-to date routing information in order to route the packets that they forward, since the packets source has already made all of the routing decisions. This fact, coupled with the entirely on-demand nature of the protocol, eliminates the need for any type of periodic route advertisement or neighbor detection packets.

   The DSR protocol consists of two basic mechanisms: Route Discovery and Route Maintenance. Route Discovery is the mechanism by which a node S wishing to send a packet to a destination D obtains a source route to D. To reduce the cost of Route Discovery, each node maintains a Route Cache of source routes it has learned or overheard. Route Maintenance is the mechanism by which a packets originator S detects if the network topology has changed such that it can no longer use its route to the destination D because some of the nodes listed on the route have moved out of range of each other.

   Compute the neighbor nodes

   Source Node, Destination Node, Transmission Range

   The following diagram shows the detailed flow of the Route discovery process from source node to the destination node.

   i =1

   Best Route Selection using Ant Colony Optimization Algorithm

   Compute Packet Delivery Ratio

   Compute the updated pheromone

   Multiple Paths obtained from GOADSR &

   Fitness Factor

   The Best Route Selection using Ant Colony Optimization can be described as follows

   No

   Stop

   Compute visibility factor

   Compute Probability of Selection

   Execute Individual GAODSR

   Yes

   i <=N neighbor

   Route Cache

   Path with highest fitness value is best

   i =i+1

   Fig:2 Multiple Routes Determination using GAODSR

   The Multiple Routes are found using GAODSR by using the flowchart as above

   1. Source Node, destination node and Transmission Range acts as an input.

   2. Find the neighbor nodes for the given

   Fig: 3Ant Colony Optimization

   1. Multiple paths are obtained using GAODSR algorithm and corresponding fitness value is computed.

   2. Computed the pheromone using the following equation

      transmission range.

   3. Compute the length of the neighbors nodes

      i, j

      FF

      k

      Nnodes

   4. For each of the neighbor nodes compute individual route discovery.

      Where,

      FF Fitness

      Factor

   5. Find the route using Individual GAODSR.

   6. Cache each of the route

   7. Repeat the above steps until all the routes are found out.

   k optimization cons tan t 0 k 1

   1. The updated pheromone is computed using the following equation

      new old

   2. The probability of selection is computed using

      Pi , j

      [i , j ]

      k

      [i, j ] [

      i

      i, j ] [i, j ]

      Where,

      cons tan t

      cons tan t

   3. The highest value of probability will correspond to routing algorithm.

2. SIMULATION RESULTS :

Input details

Node id v/s battery power in mili joules Node deployment

Best route discovered using Genetic algorithm

Various iterations of battery, new pheromone, packet delivery ratio, probability of route

Number of route v/s static routes

Route discovered v/s various network parameters

comparison

Number of node v/s battery power of the nodes

VII . CONCLUSION

In this paper we conclude that the approach presented describes a way to enhance the performance of DSR routing protocol with the help of the algorithm described. The use of Genetic Algorithm as well as Ant Colony Optimization to find the best path doubly ensures that the correct path has been found out.

REFERENCES

1. Pravin Ghosekar, Girish Katkar and Dr. Pradip Ghorpade , "Mobile AdHoc Networking: Imperatives and Challenges", IJCA Special Issue on "Mobile Ad-hoc Networks", 2010.

2. Al-Maashri, A. and Ould-Khaoua, Performance analysis of MANET routing protocols in the presence of self-similar traffic. In, Proceedings of the 31st IEEE Conference on Local Computer etworks,2006, 14-16 November 2006, pages pp. 801-807, Tampa, Florida, USA.

3. Zar Chi Su Su Hlaing and May Aye Khine, Member, Solving Traveling Salesman Problem by Using Improved Ant Colony Optimization Algorithm International Journal of Information and Education Technology, Vol. 1, No. 5,

   December 2011

4. Sachin Dnyandeo Ubarhande, "Performance Evolution of AODV and DSR Routing Protocols in MANET Using NS2", International Journal of Scientific & Engineering Research Vol 3, Issue 5, May.2012.

5. Barakovic S., Barakovic J.,Comparative Performance Evaluation of Mobile Ad Hoc Routing Protocols, Proceedings of the 33rd International Convention, pp. 518- 523, 2010.

6. Perkins C. and Bhagwat P., Highly Dynamic Destination- Sequenced Distance-Vector (DSDV) for Mobile Computers, In Proceedings of the ACM SIGCOMM, 1994.

7. David B. Johnson and David A Maltz. "Dynamic source routing in ad hoc wireless networks", Mobile Computing,

   Kluwer Academic Publishers. 1996 pp.153-18 I, 1996

8. Gulati M.K. and Kumar K., A Review of QoS Routing Protocols in MANETs, International Conference on Computer Communication and Informatics (ICCCI), pp. 1-6, 2013.

9. Chlamatac I., Conti M., Jennifer J.-N. Liu, Mobile Ad Hoc Networking : Imperatives and Challenges, Ad Hoc Networks, Elsevier, pp. 13-64, 2003.

10. Kulkarni N.S., Raman B., Gupta I., On Demand Routing Protocols for Mobile Ad Hoc Networks: A Review, International Advance Computing Conference (IACC), pp. 586- 591, 2009.

11. C.E. Perkins and E.M. Royer, "Ad-Hoc on-Demand Distance Vector Routing," Proc. Workshop Mobile Computing Systems and Applications (WMCSA '99), Feb. 1999

12. S.Usha, and Dr. S.Radha, Sathyabama, "Cooperative approach to detect misbehaving nodes in MANETs using Multi-hop acknowledgement scheme", 2009 International Conference on Advances in Computing, Control, and Telecommunication Technologies, SSN college of Engineering, Chennai 603 119, India.

13. Nadia N. Qadri, Antonio Liotta, "A COMPARATIVE ANALYSIS OF ROUTING PROTOCOLS FOR MANETS", University of Essex, Colchester, UK, IADIS International Conference Wireless Applications and Computing 2008.