# Collision Resolution Schemes with Nonoverlapped Contention Slots for Heterogeneous and Homogeneous WLANs

Authors: Raksha Upadhyay; Prakash D. Vyavahare; Sanjiv Tokekar
Journal: Journal of Engineering
 (2013)

---

## Abstract

CSMA/CA-based DCF of 802.11 MAC layer employs a best-effort delivery model, in which stations compete for channel access with the same priority. In a heterogeneous network, providing different priorities to different applications for required quality of service is a challenging task, since heterogeneous conditions result in unfairness among stations and degradation in the throughput. This paper proposes a class of collision resolution schemes for 802.11 having contention window control with nonoverlapped contention slots. In the first scheme, window ranges of two consecutive stages are nonoverlapped, and it is called nonoverlapped contention slots (NOCS) scheme. In the other scheme, termed as NOCS-offset, an offset is introduced between window ranges of two stages. Selection of a random value by a station for its contention with discontinuous distribution results in reduced probability of collision. Analytical and simulation results show that the proposed scheme exhibits higher throughput and fairness with reduced delay and collision probability in homogeneous and heterogeneous networks. Performance of the proposed scheme is evaluated for mix traffic and high data rate environment with advanced back-off management techniques to meet the requirements of the present applications.


---

## Body

## 1. Introduction

The MAC layer of 802.11 employs CSMA/CA-based distributed coordination function (DCF) as the fundamental mechanism to access the wireless medium. The DCF at a backlogged station uses binary exponential back-off (BEB) collision resolution mechanism [1] in which a station experiencing packet collision during transmission doubles its contention window size after each collision before it attempts retransmission of collided packet. The simplicity of BEB has resulted in its inclusion in 802.11 DCF. Subsequently, many versions of the BEB appeared in the literature with improved system performance. In [2], the average size of the contention window is derived which maximizes the network throughput. Fast collision resolution algorithm is proposed in [3], in which future collisions are avoided by changing the contention window size for deferring stations and regenerating the back-off timers for all potential transmitting stations. Slow contention window decrease schemes are proposed in [4], which results in improved system performance for overloaded active stations. Multiplicative increase linear decrease (MILD) and sensing back-off algorithms (SBA) schemes are proposed in [5] as an attempt to increase the channel throughput and fairness of random access in BEB. In [6], a new MAC protocol is proposed in which, after each unsuccessful transmission of packets of the different priority class, the new contention window of the class is increased with some persistence factor and contention window is updated. All these schemes, including traditional one, are based on extending the contention window ranges during various stages of retransmission attempts and suffer from collisions due to overlapped contention slots (CS). The issue of minimizing the collisions due to overlapped contention slot is addressed in [7]. Recently, DCFCOMIC is proposed [8], in which an alternate attempt is made to minimize the selection of CS in overlapped region. Truncated normal distribution with intelligent control is used in DCFCOMIC instead of uniform distribution of BEB to evaluate the system performance numerically. However, it is pointed out in [9] that the system performance depends only on mean back-off value irrespective of its distribution.Mathematical modeling of various DCFs has been the topic of current research. Bianchi [10] presented an analytical model of the DCF under the assumption that stations are saturated, homogenous, and decoupled with no hidden stations. Refinement on the DCF modeling approach is presented in [11]. In this paper, the authors evaluate the implications of actual back-off rules on the channel access process in the presence of anomalous slots (the slots immediately following a successful transmission). In [12] medium access control protocol performance is evaluated in heterogeneous and nonsaturated conditions, in which a new state is added in Bianchi’s model to account for the unsaturated behavior of the network. The throughput performance of 802.11 networks in the presence of hidden stations is evaluated in [13]. A generalized framework is presented in [9] to model the DCF in which transmission probability as given in Bianchi’s model is expressed in terms of mean back-off value of contention window. In this paper, the approach used in [9] is extended to create the system model of the proposed schemes.In this paper, a class of algorithms NOCS and NOCS-OS is proposed which are based on avoidance in overlapped contention slots with the window ranges of other stages. Nonoverlapped CS results in reduction in probability of collisions. This NOCS mechanism increases the mean value of back-off counter for different stages, which in turn increases the numbers of contention slots available for contention phase and reduces the collisions. System model is formulated for the proposed schemes. Performance measures such as the probability of collision, normalized throughput, and average end-to-end delay are evaluated for the proposed schemes and convention schemes. Analytical results are validated against those obtained from simulation. For NOCS-OS, the effect on system performance is investigated with different offset values. The optimum value of offset is calculated beyond which system performance degrades for NOCS-OS scheme. Performances of these schemes are also evaluated in heterogeneous network, in mixed traffic conditions, and in high data rate WLANs including the features of advanced back-off management. Significant improvement is found in terms of fairness and throughput of the system in the proposed schemes.The paper is organized as follows. In Section2, new back-off schemes are proposed. System model for the proposed back-off scheme is formulated in Section 3 and system performance measures such as throughput and average delay are briefly explained. In Section 4, model for heterogeneous network is presented with derivation of expression for throughput. Section 5 presents simulation and analytical results of proposed schemes for their comparison with conventional one. Results are evaluated for homogeneous and heterogeneous networks. Performances of the proposed schemes are also evaluated in the realistic conditions with the frame aggregation and the block acknowledgment features. Finally, the paper is concluded in Section 6.


## 2. Proposed Back-Off Schemes

