Adaptive Fuzzy Route Lifetime For Ad-Hoc On-Demand Distance Vector (AODV) Routing Protocol

Adaptive Fuzzy Route Lifetime For Ad-Hoc On-Demand Distance Vector (AODV) Routing Protocol

Bipasha Biswas Mallick1

Department of Computer Applications,

Haldia Institute of Technology, Haldia, WB, INDIA, 9475145486

Dipankar Pramanik2, Computer Science & Engg. DMSIT, Haldia, WB, INDIA,

Ramkrishna Das3, Department of Computer Applications,

Haldia Institute of Technology, Haldia, WB, INDIA, 9933718033,

Abstract. Ad-hoc On-Demand Distance Vector (AODV) routing protocol has been continues to be a very active and fruitful research protocol since its introduction in the wireless ad-hoc networks. AODV uses a static value for its route lifetime parameter called Active Route Timeout (ART) which states the time that the route can stay active in the routing table. Route lifetime may be more accurately determined dynamically via measurement, instead of using a statically configured value. To accomplish this, the fuzzy logic system was used to obtain adaptive values for ART depending on the situation of the transmitter and intermediate nodes. Analysis shows that the proposed design method is quite efficient and superior to the conventional design method with respect to data packet delivery ratio, routing overhead using NS-2 simulator.

Key words: Ad-hoc networks, AODV, adaptive route timeout, fuzzy route lifetime.

1. Introduction

   A Network [1] is defined as the group of people or systems or organizations who tend to share their information collectively for their business purpose. In Computer terminology the definition for network is similar as a group of computers logically connected for the sharing of information or services (like print services, multi-tasking, etc.). Initially Computer networks were started as a necessity for sharing files and printers but later they have moved from that particular job of file and printer sharing to application

   sharing and business logic sharing. Proceeding further, Tanenbaum defines [1] computer networks as a system for communication between computers. These networks may be fixed (cabled, permanent) or temporary.

   A network can be characterized as wired or wireless. Wireless can be distinguished from wired as no physical connectivity between nodes that are needed.

   Routing is an activity or a function that connects a call from origin to destination in telecommunication networks and it also plays an important role in building architectures, designing and to make operation of networks.

   degree of node mobility.

   degree of node mobility.

   Ad-hoc networks are wireless networks where nodes communicate with each other using multi-hop links. There is no stationary infrastructure or base station for communication. Each node itself acts as a router for forwarding and receiving packets to/from other nodes. Routing in ad-networks has been a challenging task ever since the wireless networks came into existence. The major reason for this is the constant change in network topology because of high

   Figure 1. Mobile Adhoc Network.

   A number of protocols that have been developed to accomplish this task. The routing protocols [1][2] in mobile networks are subdivided into two basic classes:

   • Proactive routing protocols

   • Reactive routing protocols

   The proactive routing protocols (e.g. DSDV)[2] are table-driven. They use link-state routing algorithms flooding the link information usually. Link-state algorithms maintain a full or partial copy of the network topology and costs for all known links. The reactive routing protocols (e.g. AODV) [3][4] create and maintain routes only if these are needed, on demand. They usually use distance-vector routing algorithms that keep only information about next hops to adjacent neighbours and costs for paths to all known destinations. Thus, link-state routing algorithms are more reliable, less bandwidth- intensive, but also more complex and compute memory-intensive.

   In on-demand routing protocols a fundamental requirement for connectivity is to discover routes to a node via flooding of request messages. The AODV routing protocol is one of several published reactive routing protocols for mobile ad-hoc networks, and is currently extensively researched.

2. Related Work

The purpose of this work is to modify Ad-hoc On Demand Distance Vector (AODV) Protocol [3][4]. Original AODV uses a static active route lifetime [5][9]. In our proposed protocol we used dynamic route ART [3][5][9] for routing lifetime in AODV.

For calculating ART we consider three parameters:

1. Number of nodes that are involved in data transfer.

2. Node energy.

3. Node speed.

In this paper, we propose to use adaptive route lifetime through a fuzzy logic system. Fuzzy logic[5] was chosen due to the uncertainty associated with node mobility estimation and to the non-linearity and

lack of mathematical models capable of estimating this mobility. A fuzzy set definition (membership functions) and a set of rules (rule-base) have been proposed to design the new method, called fuzzy ART. Although this new method is evaluated with the AODV routing protocol, we believe it can be generalized for application on other on-demand routing protocols as well.

