Modifying AODV to Reduce Load in MANETs

Published Online October 2016 in MECS DOI: 10.5815/ijmecs.2016.10.04

Wireless sensor network are increasingly finding popularity in many scientific and remote monitoring applications related to military ecological health and industrial processes. A wireless sensor network (WSN) is defined in [1] as:

“A sensor network is a deployment of massive numbers of small, inexpensive, self-powered devices that can sense, compute, and communicate with other devices for the purpose of gathering local information to make global decisions about a physical environment”

Due to certain special characteristics of the devices and network routing in WSN has always been a challenge and an active area of research. A related area of research is routing methods for mobile ad-hoc networks (MANETs) [2]. MANETs and WSN share some common features like

• •    Small battery operated devices as nodes

• •   Dynamic Topology

• •    Communication issues

• •   Wireless Communication

Yet, MANETs are different in following aspects

• •    Distributed operation

• •   Autonomous nodes

• •   Multihop Routing

Due to these differences, the routing of WSN cannot be adopted directly for MANETs the of routing in MANETs is to

• •    Provide scalability – Because size of network may vary from time to time. Limited bandwidth and limited resources of nodes present a challenge here.

• •    Ensure Quality of Service (QoS) in terms of high Packet Delivery Ratio, low end to end delay, low routing overhead etc.

• •    Provide energy efficiency since the nodes have limited energy.

• •    Provide a link repair mechanism because the links are prone to failures.

• •    Provide dynamic route setup due to ever changing topology and each node can play role of host and router.

Mostly all features are provided by AODV routing protocol [3] making it popular in MANETs.

AODV is a reactive routing protocol which involves primitives for both route discovery and route maintenance.

Still AODV can be further improved to have better QoS. It establishes routes as per requirement and has enough flexibility to be adopted as per desired QoS of applications. Lee et al in [4] address the problem of breakage of links for a continuous data- packet delivery and propose a Backup routing in ad hoc networks (AODV-BR) protocol. All protocols proposed using AODV direction were either reactive or pro-active. The reactive protocol finds a route on demand and floods the network with Route Request Packets (RREP). The proactive routing protocol, on the other hand, distributes the routing tables throughout the network to maintain fresh lists of destinations and their routes. A variation to both the protocols was proposed by Dargahi et al in [5] who then brought about a combination of pro-active and reactive dynamic routing protocol in their proposed SemiProactive AODV (SP-AODV) protocol. In 2010, Jiang and Hao [6] proposed an Improved AODV for ad hoc network. The simulation is done through NS-2 and optimizations in the optimized hello mechanism, local repair mechanism and single route in AODV is done. A different approach to routing was proposed by Nishat et al in [7] who designed the Reverse AODV (RAODV). This proposed approach involves the use of reverse RREQs for finding the source node. The advantages of the proposal are robust performance and reduced use of path failure correction messages. Goswami et al [8] analyzed the behavior of AODV and Destination Sequence Distance Vector (DSDV) over frequent changes node density and network topology. Comprehensive analysis of AODV, DSDV and Dynamic Source Routing (DSR) has been studied through simulation in NS-2 by Mahmood et al [9]. The results reflect that AODV might perform poorer in certain situations; hence, there is a scope of improvement in the basic AODV protocol. Low routing traffic overhead makes AODV so popular. But the performance in terms of hop routing is deteroited if the routes used in the protocol are with high hop- count and high throughput. Khan et al in [10] address this limitation of the AODV protocol by modifying the route metric and the route discovery mechanism. In2015, Qi, Wang and Jiang [11] have proposed multipath routing protocol based on AODV laying emphasis on node energy. The reason for multipath routing is because it eliminates the need of the source node to restart the route discovery process and rather select the backup route for data transmission directly when link is down or broken and is thus helpful.

Recent advances [12,13,14,15] in AODV assure that there is still much to improve in the basic algorithm.

This paper suggests an improvement to AODV protocol without incurring any routing overhead. Rather the total number of packets floating in the network is reduced making it overall energy efficient. The QoS parameters for which the improvement is demonstrated are average end to end delay and packet delivery ratio. The experiments are performed through simulation using NS2.

• II.    Proposed Protocol

Our routing algorithm applies two changes to route discovery process of AODV [3] to achieve better performance than AODV.

