Performance Analysis of the IEEE 802.11 Distributed ...

1 Mobile Networks: Analysis of the IEEE Distributed CoordinationFunction: Bianchi ModelMohammad Hossein Manshaei and Jean-Pierre HubauxMarch 20071 IntroductionCurrently, IEEE is thede factostandard for WLANs [1]. It specifies both themedium accesscontroland thephysicallayers for WLANs. The scope of IEEE groups(WGs) is topropose and develop MAC and PHY layer specifications for WLANto handle mobile and portablestations. In this standard, the MAC layer operates on top of one of several possible physicallayers. Medium access is performed usingcarrier sense multiple access with collision avoidance(CSMA/CA). Concerning the physical layer, three IEEE standards are available at the timeof this writing: a, b, and g. The first IEEE compliant products were based on 11b.

2 Sincethe end of 2001, higher data rate products based on the IEEE standard have appeared onthe market [2]. More recently, the IEEE working grouphas approved the standard,which extends the data rate of the IEEE to 54 Mbps [3].The PHY layer employsall available modulations specified for Section 2 of this document, we briefly describe the operating principles of the IEEE layer, which need to be known for a proper understanding of the IEEE performanceevaluation. There are different analytical models and simulation studies of the MAC layerin saturated condition. In Section 3, we present one of the most well-known analytical model, theso-called Bianchi model [4], to analyze the Performance of IEEE MAC layer. Finally inSection 4, we present the numerical solution of Bianchi model for the IEEE MAC layerThedistributed coordination function(DCF) is the basic medium access mechanism of IEEE ,and uses acarrier sense multiple access with collision avoidance(CSMA/CA) algorithm to mediatethe access to the shared medium.

3 The standard also describescentralized, polling-based accessmechanism, thepoint coordination function(PCF) which is very rarely used in DCF protocol in IEEE standard defines how the medium is shared among includes a basic access method and an optional channel access method withrequest-to-send(RTS)andclear-to-send (CTS) exchanged as shown in Figure 1 and 2, respectively. First, we explain thebasic access DATA time:DIFSSIFSDIFSS ourceDestinationOtherNAV updateACKF igure 1: Basic access CSMA/CA protocolCTSDATACWCW SourceOtherDestinationOtherNAV update with CTSNAV update with RTS and DATA time:DIFSSIFSSIFSSIFSDIFSACKRTSF igure 2: RTS/CTS exchange in the CSMA/CA protocolIf the channel is busy for the source, a backoff time (measuredin slot times)1is chosen randomlyin the interval [0, CW), whereCWstands for thecontention window.]

4 This timer is decreased byone as long as the channel is sensed idle for a DIFS, , Distributed inter-frame spacetime. DIFS isequal toSIF S+2 SlotT ime, where SIFS stands forshort inter-frame space(see values in Table 1).The timer stops when the channel is busy and resumes when the channel is idle again for at leasta DIFS an integer whose range is determined by the PHY layer doubled after each unsuccessful transmission, up to the maximumvalue equal toCWmax+ the backoff timer reaches zero, the source transmits thedata packet. The ACK is trans-mitted by the receiver immediately after a period of duration equal to SIFS. When a data packet istransmitted, all other stations hearing this transmissionadjust theirnet allocation vector(NAV).

5 The NAV maintains a prediction of future traffic on the medium based on the duration informationthat is announced in Data frames (or RTS/CTS frames as will beexplained in the following) prior1 The slot time is the sum of the Receiver-to-Transmitter turnaroundtime, MAC processing delay, andclearchannel assessment(CCA) detect time [1]. The value of slot time for different PHY layer protocols is shown inTable the actual exchange of data. In addition, whenever a node detects an erroneous frame, the nodedefers its transmission by a fixed duration indicated by EIFS, ,extended inter-frame time is equal to theSIF S+ACKtime+DIF contention window is initially set to the minimum value ofCWmin, equal for example to 15(see Table 1). Every time a collision occurs, this is interpreted as a high load of the network, andeach station involved in the collision throttles down its transmission rate by doubling the size of itscontention window.