DCF of IEEE 802.11 adopts the conventional back-off scheme. A station with a packet for transmission is called backlogged station. A backlogged station is initially in the stage one and selects a value from the range of numbers of the contention window. This value is called the slot number or back-off counter value. The slot number is uniformly chosen in the range[0,2kCW-1], where CW is the initial size of contention window in the first stage and k denotes the number of transmission attempts made by a packet before successful transmission. The station is said to be in stage one during first attempt of transmission of a packet with window range [0,CW-1]. At the beginning of each slot time, station reduces the back-off counter value by one. It attempts to transmit in a slot number if the counter value is zero. Collision takes place whenever the back-off counter value of two or more stations becomes zero at the same slot time, otherwise it results in successful transmission. After each unsuccessful transmission window range is doubled for stages 1 to s. For stages (s+1) to K, the window size is constant and has a value which is same for that of stage s. The station is said to be in (k+1)th stage if collided packet is retransmitted for kth time, where 0≤k≤K-1. This process is continued until either the packet is successfully transmitted or k reaches a predetermined maximum value. In either case, the station moves to stage one and the same process is continued for the transmission of next backlogged packet at the station. Figure 1 shows the probability distribution of CS in (k-1)th stage and kth stages for conventional scheme.Figure 1
Probability distribution of window ranges in conventional scheme for(k-1)th stage and kth stage.In the conventional back-off scheme, extended window ranges after each collision consists of overlapped region and nonoverlapped region with other contention window ranges. It is observed that system performance can be improved if the overlapped contention slots are reduced. Therefore, improved collision resolution schemes are proposed to eliminate overlapped contention slots for reduction in collision probability. Two such schemes, NOCS and NOCS-OS are proposed in subsequent section to reduce the probability of collision by avoiding the overlapped contention slots.


### 2.1. Nonoverlapped Contention Slots Scheme (NOCS)

Figure2 shows the distribution of CS in first and second stages for the NOCS scheme. Initially, a backlogged station is in the first stage and its back-off counter value is uniformly distributed in the entire range [0,CW-1]. A packet collision is said to have occurred when its transmission overlaps with that of other station. In such cases, the station moves to higher stage, doubles its contention window size, and selects a value for its back-off counter with uniform distribution, which is nonoverlapped with the previous window range, for example, [CW,3CW-1] for second stage. Entire window ranges in the higher stages are nonoverlapped with previous and other stages. Nonoverlapped distribution reduces significantly chances of having the same slot number of the stations as the stations of other stages during back-off. This reduces the collision probability.Figure 2
Probability distribution of window ranges in NOCS scheme for first and second stages.


### 2.2. Nonoverlapped Contention Slots Scheme with Offset (NOCS-OS)

Though collisions are reduced in the NOCS scheme significantly due to nonoverlapping window ranges of any two stages, it has a notable value. This happens because the back-off counter value of any two stations may become zero simultaneously irrespective of their stages and due to random time at which different counter values are selected by these stations. The collision probability occurring in the NOCS scheme can be further reduced if the station selects the contention window value with an offset as compared to that in the NOCS scheme. This scheme proposes a concept of addition of an offset value in between two stages. This offset further reduces the chances of collision of packets of two different stages. Figure3 shows the distribution of CS in the first and second stages. There is an offset between the two stages. Offset range can be varied as a design parameter. This further reduces collisions probability.Figure 3
Probability distribution of window ranges in NOCS-OS scheme for first and second stages.


## 2.1. Nonoverlapped Contention Slots Scheme (NOCS)

Figure2 shows the distribution of CS in first and second stages for the NOCS scheme. Initially, a backlogged station is in the first stage and its back-off counter value is uniformly distributed in the entire range [0,CW-1]. A packet collision is said to have occurred when its transmission overlaps with that of other station. In such cases, the station moves to higher stage, doubles its contention window size, and selects a value for its back-off counter with uniform distribution, which is nonoverlapped with the previous window range, for example, [CW,3CW-1] for second stage. Entire window ranges in the higher stages are nonoverlapped with previous and other stages. Nonoverlapped distribution reduces significantly chances of having the same slot number of the stations as the stations of other stages during back-off. This reduces the collision probability.Figure 2
Probability distribution of window ranges in NOCS scheme for first and second stages.


## 2.2. Nonoverlapped Contention Slots Scheme with Offset (NOCS-OS)

Though collisions are reduced in the NOCS scheme significantly due to nonoverlapping window ranges of any two stages, it has a notable value. This happens because the back-off counter value of any two stations may become zero simultaneously irrespective of their stages and due to random time at which different counter values are selected by these stations. The collision probability occurring in the NOCS scheme can be further reduced if the station selects the contention window value with an offset as compared to that in the NOCS scheme. This scheme proposes a concept of addition of an offset value in between two stages. This offset further reduces the chances of collision of packets of two different stages. Figure3 shows the distribution of CS in the first and second stages. There is an offset between the two stages. Offset range can be varied as a design parameter. This further reduces collisions probability.Figure 3
Probability distribution of window ranges in NOCS-OS scheme for first and second stages.


## 3. Analysis of the Proposed Schemes

### 3.1. System Model

