Ad-hoc On-demand Distance Vector (AODV) Protocol

in StemSocial2 months ago (edited)

AODV.png

Introduction

Wireless networks are presently employed in a range of applications, and this technology is quickly growing. Most rely on infrastructures such as access points and routers, making communication in dynamic topologies challenging. As a result, ad-hoc networks have arisen, which are decentralized networks that allow for better communication even when nodes are mobile; they enable flexibility and autonomy because there is no need for central management.

With the growth of these networks, there is a need to create routing protocols that are easily adaptable to changes. The selection of these routing protocols for implementation on communication networks on microgrids is critical, as it is required to meet network system criteria for Neighborhood Area Networks (NAN) applications on microgrids, such as low latency and high dependability.

Building a workable implementation of an ad hoc routing protocol is more difficult than developing a simulation. A simulation is a key tool in the development of mobile ad hoc networks because it provides an appropriate environment for experimenting with and validating routing protocols. However, the simulation does not guarantee that the protocol will operate in practice because simulators include assumptions and simplified models that may not accurately reflect real-world network operation.

To validate that the routing protocol specification functions under real-world settings, a functioning implementation is required. Otherwise, the protocol design’s assumptions cannot be verified as valid. An implementation can also be used to run testbed and field tests. In the simulation, the developer is in charge of the entire system, which is, in the reality, just a single component.

We have a number of required events that are unsupported. These events must be supported to achieve the task. The components and their relationships must also be investigated; hence these events include a large number of system components. For these reasons, creating an ad hoc routing protocol implementation requires significantly more effort than a simulation. In this blog, we evaluate the latency of AODV protocol by simulating it using SimPy and WSNSimPy.

AODV Protocol

The Ad-hoc On-demand Distance Vector (AODV) routing protocol is a reactive routing system, routes are determined only when they are required. The AODV protocol established network routing between two nodes based on route discovery and route maintenance. It broadcasted an RREQ message to the target node in the form of flooding during the route require process; during the route response process, the target node picked the first-arrived RREP and transmitted an RREP message. As a result of the node's rigorous activity in seeking routings, the route was easily broken, resulting in the loss of an RREP packet.

In the routing maintenance process, the damaged node would discard error packets and notify the source node to resend request message when broadcasting RERR packets, resulting in time delay of succeeding packet; in order to minimize loopback caused by fresh tours, local repair may cause the RREP provided by downstream node to be disregarded, reducing the likelihood of routing recovery. Furthermore, because the node is mobile, the route may not be repaired on time or may fail to repair, reducing the usage of network control information and potentially increasing routing latency, hurting network performance.

When a node needs to deliver a message to a destination node but does not have a valid route in its routing database, this phase happens. Then it broadcasts a route request packet (RREQ) to the destination node; this RREQ message is received by the originating node's neighbors. If no route exists to the destination, the number of hops must be increased, and this packet must also be disseminated. Simultaneously, they must save a route to the node that initiated the request in their routing database, taking into consideration the information included in the packet. If it has a route to the target, it sends a route response packet (RREP).

When an RREQ packet arrives at the target node, it must establish or change the route as needed and broadcast an RREP via unicast. When an intermediate node gets this RREP, it additionally distributes the packet through unicast, taking into account the reverse routes recorded in the routing tables via which the RREQ was communicated. The protocol employs two sequence numbers: the sequence number of the source maintains information for the route opposite the source up to date, and the sequence number of the destination aids in determining if the route presented may be accepted by the source or whether a more current route exists.

Hello messages, which are sent on a regular basis, are employed throughout this phase. These are delivered to surrounding nodes to alert them that a node is still present in the network. When a neighbor's "hello" is not received after a time, a route error packet (RERR) is issued to the source node: the RERR contains the IP address of the inaccessible node. Each intermediary node that processes the RERR will change the routes used by the now-inaccessible node and continue to broadcast the packet until all nodes in the network have received the broken link signal.

Only routes necessary by the source node at the time are saved. If the source node loses an active path owing to mobility, it can restart the route discovery process. If, on the other hand, an intermediary or destination node moves out of range, the break's predecessor sends a Route Error (RERR) message to the impacted active upstream nodes.
As a result, these nodes continue to relay RERR signals to their predecessor nodes until they reach the source node. When an RERR message is received, the source node either pauses transmission if the route is no longer necessary or restarts route discovery if the route is still necessary.

