Ad-hoc wireless networks are usually defined as an autonomous system of nodes connected by wireless links communicating in a multi-hop fashion. The benefits of ad-hoc networks are many, but the most important one is their ease of deployment without centralized administration or fixed infrastructure, thereby enabling an inexpensive way to achieve the goal of wireless communications [1]. One of the fundamental tasks that an ad hoc network should perform is congestion control and its main objective is to limit the delay and buffer overflow caused by network congestion and provide better performance of the network.
In adhoc networks, Routing protocols can be divided into proactive, reactive and hybrid protocols, depending on the routing topology. Proactive protocols are typically table-driven. An example of this type includes DSDV and WRP [1 and 4]. On contrary reactive or source-initiated on-demand protocols do not periodically update the routing information. It is propagated to the nodes only when necessary. Examples of this type include DSR, AODV and ABR [1, 2 and 3]. Hybrid protocols make use of both reactive and proactive approaches. Example of this type includes TORA, ZRP [1 and 5].
We note that the existing routing protocols are not having congestion control techniques and they are not considered, when establishing a new route and they remains the same until mobility or failure results in disconnection. Our motivation is that congestion is a main cause for packet loss in MANETs. A new perspective on this problem might be to realize congestion control in the MAC or network layer. After all, it might make sense to tackle the problem from where it emerges. An exceedingly high network load is a problem closely associated with medium access and packet forwarding. [8].
AODV Routing Protocol
The Ad Hoc On-Demand Distance Vector (AODV) routing protocol is an adaptation of the DSDV protocol for dynamic link conditions [2, 4 and 10]. Every node in an Ad-hoc network maintains a routing table, which contains information about the route to a particular destination. Whenever a packet is to be sent by a node, it first checks with its routing table to determine whether a route to the destination is already available. If so, it uses that route to send the packets to the destination. If a route is not available or the previously entered route is inactivated, then the node initiates a route discovery process. This protocol performs Route Discovery using control messages route request (RREQ) and route reply (RREP) whenever a node wishes to send a packet to destination. To control network wide broadcasts of RREQs, the source node uses an expanding ring search technique. The forward path sets up in intermediate nodes in its route table with a lifetime association using RREF. When either destination or intermediate node moves, a route error (RERR) is sent to the affected source nodes. When source node receives the route error message (REM), it can reinitiate route discovery if the route is still needed. Neighborhood information is obtained from broadcast Hello packet [2 and 9]. Since AODV has no congestion control mechanisms, routing may let a congestion happen which is not handled by congestion control. It may also lead to the following problems (i) Long delay (ii) Many packet losses (iii) Low throughput.
The above problems become more visible in large-scale transmission of traffic intensive data such as multimedia data where in congestion is more probable and the negative impact of packet loss on the service quality is of more significance [6]. Unlike well-established networks such as the Internet, in a dynamic network like a MANET, it is expensive, in terms of time and overhead, to recover from congestion. Our motivation is to clear that congestion which is a dominant cause for packet loss in MANETs. Typically, reducing packet loss involves congestion control running on top of a mobility and failure adaptive routing protocol at the network layer [6].
We use early detection techniques to detect the congestion well in advance [Section II.C]. We present a method to find alternate bidirectional path to control the congestion [Section II.D]. Ns2 simulation is used to analyze the results and prove the performance [Section III].
EARLY DETECTION OF CONGESTION AND CONTROL ROUTING PROTOCOL
Early detection of congestion and control routing protocol (EDAODV) is a uni-cast routing protocol for MANET. We present a complete design with an in-depth evaluation for this routing protocol. In EDAODV, every node appearing on a route warns its neighbor nodes when prone to be congested.
The predecessor and successor nodes on the primary path try to find alternate path bi-directionally. After finding an alternate path, the previous node uses an alternate route for bypassing the congestion path to the first non-congested node on the primary route. EDAODV consists of the following components
Route discovery
Early congestion detection
Bi-directional path discovery
We start with an example to get used to the concept of alternate path and then discuss the essential components in detail.
A. Example
S
2
3
S
S
1
D
S
(a)
40 60 60
D
3
2
1
S
S
4
S
30 30 30
(b)
Redirection
S
1
2
3
D
4
5
6
(c) Redirection
S
S
1
2
3
D
4
S
(d)
S
S
1
2
3
D
4
S
(e)
Fig 1: Example of successive local route redirection operations.
A
B
C
D
E
C
B
A
D
Fig 2: Basic cases of alternative sub-paths.
A simplified example is illustrated in Fig. 1. A route S ->1 -> 2 ->3-> D is initially found for the source S to the destination D. This route is called the primary route from S to D. as shown in Fig. 1(a). Every packet follows the primary route. Thus, nodes 2 and nodes 3 will continuously be used in forwarding the traffic, leaving the other nodes free from the traffic load. As a result, node 2 detects that congestion is likely to occur and sends a warning to its neighborhood, they are aware of this situation as shown in Fig 1(b). In response, node 1 applies congestion aware routing scheme will try to divert the traffic to other nodes based on route redirection. In Figure 2 shows two basic redirections. In case 1, nodes A, B, and C are three consecutive nodes on the path for S-D connection. Node X is a nearby node which is a common neighbor of all three nodes. In a network that is dense enough to maintain continuous network connectivity, this scenario could occur frequently. As the congestion status packets (CSP) are successively broadcast by the B, node X can overhear the packet. With careful bookkeeping, node X can identify this scenario and realize that it can replace node B for the connection, namely, the sub-path A->B->C can be redirected to A->X->C. If node X sees the current congestion status of node B, and find out that the difference of congestion status at node B and itself is significant enough ( congestion level of X is less than that of B), node X will do the redirection. In case 2 shown in Figure 2, we suppose that the congestion difference between B and X is significant enough. The same is true between node Y and B. As a CSP packet travels along nodes A, B and C, node X will find out that node B needs to be bypassed. Node X also knows that it is a neighbor of both node B and its up-stream on-route neighbor, namely, node A. Similarly, node Y will find out that node B needs to be bypassed and node Y is adjacent with the down-stream on-route neighbor of node B, namely node C. We see that even from the locally overheard information, nodes X and YQ can distinguish their different roles. It is up to node Y to find the existence of node X. To facilitate this process, Y broadcasts a message saying that "Node B needs help, and I am its down-stream helper, who is its up-stream helper?" If the up-stream helper, node X, gets this message, it replies with an acknowledgement. The wireless link between X and Y is thus identified. The two helper nodes will do the redirection to replace the A-B-C sub-path by the new A-X-Y-C path.
Consider the example shown in Fig 1(a), nodes 2 and 3 both fall zone II level congestion. After one redirection of case 2, node 2 is bypassed and the S->1->2->3->D path becomes S->1->4->5->3->D, shown in Fig 1(c). Then, after a case 1 redirection takes effect, the new S->1->4>5->6->D path will replace the original one, as shown in Fig 1(d).
B. Route Discovery
The source discovers the route to the destination; it broadcasts an RREQ packet toward the destination, the destination responds to the first arrived RREQ and sends back an RREP packet. The RREP will travel back in the path the RREQ previously travelled and adds a new entry in its routing table. This path becomes the primary route between the source and the destination. Each node has two routing tables, primary table (denoted as PRT) and alternate path routing table (denoted as ART). PRT is used to direct packets on the primary route, while ART directs packets on alternate path routes. If ART=0 for a node that does not appear on an alternate path route of any connection and this will be discussed in Section II.D. For PRT, the main parameters are described in Table I. An entry in PRT is unique to a destination node. We denote by PRT[X, D] the entry for destination D in the routing table of node X. For instance, the entry for node regarding destination D in Fig 1(e) is PRT[ 1,D]= (S, D, Node 2, hop count 1, Zone II, Node D, hop count 3, Node D, Node 4,Zone I ). On receipt of an RREP initiated by destination D, a node X adds a new entry for D, or replaces the old entry with the new one, into PRT. The entry for D is removed from PRT if no data packet is destined for D.
Table I: Primary path Routing table of a Node
Parameters
Description
Src
Source
Dst
Destination
Seq_no
Sequence Number of a Node
H_count
Hop count of a Node
N_Node
Next node on primary path
NCongest_status
Congestion status of next node on primary path
TableII: Neighbors table for a Node
Parameters
Description
Neighbors_list
Neighbors information
Neighbor_id
Neighbor_hop
Neighbor_Congst_status
C. Early Congestion Detection Techniques
Congestion in a network may occur at any interval, if the load on the network (the number of packets sent to the network) is greater than the capacity of the network (The number of packets network can handle) When the number of packets coming to a node exceeds its buffer capacity; the node becomes congested and starts losing packets. Congestion metric can be used at a node to detect the congestion well in advance otherwise it may be harmful if the buffer is almost full. We use base design of Random Early Detection queue model for constructing buffer [10] as shown in Fig.2.
Safe zone
Zone I
Likely to be congested zone
Zone II
Congested zone
Zone III
Minth
Maxth
Fig.2. Buffer Classification
The expression (1) and (2) are used to set the Minimum threshold and Maximum threshold values
To detect the congestion well in advance, compute the average queue size as
Where wq, the queue weight is a constant parameter (wq=0.002 from RED queue experimental result [11]) and Inst_Que is an instantaneous queue size.
In our early detection model, we introduce Queue_status of actual queue size over average queue size given by Equation (4), which reflects the heaviness of the incoming traffic. Based on the Queue_status, the mobile node can get useful information about the incoming traffic. If the Queue_status value is large, the incoming traffic becomes bursty traffic. The continuous growth of the Queue_status indicates that the incoming heavy traffic is beyond the mobile node's buffer capacity and buffer overflow is imminent.
If Queue_status < minimum threshold, the incoming traffic is low and queue is in safe zone.
If Queue_status > minimum threshold and Inst_Que < maximum threshold, the incoming is above average and queue is in likely to be in congested zone. If Inst_Que > maximum threshold, the incoming traffic is heavy and queue is in congested zone as shown in algorithm I, given in Fig.3.
Algorithm I: Early Congestion detection
//initialization
begin
Avgque := 0
Inst_Que := 0
Minth := 0.25 * buffer_size
Maxth := 0.75 * buffer_size
Warn_line := buffer_size / 2
For each arriving packet in the queue
Increment Inst_Que by 1
Calculate average queue size
If the queue is not empty
Avgque : (1-wq) Avgque+ Inst_Que * wq
If Inst_Qque is greater than Avgque
Queue_status := Inst_Que - Avgque
Else
Queue_status := 0
If Inst_Que is greater than warn_line
If Queue_status is grater than Minth and Inst_Que is less than Maxth)
Call procedure Create CSP
Else
Queue is in congested zone
For each departing packet in the queue
Decrement Inst_que by 1
End
Fig.3. Early Congestion detection
D Congestion Aware Routing
A primary path of a node predicts its congestion status and periodically broadcasts a congestion status packet (CSP) with TTL = 1.We require adding fields to the congestion status packet (CSP) P. they are Source, Destination, Hop Count, Sequence Number, Congestion Status and Neighbors information. For a packet P, we use S(P),D(P),Seq(P) Hop(P),Cong(P), and N_list(P). We use S-D(P) to represent the source-destination pair of the flow that the packet belongs to. A Routing table is maintained at each node. Each entry in the table contains the following information source destination pair, sequence number, Hop count, Next node on primary path, Congestion status of next node on primary path and Neighbors_list. Each entry represents a traffic flow in the network, identified by the source-destination pair field as shown in Fig 4
Fig.4. Create congestion status packet (CSP)
Algorithm II: Create CSP of at Likely to be congested node X
Begin
Cong:= current congestion status of X
for (each destination D in routing table RT[X])
do
If X falls ZoneII Congestion
S := Src
D :=Dst
Seq := Seq_no
Hop := H_count
N_list: = Neighbors_list
Endif
End do
add (Cong, [S,D,Seq,Hop,N_list] to packet p
End
When the neighbors receive a CSP packet from its primary path node of X regarding destination Dst, neighbors will be aware of the congestion status of X. Once neighbor receives (CSP) packet P, it checks its source and destination information in their routing table. If the packet is freshest to this node, a new entry is added in its routing table. Otherwise, let E be the routing table entry representing the flow. We use Src(E),Dst(E), Seq_no(E),and Neighbors_list(E) to represent its four fields. The Neighor_list(E) only collects packets of the flow carrying the same sequence number identified by Seq_no(E). Thus, if Seq(P) is less than Seq_no(E), the packet is ignored. If Seq(P) is greater than Seq_no(E), Seq_no(E) is updated to Seq(P) and current entries in Neighbors_list(E) are all deleted. Only if Seq(P) is equal to Seq_no(E), a new entry representing packet P is added to neighbors list. The new entry has three fields as Neighbor_id, Neighbor_hop, and Neighbor_congst_status, The congestion status field records the current congestion level at transmitting node of the packet. The detailed description of EA-SHORT is given algorithm shown in Fig.5. Now that the sub path at a node has been found, data packets coming to this node are passing over the sub path that which is mainly because the primary route is congested and does not want to impose any unnecessary burden on the primary nodes
PERFORMANCE STUDY
EDAODV is implemented using the Network Simulator (Ns2.33) [9]. A comparison of EDAODV's performance to
AODV routing protocols in MANET is made. Thus the observation is presented below as
A. Performance Metrics
To compare the two protocols, the following metrics are used:
When node N receives packet P from Node X,
BEGIN
Lookup S-D(P) in routing table;
IF no match, add entry E': Src-Dst(E'):=S-D(P),
Seq_no(E'):=Seq(P), Neighbors_list(E') initialized with first
Entry <Neighbors_id(P), Neighbors _hop(P), Neighbors_Congst_status(P)>. GOTO END;
(Assume a match is found at entry E.)
IF Seq(P) is less than Seq_no(E), ignore P. GOTO END;
IF Seq(P) is greater than eq_no(E), update E as the following:
Seq_no(E):=Seq(P), Neighbors_list(E) reset as having only one
Entry < Neighbors_id(P), Neighbors _hop(P), Neighbors_Congst_status(P)>. GOTO END;
IF Seq(P) is equal to Seq_no(E), do the following:
Add entry < Neighbors_id(P), Neighbors _hop(P), Neighbors_Congst_status(P)> into Neighnors_list(E);
IF Neighbors_list(E) has three entries A, B, C satisfying the following conditions, a better sub-path is found.
1)Neighbors_hop(C) is equal to Neighbors_hop (B)+1 is equal to Neighbors_hop (A)+2;
2) Neighbors_Congst_status(node N) is greater than and equal to MAX(Neighbors_Congst_status (A), Neighbors_Congst_status (C));
3)( Neighbors_Congst_status (node N)- Neighbors_Congst_status (B)) is greater than and equal to 2.
Activate this new subpath. Delete entry E from Routing table. GOTO END;
.IF Neighbors_list(E) has two entries A and B,
such that Neighbors_hop (B)is equal to Neighbors_hop (A)+1 and Neighbors_hop (node I) is greater than and equal to MAX(Neighbors_Congst_status (A), Neighbors_Congst_status (B)+2), add this indicator I in the WaitingIndicator list: candidate(I):=B,
Seq(I)= Seq _no(E), Src-Dst(I):=Src-Dst(E). GOTO END;
IF Neighbors_list(E) has two entries B and C,
such that Neighbors_hop (C) is equal to Neighbors_hop (B)+1 and Neighbors_Congst_status (node N) is less thab and equal to MAX(Neighbors_Congst_status (B)+2, Neighbors_Congst_status (C)), node N broadcast one SHORT
informing packet Q as follows: candidate(Q):=B, Seq(Q):=Seq_no(E) Src-Dst(Q):=Src-Dst(E);
When node I receives a SHORT informing packet Q,
BEGIN
1. Compare fields of Q with any valid entry in
WaitingIndicator list;
2. IF there is no match, ignore packet Q;
ELSE a better subpath is found. Activate this
new subpath by updating routing tables;
ENDPacket Delivery Ratio (PDR): The ratio between the number of packets received by the destination and the number of packets sent by the source.
End-to-End Delay: The delay a packet suffers from leaving the sender to arriving at the receiver.
B. Simulation Configuration
Routing
EDAODV, AODV
MAC
802.11
Bandwidth
2 Mbps
Terrain
1400m,1400m
Nodes
100
Antenna
2 Ray Ground
Node Placement
Uniform
Data traffic
CBR
Simulation Time
600 seconds
Queue size
50 packets
Load (Flows)
10 - 50 Flows
Load (Pkts/Seconds)
4 - 16 Pkts/S
Max Sped (m/s)
0 - 10 meter/seconds
Pause Time(s)
30 seconds
C. Varying Number of Connections
(a) Packet delivery ratio
(b) End to End delay
Fig.6. Performance when number connections (source and destination) change.
In this simulation, the number of connection (source and destination) is varied from 10 to 50, CBR sending rate 4 packets per second, maximum node speed 10 m/s and pause time 30s.
Fig.6 (a) and Fig.6 (b) shows the packet delivery ratio and the End-to-End delay for EDAODV and AODV respectively. When the number of flows is less than 20, EDAODV does not show much improvement over AODV. When the number of flows increases from 20 to 50, the packet delivery ratio of AODV has a sudden fall from 87% to 14 %. When compared with the above packet delivery ratio, the figures of the EDAODV fall only a gradual fall from 91% to 40% as shown in Fig.6 (a).
One observes that the End-to-End delay between AODV and EDAODV as shown in Fig.6 (b), when the number of flows increases from 20 to 50. The End-to-End delay has increased from 0.7 seconds to 7.9 seconds. The corresponding variation for EDAODV is from 0.6 to 5.5 when the number of flows increases, the network carries more traffic. The AODV incurred the heaviest traffic by increasing traffic, but EDAODV seemed unaffected by increasing traffic because it resolved congestion by predicting its occurrence and adaptively distributing it over the primary and alternate paths. Thus, EDAODV significantly improves the performance of AODV in all aspects, instead of trading off one for another.
D. Varying CBR Load
In this simulation, the number of connection (different source and different destination) is kept at 20. The CBR sources send data packets to the destinations at different rates, varying from 4 packets/s to 16 packets/s.
(a) Packet delivery ratio
(b) End to End delay
Fig.7. Performance when CBR load changes.
Fig.7 (a) and Fig.7(b) shows the packet delivery ratio and the average End-to-End delay between EDAODV and AODV respectively. When the data packet-sending rate is greater than 4 packets per seconds, the packet delivery ratio of AODV has a sudden fall from 55% to 10 %. When compared with the above packet delivery ratio, the figures of the EDAODV fall only a gradual fall from 77% to 27% as shown in Fig.7 (a).
One observes that the End-to-End delay between AODV and EDAODV is as shown in Fig.7 (b). When the data packet-sending rate is greater than 4 packets per seconds, the End to End delay has increased from 1.58 seconds to 5.2 seconds the corresponding variation for EDAODV is from 1.1 to 3.95. When the CBR sources inject more data packets to the network, the network becomes congested and more packets cannot be forwarded to their next hop nodes. As a result, loss in the network is due to network congestion. EDAODV has resolved congestion by predicting its occurrence and adaptively distributing it over the primary and alternate paths. In the simulation shown that the EDAODV has improved packet delivery ratio and offered best delay than AODV.
CONCLUSIONS
Thus the proposed EDAODV is a predictive congestion and control routing protocol in MANETs. EDAODV has lost fewer packets than AODV that are not having congestion control mechanism. This is because EDAODV tries to detect congestion in advance from occurring in the first place, rather than dealing with it reactively. A key in EDAODV design is the bi directional alternate path discover concept. This concept tries to find out non-congested alternate path and tries to avoid congestion in the network. Our ns-2-based simulation has confirmed that the advantages of EDAODV demonstrated a significantly improvement of End-to-End delay and packet delivery ratio over AODV.
