Simulation of CSMA/CA using smpl
Wei Nan HT042584N
Department of Electrical and Computer Engineering
Faulty of Engineering
NationalUniversity of Singapore
1. Introduction
This report describes a simulation model of Carrier Sense Multiple Access with Collision Avoidance(CSMA/CA) protocol which implement by smpl simulation library. Our propose is to analyze the performance in terms of normalized throughput S and normalized mean delayDin basic access mechanism and RTS/CTS access mechanism. CSMA/CD is widely popular in Ethernet, however it can not be used in Wireless Local Area Network (WLAN) such as IEEE802.11b. Instead, CSMA/CA is commonly used in WLAN. Their common part is CSMA, which works as the following mechanism.
When a station desires to transmit, it senses the medium is busy or idle. If the medium is idle, the station is allowed to transmit, otherwise, it defers its transmission for a later time.
Collision Detection (CD) mechanism is a good idea in wired LAN. But on the other hand,in WLAN environment, it can not be used for these two main reasons.
(1).Implementing CD mechanism need a Full Duplex radio, capable of transmitting and receiving at once, an approach of that would increase the price significantly [1].
(2). There is "Hidden Node" Phenomenon. CD mechanism makes sure that all the stations can sense their shared medium at the same time. Nonetheless, in WLAN, we can not sure that all stations can see each other. Because each wireless station (STA/AP) has their range of communication. If station A and B are not within range of each other(figure a), station A senses the medium is idle, then it transmit. But station B does not know this, it also senses the medium is idle and start transmission at the same time [2].
Figure a
There are two parts of CSMA/CA protocol: (1) basic access mechanism, called Stop-and-Wait CSMA/CA; (2) RTS/CTS access mechanism, called 4-Way Handshake CSMA/CA [3].
In Stop-and-Wait CSMA/CA (see figure b-1), when a station desires to transmit, it senses medium is idle or busy. If the medium is busy, then it defers for a random backoff timer. If the medium is idle for a DIFS time, it could starts transmission. The destination station will check the CRC (cyclic redundancy check) of the receiving packet and send the ACK to the source station after a SIFS time. If the source station receives the ACK packet, it knows there is no collision occurs. If source station does not receive the ACK packet, it will retransmit the fragment until reaches the max number of retransmission.
In 4-Way Handshake CSMA/CA (see figure b-2),when a station senses the medium is idle for a DIFS time, firstly, it transmits a RTS (Request to Send) packet to the destination station. Then the destination station will respond the source station a CTS (Clear to Send) packet after a SIFS time if the medium is idle. If the source station does not receive the CTS, it will retransmit RTS until exhaust its max retransmission time for no receiving CTS.If the source station receives the RTS packet, it will send the data packet after SIFS time. There are two NAV(Network AllocationVector) values in RTS and CTS, which indicate the time duration that reserved for transmitting the actual data packet. Thisinformation is transmitted to all other stations which willstop transmission during this duration. Other processes are as the same as Stop-and-Wait CSMA/CA.
The backoff process is necessary when the station defers. After the station detects the medium is idle for a slot time, the backoff timer will reduce a slot time. When the backoff timer equal zero , the station is allow to transmit. In 802.11, the backoff timer is calculated as follow:
Backoff timer = Random () * slot time
Where Random () is the pseudo random integer drawnfrom a uniform distribution between 0 and CW (Contention Window). CW is integer between CWmin and CWmax. For the packet’s first transmission, CW is set to CWmin. After each collision, CW will be doubled till reaches CWmax.
2. Program design and structure
Thesetwo simulation programs are designed with smpl. In both bcsmaca (see Figure c-1)and rscsmaca, the WLAN is viewed as a closed system with a single server (the channel) and a pool of request sources (stations). The stations are represented by token and request transmission in random intervals. The inter-request intervals are exponentially distributed.
There are eight events in Stop-and-Wait CSMA/CA and nine events in 4-Way Handshake CSMA/CA. Their different is 4-Way Handshake CSMA/CA has an event for waiting CTS. The first event is TransmitFrame.
2.1 Stop-and-Wait CSMA/CA
TransmitFrame The event initiates the frame transmission. It sets some variables such as backoff timer and number of retransmission to zero. Especially, mean frame transmission time Tf is calculated as Tf = Tp/a. Tp is propagation delay time and a is the ratio of Tp to Tf.After initiation, schedule event 2 Defer for request transmission. Then inactive station count is reduced and schedule next arrival.
DeferThe request station check the channel is free or busy. If the channel is busy, the station waits for a backoff period (schedule event 7). Otherwise schedule event 3, StartTransmit, after a dt+Tdifsinterval. If the arrival come after this time, it schedule event three immediately.
StartTransmitIn this event, the station check the channel is free or busy again. If the channel is free, which means the channel is free for DIFS duration, the station schedule event 5, WaitACK, after Tf interval. If the channel is busy, station schedule event 7 for backoff process.
WaitACK This event represents the process of source station waiting for ACK. A random integer from random (1,100) determines the probability of missing ACK. I define if the random integer smaller than 10, the ACK will be missed, otherwise, the source station could receive the ACK successfully. If the ACK is missed, the source station retransmits the data packet (schedule 5) after ACK_Timeout+Tf interval until reaches Max_retran_Data(Long Retry Limit: Max data retransmission number of no receiving ACK set to 6). If the source station receives ACK, schedule event 6, EndTransmit, after Tsifs+Tack interval.
EndTransmit This event represents the successful completion of a transmission. It will schedule event 8, Deassert, to release the channel. And new request arrival event is scheduled.
InitBackoffThis event compute the value of backoff timer for backoff process. Then, it schedules event 9, Backoffprocess, after a slot time.
DeassertThe station release the channel. And set tis=smpl_time()
BackoffprocessThe backoff process is mentioned above. When the channel is free for a slot time, the backoff timer will reduce a slot time. If the backoff timer equal or smallerthan zero, the station start to transmit, schedule event 5 after Tf interval. If the backoff timer bigger than zero, the station still need to waiting, schedule event 9 after a slot time. If the channel is busy, the backoff time will be suspended, reschedule 9 after a slot time.
2.2 4-Way Handshake CSMA/CA
This section describes the different between the Stop-and-Wait CSMA/CA and 4-Way Handshake CSMA/CA in the program. The same process will not be mentioned in this section.
DeferIn this event, if the channel is busy, the station need to wait for a NAV time, then it schedules event 7.
StartTransmitThe source and destination station will exchanges RTS/CTS, thus, there is an additional event 4, WaitCTS, for waiting for CTS. If the channel is busy, station schedules event 7 after a NAV time. If the channel is free, the station sends RTS and schedule event 4, WaitCTS.
WaitCTSWe use the same algorithm as WaitACK to calculate the missing probability of CTS. If source station does not receive the CTS, schedule WaitCTS after CTS_Timeout+Trts interval, until reaches Max_retran_RTS (Short Retry Limit: Max RTS retransmission number of no receiving CTS, set to 8). Otherwise, it schedules event 5 after Tsifs+Tcts+Tsifs+Tf.
BackoffprocessIf backoff timer equal and smaller than zero, it schedules event 4 after RTS interval.
3. Simulations and Results Analysis
We conduct simulation using both bcsmacaand rccsmacafor a range of offered load G from 0.01≤G≤100.We assume 100 stations in the network. You could find the variables in the program (appendix 1). In this simulation, ratio a (propagation delay time/transfer time) equals 0.05. Figure d-1 shows the throughput is increased exponentially when offered load is increased between 0.01 and 1. Nonetheless, if the offered load is increased above 1, the throughput converged to a finite limit. Figure d-2 reports the normalized delay slowly increases when the offered load is in the range of 0.01 to 1. However, it increases rapidly when offered load is increased between 1 and 40. When offered load is increased above 40, the normalized delay is stable. According to the two figures, the performances of Stop-and-Wait CSMA/CA and 4-Way Handshake CSMA/CA are extremely similar. While the offered load below 0.75, throughput and normalized delay are the same of the two kinds of CSMA/CA. Nevertheless, when the offered load is in range of 0.75 to 100, SW CSMA/CA’s performance is a little better than 4W CSMA/CA’s. This is caused by the lack of the simulation software. The probability of missing ACK and CTS is defined by manual work. When I change this probability, performance of 4W CSMA/CA could be better than the other one.
Figure d -1:normalized throughput S vs. offered load G Figure d-2:normalized mean delay vs. offered load G
In the second experiment, we record the maximum value of S (denote as Smax) for a range of a (0.00001≤a≤1.0) in various G. Figure d-3 shows the Smax evidently decreases when the ratio a is increased from 0.00001 to 1.0 for both CSMA/CA mechanisms. The performance of SW CSMA/CA is a little better than 4W CSMA/CA for the same reason.
Figure d -3:max normalized throughput Smax vs. Ratio a
For further consider that the performance could be affected by the capture effect for channel impaired such as Rayleigh fading, shadowing and near-far effect etc. We can denote capture probability Pc(k) here, the throughput S is ((Zdunek et al. '89),
We also can describe this effect by capture ratio model which is simple and relatively reliable (Linnartz et al. '92). In the experiment, the throughput decreases when the capture ratio is increase [4].
4. Conclusions
In this report, we have analyzed the performance of Stop-and-Wait CSMA/CA and 4-Way Handshake CSMA/CA. We have found that the throughput and normalized delay time converged to a finite limit as the offered load is increased for these two CSMA/CA. We also have discovered that the maximum value of throughput decreases when the ratio a (propagation/transfer time) is increased.
References
[1] Pablo Brenner, “A Technical Tutorial on the IEEE 802.11 Protocol”, Jul. 1996, BreezeCom.
[2] “802.11b Wireless LANs”, StanfordUniversity.
(
[3] Jae Hyun Kim, “Performance Analysis of CSMA/CA (Carrier Sense Multiple Access with Collision Avoidance) Protocols for Wireless Local Area Networks in Multipath and Shadowing Environments.
[4] Heikki Laitinen, “Capture Effects on ALOHA and CSMA”, 2004