Introduction

Today modern civilization is bestowed with enormous advancement of information technology and mobile communication. Internet technology has added much ease and speed in all spheres of our life, from office job to personal entertainment, emergency services like ambulance, natural disaster, military and police, Besides these applications it is expected in the near future that ad hoc networking will be more intensively used for different applications such as: Digital battlefield communications, movable base-stations (for military applications), range extension for cellular telephone. Recently mobile computing has enjoyed a tremendous improvement and enhancement. Excellent rise of processing power and computing power of mobile devices deserves the credit of such proliferation.

Mobile ad hoc network users share resources, applications and information quickly and without the need or possibility of any centralised infrastructure. Applications of ad hoc networks include the emergency services and military sectors. Mobile ad hoc networks come together to form a network without any centralised control. Because of the limited transmission range of wireless devices, data hops across the network from source to destination, makes use of intermediate nodes. Ad hoc network nodes accept responsibility for managing the network and routing of data. Routing of data, the most intensive task, is performed in a distributed manner. To send data to a destination who is not an immediate neighbor, a node must first find a route to that destination. Intermediate nodes co-operate to forward packets from the source to the destination.

AODV
The Ad Hoc On-Demand Distance Vector (AODV) routing protocol enables multi-hop routing between participating mobile nodes wishing to establish and maintain an ad-hoc network. AODV is based upon the distance vector algorithm. The difference is that AODV is reactive, as opposed to proactive protocols like DV, i.e., AODV only requests a route when needed and does not require nodes to maintain routes to destinations that are not actively used in communications. As long as the endpoints of a communication connection have valid routes to each other, AODV does not play any role.

Features of this protocol include loop freedom and that link breakages cause immediate notifications to be sent to the affected set of nodes, but only that set. Additionally, AODV has support for multicast routing and avoids the Bellman Ford counting to infinity problem. The use of destination sequence numbers guarantees that a route is fresh.

The algorithm uses different messages to discover and maintain links. Whenever a node wants to try and find a route to another node, it broadcasts a Route Request (RREQ) to all its neighbors. The RREQ propagates through the network until it reaches the destination or a node with a fresh enough route to the destination. Then the route is made available by unicasting a RREP back to the source.

The algorithm uses hello messages (a special RREP) that are broadcasted periodically to the immediate neighbors. These hello messages are local advertisements for the continued presence of the node and neighbors using routes through the broadcasting node will continue to mark the routes as valid. If hello messages stop coming from a particular node, the neighbor can assume that the node has moved away and mark that link to the node as broken and notify the affected set of nodes by sending a link failure notification (a special RREP) to that set of nodes.

The problem with AODV is that its capabilities are not used efficiently due to the presence of congestion. If there is congestion in the network the performance of this protocol degrades due to the non availability of another route towards the destination, which leads to more packet drops. Thus the performance of protocol affected.

Previous Works
Although the research on congestion analysis have been covered quite thoroughly in wired networks, research on congestion for wireless networks is still in the early age and there is always a need of new techniques for new technologies and methodologies. There are some proposed By Pass-routing protocols for MANET. However, these distribute traffic on one connection at a time for each source-destination pair. In other words, traffic is not diversified into multiple routes at the same time but focused on primary route. When this route is broken, other alternate routes are used for transmission. The D-LAOR (Song et al., 2004) delay based load aware on demand routing determines the optimal path based on the estimated total path delay and the hop count. D-LAOR also has a mechanism in new route selection to avoid a congested node by selectively dropping the route request (RREQ) packets. In Barry et al. (2004) initially congestion is handled locally and packets are re-routed using an appropriate non-congested route. In the event that this does not resolve the issue, congestion is dealt with by preventing source nodes from adding packets to the network by using routes which they know to contain congested nodes. Congestion management attempts to predict when congestion is about to occur and reduces the transmission rate at this time. Jacquer and Viennot (2004) proposes a probabilistic model for the network topology and the data traffic is proposed in order to estimate overhead due to control packets of routing protocols. In Dynamic Load-Aware Routing (DLAR) protocol (Lee and Gerla, 2000a) that considers intermediate node routing loads as the primary route selection metric. The protocol also monitors the congestion status of active routes and reconstructs the path when nodes of the route have their interface queue overloaded. A bandwidth efficient routing mechanism is introduced in which route discovery is based on delay variance and hop count (Sharma et al., 2006).

In CRP (Raghavandra and Tran, 2004), every node appearing on a route warns its previous node when prone to be congested. The previous node then uses a “bypass” route bypassing the potential congestion to the first non-congested node on the route. Traffic will be split probabilistically over these two routes, primary and bypass, thus effectively lessening the chance of congestion occurrence. In Congestion Avoidance Using Multipath Routing and Power Control in Mobile Ad Hoc Network (Pham, 2002), Utilization of multi-path routing mechanism to provide improved throughput and route resilience as compared with single-path one has been explored in details in the context of wired network.

