Keywords
|
| MANET, AODV, routing, NS2, packet delivery ratio . |
INTRODUCTION
|
| Wireless multi-hop packet networks that do not have any fixed infrastructure are called as Ad hoc networks (AHNs) [1]. In an adhoc network, which constitutes of only terminals, each terminal acts like a router i.e. all the terminals in the network also provide relaying service to each other. Some of the advantages of such networks are |
| ? Robustness, |
| ? Rapid deployment, |
| ? Flexibility and |
| ? Inherent support for mobility. |
| AdHoc networks can be used as a stand-alone autonomous network that is capable of providing connectivity within a group. This type of networks is required for applications such as shared desktop meeting, disaster recovery, or in various military applications. However, this technology is not being used for commercial purpose very commonly. |
| In the future, ad hoc networks probably form the outermost region of the internetwork, where a wired backbone connects both the fixed local area networks and the mobile (both the fixed infrastructure and the ad hoc) networks. Whereas the base stations of a fixed infrastructure networks are directly connected to the core, an AHN is typically connected through a satellite link or a terrestrial switch (fixed wired connection point, or mobile radio link). This vision, however, requires still some further developments in ad hoc networking. |
| Latest research and new applications in the area of AdHoc networks is driving the researchers to carry out their work in this area leading to new achievements. This research is mainly driven by new applications and at the same time, new applications are created by the continuous research initiatives in the field of AdHoc networks. Although this network concept has been originally considered in the context of packet radio networks [2] earlier, it has become very popular again during the past few years. The pioneer research work is going on within the IETF?s MANET working group [3,4] for standards and the research in new directions is very active throughout the world. Packet routing is a very hot topic amongst researchers in the fundamental research being done in AdHoc networking. In fixed infrastructure mobile networks routing is, for the most part, an engineering problem (implementation of hand-overs etc.), whereas in ad hoc networks it is essentially theoretical [5]. The problems and their solutions considering packet routing are closely related to those widely studied [6] in the case of ordinary fixed networks, but also completely new fundamental challenges have emerged due to the peculiar features of AHNs, such as: |
| ? Dynamic network topology and structure |
| o Nodes may join or leave the network |
| o Some or all nodes may be mobile |
| ? Limited bandwidth |
| ? Constrained power |
| ? Broadcast nature of transmission |
| Mobile wireless devices are becoming popular day-by-day due to their flexibility, power, portability and anywhere, anytime service [7]. Due to this, need of efficient data transfer protocols has aroused to facilitate the communication between these wireless devices. Various routing protocols are employed for transferring the data packets between the nodes in Mobile Ad Hoc Networks (MANETs) and Wireless Mesh Networks (WMNs). Ad hoc On-Demand Distance Vector (AODV) protocol is one such routing protocol [8,9] and is very popular nowadays for MANETs and WMNs. It has also gained a lot of importance as it a standard protocol and many other protocols are based on it. Now, AODV has been standardized by the IETF MANET working group as experimental RFC3561. |
AODV ALGORITHM
|
| Each AODV node builds and maintains routing table entries containing the destination sequence number, next hop node in the shortest path to the destination, and the distance to the destination. A destination sequence number is created by the destination for any route information it sends to the requesting nodes, using sequence numbers eliminates looping and indicates the age of routing information. AODV is based on the distance vector algorithm, but unlike other proactive distance vector algorithms, does not use periodic or triggered updates to disseminate routing information. With AODV, route requests are made only when needed and nodes are not required to maintain routes to destination that are not actively used in communications. Routing tables are built using route discovery and maintained by route maintenance. |
Route Discovery
|
| When a node to send a packet to destination which it does not have a routing entry, it broadcasts a route request (RREQ) packet. To prevent unnecessary broadcasts of RREQs, the source node uses and expanding ring search. In an expanding ring search, the source node initially uses a time-to-live (TTL)-Start in the RREQ packet IP header and sets a timeout for receiving a reply (RREP). Upon timeout, the source retransmits a RREQ with TTL incremented by TTLincrement, this continues until TTL reaches a specified maximum. The source will retransmit the RREQ with the highest TTL if it does not receive ant reply within the timeout period. A node receiving a RREQ establishes a reverse path to the sources of the RREQ in their routing table, and either replies to the RREQ if they already have an entry for the destination or forwards the RREQ if there is no routing information to the destination in its routing table. Finally the destination will reply. Nodes receiving a RREP setup a path to the destination. And in this way, desirable routes are discovered. |
Route maintenance
|
| An existing routing entry may be invalidated if it is unused within a specified time interval, or if the next hop node is no longer reachable. In that case, the invalidation is propagated to neighbors that have used this node as their next hop. Each time a route is used to forward a data packet, its route expiry time is updated. When a node detects that a route to a neighbor is no longer valid, it removes the invalid entry and sends a route error message to the neighbors that are using the route. The nodes receiving route error messages repeat this procedure. Finally, the route requests a new route if it still needs the route. |
| AODV combines the use of destination sequence numbers in DSDV with the on-demand route discovery technique in DSR to formulate a loop-free, on-demand, single path, distance vector protocol. Unlike DSR, which uses source routing, AODV is based on hop-by-hop routing approach. Each node maintains a routing table, which contains a destination address, sequence number of destination; hop count (number of hops to reach the destination), and next hop to reach the destination and expiration timeout. |
| Multipath routing algorithm AOMDV offers better performance relative to AODV under a wide range of mobility and traffic scenarios. It has been observed that AOMDV offers a significant reduction in delay, often more than a factor of two. It also provides up to about 20% reduction in the routing load and the frequency of route discoveries. In general, AOMDV always offers a superior overall routing performance than AODV in a variety of mobility and traffic conditions. |
| In this paper, we present the results of an improved AODV based routing algorithm which is optimized for small area ad-hoc networks. The algorithm is compact and needs less hardware to implement in comparison to its counterpart AODV and AOMDV. At the same time, the performance of the algorithm is comparable and even better than that of AODV and AOMDV for small areas. |
THE ALGORITHM
|
Features
|
| AODV is an ad-hoc routing protocol. It is able to discover a route through a network of computers. |
| ? Creates routes on-demand |
| ? Built for mobile networks |
| ? Loop free with quick convergence |
| ? Can scale to handle a few hundred nodes |
| ? Can be integrated into the existing protocol stack |
| When AODV was designed it incorporated many features designed to maximize performance at the cost of added complexity. The features of Link layer detection of AODV are as following:- |
| ? Link layer detection allows a sending node to detect if a unicast packet is successfully received. |
| ? In simulations, AODV using link layer detection provides amazing performance. |
| ? Currently it is impossible to access link layer feedback information in off the shelf hardware. |
| ? Current implementations use periodic hello messages to detect local link connectivity. |
| ? Hello messages cause a large amount of control overhead. Each node must periodically send broadcast packets. Each receiving node must also process them. |
| Modified - Ad hoc On-Demand Distance Vector (M-AODV) is a simple algorithm based on AODV which has performance nearly same as that of AODV but its main advantages are its simplicity, light weight and no routing overheads. AODV and AOMDV specification contains many sections prone to erroneous programming. M-AODV is a simplified variant of AODV specification which removes all but the essential elements of AODV. |
| M-AODV removes the following items from the AODV specification. |
| ? Hello Messages |
| ? Hop Count |
| ? Gratuitous RREP |
| ? Precursor lists |
| ? RERR |
| ? Sequence Numbers |
Operation
|
| Whenever an M-AODV router receives a request to send a message, it checks its routing table to see if a route exists. If a route exists, the router simply forwards the message to the next hop. Otherwise, it saves the message in a message queue, and then it initiates a route request to determine a route. |
| To accomplish this M-AODV requires slightly different operation when compared to AODV. It is able to do this by requiring only destinations to reply to RREQ and uses end-to-end hello messages to maintain routes. Removing sequence numbers requires the destination to respond to RREQ; no intermediate nodes may respond. This also eliminates the need for Gratuitous RREP since all routes will be bidirectional. Since the destination will only respond to the first RREQ it receives the “best” (fastest) route is always chosen regardless of the number of hops. To perform route maintenance route lifetimes are only updated by the reception of packets and not the sending of packets. This requires the destination to occasionally send a packet to the source. If data traffic is unidirectional periodic messages (connect) are sent to maintain the route. If data communications are bidirectional, no additional overhead is needed. Using this end-to-end strategy, hello messages, RERR and precursor lists are not needed. |
| When a break in the route occurs, the source will stop receiving messages from the destination. In figure 1c, node 4 leaves the route. After a period of time node 1 detect the route is broken because it has not received a message from the destination and will reinitiate route discovery if the route is still needed. |
RESULT AND DISCUSSIONS
|
| The entire simulations were carried out using NS-2.35 network simulator which is a discrete event driven simulator developed at UC Berkeley as a part of the VINT project [10]. The prime goal of NS-2 is to support Research and Education in networking. It is suitable for designing new protocols, comparing different protocols and traffic evaluations. NS-2 simulator developed as collaborative environment of networks is distributed as open source software. Large number of Institutes and Researchers use it as network simulator tool for prototype of network simulation in research studies [11,12]. NS-2 versions are easily available and are compatible with Linux, Solaris, Windows and Mac OS X. |
| The procedural flow involved in NS-2 simulation programming is as follows- The user has to program with OTcl script language to initiate an event scheduler, set up the network topology using the network objects and informs traffic sources to start and stop transmitting packets through the event scheduler. OTcl script is executed by NS-2. The simulation results from running this script in NS-2 include one or more text based output files and an input to a graphical simulation display tool called Network Animator (NAM). Text based files record the activities taking place in the network. It can be analyzed by other tools such as „Perl? or „Gwak? to evaluate the results. |
| NAM is an animation tool for viewing network simulation traces and real world packet traces. It has a graphical interface, which can provide information such as number of packets drops at each link. We can either start NAM with the command 'nam <nam-file>' where '<nam-file>' is the name of a NAM trace file that was generated by NS, or one can execute it directly out of the Tcl simulation script for visualization of node movement. Fig 4 shows the screen shot of a NAM window with important functions. |
| The performance of Ad hoc network was studied under varying condition of the area with all other simulation parameters fixed. Two models used in the simulation study of evaluation of on demand and table driven protocols for Ad hoc networks are as follows- |
| 1. Mobility Generation Model. It is used to study the effect of mobility of nodes on overall performance of the network. |
| 2. Traffic Generation Model. It is used to study the effect of traffic load on the network. |
| Implementation study begins with simulation of Network Environment. This requires setting of simulation network parameters. These parameters are depicted in the Table 1. |
| To analyze the effect of variation of area, area was varied from 50 m2 x 50 m2 to 500 m2 x 500 m2 with all other simulation parameters as same. The results are presented in tabular and graphical form in Table 2 and Figure 5, respectively. |
| As it can be seen in the Table 2, the algorithm M-AODV gives better results that AODV and AOMDV for smaller field areas. But as the field area increases, its performance decreases at a very fast rate. This is also visible in the results shown graphically in Fig. 5. |
| A more recent research topic for MANETs could be multipath routing protocols. Multipath routing protocols establish multiple disjoint paths from a source to a destination and are thereby improving resilience to network failures and allows network for load balancing. These effects are particularly interesting in networks with high node density (and the corresponding larger choice of disjoint paths) and high network load (due to the ability to load balance the traffic around congested networks). The benefits of multipath routing protocol are fault tolerance, load balancing, bandwidth aggregation and reduced End-to-End delay. |
| For robust scenario where mobility is high, nodes are dense, area is large, the amount of traffic is more, network pattern sustains for longer period and number of maximum connections is small, AODV performs better. To achieve lower routing overhead, better throughput, lower end-to-end delay, to be more resilient to route failures and alleviate congestion for robust scenario where mobility is high, nodes are dense and traffic is more and number of maximum connections is large, AOMDV is a better choice. |
| Therefore, AODV and AOMDV are currently amongst the easiest and most widely implemented MANET protocol. However, their specification still contains many sections prone to erroneous programming. MAODV is a simplified variant of AODV specification which removes all but the essential elements of AODV. From the results, it can be seen that MAODV has the same performance as AODV or AOMDV for smaller area specifications, with minimum routing overheads and average path length in comparison to both AODV and AOMDV. |
CONCLUSIONS
|
| In this paper, we have modified the AODV algorithm to make it compact and occupy less hardware to implement. We have demonstrated that the algorithm is having very good efficiency in terms of Packet Delivery Ratio, which is comparable to AODV and AOMDV. For small areas, the algorithm gives better results that AODV or AOMDV. However, if the area increases above 200 m2 x 200 m2, the efficiency of the algorithm falls down considerably but for small areas the algorithm performs pretty well. |
Tables at a glance
|
 |
