Performance Evaluation of a New AODV Protocol with Auxiliary Metrics
- Author: Ngo Van-Vuong, Jang Jaeshin
- Publish: Journal of information and communication convergence engineering Volume 14, Issue1, p14~20, 31 March 2016
The AODV protocol uses many RREQ messages and one RREP message in the path-discovery process. This protocol has only one metric, the number of hops. Although it is simple, this protocol is not efficient. To avoid this problem, we propose a new AODV with two auxiliary metrics (AuM-2-AODV). The AuM-2-AODV protocol tries multiple route replies, which reduces the chance of path failure and helps the network obtain a better data rate. It has two auxiliary metrics, the remaining energy of its nodes and the number of HELLO messages received at the nodes. With these two metrics, the reliable path from the source node to the destination node will be chosen. In this paper, the performance of the AuM-2-AODV is evaluated using the NS-3 simulator. The performance results show that AuM-2-AODV provides greater throughput and packet delivery ratio by 20% and up to 50% and about 100% in some cases, respectively, than previous protocols.
AODV , AuM-2-AODV , MANET , NS-3 , PDR , Throughput
A mobile ad hoc network (MANET)  is a wireless network that has many autonomous mobile nodes (devices); “ad hoc” is a Latin phrase meaning “for this special purpose”. The term “ad hoc networking” typically refers to a system of network elements that forward packets to and from each other instead of relying on a base station to control the flow of messages.
Ad hoc on-demand distance vector (AODV)  stands out among routing protocols for MANET. However, it still has some shortcomings. First, there are many request messages but only one reply message. Second, the metric is the number of hops, which means that the shortest path is always chosen, neglecting other features such as the remaining energy of nodes. Several proposals have been made to overcome these issues. In some studies, the metric is changed to give more weight to other characteristics of links besides the number of hops. In other papers, the reply messages’ response is also improved to guarantee the forwarding of the reply messages.
In order to develop a better routing protocol, we propose a new AODV protocol with two auxiliary metrics (AuM-2-AODV). AuM-2-AODV has more metrics than other protocols. It still uses the main metric, number of hops, while some other protocols discard this important metric. It also has multiple reply messages. In addition, a new mechanism of comparing redundant request messages is provided, which will help the nodes choose more reliable links, unlike other protocols, in which redundant request messages are simply discarded.
In this paper, we review related works in Section II. Section III gives information about the AODV protocol. AuM-2-AODV is described in Section IV. We present simulation results in Section V and conclude in Section VI.
Some studies have scrutinized the route reply (RREP) response; a typical example of a proposal from those studies is reverse AODV (R-AODV). In R-AODV , the source node and the destination node play the same role with regard to sending control messages. Thus, after receiving a route request (RREQ) message, the destination node broadcasts the reverse route request (R-RREQ) messages to find the source node. Moreover, this paper showed that using multiple RREPs does not produce more control packet overhead than using a single RREP in case of a broken reverse path. In MRAODV , R-AODV is improved with a new metric—route stability. The source node will choose the path based on this metric. Another improvement was also presented, which is IMRAODV. In IMRAODV , the energy of nodes is considered and recorded in a new field of the R-RREQ packet.
Other studies concern the energy at nodes. In ES-AODV , the protocol calculates the cost of each link based on the energy at nodes. These link costs are recorded in RREPs that are sent to the source node. After receiving a RREP packet, the source node waits for 3 time cycles, calculating and choosing the minimum cost link in many alternative routes to transmit the data. In EM-AODV , there is a new approach which tries to use the metric “residual energy of nodes” instead of the number of hops. The authors define the rate of energy consumption for each node to estimate its lifetime. Then, they define a cost that fits this lifetime and the energy level. This information is used to calculate route costs.
There are some studies that use another metric instead of the number of hops. In SNR-based AODV , the source node chooses the path with a higher signal-to-noise ratio. In AODV-EER , the main goal is to find the route with the lowest drop rate from the source to destination. In H-MAODV , the metric is calculated as a function
fijof nodes’ velocity.
αand βare the weights satisfying α+ β= 1; Dijis the distance between node iand node j; Triis the transmission range of node i; Vrijis the relative velocity between node iand node j; and Vrmax ijis the maximum relative velocity between node iand node j.
AODV uses RREQ and RREP messages to find the path from a source node to a destination node. First, the source node broadcasts RREQs to its neighbor nodes. These neighbor nodes then forward the RREQs to other inter-mediate nodes until RREQs reach the destination node. The destination node replies to the source node with an RREP that contains the information about the route from the source node to the destination node. The source node determines how it should update its routing table based on the number of hops in the RREP. Normally, the source node updates its routing table with the shortest path (the path that has fewest hops from the source node to the destination node).
Nodes may offer connectivity information by broadcasting local HELLO messages. When HELLO messages from node B are received by node A, node A refreshes all entries in its routing table in which node B appears to be the next hop. If node A has not heard any HELLO or regular message from node B for some amount of time, node A assumes that node B is no longer its neighbor and invalidates all routes through node B (routes to all destinations in which node B is the next hop).
Fig. 1 illustrates an example of the AODV path discovery process. The source node S tries to find a route to the destination node D, so node S broadcasts RREQs to other nodes. One RREQ goes from node S to node 1, then node 2 and finally reaches node D. Afterwards, Node D replies with an RREP. The RREP travels along the reverse path (node 2 – node 1 – node S). Node S will transmit data after it receives the RREP. The RREQ that goes in the path node 3 – node 4 – node 5 – node 6 – node D will be discarded by node D. Redundant RREQs will be ignored by every node in AODV, so node D only replies to the first RREQ and does not care about the second RREQ.
In this section, we present an overview and describe the route discovery procedure of AuM-2-AODV.
In AODV, the destination node only sends one RREP message to the source node. On the other hand, in AuM-2-AODV, the destination node sends several RREP messages to the source node. In addition, AuM-2-AODV has one main metric (the number of hops) and two auxiliary metrics (the remaining energy of the nodes and the HELLO messages received from the nodes). First, the nodes will compare the main metric. If the paths have the same main metric, the nodes will update their routing tables by comparing the auxiliary metrics of these paths.
AuM-2-AODV has several RREP unicasts instead of the R-RREQ broadcast of R-AODV. In R-AODV, the destination node broadcasts the R-RREQ after it receives the RREP. In Fig. 4, the destination node (node D) broadcasts R-RREQs to its neighbor nodes after receiving a RREQ from the source node (node S). In AuM-2-AODV, however, each time the destination node receives a RREQ, it sends a RREP for the source node (Fig. 5). Each RREP is a response to each duplicated RREQ. Therefore, the number of control packets in AuM-2-AODV is fewer than in R-AODV. In both Figs. 4 and 5, node 4 moves out of transmission range of node 5 when a RREP travels along the reverse path node D – node 5 – node 4 – node 1 – node S, so this RREP will be lost. AODV needs to initiate the RREQs broadcast again. However, R-AODV and AuM-2-AODV can overcome this problem because they use multiple RREPs.
Unlike both ES-AODV and EM-AODV, AuM-2-AODV not only keeps the original metric, the number of hops, but also takes the energy at nodes into consideration. Moreover, AuM-2-AODV transmits data packets immediately, while ES-AODV needs to wait 3 time cycles before transmitting data packets.
Similarly, the drawback of the SNR-based AODV and H-MAODV is that they only have one metric. SNR-based AODV ignores the number of hops and H-MAODV tries to calculate a function of different variables that do not have the same units. This approach undervalues the number of hops, which is an important metric in AODV. AuM-2-AODV has a better procedure for choosing metrics because it compares each metric separately.
AuM-2-AODV uses the original control packets of AODV with modification in the Reserved field. The RREQ packet shown in Fig. 6 contains the following information: message type, source address, destination address, broadcast ID, hop count, source sequence number, destination sequence number, and the remaining energy (inserted into the Reserved field). The RREP packet shown in Fig. 7 contains the following information: message type, source address, destination address, hop count, destination sequence number, life time and the number of HELLO messages received (inserted into the Reserved field). The routing tables in nodes also need to contain two more fields to record two auxiliary metrics.
When one node (the source node) wants to send data to another node (the destination node) without any information about the route, the source node initiates a route discovery procedure by broadcasting the RREQs. The source node sends the RREQs to all neighbor nodes within its transmission range to ask about the route to the destination node. Afterwards, these neighbor nodes keep broadcasting the RREQs if they do not have the information about the requested route. However, there is a congestion problem if intermediate nodes receive flooded RREQs and forward them without examination. The source node increases the broadcast ID each time it issues a new RREQ. Thus, each RREQ packet is distinguishable with a unique combination of the broadcast ID and the source and the destination addresses. When an intermediate node receives an RREQ, the node refers to its routing table and checks whether it has already received an RREQ with the same broadcast ID and source address. In AODV, the node records the broadcast ID and the source address of the RREQ for the first time in its routing table and drops redundant RREQs. However, in AuM-2-AODV, the node will make the comparison between RREQs that have the same broadcast ID and source address. It will update its routing table with the RREQ that has the fewest number of hops. If two RREQs have the same number of hops, the node continues to compare the remaining energy value. This remaining energy value is accumulated each time the RREQ passes a node; in other words, it is the sum of the remaining energy of the nodes that the RREQ passes.
Fig. 8 illustrates the reception of two duplicate RREQs. The first RREQ goes through node 1 – node 2 – node 4 and the second RREQ goes through node 1 – node 3 – node 4. Assuming that node 3 has more remaining energy than node 2, node 4 then updates its routing table with the path node 1 – node 3 – node 4. If the routing protocols are AODV, R-AODV, SNR-based AODV, etc., the redundant RREQs are ignored and there is no comparison process with RREQs.
In AODV, the destination node ignores the duplicate RREQs and only answers once for the first RREQ that arrives. However, in AuM-2-AODV, the destination node does not discard duplicate RREQs. Because each duplicate RREQ can travel another route from the source node to the destination node, the reverse paths can be independent of each other (node-disjoint paths). When one reverse path is disconnected, the other paths can still be stable. When the destination node receives an RREQ, it generates an RREP and sends it to the source node along the reverse path. This process recurs each time that the destination receives an RREQ with different reverse paths. The number of HELLO messages received will accumulate when the RREP passes a node; in other words, this field is the sum of all the received HELLO messages of the nodes that RREP passes. When RREPs arrive at the source node, the source node will examine what path is better and update the routing table. The shortest path will be chosen and the data transmitted immediately. If there are two RREPs having the same number of hops, then the source node will compare the number of HELLO messages received on each RREP, and it will choose the path that has fewer HELLO messages received. The number of HELLO packets received provides some information to support the process of choosing a suitable path between some short paths. The nodes that receive many HELLO messages often lie in the crowded region and have a high chance of being involved in transmission. In case that there are some transmission links, these nodes can lose their energy faster than others. Furthermore, the network may suffer congestion in dense areas. With the information about the number of HELLO messages received at each node, the data can be transmitted through less crowded areas, balancing the load of the nodes.
Fig. 9 illustrates the reception of RREPs. The destination node (node D) sends two RREPs to the source node (node S). Node S will compare these two RREPs and transmit data packets along the appropriate path.
Because of the multiple replies from destination to source node, the power consumption of an intermediate node on a MANET is increased slightly. The destination node only sends some RREPs along the reverse paths to the source node. In , the simulation shows that each RREP is generated at the cost of more than 80 transmissions of the RREQs on average. It is also shown that the RREP loss ratio increases as the number of flows increases. In case that an RREP is lost, the source node needs to re-initiate the broadcast of the RREQ. This means that more than 80 transmissions of the RREQs are wasted, and the network will need energy for another 80 transmissions of the RREQs. Compared to the power consumption of broadcasting hundreds of RREQs, the power consumption of sending several RREPs is negligible.
Our simulations are implemented using Network Simulator 3 (NS-3) . We conducted two scenarios.
The common simulation parameters are in Table 1.
To evaluate the performance of AuM-2-AODV and that of the AODV protocol, we use two performance metrics.
1) Scenario 1 Simulation Results
Fig. 10 shows throughput comparison of AODV and AuM-2-AODV protocols. Fig. 11 presents packet delivery ratio comparison of the AODV and AuM-2-AODV protocols. AuM-2-AODV outstrips AODV, especially in cases of huge networks. While the increase of throughput is only 20% in cases of networks with 60 nodes and 70 nodes, the value of increased throughput is 50% in cases of networks with 80, 90, and 100 nodes. In these cases of huge networks, the intermediate nodes often broadcast RREQs; the more intermediate nodes the network has, the more times the RREQs are forwarded. Therefore, the network may suffer congestion because of these RREQs. This congestion may lead to a decrease in throughput and the packet delivery ratio.
2) Scenario 2 Simulation Results
Figs. 12 and 13 show throughputs and packet delivery ratio comparison of the AODV and AuM-2-AODV, respectively. AuM-2-AODV improves the packet delivery ratio and the throughput significantly. The throughput of AuM-2-AODV is in the vicinity of 120 kbps, whereas the throughput of AODV only reaches its peak at approximately 112 kbps. Besides, it is evident that the network with the AODV routing protocol suffered congestion because the packet delivery ratio of AODV gradually decreases when the number of nodes is increased from 80 nodes to 100 nodes.
AuM-2-AODV still uses a part of the AODV path-discovery mechanism, and the main metric is the number of hops, so the path setup time of AuM-2-AODV is approximately that of AODV. For example, in scenario 1, the source node using the AuM-2-AODV routing protocol starts sending the UDP packets at 2.06156 seconds and 2.05059 seconds in cases of networks of 60 nodes and 70 nodes, respectively. However, the source node using the AODV routing protocol starts sending the UDP packets at 2.0661 seconds and 2.06391 seconds in cases of network of 60 nodes and 70 nodes, respectively.
We proposed a modified version of the AODV routing protocol, AuM-2-AODV, which takes into consideration the number of HELLO messages received and the remaining energy of nodes. These metrics are inserted to the Reserved field of control packets. Moreover, we introduced the procedure of comparison between redundant RREQs. The response with the RREP of AODV is also improved with multiple RREPs in AuM-2-AODV. The results show that AuM-2-AODV surpasses the performance of AODV in the throughput and the packet delivery ratio. According to computer simulation results, the throughputs of AuM-2-AODV are 20% to 50% higher than those of AODV. The packet delivery ratio of AuM-2-AODV is always higher than that of AODV, and notably, in some cases the packet delivery ratios of AuM-2-AODV are twice those of AODV.
[Fig. 1.] AODV route discovery procedure.
[Fig. 2.] RREQ packet format of AODV.
[Fig. 3.] RREP packet format of AODV.
[Fig. 4.] Broadcast of R-RREQs in R-AODV.
[Fig. 5.] Response of RREPs in AuM-2-AODV.
[Fig. 6.] RREQ packet format of AuM-2-AODV.
[Fig. 7.] RREP packet format of AuM-2-AODV.
[Fig. 8.] Duplicated RREQ reception in AuM-2-AODV.
[Fig. 9.] RREPs reception in AuM-2-AODV.
[Table 1.] Simulation parameters
[Fig. 10.] Comparison of throughput in scenario 1.
[Fig. 11.] Comparison of packet delivery ratio in scenario 1.
[Fig. 12.] Comparison of throughput in scenario 2.
[Fig. 13.] Comparison of packet delivery ratio in scenario 2.