6 In this way, the contention window can take values equal for example to 31,63, 127, 255, 511, up toCWmax= 1023. Larger contention windows slow down the transmissionof packets and reduce the probability of collisions. In caseof a successful ( collision-free)transmission, the transmitting station brings the value ofits contention window back mechanism we have just described is calledexponential backofforbinary exponential the optional access method is used, an RTS frame should be transmitted by the source and thedestination should accept the data transmission by sendinga CTS frame prior to the transmissionof the actual data packet. Note that stations in the sender srange that hear the RTS packet shouldupdate their NAVs and defer their transmissions for the duration specified by the RTS.

7 Nodesthat overhear the CTS packet update their NAVs and refrain from transmitting. In this way, thetransmission of the data packet and its corresponding ACK can proceed without interference fromother nodes (hidden nodes problem). Table 1 shows the important time interval between frames indifferent standard specification calledinter-frame space(IFS) [2, 5, 3]. IEEE uses the IFScorresponding to its operating 1: Inter frame space andCWtime for different PHY (FH)(DS)(IR)(High Rate)Slot Time ( s)95020820 SIFS ( s)1628101010 DIFS ( s)34128502650 EIFS ( s) or 193268 or 364 CWmin(SlotT ime)1515316331 CWmax(SlotT ime)10231023102310231023 Physical Data Rate (Mbps)6 to 54 1 and 2 1 and 21 and 21, 2, , and 113 Bianchi ModelThe main contribution of Bianchi s model is the analytical calculation of saturation throughput ina closed-form expression.

8 The model also calculates the probability of a packet transmission failuredue to collision. It assumes that the channel is in ideal conditions, , there is no hidden terminaland capture uses a two-dimensional Markov chain ofm+ 1 backoff stages in which each stagerepresents the backoff time counter of a node, see Figure 3. A transition takes place upon collisionand successful transmission, to a higher 2stage ( , from stagei 1 to stageiin Figure 3) and2 Actually it appears lower in the the lowest stage ( , stage 0) 3: Markov chain model of backoff window size in CSMA/CA. In each stage,CWiis themaximum value for the contention window and is equal to 2i(CWmin+ 1) (Note that we define forconvenienceWmin=CWmin+ 1 and thatCWmaxis equal to 2mWmin).

9 If a correct transmissiontakes place in any (i,0) state, a random backoff will be chosen between 0 andCW0 1 withprobability of1 pCW0. This case is represented by states (0,0) to (0, CW0 1) in the Markov the case of collision ( , in state (i 1,0)), a random backoff will be chosen (between 0 andCWi 1, each with probabilityp/CWi). This case is represented by states (i,0) to (i, CWi 1) inthe Markov chain. From [4],c IEEE, model adopts a discrete and integer time scale. In this time scale,tandt+ 1 correspondto the beginning of two consecutive slot times. Each stationdecrements its backoff time counterat the beginning of each slot time. Note that as the backoff time decrement is stopped when thechannel is busy, the time interval betweentandt+ 1 may be much longer than the defined slottime for , as it may include a packet transmission or a state of this bidimensional Markov process is represented by{s(t), b(t)}, whereb(t) is thestochastic process representing the backoff time counter for a given station ands(t) is the stochasticprocess representing the backoff stage (0,1, , m) of the station at timet.

10 This model assumes4that in each transmission attempt, regardless of the numberof retransmissions suffered, each packetcollides with constant and independent probabilityp. In other words,pis the probability that, ina slot time, at least one of theN 1 remaining stations transmits as well. If at steady state eachremaining station transmits a packet with probability ,pcan be written as:p= 1 (1 )N 1(1)Letbi,k=limt P{s(t) =i, b(t) =k}, i (0, m), k (0, CWi 1) be the stationary distri-bution of the chain. A transmission occurs when the backoff time counter is equal to zero. Thus,we can write the probability that a station transmits in a randomly chosen slot time as: =mXi=0bi,0(2)For the above Markov chain, it is easy to obtain a closed-form solution forbi,0as a function ofp.