1. Proposed idea-

   1. Route Lifetime Optimization

In designing on-demand ad-hoc routing protocols, four values are used for route lifetime. These are:

1. Route lifetime is equal to 0. This means the route is found when a packet is ready to be transmitted, and kept active during transmission, and deleted at the end of transmission. An example of such a protocol is Associatively Based Routing (ABR) [2]. ABR measures the lifetime of a link using hello messages which are periodically broadcasted.

2. Route lifetime is equal to infinity. This means that from the time the route is discovered, is kept active until the broken link is discovered. Examples of such protocols are Dynamic Source Routing (DSR) [1] and Temporally Ordered Routing Algorithm (TORA) [1][2].

3. Route lifetime is equal to a predetermined static value. This means that from the time the route is discovered, it is kept active up to predetermined amount of time. An example of such a protocols is AODV [6]. In this protocol, ART is set to 3 milliseconds.

4. Route lifetime is equal to an adaptive value. This category is subdivided to two subcategories:

   1. Restricted adaptive lifetime: A parameter affinity which characterizes the strength and stability of a relationship between two nodes. The path with minimum affinity will be used to transmit data between those two nodes. This path will be saved in the routing

      table as long as the affinity is greater than a certain threshold.

   2. Un-restricted adaptive lifetime: The route lifetime is adaptively calculated according to network situation and kept active as long as the route not breaks.

Protocols that use the adaptive route lifetime method found interesting results in minimizing routing delay and traffic overhead. Researchers who designed these protocols used advanced mathematical tools to determine the values of adaptive route lifetime. In this paper, we attempt to simplify these protocols by using the fuzzy logic system.

1. Active Route Timeout AODV (ART-AODV):

   In this section, the concept and rules for ART that will be used with AODV are introduced and the method to design its membership functions is presented.

   1. Efect of path length on ART

      In mobile ad-hoc networks, node mobility causes paths between nodes to break frequently. Although use of more hops may reduce the distance between paths, the increasing number of hops also introduces greater risk of route breakage. When

      Figure 2. Effect of number of stations.

      the number of hops between the source and destination (HopCount) is high, the probability that the path will break because of node movement is also high. The probability of a path break pb can be calculated as:

      Pb = 1 (1 Pl) k

      Where Pl is the probability of a link break and k is a path length.

      Figure 3. Nos. of hop vs. path break probability. Figure shows pb versus HopCount [4] when pl is equal to 0.1, 0.3 and 0.5. It is clear that the probability of a path break increases as the path length increases, terminating the lifetime of the routes containing those paths (the ART time). Based on previous studies, we can state that when HopCount is high, the route lifetime must be low and vice versa. Consequently the following rules are proposed:

      R1: If HopCount is high then ART must be low

      R2: If HopCount is medium then ART must be medium R3: If HopCount is low then ART must be high

   2. Effect of node Velocity on ART

      Ad-hoc networks experience dynamic changes in network topology because of the unrestricted mobility of the nodes in the network. If the end nodes (source and destination) move frequently, then it is highly probable that their path will break.

      Figure 3. Mobility affects connectivity.

      In general, a rule can be defined: when Velocity is high, the route lifetime must be low and vice versa. Consequently the following rules are proposed:

      R4: If speed t is high then ART must be low

      R5: If speed is medium then ART must be medium R6: If speed is low then ART must be high

   3. Effect of node Energy on ART

      The routes lifetime used by nodes of ad-hoc network is highly sensitive to the transmission power of those nodes. Energy is the strength with which the signal is transmitted. In our system, signal power degradation is modelled by the free space propagation model [1][3] which states that the received signal strength is:

      (d)= 2

      R7: If Energy is high then ART must be high

      R8: If Energy is medium then ART must be medium R9: If Energy is low then ART must be low

2. The rule- base for fuzzy ART

To compare between different parameters that effect on ART, we have proposed three methods to design the fuzzy ART [5][9]:

(4)2 2

Where Pr and Pt are the receive and transmit powers (in Watts), Gt and Gr are the transmit and receive antenna gains, d is the transmitter-receiver separation distance, L is a system loss factor (L = 1 in our simulations which indicates no loss in the system hardware), and? Is the carrier wavelength (in meters) which related to the carrier frequency by:

=

