RSAODV : A Route Stability Based Ad Hoc on Demand Distance Vector Routing Protocol for Mobile Ad Hoc Network

International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 DOI : 10.5121/ijwmn.2014.6609 113 RSAODV : A ROUTE STABILITY BASED AD HOC ON DEMAND DISTANCE VECTOR ROUTING PROTOCOL FOR MOBILE AD HOC NETWORK Sanjeev K. Prasad1 and Karamjit Bhatia2 1Ajay Kumar Garg Engg. College, Ghaziabad (India) 2Gurukula Kangri Vishwavidyalaya, Haridwar (India) ABSTRACT High mobility of mobile nodes is one of the major reasons for link failures in mobile ad hoc network (MANET). The present paper aims at proposing modification of well known Ad hoc On demand Distance Vector (AODV) routing protocol for MANET seeking stable route for data transmission and incorporating link break avoidance scheme for such networks. The performance of the proposed routing protocol, named as Route Stability based Ad hoc On demand Distance Vector (RSAODV), is evaluated considering some major performance metrics which include average route life time, throughput, packet delivery fraction, normalized routing load and end–to-end delay. The study is based on simulation runs adopting CBR traffic pattern taking care of node failure scenarios. The performance of RAODV is compared with AODV routing protocol. The simulation runs exhibit significant increase in average route life time, packet delivery fraction and throughput for RSAODV, on the other hand, the normalized routing load and end–to-end delay are reduced for this routing protocol as compared to AODV routing protocol. KEYWORDS: Route Stability, Node Stability, Node Mobility, Node Energy, Traffic Load, Transmission Power. 1. INTRODUCTION In mobile ad hoc network (MANET), mobile nodes are continuously moving from one location to another with a pause-time. Thus, MANET topology can change often and unpredictably. Excessive node mobility may lead to topology changes before network updates can propagate [1]. Many protocols have been proposed for multihop MANET routing to maintain best effort routes. Route stability mainly relies on route lifetime which, in turn, is related to the route length and the lifetime of each link [2]. In large-scale MANETs, the route stability is very important [6]. The hop count of a route may be large. If a route fails, the procedure of route rediscovery results in an increase in control overhead and end-to-end delay. In high-mobility MANETs, the fast changes in topology increase the complexity of routing [10]. Hence, there is a need to construct a route in which each link has long lifetimes. This paper addresses two main problems in routing of CBR traffic in MANETs - route stability and route recoverability. To improve route stability in large-scale and high mobility MANETs, the present work proposes a Route Stability algorithm. In the proposed protocol, a route stability estimation method and a path finding algorithm are developed to find and maintain stable routes for communication services in MANETs. In present work, route estimation relies on the node energy, node mobility, transmission power and traffic load. For the route recoverability in high mobility MANETs, the present work proposes a Link Break Avoidance Scheme. The performance of RSAODV is compared with the well-known Ad-hoc On demand Distance Vector (AODV) International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 114 routing protocol [9]. The simulation runs exhibit significant increase in average route life time, packet delivery fraction and throughput for RSAODV where as normalize routing load and end– to-end delay are decreased for this routing protocol as compared to AODV routing protocol. 2. RELATED WORK In mobile ad hoc network, nodes are continuously moving from one place to another with a pause-time and stability of link/route is an important parameter in such an environment [5]. Route Stability is the quality which asserts the network environment‟s consistency. Many stability based routing algorithms considering different criteria have been proposed in literature for MANETs. The power aware and transmission range route stability schemes are proposed in [3, 4, 16]. In [3], AOSV algorithm for computing link/route stability, initially, every node begins to estimate the stabilities of radio links to its neighbours and for keeping track of the link stabilities between a node and its neighbors, each node periodically broadcasts Hello message (HELLO) including the location of the broadcasting node towards its neighbours. PAMAS routing algorithm [4] is based on minimizing the amount of power required to get a packet from source to destination. This algorithm selects routes with more hops than other routing algorithms. In [16], AODVSR is proposed where a node receives Hello messages and it first calculates its distance from the neighboring node using received HELLO messages. Using this distance information, it evaluates the stability of radio link to the broadcasting neighbour. This information is recorded for estimating stabilities of multi-hop routes in follow-up processes. In path discovery process, source node broadcasts RREQ packet that has new link stability field. The intermediate node rebroadcasts only the RREQ packet with the maximum value for route stability among received RREQs. The location updating route stability schemes are proposed in [11, 17]. In [11], the algorithm works on the stability of the node which is determined by the combination of the speed of the node, the range of the node, the location of the node and the battery power of the node. The main focus of the algorithm is to reduce the number of acknowledgment packets by varying the updating information of less stable nodes more frequently as compared to the more stable nodes. An algorithm presented in [17] enables mobile nodes to implement self-regulated movements in MANETs. This scheme maintains a certain level of network-based stability by harmonizing the node movements autonomously due to their limited transmission range and dynamic topology. The work employed entropy methods for forecasting the future moments of node. The energy aware and traffic load route stability schemes have been presented in [7, 12, 13]. In [7], Tomas Holmberg et. al. estimate the traffic at node level by using the incoming/outgoing packets and introduced traffic estimator that uses two steps in order to predict the traffic over the links in ad hoc networks. In [12], EA-DYMO considers both the traffic load and energy aware path for route stability. The work modifies the route selection procedure of DYMO [22] by taking ratio of the energy factor and the average traffic load for each path. In [13], author has designed a variable range energy aware dynamic source routing in which the route selection is based on energy, stability and traffic load. It selects two routesmain and alternate. The network depended route stability schemes are discussed in [14, 15]. Both schemes modify the AODV path discovery phase for finding stable route. In [14], Tamanna et. al. proposed the concept of “moving average” to calculate the neighbor stability. In their work each node calculates the stability of its neighboring nodes considering both old stability and current stability values. The old stability means the stability a node has encountered in the previous stability calculation. Stability calculation is triggered by a timer which expires after a constant interval periodically. In [15], the authors presented a scheme (VON scheme) that depends on the velocity and the traffic load of the nodes to determine the nodes involved in rebroadcast to build a stable International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 115 route. This scheme divides the nodes into high speed nodes and low speed nodes. High speed nodes do not participate in the route discovery phase as they produce unstable routes. The weight-based stable routing scheme is presented in [2, 18]. In [2], a Stable Weight-Based On-Demand Routing Protocol (SWORP) for MANETs is proposed in which the weight of a route is decided by three factors: the route expiration time, the error count, and the hop count. The route discovery mechanism finds multiple routes from the source node to the destination node. The algorithm selects the path with the largest weight value for routing. In [18], a Link lifetime based Backup Routing (LBR) a modified version of SWORP is reported. LBR also selects the multiple paths with the largest weight value for routing but it keeps the remaining routes as a backup route. 3. PROPOSED MODEL FOR RSAODV ROUTING PROTOCOL The proposed model aims at improving the well known AODV routing protocol. The new protocol is named as RSAODV routing protocol. The aim of RSAODV is to provide a more stable route with avoidance of route break for mobile ad hoc networks. In this scheme, route stability is estimated by the stability of node which depends on node energy, node mobility, transmission power and traffic load. These four major processes are employed to find and maintain the most stable route from source to destination. The mechanism of the proposed RSAODV routing protocol is shown in Fig. 1. The abbreviation used in model are : RSV – Route Stability Value, NSV – Node Stability Value, UN –Upstream Node, DN – Downstream Node, RT – Routing Table, RM – Route Maintenance, RD – Route Discovery, RREQ packet– Route REQuest packet, RREP packet – Route REPly packet, RM – Route Maintenance, RD – Route Discovery. 3.1 Route Stability Estimation In order to allow more stable routes for data transmission in MANETs, we hereby propose to include a new field, called route stability (RS) field, which is a measure of the stability of the route, in the RREQ packet, the routing table and the HELLO packet of AODV routing protocol. International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 116 Figure 1. The Mechanism of the Proposed RSAODV Routing Protocol. In a network, each node periodically broadcasts HELLO message with node stability value. When a node receives HELLO message it checks node stability value of received HELLO packet and if it is larger than the threshold value then the node adds the sender of the HELLO packet as its neighbor node. To determine route stability of the path the source node invokes route discovery process. The proposed model includes following steps for stable route discovery: 1) The source node adds node stability value (NSV) in RS field of RREQ packet and sends it to the neighbor nodes (which may be an intermediate node in the final route). 2) Neighbor node compares its own NSV with received RREQ packet route stability value (RSV). The lowest value is selected i.e. if NSV < RSV then RSV  NSV in RREQ packet. Forward RREQ packet to the neighbors and so on. This ensures lowest NSV to be the route stability value of the path being discovered. 3) If destination node receives more than one RREQ packet then it sends an RREP packet in response to the RREQ packet with the largest Route Stability value to the source node. The algorithm 1 shows the determination of minimum Route Stability Value of the path. Algorithm 1: RS_Value(SN, RN) {//SN sending node and RN receiving node If ( NSV[SN] < NSV[RN] ) Update NSV[SN] in RREQ packet. } International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 117 Based on the above scheme, the route stability RS(p) of path is equal to the lowest node stability value NS(n) of the node in a path and is exceeding a threshold value ω. RS(p) is given by following expression: RS(p) = MIN ( NS(SourceNode), .., NS(IntermediateNode), …, NS(DestinationNode)) where RS(p) > ω, the selecting value for route stability. 3.2 Node Stability Estimation In our method, the estimation of the node stability NS(n), of a node n, is considered to be based on four different processes e.g. Energy Level (EL), Mobility of Node (MN), Transmission Power (TP) and Traffic Load (TL). In our scheme, nodes periodically calculate NS value and transmit it through HELLO message. If any node receives larger NSV than predefined threshold value β from some node (say x), it adds node x as its neighbor node. The proposed simple linear equation for node stability NSn of a node n is given by the following expression: NS(n)= a*EL + b*MN + c*TP + d*TL where NS(n) > β β is the minimum node stability value for the route and a, b, c, and d are weighing factors for the corresponding network parameters. All four parameters, with values ranging from 0 to 1, are chosen so that a + b + c + d = 1. These values are kept flexible so that they can be changed as per the network scenario. For example, when the network traffic is very high „d‟ can be given more weight than the other three. Similarly, in a high mobility network, the weight „b‟ dominates the other factors. In the computation of NS(n) above, the EL is energy level of node. When energy of each intermediate node is empty, it is impossible to communicate and link break occur. The MN is the mobility of node that holds the current speed of node. MN implies node stability and hence the stability of route. The TP is the transmission power and used in order to elect the node which can cover the largest range. The TL is traffic load on a node. Nodes, such as intermediate nodes, are engaged with other jobs. Our method also incorporates the provision to avoid such type of nodes at the time of making path. 3.2.1. Energy Model In our energy model, the Energy Level EL of a node n refers to the available energy EA of a node n which depends on total initial energy and consumed energy [12]. Available energy of node n is given by the following expression: EA(n)= TE(n) – EC(n) where EA(n) > ε, the threshold energy level for a node. TE(n) is the total initial energy of node n and EC(n) is the consumed energy of node n. The energy consumed EC(n) depends on transmitting (Etransmit) and receiving (Ereceived) one packet is given by following expression : EC(n) = Etransmit (n) + Erecieved (n) The energy dissipated in transmitting (Etransmit) and receiving (Ereceived) in one packet and is calculated as follows [13] : Etransmit (n) = Ptransmit (n) × TD Erecieved (n) = Preceived (n) × TD International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 118 where, Ptransmit is a transmitting power of one packet, Preceived is a receiving power of one packet and TD denotes the transmission duration of the received/transmit packets at node. In our proposed scheme, the algorithm chooses only those nodes in a route that have higher energy than threshold value ε. 3.2.2. Node Mobility Factor Deciding Model In a dynamic network such as MANET, the mobility of nodes can not be ignored. It has a vital role in maintaining a stable route. Thus, we consider mobility or average displacement of node to be the deciding factor for route setup so that a better route stability can be achieved. In our proposed scheme we adopt the policy given in [19], where a node with lower average displacement has a higher chance of being an intermediate node. The weights assigned to the nodes are reciprocal to their respective displacements. i.e. a node with lower average displacement is assigned a higher weight and the node with higher value is assigned a lower weight. Basically, we consider the mobility of a node by taking the average of the distances covered by mobile node in a given time slot. We measure the mobility of node MNT(n) as an average speed S(n) of node in time duration T. Thus, mobility MNT(n) of node n in time slot T (consisting of N sub slots) is given by the following expression: T (n)S =(n)MN N =i i Δt T1 where, MNT(n) < α, the threshold mobility value for a node. S(n) is the distance D(n) covered by node n in time interval ∆t. Thus speed of node is given by the following expression : t nD nS t t)( )( where, the distance covered by node n in time slot ∆t (i. e. from time t-1 to time t) from position Pt-1 (x, y) to Pt ( x, y) is given by the following expression : 2 1 2 1 ()y(n)(y(n)+)x(n)x(n)=(n)D ttttΔt 3.2.3. Transmission Power Model The transmission power TP is used to elect the node which can cover the largest range. In a dynamic network the transmission power plays a vital role in maintaining the stable route and hence ad-hoc routing protocols must give due emphasis on the radio propagation model for effect on signal strength. The effect not only leads to the average signal power decreasing with the propagation distance but also yields large fluctuation of signal strength in a short range [3], i.e., small-scale fading, or in a medium range, i.e., shadowing. These may result in an unstable link between any two moving nodes even with a short propagation distance. We have used two-ray ground reflection model [21] for the calculation of transmission power of a node. This model considers both the direct path and a ground reflection path for this purpose. In this model the transmission power TP is calculated from the received power Pr at distance d and is predicted by : International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 119 Ld hhGGP =dP rtrtt r4 22 where, Pt is the transmitted signal power, Gt and Gr are the antenna gains of the transmitter and the receiver respectively and L (L ≥ 1) is the system loss. It is common to select Gt = Gr = 1 and L = 1 in ns simulations. ht and hr are the heights of the transmit and receive antennas respectively and dn is the distance between two nodes. We have taken n=2 for short distance and n=4 long distance in our study. The two-ray model does not give a good result for a short distance due to the oscillation caused by the constructive and destructive combination of the two rays [20]. Therefore, a cross-over distance dc is calculated in this model. So dc can be calculated as : rt c hh d4 where, λ is wavelength of signal. In our scheme if node receiving signal power Pr(d) < ρ, the threshold value for node signal power, the proposed routing algorithm will not select this node for routing. 3.2.4. Traffic Load Estimation Model Traffic Load for a node is defined as the measure of total cost incurred in sending/receiving packets by a node. If the time-arrival between sending/receiving two packets is ∆T seconds and the size of packet is ∆L bits, then the traffic load TL(n) of node n is given by the equation [8] : T L nTL)( In the present work, we have assumed that in the network, each mobile node sends messages to any other node with a uniform rate. 3.3. Route Discovery Route discovery is a process that executes the algorithm 2 to discover the stable route for a requesting source and destination pair. We propose to introduce a new field Route Stability (RS) in RREQ packet which indicates route stability value of a path from source to particular node. In this process, when network initiates all the nodes are assigned a similar high node stability value (NSV). Algorithm 2: Route_Discovery Step1: The source node S initiates a route discovery process by broadcasting a Route Request (RREQ) packet to all its neighboring nodes. RREQ packet contains the NSV of S. If ( NSV[S] > β ) then Broadcast RREQ packet to neighbors with NSV(s). Else Not able to generate RREQ packet. Step 2: Neighboring node N receives RREQ packet. N may be an intermediate node or a destination node. International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 120 If ( NSV[N] > β ) then //This is a new RREQ packet { If ( N is an intermediate node ) then // here N is RN node { N calculates the RSV form RS_Value(S, N). // Algorithm 1 Update RSV field in routing table, update RS field in RREQ packet and forward it to all neighboring nodes of N. If ( N receives other RREQ packets for same sequence number from some other sending node(s) ) then Discard these RREQ packets. } Else //N is a destination node. If ( N receives multiple RREQ packets within a time window, which starts from the first arrival of RREQ ) then N picks the largest RSV of RREQs. //Destination will select highest RSV from RREQ packets from among all received RREQ packets. If ( RSV[N] > ω ) then N sends back reply packet as a RREP to the source node S. Else N discards the RREP packet. } Else N discards the RREQ packet In our model, nodes with NSV greater than threshold value β can become the part of active route. Further, the threshold mobility value α of a node has also been considered in the proposed method. This confirms that all the nodes in the active route have sufficient processing power, manageable traffic load and mobility. This implies that all such nodes can‟t fail too soon resulting in a more stable route. 3.4. Route Maintenance After the stable route is discovered, the source node starts transferring data packets to destination node and periodically checks the stability of the route discovered. At the destination node, the best stability of the discovered route is obtained from received RSVs. During data transmission via stable route, if any intermediate node becomes an unstable node (a node having its NSV less than a predefined threshold value) at some instance of time, or a link/route breakage is detected along this route, the intermediate node informs upstream node which initiates a local route discovery process. If upstream node is unable to find new route, it sends rerouting request (RERREQ) packet back to the source node which then initiates a new route discovery process in order to discover another route to replace the earlier discovered one. 3.4.1. Link Breaking Avoidance Algorithm For the route recoverability, we propose the Link Breaking Avoidance Scheme. In this scheme, each node periodically calculates its NSV and transmits it to its neighbors through hello packets to check the stability of the connecting route. During the transmission of data packets, if any intermediate node‟s NSV is less than the threshold value β then intermediate node IN informs International Journal of Wireless & Mobile Networks (IJWMN) Vol. 6, No. 6, December 2014 121 upstream node UN through unstable node detection (UND) packet. UN then reinitiates the route discovery process. In our route maintenance scheme, we introduce Unstable Node Detection (UND) packet, which is send by the unstable (intermediate) node to its UN, for removal of unstable node. This UND packet contains the sender node address, upstream node (UN) address, downstream node (DN) address, source node address and destination node address. Algorithm 3: Local_Route_Maintenance Step 1: If ( IN.NSV < β ) then IN informs next immediate UN through UND packet. Step 2: If ( UN.NSV < β ) then UN declares ROUTE ERROR, UN sends RERR packet to source node & destination. Source node reinitiates route discovery process. else //UN checks own neighbor table. If ( destination node is the neighbor node of UN ) then UN removes IN from the existing path and updates the path. UN forwards the all data packets to this updated path. else UN initiates the route discovery process to the DN. 4. PERFORMANCE EVALUATION The performance of proposed RSAODV protocol is evaluated using simulation tool NS-2.35 [20] and is compared with AODV routing protocol. The performance evaluation is done on the basis of following performance parameters : Packet delivery fraction: The ratio of the number of the successful arrived packets to the number of all packets transmitted by source. The larger value indicates that the more data packets are successfully delivered to destination. End-to-end delay: The average time spent on data packet transmission from source to destination, including all possible types of delay during the transmission. Normalized routing load: The normalized routing load is measured by the total number of routing packets sent divided by the number of routing packets delivered successfully. Throughput: The throughput is defined as the total amount of data a receiver receives from the sender divided by the time it takes for the receiver to get the last packet. The throughput is measured in bits per second (bit/s or bps). Route lifetime: The route lifetime is defined as the average time elapsed from route establishment to route failure. 4.1. Performance Evaluation and Result Discussion The performance of RSAODV is evaluated through simulation using NS-2.35 [20]. The simulation network area is considered as 1000m × 1000m with 100 nodes in each simulation run