The on-demand multi-path routing scheme is presented by Nasipuri and Das (1999) as a multi-path extension of dynamic source routing (DSR) (Johnson and Maltz, 1996), in which alternate routes are maintained so that they can be utilized when the primary one fails. Multiple Source Routing protocol (MSR) (Lee and Gerla, 2001) proposes a weighted round-robin heuristic-based scheduling strategy among multiple paths in order to distribute load, but provides no analytical modeling of its performance. Split multi-path routing (SMR), proposed by (Pearlman et al., 2002), focuses on building and maintaining maximally disjoint paths, however, the load is distributed in two routes per session. In AODV-BR (Lee and Gerla, 2000b), an extension of AODV (Perkins et al., 2003), multiple routes are maintained and utilized only when the primary roots fails. However, traffic is not distributed to more than one path. The secondary path is kept based on the assumption that each node over listens the broadcasts of its neighbor. Thus maintains a route towards the destination that can be used as an alternate route towards the destination. The positive effect of alternate path routing (APR) on load balancing and end-to-end delay in mobile ad hoc networks has been explored (Ogier et al., 2003).

The Reliable Adaptive Lightweight Multicast (RALM) (Tang et al., 2002) protocol is a multicast transport protocol that favors reliability and congestion control over throughput. RALM employs TCP-like congestion and error control mechanisms. RALM is a reliable congestion controlled protocol specifically designed for the multi-hop wireless ad hoc network. RALM performs TCP-like error and congestion control by picking one multicast receiver at a time in a round-robin fashion. The goal is to reduce control overhead while guaranteeing reliable multicast delivery. RALM achieves reliability by guaranteeing reliable data delivery to one multicast member at a time in a round-robin order. History-Aware Multi-path Routing (HAMR) protocol (Kim and An, 2003) introduces a session history as one of routing metrics. A session history implies how many times and how much duration a node is involved in communication sessions between mobile nodes in a network. The motivation of HAMR is that if a node’s session history is higher, the node will be more stable than nodes with lower histories. HAMR supports the establishment of multiple paths, which are selected in consideration for their session histories. HAMR’s approach sets the goal at reducing control traffic overhead and route reconfiguration time by decreasing frequent route re-starts due to route failures.

From the research survey of literature for congestion adaptive routing strategy, there are still many issues in applying by-pass routing techniques into mobile ad hoc networks that are to be covered. In most of the routing protocols, the traffic is distributed mainly on the primary route. It is only when this route is broken that the traffic is diverted to alternate routes. Clearly, load-balancing is not achieved by using these routing mechanisms. Although there are some routing protocols which distribute traffic simultaneously on multiple paths, there has not been a routing protocol which could dynamically cope with the changes of topology in ad hoc network.

Obviously, there is a demand for a congestion adaptive routing strategy that not only efficiently can balance the load on the network but also can cope with the dynamics of the network.

Congestion Adaptive Ad Hoc On Demand Distance Vector Routing Protocol
Congestion adaptive ad hoc on demand distance vector routing protocol copes the problem of load sharing in case of congestion dynamically with the change in network and this is done by means of the changing status of the probability of the nodes around a node. Our approach works in coordination with AODV rather than against it. In this approach every node warns its preceding node about the occurrence of congestion using congestion status parameters. This is done based on the condition whether the number of packets being queued at the interface queue of a node is more than 80% of its buffer size. If this is the case than the preceding node uses a secondary non-overlapping route to direct the incoming packets. That route must be non-congested. Traffic will split probabilistically over these two routes, primary and secondary, thus reducing the chances of congestion.

Our approach consists of following components:

Examining Congestion
In order to examine the congestion status of the route we used two parameters namely average packet delay and average queue length. Status of congestion depends on whether the number of packets being queued at the interface queue of a node is more than 80% of its buffer size. If this is the case than the preceding node uses a secondary non-overlapping route to direct the incoming packets. We further classify the congestion status into three levels. These are Green (G), Red (R) and Yellow (Y). A node is said to be in G state if it is not congested, in Y state if it is slightly congested and R state if it is congested. The next G node is the first G node at least two hops away downstream on the primary route.

Secondary Route Discovery
During normal route discovery in the AODV, each node takes advantage of the broadcasting nature of the wireless networking and listens to the packets that are transmitted by there neighboring nodes. From these packets node obtains alternate path information. When a node not a part of primary route listens a RREP packet not directed to it transmitted by a neighbor, it records that neighbor as a next hop to the destination in its alternate route table.

A node may receive numerous replies for the same route, so it chooses the best route among them and add them into their alternate route table. During congestion, alternate route table provides the secondary path towards the destination. However, after one hop route must be directed towards the primary route.