Where fc is the carrier frequency (in Hertz) and c is the speed of light (3 × 108 m/s). Assuming a unity gain antenna with a

Figure 4. Transmission range versus transmission power.

900 MHz carrier frequency, Figure 4 shows the relation between the transmission range and the transmission power of a node for different values of the receiver power. Increased Energy means larger transmission range. If the Energy of a node is too low, then its signal will reach to a few neighbours only and its links with those neighbours may be very weak and easy to break. High Energy of a node will lead to high average number of its neighbours and hence increase the lifetime of its routes. Consequently the following rules are proposed:

1. Fuzzy-velocity: In this method the effect of path length and node velocity are considered. To implement this method, the first six previous rules (R1 to R6) can be combined with one 2- dimensional rule-base for controlling the ART adaptively as presented in Table 1.

   HopCount	Node_velocity Low Medium High
   	Active Route Lifetime
   Low Medium High	High	High	Medium
   	High	Medium	Low
   	Medium	Low	Low

   Table 1. Rule-Base for Fuzzy- node_speed

2. Fuzzy-Energy: In this method the effect of path length (rules R1 to R3) and node energy (rules R7 to R9) are combined to design a rule-base shown in Table 2.

   HopCount	Energy Low Medium High
   	Active route life
   Low Medium High	Medium	High	High
   	Low	Medium	High
   	Low	Low	Medium

   Table 2: Rule-Base For Fuzzy-energy

3. Fuzzy-Comb: In this method, previous two methods are combined. So, ART is calculated by tacking the average of ARTs produced by fuzzy- speed and fuzzy-energy methods.

Midpoint is the value of the fuzzy variable, which can be chosen from the real network, simulation and analysis or from the default values of protocol specification as follows. Route breakage probability distribution obtained from random simulation and analysis on route length equal to 3 links, 6 links, 9 links, and 12 links. The results showed that the practical sizes of ad-hoc networks would range around 5 nodes. Hence, for HopCount membership function, midpoint should be equivalent to 5 nodes.

The value of Speed depends on the number of nodes in the network. So, the midpoint can be calculated as:

Midpoint(S) = avg. node_speed × number of nodes

×10.

This value has been observed during a run of ad-hoc network simulator with different sizes of the network. Midpoint of Energy membership function can be the average Energy of the mobile nodes in the network. For example, if the Energy of the nodes is in between 18 kW and 24 kW then midpoint is 21 kW.

Midpoint (E) =total energy/number of nodes The active route timeout ART is as follows:

consists of C++ core methods and uses Tcl and Object Tcl shell as interface allowing the input file (simulation script) to describe the model to simulate. Users can define arbitrary network topologies composed of

Figure 5. Flow of events for a Tcl file run in NS.

nodes, routers, links and shared media. A rich set of protocol objects can then be attached to nodes, usually as agents. It had already become the de facto standard in networking research.

4.2 Performance Metrics

Two metrics were used for measuring performance:

4.2.1 Routing Overhead:

Number of received data by destination

= =0

()

=0

Number of Sent data by source

ART= ()×

