Wifi backoff algorithm

Not being able to access the packets per retransmission means that implementing a backoff algorithm per transmission is not possible. Alternatively, a per-packet variant of HBAB has been pro-. Figure 2. Table 4 shows the wireless adapters used in this work along with their specifications. In order to. Figure 3 A. In order to evaluate HBAB real-time performance, a number of testing scenarios were conducted in both simulation and Linux testbed environments.

In all testing scenarios, the main connection that was used to evaluate HBAB performance, i. The packet generation rate was changed per testing scenario. Other connections were established between Stations 1 and 3 as well as Stations 2 and 4 to generate background traffic, whose packet generation rate also varied per testing scenario.

The performance measures average delay, loss fraction and throughput were extracted from the log files produced at Station 4 after each testing scenario. Table 5 further shows the parameters of the testing scenarios.

The results of the Linux testbed experiments are shown in Table 6 and Figures 5 — 7. Since HBAB implementation in the Linux testbed was a bit different from simulation, performance results were different as well.

In general, there was no consistent performance improvement pattern in the testbed experiment results as illustrated in simulation. The special characteristics of MANETs, such as mobility and absence of centralized control, have made the provisioning of end-to-end QoS guarantees a very challenging problem.

In this work, an adaptive backoff algorithm was developed based on the IEEE Figure 4 A. The simulation environment featured fifty nodes moving in random way-point fashion within square meters area, whereas the Linux testbed comprises four.

Figure 4 B. Table 4. Wireless cards specifications. Table 5. Testbed parameters. Table 6. Due to some hardware limitations, it was not possible to implement HBAB in the Linux-based testbed with its original design as im plemented in simulation. Simulation results have shown significant improvement in IEEE That was revealed as a decrease in the average delay and increase in PDF and throughput.

The overhead associated with implementing HBAB is due to two factors: extra memory space for nine new variables and extra computations for five additional operations. There are a number of open issues for future development.

Figure 5 A. Figure 5 B. Figure 6 A. Figure 6 B. Figure 7 A. Figure 7 B. Deng and R. EB, No. Barry, A. Campbell, and A. Kanodia, C. Li, A. Sabharwal, B. Sadeghi, and E. Aad and C. Ni, I. Aad, C. Barakat, and T. Chatzimisios, et al.

Moura and R. Conti, and E. Bruno, M. Reddy, J. John, and C. Nasir and M. This set is called the contention window. Before they try to transmit, they listen to the channel and transmit only if the channel is idle. This causes the source which picked the smallest integer in the contention window to succeed in transmitting its frame.

So, Back-off algorithm defines a waiting time for the stations involved in collision , i. Now, both the station randomly pick an integer from the set K i. Skip to content. Change Language. Related Articles. Computer Network Fundamentals. Physical layer. Data Link layer. Network layer. We also derived an optimal CW for the number of active stations. In Section 4 , we present an analysis of the proposed scheme.

The simulation results and discussion are presented in Section 5 , and we conclude the paper in Section 6. According to the DCF mechanism, when a station has a packet to transmit, it senses the channel for an idle period that is greater than a DIFS interval. If the channel remains idle, the station transmits the packet; otherwise, the transfer is deferred until the ongoing transmission is terminated.

The station continues to monitor the channel until it is measured as idle for a DIFS interval, and it then generates a random backoff interval. Random backoff intervals are slotted, and stations are only allowed to transmit their packets at the beginning of each slot.

The random backoff interval value is uniformly selected from the range , interval, where CW is the current CW. The contention window size doubles with each collision, and this occurs when two or more stations transmit their packets in the same time slot. The backoff counter is frozen when activities are detected on the channel, and it is reactivated after it is sensed that the channel is again idle for more than a DIFS interval; the counter is decremented as long as it is sensed that the channel is idle.

When the backoff timer reaches zero, the station attempts to transmit a packet at the beginning of the next time slot. If the packet transmission is unsuccessful as indicated by an ACK timeout, a retransmission is scheduled, and the CW increased by two with each unsuccessful transmission until it reaches its maximum value; that is, , where is the maximum backoff stage and its value could be 5 or 7, depending on the maximum and minimum contention window size.

