PLANETE project, INRIA [imad.aad, qiang.ni, chadLbarakat, thierry.turletti]@inriaJr http://www.inria.fr/planete.html 11 is the most deployed wireless local area networking standard nowadays. It uses carrier sense multiple access with collision avoidance (CSMAlCA) to resolve contention between nodes. Contention windows (CW) change dynamically to adapt to the contention level: Upon each collision, a node doubles its CW to reduce further collision risks. Upon a successful trausmission, the CW is reset, assuming that the contention level has dropped. However, contention level is more likely to change slowly, and resetting the CW causes new collisions and retransmissions before reaching the optimal value again. This wastes bandwidth and increases delays. In this paper we analyze simple slow CW decrease functions and compare their performances to the legacy standard.. We use simulations and mathematical modeling to show their considerable improvements at all contention levels and transient phases, especially in high congested environments. Wireless access networks are experiencing a huge success similar to that of the deployment of the Internet a decade ago. Wireless devices are used almost everywhere to provide cheap, mobile and easy to deploy networks, with or without access to wired infrastructures like the Internet. Wireless access networks can be grouped into two categories: Centralized or distributed (ad-hoc). Centralized architectures are mainly controlled by a coordinator that grants access to the wireless nodes in its area in a contention free manner. On the other hand, distributed architectures have no central coordinators: All nodes contend to access the chann el using a distributed The next section presents the motivations and related work. Section III introduces the approach of slow CW decrease (SD) and evaluates its performances from the throughput, delay and jitter point of view, using simulations and mathematical modeling. Section IV introduces another performance metric, the settling time of SD. Section V explores the fairness prop erties of the proposed SD scheme, then section VI analyzes its ener g y savin g s. We analyze in Section VII the channel noise effect on the mechanism. Section VIII concludes the paper. In a distributed wireless congested environment, a station has no knowledge of the number of contending terminals. The 802.11 standard MAC protocol adapts its CW to the current congested level by doubling its CW upon each collision, and resetting it upon a successful transmission. Doubling the CW assumes a higher congestion level and therefore the need to increase the CWo When a node increases its CW, it reduces the chances of simultaneous transmissions with other nodes, at the cost of more backoff overhead. This reduces collisions and the corresponding retransmission times, therefore improving the throughput. When a node succeeds to transmit a frame, it assumes that the congestion level has dropped, and therefore it resets its CW to CWmin. However, when a node succeeds to transmit a frame at a given CW;, this does not correspond to a congestion level decrease, but rather to a convenient CW value. Therefore the CW value must be kept large as long as the congestion level remains the same. By resetting the CW, a node takes the risk of experiencing the same colli s ion s and retransmissions until it reaches convenient (high) CW values again, wasting time and bandwidth. To adapt the CW to possible congestion level drops, we should consider decreasing the CW upon successful trans missions. However, since congestion level is not likely to drop suddenly, we should consider slow CW decrease (SD) functions. Intuitively, the advantage of SD functions is more collision avoidance during congestion, leading to less col lisions and retransmissions, which increases throughput and decreases delays. The drawback is keeping high CW values after congestion level drops, increasing the overhead and decreasing the throughput. This inconvenience is negligible compared to the advantage of SD, since it is very unlikely that the congestion drops quickly to low levels. In the fol lowing sections we propose SD functions and evaluate their performances by comparing them to the actual standard in different scenarios. The slow CW decrease was first introduced in MACAW [5] which is an extensions to the CSMA and MACA schemes: The main idea of MACAW was to increase the CW at each collision by multiplying it by 1.5, and to linearly decrease it by I at each successful frame transmission. The approach was called MILD (multiplicative increase, linear decrease). But it did not explore the effect of other decrease factors than linear decrease on channel efficiency. Furthermore, only throughput measure in infrastructure mode was considered. Ad-hoc topology and other performance metrics like fairness, delays, resilience to noise, power consumption and settling times remained unexplored. In [6], the slow CW decrease was considered, but from the fairness enhancement point of view. [6] tries to establish local utility functions in order to achieve system-wide fairness, with no explicit global coordination. Then, it "translates" a given fairness model into corresponding backoff-based col lision resolution algorithms that probabilistically achieve the fairness objective. These algorithms include different backoff increase/decrease factors. [61 tries to enhance the fairness properties that MACAW [5] and CB-Fair first proposed in [7]. Always aiming to establish fair contention algorithms, [7] uses smooth CW increase and decrease functions. Each station i contends to access the channel in order to send a frame to station j with a probability Pij, computed in two ways using time-based and connection-based methods. These methods are pre-established using information broadcast by each station such as the number of logical connections and the contention time. In this paper we aim to investigate different CW decrease functions from the data rate, delay, response time, fairness and power saving efficiency point of view. Our main contributions are: (i) we propose an efficient multiplicative CW decrease a . �proach to improve the throughput of 802.11 MAC protocol; (11) we use mathematical modeling and simulation results to evaluate the performance of the SD scheme in different scenarios. Consider 100 wireless stations uniformly distributed in a lOOxlOOm square area communicating with each other two by f 100 ·---+----t-----l�---r·--�f two (50 f l ows). All nodes are within the range of each other, hence no routing protocol is needed. We start the simulation (using ns) at time t = 40 seconds (5). We increase the number of active f l ows by one every two seconds. Each transmitting station sends 1050-byte CBR packets every 5ms (providing full data rate of 1.6 Mbps). At t = 1508, all traffi c sources stop except one. At t = 260s, all sources stop sending data. Optimally, when the number of contending flows n increases, each flow would get 1/ n of the available data rate. However, due to the increasing collisions, actual throughput observed by each flow is lower this value. The dashed curve in Figure I shows how the total through put, averaged over one-second intervals, decreases as the number of contending flows increases (e.g. during t = 408 -+ 150s). In fact, after each collision, the source has to wait for a timeout to realize that the frame collided, increases its CW (to reduce further collision risks) then retransmits the frame. After a successful transmission the source resets its CWo As a node resets its CW after a successful transmission it "forgets" about the collision experience it had. If all stati�ns keep transmitting with the same data rate, most probably the new transmission will observe contention and collisions as before. This can be avoided by keeping some history on the observed collisions: Instead of resetting the CW to CW . we set the CW to 0.9 times its previous value (lower bounded by CWmi n , i.e. CWnew = max{CWmin,0.9 x CWprev} ). The solid curve in Figure 1 shows the considerable throughput enhancement we get (up to 37%), especially with high number of active flows (at t = 1508). When we decrease the CW slowly, we waste more time on backoff, but this is in favor of better collision avoidance. Furthermore, throughput is more stable, due to lower/smoother variations of CW values. SD is a tradeoff between large CW values and risking a collision followed by the whole frame retransmission. Since the time indu�ed by the latter is much larger than the backoff time, SD IS much better on average. The average overhead due to backoff and retransmissions can be written as: where Peol is the probability of a collision, Obko/(j) is the overhead due to backoff time at stage j of the successful The worst case for SD would be when we consider high CW values, but no congestion is taking place. This is the case at t = 1508, when we stop all but one transmission in order to observe the remaining throughput. Figure 1 shows that SD still behaves better than resetting the CWO After few successful transmissions, SD would reach the CW min value that CW reset scheme would have directly reached. Note that the CW reset scheme takes long time to increase its throughput. In fact, all traffic sources (but one) stop at t = 1508, but the effect is "shifted" to around t = 1688. This is due to the residual frames queued in the interfaces of all 49 transmitters (the interface queue length is 50 frames). After sources stop, these remaining frames will continue contending to access the channel, which possibly cause collisions. Consider now the same scenario as before, but with shorter interface queue lengths (= 2), in order to remove the effect of smoothly stopping sources and observe the real overhead due to SD. Figure 2 shows that the above queueing effects are eliminated, and the overhead due to SD can be observed in its worst case (no congestion, high CW values. i.e. at t = 1508). This shows that SD performs as well as CW reset scheme at low congestion, even right after high congestion. This can be considered as the response of the function to the congestion changing frequency at its maximum, i.e. when the number of contending nodes vary up and down very fast. SD performs
The authors of REF propose to multiplicatively decrease the contention window after a successful transmission using a decrease factor δ in the range [0, 1] that is set constant for all stations.
Enhancing IEEE 802.11 MAC in congested environments
2004 4th Workshop on Applications and Services in Wireless Networks, 2004. ASWN 2004.
2004 4th Workshop on Applications and Services in Wireless Networks, 2004. ASWN 2004.
Computer Science