• (i)    In our approach, location information is used in route discovery process to restrict the broadcast of Rote Request(RREQ) packets in the direction of sink. As the location of Sink is already known to all nodes, all the nodes which lie away from sink nodes, compared to sender node do not broadcast the RREQ packet thus limiting the number of broadcast queries. For this, we have used an extra parameter in RREQ packet called distance_val. This distance_val is sent with RREQ packet which is the scaled value computed from distance of sender to sink and a dist_factor which maintains a fixed value to increase or decrease distance based on network characteristics. The computations of this scaled value distance_val depends on three parameters viz scalability_factor, distance between sender/source & sink and dist_factor.

distance_val=(dist(s,d)–dist_factor)/ scalability_factor where, dist(s,d)= distance between sender (S) and destination

(D)

dist_factor= a factor to increase and decrease distance for performance improvement scalability_factor = a scale value of distance depending on expected network size/width

Scalability_factor remains constant for every node in the network.

Fig.1 Illustration of distance factor between sink and source Like AODV, our algorithm also makes use of sequence numbers and hop counts to avoid stale path and select a better path. Loops are also avoided by using the same mechanism as AODV.

• (ii)    We have used a busyness_factor and busyness_threshold values to check busyness of nodes. Busyness of a node is defined as the total packets in queue of a node divided by total limit of packet queue in node. This helps in reducing the packet drop rate as well as reducing the number of RREQ request packets. Any node receiving this RREQ packet check its packet queue and decides whether it has to forward /process RREQ packet or discard it, on the basis of the busyness threshold value. In this way, already busy nodes ignore the RREQ and do not participate in route discovery procedure, which otherwise could result in packet drops increasing the packet drop rate and affecting delivery ratio.

Node busyness = (Current packets in packet queue / total Limit of queue) *100

Both busyness_th and scalability_factor depends on size and characteristics of the network. Busyness_th depends on network load and sclalability_factor depends on size of network. However, unlike scalability_factor, busyness_th can be modified frequently based on needs of network. For this purpose separate broadcast control packets can be used. These values can also be predefined in the nodes.

Pseudocode of Proposed Protocol

The modified algorithms in our approach over AODV [3] are given below.

Algorithm: ROUTE REQUEST()

If Node has data to send

• 1.    Check Route Table for next hop entry to destination

• a.    If No route entry found or route expired

• i.    Prepare RREQ packet and fill entries

• ii.    Compute distance_val and add it in RREQ header

distance_val = (dist(s,d) – dist_factor) / scalability_factor

• iii.    Broadcast the RREQ packet

• b.    If route entry is found, Send Data packet to next hop entry in route table.

• c.

Algorithm: RECV REQUEST()

If a Node Receives a RREQ

• 1.    Check the packet

• a.    If it a destination node update route table entries, send Route Reply (RREP) (unicast) to source node through next hop node in route table.

• b.    If it has a route available to destination node then update route table entries, send RREP (unicast) to source node through next hop node in route table.

• c.    If it’s not destination node and have no current entries in route table

• i.    Check the distance_val in packet.

• ii.    Compute scaled value of distance(node,sink).

• iii.    If           ( distance_val(packet)           <

distance(node,sink)), discard the RREQ packet.

• iv.    Else check node busyness factor

• 1.    If ( node busyness >  busyness_th) discard the RREQ packet

• 2.    Else

• a.    Compute new distance_val and

• b.    Update distance_val in RREQ packet and

• c.    Broadcast the packet.

• III.    Assumptions of the Proposed Scheme

The assumptions of our proposed routing algorithm are as follows:

• (a)    Node Deployment:- Nodes are assumed to be mobile and are deployed randomly in the network area. The sensor nodes are equipped with GPS devices to provide location information.

• (b)    Sink Nodes:- Multiple mobile sink nodes in the network that follows a pre-planned path and schedule known to all the nodes in the network.

• (c)    Location Awareness: - Each node can find out its own location in the network using GPS technology. With location information, RREQ packets are

directed towards the direction of sink nodes limiting the number of RREQ packets and increasing performance of proposed algorithm.

• (d)    Node Mobility: - Node mobility makes the performance of routing dependent on a variety of random factors or simply unpredictable at times. In our routing, we assume mobile nodes having motion with randomly varying speed in any direction constrained by maximum speed possible. Sink nodes are also mobile. However, they are supposed to follow a pre-planned motion path & schedule such that even if any sink deviates from its path it can regain the path and schedule by itself. Also, a little deviation in sink will not affect the performance of the proposed algorithm.