AODV Protocol Simulation

We evaluate time for the AODV protocol to establish a route or connection from the source node to the destination node. We evaluate the time needed to establish a connection from the source node to destination node. We perform 30 simulation with starting node at 1 and node 99 as the destination node. The simulation time is set to 100 seconds.


wsnn1.PNG

AODV protocol transmit and floods the "Hello" message to detect destination node


We start with the node 1 as the source node and node 99 as the destination, see figure. The average time to establish route between 13.76197 seconds. We note that the AODV protocol can establish connection between 13 to 17 seconds. From the 30 simulations, there are 3 out of 30 instance that a route was not establish due to the "Hello" message hopes over the nodes.


wsnn3.PNG

AODV protocol detected destination node


wsnn4.PNG

AODV protocol establish route between source and destination nod


The protocols are simulated using WSNSimPy and SimPy in Python. SimPy is a Python-based process-based discrete-event simulation toolkit. SimPy processes are defined by Python generator functions and can be used to model active components such as consumers, vehicles, or agents. On the other hand, WsnSimPy is a simulator for wireless sensor networks, modeling both network-level messaging and full-stack communications. It is written in Python 3 and built on top of the SimPy simulation framework.


AODV Protocol Simulation

Node #99 [   6.37665] Receive RREQ from 1
Node #99 [  11.37665] Send RREP to 1
Node #1  [  13.97753] Receive RREP from 99
Node #1  [  18.97753] Start sending data
Node #1  [  19.97753] Send data to 99 with seq 0
Node #1  [  19.97753] Forward data with seq 0 via 11
Node #11 [  20.17758] Forward data with seq 0 via 22
Node #22 [  20.37766] Forward data with seq 0 via 23
Node #23 [  20.57773] Forward data with seq 0 via 24
Node #24 [  20.77776] Forward data with seq 0 via 34
Node #1  [  20.97753] Send data to 99 with seq 1...
...
Node #99 [  99.55267] Got data from 1 with seq 75
Node #11 [  99.75169] Forward data with seq 78 via 21
Node #53 [  99.75203] Forward data with seq 77 via 44
Node #58 [  99.75235] Forward data with seq 76 via 59
Node #21 [  99.95176] Forward data with seq 78 via 31
Node #44 [  99.95207] Forward data with seq 77 via 55
Node #59 [  99.95242] Forward data with seq 76 via 69

A snipet of AODV protocol Node log


Conclusion

A simulation is a key tool in the development of mobile ad hoc networks because it provides an appropriate environment for experimenting with and validating routing protocols. The AODV routing protocol is a reactive routing system, routes are determined only when they are required. The AODV protocol established network routing between two nodes based on route discovery and route maintenance, which broadcasted an RREQ message to the target node in the form of flooding. In this paper, we evaluate the latency of AODV protocol that it can establish a route from source to end node at about 13 seconds.

References

  1. A. Dumka, S. K. Chaurasiya, A. Biswas, and H. L. Mandoria, A Complete Guide to Wireless Sensor Networks. 2019

  2. Waltenegus Dargie and Christian Poellabauer, Fundamentals of Wireless Sensor Networks: Theory and Practice. John Wiley & Sons Ltd., 2010.

  3. H. Karl and A. Willig, Protocols and Architectures for Wireless Sensor Networks. 2006.

  4. Chakeres, Ian & Belding, Elizabeth. AODV Routing Protocol Implementation Design. Proceedings of the 24th International Conference on Distributed Computing systems Workshops. 698-703. 10.1109/ICDCSW. 2004.1284108.

  5. Martinus Dipobagio. An Overview on Ad Hoc Networks. Institute of Computer Science (ICS), Freie Universität Berlin

  6. Sheng Liu, Yang Yang, Weixing Wang, Research of AODV Routing Protocol for Ad Hoc Networks1, ISSN 2212-6716,https://doi.org/10.1016/j.aasri.2013.10.054

  7. E. M. Royer and C. E. Perkins, "An implementation study of the AODV routing protocol," 2000 IEEE Wireless Communications and Networking Conference. Conference Record (Cat. No.00TH8540), 2000, pp. 1003-1008 vol.3, doi: 10.1109/WCNC.2000.904764.

  8. Chaiporn Jaikaeo. WSNSimPy: A simulator for wireless sensor networks based on SimPy simulation framework.