1. Introduction

The mobile adhoc network is an autonomous transitory association of wireless mobile nodes that communicate with each other through wireless links. Nodes organize themselves dynamically in order to provide the necessary network functionality in the absence of fixed infrastructure or central administration. In order to enable communication between nodes that are not directly within each other’s send range, intermediate nodes act as routers that relay packets generated by other nodes to their destination[13]. As mobile ad hoc networks are characterized by a multi-hop network topology that can change frequently due to mobility, efficient routing protocols are needed to establish communication paths between nodes, without causing excessive control traffic overhead or computational burden on the power constrained devices[7].

To facilitate multi-hop communication between non-neighbor nodes, other nodes must act as routers. Since MANETs can be set up easily and inexpensively, they have a wide range of applications, especially in military operations and emergency and disaster relief efforts. IEEE 802.11 is the recommended standard for wireless networks. The MAC layer technique of the IEEE 802.11 standard is called Distributed Coordination Function (DCF). DCF is the fundamental access method used to support asynchronous data transfer on best effort basis[2].

According to DCF, each node with a new packet ready for transmission monitors the channel activity until an idle period equal to a Distributed Inter-Frame Space (DIFS) is detected and then the node transmits. Otherwise, if the channel is sensed busy, the node initializes its backoff timer and defers transmission for a randomly selected backoff interval in order to minimize collisions. It is calculated as the slot time multiplied by a random number which is uniformly distributed between zero and CW (Contention Window) size. The backoff timer is decremented by one when the medium is idle, is frozen when the medium is sensed busy and resumes only after the medium has been idle for longer than DIFS. The node whose backoff timer reaches zero begins transmission and the other nodes freeze their timers and defer transmission. Once the current node completes transmission, the backoff process repeats again and the remaining nodes reactivate their backoff timers. Upon the successful reception of a packet, the destination node sends back an immediate positive acknowledgment (ACK) after a time interval equal to Short Inter-Frame Space (SIFS)[8]. Under the RTS/CTS (Request To Send/ Clear To Send) scheme, the node issues a RTS packet, prior to the transmission of the data packet. When the destination receives the RTS packet, it will transmit a CTS packet after SIFS interval immediately following the reception of the RTS packet. The source node is allowed to transmit its packet only if it receives the CTS correctly. If a collision occurs with two or more RTS packets, which is detected by the lack of the CTS response, less time is wasted comparing with the situation where larger data packets collide in the basic access mode. Therefore, after the successful RTS/CTS exchange, the source node transmits the data packet and then the receiver responds with an ACK packet to acknowledge a successful reception of the data packet. The rest of the paper is organized as follows. The next section presents study of the backoff mechanisms described for IEEE 802.11 standard. Section III concludes the paper.

2. Backoff Schemes - An analysis

Channel bandwidth is a very scarce resource in wireless networks. However, the way in which IEEE 802.11 DCF uses random backoff time to resolve the channel contention leads to inefficient utilization of this scarce resource[7]. Especially in a heavily loaded network, the portion of channel bandwidth is wasted in idle or collision state. Collisions are not completely eliminated even when the RTS/CTS dialogue option is used by the competing nodes. When access collisions take place, active nodes need to backoff randomly to avoid repeated collisions. This random backoff time is uniformly selected from the contention window, CW, which is dynamically controlled by BEB algorithm. However, the BEB scheme suffers from a fairness problem and its throughput performance is unsatisfactory under high traffic load[10].

In BEB, nodes underwent channel contention and packet transmission stages sequentially. Channel contention stage consumes channel bandwidth[19]. Thus time spent on channel contention is reduced when probability of collision is small. But it is difficult to achieve. Channel contention cannot be started until the current transmission finishes. Channel idle time and contention overhead is more because of this serial transmission. Also access to a slot is not uniform in BEB. Only the winners repeatedly get the chance to access the channel. This leads to the channel capture effect.

Marek et al. employs random backoff mechanism to avoid the collisions[12]. Transmitting nodes select random value of CW. The nodes start to transmit their frames in random moments, so the probability of collision decreases. The proper selection of parameters of backoff mechanism has a very large influence on the network performance. The wrong selection of CW parameters cause degradation of the throughput and the mean packet delay can grow several times.