• (e)    Node Design: - Communication in MANETs is achieved in hop by hop fashion using wireless signals, so each sensor node is equipped with proper devices for carrying out signalling and communications. Sensor nodes have omnidirectional modems & antennas to transmit and receive packets. Our routing algorithm supposes that all nodes have good storage, high speed processors, intelligent processing routines and batteries for providing power.

• IV.    Simulation Results

Table 1. Simulation Parameters And Values

SIMULATION SETTING	VALUE
Node Deployment Area	1000 x 1000 sq metres
Node Deployment Type	Random deployment ( Mobile Nodes)
Node Motion	Max 10 m/sec (random in each direction )
Transmission Range	250 metres
Size of Data Packet	512 bytes
Packet generation rate	2-5 packets/second
Initial Energy Value	200 Joule
scalability_factor	500( depends on network size)
busyness_th	85 percent
Connections	60 random connections from any node to sink each for duration of 20 seconds
Total Sink	3
Total Simulation time	100 seconds.

There are 3 destination nodes referred to as sink nodes which are considered to move in a pre-planned path. The sinks pre-planned motion schedule is known to each of the sensor nodes in the network. Packet dropping scenarios and working of other messages (like hello, ack, error etc) are assumed to be just like original AODV routing.

Given below are the three screenshots showing the simulation of the proposed algorithm. Fig. 2 shows the scenario of 30 nodes with node 4 as the source and three differently colored nodes as the sinks.

Fig.3 shows how the source node multicasts request packets to its neighborhood nodes. Since node 16 does not satisfy the criteria of the proposed algorithm, the route requests are sent to the remainig nodes 13, 23, 8 and 9 falling in the transmission range as shown.

Fig. 4 shows that at a later working stage, the nodes that lie close to the sink nodes are more active than the remaining as observed through the movement of nodes 8,9,13 and 23 as compared to node 16.

Fig.2. Simulation Screenshot 1

Fig.3. Simulation Screenshot 2

Fig.4 Simulation Screenshot 3

• A. Performance Metrics

In our simulations, we evaluate the performance of our proposed routing algorithm with respect to the number of nodes in the network.

The following performance metrics were evaluated for our proposed routing protocol.

• •   End-to-End Delay

• •   Number of hops

• •    Packet Delivery Ratio

• •    Throughput

• •   Total Energy Consumed

B. Performance Evaluation through Results

Fig.5. Growth of Average end-to-end delay with number of nodes

Simulation results for average end to end delay of proposed routing algorithm and AODV [3] are presented in form of graph in Fig. 5. The end-to-end delay recorded for AODV is always higher than the proposed protocol. The reduction in end-to-end delay indicates faster delivery of packets. With increasing number of nodes, the delay increases because of increased traffic and larger distance (hops) between source and destination. Growth with increasing nodes is similar for both AODV and the proposed protocol implying that the proposal retains characteristics of AODV.

Average hop count or total hops required to deliver packets from source to destinations can also be used to observe the delay caused by a routing protocol. More hops means larger delay. The proposed protocol has an overall lesser loop count than AODV. Fig. 6 shows the growth in total hops with increasing number of nodes for both AODV and the proposal. The proposed method effectively reduces the average hop count and total hops.

Fig.6. Growth of Total hops with number of nodes

Packet Delivery Ratio (PDR) is a metric which informs about how many packets are actually delivered to the sink. It reveals the useful proportion of total traffic in the network. PDR is already very high for AODV. Fig. 7 shows variation in PDR when number of nodes is increased. There is not much to drop. The proposed protocol also follows the PDR curve of AODV, while maintaining a higher value most of the time.

Fig.7. Growth of Average Packet delivery ratio with number of nodes

Throughput is a metric that combines the effects of reduced delay and increased number of packets reaching destination. As expected, the throughput of the proposed protocol is much higher than AODV. Fig. 8 is the throughput variation of both protocols with increasing number of nodes. The curve of AODV shows much drop in throughput as the number of nodes increase. While the proposed protocol shows more consistency and maintains higher throughput.

Fig.8. Growth of Throughput with number of nodes

Fig.9. Growth of energy with number of nodes

When such improvements are recorded for any routing protocol, there is a concern that it might not consume much energy. Energy is a major issue in WSNs and its consumption must be kept low. AODV has a linear growth of energy consumed with increasing number of nodes. More are the nodes, more is the energy consumption. Proposed protocol also has a linear consumption but slope is lesser than AODV, as shown in Fig. 9. This indicates that as the nodes or size of WSN will grow, the proposed protocol would consume lesser energy than AODV.