The DCF of 802.11 has been modeled as the two-dimensional Markov chain by Bianchi in [10]. In [9], simplified and generalized analysis of the DCF is performed. Modeling and analysis of the DCF for the scheme proposed in previous section are based on generalized frame work model described in [9]. The proposed model is based on similar assumptions. The transmission queue of each station is always nonempty and all stations are homogeneous; that is, the back-off parameters of all the stations are the same. At each transmission attempt, each packet collides with the constant and independent collision probability p. The nodes are assumed to attempt in each slot with the constant probability equal to the average attempt rate τ, which is given by
(1)τ=∑k=0K-1pk∑k=0K-1bkpk,
where bk is the mean back-off value, which depends on the range of contention window number at the kth stage and probability distribution of CS by the station. For a system with n number of stations, the conditional collision probability of a packet during transmission is given by
(2)p=1-(1-τ)n-1.Equations (1) and (2) form a system with nonlinear equations, which can be solved numerically. System equations can be used to represent the system of the DCF for proposed back-off schemes with modification in (1), which is given by
(3)τ=∑k=0K-1pk∑k=0K-1bmkpk,
in which bmk is the modified mean back-off value for proposed schemes. For NOCS scheme, bmk is given by
(4)bmk=(2k×1.5-1)CW,1≤k≤K-1.For NOCS-OS offset,bmk is given by
(5)bmk=(2k×1.5-1)CW+Offset,1≤k≤K-1.
For k=0, the mean back-off value is the same in both of the proposed schemes as for the conventional scheme and is given by CW/2, where CW is initial size of contention window in the first stage.


### 3.2. Performance Measures

#### 3.2.1. Throughput

LetS be the normalized system throughput which according to [1] defined as the fraction of the time; the channel is used to successfully transmit payload bits:
(6)S=TTsE[U]E[U]+E[NU],
where E[U] is the expected value of useful period and E[NU] is the expected value of non useful period, Ts is the time interval, for which medium is sensed busy due to successful transmission, and T is the packet length. E[U] can be computed as follows:
(7)E[U]=nτ(1-τ)n-1Ts,
where Ts expressed by T+SIFS+DIFS+ACK+2α, where DIFS, SIFS, and ACK are distributed interframe space delay, shortest interframe space delay, and acknowledgment delay, respectively, and α is the propagation delay.The expected value of the nonuseful period is given by(8)E[NU]=E[IDLE]+E[UTC],
in which E[IDLE] is mean time duration of a slot being idle and E[UTC] is mean time duration of unsuccessful transmission due to collisions and are given by
(9)E[IDLE]=(1-τ)nσ,(10)E[UTC]=[1-(1-τ)n-nτ(1-τ)n-1]Tc,
where Tc is the time interval, medium is sensed busy due to collision and is expressed as T+DIFS+α, and σ is the time duration of a slot.


#### 3.2.2. Delay

The time duration between the packet arrival at the front of sending stations transmit buffer to its successful reception at the receiver is called the packet delay,Td [14]. It is given by the expression Td=E[D]T, where E[D] is the average number of slots needed for successful transmission and is given by
(11)E[D]=∑k=0sbmkpk-ps+f+11-ps+f+1+∑k=s+1s+f=K-1bmaxpk-ps+f+11-ps+f+1;
note that bmk is the mean back-off duration in stage k, s is the total number of back-off stages with different bmk, bmax is the maximum value of mean back off counter (which is same for s+1≤k≤s+f), and (s+f) is retry limit, which is equal to K.


#### 3.2.3. Fairness

A network is considered to be fair if each station achieves the same long-term throughput, that is,1/n share of total bandwidth. Fairness index (FI), the measure of fairness, is given by [15]
(12)FI=(∑i=1nTi/ϕi)2n∑i=1n(Ti/ϕi)2,
where n is the number of flows, Ti is the throughput of flow i, and ϕiis the weight of flow i. It is evident that FI≤1 and equality holds if and only if all Ti/ϕi are equal. Therefore, the closer FI approaches 1, the better is throughput fairness.


## 3.1. System Model

The DCF of 802.11 has been modeled as the two-dimensional Markov chain by Bianchi in [10]. In [9], simplified and generalized analysis of the DCF is performed. Modeling and analysis of the DCF for the scheme proposed in previous section are based on generalized frame work model described in [9]. The proposed model is based on similar assumptions. The transmission queue of each station is always nonempty and all stations are homogeneous; that is, the back-off parameters of all the stations are the same. At each transmission attempt, each packet collides with the constant and independent collision probability p. The nodes are assumed to attempt in each slot with the constant probability equal to the average attempt rate τ, which is given by
(1)τ=∑k=0K-1pk∑k=0K-1bkpk,
where bk is the mean back-off value, which depends on the range of contention window number at the kth stage and probability distribution of CS by the station. For a system with n number of stations, the conditional collision probability of a packet during transmission is given by
(2)p=1-(1-τ)n-1.Equations (1) and (2) form a system with nonlinear equations, which can be solved numerically. System equations can be used to represent the system of the DCF for proposed back-off schemes with modification in (1), which is given by
(3)τ=∑k=0K-1pk∑k=0K-1bmkpk,
in which bmk is the modified mean back-off value for proposed schemes. For NOCS scheme, bmk is given by
(4)bmk=(2k×1.5-1)CW,1≤k≤K-1.For NOCS-OS offset,bmk is given by
(5)bmk=(2k×1.5-1)CW+Offset,1≤k≤K-1.
For k=0, the mean back-off value is the same in both of the proposed schemes as for the conventional scheme and is given by CW/2, where CW is initial size of contention window in the first stage.


## 3.2. Performance Measures

### 3.2.1. Throughput

LetS be the normalized system throughput which according to [1] defined as the fraction of the time; the channel is used to successfully transmit payload bits:
(6)S=TTsE[U]E[U]+E[NU],
where E[U] is the expected value of useful period and E[NU] is the expected value of non useful period, Ts is the time interval, for which medium is sensed busy due to successful transmission, and T is the packet length. E[U] can be computed as follows:
(7)E[U]=nτ(1-τ)n-1Ts,
where Ts expressed by T+SIFS+DIFS+ACK+2α, where DIFS, SIFS, and ACK are distributed interframe space delay, shortest interframe space delay, and acknowledgment delay, respectively, and α is the propagation delay.The expected value of the nonuseful period is given by(8)E[NU]=E[IDLE]+E[UTC],
in which E[IDLE] is mean time duration of a slot being idle and E[UTC] is mean time duration of unsuccessful transmission due to collisions and are given by
(9)E[IDLE]=(1-τ)nσ,(10)E[UTC]=[1-(1-τ)n-nτ(1-τ)n-1]Tc,
where Tc is the time interval, medium is sensed busy due to collision and is expressed as T+DIFS+α, and σ is the time duration of a slot.