The MACA (Multihop Access Collision Avoidance), media access protocol first proposed by Karn[9] and later refined by Biba[3] uses an RTS-CTS-DATA packet exchange and binary exponential backoff. V.Bharghavan et al. have discussed the design of a new media access protocol for wireless LAN’s called MACAW which uses an RTS-CTSDS- DATA-ACK (DS-Data Sending) message exchange and includes a significantly different backoff algorithm[1]. This design process relied on the following four points. First, the relevant congestion is at the receiver, not at the sender. Second, congestion is not a homogeneous phenomenon. It is inadequate to characterize congestion by a single backoff parameter. They instead introduced separate backoff parameters for each stream, and then for each end of the stream. Care was taken to identify which end of the stream was experiencing collisions. Third, learning about congestion levels should be a collective enterprise. To rectify this, they introduced “copying” the backoff parameters from overheard packets. Fourth, the media access protocol should propagate synchronization information about contention periods, so that all devices can contend effectively. These various changes have significantly improved the performance of the media access protocol.

Bianchi presented a simple analytical model to compute the saturation throughput performance of the 802.11 DCF[2]. This model assumes a finite number of terminals and idle channel conditions. The model is suited for any access scheme employed. It is extremely accurate in predicting the system throughput. The performance of the Basic Access method strongly depends on the system parameters. But the performance is only marginally dependent on the system parameters when the RTS/CTS mechanism is considered. The RTS/CTS mechanism has proven its superiority in most of the cases.

H.Wu et al. presented a throughput enhancement mechanism for DCF by adjusting the CW resetting scheme [17]. In case of collisions, CW size is doubled. For each successful transmission, CW size is halved. Markov chain is used to analyze the effect of new back off scheme. This model can be used by both basic access method and RTS/CTS access method. It is accurate in predicting the performance and proves the effectiveness of the new backoff scheme.

X.Yang et al. presented a different mechanism with pipeline collision resolution and packet transmission so that the time period in which channel is in idle or collision is reduced[19, 21]. As a result of pipelining concept, both the channel idle time and colliding time have been minimized. The utilization of channel bandwidth can be close to peak performance even in a highly loaded network.

X.Yang et al. presented a Dual Stage Contention Resolution MAC protocol (DSCR). DSCR is compatible with 802.11 and differs in the backoff mechanism used for contention resolution[18]. With the help of two “virtual” contention resolution stages, DSCR significantly reduces channel contention among active nodes in highly loaded networks. DSCR achieves better channel scheduling efficiency and improves stability of the network.

In MILD (Multiplicative Increase and Linear Decrease), contention window size is multiplied by 1.5 on a collision and decreased by one on a successful transmission[1, 22]. It performs well when the network load is steadily heavy. When the number of active nodes changes from high to low, it can’t adjust its CW fast enough because of its linear decrease mechanism. N.Song et al. discussed the Exponential Increase Exponential Decrease (EIED) backoff algorithm in which the CW resetting scheme causes a very large variation of the CW size and degrades the performance of a network when it is heavily loaded since each new packet starts with CW_min which can be too small for heavy network load[14]. BEB does not use the collision history of the previous packets and reduces CW too fast making it not suitable for network under heavy load. They analyzed that EIED outperforms BEB and MILD in terms of both throughput and delay.

J.Deng et al. have introduced a new backoff algorithm, termed the Linear MILD (LMILD) backoff algorithm[6]. In LMILD scheme, colliding nodes increase their contention windows multiplicatively, while other nodes overhearing the collisions increase their contention windows linearly. After successful transmissions, all nodes decrease their contention windows linearly. In order to perform such an operation, network nodes make use of the extra information available from the physical layer, which generates physical carrier sensing signal and reports no packet header reception during collisions. This special feature differentiates the LMILD scheme from the MILD scheme. The fairness performance of the LMILD scheme is better than the BEB scheme as well.

The neighboring nodes could fail to detect the collided packets due to channel fading or could mistake other signals as packet collisions. This wrong detection and false positive problems may affect the performance of the LMILD scheme. However, it suffers from low throughput in networks with large number of active nodes as well.

FCR (Fast collision Resolution) redistributes the backoff timer for all competing nodes. It resolves collisions more quickly and obtain higher throughput than DCF[10]. The buffer is sufficiently large and loss of frame is due to the collision. Collision rate increases when CW_min is too small. When CW_min increases, collision rate decreases but more channel bandwidth is lost. But it itself can inversely affect the fairness unless it is combined with additional fair scheduling mechanism.

C.Wang et al. investigated a new efficient collision resolution mechanism called GDCF (Gentle DCF). This scheme considers a more conservative measure by halving the contention window size after consecutive successful transmissions[16]. This “gentle” decrease can reduce the collision probability, especially when the number of competing nodes is large. Compared to FCR, GDCF achieves better fairness and simplicity and can easily support priority or QoS (Quality of Service) differentiation effectively. But the performance of GDCF when the number of nodes varies frequently is not analyzed.

