Literature Survey

Wireless Communication via Ad-hoc On-demand Distance Vectoring (AODV)

Stephen Walter
November, 2008

1. Introduction

Presently, most wireless networks run in a structured setting where clients connect to a hub that is wired into the rest of the network. Yet, not all sites where we need networks have the infrastructure in place, which demands for a new method of communication. These Ad-hoc situations have lead to the development of new protocols to send data across computers. One of these protocols was the Adhoc On-demand Distance Vectoring (AODV) designed in 1999. This is a pioneering method to handle fragile and mobile wireless networks, but it remains as a prominent standard protocol even today.

2. Mobile Networks

Our society grows more dependant on computer networks, even in underdeveloped or dysfunctional locations. Just a decade ago, AODV creator Perkins realized the emerging market for mobile networks from improving laptop computers. These computers could not work using traditional table driven networks without their fixed wireless hubs. A decentralized network had to be established that also fulfilled several qualities. Wireless networks must strive to maximize limited bandwidth, minimize consumed energy of portal devices, handle security without authority, and set up automatically due to the changing environment [1].

2.1 Ad-hoc Networks

These new networks are called Ad-hoc networks, which means it lacks any backbones to hold the network together. Instead, individual computers must rely on themselves to transmit data across the network. West points out an important key concept in Ad-hoc terminology. While computers do talk directly to their neighbors to send their own communications, ad-hoc technology requires every computer to assist in relaying data for other computers. This allows routing through areas beyond a computer's immediate reach.

2.2 Routing Environment

Before setting up a route through a Ad-hoc wireless network, we must consider the wireless environment. The network must adapt to mobile configurations, consider the limited airwaves, and preserve resources. Ad-hoc networks require flexible and path-evolving protocols [3]. We also must consider that mobile networks will break. We no longer have to make the assumption that wireless networks have stable connections [4]. Additionally since radio signals cannot overlap without making original messages unreadable, the network should consider radio bandwidth as a limited resource [2]. Moreover, some issues exist such as the hidden terminal problem where a outlying terminal is within range of either sender or receiver, but not both. This terminal may block the sender's signal by making its own connections without realizing the original connection taking place [1]. All these issues must be handle by the protocol that orchestrates the wireless communication.

2.2.1 Proactive, Table-driven Protocols

Traditionally to handle networking, computers would collect and store all of the surrounding network information in a table. This table provides a proactive method, since it is providing the exact route when the computer needs to make a connection. However, the ad-hoc enivornment is a changing and unstable network working off of limited resources. It is no longer feasible to have each computer tell its neighbors about the entire surrounding network, because this would build large overhead on maintaining the network[2]. Without existing knowledge of the whole network, we cannot proactively build routes.

Destination-Sequenced Distance Vector (DSDV) is an example of a proactive protocol, which is important to AODV since its author treats DSDV as a parent protocol. [2] Like any proactive, table driven protocol, this protocol for wireless networks has size limitation because it needs to periodical broadcast the whole network. Much of this information is not necessary and unused. Regardless, the protocol requires the network to continuously update its status to account for any changes [2] [3].

2.2.2 Reactive, On-demand Protocols

To solve the deficiencies of the table approach, researchers designed protocols that would only operate when a connection was needed. This on-demand approach only required individual computers to know its local network [2]. Since computers are not required to know the topology of the entire network, the network saves overhead cost of sending routing data [1]. Terminals only requests and store information for active communication [2]. There are several of these reactive, on-demand protocols: Ad-hoc On-demand Distance Vector (AODV), Dynamic Source Routing (DSR), Cluster Based Routing Protocol (CBRP), and Preemptive On-demand Distance Vector (PAODV) to name a few of the more common types. Each protocol differs by amount of discoveries, locality detection, source tracing, or broadcast request range [3].

3. AODV

Ad-hoc On-demand Distance Vector was one of the pioneering, reactive protocols at its time in 1999. Its goal was to find connections when needed, rather then the proactive approach of building routes before sending data [1]. The protocol can be broken down into two major parts consisting of route discovery and maintenance.