### 3.2.2. Delay

The time duration between the packet arrival at the front of sending stations transmit buffer to its successful reception at the receiver is called the packet delay,Td [14]. It is given by the expression Td=E[D]T, where E[D] is the average number of slots needed for successful transmission and is given by
(11)E[D]=∑k=0sbmkpk-ps+f+11-ps+f+1+∑k=s+1s+f=K-1bmaxpk-ps+f+11-ps+f+1;
note that bmk is the mean back-off duration in stage k, s is the total number of back-off stages with different bmk, bmax is the maximum value of mean back off counter (which is same for s+1≤k≤s+f), and (s+f) is retry limit, which is equal to K.


### 3.2.3. Fairness

A network is considered to be fair if each station achieves the same long-term throughput, that is,1/n share of total bandwidth. Fairness index (FI), the measure of fairness, is given by [15]
(12)FI=(∑i=1nTi/ϕi)2n∑i=1n(Ti/ϕi)2,
where n is the number of flows, Ti is the throughput of flow i, and ϕiis the weight of flow i. It is evident that FI≤1 and equality holds if and only if all Ti/ϕi are equal. Therefore, the closer FI approaches 1, the better is throughput fairness.


## 3.2.1. Throughput

LetS be the normalized system throughput which according to [1] defined as the fraction of the time; the channel is used to successfully transmit payload bits:
(6)S=TTsE[U]E[U]+E[NU],
where E[U] is the expected value of useful period and E[NU] is the expected value of non useful period, Ts is the time interval, for which medium is sensed busy due to successful transmission, and T is the packet length. E[U] can be computed as follows:
(7)E[U]=nτ(1-τ)n-1Ts,
where Ts expressed by T+SIFS+DIFS+ACK+2α, where DIFS, SIFS, and ACK are distributed interframe space delay, shortest interframe space delay, and acknowledgment delay, respectively, and α is the propagation delay.The expected value of the nonuseful period is given by(8)E[NU]=E[IDLE]+E[UTC],
in which E[IDLE] is mean time duration of a slot being idle and E[UTC] is mean time duration of unsuccessful transmission due to collisions and are given by
(9)E[IDLE]=(1-τ)nσ,(10)E[UTC]=[1-(1-τ)n-nτ(1-τ)n-1]Tc,
where Tc is the time interval, medium is sensed busy due to collision and is expressed as T+DIFS+α, and σ is the time duration of a slot.


## 3.2.2. Delay

The time duration between the packet arrival at the front of sending stations transmit buffer to its successful reception at the receiver is called the packet delay,Td [14]. It is given by the expression Td=E[D]T, where E[D] is the average number of slots needed for successful transmission and is given by
(11)E[D]=∑k=0sbmkpk-ps+f+11-ps+f+1+∑k=s+1s+f=K-1bmaxpk-ps+f+11-ps+f+1;
note that bmk is the mean back-off duration in stage k, s is the total number of back-off stages with different bmk, bmax is the maximum value of mean back off counter (which is same for s+1≤k≤s+f), and (s+f) is retry limit, which is equal to K.


## 3.2.3. Fairness

A network is considered to be fair if each station achieves the same long-term throughput, that is,1/n share of total bandwidth. Fairness index (FI), the measure of fairness, is given by [15]
(12)FI=(∑i=1nTi/ϕi)2n∑i=1n(Ti/ϕi)2,
where n is the number of flows, Ti is the throughput of flow i, and ϕiis the weight of flow i. It is evident that FI≤1 and equality holds if and only if all Ti/ϕi are equal. Therefore, the closer FI approaches 1, the better is throughput fairness.


## 4. Model for Heterogeneous Networks

Analysis given in the previous section is for the homogeneous network. In this section, the DCF model is presented for the heterogeneous network with two classes. Each class has the same station parameters including payload sizes, minimum and maximum values of the contention window, and arrival rate. Letn1 be the number of stations in class one and n2 the number of stations in class two, τ1, τ2, p1, and p2 are the attempt rates and collision probability for each class of the heterogeneous network, respectively. Then, the system can be represented by the following set of equations:
(13)p1=1-(1-τ1)n1-1(1-τ2)n2p2=1-(1-τ1)n1(1-τ2)n2-1τ1=∑k=0K-1p1k∑k=0K-1bk1p1kτ2=∑k=0K-1p2k∑k=0K-1bk2p2k,
in which bk1 and bk2 are the mean back-off durations of class one and class two. The throughput, the delay, and the fairness for the heterogeneous network will be expressed by the same equations ((6), (11), and (12), resp.) as those for the homogeneous networks with the modifications as given in the following equations:
(14)E[U]=PtrTs=[P1,tr+P2,tr]TS,
in which Ptr is the probability of only one transmission in the network with P1,tr is the probability of only one transmission from class one and P2,tr is the probability of only one transmission from class two of heterogeneous network. These are represented by the following equations:
(15)P1,tr=n1τ1(1-τ1)n1-1(1-τ2)n2(16)P2,tr=n2τ2(1-τ1)n1(1-τ2)n2-1.E[NU], the expected value of nonuseful period is given by (8), with modifications in expressions of E[IDLE] as given by
(17)E[IDLE]=[(1-Ptr)σ],
where (1-Ptr) is the probability of no transmission from any class in a slot duration the heterogeneous network and is given by
(18)1-Ptr=(1-τ1)n1(1-τ2)n2E[UTC], the mean time of unsuccessful transmission due to collisions for the heterogeneous network, is expressed by (19)
(19)E[UTC]=[1-(P1,tr+P2,tr)+(1-Ptr)]TC.Similarly, other parameters and the delay can be computed for heterogeneous network.