The proposed protocol was also compared with AODV for Packet Delivery Ratio keeping number of nodes fixed at value 50 and varying pause time. Fig 10 shows the plot for the same.

Fig. 10. Growth of Packet Delivery Ratio with varying pause time at 50 nodes

The comparison between the proposed protocol and AODV for End to End delay at fixed number of nodes 50 and varying pause time is shown in Fig 11.

The observed results assure that overall energy consumed will be less if proposed protocol is used.

Fig.11. Growth Of End To End Delay With Varying Pause Time At 50 Nodes

• V.    Comparison with other Protocols

This section compares the performance of the proposed protocol with other related works [12,13,14,15]. The parameters taken into account for comparison are Packet Delivery ratio and end to end delay. Instead of using the absolute values for comparison, the amount of improvement from the basic AODV of is computed and compared. Each research work simulates AODV and suggested improvement under certain conditions and assumptions. Hence, the improvement in QoS parameter values over AODV is better expressed as percentage of improvement.

Table 2 shows the amount of improvement in Packet Delivery Ratio achieved through Ad-AODV [12] and the proposed protocol. The amount of decrease in End-to-End delay achieved through Ad-AODV [12] and the proposed protocol are compared in Table 3. The results are for different number of nodes, from 20 till 80 and fixed pause time.

The comparison between Ad-AODV and the proposed protocol is also done keeping the number of nodes fixed at value 60 and varying Pause time from 0 till 10. Tables 4 and 5 show the comparison between the reported results of Ad-AODV [12] and the proposed AODV for percentage improvement in Packet Delivery Ratio and percentage decrease in End to End delay respectively over basic AODV protocol. The proposed AODV shows significantly better improvement percentage in both the parameters.

Table 2. Comparison Based On Improvement In Packet Delivery Ratio At Varying Nodes

Nodes	AD-AODV [4] (%)	Proposed AODV( %)
20	4.109	-
30	-	3.618
40	4.938	5.061
50	-	15.06
60	2.702	25.96
70	-	11.232
80	1.190	1.210

Table 3. Comparison Based On Decrease In End To End Delay At Varying Nodes

Nodes	AD-AODV [4] (%)	Proposed AODV (%)
20	2.439	-
30	-	33.333
40	28.421	51.501
50	-	52.38
60	10.569	64.66
70	-	36.923
80	8.333	26.041

Table 4 Comparison Based On Improvement In Packet Delivery Ratio At Varying Pause Time

Pause time	Ad-AODV (in %)	Proposed AODV ( %)
0	2.702	25.96
2	2.66	18.317
4	3.79	66.80
6	1.19	49.43
8	3.52	46.07
10	3.37	24.54

Table 5. Comparison Based On Decrease In End To End Delay At Varying Pause Time

Pause time	Ad-AODV ( %)	Proposed AODV ( %)
0	10.5	64.66
2	16.66	57.29
4	20	54.68
6	33.33	77.23
8	26.66	51.00
10	28.57	62.40

At fixed value of Pause time and number of nodes fixed at 50, the proposed protocol is compared with NDj-AODV[13], AOMDV[14] and I-AODV[15] (taking the results as reported in their research works) for seeing the improvement in performance for both the parameters. Tables 6 and 7 show the improvement results for Packet Delivery Ratio and End to End delay respectively. The improvement is expressed as percentage increased from basic AODV.

Table 6. Comparison Based On Improvement In Packet Delivery Ratio At Fixed Pause Time And Nodes

Protocol	Improvement (in %)
NDj-AODV	8.33
AOMDV	25
I-AODV	-
Proposed AODV	52.38

Table 7. Comparison Based On Decrease In End To End Delay At Fixed Pause Time And Nodes

Protocol	Improvement (in %)
NDj-AODV	11.11
AOMDV	6.66
I-AODV	5.43
Proposed AODV	15.06

• VI.    Conclusion

MANETs are essentially dynamic in topology, hence routing consumes much of the energy of the devices. We proposed here a routing scheme for MANETs based on the popular AODV protocol. We have retained most of the properties of AODV to maintain backward compatibility. Energy saving is done by reducing the total number of messages being circulated. As a result, we achieved a protocol with lower end-to-end delay, lesser average hop count, higher packet delivery ratio, higher throughput and lower energy consumption.

As future work, energy can be further saved by reducing any redundant information or messages. Also, if a subnet does not change within the network, the routing decisions can be saved from past experiences.