|
| Table 1 |
Table 2 |
|
Figures at a glance
|
 |
 |
 |
| Figure 1 |
Figure 2 |
Figure 3 |
|
 |
 |
 |
| Figure 4 |
Figure 5 |
Figure 6 |
|
References
|
- Charles E. Perkins (Ed.). Ad Hoc Networking, Addison-Wesley, December 2000.
- John Jubin and Janet D. Tornow.The DARPA packet radio network protocol.Proc. of IEEE, 75(1):21–32, 1987.
- IETF. Mobile ad hoc networks working group. http://www.ietf.org/html.charters/manetcharter.html.
- https://www.ietf.org/rfc/rfc3561.txt
- Ram Ramanathan and Jason Redi, “A brief over view of Ad hoc network: Challenges and direction”, IEEE Communication Magazine, pages 20-22, May 2002.
- S. Ramanathan and Martha Steenstrup, “A Survey of Routing Techniques for Mobile Communications Networks”, ACM/Baltzer Mobile Networks and Applications, 1(2): pages 89–103, 1996.
- E. M. Royer and C.K. Toh, “A review of current routing protocols for ad hoc mobile wireless networks”, IEEE Personal Communications, 6(2): pages 46– 55, April 1999.
- M.K. Marina and S.R. Das, “On-demand multipath distance vector routing in ad hoc networks,” Proceedings of the International Conference for Network Procotols (ICNP), pages 14–23, Nov. 2001.
- Charles E. Perkins, Elizabeth M. Royer, Samir R. Das, “Ad-hoc On-demand Distance Vector Routing”, IETF Draft,(NMCSA), pages 90-100 October 1999.
- A tutorial named NS by example: http://nile.wpi.edu/NS/, visited 2006-07-22.
- NS2 installation instruction under windows operating system, http://140.116.72.80/~smallko/ns2/setup_en.htm, visited 2006-07-22.
- 5th VNIT/NS Simulator Tutorial/Workshop slides and the NS Manual [2009].
|
Menu