## 5. Results

### 5.1. Homogeneous WLAN

In this subsection, results are obtained for the homogeneous WLAN. Performance measures such as the average throughput, the mean delay, and the probability of collisions are evaluated for the conventional scheme and the proposed schemes. The results are compared with those obtained from analytical model for verification. MAC layer parameters with their values used in simulation are mentioned in Table1 [16].Table 1
MAC layer parameters.
Parameters
Values
Channel data rate
1 Mbps
SIFS
10μs
DIFS
50μs
ACK
300μs
Packet length
10 ms
Propagation delay
2μs
Slot time
20μs
No. of back-off stages
8Figure4 shows the collision probability of the system versus number of stations, for the conventional scheme, the NOCS scheme, and the NOCS-OS scheme. The performance of the system is evaluated for the different values of offset. The size of the window in case of proposed schemes in each stage is the same as in the conventional approach. It is observed that from n>20, there is significant reduction in collision probability. For n=70, reduction in collision probability is 22.6% for the NOCS scheme, as compared to the conventional scheme. Reduction in the collision probability increases as the offset is inserted between two stages and increased. Reduction in collision probability is 27.35%, 37.09%, 45.70%, 55.77%, and 65.44% for the offset value of CW, 4CW, 8CW, 16CW, and 32CW, respectively. This happens due to reduction in possibility of selecting the same slot by two or more colliding stations in the next stages and due to availability of more CS in the next stage.Figure 4
Collision probability for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Reduction in collision probability results in improvement in the system throughput. Figure5 shows the throughput for these schemes as a function of number of stations in the system. Performance improvement is 16.5% for the NOCS scheme. For the NOCS-OS scheme, performance improvement increases as the offset is increased. Improvement in the throughput for NOCS-OS scheme is 19.6%, 25.60%, 30.5%, 35.7%, and 40.20% for the offset values of CW, 4CW, 8CW, 16CW, and 32CW, respectively for n=70, in comparison with the conventional scheme. It is also found that there is an excellent match between the results from analytical model and with those obtained using simulation for all the schemes. All the simulation results are within 95% confidence interval.Figure 5
Saturation throughput for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Evaluation of Maximum Throughput. It is observed that as the value of the offset increases for the NOCS-OS scheme, performance of the system improves. Higher offset reduces the chances of selecting the same value by collided stations of different stages. This reduces the chances of collisions. It is found that a limit is reached after which throughput performance starts decrementing as offset value increases for a particular number of stations. This happens because higher offset results in increased idle slots in the system, thereby reducting the throughput. In [10], the optimum value of attempt rate, τopt is evaluated, at which maximum throughput is achieved, and is given by
(20)τopt≈1nTc*/2,
where Tc*=TC/σ in which Tc is the average time, the channel is sensed busy by each station during collision, and σ is the slot time. The optimum value of offset τopt is calculated using (20). The minimum collision probability is then calculated with the help of the optimum attempt rate and given by
(21)popt=1-(1-τopt)n-1.Finally using (5), (20), and (21), bmk can be calculated by solving the equation
(22)τopt=∑k=0K-1pk∑k=0K-1bmkpk,
where bmk can be expressed in terms of bm0, mean back of duration of first stage, and the offset. The optimum offset is then calculated for the proposed scheme. Figure 6 shows the throughput as a function of the offset value. Maximum value of the throughput for a particular number of stations can be observed from the figure. It can also be verified theoretically.Figure 6
Throughput as a function of offset value for NOCS-OS scheme for a different number of stations.Figure7 shows the packet delay as a function of the number of stations for the conventional, the NOCS, and the NOCS-OS schemes. In the proposed schemes, mean value of the back-off counter is more as compared to conventional scheme. This is the result of increased idle counts. These idle counts do not increase the average end-to-end delay as compared to the conventional scheme because these schemes are less collision prone and time delay involved in one collision is much more as compared to multiple idle slots. The delay performance is better as compared to conventional scheme as can be observed from Figure 7. Reduction in the mean delay performance for offset values of CW, 4CW, 8CW, 16CW, and 32CW are 5.8%, 7.5%, 9.9%, 13.2%, and 15.04%, respectively, while the delay reduction is 3.7% in case of the NOCS scheme. Figure 8 shows the fairness index for homogeneous networks using conventional and proposed schemes. There is comparable performance of fairness index for conventional and proposed schemes.Figure 7
Packet delay for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Figure 8
Fairness index for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.


### 5.2. Performance of the Proposed Approach in Emerging WLANs

Most of the real-time applications such as web and email are typically bursty in nature with variable demanded transmission rate. Moreover, different applications may require different priorities. High data rate and higher throughput is the requirement of high-speed WLANs. In this section, the performance of the proposed scheme is evaluated in different real-time conditions and in high-speed WLANs.


#### 5.2.1. Heterogeneous Network