Data packets are passed through the main route unless there is congestion on the primary route. When a node detects congestion (for ex. Average packet delay is more and the average queue length is exceeded) it checks the updated hello message to find the next G node towards the destination and route the packets through that node. Data packets therefore can be delivered through alternate route and are not dropped when congestion occur.

Disseminating Congestion Status
A node periodically broadcasts to neighbors Hello packets with the additional information about the congestion status (len_) and a set of values {Accumulative probability of neighbor}.

Table 1:	Probability adjustment for congestion control

The purpose is that when a node receives a hello message from its next primary node, the node will be aware of the congestion status of neighbor node. If the node is R or Y then congestion is likely ahead if data continues to flow on the primary route, so it’s better to divert it through alternate path from alternate route table.

Traffic Ripping
At each node, the probability to send data on the primary link is initially set to 1. It is then modified periodically based on the congestion status of the next primary node and secondary route shows in Table 1.

Probability

P_node = 1 - (number of packets in interface queue/max. buffer size)
Or
P_node = 1 - len_/ AODV_RTQ_MAX_LEN
where:
AODV_RTQ_MAX_LEN is the maximum number of packets that we allow a routing protocol to buffer
len_: number of packets currently in the buffer

The congestion status is the accumulative status of every secondary node. We increased the amount of traffic on the primary link if primary link leads to less congested node and reduce otherwise.

If the probability p to forward the data on primary link approaches 1, the next node on main route is far from congestion or the secondary route is congested, so secondary route is deleted. However, if the primary route is congested then it is removed and the secondary route is selected for the data flow.

In this algorithm we implemented the concept used by CISCO routers to overcome the problem of congestion. In CISCO routers, each node looks after its own packet queue to find out the number of packets residing in it. If the number of packets reaches a certain percentage (80%) of the buffer size than it decides to block further intake in take of packets from the previous node. It sends a message to the previous node that its buffer size had reached a certain level and now any further intake will leads to the congestion. So kindly don’t send any packet. This concept is used in congestion adaptive ad hoc on demand distance vector routing protocol to decide when to stop further intake of packets in the buffer. After this decision is made node sends its previous node a sendError() message to inform it not to send further packet. Than sendHello() message is used to send the probability situation to the other nodes. Other node receives this information from the neighbor node and keeps it as the probability of the neighbor node P_nb. This information from the other nodes and also probability of the node is used to find the congestion status of the nearby node to find a best route towards the destination. This probabilistic information is than used to forward the incoming packets towards the destination.

These are the two new fields added to the hello message to pass the values of the node probability to the neighbor or vice versa. Status field shows the current probability status of the node.

Fig. 1:	Cumulative sum of generated packets vs event time

Fig. 2:	Average end to end delay vs packet size

Cumulative sum graph in Fig. 1 is an empirical cumulative distribution function. One more field is added into the header format of the hello messages as shown in Fig. 8. This is the congestion status of the current node which is calculated on the basis of the status of the length o the interface queue at that instance. This is probability is passed as neighbor probability to the neighbor nodes. Number of generated packets increases because now Hello messages also carries with them the neighbor probability. Therefore congestion adaptive ad hoc on demand distance vector routing protocol shows a rise in the cumulative sum of generated packets.

Fig. 3:	End to end delay vs packet sent time

Fig. 4:	Throughput of generated packet vs simulation time

Fig. 5:	Throughput of receiving bits vs. average simulation processing time

Fig. 6:	Throughput of sending bits vs average end to end delay

Packet size vs average end to end delay graph in Fig. 2 shows minimal/average/maximal delay in the whole network (simulation End to End delay). Here we have taken into consideration only the average simulation end to end delay versus packet size in order to find out the proportional effect of delay on the packet size. The graph shows a steep increase in average end to end delay with increases in packet size, this is due to the presence of control messages of ADOV protocol but as the packet size reaches to the level where it resembles the data packet (512 bits) the delay starts reducing. Here congestion adaptive ad hoc on demand distance vector routing protocol outperforms the existing AODV by reducing the end to end delay in packets (either control packets or the data packets).

Send events time vs end to end delays graph in Fig. 3 shows time when packets were sent (X-axis) vs end to end delay (Y-axis).

Throughput of Generated Packets Vs Processing Time graph in Fig. 4 shows throughput (bits) on Y axis and simulation time on X-axis. Throughput and processing times are calculated every TIME INTERVAL. Throughput of generating bits and processing times are calculated in the whole network. Because of buffer check those packets which are unnecessarily waiting in the buffer now finds alternate route to reach the destination. This causes a rise in the throughput of the generated packets. Congestion adaptive ad hoc on demand distance vector routing protocol definitely out performs existing AODV in this regard.

