Self-Adjusting Congestion Avoidance Routing Protocol for Ad Hoc Networks
Yi Lü, Bharat Bhargava · Purdue e-Pubs (Purdue University System) · 2003
In an ad hoc network, the wireless media is shared by multiple nodes.The contention among neighbors for the access to the shared media is the major cause fornelwork congestion.As wireless links usually have low capacity, congestion in ad hoc networks is a morc severe problem than in wired networks.The main thrust of our work is to avoid congestion at IP layer by minimizing conlemions for channel access.The intermediate delay, which characterizes !.he impacis of channel contention, lraffic load, and lhe length of a route, is developed as a new routing melric.Two approaches are proposed to locally estimate delay using statistic and probability methods respectively.An ad hoc routing protocollhat uses intermediate delay as melric is developed, namely self-adjusting congestion avoidance (SACA) protocol.The perfonnance of SACA is compared against that of AODV and DSR using three types of traffic.SACA is able to deliver more than 80% data packets even under heavy uaffic load.It is 50% -60% more efficient than DSR in terms of delivery ratio.It introduces 50% less protocol overhead than DSR does.SACA delivers 40% -400% more packets than AODV depending on the type of traffic. IntroductionA mobile ad hoc network (MONET) is a collection of mobile nodes that are deployed as a multi-hop wireless ne[WOIk without the aid of any preexisting infrastructure or centralized administration.It relies on nodes cooperation to maintain network connectivity and functionality.The salient characteristics of ad hoc networks, inclUding highly dynamic topologies, low bandwidth, energy-constrained operations, and limited computation capability, make the design of routing protocols a challenging problem.The protocols must be capable of keeping up with the drastically and unpredictably changing network topology, with minimized message exchanges, in a fully distributed way.Wireless links have significantly lower capacity than their hardwired counterparts (e.g., 54Mbps for 802.llgYS. 9.9S2Gbps for OCI92).The real throughput, which is affected by multiple access, fading, noise, and interference conditions, is often much less than a channel's maximum transmission rate.Congestion is typically the norm rather than the exception in ad hoc networks [8], that is, the aggregated traffic demand will frequently approach or exceed the link capacity.Traditional congestion control mechanisms such as TCP, are implemented at higher network layers.They reduce traffic sending rate upon occurrence of congestion.In ad hoc networks, the existence of multiple routes be[Ween two nodes makes it possible for the routing protocol to select an appropriate route, so that network congestion can be minimized without sacrificing traffic rate.~This rcscnrch is supponcd by Center for Education and Research in InforTIlaiion Assurance and Security (CERIAS), NSF gr.mIS CCR-0001788 and ANI-02I9110, and CISCO URP grunt.Many routing protocols are proposed for ad hoc networks, such as destination-sequenced distance vector (DSDV) [19], ad-hoc on-demand distance vector (AODV) [18], and dynamic source routing (DSR) [13].Most of them adopt the content of routing information from the Internet protocols and use hop count as the metric to make routing decisions.Hop count does not provide enough information for congestion control or avoidance.Routing with load balancing has been explored in [22][6].The idea is to provide some additional information, such as the secondary metric based on the current load on each node, to help distribute and balance traffic load.It prevents a single node from being overwhelmed.The experimental study in [16] shows that exceeding the capacity of the channel is the major reason for network congestion.In an ad hoc network, the wireless media is shared by multiple contending nodes.The access to the shared media is complicated due to the hidden terminal problem [4] (e.g., a node will contend for the wireless channel not only for sending but also for receiving packets).The contention among multiple nodes leads to congestion.If the contention is already tense among a node's neighbors, it should not be chosen to forward packets even if there is no load on itself.The main Lhrust of our work is to reduce network congestion at the IP layer by minimizing channel contentions.The essence is to avoid hot spots where multiple nodes are contending with each other.The global coupling effects of wireless channel access in ad hoc networks poses a great challenge to the evaluation of the degree of contentions with local information.In addition, traffic load on a node must be considered, as the store-and-forward process may also cause congestion when the capacity of a node is exceeded.The shorter routes are preferred because longer routes means higher possibility of potential congestion.Our methodology to solve this problem is as follows: (1) We use a single server queueing system to model nodes in ad hoc networks.The impact of channel contention is quantified using the service time.The routing cost at each node is computed as the estimated delay, which reflects the effects of channel contention, current load, and expected load in the future.(2) A new routing metric, namely intermediate delay. is developed, which measures the amount of communication delay introduced by the nodes in between the source and destination.The route with the least intermediate delay will likely involve in the least channel contention.(3) 1\vo approaches are designed to estimate the delay at a node.The first one applies statistical methods to evaluate the mean service time in case there is active traffic.The second one uses probability methods to compute the expectation of the service time according to the underlying MAC protocol when no active traffic exists.(4) A new proactive ad hoc routing protocol, self-adjusting congestion avoidance (SACA), is developed.It uses intennediate delay as the metric to avoid network congestion.Experimental studies are conducted to evaluate the performance of SACA and compare it with AODV and DSR protocols.Our work is conducted in the framework ofCSMAlCA (carrier sense multiple access with collision avoidance) paradigm, which is adopted by lhe widely used IEEE 802.11 standard [1].The ideas and proposed solutions are also applicable to other contention-based media access protocols.The rest of this paper is organized as follows.Section 2 discusses related work.Section 3 introduces contention-based access to shared media, channel spatial reuse, and the idea of ad hoc routing based on intermediate delay to avoid congestion.1\\'0 approaches are proposed in section 4 to locally estimate delay.Section 5 presents the detail of self-adjust congestion avoidance routing protocol.The performance of the proposed protocol is compared against AODV and DSR in section 6. Section 7 concludes the paper. Related WorkAccording to the way in which mobile nodes exchange routing information, ad hoc routing protocols may be categorized as proactive and on-demand.The proactive protocols periodically disseminate routing information among all the nodes in the network, so that every node has the up-to•date information for all possible routes.On-demand routing protocols operate on a need basis, discover and maintain only active routes that are currently used for delivering data packets.C.E. Perkins and P. Bhagwat introduced the destination~sequenced distance-vector (DSDV) routing in [19].DSDV extends the basic Bellman-Ford mechanism by attaching a sequence number that is originated by the