INT J COMPUT COMMUN, ISSN 1841-9836 8(6):891-900, December, 2013. RSEA-AODV: Route Stability and Energy Aware Routing for Mobile Ad Hoc Networks P. Srinivasan, P. Kamalakkannan P. Srinivasan* Mahendra Institute of Technology, Namakkal Tamil Nadu, India *Corresponding author: salemsrini4u@gmail.com Dr. P. Kamalakkannan Department of Computer Science, Government Arts College, Salem Tamil Nadu, India Abstract: Frequent changes in network topology, confined battery capacity of nodes and unreliable nature of wireless channels are the main challenges for reliable routing in Mobile Ad hoc Network (MANET). Selecting a long lasting route is a critical task in MANET. In this paper, we propose a new protocol, Route Stability and Energy Aware Ad hoc On-demand Distance Vector (RSEA-AODV) protocol which is an enhancement of Ad hoc On-demand Distance Vector (AODV) protocol. It designs a bi-objective optimization formulation to compute the reliability factor based on stability and residual energy of nodes. The route with the highest reliability factor value is selected for data transmission. This protocol is compared with other similar routing protocols: PERRA and AODV. We use ns-2 for simulation. Our simulation results show that, the proposed protocol increases the node expiration time by 12 - 32 % and accomplishes 7 - 13 % higher packet delivery ratio compared to PERRA or AODV. The packet delay and control overhead of the proposed protocol is comparable to that of AODV. Keywords: MANET, reliable routing, route stability, biobjective optimization. 1 Introduction Mobile ad hoc networks (MANET) are groups of wireless mobile devices, which can com- municate with each other without any infrastructure support. It is a self-configured and self- maintained network with no central authority. Every node in MANET acts as both a host and a router. Dynamic topology, limited bandwidth, battery, CPU resources and multi-hop communication are the characteristics that put special challenges in routing protocol design. Several routing protocols have been proposed for MANETs. Based on the route discovery principle, we can classify them into either proactive or reactive. Proactive routing protocols update routes for every pair of nodes at regular intervals irrespective of their requirement. The reactive or on-demand routing protocols, determine route only when there is a need to transmit a data packet, using a broadcasting query-reply (RREQ-RREP) procedure. Most of these protocols use min-hop as the route selection metric and found that the routes discovered by these protocols are not stable. The stability based routing protocols [1]- [4] are designed to choose stable route passing through stable links. These protocols improve route lifetimes and packet delivery ratio compare to the shortest path routing protocols. The energy-aware routing protocols [5, 6] are designed considering factors like residual energy, total transmission power or both. These protocols avoid over using of certain nodes and reduce total energy consumptions. But, there exist a very few protocols in the literature [6] - [8] that consider both stability and energy metric during route discovery and maintenance. Copyright © 2006-2013 by CCC Publications 892 P. Srinivasan, P. Kamalakkannan In this paper, our objective is to design a routing scheme based on route stability and residual energy metrics during route discovery and maintenance. This scheme compute the link stability based on measurement of received signal strength of successive packets and route stability is computed as the product of link stability of all links that make up the route. This scheme allows nodes that satisfy required energy metric to act as intermediate nodes. 2 Related Work AODV [9] a reactive routing protocol establish a route to a destination only on demand.. The advantage of AODV is reduced control overhead. But, multiple RREP packets in response to a single RREQ packet can lead to heavy control overhead. Presence of stale routes and unnecessary bandwidth consumption due to periodic beaconing are the drawbacks of AODV. Link stability is a measure of how stable the link is and how long it will last. Signal strength, pilot signals, link duration distributions, residual energy of the nodes and relative speed between nodes are the parameters used for the computation of link stability. Stability based routing protocols use link stability factor and path stability factor calculated using the above specified parameters to select stable path for data transmission. The lifetime of a network is one of the important factors to be considered in designing a MANET routing protocol. Maximizing the network lifetime by minimizing the power consump- tion for the data transfer is the main aim of Energy aware routing protocols [5]. Optimizations carried out in these protocols are classified in the following schemes. (i) Minimize the total energy consumed along the route (ii) Avoid using node with minimum residual energy and (iii) Minimize the total battery cost along the route. They reduce the energy wastage ensuing from retransmission due to bit error rate, frame error rate and link failures due to energy depletion. In [4], the authors propose Route Stability based QoS Routing (RSQR) where they use the received signal strength of the packets to calculate link stability and route stability. It considerably reduces the number of route breakages by restricting traffic admission. However, the above described protocols do not consider energy metrics during route discovery. In [7], the authors propose Link-Stability and Energy Aware Routing protocol (LAER). It considers joint metric of link stability and energy drain rate into route discovery. It balances the traffic load on the nodes and considerably decreases the control overhead. However, LAER does not able to discriminate between links of the same age. In [8], the authors propose Power Efficient Reliable Routing Protocol for Ad Hoc networks (PERRA), a reactive routing protocol, which accounts for both link stability and power efficiency on route discovery. It considerably reduces control overhead by constrained flooding of route requests. However, PERRA does not able to discriminate longer link from lifetime point of view as it does not consider link lifetime and its statistical behavior. 3 Route Stability and Energy Aware (RSEA) Model 3.1 Stability Aware Metric RSEA model considers signal strengths and mobility for computing the probability of link failures. It computes link stability (LS) using signal strength values receivd from the MAC layer. Any link e has an associated link stability LS(e) [4] and it is given by LSi,j = u2 − DSSi,j u2 − u1 (1) RSEA-AODV: Route Stability and Energy Aware Routing for Mobile Ad Hoc Networks 893 where DSS is the differentiated signal strength to decide whether the signals are getting stronger or weaker. It is computed as follows. DSSi,j = SScuri,j − SSnewi,j (2) A path between source s and destination d is given as P(s, d) = (s, e(s, x),x, e(x, y),y, ... , e(z, d), d). Formally, a path between two nodes s and d is a set of all feasible path between them and can be represented as P(s, d) = P0, P1, . . . , Pn, where each Pi is a feasible path between s and d. We define the stability of the path P, by the product of link stability of its edges as follows Stability(P) = ∏ e∈P LS(e) (3) The path with higher path stability value contains more stable links and choosing it will consid- erably reduce the probability of link failure. 3.2 Energy Aware Metric It is assumed that all wireless nodes come with residual power detection device. The energy required to transmit a packet (Etx) [8] can be computed as Etx = Psize ∗ Ptx BW (4) where Psize is the packet size, Ptx is the packet transmitting power and BW is the bandwidth of the link. The transmitting energy is directly proportional to the distance between nodes. The source application layer communicates n value to the network layer, for selecting nodes that meet the energy requirement. It avoids link breakages due to energy depletion. The total energy required (REQe) for data packet transmission is given by REQe = n ∗ (Etx + Eproc) (5) where Eproc is the energy required for packet processing and n is the number of packet . The energy metric (EM) of the path is given by EM(P) = n∏ i=1 ( Ri Fi ) (6) where Ri(t) is remaining battery capacity and Fi is full battery capacity of intermediate node i, at time t. The goal of this metric is to maximize EM. It takes the product of the residual battery of the intermediate nodes to select a path that has nodes with maximum residual energy among the path that just meet the basic energy requirement REQe. 3.3 Problem Formulation The problem can be stated as, ‘To find a reliable path for data communication based on route stability and residual energy metrics’. The above bi-objective optimization problem can be transformed into a single objective problem, by providing importance factor (i.e. W1 and W2) for each criterion of the objective. We combine the objectives into a single objective function to calculate the Reliability Factor (RF) of the path P, can be mathematically stated as RF(P) = W1 · Stability(P) + W2 · EM(P) (7) 894 P. Srinivasan, P. Kamalakkannan where the parameters w1 and w2 are chosen based on the network dynamics and application requirements. In this study, in order to give equal importance to both stability and energy metrics, we assign 0.5 to both W1 and W2, such that W1+ W2=1 condition is satisfied. Consequently, the sum of the objectives has to be maximized and Maximum Reliability Factor (MRF) can be computed by MRF = max(RF(P1),RF(P2)...,RF(Pn)) (8) The path with MRF value is selected as a reliable path for data transmission. 4 Route Stability and Energy Aware (RSEA) routing in MANET 4.1 Route Discovery When a node S needs to send packets to a destination D, it searches for the route in its route table. If a route to the destination D is not available, then the source S will broadcast a route request (RREQ) message to its neighbors. The RREQ of RSEA-AODV is an extension of a RREQ packet of AODV routing protocol. Three new fields Accumulated Path Stability (APS), Accumulated Energy Metric (AEM) and required energy (REQe) are added to the RREQ Packet. It initializes the values to the added fields as follows: APS, AEM with 1. The required energy is calculated using equation 5 and is initialized to REQe field. 4.2 Route Discovery at Intermediate Nodes If the strength of the RREQ packet is poor, then it drops the RREQ. Then node i checks whether its residual energy will meet the required energy REQe specified in the RREQ packet. If the above conditions are satisfied, then node i make a reverse route entry in the Routing Table (RT). Then it calculates LS. If the signal strength is above SThr1, then it assigns 1 to LS. It implies that nodes are close and link is sufficiently stable. Otherwise, it calculates LS using equation 1. Energy metric is calculated using equation 6. After these steps, it updates the APS and AEM fields such that the updated values contain the route stability and energy metric of the explored route up to the current node. It enters the relevant information from RREQ into Route Request Forward Table (RFT). Then, Node i broadcast the RREQ to its neighbor. In case of duplicate packet, if it contains better values for APS or AEM, then it makes an entry in RFT and discards the packet. On receiving a RREP packet, node i measures the strength of RREP. If its strength is poor, then it will drop the RREP packet. It looks up RFT for the corresponding RREQ entries, to select the node with the highest RF value. It forwards the RREP packet to the node with the highest RF value. It is shown in Algorithm 2. It makes an entry in the RT. 4.3 Route Selection at Destination Destination node will receive RREQ packets from different possible routes. On receiving the first RREQ packet, the node D starts a timer t1 for the duration of Route Reply Latency (RRL) time. It stores all the RREQ that arrives, in its routing table. It computes RF value for the path explored by the RREQ. If destination node receive more than one RREQ before the timer t1 expires, then it forwards the RREP packet to the node with the highest RF value. It is shown in Algorithm 3. This considerably reduces the amount of control overhead incurred during the route establishment due to multiple RREP for single RREQ as in AODV. The Destination node makes an FT entry for the flow. In case, if it does not receive any data packets within the timeout period, then it will delete the respective entry from the FT table. RSEA-AODV: Route Stability and Energy Aware Routing for Mobile Ad Hoc Networks 895 896 P. Srinivasan, P. Kamalakkannan 4.4 Route Maintenance In dynamic mobile ad-hoc networks, link-breaks occur frequently. RSEA-AODV comes with make-before-break route maintenance mechanism. This mechanism quickly adapt to the link breakage likely to occur due to the mobility and energy drain. It is depicted in Algorithm 4. It executes the mechanism after every t2 seconds, to monitor the status of the route established. If an intermediate node is in the critical battery status or it is receiving weaker signal packets, then it creates an HLP message with Time To Live (TTL) set to 1 and broadcasts it to its neighbors. Neighbors on receiving the HLP packet, check for route availability in its routing table for the destination specified in the HLP packet. If the route is available, then it returns the route to the downstream node of the node broadcasting the HLP packet. The downstream node on receiving the route it updates its routing table. It routes the data packets in the new route available, preventing packet losses due to link breakage. If the node with critical battery is the destination node, then it will send the stop traffic intimation to the source node, to avoid future packet drops and wastage of resources. If there is no alternate route available with the one-hop neighbors, then after the expiry of timer i.e. timeout, the node will send the Route Change Request (RCR) to the source node. The source node on receiving the RCR will go for the re-route discovery to the destination. RSEA-AODV: Route Stability and Energy Aware Routing for Mobile Ad Hoc Networks 897 4.5 Simulation Parameters We have simulated a scenario of 50 mobile nodes in a rectangualr toplpogy of 1000m * 500m, with each node having a transmission range of 250m. The values of SThr1 and SThr2 are set to 1.5 * RxThr and 1.2 * RxThr, respectively. We simulate it in NS2 2.31.The simulation has been run for 600 seconds. The results show 95% confidence interval on all observed metrics. The first experiment evaluated the overall performance of RSEA-AODV, PERRA and AODV. During simulation, we generated 12 CBR connections producing 3 packets /second. Table 1: Simulation Results Parameters RSEA-AODV PERRA AODV PDR 96.42 90.54 86.29 COH 0.8342 1.0871 1.1956 Delay(sec) 0.0698 0.0732 0.0659 Table 1 presents the results of the simulations. We observe that the PDR of RSEA-AODV is improved by 6.5% and 13.2 % relative to PERRA and AODV, respectively. This is because of node selection and, route maintenance strategy carried on by the RSEA-AODV. It chooses the intermediate nodes considering the stability and residual energy issues. In case of AODV, it chooses a path with the shortest route. It may contain low energy nodes which lead to disconnections of sessions. The control overhead of RSEA-AODV is reduced by 22 % and 30.2% relative to PERRA and AODV, respectively. This is due to reduction in path reconstruction and constrained flooding of control packets. As RSEA-AODV selects the most reliable path, it considerably reduces the total number of required messages for route reconstruction. The packet delay for RSEA-AODV is comparable to AODV and PERRA. This is due to following opposing factors. (i) Finding a reliable route, considering the stability and energy metrics, increases the delay on the one hand. (ii) On the other hand, route selection and route maintenance procedure of RSEA-AODV increases the lifetime of the routes and the bottle-neck nodes. It significantly reduces the need for packet retransmissions. Figure 1: Node ExpirationTime Figure 2: Connection Expiration Time The plots of NET and CET are presented in Figures 1 and 2. It is observed that RSEA- AODV extends the node lifetime by between 12%-24% over PERRA and by between 20%-32% over AODV. This is because of RSEA-AODVs route maintenance mechanism, in which nodes stop transmitting data traffic if they are about to drain and find an alternate route. AODV exhibits 898 P. Srinivasan, P. Kamalakkannan the worst performance in terms of the nodes expiration time because intermediate nodes continue packet forwarding regardless of the remaining battery until battery depletion. AODV exhibits a longer lifetime of connections despite a shorter lifetime of nodes. It is noted that, AODVs connection expiration times being anywhere between 25%-5% better than RSEA-AODV or PERRA. This is because, in RSEA-AODV: (i) a source node tries for route reestablishment only fixed number of times after route change request or link failures, and (ii) Nodes reject request for new session once their residual energy is below energy threshold. But AODV keeps retrying and so has a higher chance of finding an alternate route and keeps con- nection alive for a longer time. Figure 3: Average number of path reconstructions Figure 3 shows the number of path reconstructions due to node mobility and energy shortages. RSEA-AODV chooses the more reliable route and thus, reduces the need for route reconstruc- tions. In addition, it decreases the control overhead and offers some energy benefits. The route discovery and maintenance mechanism carried on by PERRA considerably reduced the number of route reconstructions compared to AODV. In the second experiment, the stability weight (w1) was provided with the values 0.1, 0.3, 0.5, 0.7 and 0.9 (lowest to highest) and performance of the protocols are observed. The nodes moved at the maximum speed of 5 meters / second. From Figure 4, it is observed the packet delivery ratio of RSEA-AODV was higher than that of PERRA and AODV. It is because it uses more stable routes and presence of enhanced route maintenance mechanism. PERRA showed comparatively better performance than AODV, due to its route discovery mechanism and main- tenance of alternative route. As AODV does not discriminate the link in stability issue, it does not show any deviation. The variance of residual node energy is depicted in Figures 5. This parameter shows the load balancing capability of the protocols. It is noted that as stability weight factor increases, there is an increase in energy variance. As AODV overloads certain nodes and shows a big variance between remaining energies of the node. Figure 6 shows that there is a gradual increase in the hop count as stability weight increases in both RSEA-AODV and PERRA. The increase in hop count is due to the selection of short and stable link as the stability weight increases. The average physical length of the hops chosen by RSEA-AODV is 45-55% of the transmission range. It is 50-60% in the case of PERRA and 55-65% in the case of AODV. The third experiment measured the average residual energy of the nodes on the chosen path. RSEA-AODV: Route Stability and Energy Aware Routing for Mobile Ad Hoc Networks 899 Figure 4: Packet delivery ratio vs. Stability Figure 5: Residual energy vs Stability Figure 6: Hop count vs. Stability Figure 7: Residual energy vs. Energy The average residual energy of nodes was set at 30 [J] and with some randomness as in [8] REe = E[REe] ± γ (9) where E[REe] is the residual energy. 10 - 50 % randomness in the residual energy for the nodes was provided in this simulation. For example, in the case of 10 % randomness, each node had 27 - 33 [J] residual energy. The sources energy requirement was 30J. Figures 7 depicts the average energy of the nodes on the chosen path by the protocols. It is noted that RSEA always had higher residual energy compared to PERRA and AODV protocols. This was due to the consideration of nodes residual energy during route selection. But, AODV showed lower residual energy as it goes for the shortest path selection and does not consider residual energy during route discovery. 5 Conclusions and Future Work In this paper, we proposed a new Route Stability and Energy Aware routing scheme. It establishes route based on the joint metric of link stability and residual energy. During the route discovery process, it constructs the route with nodes that satisfy the sources energy requirement. Among the possible routes, RSEA selects the route with the highest reliability factor for data 900 P. Srinivasan, P. Kamalakkannan transmission. This scheme can be incorporated in any of the existing MANET routing protocols. Using the ns2 simulator, we compared the performance of RSEA-AODV with PERRA and AODV. The simulation results highlight that RSEA-AODV was outstanding in terms of node expiration time, delivery ratio and path reconstruction overhead. We intend to evaluate the performance of the protocol under different node densities and traffic loads, as part of our future work. Bibliography [1] Abid, M.; Belghith, A. (2011); Stability routing with constrained path length for improved routability in dynamic MANETs, Personal and Ubiquitous Computing, 15: 799-810. [2] Hui, Z.; Ning, D.Y. (2007); A novel path stability computation model for wireless ad hoc networks, IEEE Signal Process. Letter, 14: 799-810. [3] Sarma, N.; Sukumar Nandi. (2010); Multipath QoS Routing with Route Stability for Mobile Ad Hoc Networks, IETE Technical Review, 27: 380-397. [4] Nandi, S.; Sarma, N. (2009); Route Stability Based QoS Routing in Mobile Ad Hoc Networks. Wireless Pers. Commun, Springer, 54: 203-224. [5] Tan, W.C.W.; Bose, S.K. (2012); Power and mobility aware routing in wireless ad hoc net- work. Commun, IET, 6: 1425-1437. [6] Lee, S.; Park. (2008); A routing protocol for Extent Network Lifetime through the Residual Battery and Link Stability in MANET, in Proc. ACC 08, 199-204. [7] Rango, F. De.; Fazio, P.; (2012); Link Stability and Energy Aware Routing Protocol in Distributed Wireless Networks, IEEE Trans. on Parallel and Distributed systems, 23: 713- 726. [8] Kim, K.J.; Sang, Y. (2005); Power-Efficient Reliable Routing Protocol for Mobile Ad hoc Networks, IEICE Trans. on Commun., 88: 4588-4597. [9] Perkins, C.E.; Royer , E.M.; and Das, S.R. (2003); Ad hoc on-demand distance vector (AODV) routing, IETF RFC 3561.