The heterogeneous network model consists of two classes of stations with different values of contention window size. For class two, the minimum size of contention window is considered as 7, while for class one it is 32, the same as in homogeneous case. Other parameters are the same for both of the classes and are shown in Table1.When the proposed schemes are applied to the heterogeneous network, substantial change in the network performance is achieved. Figure9 shows the throughput of the heterogeneous network with the conventional scheme and the proposed scheme. Throughput for the NOCS-OS scheme is evaluated for different values of OS. Throughput improvement of 51%, 60%, 67%, and 74% is achieved for the offset of CW, 4CW, 8CW, and 16CW, respectively, for n=70. Since more slots are now available for back-off, this results in the improved system performance. The fairness index is also evaluated for the heterogeneous network using the conventional and the NOCS-OS schemes. Fairness is improved by 35%, 36%, 37.2%, and 37.4% for offset values of CW, 4CW, 8CW, and 16CW for n=70 as shown in Figure 10.Figure 9
Throughput for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.Figure 10
Fairness index for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.


#### 5.2.2. Mixed Traffic

In this subsection, the performance of the NOCS-OS scheme is evaluated for a mixed traffic environment. The network is grouped into two subgroups. Each subgroup is carrying different data types. Queues of group one stations are saturated, while bursty traffic is applied to group two stations, which is Poisson distributed [17]. There are 15 numbers of stations in each subgroup and simulation is performed on 30 numbers of stations. Figure 11 shows the normalized per station throughput as a function of the load on group two stations. Difference in the outcomes can be observed when the simulation is performed using the NOCS-OS scheme with OS value is equal to CW. For higher offset values network, performance would be better. Overall network throughput is shown in Figure 12 for n=10 and n=30 as function of load on group two stations. Performance improvement in proposed scheme is 4% for n=10 and is 12.3% for n=30.Figure 11
Normalized per station throughput for conventional and NOCS-OS scheme as a function of load of group two stations.Figure 12
Normalized throughput for conventional and NOCS-OS scheme as a function of load of group two stations.


#### 5.2.3. Higher Data Rates

Higher data rate is the requirement of most of the present applications. It is well known that as the data increases throughput decreases. The drop in the throughput results from the fixed overhead in the preamble and in the interframe space [18]. Performance of the NOCS-OS scheme has been shown in Figure 13 for different data rates with offset is equal to CW. It is also compared with the conventional scheme. It is observed that for a wide range of data rates the proposed scheme performs better, but the performance improvement reduces over the conventional scheme as data rate increases. Outcomes are computed for mixed traffic with group one stations in saturation, while group two stations follow the Poisson traffic with 0.4 arrival rate. All other parameters are set according to 802.11 a/g standard.Figure 13
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes (bold lines for conventional and dashed lines for proposed scheme).


#### 5.2.4. Advanced Back-Off Management Techniques

The most important features of the high-speed WLANs are frame aggregation and block acknowledgment for the enhancement of the MAC throughput. In this subsection, the performance of the proposed scheme and the conventional schemes are compared by incorporating these two features of the high-speed WLANs. Figure14 shows the comparison of the conventional and the NOCS-OS scheme for two formats of block acknowledgments with frame aggregation. One format uses 128-byte uncompressed block acknowledgment and the other one uses 8-byte compressed block acknowledgment [16]. The offset value is set to CW, traffic is considered bursty with average burst size set to ten. Arrival rate is kept as 0.5 packets per slot time and data rate is considered as 54 Mbps. Acknowledgment frames are transmitted at the rate of 6 Mbps. It is observed that the performance of the NOCS-OS scheme is little better as compared to that of conventional scheme.Figure 14
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes for advanced back-off management technique.


## 5.1. Homogeneous WLAN

In this subsection, results are obtained for the homogeneous WLAN. Performance measures such as the average throughput, the mean delay, and the probability of collisions are evaluated for the conventional scheme and the proposed schemes. The results are compared with those obtained from analytical model for verification. MAC layer parameters with their values used in simulation are mentioned in Table1 [16].Table 1
MAC layer parameters.
Parameters
Values
Channel data rate
1 Mbps
SIFS
10μs
DIFS
50μs
ACK
300μs
Packet length
10 ms
Propagation delay
2μs
Slot time
20μs
No. of back-off stages
8Figure4 shows the collision probability of the system versus number of stations, for the conventional scheme, the NOCS scheme, and the NOCS-OS scheme. The performance of the system is evaluated for the different values of offset. The size of the window in case of proposed schemes in each stage is the same as in the conventional approach. It is observed that from n>20, there is significant reduction in collision probability. For n=70, reduction in collision probability is 22.6% for the NOCS scheme, as compared to the conventional scheme. Reduction in the collision probability increases as the offset is inserted between two stages and increased. Reduction in collision probability is 27.35%, 37.09%, 45.70%, 55.77%, and 65.44% for the offset value of CW, 4CW, 8CW, 16CW, and 32CW, respectively. This happens due to reduction in possibility of selecting the same slot by two or more colliding stations in the next stages and due to availability of more CS in the next stage.Figure 4
Collision probability for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Reduction in collision probability results in improvement in the system throughput. Figure5 shows the throughput for these schemes as a function of number of stations in the system. Performance improvement is 16.5% for the NOCS scheme. For the NOCS-OS scheme, performance improvement increases as the offset is increased. Improvement in the throughput for NOCS-OS scheme is 19.6%, 25.60%, 30.5%, 35.7%, and 40.20% for the offset values of CW, 4CW, 8CW, 16CW, and 32CW, respectively for n=70, in comparison with the conventional scheme. It is also found that there is an excellent match between the results from analytical model and with those obtained using simulation for all the schemes. All the simulation results are within 95% confidence interval.Figure 5
Saturation throughput for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Evaluation of Maximum Throughput. It is observed that as the value of the offset increases for the NOCS-OS scheme, performance of the system improves. Higher offset reduces the chances of selecting the same value by collided stations of different stages. This reduces the chances of collisions. It is found that a limit is reached after which throughput performance starts decrementing as offset value increases for a particular number of stations. This happens because higher offset results in increased idle slots in the system, thereby reducting the throughput. In [10], the optimum value of attempt rate, τopt is evaluated, at which maximum throughput is achieved, and is given by
(20)τopt≈1nTc*/2,
where Tc*=TC/σ in which Tc is the average time, the channel is sensed busy by each station during collision, and σ is the slot time. The optimum value of offset τopt is calculated using (20). The minimum collision probability is then calculated with the help of the optimum attempt rate and given by
(21)popt=1-(1-τopt)n-1.Finally using (5), (20), and (21), bmk can be calculated by solving the equation
(22)τopt=∑k=0K-1pk∑k=0K-1bmkpk,
where bmk can be expressed in terms of bm0, mean back of duration of first stage, and the offset. The optimum offset is then calculated for the proposed scheme. Figure 6 shows the throughput as a function of the offset value. Maximum value of the throughput for a particular number of stations can be observed from the figure. It can also be verified theoretically.Figure 6
Throughput as a function of offset value for NOCS-OS scheme for a different number of stations.Figure7 shows the packet delay as a function of the number of stations for the conventional, the NOCS, and the NOCS-OS schemes. In the proposed schemes, mean value of the back-off counter is more as compared to conventional scheme. This is the result of increased idle counts. These idle counts do not increase the average end-to-end delay as compared to the conventional scheme because these schemes are less collision prone and time delay involved in one collision is much more as compared to multiple idle slots. The delay performance is better as compared to conventional scheme as can be observed from Figure 7. Reduction in the mean delay performance for offset values of CW, 4CW, 8CW, 16CW, and 32CW are 5.8%, 7.5%, 9.9%, 13.2%, and 15.04%, respectively, while the delay reduction is 3.7% in case of the NOCS scheme. Figure 8 shows the fairness index for homogeneous networks using conventional and proposed schemes. There is comparable performance of fairness index for conventional and proposed schemes.Figure 7
Packet delay for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.Figure 8
Fairness index for conventional, NOCS, and NOCS-OS schemes as a function of number of stations.