P.Chatzimisios et al. presented a simple and effective contention window-resetting scheme[4], named Double Increment Double Decrement (DIDD). DIDD can decrease the chance of a packet collision by utilizing a higher CW after a successful transmission instead of resetting it to CW_min. DIDD minimizes the number of packet collisions whereas RTS/CTS shorten collision duration. It attains higher packet delay values since it includes the time delay of packets that otherwise would have been discarded. The authors do not consider the support of priority applications or QoS differentiation through choosing smaller (larger) CW values for high-priority (low priority) applications. DIDD also could be combined with other enhancements techniques i.e. packet bursting to improve IEEE 802.11 services by maximizing protocol performance.

Nakjung Choi et al. discussed P-DCF (Predictive- DCF) enables mobile nodes to choose their next backoff times in the collision-free backoff range by continuously listening to the medium[5]. P-DCF utilizes the past history of successful transmissions. Hence collision probability is reduced. The advantage of this scheme is that mobile nodes can reduce the packet collision probability by predicting others’ backoff times even in the saturated network. Therefore, each mobile node is able to acquire the performance gain. In addition, an adaptive contention window mechanism may make P-DCF more robust. P-DCF ensures high throughput and low packet latency by reducing the packet collision probability. A study on how to derive the predictive distribution from a mobile node’s P-BCT is in progress.

Table 1. Comparison of well known Backoff schemes Backoff Scheme Author&Year CW Value on Success CW Value on Failure Advantages Disadvantages BEB IETF Work Group Reset to CWmin Doubled Accurate Unfair channel access MILD Bhargavan et al, 1994 Reduced by 1 Increased by 1.5 times Solves Fairness problem Low throughput with large number of active nodes EIED N.Sang et al, 2003 Decreased by a factor Multiplied by a factor Better than BEB in terms throughput &delay Not suitable for heavily loaded networks FCR Y.Kwon et al., 2003 Reset to CWmin Doubled Resolves collision more quickly Performance is lightly affected under high load LMILD J.Deng et al., 2004 Reduced by 1 Multiplied by a factor Better than BEB Unfair channel access GDCF C.Wang et al., 2004 CW/2 Doubled Achieves better fairness and simplicity than FCR Affects performance when load is high DIDD P.Chatzimisios et al., 2005 CW/2 Doubled Minimizes collision No priority support P-DCF Nakjung Choi et al., 2005 Reduced by number of idle slots Increased based on number of competing nodes Reduces packet collision probability Poor performance under heavy load NBA M. Taifour et al., 2005 Reduced by αN+β Doubled Performance is better than BEB Hidden/Exposed nodes are not considered

In order to improve the channel capacity in wireless ad-hoc networks, M. Taifour et al. introduced a new backoff algorithm named Neighborhood Backoff Algorithm (NBA). In this every node modifies its backoff interval according to the number N of its neighbors[15]. They have modified the initial contention window size to be relative to the number of contending nodes, which can be easily calculated from the routing table in each node. Large bandwidth is wasted due to collisions. To achieve optimum result, system parameters must be selected according to traffic condition. Delay and data dropped is better. They have found that the minimum contention window is proportional to the number of neighbors. Comparison of these backoff schemes are listed in Table 1.

S.S.Manaseer et al. introduces a modified logarithmic backoff algorithm that uses logarithmic increment instead of exponential extension of window size to eliminate the degrading effect of random number distribution. This new algorithm achieves higher throughput when the network size is large[11]. R.Ye et al. discussed a Multi-Chain Backoff (MCB) algorithm that enables nodes to adapt to different congestion levels with the help of multiple backoff chains[22]. Advantage of MCB is that it doesn’t have to estimate the number of contending nodes, traffic load etc but provides high throughput and fair channel access. With the capability of switching to different backoff chains, MCB offers higher throughput than the existing protocols, such as GDCF, IEEE 802.11, MILD, EIED and LILD, yet still provides fair access to the wireless channel.

3. Conclusions

In mobile adhoc networks, nodes experiencing collisions on the shared channel need to backoff for a random period of time, which is uniformly selected from the Contention Window (CW). This contention window is dynamically controlled by the backoff algorithm. This paper analyzes existing backoff algorithms and their advantages and disadvantages. From the analysis, it has been understood that the size of contention window has a great impact on the performance of network.