Figure 5 shows graph of Throughput of receiving bits vs. average simulation processing time in which throughput consistency is found in the modified approach.

For throughput of sending bits graphs in Fig. 6 shows delays of sent packets are calculated in the same time intervals as throughput is calculated. If a bit founds that the node it is being forwarded to is about to get congested in the near future by looking at the status of buffer, it starts moving itself through another route so that its chances of reaching the destination increases manifold thus reducing the average end to end delay.

Fig. 7:	Throughput of sending bits vs average simulation jitter

Fig. 8:	Congestion adaptive ad hoc on demand distance vector routing protocol hello message: header

Congestion adaptive ad hoc on demand distance vector routing Protocol had again outperforms the existing AODV. There is slight increase in delay with the increase in throughput but as compared to existing AODV it is far better

Throughput vs jitter graph in Fig. 7 shows throughput (bits) on X-axis and jitter on Y-axis. It's similar to throughput vs delay graphs. If S(i) is the time packet i was sent from the sender and R(i) is the time it was received by the receiver,

jitter(i) = [(R(i+1)-S(i+1))-(R(i)-S(i)]. Congestion adaptive ad hoc on demand distance vector routing protocol has reduced simulation jitter many fold compared with the existing AODV (Fig. 8). This simulation study has been conducted is school of information technology, Rajiv Gandhi Technological University and Samrat Ashok Technological Institute.

Discussion

We have simulated above said protocol that utilizes a well known schema being used by the CISCO routers for the load shedding purpose. This scheme can be used with any other on-demand routing protocol to improve reliable packet delivery in the case of route congestion. We hadn’t temper with the basic functionality of the existing protocol. The decision when to find an alternate path for the packet transmission is taken in case of interface queue is full more than 80% of buffer size is chosen independently by the existing AODV in the manner it is doing normal packet transmission. The secondary path for congestion avoidance uses probabilistic approach. The secondary path is discovered on the basis of the congestion status of the neighbor node and the next node on the primary route. Probability is used to split the traffic between the primary route and the secondary route. The secondary path provides an alternate route for data packets to flow up-to the destination without making another attempt for route discovery in case the congestion is likely to happen in the primary route. These routes are utilized only for data packet delivery. As a case study we compared our scheme with the existing AODV and measured performance improvements. Results provided by the NS2 simulator shows that this scheme perform well under low traffic. The number of packet dropped due to congestion is reduced with congestion adaptive ad hoc on demand distance vector routing protocol because of the presence of an alternate route towards the destination through which node can forwards packets to the destination.

We measured mechanism performance on reactive routing protocol AODV along metrics such as cumulative sum of generated packets, throughput, end to end delay, jitter and processing time in high mobility environment.

For congestion adaptive ad hoc on demand distance vector routing protocol in high mobility, we observed that the packet delivery ratio for congestion adaptive ad hoc on demand distance vector routing protocol is increased manifold. It can be seen from the figures that in the high mobility scenario the packet delivery ratio of congestion adaptive ad hoc on demand distance vector routing protocol is almost constant and nearly 100%. However, the packet delivery ratio of AODV suffers severely when 20% of the nodes drop the data packets. It should also be noted that in the case of throughput of receiving bits the performance of AODV gets better. When the nodes move constantly their overall effect becomes more significant. Average end to end delay in case of congestion adaptive ad hoc on demand distance vector routing protocol for different packet size has reduced as compared with AODV. Throughput of generated packet in case of congestion adaptive ad hoc on demand distance vector routing protocol against simulation time is constant throughout as compared with the AODV because of the presence of an alternate path for every node through which it can send packets without any delay.

Purpose of the simulation study of congestion Adaptive routing protocol is to provide strength to the protocol by verification of the results in comparison with the most popular routing protocol AODV in mobile ad hoc network environment.

This study shows that Congestion Adaptive routing protocol works batter the AODV high mobility scenario and provide good packet delivery ratio. It is found that in the high mobility scenario the packet delivery ratio of congestion adaptive ad hoc on demand distance vector routing protocol is almost constant and nearly 100%. However, the packet delivery ratio of AODV suffers severely when 20% of the nodes drop the data packets, this provide consistency of network which is very important aspect in network planning.

Future Work
In our simulation model we incorporate few parameters for the probabilistic evaluation of congestion. These are: the average queue length and based on this length the probabilities of the next node on the primary route and the neighbor node. However, there are other parameters also on which congestion depends. These may be retransmit time of packet, standard deviation of packet delay, buffer space etc. Simulation results based on these parameters can also be evaluated. Above technique can also be checked with different network scenarios i.e., with more number of mobile nodes, higher mobility rates, for varying packet loads.

Additionally this scheme can further be evaluated using more detailed and realistic channel models with fading and obstacles in the simulation.