## 5.2. Performance of the Proposed Approach in Emerging WLANs

Most of the real-time applications such as web and email are typically bursty in nature with variable demanded transmission rate. Moreover, different applications may require different priorities. High data rate and higher throughput is the requirement of high-speed WLANs. In this section, the performance of the proposed scheme is evaluated in different real-time conditions and in high-speed WLANs.


### 5.2.1. Heterogeneous Network

The heterogeneous network model consists of two classes of stations with different values of contention window size. For class two, the minimum size of contention window is considered as 7, while for class one it is 32, the same as in homogeneous case. Other parameters are the same for both of the classes and are shown in Table1.When the proposed schemes are applied to the heterogeneous network, substantial change in the network performance is achieved. Figure9 shows the throughput of the heterogeneous network with the conventional scheme and the proposed scheme. Throughput for the NOCS-OS scheme is evaluated for different values of OS. Throughput improvement of 51%, 60%, 67%, and 74% is achieved for the offset of CW, 4CW, 8CW, and 16CW, respectively, for n=70. Since more slots are now available for back-off, this results in the improved system performance. The fairness index is also evaluated for the heterogeneous network using the conventional and the NOCS-OS schemes. Fairness is improved by 35%, 36%, 37.2%, and 37.4% for offset values of CW, 4CW, 8CW, and 16CW for n=70 as shown in Figure 10.Figure 9
Throughput for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.Figure 10
Fairness index for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.


### 5.2.2. Mixed Traffic

In this subsection, the performance of the NOCS-OS scheme is evaluated for a mixed traffic environment. The network is grouped into two subgroups. Each subgroup is carrying different data types. Queues of group one stations are saturated, while bursty traffic is applied to group two stations, which is Poisson distributed [17]. There are 15 numbers of stations in each subgroup and simulation is performed on 30 numbers of stations. Figure 11 shows the normalized per station throughput as a function of the load on group two stations. Difference in the outcomes can be observed when the simulation is performed using the NOCS-OS scheme with OS value is equal to CW. For higher offset values network, performance would be better. Overall network throughput is shown in Figure 12 for n=10 and n=30 as function of load on group two stations. Performance improvement in proposed scheme is 4% for n=10 and is 12.3% for n=30.Figure 11
Normalized per station throughput for conventional and NOCS-OS scheme as a function of load of group two stations.Figure 12
Normalized throughput for conventional and NOCS-OS scheme as a function of load of group two stations.


### 5.2.3. Higher Data Rates

Higher data rate is the requirement of most of the present applications. It is well known that as the data increases throughput decreases. The drop in the throughput results from the fixed overhead in the preamble and in the interframe space [18]. Performance of the NOCS-OS scheme has been shown in Figure 13 for different data rates with offset is equal to CW. It is also compared with the conventional scheme. It is observed that for a wide range of data rates the proposed scheme performs better, but the performance improvement reduces over the conventional scheme as data rate increases. Outcomes are computed for mixed traffic with group one stations in saturation, while group two stations follow the Poisson traffic with 0.4 arrival rate. All other parameters are set according to 802.11 a/g standard.Figure 13
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes (bold lines for conventional and dashed lines for proposed scheme).


### 5.2.4. Advanced Back-Off Management Techniques