The main reason for the throughput degradation in DCF is the exponential backoff, which changes the CW based on the last transmission status. As shown in Figure 1 , the BEB algorithm works well for a small number of stations.

However, as the number of stations increases, the collision rate increases and the throughput significantly decreases. By making the CW dynamically adjust irrespective of the last transmission attempt, our proposed algorithm adjusts the CW based on the network conditions.

It estimates the number of stations and then adjusts the CW based on the number of active stations in the network, which improves the network performance in terms of the throughput and collision probability. Our objective is to develop an adaptive backoff algorithm for IEEE As discussed above, fixed-CW backoff algorithms do not consider the network conditions when estimating the CW.

As such, to realize successful transmissions, all of the algorithms reduce the CW exponentially or linearly, while increasing the CW for each collision that occurs. To overcome this problem, some recent research considered the channel-state parameters utilizing the network conditions in order to dynamically adjust the CW, thus improving the throughput and fairness of the network. To adjust the CW adaptively in order to realize maximum throughput and to achieve good fairness, we derived an analytical model that utilizes the network conditions when calculating the optimal CW.

The proposed algorithm has two main features: it estimates the number of active stations from the channel-state information, which is discussed in the next section. Then, it adjusts the CW according to the number of active stations on the network.

The proposed algorithm adjusts the CW using the network load. It increases the CW when the network is dense and reduces it when the network load decreases. Thus, the proposed algorithm improves the network performance in terms of the throughput and collision probability.

By finding the optimal CW based on the number of active stations, the proposed algorithm also provides an equal opportunity to all active stations, which also improves the fairness of the network. In order to obtain actual channel status information, a station has to observe the channel for an entire backoff period. As shown in Figure 2 , the channel status can be generally divided into three states, namely, the collision state, success state, and idle state.

To calculate the channel-state probabilities, we consider slots in the total backoff period and stations, and the probability that one out of stations transmits data during a slot is given by The number in a particular slot is called the occupancy number of that slot [ 34 ].

The expected number of slots, with the occupancy number , is The probability of having an occupancy number 0 is given by and the probability of having an occupancy number 1 can be calculated by A collision occurs when two or more stations transmit their data on the same slot at the same time, and the probability of having an occupancy number 2 can be calculated using.

The throughput is a function of , , and , as shown in 6. The other parameters , , and are constant with respect to the PHY parameters of the networks. We will discuss these parameters in detail in Section 4. For a given , there exists an optimal contention window, , which achieves the maximum throughput. To find , we take the partial derivative in 6 with respect to CW. To simplify the calculation, we take the partial derivative with respect to because is a function of CW.

Using the quotient rule [ 35 ], the derivative of 6 is given as 7. Consider By solving 8 , we obtain the following: By simplifying and then substituting the value into 9 , where [ 7 ], we obtain the relationship between and from the following: where is the minimum contention window, while is the optimal contention window and is the number of stations in the network.

As shown in 10 , depends on and the number of active stations on the network. Usually, this number is unknown and needs to be estimated. In this section, we find an accurate estimation of the number of active stations from the collision probability and by replacing the value in 13 using 12 [ 7 ]. We obtain the estimated number of active stations as follows: where depends on the PHY parameters of the network.

Detailed procedures for estimating the number of stations are summarized in Algorithm 1. As shown in Figure 3 , the proposed scheme provides an accurate estimation of the number of stations on the network, which we subsequently use to calculate the optimal CW.

For all contentions, each station has to observe the channel for the total backoff period and calculate using 5. Then, all of the stations estimate the number of active stations on the network using Algorithm 1.

Next, a station determines based on the number of active stations using When a station receives a packet from a higher layer or another station, it randomly chooses an integer value using a uniform distribution over the interval , to determine the backoff timer, and it then begins to perform the backoff procedure. The backoff procedure is the same as that of DCF.