3.1 Route Discovery

When attempting to establish a new connection, a computer will send a request for connecting to its destination IP while providing along its own IP. Neighboring computers receive the signal and either reply with a match or rebroadcast the route request to its own neighbors [1]. If a route to the destination exists, the route request will eventually reach its goal. To prevent an indefinite search for the destination, each of these route requests (RREQ) contains a destination sequence number to track life of data. This procedure was grandfathered from the Destination-Sequenced Distance Vector protocol [2].

The protocol will track two counters while it broadcasts a RREQ. The first is a broadcast identification which uniquely defines each new request made by the original computer requesting the connection. [2] This effectively provides timestamps on requests to track which signals are more recent [1]. This also guarantees that no network loops are created, since the tracking sequence number determines whether to send RREPs [2]. The second is a hop count that tracks the nodes in the routing path [2]. The protocol uses this counter to limit number of hops the request is allowed to make [1]. This prevents computers from sending route requests throughout the whole network when the destination could have already been found earlier. The protocol will start with a relatively small hop count limit. Upon the lack of a discovery, the original sender will rebroadcast the request with larger limit on hops [1].

When the route request reaches its destination, the protocol will setup reverse path formation for the reply, and constructs a forward path formation for the original computer [2]. Since requests are saved, each node knows where to send the reply when moving in reverse [1]. When the route reply reaches the original sender, the route for communication is complete.

3.2 Route Maintenance

After the route is connected and active, the protocol needs it ensure the connection remains intact. Each node in the route uses hello messages (single hop reply messages) or link-layer acknowledgments to detect communication breaks [1][2]. When a set number of these hello messages fail, the node will relay back the break to everyone involved in the route. On this break, each node in the route will discard outdated routing information that was saved. This information reaches back to sender, who can begin a new RREQ to rediscover its destination [1]. Routing data must be timed out and expired in order to keep communication fresh and eliminate dead end routes. The protocol should only connect with nodes that are bidirectional so that they can communicate with hello messages [2]. Perkins believes that connection breaks could often be a single node lost in the connection that could be fixed locally without setting up a whole new connection. In this case, the node that discovered a break could attempt a small scale, local route repair. This node would run its own AODV route request to a small area, however the node would need to buffer the incoming packets from the original sender since it is unaware that a break occurred [1].

3.3 RREQ Flooding

During the route discovery process, every request expands out to all neighbors which is called network flooding. This holds some ramifications to network performance.

3.3.1 Benefits

By design of the flood, each request request operation becomes fast because it will discovery the shortest route with little delay and no cycling. All connections are loop-free due to the protocol's counting variable. Even with the RREQ flood, the network saves on overall bandwidth by not sending the entire network routing table. It also saves bandwidth since it uses on-demand functionality instead of periodically rebuilding routes that may not have broken [2].

3.3.2 Drawbacks

Every connection break will destroy the whole route chain. This causes a new request to broadcast and flood the network again. This means that several connection breaks can greatly increase the protocol's overhead to maintain connections. Boukerche has discovered that AODV has one of the highest overhead ratios out within the proactive protocols, since it floods the network on every break [3].

Additional problems exist on implementation of the protocol. The problem is that modern operating systems, namely Windows, assume networks are static and don't require a route discovery. The Windows operating system will allow software to define the routing table, however software cannot request for unknown destination as that is considered an error. IP routing and network information that is sent out to appropriate network devices occurs at the kernel level. Linux systems can be easily modified to accommodate route discovery and thus are popular system for constructing AODV systems [1].

3.4 Performance

When Perkins originally described the AODV protocol, he included simulations ranging between 50 to 1000 mobile nodes. His results were that "AODV can find routes quickly and accurately." The percentage of real communication data out of all data broadcasted remained above 90% for the 50 and 100 examples He concluded that while performance lowered for larger networks, his protocol was deemed the best scaling protocol for its time [2]. However, Perkins did not compared against other protocols.

