Collisions are troublesome in WiFi networks for various reasons:
- Collisions increase with the number of stations (n).
- Each collision takes as much channel time as successful transmissions. Meaning that a network filled with collisions slots would look as busy as a capped TDMA network but with no efficiency whatsoever.
I can go on for many more lines but, on the bottom line avoiding collisions with CSMA/CA is still away from an optimum channel efficiency, where only successful and tiny empty slots are seen.
The Binary Exponential Backoff (BEB) mechanism of CSMA/CA.
CMSA/CA relies on a BEB function to handle collisions. I briefly introduced it when describing how CSMA/CA handles collisions. To summarize: after each collision a CSMA/CA node will increment its backoff stage (k+=1) and drawn a new backoff counter B ∈ [0, CW(k)] from a doubled pool (because CW(k)=2^k * CWmin). Each collision will double CW(k) up until CWmax, which is the maximum contention window (usually with CW(k=5)). This function reduces the collision probability after each collision, augmenting the chances of successfully transmitting a frame.
Think on a very crowded and saturated network, let’s say, with 30 nodes. Some stations will attempt transmission at the same time (because of the random backoff) and consequently collide, increase the backoff stage and repeat the backoff process. From the point of view of a single station each collision will delay the transmission of the frame, reducing the possibility of colliding again. But once the frame is successfully transmitted and the backoff stage reset, the collision probability increases again. This “vicious cycle” is responsible for the reduction of throughput on crowded WiFi networks.
Learning-BEB (L-BEB): Combining CSMA/CA and TDMA virtues
Jaume Barceló et al. faced with this problem in 2008, namely: getting rid of collisions in a simple, backwards compatible and totally distributed way.
They figure out that by allowing nodes to pick a deterministic backoff Bd = CWmin/2 after successful transmissions, nodes won’t collide with other successful nodes in future cycles. The figure below provides an easy appreciation of the L-BEB mechanism.
In the figure, STAn indicates the station number, horizontal lines represent the slotted time with numbers indicating the number of slots left until the backoff expires; the rounded rectangles are transmissions for each corresponding station. It shows 4 stations attempting the transmit. The first red outline indicates that at lease two stations selected the same backoff and will collide on the next transmission attempt.
These two colliding stations (STA3 and 4) will increase the backoff stage and recompute a new random backoff (14 and 2 for STA3 and 4, respectively). After STA4 successfully transmits, it picks a deterministic backoff, Bd = 7, and avoid collisions with other successful nodes in future cycles.
L-BEB is able to achieve higher throughput than BEB, mostly because it reduces the number of collisions when the number of stations n is lower or equal to CWmin/2.
But, what happens when n > CWmin/2? What about unsaturated conditions? Can all the nodes share the medium in a fair way? That is, can all the contending nodes fairly divide the available network throughput? I will provide insight on this subjects on the last part of this Collisions in WLANs Saga.