1. Simulation Environment

   The proposed scheme is studied via simulation. The simulation is done by NS-2[7]. (Version 2.8).

   4.1 ABOUT NS 2

   Ns-2 is an object-oriented simulator [7][8] developed as part of the VINT project at the University of California in Berkeley. The project is funded by DARPA in collaboration with XEROX Palo Alto Research Centre (PARC) and Lawrence Berkeley National Laboratory (LBNL). Ns-2 is extensively used by the networking research community. It provides substantial support for simulation of TCP, routing, multicast protocols over wired and wireless (local and satellite) networks, etc. The simulator is event-driven and runs in a non-real time fashion. It

   Where n is number of nodes in the network. This metric can be employed to estimate how many transmitted control packets are used for one successful daa packet delivery to determine the efficiency and scalability of the protocol.

   4.2.2 Packet Delivery Rate:

   The PDR is the usual metric used to indicate the performance of A-hoc mobile networks protocol [9]. The PDR[6] of a communication protocol is the ratio between the total number of messages send out and the number of messages that were successfully delivered to their destination .

   = Total messages delivered × 100

   (Total messages sent)

   4.3. Simulation Parameter

   Simulator	NS- 2 Version 2.8
   Network Size	870×870
   No of Nodes	25
   Channel	Channel/Wireless Channel
   Physical Layer	Phy/WirelessPhy
   MAC Layer	Mac/802_11
   Routing Protocol	ART-AODV
   Maximum pkt. In queue	50
   Initial Energy	100 joule
   Mobility model	Random Way point
   Packet type	UDP
   Routing traffic	CBR
   Simulation time	30.0 sec

   Simulator	NS- 2 Version 2.8
   Network Size	870×870
   No of Nodes	25
   Channel	Channel/Wireless Channel
   Physical Layer	Phy/WirelessPhy
   MAC Layer	Mac/802_11
   Routing Protocol	ART-AODV
   Maximum pkt. In queue	50
   Initial Energy	100 joule
   Mobility model	Random Way point
   Packet type	UDP
   Routing traffic	CBR
   Simulation time	30.0 sec

   Proposed routing protocol is being implemented in NS -2 simulator (version 2.8)[7][8] which has been done and the results of the simulations done for the protocols. The simulations were conducted under windows platform using cygwin [2][16]. All the simulation parameter are listed in Table 6.6

   Table 3. Simulation Parameters.

   Metric	AODV	ART-AODV
   Packet Delivery Ratio(PDR)	63.75420006721075 %	43.69565217 3913%
   Over Head	79.7026086956522 bytes/sec	89.13739130 4378 bytes/sec
   No. of packet send	2083 packets	4140 packets
   No. of packet receive	1328 packets	1809 packets

   Metric	AODV	ART-AODV
   Packet Delivery Ratio(PDR)	63.75420006721075 %	43.69565217 3913%
   Over Head	79.7026086956522 bytes/sec	89.13739130 4378 bytes/sec
   No. of packet send	2083 packets	4140 packets
   No. of packet receive	1328 packets	1809 packets

2. Simulation Results and Evaluations

   Table 4. AODV vs. ART-AODV

   Table 4 shows the result packet delivery Ratio (PDR) and Over Head for AODV and ART-AODV. IT shows that PDR is high for AODV and low for ART- AODV. Over Head is low for AODV and High for ART-AODV but number of packet send and receive is larger than AODV.

3. Future Work

   As a future work, the proposed protocol will tested in different mobility model and its performance will be analyzed. This protocol also be compare with protocol like DSR, DSDV, FORP. We also try to improve the performance in respect of packet delivery ratio (PDR) and routing overhead of the proposed scheme.

4. Conclusion

AODV routing protocol is use static route active time

.to make dynamic we modify the proposed ART- AODV protocol with dynamic route active time. From simulation we see that ART-AODV performance not went up to AODV respect of packet delivery ratio and overhead .It may be for random mobility of the nodes. Various simulation experiments were conducted for comparing the proposed scheme with the existing protocol. We also see that it gives same values for small number of nodes (2-5).

REFERENCES

1. Andrew S. Tanenbaum. Computer Networks, 4th Edition. PRENTICE HALL, 2002. P-p [50-250].

2. Akanksha Nigam, "A STUDY OF AD HOC ON DEMAND DISTANCE VECTOR ROUTING PROTOCOL", IJRIM, Volume 1, Issue 2 (June, 2011).

3. Zeki Bilgin, Bilal Khan, "A Dynamic Route Optimization Mechanism for AODV in MANETs", Version 1, (May, 2010).

4. http://www.ietf.org/rfc/rfc3561.txt/[visited 12-6-

   2012].

5. Natsheh, S. Khatun and A. Jantan, Adaptive Fuzzy Route Lifetime for Wireless Ad-hoc Networks, The International Arab Journal of Information Technology, Vol. 3, No. 4, (October 2006).

6. Mubashir Husain Rehmani, Sidney Doria, and Mustapha Reda Senouci, A Tutorial on the Implementation of Ad-hoc On Demand Distance Vector (AODV) Protocol in Network Simulator (NS- 2), Version 1,(28th June 2009).

7. http://elmurod.net/index.php/category/network- simulator-ns2/(visited 2012-02-25).

8. http://www.isi.edu/nsnam/ns/(visited 20-10-2012).

9. Wadhah Al-Mandhari, Koichi Gyoda, Nobuo Nakajima, Ad-hoc On Demand Distance Vector (AODV) Performance Enhancement with Active Route Time-Out parameter, The University of Electro-Communications 1-5-1 Chofugaoka, Chofu- shi, Tokyo 182-8585.