Understanding Collisions under CSMA/CA [1/3]

As many know, the wireless medium is both limited (in spectrum) and shared. This creates a particular problem: not everyone can use it at the same time. Analogous to a crowded room, if everybody starts yelling at the same time it would be very difficult to listen to the speaker you are interested on.

Breaking comparisons, the Radio Frequency (RF) spectrum is composed of very useful frequencies, often used for technologies that we are all familiar with: WiFi, Bluetooth, cordless phones and many more.

WiFi, or at least 802.11g/n work in a band of the RF spectrum which use is unlicensed, meaning that anyone can use it within certain guidelines. This is why you find WiFi almost everywhere!

Now, how can nodes coordinate transmissions so the desired transmitter-receiver(s) can effectively communicate? Here is where a Medium Access Control (MAC) protocol is useful. WiFi’s MAC protocol implements a method called Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA), which is in charge of coordinating transmissions so every node in the network may have a slot to transmit on each schedule.

Time in WiFi networks is slotted. It is composed of successfulcollisions and empty slots, where successful transmissions or collision events occur, and are separated by tiny empty slots of fixed width.

So, how can we only have successful slots and ensure effective communication? Well, CSMA/CA is totally distributed, this means that nodes do not need to communicate with any other in order to access the channel and attempt transmissions. This is very useful under the traffic patters seen in this type of networks, where traffic is mostly bursty and nodes have no clear way of knowing the number of nodes attempting to transmit.

CSMA/CA just instructs nodes to generate a random backoff counter, let’s call it B ∈ [0, CW(k)], where CW(k) = 2^k * CWmin is the Contention Window at backoff stage k ∈ [0,m] (where m is the maximum backoff stage, generally 5); and CWmin is the minimum Contention Window with a typical value of 15. Every time a node generates B, it counts down upon every passing empty slot. When the backoff expires (= 0), the node will check if the channel is free and if so, attempt transmission. If an Acknowledgement (ACK) is received accounting for that message, then the transmission is considered successful, otherwise a collision is assumed.

Collisions are handled using a Binary Exponential Backoff (BEB) technique. Looking at the description of the backoff counter above: if an ACK is not received accounting for the delivery of a frame, the transmitter will increment the backoff stage (k+=1), effectively doubling the range of possible values where B is drawn from (i.e.: with k=1, B ∈ [0, 31], and so on up to k m). This method reduces the collision probability after each collision. When a frame is successfully sent, the node resets its backoff stage (k = 0) and the backoff process is restarted.

Figure 1 below shows the percentage of collision slots when incrementing the number of nodes in a WiFi Network. All nodes have something to transmit, that is what we call a saturated scenario, or an scenario under saturation.

Collisions in a saturated CSMA/CA network

Fig. 1: Collisions in a saturated CSMA/CA network

So, CSMA/CA is an effective way of coordinating transmissions in a shared medium on a totally distributed manner. It is based on simple but strong methods of ensuring that every node gets its share of channel time. But, collisions still exist!

I really hope that this could be useful for you, my goal is just to get all my thoughts and understandings out of my head, try to exchange comments with other people interested on the subject and account a little bit for the time I spend doing research :).

I invite you to keep reading the Collisions in WLANs Saga with the second of three posts about the subject.



Posted under: CSMA/CA, MAC, WiFi

Tagged as: ,