When the channel is idle, the backoff counter decreases by one for each slot time; however, when the channel is busy, the backoff counter is frozen. The packet transmits whenever the backoff timer expires. Channel-state probabilities have been extensively studied as they are among the critical performances metric employed to analyze IEEE In this section, we calculate the channel-state probabilities for the proposed ABA-CW scheme; we represent the collision probability by , success probability by , and transmission probability by for a saturated network under ideal channel conditions.

For the simple mean-value analysis, the Bianchi model [ 7 ] is sufficient to obtain an accurate prediction of the channel-state probabilities for a saturated network under ideal channel conditions. We assume a fixed number of stations in saturated network conditions. In a saturated network, every station always has a packet to transmit. The Bianchi model assumes that each packet collides with constant and independent probability , which is independent of the channel state.

Let be the probability that a station attempts to transmit in a randomly chosen slot time, which is given by To compute the collision probability where at least one of the remaining stations transmits within a slot time, we use Using 12 and 13 , we can find the values of and.

Once we obtain the value of , we can compute the transmission, idle, and success probabilities for a randomly chosen slot. Let be the transmission probability, where there is at least one station attempting to transmit in the considered slot time. In order to compute the normalized system throughput, , we need to compute the actual time lengths of the collision slot and success slot. For the IEEE In this case, we assumed that all packets have the same size, and thus.

Therefore, we can compute the throughput of the system as follows [ 7 ]: where is the slot time for a backoff window. In order to achieve the maximum theoretical throughput limit, as seen in 18 , we need to maximize the success probability , while reducing the collision probability and idle backoff time of the DCF. For this reason, we need to select to increase the throughput of the system while reducing the collision probability and idle backoff time. The fairness can indicate how fairly the resources are allocated among the stations.

Fairness is an important problem, primarily in fixed-CW backoff algorithms. A fairness index of 1 indicates a fair resource distribution among the stations, while 0 represents an unfair distribution among the stations. The channel utilization is defined as the total effective transmission time for all stations divided by the total simulation time as shown in Figure 11 : where , , , and represent the transmission time, packet length, slot time, and the number of slots, respectively.

For the frame delay analysis, we considered [ 37 ] as reference model, where the backoff delay and the number of collisions are the main causes for the frame delay. The frame delay can be calculated by the following relation: where a station has to wait time to sense the channel again after collision occurred.

For the performance validation, we compared the throughput, collision rate, utilization, and fairness of the proposed ABA-CW algorithm with the DCF algorithm, as shown in Table 1. As shown in Table 1 , the throughput, utilization, and fairness of the DCF algorithm decrease as the number of stations in the network increases, while the ABA-CW algorithm maintains a constant throughput, utilization, and fairness for a varying number of stations in the network.

The collision rate of the DCF algorithm increases as the number of stations in the network increases, while the ABA-CW achieved a collision rate of less than 0. For the simulation, we consider an IEEE Considering IEEE We performed the simulation and evaluation while varying the number of stations. Figure 4 illustrates the performance comparison of the ABA-CW scheme with the fixed-CW mechanisms with respect to the collision probability.

The horizontal axis represents the number of stations, while the vertical axis is the collision probability. As illustrated in Figure 4 , the collision probability of the fixed-CW schemes increases as the number of stations in the network increases, while the proposed ABA-CW algorithm gives an almost constant collision probability regardless of the number of stations in the network. The four algorithms fixed-CW mechanisms only increase or decrease their CWs with their rules depending on whether the transmitted packets collided.

These result in changes in the collision probability although the number of stations is fixed. However, the proposed scheme adjusts the CW based on the number of stations in the network. The horizontal axis represents the number of stations, while the vertical axis represents the throughput of the backoff schemes. The throughput of the fixed-CW schemes decreases as the number of stations increases, while the ABA-CW scheme achieves an almost constant throughput for different numbers of stations.

Therefore, the proposed ABA-CW scheme performs better and achieves an almost constant throughput for the reasons explained for Figure 4.

The probability of realizing stable collisions is directly related to a constant and high throughput. The channel utilization is an important performance matric in the performance analysis of backoff algorithms. Most of the fixed-CW schemes do not utilize the channel in optimum way, which leads to a lower throughput for the fixed-CW schemes. The horizontal axis represents the number of stations, while the vertical axis represents the utilization.