Sage Journals: Discover world-class research

Abstract

This paper presents an analytical model for the performance evaluation of an IEEE 802.11e network in non-saturation environments. We first characterize the probability distribution of the MAC layer packet service time. Based on the probability distribution model of the MAC layer packet service time, we then study the queuing performance of the wireless local area networks (WLANs) at different traffic loads based on the IEEE 802.11e MAC protocol. The numerical results show that we can choose a feasible number and bandwidth of the node which determines the system performance that a user demands.

Keywords

IEEE 802.11e queuing analysis service time WLAN

1. Introduction

The widespread implementation of IEEE 802.11 as the standard for wireless local area networks (WLANs) has given reliability to the notion that WLANs may soon spread over a large number of multiservice communication networks. The primary difficulty faced in the use of IEEE 802.11 in multiservice wireless networks is the lack of quality of service (QoS) functionality as required by real-time voice and video applications [1]. To resolve this problem, the IEEE 802.11 Working Group created Task Group E to design medium access control (MAC) layer QoS enhancements according to the IEEE 802.11 standard [2]. The primary focus of the IEEE 802.11e standard is the hybrid coordination function (HCF). The HCF provides an efficient mechanism for centrally coordinated medium access and it uses the enhanced distributed coordination function (EDCF) for the distributed coordination of medium access. EDCF provides service differentiation among the different traffic priorities. It is also backwards compatible with the legacy 802.11 distributed coordination function (DCF).

In this paper, we present a mathematical model for the queuing analysis of IEEE 802.11e in a non-saturation condition. Bianchi has proposed a Markov chain model for the binary exponential backoff procedure in order to analyze and compute the IEEE 802.11 DCF saturated throughput [3]. There have also been attempts to construct a mathematical model for the throughput performance of IEEE 802.11e [4, 5]. These papers do not present the queue analysis results. Our analysis is based on the analytical framework used in [4] to compute the throughput performance of IEEE 802.11e.

In order to consider the non-saturated scenario, more practical queuing models for IEEE 802.11 DCF are proposed. They incorporate practical packet arrival processes [6]. The operation of a personal area network, operating under the IEEE 802.15.4 in the non-saturated scenario, which is also analysed using the theory of discrete time Markov chains and M/G/1/K queues [7].

To our knowledge, no comprehensive study has been done on the queue dynamics of IEEE 802.11e WLANs. The delay analysis is limited to the derivation of the mean value while the higher moments and the probability distribution function of the delay are untouched. Most of the current papers focus on the performance analysis in saturated traffic scenarios, while a comprehensive performance study under non-saturated traffic situations remains open.

In this paper, to concentrate on the above issues, first characterizing the probability distribution of the MAC layer packet service time. Based on the probability distribution model of the MAC layer packet service time, we then study the queuing performance of WLANs at different traffic loads based on the IEEE 802.11e MAC protocol.

The outline of this paper is as follows. The non-saturation Markov chain model is shown in Section 2. The analytical model for the packet service time is developed in Section 3 and the queue analysis of the model is presented in Section 4. Analytical results are presented in Section 5. Conclusions are given in Section 6.

2. Non-Saturation Analysis Model for EDCF

A simple and accurate analytical model was presented in order to compute the throughput of a saturated IEEE 802.11e DCF network under ideal channel conditions [4]. The model relies on two discrete time processes in order to model the progress of a given station through backoff. One process $b (t)$ represents the backoff counter of the station. Whenever $b (t)$ reaches zero, the station transmits and, regardless of the result of the transmission, begins a new backoff. Thus, it draws a new value for $b (t)$ . Otherwise, $b (t)$ is decremented at the start of every idle backoff slot. It monitors only the backoff slots. It is suspended for the duration of all transmissions and interframe spaces (i.e., SIFS and DIFS). Since the value of $b (t)$ after transmission depends on the size of the contention window from which it is drawn, $b (t)$ depends on the station's transmission history, and so it is non-Markovian. To overcome this, we set another process, $s (t)$ , called stage. It is defined to track the size of the contention window $(W_{i}, i = s (t))$ from which it is drawn. After every successful transmission $s (t)$ is reset to zero, and for every collision it is incremented up to a maximum of m corresponding with the stage at which the size of the contention window equals aCWmax. We assume the following two conditions for this model. First, the probability τ that a station will attempt transmission in a timeslot is constant across all timeslots. Second, the probability $P_{c}$ that any transmission experiences a collision is constant and independent of the number of collisions that it has already suffered. Using these assumptions, a multi-dimensional Markov process ${s (t), b (t)}$ is formed, whose stationary distribution $b_{i, k} = \lim_{i \to \infty} P {s (t) = i, b (t) = j}, i \in [0, m], j \in [0, W_{i} - 1]$ is expressed in terms of $P_{c}$ and the constant system parameters. Note that τ is given by, $\sum_{i = 0}^{m} b_{i, 0}$ and