Boukerche conducted a test with AODV and four other protocols. His results showed no overall winner. AODV produced more overhead than others when its connections are broken due to fast moving nodes, but outperformed proactive protocols such as DSDV. AODV had the shortest delay between connections compared to other reactive protocols due to the speed of route discovery [3].

Another evaluation compared AODV with three other protocols using the "two ray" and "shadowing" models. This concluded with a clear distinction when the network is overloading. AODV performed slightly stronger in the shadowing model than DSR as the number of nodes increase, but both were beaten by the proactive protocol, DSDV. The two ray ground model reversed the results, giving both AODV and DSR good delivery ratio with high nodes and poor results for DSDV [4].

4. AODV Derivatives

4.1 Multicast

Perkins stated that AODV was able to use multicast by design [2]. This means the protocol could be adjusted to discovery multiple routes during the route discovery process. Using redundancy, the protocol can solve network breaks by using the alternative routes as backup. An example created by one researcher was Ad hoc On-Demand Multipath Distance Vector (AOMDV). By sending multiple RREPs and using special code to prevent loops from forming, this protocol keeps overhead low. An additional routing algorithm is required to prevent the network from bottling up at select nodes. Overall, the modification produces less packets loss and required less discovery [6].

4.2 Multiradio

Another approach to improving AODV involves using several radio bands for communication to increase capacity. While similar to AODV, the new protocol broadcasts on one common channel when sending out route requests. Researchers found that multi radio AODV provides a significant decrease in packet loss, latency, and overhead with each additional interface. Their AODV-MR-3 was able to maintain high loads (3 Mbps) of traffic with strong delivery rate where AODV failed [5].

4.3 Route repairing

As described in the original protocol, there is the possibility of rebuilding broken local networks, without recreating an entirely new connection.[2] This method can save overhead from reflooding the network using small discovery fixes, but only when the routing path is long enough to justify local repairs. One researcher simulated such an algorithm in a modified version of AODV, which showed a slight decrease in network load [7].

5. Conclusion

With the tested algorithm of the AODV protocol, many new ad-hoc protocols will use AODV as a foundation. Using AODV's speed of reactive route discovery, other protocols can address its inherited flaws of network overhead. Multicasting, multiradio, and local repairs are merely the beginning of the enhancements that can be made to improve the protocol. When researchers can design this protocol to handle all situations well, our normal computers could except to see this evolved protocol as the standard.

References

[1] West, David, "An Implementation and Evaluation of the Ad-hoc On-demand Distance Vector Routing Protocol for Windows CE," Master Thesis, University of Dublin, Sept 2003.

[2] Perkins, Charles E. and Royer, Elizabeth M., "Ad-hoc On-Demand Distance Vector Routing," Second IEEE Workshop on Mobile Computer Systems and Applications, pp. 90, February 1999.

[3] Boukerche, Azzedine, "Performance Evaluation of Routing Protocols for Ad Hoc Wireless Networks," Mobile Networks and Applications, vol. 9, pp. 333-342, 2004.

[4] Tao, Yang, Makoto Ikeda, Giuseppe De Marco, and Leonard Barolli. "Performance Behavior of AODV, DSR and DSDV Protocols for Different Radio Models in Ad-Hoc Sensor Networks," ICPPW. International Conference Workshops on Parallel Processing, pp. 6, Sept 2007.

[5] Pirzada, A. Amir, Portmann, M. Portmann and Indulska, Jadwiga, "Evaluation of Multi-Radio Extensions to AODV for Wireless Mesh Networks," Proceedings of the 4th ACM International Workshop on Mobility Management and Wireless Access pp. 45-51, 2006.

[6] Marina1, Mahesh K. and Das, Samir R., "Ad hoc on-demand multipath distance vector routing," Wireless Communications and Mobile Computing, vol. 6, pp. 969-988, 2006.

[7] Tomar, G.S. "Modified Routing Algorithm for AODV in Constrained Conditions," Second Asia International Conference on Modeling & Simulation vol. iss. 13-15, pp. 219-224, May 2008.