The most important features of the high-speed WLANs are frame aggregation and block acknowledgment for the enhancement of the MAC throughput. In this subsection, the performance of the proposed scheme and the conventional schemes are compared by incorporating these two features of the high-speed WLANs. Figure14 shows the comparison of the conventional and the NOCS-OS scheme for two formats of block acknowledgments with frame aggregation. One format uses 128-byte uncompressed block acknowledgment and the other one uses 8-byte compressed block acknowledgment [16]. The offset value is set to CW, traffic is considered bursty with average burst size set to ten. Arrival rate is kept as 0.5 packets per slot time and data rate is considered as 54 Mbps. Acknowledgment frames are transmitted at the rate of 6 Mbps. It is observed that the performance of the NOCS-OS scheme is little better as compared to that of conventional scheme.Figure 14
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes for advanced back-off management technique.


## 5.2.1. Heterogeneous Network

The heterogeneous network model consists of two classes of stations with different values of contention window size. For class two, the minimum size of contention window is considered as 7, while for class one it is 32, the same as in homogeneous case. Other parameters are the same for both of the classes and are shown in Table1.When the proposed schemes are applied to the heterogeneous network, substantial change in the network performance is achieved. Figure9 shows the throughput of the heterogeneous network with the conventional scheme and the proposed scheme. Throughput for the NOCS-OS scheme is evaluated for different values of OS. Throughput improvement of 51%, 60%, 67%, and 74% is achieved for the offset of CW, 4CW, 8CW, and 16CW, respectively, for n=70. Since more slots are now available for back-off, this results in the improved system performance. The fairness index is also evaluated for the heterogeneous network using the conventional and the NOCS-OS schemes. Fairness is improved by 35%, 36%, 37.2%, and 37.4% for offset values of CW, 4CW, 8CW, and 16CW for n=70 as shown in Figure 10.Figure 9
Throughput for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.Figure 10
Fairness index for conventional and NOCS-OS scheme as a function of number of stations for heterogeneous network.


## 5.2.2. Mixed Traffic

In this subsection, the performance of the NOCS-OS scheme is evaluated for a mixed traffic environment. The network is grouped into two subgroups. Each subgroup is carrying different data types. Queues of group one stations are saturated, while bursty traffic is applied to group two stations, which is Poisson distributed [17]. There are 15 numbers of stations in each subgroup and simulation is performed on 30 numbers of stations. Figure 11 shows the normalized per station throughput as a function of the load on group two stations. Difference in the outcomes can be observed when the simulation is performed using the NOCS-OS scheme with OS value is equal to CW. For higher offset values network, performance would be better. Overall network throughput is shown in Figure 12 for n=10 and n=30 as function of load on group two stations. Performance improvement in proposed scheme is 4% for n=10 and is 12.3% for n=30.Figure 11
Normalized per station throughput for conventional and NOCS-OS scheme as a function of load of group two stations.Figure 12
Normalized throughput for conventional and NOCS-OS scheme as a function of load of group two stations.


## 5.2.3. Higher Data Rates

Higher data rate is the requirement of most of the present applications. It is well known that as the data increases throughput decreases. The drop in the throughput results from the fixed overhead in the preamble and in the interframe space [18]. Performance of the NOCS-OS scheme has been shown in Figure 13 for different data rates with offset is equal to CW. It is also compared with the conventional scheme. It is observed that for a wide range of data rates the proposed scheme performs better, but the performance improvement reduces over the conventional scheme as data rate increases. Outcomes are computed for mixed traffic with group one stations in saturation, while group two stations follow the Poisson traffic with 0.4 arrival rate. All other parameters are set according to 802.11 a/g standard.Figure 13
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes (bold lines for conventional and dashed lines for proposed scheme).


## 5.2.4. Advanced Back-Off Management Techniques

The most important features of the high-speed WLANs are frame aggregation and block acknowledgment for the enhancement of the MAC throughput. In this subsection, the performance of the proposed scheme and the conventional schemes are compared by incorporating these two features of the high-speed WLANs. Figure14 shows the comparison of the conventional and the NOCS-OS scheme for two formats of block acknowledgments with frame aggregation. One format uses 128-byte uncompressed block acknowledgment and the other one uses 8-byte compressed block acknowledgment [16]. The offset value is set to CW, traffic is considered bursty with average burst size set to ten. Arrival rate is kept as 0.5 packets per slot time and data rate is considered as 54 Mbps. Acknowledgment frames are transmitted at the rate of 6 Mbps. It is observed that the performance of the NOCS-OS scheme is little better as compared to that of conventional scheme.Figure 14
Normalized throughput for conventional and NOCS-OS scheme as a function of packet length in bytes for advanced back-off management technique.


## 6. Conclusion

The collision resolution schemes NOCS and NOCS-OS are proposed in this paper for IEEE 802.11. In these schemes, the back-off counter values of two different stages are nonoverlapping. Moreover in NOCS-OS, window ranges of two consecutive stages are discontinuous and separated by an offset value. Probability of selection of same back-off counter value is minimized due to nonoverlapping contention slots, which results in lesser collision probability and improved performance. The system model is formulated for proposed schemes in terms of attempt rate and collision probability. The throughput performance of the NOCS-OS scheme is investigated for different offset values. These schemes can be easily incorporated with little modifications in IEEE 802.11 standard. Since heterogeneous conditions result in unfairness among stations and degradation in network performance in terms of throughput and fairness. Significant improvement in the performance is observed with the proposed schemes than conventional scheme. Performance of the proposed scheme is also evaluated in mixed traffic conditions and high data rate applications with 802.11 a/g specifications. It has been shown that up to 100 Mbps the NOCS-OS scheme performs better as compared to the conventional approach. Throughput is also evaluated using frame aggregation and block acknowledgment features of high-speed WLANs. For offset ofCW, proposed approach offers little improvement as compared to the conventional approach using advanced back-off management techniques.



---

*Source: 852959-2013-04-28.xml*