P_{c} = 1 - {(1 - τ)}^{n - 1}

where n is the number of nodes with packets to transmit. In order to accommodate the QoS features provided by EDCF, we assume that each queue in the system is modelled by a Markov process that is specific to the AC associated with the queue. In the non-saturation regime, we assume that each network node accepts new packets via a finite buffer of size K. When the buffer is empty, the device will not attempt to do any transmission but when the buffer is full, the device will reject new packets coming from the upper layers of the protocol stack. The time required to transmit a packet from the head of the queue includes the time from the moment when the EDCF algorithm has started (i.e., from the start of the backoff counter procedure) to the moment when the receipt of the packet has been acknowledged by the receiving device. We will denote the packet service time with a Probability Generating Function (PGF) as $B (z)$ . Clearly, the packet queue of AC in the device buffer should be modelled as an M/G/1/K queuing system. An important characteristic of such a system is that the probability $π_{0}$ that the queue is empty immediately after the packet departure is not equal to the probability $P_{0}$ that the queue is empty at an arbitrary time. However, both probabilities are needed in the Markov chain model of the transmission system. They are shown in Fig. 1.

Figure 1.

Markov chain model of EDCF in a non-saturation regime with a finite buffer

In the figure, ${0, s (t), b (t)}$ forms a multi-dimensional Markov process. The corresponding state space is denoted as follows:

Ω = {(0), (i, j) | 0 \leq i \leq m, 0 \leq j \leq W_{j} - 1, j = 0, \dots, m}

We assume that the values of $P_{c}$ , $π_{0}$ and $P_{0}$ are known and we define the range of possible backoff stage values for a stage i as within $[0, W_{i} - 1]$ . As such, the one-step transition probabilities of the Markov process are given by:

