layer –
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 1
ISSN 2229-5518
Performance Analysis of Backoff
Algorithm in IEEE 802.11 Networks
Sakshi Suhane, Dr. Sanjeev Sharma, Prof. Varsha Sharma
Abstract— The primary Medium Access Control (MAC) technique of IEEE 802.11 is called Distributed Coordination Function (DCF). This protocol adopts a Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) with a binary exponential backoff (BEB) algorithm to access the channel. The protocol performance mainly depends on backoff procedure which reduces the probability of collision. W ith BEB, waiting time of a node gets doubled after every unsuccessful transmission. This introduces fast-growing retransmission delays for the backlog traffic. In a mobile ad hoc network (MANET), it would be worthwhile to slow down the growth-rate of waiting time because the nodes communicating in a MANET might move out of collision range while waiting for retransmission. Moreover, DCF reduces the Contention W indow to the initial value after each successful transmission which essentially assumes that each successful transmission is an indication that the system is under low traffic loading. In this paper analyzed the problem with existing Backoff Algorithm.
Index Terms— DCF, MAC, CSMA/CA, BEB, MANET.
—————————— • ——————————
n recent years, much interest has been involved in the design of wireless networks for local area communication. Study group 802.11 was formed under IEEE Project 802 to recommend an international standard for Wireless Local Area Networks (WLAN’s). The final version of the standard was released in 1999, and provides detailed medium access control (MAC) and
physical layer (PHY) specification for WLAN’s [1].
WLANs can operate in two modes namely infrastructure based and infrastructure-less mode or ad-hoc mode. In infrastructure based mode, a central coordinator or an Access Point (AP) is needed for operation of network. The AP resolves issues related to channel access and transfer of information between stations. AP based networks are also called as a single-hop networks where the all the information from a source to destination is transferred via the AP. Stations cannot communicate with each other directly. In the other mode of operation, known as the Mobile Ad-hoc Network (MANET) nodes communicates directly with each other without any central coordinator. This requires that all nodes must act as packet forwards to relay packets between two stations that are outside the radio coverage of each other. This provides greater flexibility and robustness.
To transmit packets to a node outside its range, the network uses multi-hop store-and-forward routing.
————————————————
• Sakshi Suhane is currently pursuing masters degree (M.Tech-IT) in Ad- hoc Networking in SOIT RGPV ,BHOPAL(MP),INDIA, PH-9424958241. E-mail: sakshi.suhane@gmail.com,sakshi_srit@yahoo.com
• Dr. Sanjeev Sharma is currently working as HOD (SOIT) in SOIT
RGPV,BHOPAL(MP),INDIA. E-mail: sanjeev@rgtu.net.
• Prof. Varsha Sharma is currently working as Professor in SOIT
RGPV,BHOPAL(MP),INDIA. E-mail: varshasharma@rgtu.net
WLANs have great potential for both military and commercial applications. In a WLAN, nodes transmit packets in an unsynchronized fashion. The protocol employed in the medium access control (MAC) layer is responsible for coordinating access to the shared channel while minimizing conflicts. Hence it is important to design an efficient and effective MAC protocol.
In the 802.11 protocol, the fundamental mechanism to access the medium is called distributed coordination function (DCF). This is a random access scheme, based on the carrier sense multiple access with collision avoidance (CSMA/CA) protocol. Retransmission of collided packets is managed according to binary exponential backoff rules. The standard also defines an optional point coordination function (PCF), which is a centralized MAC protocol able to support collision free and time bounded services.
The MAC layer has to fulfill several tasks. It has to control medium access but it can also offer support for roaming, authentication, and power conservation. The basic services provided by the MAC layer are the mandatory asynchronous data service and an optional time bounded service. The following three basic access mechanisms have been defined for IEEE 802.11: the mandatory basic access method based on CSMA/CA, an optional method avoiding hidden terminal problem, and finally a contention-free polling method for time bounded services. The first two methods are also summarized as Distributed Coordination Function (DCF), the third method is called Point Coordination Function (PCF). The MAC mechanisms are also called as distributed foundation wireless medium access control (DFWMAC).
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 2
ISSN 2229-5518
Following figure depicts the architecture of 802.11 MAC
layer –
Required for Contention
Used for
Contention
mechanism, also known as basic access method. A positive MAC acknowledgement (ACK) is transmitted by the destination station to signal the successful packet transmission. The other optional one is a four-way handshaking mechanism, which uses request-to- send/clear-to-send(RTS/CTS) technique to reserve the channel before data transmission. Before transmitting a packet, a station operating in RTS/CTS mode “reserves”
MAC Extent
Point Coordination Function (PCF)
Services and
basis for
the channel by sending a special Request-To-Send short frame. The destination station acknowledges the receipt of an RTS frame by sending back a Clear-To-Send frame, after which normal packet transmission and ACK response occurs. Since collision may occur only on the
Distributed Coordination
Function (DCF)
Figure 1: MAC Architecture
The fundamental access method of the IEEE 802.11 MAC is a DCF known as carrier sense multiple access with collision avoidance (CSMA/CA). The DCF must be implemented in all stations, for use within both ad-hoc and infrastructure network configurations. For a station to transmit, it shall sense the medium to determine if another station is transmitting. If the medium is not determined to be busy, the transmission may proceed. The CSMA/CA distributed algorithm mandates that a gap of a minimum specified duration exist between contiguous frame sequences. A transmitting station must ensure that the medium is idle for this required duration before attempting to transmit. If the medium is determined to be busy, the station shall defer until the end of the current transmission. After deferral, or prior to attempting to transmit again immediately after a successful transmission, the station shall select a random backoff interval and should decrement the backoff interval counter while the medium is idle.
In 802.11, the DCF is the fundamental access method used to support asynchronous data transfer on a best effort basis. As specified in the standards, the DCF must be supported by all the stations in a basic service set(BSS). The DCF is based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). CSMA/CD is not used because a station is unable to listen to the channel while transmitting. In 802.11 CS is performed both at physical layer, which is also referred to as physical carrier sensing, and at the MAC layer, which is known as virtual carrier sensing. The PCF in the 802.11 is a polling-based protocol, which is designed to support collision free and real time services.
There are two techniques used for packet transmitting in DCF. The default one is a two-way handshaking
RTS frame, and it is detected by the lack of CTS response, the RTS/CTS mechanism allows to increase the system performance by reducing the duration of a collision when long messages are transmitted. As an important side effect, the RTS/CTS scheme designed in the 802.11 protocol is suited to combat the so-called problem of Hidden Terminals, which occurs when pairs of mobile stations result to be unable to hear each other. However, the drawback of RTS/CTS mechanism is increased overhead for short data frames.
A station with a new packet to transmit monitors the channel activity. If the channel is idle for a period of time equal to a distributed inter-frame space (DIFS), the station transmits. Otherwise, if the channel is sensed busy (either immediately or during the DIFS), the station persists to monitor the channel until it is measured idle for a DIFS. At this point, the station generates a random backoff interval before transmitting (this is the Collision Avoidance feature of the protocol), to minimize the probability of collision with packets being transmitted by other stations. In addition, to avoid channel capture, a station must wait a random backoff time between two consecutive new packet transmissions, even if the medium is sensed idle in the DIFS time.
For efficiency reasons, DCF employs a discrete-time backoff scale. The time immediately following an idle DIFS is slotted, and a station is allowed to transmit only at the beginning of each slot time. The slot time size is set equal to the time needed at any station to detect the transmission of a packet from any other station.It depends on the physical layer, and it accounts for the propagation delay, for the time needed to switch from the receiving to the transmitting state, and for the time to signal to the MAC layer the state of the channel (busy detect time).
The backoff procedure shall be invoked for a STA to transfer a frame when finding the medium busy as indicated by either the physical or virtual carrier-sense mechanism (see Figure). The backoff procedure shall also be invoked when a transmitting STA infers a failed transmission.To begin the backoff procedure, the STA
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 3
ISSN 2229-5518
shall set its Backoff Timer to a random backoff time. All backoff slots occur following a DIFS period during which the medium is determined to be idle for the duration of the DIFS period, or following an EIFS period during which the medium is determined to be idle for the duration of the EIFS period following detection of a frame that was not received correctly. A STA performing the backoff procedure shall use the carrier-sense mechanism to determine whether there is activity during each backoff slot. If no medium activity is indicated for the duration of a particular backoff slot, then the backoff procedure shall decrement its backoff time by slotTime.If the medium is determined to be busy at any time during a backoff slot, then the backoff procedure is suspended; that is, the backoff timer shall not decrement for that slot. The medium shall be determined to be idle for the duration of a DIFS period or EIFS, before the backoff procedure is allowed to resume. Transmission shall ommence whenever the Backoff Timer reaches zero.A backoff procedure shall be performed immediately after the end of every transmission.In the case of successful acknowledged transmissions, this backoff procedure shall begin at the end of the received ACK frame. In the case of unsuccessful transmissions requiring acknowledgment, this backoff procedure shall begin at the end of the ACK timeout interval. If the transmission is successful, the CW value reverts to aCWmin before the random backoff interval is chosen, and the STA short retry count and/or STA long retry count are updated . This assures that transmitted frames from a STA are always separated by at least one backoff interval. The effect of this procedure is that when multiple STAs are deferring and go into
random backoff, then the STA selecting the smallest backoff time using the random function will win the contention.
From the above discussion we can see that DCF resolves collision through Contention Window and backoff time. As specified in the original standard, after each successful transmission, the backoff stage will resume to the initial stage 0, and the contention window will be set to CWmin regardless of network conditions such as number of competing nodes. This method, referred to as ‘heavy decrease’ tends to work well when the number of competing nodes is less. When the number of competing nodes increases, it will be shown to be ineffective, since the new collisions can potentially occur and cause significant performance degradation.
For example, let us assume that the current backoff stage is ‘i’ with contention window CW( i ) = 2^i * CWmin , and there is a successful transmission, the next backoff stage will be stage 0 with contention window CW( 0 ) = 31 according to the specification. But if the number of competing nodes is large enough (>>31), the new collision will likely occur at the backoff stage 0. The main argument is that since the current backoff stage is ‘i’ some collision must have occurred recently at the previous stage. Now if the number of current competing nodes is larger than or close to CW( i ), and if the backoff stage is set to 0, there is a high probability that new collisions will happen. So resetting the contention
Frame
CWindow
Defer Backoff
Frame
Defer
Frame
CWindow
Defer
CWindow
Defer
Frame
CWindow
= Backoff = Remaining Backoff
CWindow=Contention Window
Figure 2: Backoff Procedure
IJSER © 2011 http://www.ijser.org
International Journal of Scientific & Engineering Research Volume 2, Issue 6, June-2011 4
ISSN 2229-5518
window after every successful transmission is an inefficient approach if the number of nodes is large.
Thus, the operation of the BEB algorithm can be summarized as follows:
CW = min [2*CW, CWmax], upon collision (1) CW = CWmin , upon success (2 )
The operation of existing DCF protocol can be summarized from the following figure –
Stage 0 Stage 1 Stage n
[5] Yunli Chen, Qing-An Zeng, Dharma P. Agrawal, “ Performance analysis and enhancement for IEEE 802.11 MAC protocol”, ICT
2003. 10th International Conference on Telecommunications,
2003, Volume 1, 23 Feb.- 1 March 2003 Page(s):860 – 867
[6] Manshaei M.H., Cantieni G.R., Barakat C., Turletti T, “Performance analysis of the IEEE 802.11 MAC and physical layer protocol”, Sixth IEEE International Symposium on a World of Wireless Mobile and Multimedia Networks, 2005. WoWMoM 2005. 13-16 June 2005 Page(s):88 – 97
[7] Haitao Wu, Yong Peng, Keping Long, Shiduan Cheng, “A simple model of IEEE 802.11 wireless LAN”, International Conferences on Info-tech and Info-net, 2001. Proceedings. ICII 2001 - Beijing.
2001 Volume 2, 29 Oct.-1 Nov. 2001 Page(s):514 – 519
Collision
Success
Success or
Failure
Figure 3. Operation of 802.11 DCF with BEB Algorithm
We also observe that The BEB algorithm causes a fast build-up (i.e., growth-rate) of waiting times spreading the backlog traffic over a larger time frame. However, this fast build-up of waiting time with increasing number of occurrence of collisions might not be appropriate for a MANET, wherein the contending nodes might leave the geographical location of contention itself after a short while due to their mobility. In view of this, we conjecture that it may not be necessary to make a node wait for a duration that builds up exponentially with a binary base.
[1] IEEE 802.11 standard, “Wireless LAN Medium Access Control (MAC) and Physical Layer (PHY) Specifications,” IEEE Std. June 1999.
[2] C. Rama Krishna, Saswat Chakrabarti, and Debasish Dutta, “A modified backoff algorithm for IEEE 802.11 DCF based MAC protocol in a Mobile Ad-Hoc Network”, TENCON 2004.
[3] Chonggang Wang, Weiwen Tang, Kazem Sohraby, Bo Li, “A simple mechanism on MAC layer to improve the performance of IEEE 802.11 DCF”, Broadband Networks, 2004. BroadNets
2004. Proceedings of First International Conference on
Broadband networks 2004
[4] Guanghong Wang, Yantai Shu, Liang Zhang, Oliver W.W.
Yang,“Improving DCF in IEEE 802.11 Wireless LAN”, IEEE CCECE 2003. CanadianConference on Electrical and Computer
Engineering, 2003.
IJSER © 2011 http://www.ijser.org
International
5
ISSN 2229-5518
Journal of Scientific &
Eng ineering
Research
Volume 2, Issue 6, June-2011
IJSER lb)2011