\begin{array}{l} P {0 | i, 0} = {\begin{cases} (1 - P_{c}) π_{0}, i \in [0, m - 1] \\ π_{0}, i = m \end{cases} \\ P {0 | 0} = P_{0} \\ P {0, j | 0} = (1 - P_{0}) / W_{0}, j \in [0, W_{0} - 1] \\ P {i, j | i, j + 1} = 1, i \in [0, m], j \in [0, W_{i} - 1] \\ P {i, j | i - 1, 0} = P_{c} / W_{i}, i \in [1, m], j \in [0, W_{i} - 1] \\ P {0, j | i, 0} = {\begin{cases} (1 - P_{c}) (1 - π_{0}) / W_{0}, \\ i \in [0, m - 1], j \in [0, W_{i} - 1] \\ (1 - π_{0}) / W_{0}, i = m, j \in [0, W_{i} - 1] \end{cases} \end{array}

(1)

By ordering the elements of Ω lexicographically, we obtain the following transition probability matrix:

P = (\begin{matrix} \begin{matrix} D \\ A_{0} \\ A_{1} \end{matrix} & \begin{matrix} 0 \\ B_{0} \\ C_{1} \end{matrix} & \begin{matrix} \dots \\ 0 \\ B_{1} \end{matrix} & \begin{matrix} \begin{matrix} \dots & \dots & 0 \end{matrix} \\ \begin{matrix} \dots & \dots & 0 \end{matrix} \\ \begin{matrix} 0 & \dots & ⋮ \end{matrix} \end{matrix} \\ ⋮ & ⋮ & ⋱ & \begin{matrix} ⋱ & ⋱ & 0 \end{matrix} \\ A_{m - 1} & 0 & \dots & \begin{matrix} \dots & C_{m - 1} & B_{m - 1} \end{matrix} \\ E & 0 & \dots & \begin{matrix} \dots & \dots & C_{m} \end{matrix} \end{matrix})

where the submatrices $A_{i}, B_{i}, C_{i}, D$ and E are given by:

\begin{matrix} A_{i} = (\begin{matrix} \begin{matrix} (1 - P_{c}) π_{0} \\ \begin{matrix} 0 \\ ⋮ \end{matrix} \\ 0 \end{matrix} & \begin{matrix} \underset{W_{i}}{\underset{︸}{\begin{matrix} (1 - P_{c}) (1 - π_{0}) / W_{i} & \begin{matrix} \dots & \dots \end{matrix} & (1 - P_{c}) (1 - π_{0}) / W_{i} \end{matrix}}} \\ \begin{matrix} 1 & 0 & \dots & 0 \end{matrix} \\ \begin{matrix} \begin{matrix} ⋱ \\ \dots \end{matrix} & \begin{matrix} ⋱ \\ 0 \end{matrix} & \begin{matrix} ⋱ \\ 1 \end{matrix} & \begin{matrix} ⋮ \\ 0 \end{matrix} \end{matrix} \end{matrix} \end{matrix}) \\ B_{i} = (\begin{matrix} \underset{W_{i + 1}}{\underset{︸}{\begin{matrix} P_{c} / W_{i + 1} & \dots & \dots & P_{c} / W_{i + 1} \end{matrix}}} \\ \begin{matrix} 0 & \dots & \dots & 0 \end{matrix} \\ \begin{matrix} ⋮ & \dots & \dots & ⋮ \end{matrix} \\ \begin{matrix} 0 & \dots & \dots & 0 \end{matrix} \end{matrix}) \end{matrix}

\begin{matrix} C_{i} = (\overset{W_{i}}{\overset{⏞}{\begin{matrix} 0 & \dots & \dots & \dots & 0 \\ 1 & 0 & \dots & \dots & 0 \\ 0 & ⋱ & ⋱ & \dots & 0 \\ ⋮ & ⋱ & ⋱ & ⋱ & ⋮ \\ 0 & \dots & 0 & 1 & 0 \end{matrix}}}) \\ D = (\begin{matrix} P_{0} & \underset{W_{0}}{\underset{︸}{\begin{matrix} (1 - P_{0}) / W_{0} & \dots & (1 - P_{0}) / W_{0} \end{matrix}}} \end{matrix}) \end{matrix}

and:

E = (\begin{matrix} \begin{matrix} π_{0} \\ \begin{matrix} 0 \\ ⋮ \end{matrix} \\ 0 \end{matrix} & \begin{matrix} \underset{W_{0}}{\underset{︸}{\begin{matrix} (1 - π_{0}) / W_{0} & \begin{matrix} \dots & \dots \end{matrix} & (1 - π_{0}) / W_{0} \end{matrix}}} \\ \begin{matrix} 1 & 0 & \dots & 0 \end{matrix} \\ \begin{matrix} \begin{matrix} ⋱ \\ \dots \end{matrix} & \begin{matrix} ⋱ \\ 0 \end{matrix} & \begin{matrix} ⋱ \\ 1 \end{matrix} & \begin{matrix} ⋮ \\ 0 \end{matrix} \end{matrix} \end{matrix} \end{matrix})

Note that all the states in Ω are a positive recurrence and the system is stable. Therefore, the steady state probability vector $b$ that satisfies $b P = b$ and $b e = 1$ exists, where, $e$ is the $1 x (1 + \sum_{i = 0}^{m} W_{i})$ column vector whose components consist of 1. The vector $b$ is denoted by:

b = (b_{0}, b_{0, 0}, \dots b_{0, W_{0} - 1}, \dots, b_{m, 0}, \dots, b_{m, W_{m} - 1})

By solving the equation $b P = b$ , we have the following equations:

\begin{matrix} b_{0} P_{0} + (1 - P_{c}) π_{0} \sum_{i = 0}^{m - 1} b_{i, 0} + b_{m, 0} π_{0} = b_{0} \\ \frac{b_{0} (1 - P_{0})}{W_{0}} + \frac{(1 - P_{c}) (1 - π_{0})}{W_{0}} \sum_{i = 1}^{m - 1} b_{i, 0} + \sum_{i = 0}^{m} b_{i, j} + \frac{(1 - π_{0})}{W_{0}} b_{m, 0} \\ = b_{0, j - 1}, j = 0, \dots, W_{0} - 2 \\ \frac{b_{0} (1 - P_{0})}{W_{0}} + \frac{(1 - P_{c}) (1 - π_{0})}{W_{0}} \sum_{i = 1}^{m - 1} b_{i, 0} + \frac{(1 - π_{0})}{W_{0}} b_{m, 0} = b_{0, W_{0} - 1} \\ b_{i - 1, 0} \frac{P_{c}}{W_{i}} + b_{i, j} = b_{i, j - 1}, i = 1, \dots, m, j = 0, \dots, W_{i} - 1 \end{matrix}

(2)

By Eq. (2), $\sum_{j = 0}^{m - 1} b_{j, 0} = (1 - P_{c}^{m}) / (1 - P_{c})$ and $b_{0} = π_{0} b_{0, 0} / (1 - P_{0})$ , we obtain the stationary probabilities as follows:

b_{i, k} = \frac{W_{i} - k}{W_{i}} {\begin{cases} (1 - p_{c}) (1 - π_{0}) \sum_{j = 0}^{m - 1} b_{j, 0} + (1 - π_{0}) b_{m, 0} \\ + (1 - P_{0}) b_{0}, i = 0 \\ p_{c} b_{i - 1, 0}, i \in (0, m] \end{cases}

(3)

b_{i, k} = \frac{W_{i} - k}{W_{i}} P_{c}^{i} b_{0, 0}, i \in [0, m]

(4)

Since, $b e = 1$ and Eqs. (3-4), we calculate $b_{0, 0}$ as follows:

\begin{array}{l} b_{0, 0} = {2 (1 - 2 P_{c}) (1 - P_{c}) (1 - P_{0})} / \\ {(1 - 2 P_{c}) (1 - P_{c}) 2 π_{0} + W (1 - {(2 P_{c})}^{m + 1}) (1 - P_{c}) \\ + (1 - 2 P_{c}) (1 - {(P_{c})}^{m + 1})} \end{array}

(5)

Therefore, by substituting Eq. (5) into Eq. (4) we obtain $b_{i, k}$ as follows:

\begin{array}{l} b_{i, k} = \frac{W_{i} - k}{W_{i}} P_{c}^{i} {2 (1 - 2 P_{c}) (1 - P_{c}) (1 - P_{0})} / \\ {(1 - 2 P_{c}) (1 - P_{c}) 2 π_{0} + W (1 - {(2 P_{c})}^{m + 1}) (1 - P_{c}) \\ + (1 - 2 P_{c}) (1 - {(P_{c})}^{m + 1})} \end{array}

3. Probability Distribution of the MAC Layer Service Time

There are three basic processes when the MAC layer transmits a packet: the decrement process of the backoff timer, the successful packet transmission process that takes a time period of $T_{s u s}$ , and the packet collision process that takes a time period of $T_{c o l}$ . $T_{s u s}$ and $T_{c o l}$ are non-negative random variables and they represent the period when the medium is sensed as being busy due to a successful transmission and the period when the medium is sensed as being busy by each station due to collisions, respectively.

The MAC layer service time is the time interval from the time instant when a packet becomes the head of the queue and starts to contend for transmission to the time instant where either the packet is acknowledged for a successful transmission or else it is dropped.

This time is important for when we examine the performance of higher protocol layers. Apparently, the MAC layer service time is a discrete random variable as the time unit used in transmission is a time slot. Even though $T_{s u s}$ and $T_{c o l}$ depend on the transmission rate, the length of the packet and the overhead (with a discrete unit, i.e. a bit), and the specific transmission scheme (the basic access DATA/ACK scheme or the RTS/CTS scheme), we assume that the variables take discrete values as the unit of a time slot.

Let the non-negative random variable $T_{S}$ be the MAC layer service time. To derive the probability generating function (PGF) of $T_{S}$ , we will model the transmission process of each packet as a Markov chain. We first discuss how to derive the PGF of $T_{S}$ from the generalized state transition of the Markov chain.

The packet that leaves the mobile station through either being successfully transmitted or dropped goes to the absorption state of the Markov chain for the backoff mechanism. To obtain the average transition time to the absorption state of the Markov chain, we can use the matrix geometric approach. However, in the case of a Markov chain for $T_{S}$ with various transition times on different branches, it requires a new matrix formulation. This is to accommodate the different transition times. Its solution always accompanies extraneous complicated computations. Here, we apply the generalized state transition diagram shown in Fig. 2. From this, we can easily derive the PGF of $T_{S}$ and obtain an arbitrary nth moment of $T_{S}$ .

We first study the RTS/CTS mechanisms. The period of the successful transmission $T_{s u s}$ is equal to:

T_{s u s} = RTS + CTS + DATA + ACK + 3SIFS + AIFS[AC]

(6)

While the period of collision $T_{c o l}$ is equal to:

\begin{array}{l} T_{c o l} = RTS + SIFS + ACK + AIFS[AC] \\ = RTS + EIFS \end{array}

(7)

$T_{c o l}$ is a fixed value and its PGF $C_{t} (z)$ , which is equal to:

Figure 2.

Generalized state transition diagram for the transmission process

C_{t} (Z) = Z^{R T S + E I F S}

(8)

$T_{s u s}$ is a random variable determined by the distribution of the packet length. In case the length of DATA has a uniform distribution in $[l_{\max}, l_{\min}]$ , its PGF $S_{t} (Z)$ is equal to:

S_{t} (Z) = Z^{R T S + C T S + A C K + 3 S I F S + A I F S [A C]} \times \frac{1}{l_{\max} - l_{\min}} \sum_{i = l_{\min}}^{l_{\max}} Z^{i}

(9)

In case the length of DATA is a fixed value $l_{D}$ , its PGF $S_{t} (Z)$ is equal to:

S_{t} (Z) = Z^{R T S + C T S + l_{D} + A C K + 3 S I F S + A I F S [A C]}

(10)

If the basic scheme is adopted, then $T_{c o l}$ is determined by the longest from among the collided packets. When the probability that three or more packets simultaneously collide is neglected, its probability distribution can be approximated by the following equation:

\Pr {T_{c o l} = i} = \Pr {l_{1} = i, l_{2} \leq i} + \Pr {l_{2} = i, l_{1} \leq i} - \Pr {l_{1} = i, l_{2} = i}

(11)

where $l_{i} (i = 1, 2)$ is the packet length of the i th collided packet. Thus, we can obtain:

C_{t} (Z) \approx Z^{E I F S} \frac{1}{{(l_{\max} - l_{\min} + 1)}^{2}} \times \sum_{i = l_{\min}}^{l_{\max}} (2 i - 2 l_{\min} + 1) Z^{i}

(12)

S_{t} (Z) = Z^{S I F S + A C K + A I F S [A C]} \frac{1}{l_{\max} - l_{\min} + 1} \sum_{i = l_{\min}}^{l_{\max}} Z^{i}

(13)

In the backoff process, if the medium is idle, the backoff timer will decrease by one for every idle slot detected. When detecting an ongoing successful transmission, the backoff timer will be suspended and it will be deferred for a time period of $T_{s u s}$ . while if there are collisions among the stations, the deferring time will be $T_{c o l}$ . $P_{c}$ is the probability that a collision is seen by a packet which is being transmitted on the medium. Assuming that there are n stations in the WLAN and packet arrival processes at all the stations which are independent and identically distributed, we observe that $P_{c}$ is also the probability that there is at least one packet transmission in the medium among the other $(n - 1)$ stations in the interference range of the station under consideration. This yields:

P_{c} = 1 - {[1 - (1 - P_{0}) τ]}^{n - 1}

(14)

where $P_{0}$ is the probability that there are no packets ready to transmit at the MAC layer in the wireless station under consideration, and τ is the packet transmission probability that the station transmits in a randomly chosen slot time given that the station has packets to transmit. Let $P_{s u c}$ be the probability that there is one successful transmission among the other $(n - 1)$ stations in the considered slot time, given that the current station does not transmit. Then:

\begin{array}{l} P_{S U C} = (\begin{matrix} n - 1 \\ 1 \end{matrix}) (1 - P_{0}) τ {1 - (1 - P_{0}) τ}^{n - 2} \\ = (n - 1) {1 - {(1 - P_{c})}^{n - 1}} {(1 - P_{c})}^{\frac{n - 2}{n - 1}} \end{array}

(15)

$P_{c} - P_{S U C}$ is the probability that there are collisions among the other $(n - 1)$ stations (or neighbours). Thus, the backoff timer has a probability of $1 - P_{c}$ to decrement by 1 after an empty slot time, the probability $P_{S U C}$ to stay at the original state after $T_{s u s}$ , and the probability of $P_{c} - P_{S U C}$ to stay at the original state after $T_{c o l}$ . Accordingly, the decrement process of a backoff timer is a Markov process, as described in Fig. 1. As we defined $T_{S}$ before, the random variable $T_{S}$ is the duration of time taken for a state transition from the start state (beginning to be served) to the end state (being transmitted successfully or discarded after a maximum of α retransmission failures).

Let $B O_{j}^{i}$ and $B O_{}^{i}$ be the time until the backoff counter is decremented j times at stage i and the total time until all the backoff counters are decremented at stage i, respectively. Then, we have PGFs of $B O_{j}^{i}$ , as follows:

E (Z^{B O_{1}^{i}}) = \frac{(1 - P_{c}) Z^{σ}}{[1 - P_{S U C} S_{t} (Z) - (P_{C} - P_{S U C}) C_{t} (Z)]}, i \in [0, m]

(16)

From the above formula, we observe that $E (Z^{B O_{1}^{i}})$ is a function of $P_{c}$ , the number of stations n and the dummy variable Z. In addition, for $j = 2, \dots, W_{i} - 1$ :

E (Z^{B O_{j}^{i}}) = {\begin{matrix} \frac{1}{2^{i} W} \sum_{j = 0}^{2^{i} W - 1} {(E (Z^{B O_{1}^{i}}))}^{j}, i \in [0, m] \\ \frac{1}{2^{m} W} \sum_{j = 0}^{2^{m} W - 1} {(E (Z^{B O_{1}^{m}}))}^{j}, i \in [m + 1, α] \end{matrix}

(17)

Therefore, the PGF of $B O_{}^{i}$ is given by:

E (B O^{i}) = \begin{matrix} \prod_{k = 0}^{i} E (Z^{B O_{j}^{k}}), & (0 \leq i \leq α) \end{matrix}

(18)

For notational simplicity, we use the following notations:

\begin{array}{l} H_{d} (Z) = E (Z^{B O_{1}^{i}}), H W_{i} (Z) = E (Z^{B O_{j}^{i}}), \\ and H_{i} (Z) = E (B O^{i}) \end{array}

By using the Eqs. (16)-(18), we obtain the PGF of $T_{S}$ , as follows:

\begin{array}{l} E (Z^{T_{S}}) = B (Z) = (1 - P_{C}) S_{t} (Z) \sum_{i = 0}^{α} {(P_{C} C_{t} (Z))}^{i} H_{i} (Z) \\ + {(P_{C} C_{t} (Z))}^{α + 1} H_{α} (Z) \end{array}

(19)

Since the expectation of $T_{S}$ is calculated as: $E [T_{S}] = {\frac{d B (Z)}{d Z} |}_{Z = 1}$ , we have the MAC layer service rate μ as $1 / E [T_{S}]$ .

4. Queuing Modelling and Analysis

Many applications are sensitive to end-to-end delay and queue characteristics such as average queue length, waiting time, queue blocking probability, and service time. So, to obtain such performance metrics, it is necessary to investigate the queuing modelling and analysis for WLANs. A queue model can be characterized by the arrival process and the service time distribution with a certain service discipline. We have characterized the MAC layer service time distribution in the previous section. In this paper, we assume that the packet arrivals at each mobile station follow the Poisson process. The packet transmission process at each station can be modelled as a general single server. The buffer size at each station is K. Thus, the queuing model for each station can be modelled as an M/G/1/K when the Poisson arrivals of the packets are assumed.

Let $X_{n}$ and X be the number of packets in the queue seen upon the nth departure and the number of packets in the queue in an arbitrary time, respectively. Then, they can have the values in $[0, K]$ and we may consider the transition probability for each state. Let the transition probabilities of $X_{n}$ be given by $p_{i j} = P (X_{n + 1} = j | X_{n} = i), i, j \in [0, K]$ .

As such, we note that $p_{i j} = \frac{{(λ T_{s})}^{j - i}}{(j - i)!} e^{- λ T_{s}}$ , where the random variable $T_{S}$ is a service time of a packet. For notational simplicity, we use $k_{n}$ as $k_{n}$ = P(n arrivals during service time $T_{S}$ ). In addition, we note that the expectation of n packets' arrival during a service time is calculated as follows:

E (n arrivals during a service time) = \sum_{i = 0}^{\infty} \frac{e^{- λ i} {(λ i)}^{n}}{n!} \Pr {T_{S} = i}

(20)

Then, we have the following transition probability of $X_{n}$ :

Ρ = {p_{i j}} = [\begin{matrix} k_{0} & k_{1} & k_{2} & \dots & k_{(K - 2)} & 1 - \sum_{n = 0}^{K - 2} k_{n} \\ k_{0} & k_{1} & k_{2} & \dots & k_{K - 2} & 1 - \sum_{n = 0}^{K - 2} k_{n} \\ 0 & k_{0} & k_{1} & \dots & k_{K - 3} & 1 - \sum_{n = 0}^{K - 3} k_{n} \\ ⋮ & ⋮ & ⋮ & ⋮ & ⋮ \\ 0 & 0 & 0 & \dots & k_{0} & 1 - k_{0} \end{matrix}]

(21)

Moreover, we notice that:

k_{0} = B (e^{- λ}), k_{n} = \frac{λ^{n}}{{(- 1)}^{n} n!} \frac{\partial^{n} B (e^{- λ})}{\partial λ^{n}}

(22)

where $B (e^{- λ})$ is obtained by replacing Z with $e^{- λ}$ in Eq. (22), i.e., the PGF of the MAC layer service time $T_{S}$ .

According to the balance equation:

π Ρ = π, \sum_{i = 0}^{K} π_{i} = 1

(23)

where $π = {π_{n}}$ and the normalization equation, we can compute the π. For a finite system size K with Poisson input, we have:

\begin{matrix} P_{0} = \frac{π_{0}}{π_{0} + ρ}, \begin{matrix} P_{n} = \frac{π_{n}}{π_{0} + ρ} & (0 \leq n \leq K - 1), \end{matrix} \\ P_{K} = 1 - \frac{1}{π_{0} + ρ} \end{matrix}

(24)

where ρ is the traffic intensity and $ρ = λ E [T_{s}]$ .

From the above derivation, we know that $P_{0}$ is a function of $P_{c}$ , n and λ. So, we can compute $P_{c}$ under different values of λ and n with the help of Eq. (24) using a recursive algorithm. Thus, we can obtain the distribution of MAC service time for different offered loads according to the results. Here, we assume that the packet arrival process at each station is independent and is identically distributed. Hence, we could obtain the aggregate performance of WLAN from the queuing analysis in this section.

Table 1.

DSSS system and access category parameters

Parameter	Value
Channel bit rate	2 Mbps
Average frame size	8000 bits
MAC header	224 bits
PHY header	192 bits
ACK	112+PHY header
RTS	160+PHY header
CTS	112+PHY header
Slot time	20 µsec
SIFS	10 µsec
DIFS	34 µsec
AIFS [3]	50 µsec
AIFS [1]	50 µsec
CWmin [3]	15
CWmin [1]	31
CWmin [3]	511
CWmin [1]	1023

Table 2.

Throughput comparisons between numerical and simulation results (unit: Mbps)

Average Bandwidth of Nodes(Mbps)	Numerical Results	Simulation
0.05	0.50	0.4760
0.15	1.50	1.4421
0.25	2.50	2.4565
0.35	3.50	3.3665
0.45	4.50	4.4135
0.55	5.50	5.6043
0.65	6.50	6.6640
0.75	7.50	7.6429
0.85	8.25	8.2163
0.95	8.25	8.0252
1.05	8.25	8.4388
1.15	8.25	7.9149
1.25	8.25	8.1826
1.35	8.25	8.3783
1.45	8.25	8.0493
1.55	8.25	8.2039
1.65	8.25	8.3046
1.75	8.25	8.0574
1.85	8.25	8.1299
1.95	8.25	7.9581

The average queue length, blocking probability and the average waiting time - including the MAC service time - are given by:

\begin{array}{l} L = \sum_{i = 0}^{K} i \times P_{i}, P_{B} = P_{K} = 1 - \frac{1}{π_{0} + ρ}, \\ W = \frac{L}{λ (1 - P_{B})} \end{array}

(25)

If we know the blocking probability $P_{B}$ , then the throughput S at each station can be computed easily by:

S = λ (1 - P_{K}) (1 - P_{c}^{α + 1})

(26)

where $P_{c}^{α + 1}$ is the packet discard probability due to transmission failures.

5. Numerical results

In this section, we present the performance of the analysis and then we compare the analytical and simulation results to verify the accuracy of the proposed numerical model. Simulations are performed with the Matlab simulator. The parameters used in the numerical analysis and the simulations are listed in Table 1. In the analytical and simulation results, we use a three dimensional view of the performance metric for a varying number of nodes and the average bandwidth of nodes, respectively, in order to check the impact of the total incoming traffic load. Moreover, there exist AC3 and AC1 traffics in the experiment to show the effect of the service differentiation of EDCF. First of all, in order to verify the accuracy of the proposed model, the comparison of throughputs with a varying average bandwidth of nodes (the number of the nodes is fixed to 20) is presented in Table 2. As shown in the table, the results of simulation are almost the same as those of the numerical analysis. All of the simulation results in the table are obtained with a 97.85 % confidential rate (CR), which is calculated by the following:

C R_{U} = (1 - | \frac{E [U_{anal} - U_{sim}]}{E [U_{anal}]} |) \times 100 % .

(27)

where U denotes the throughput. Since the differences between the analytical and simulation results are negligible, in the remaining figures we present the results of the numerical analysis only.

Figure 3.

Throughput

Fig. 3 shows the three dimensional view of the throughput for a varying number of nodes and the average bandwidth of the nodes. As mentioned earlier, the variations in the number of nodes and the average bandwidth of them reflect the traffic load injected into the network. With these two metrics, we can obtain the normalized offered load as follows:

L = \frac{n \times P \times λ}{D}

(28)

where n, P, λ and D denote the number of nodes, packet length, packet arrival rate and channel bit rate, respectively. In Fig. 3, it can be observed that the status of the network is divided into three parts, which are the non-saturated, semi-saturated and saturated conditions. In the first part (L < 0.72) of the two figures - viz. Figs. 3 (a) and 3 (b) - as the traffic load increases, the throughputs linearly increase. In the non-saturated condition, the network can sufficiently accommodate the increasing data traffic. On the contrary, in the second part (0.72 < L < 0.96), which is the semi-saturated condition, the throughput of AC3 still increases linearly while that of AC1 decreases sharply. Then, when the network comes into the saturated condition (L > 0.96), the throughputs of both AC3 and AC1 remain constant regardless of the increase in the traffic load. It is clear that the saturated throughput of AC3 is larger than that of AC1.

Figure 4.

Delay

Fig. 4 shows the three dimensional view of the packet delay. When the semi-saturated condition starts, the delay of AC3 starts to increase linearly. However, in the case of AC1, the delay exponentially increases. Note that, under the saturated condition, AC1 exhibits a higher packet delay than is the case with AC3 (the average delays of AC3 and AC1 are 5 msec and 17 msec, respectively).

The variation of the collision probability is shown in Fig. 5. In the semi-saturated condition, the collision probabilities of the two node groups AC3 and AC1 increase sharply. When the network becomes saturated, they maintain constant values. Overall, the collision probabilities of AC3 are spread from 0 to 0.5 (Fig. 5 (a)), while the values of AC1 are spread from 0.1 to 0.6 (Fig. 5 (b)).

Comprehensively, the EDCF of IEEE 802.11e provides the prioritized QoS through the different access categories. Most of the performance metrics except for the throughput are rapidly deteriorated in the semi-saturated condition, rather than slowly, declining in the non-saturated status. In other words, the semi-saturated status acts as a performance boundary period between the non-saturated and saturated conditions.

Figure 5.

Collision probability

6. Acknowledgments

This research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Science and Technology (2011-0014740).

7. Conclusion

This paper presented an analytical model for the non-saturation performance analysis in an IEEE 802.11e network. The model accounts for both the AIFS/CW differentiation mechanisms and the buffer state. Moreover, it considers the use of both basic and RTS/CTS access mechanisms. Significantly, it contains a probability distribution of the MAC packet service time, which is needed for M/G/1/K systems with small contention windows or operating under very high loads. The numerical results also show that most of the performance metrics in the IEEE 802.11e network rapidly deteriorated in the semi-saturated condition, which is the performance boundary period between the non-saturated and saturated conditions, rather than declining slowly during the non-saturated status. From the proposed model, we can choose the feasible number and bandwidth of the node which determine the system performance that a user demands.

References

Hsu

Y-L.

Huang

Y-K.

Pang

A.-C.

, “QoS enhancement for co-existence of IEEE 802.11e and legacy IEEE 802.11,” in Proc. IEEE GLOBECOM, 2008, pp. 1–5.

IEEE WG 802.11, Part 11: Wireless LAN Medium Access Control (MAC) and Physical layer (PHY) specifications, Amendment 8: Medium Access Control (MAC) Quality of Service Enhancements, IEEE Standards 802.11e, 2005.

Bianchi

, “Performance analysis of the IEEE 802.11 distributed coordination function,” IEEE J. Sel. Areas Commun., vol. 18, no. 3, 2000, pp. 535–547.

Robinson

J.W.

Randhawa

T.S.

, “Saturation throughput analysis of IEEE 802.11e enhanced distributed coordination function, ” IEEE J. Sel. Areas Commun., vol. 22, no. 5, 2004, pp. 917–928.

Lee

J.Y.

Lee

H.S.

, “A performance analysis model for IEEE 802.11e EDCA under saturation condition, ” IEEE Trans. Commun., vol. 57, no. 1, 2009, pp. 56–63.

Zhai

Kwon

Fang

, “Performance analysis of IEEE 802.11 MAC protocols in wireless LANs, ” Wireless Communications & Mobile Computing, vol. 4, no. 8, 2004, pp. 917–931.

Misic

V.B.

Shafi

, “Performance of IEEE 802.15.4 beacon enabled PAN with uplink transmissions in non-saturation mode - access delay for finite buffers, ” in Proc. IEEE BROADNETS, 2004, pp. 416–425.