1 Introduction

The DCF is the generic protocol used in all IEEE 802.11 standards that employ Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA) method using binary exponential backoff algorithm. Readers can refer [1] for data transmission procedures under basic and RTS/CTS mechanisms used in DCF protocol. For supporting the real time applications, throughput and minimum End-to-End delay are the two main challenging issues in the design of IEEE 802.11 WLAN protocols. To evaluate and enhance the performance of IEEE 802.11 DCF protocol, several packet transmission procedures have been suggested in the literature and these are represented with Markov chain models. However, these models cannot accurately predict the performance of the network and they suffer with high packet collisions resulting in degradation of throughput and End-to-End delay, particularly under congested environments. Many researchers concentrated on the performance evaluation of DCF assuming ideal channel conditions. Bianchi was the first to derive a model that incorporates the exponential backoff process inherent in 802.11 as a two dimensional Markov chain to analyze the saturated throughput of 802.11 [2, 3]. To increase the accuracy of the results, busy medium conditions are considered in the model [4]. Here, the throughput is analyzed under saturated traffic conditions. Daneshgaran et al. [5] presented a Markov model to analyze the throughput considering transmission errors and capture effects over Rayleigh fading channels. Hung et al. [6] considered the effect of hidden nodes to evaluate the performance of IEEE 802.11 DCF. Malone et al. [7] extended the Bianchi’s model to evaluate the throughput in non-saturated conditions considering different traffic arrival rates. However, these models cannot evaluate the performance of DCF accurately. In our previous research, we have proposed an exact Markov chain model to accurately predict the performance of the DCF protocol [8]. To alleviate the collisions and avoid channel capture effect, a post backoff stage is introduced to provide inter packet backoff (IPB) delay between successive packet transmissions. The modified model is named as Collision Alleviating DCF (CAD) protocol and showed that the performance of the proposed model is better than the existing models.

Due to absence of infrastructure, a number of problems arise in Ad hoc networks, such as bandwidth constraints, security, mobility, hidden node and exposed node problems, reliability and routing mechanisms [9]. Packet loss occurs in Ad hoc networks due to frequent link failures because of the mobility of nodes. Due to sharing of wireless bandwidth among Ad hoc nodes, medium access control may rely on physical carrier sensing multiple access mechanism with collision avoidance to determine the idle channel, such as in the IEEE 802.11 DCF [10]. In wireless networks, the channel is non-uniformly shared which leads to hidden terminal problem in Ad hoc networks.

Since communication through Ad hoc networks plays a major role in emergencies, it is very important to design an efficient MAC protocol for wireless Ad hoc networks. To improve the performance of nodes in Ad hoc as well as in congested wireless networks, designing of a backoff algorithm is crucial. Several backoff algorithms have been proposed in the literature for IEEE 802.11 based networks. The Binary Exponential Backoff (BEB) algorithm is used in IEEE 802.11 Wireless Local Area Network (WLAN) standard. Algorithms such as Double Increment Double Decrement (DIDD) [11], Exponential Increase Exponential Decrease (EIED) [12], Hybrid backoff (HB) algorithm [13], Binary Negative Exponential Backoff (BNEB) algorithm [14], Contending Stations Backoff Algorithm (CSBA) [15], etc. have been proposed in the literature for the IEEE 802.11 DCF protocol to reduce the number of collisions and to improve system performance. A backoff algorithm was proposed in which the size of the contention window is adjusted according the number of stations [16]. Authors have proposed an Adaptive minimum Contention Window Binary Exponential Backoff (AWBEB) algorithm in which the size of contention window for the next packet depends on the backoff stage from which the previous packet was transmitted successfully [17]. The history of the past trials of transmission is considered in History Based Adaptive Backoff (HBAB) algorithm [18]. Size Based Adaptive (SBA) backoff algorithm has been developed to provide Quality-of-Service (QoS) requirements in mobile Ad hoc networks [19]. However, these algorithms (except BEB algorithm) have not been designed for finite load conditions.

In binary exponential backoff algorithm, the node increases its contention window (CW) exponentially when the current packet transmission is unsuccessful. So, the node has to sense the channel for a long time to transmit data. Any other node which senses the channel at the same time with a lower contention window size gets access to the channel. The other node may be in the coverage area of the current transmitting node or may be a hidden node. The node which is in the coverage area captures the channel and transmits data. As hidden nodes cannot sense the transmission of other nodes, they can start their transmissions with lower contention window size which leads to packet collisions. In this case, the actual node keeps on doubling its contention window size leading to wastage of time and energy. Due to the above-mentioned reasons, the throughput of the wireless network decreases and the average delay required for packet delivery increases. Hence, the current backoff algorithm is inefficient for congested wireless and Ad hoc networks. To solve these problems, a new Contention Window based Multiplicative Increase Decrease Backoff (CWMIDB) algorithm is proposed in this paper to reduce the number of collisions. The CAD protocol which is developed in our previous research is used to avoid channel capture effect [8]. So, the CAD protocol with CWMIDB algorithm is considered here to reduce the collisions and to enhance QoS parameters such as throughput and End-to-End delay in wireless networks under finite load conditions.

2 CWMIDB Algorithm

The purpose of using CWMIDB algorithm in IEEE 802.11 is to minimize collisions during contention between multiple nodes and also in the presence of hidden nodes. This is a very simple backoff algorithm in which the size of the contention window increases and decreases rather than increasing exponentially.

In CWMIDB algorithm, whenever a node wishes to transmit data, it senses for a carrier on the channel. If the channel is idle for a period of time equal to distributed interframe space (DIFS), the node transmits. If the frame is correctly received, the receiving node sends an acknowledgment (ACK) frame after another fixed Short interframe space (SIFS) period. If the channel is sensed busy for a period of DIFS, the node generates a random backoff interval before transmitting, to minimize the probability of collision with packets being transmitted by other nodes. Initially, the backoff time is uniformly chosen in the range (0, \({CW}_{min}-1\)) where \(CW_{min}\) is the minimum contention window size. The backoff time counter is decremented as long as the channel is sensed idle, “frozen” when a transmission is detected on the channel, and reactivated when the channel is sensed idle again. The node transmits when the backoff time reaches zero. If two nodes have the same backoff value at any given instant, they transmit at the same time and eventually, a collision occurs. When a node detects a failed transmission (it does not receive the ACK of a frame), it reschedules the backoff procedure.

2.1 Algorithm

  1. Step 1:

    Initialize Contention window CW to its minimum value \({CW}_{min}\) and the maximum value of CW to its maximum value \({CW}_{max}\) according to the specifications of the IEEE 802.11 standard.

  2. Step 2:

    Sense the channel for a period of DIFS. If the channel is idle, transmit the data frame and go to step 5. Otherwise go to step 3.

  3. Step 3:

    Set the backoff counter (BOC) between 0 and (\({CW}_{min}-1\)).

  4. Step 4:

    Decrement the BOC by 1 if the channel is idle. If BOC reaches zero, transmit the data frame.

  5. Step 5:

    If acknowledgment received, go to step 1 to transmit the next data frame. Else go to step 6.

  6. Step 6:

    If the acknowledgement is not received select the BOC between 0 and (\(W_{i}- 1\)) if \({CW} < {CW}_{max}\). Else \({CW} = {CW}_{max}\). Here \(W_i =2^{i/2}W\) for even values of \(i\) and \(W_i =4X2^{{\left( {i-1} \right) }/2}W\) for odd values of \(i\) where \(i\) is the retransmission attempt and \(W = {CW}_{min}\). Go to Step 4.

2.2 Markov Chain Model

The state transition diagram of the Markov chain model for the CAD protocol is shown in Fig. 1 [8]. In this model, to avoid channel capture and reduce contention among nodes, after successful transmission of a packet at any backoff stage, the node waits for a random backoff interval to access the channel again. Under saturated conditions, the node selects this interval between (0, \({CW}_{min}-1\)) at post backoff stage. In unsaturated conditions, where the packet arrival follows the Poisson’s process, the node waits in idle state (\(-\)1, 0) at post backoff stage until the next packet arrives in its queue. When the packet arrives at the node’s buffer and the channel is idle, from (\(-\)1, 0) state, it goes to state (0, 0) and transmits the packet. When the channel is busy, it selects the CW between 0 and (\({CW}_{min}-1\)). The selection of the contention window in the next stage depends on the backoff algorithm as explained in Sect. 2.1. The packet can be transmitted at any backoff stage when its backoff counter is zero.

Fig. 1
figure 1

State transition diagram of the Markov chain model for the CAD protocol

Full size image

Consider the number of contending nodes as fixed, defined as \(n\). Let \(b(t)\) and \(s(t)\) be the stochastic process representing the backoff counter and the backoff stage (0,.....m) respectively for a given node at slot time \(t\), where \(m\) is the maximum backoff stage. In order to consider the non-saturated traffic, we define \(q\) as the probability of having at least one packet in the node’s buffer to transmit. Similar to [3], the key approximation in the proposed model is that, at each transmission attempt, and regardless of the number of retransmissions suffered, each packet collides with constant and independent probability \(P_{col}\). Also, it is assumed that transmission errors due to imperfect channel can occur with probability \(P_{e}\) and the channel is busy with probability \(P_{b}\). The collision and transmission error probabilities are assumed to be statistically independent [15]. Here, the state of each node is described by \(\{i, k\}\), where \(i\) indicates the backoff stage (0,.....m) and \(k\) indicates the backoff delay. The backoff delay takes the values (0,1,....\(W_{i }-1\)) where \(W_{i} = 2^{i }{CW}_{min}\). \(W, W_{0}\) and \({CW}_{min}\) can be interchangeable. The contention window will be increased either due to packet collisions or due to transmission errors since a node cannot distinguish a packet collision from a transmission error. The probability of successful transmission is therefore equal to (\(1 - P_{e})(1 - P_{col})\), from which the equivalent probability of failed transmission \(P_{eq}\) can be expressed as \(P_{eq}=P_{e}+P_{col}-P_{e}P_{col}\). The state transition diagram of the Markov chain model shown in the Fig. 1 has the following transition probabilities [8]:

2.2.1 Backoff State Transitions

  1. (i)

    The backoff counter decrements when the node senses the channel to be idle.

    $$\begin{aligned} P\left\{ {(i,k)\;|\;(i,k+1)} \right\} =1-P_b \quad \quad k\in \left( {0,W_i -2} \right) , \quad i\in \left( {0,m} \right) \end{aligned}$$
    (1)
  2. (ii)

    The backoff counter freezes when the node senses that the channel is busy.

    $$\begin{aligned} P\left\{ {(i,k)\;|\;(i,k)} \right\} =P_b \quad \quad k\in \left( {1,W_i -1} \right) , \quad i\in \left( {0,m} \right) \end{aligned}$$
    (2)
  3. (iii)

    After each successful transmission, the node with a packet in queue goes to post-backoff stage.

    $$\begin{aligned} P\left\{ {(-1,k)\;|\;(i,0)} \right\} =\frac{\left( {1-P_{eq} } \right) q}{W_0 } \quad \quad k\in \left( {0,W_0 -1} \right) \end{aligned}$$
    (3)
  4. (iv)

    After an unsuccessful transmission at stage \(i \)-1, the node reschedules a backoff delay in the next stage.

    $$\begin{aligned} P\left\{ {(i,k)\;|\;(i-1,0)} \right\} =\frac{P_{eq} }{W_i } \quad \quad k\in \left( {0,W_i -1} \right) , \quad \quad i\in \left( {1,m} \right) \end{aligned}$$
    (4)
  5. (v)

    When the transmission is unsuccessful in all the stages, the node reaches the last stage of backoff procedure and remains in that stage until the packet transmission is successful.

    $$\begin{aligned} P\left\{ {(m,k)\;|\;(m,0)} \right\} =\frac{P_{eq} }{W_m } \quad \quad k\in \left( {0,W_m -1} \right) \end{aligned}$$
    (5)

2.2.2 Post-Backoff State Transitions

  1. (i)

    After each successful transmission, the node goes to idle state (\(-\)1, 0) when the queue is empty and waits in that state until the new packet arrives in the queue.

    $$\begin{aligned}&P\left\{ {(-1,0)\;|\;(i,0)} \right\} =\left( {1-P_{eq} } \right) \left( {1-q} \right) \quad i\in \left( {0,m} \right) \nonumber \\&P\left\{ {(-1,0)\;|\;(-1,0)} \right\} =1-q \end{aligned}$$
    (6)
  2. (ii)

    The node with a packet for transmission, goes to (0, 0) state when the channel is free and then transmits the packet.

    $$\begin{aligned} P\left\{ {(0,0)\;|\;(-1,0)} \right\} =q\left( {1-P_b } \right) \end{aligned}$$
    (7)
  3. (iii)

    The node with a packet for transmission, selects a backoff stage when the channel is busy.

    $$\begin{aligned} P\left\{ {(0,k)\;|\;(-1,0)} \right\} =\frac{qP_b }{W_0 } \quad \quad k\in \left( {0,W_0 -1} \right) \end{aligned}$$
    (8)
  4. (iv)

    In the post-backoff stage, the backoff counter decrements when the node senses the channel to be idle and freezes when the channel is busy.

    $$\begin{aligned} P\left\{ {(-1,k)\;|\;(-1,k+1)} \right\}&= (1-P_b ) \quad \quad k\in \left( {0,W_0 -2} \right) \nonumber \\ P\left\{ {(-1,k)\;|\;(-1,k)} \right\}&= P_b \quad \quad k\in \left( {1,W_0 -1} \right) \end{aligned}$$
    (9)

The probability that a node occupies a given state \(\{i, k\}\) at any discrete time slot is \(b_{i,k }= \lim _{t\rightarrow \infty } P\{s(t)=i, b(t)=k\}\) where \(i, k\) are integers and \(-1 \le i \le m, 0 \le k \le W_{i}\) – 1.

The following relations are valid in steady state:

$$\begin{aligned} b_{i,0} =P_{eq}^i b_{0,0} \quad \quad i\in \left( {1,m-1} \right) \end{aligned}$$
(10)

In the above Eq., \(P_{eq}\) is the equivalent probability of failed transmission.

When the packet transmission is unsuccessful at any backoff stage \(i-1\), the node reschedules a backoff delay in the next stage \(i\). The backoff counter freezes at \((i, k)\) state when the node senses that the channel is busy. So, the steady state probability of \((i, k)\) state \(b_{\mathrm{i},k}\) is given by the following Eq. (11).

$$\begin{aligned} b_{i,k} =\frac{P_{eq}^i }{1-P_b }\frac{W_i -k}{W_i }b_{0,0} \quad i\in \left( {1,m-1} \right) , \quad k\in \left( {1,W_i -1} \right) \end{aligned}$$
(11)

Based on the Eq. (10) and considering that the node keeps iterating in the \(m^{th}\) stage until the packet transmission is successful, the steady state probabilities of \((m, 0)\) and \((m-1,0)\) states \(b_{m,0}\) and \(b_{m-1,0}\) are given by

$$\begin{aligned} b_{m,0}&= \frac{P_{eq}^m }{1-P_{eq} }b_{0,0}\end{aligned}$$
(12)
$$\begin{aligned} b_{m-1,0}&= P_{eq}^{m-1} b_{0,0} \end{aligned}$$
(13)

Similarly, the steady state probability of \((m, k)\) state \(b_{m,k }\) is given by

$$\begin{aligned} b_{m,k} =\frac{W_m -k}{W_m }\frac{P_{eq}^m }{\left( {1-P_{eq} } \right) \left( {1-P_b } \right) }b_{0,0} \end{aligned}$$
(14)

In the above Markov chain model, after successful transmission at any backoff stage, the node directly enters the state (\(-\)1, 0) when there are no packets to be transmitted and keeps iterating in that state until the arrival of new packet. The stationary probability to be in state \(b_{-1,0}\) can be evaluated as

$$\begin{aligned} b_{-1,0} =\frac{1-q}{q}b_{0,0} \end{aligned}$$
(15)

After successful transmission at any backoff stage, when the node is ready to transmit the next packet, the node enters the state \((-1, k)\) to provide a backoff delay between these packets to avoid channel capture. So the stationary probability to be in state \(b_{-1,k}\) obtained is

$$\begin{aligned} b_{-1,k} =P_b b_{-1,k} +q\left( {1-P_{eq} } \right) \sum _{i=0}^m {b_{i,0} \frac{W_0 -k}{W_0 }} \end{aligned}$$
(16)

Where,

$$\begin{aligned} \sum _{i=0}^m {b_{i,0} =}\ \frac{1}{1-P_{eq} }b_{0,0} \end{aligned}$$
(17)

Now, substituting Eq. (17) in to the Eq. (16), \(b_{-1, k}\) becomes

$$\begin{aligned} b_{-1,k} =q\left( {\frac{W_0 -k}{W_0 }} \right) \frac{1}{1-P_b }b_{0,0} \quad k\in \left( {1,W_0 -1} \right) \end{aligned}$$
(18)

When the node has a packet for transmission at idle state and when the channel is busy, it selects backoff counter between 0 and \(W_{0}\). The stationary probability that the node to be in state \(b_{0, k}\) is

$$\begin{aligned} b_{0,k} =\frac{P_b \left( {1-q} \right) }{1-P_b }\frac{W_0 -k}{W_0 }b_{0,0} \quad k\in \left( {1,W_0 -1} \right) \end{aligned}$$
(19)

2.3 Derivation for Transmission Probability, \(\tau \)

After each unsuccessful packet transmission, when the backoff period increases linearly or exponentially such as in BEB algorithm, the packet delay increases. On the other hand, when the backoff period decreases for each unsuccessful transmission, such as in BNEB algorithm, throughput also decreases. An efficient backoff algorithm must enhance network throughput and reduce End-to-End delay. In order to satisfy these characteristics, the backoff procedure should be modified. In CWMIDB algorithm, when collision occurs at any backoff stage, the node selects its contention window size depending on the retransmission attempt, \(i\). For even values of \(i\), the size of the contention window \(W_{i}\) becomes \(2^{i/2}W\) and for odd values of \(i, W_{i}\) becomes \(4X2^{{\left( {i-1} \right) }/2}W\).

Let \(L\) be the variable and \(L = 0,1,2,3\) and so on.

$$\begin{aligned} \left\{ {\begin{array}{l} W_{2L} =2^{L}W \\ W_{2L+1} =4X2^{L}W \\ \end{array}} \right. \end{aligned}$$
(20)

In other words,

$$\begin{aligned}&\hbox {For} \;\;\hbox {even}\;\; \hbox {values}\;\; \hbox {of}\;\; i, W_{2L} =2^{L}W\; ; 1< L < (m-1)/2 \;\;\hbox {and}\\&\hbox {For}\;\; \hbox {odd}\;\; \hbox {values}\;\; \hbox {of}\;\; i, W_{2L+1} =4X2^{L}W\; ; 0 < L < (m-3)/2 \end{aligned}$$

Therefore, if \(i\) is even, \(W_{i} = 2^{L}W\). If \(i\) is odd, \(W_{i} = 4 X 2^{L}W\).

According to probability conservation relation, total probability is equal to one. Therefore,

$$\begin{aligned} \sum _{i=-1}^m {b_{i,0} +\sum _{i=-1}^m {\sum _{k=1}^{W_i -1} {b_{i,k} =1} } } \end{aligned}$$
(21)

The above Eq. can be expanded as

$$\begin{aligned} \left( {b_{-1,0} + \sum _0^m {b_{i,0} } } \right)&+ \left( {\sum _{k=1}^{W_0 -1} {b_{-1,k} } } \right) + \left( {\sum _{k=1}^{W_m -1} {b_{m,k} } } \right) + \left( {\sum _{i=1}^{m-1} {\sum _{k=1}^{W_i -1} {b_{i,k} } } } \right) \nonumber \\&+ \left( {\sum _{k=1}^{W_0 -1} {b_{0,k} } } \right) =1 \end{aligned}$$
(22)

The only difference between BEB and CWMIDB algorithms is in selection of contention window at each backoff stage and hence the value of \(b_{i, k}\) is different for even and odd values of \(i\) in CWMIDB algorithm. In the above Eq. (22), the derivation of all the terms except term 4 is the same for BEB and CWMIDB algorithms. Terms 1, 2, 3 and 5 can be expanded as in CAD protocol [8].

The term 4 must be derived separately for even and odd values of \(i\). For 1\(\le i \le m-1\), and even values of \(i\), the limits are 2 and \(m-1\) and for odd values of \(i\), the limits are 1 and \(m-2\).

Therefore,

$$\begin{aligned} \hbox {For} \;\; i&= \hbox {even}, 2L = 2.\, \hbox {Then}\;\; L = 1; \qquad 2L=m - 1; L = (m- 1) /2\\ \hbox {For}\;\; i&= \hbox {odd}, 2L+1 = 1.\, \hbox {Then}\;\; L = 0;\qquad 2L+1 = m - 2; L = (m-3)/2 \end{aligned}$$

Now, the term 4 can be written as

$$\begin{aligned} \sum _{i=1}^{m-1} {\sum _{k=1}^{W_i -1} {b_{i,k} } } =\sum _{k=1}^{W_i -1} {\sum _{L=1}^{\frac{m-1}{2}} {b_{2L,k} }} + \sum _{k=1}^{W_i -1} {\sum _{L=0}^{\frac{m-3}{2}} {b_{2L+1,k} } } \end{aligned}$$
(23)

Now, after simplification, the term 4 becomes

$$\begin{aligned} \sum _{i=1}^{m-1} {\sum _{k=1}^{W_i -1} {b_{i,k} } }&= \frac{b_{0,0} P_{eq}^2 }{2\left( {1-P_b } \right) }\left( {\frac{2W\left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) }{1-2P_{eq}^2 }-\frac{1-P_{eq}^{m-1} }{1-P_{eq}^2 }} \right) \nonumber \\&\quad +\, \frac{b_{0,0} P_{eq} }{2\left( {1-P_b } \right) }\left( {\frac{4W\left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) }{1-2P_{eq}^2 }-\frac{1-P_{eq}^{m-1} }{1-P_{eq}^2 }} \right) \end{aligned}$$
(24)

Now, substituting the equations for all the terms in to the Eq. (22), the Eq. for \(b_{0,0 }\)is as follows.

$$\begin{aligned} b_{0,0}&= \left\{ \frac{1-q}{q}+\frac{1}{1-P_{eq} }+q\left( {\frac{W-1}{2}} \right) \frac{1}{1-P_b }\nonumber \right. \\&\quad \left. +\left( {\frac{4X2^{\frac{m}{2}}W-1}{2}} \right) \frac{P_{eq} ^{m}}{\left( {1-P_{eq} } \right) \left( {1-P_b } \right) }+\frac{P_b \left( {1-q} \right) }{\left( {1-P_b } \right) }\frac{W-1}{2}+\alpha \right\} ^{-1} \end{aligned}$$
(25)

Where

$$\begin{aligned} \alpha&= \frac{P_{eq}^2 }{2\left( {1-P_b } \right) }\left( {\frac{2W\left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) }{1-2P_{eq}^2 }-\frac{1-P_{eq}^{m-1} }{1-P_{eq}^2 }} \right) \\&\quad +\,\frac{P_{eq} }{2\left( {1-P_b } \right) }\left( {\frac{4W\left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) }{1-2P_{eq}^2 }-\frac{1-P_{eq}^{m-1} }{1-P_{eq}^2 }} \right) \end{aligned}$$

The probability that a node transmits a packet in a randomly chosen slot time \(\tau \) can be expressed as

$$\begin{aligned} \tau =\sum _{i=0}^m {b_{i,0} =\frac{1}{1-P_{eq} }b_{0,0} } \end{aligned}$$
(26)

By substituting Eq. (25) in to Eq. (26), \(\tau \) becomes

$$\begin{aligned} \tau =\frac{2q\left( {1-P_b } \right) \left( {1-2P_{eq}^2 } \right) \left( {1-P_{eq}^2 } \right) }{{\begin{array}{l} 2\left( {1-P_b } \right) \left( {1-2P_{eq}^2 } \right) \left( {1-P_{eq}^2 } \right) \left[ {1-P_{eq} \left( {1-q} \right) } \right] +q\left( {W-1} \right) \left( {1-P_{eq} } \right) \\ \left( {1-P_{eq}^2 } \right) \left( {1-2P_{eq}^2 } \right) \left[ {q+P_b \left( {1-q} \right) } \right] +q\left[ {4X2^{\frac{m}{2}}W-1} \right] P_{eq} ^{m}\left( {1-2P_{eq}^2 } \right) \\ \left( {1-P_{eq}^2 } \right) +2P_{eq} Wq\left( {1-P_{eq} } \right) \left( {1-P_{eq}^2 } \right) \left[ P_{eq} \left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) \right. \\ \left. + 2\left( {1-\left( {\sqrt{2}P_{eq} } \right) ^{m-1}} \right) \right] -qP_{eq} \left( {1-P_{eq} } \right) \left( {1-2P_{eq}^2 } \right) \\ \left[ {P_{eq} \left( {1-P_{eq}^{m-1} } \right) +\left( {1-P_{eq}^{m-1} } \right) } \right] \\ \end{array}}} \end{aligned}$$
(27)

In Eq. (27), under saturated traffic conditions (\(q\rightarrow \)1) when \(m = 0\), i.e., when no exponential backoff is considered and assuming \(P_{b}=P_{eq} = 0\), the transmission probability \(\tau \) reduces to 2/(\(W\)+1). This is similar to the Eq. for the constant backoff window problem. The relation between \(\tau , P_{b}\) and \(P_{col}\) can be found in [8]. A unique solution can be obtained on solving the equations of \(\tau \) (27), \(P_{b}, P_{eq}\) and \(P_{col}\) using numerical methods. In the above equations, \(W, W_{0}\) and \({CW}_{min}\) are interchangeable.

3 Throughput Analysis

Throughput is defined as the average rate of successful data delivery over a communication channel. It is the ratio of the effective payload to the time required to transmit the payload successfully. Here, the effective payload is the size of the data within the frame or packet excluding the MAC and physical layer headers. The payload information including the MAC header is transmitted with the same data rate. The actual data rate depends on the modulation technique used. The PHY header and the control frames (RTS, CTS and ACK) are transmitted with lower transmission rates. In this section, the performance of IEEE 802.11 protocol using CWMIDB algorithm is analyzed in terms of throughput and this is done in three different situations. First, the saturation throughput analysis is done as a function of the number of nodes under ideal channel conditions. The analysis is then extended by considering the packet errors due to transmission through Rayleigh fading channel. Finally, the throughput analysis is carried out considering the non-saturated traffic conditions. The performance of the proposed CWMIDB algorithm is compared with the legacy DCF (BEB algorithm) and various existing backoff algorithms such as HB and DIDD. CWMIDB algorithm is also compared with the CAD protocol using BEB algorithm. Even though the algorithm is suited for any IEEE 802.11 family, performance analysis is done using the network parameters of IEEE 802.11b protocol since it is easier to compare with the existing models. The performance analysis can be applied to both the access mechanisms (basic and RTS/CTS). In the analysis of throughput, the minimum value of the contention window \({CW}_{min}\) plays a key role. This value depends on the protocol. The values of \({CW}_{min}\) for IEEE 802.11b and IEEE 802.11a are 32 and 15 respectively.

3.1 Effect of Packet Collisions and Channel Errors on Packet Transmission

When the channel is erroneous, multipath fading occurs and hence the SNR (Signal-to-Noise Ratio) decreases, which causes packet errors. Therefore, factors that affect the error performance of wireless channels are to be considered when designing wireless network protocols. The error performance of wireless channels is usually modeled by capturing the statistical nature of the interaction among reflected radio waves. Statistical calculation for Bit Error Rate (BER), which is generally used to characterize channel errors at the physical layer, is a well-known practice. The BER for a communication channel is defined as the probability of a single bit being corrupted in a defined number of transmitted bits [20]. For example, a BER of \(10^{-3}\) means that, 1 bit in every 1,000 bits would be corrupted on an average.

In this paper, it is assumed that degradation in network performance can be either due to packet collisions or transmission errors. In other words, packet transmission is unsuccessful when more than one node transmits the packets simultaneously, in which case, they collide with each other or the transmitted packets may be corrupted at the receiver. This assumption is due to the fact that a node cannot distinguish a packet collision from transmission errors. In both the cases, the transmitting node will not be able to receive an acknowledgement, and then it reschedules its backoff mechanism until the packet is transmitted successfully. The packet/frame error rate depends on the BER, the packet payload and the length of physical and MAC layer headers. In turn, the BER depends on the SNR, the modulation technique used and the coding scheme. The equations of frame error probability have been presented in [8] and [22].

3.2 Effect of Packet Arrival Rate on the Performance of the Network

Similar to [5], it is assumed that the packet arrival process at each node is Poisson distributed and \(\lambda \) is the rate at which the packets arrive at the node’s buffer from the upper layers. Then the probability \(q\) that the queue contains at least one packet available at the end of a slot can be expressed as Eq. (28).

$$\begin{aligned} q=1-e^{-\lambda E[S_t ]} \end{aligned}$$
(28)

In the above Eq., the average length of slot time \(E[S_{t}]\) when the channel errors are considered is given as

$$\begin{aligned} E[S_t ]=P_{tr} P_s \left( {1-P_e } \right) T_{success} +P_{tr} \left( {1-P_s } \right) T_{collision} +\left( {1-P_{tr} } \right) slottime+P_{tr} P_s P_e T_e \end{aligned}$$
(29)

This time can be calculated by taking the successful transmission time \(T_{success}\) with a probability of \(P_{s}(1-P_{e})\), unsuccessful transmission time due to collision \(T_{collison}\) with a probability of (\(1-P_{s})\), unsuccessful transmission time \(T_{e}\) due to channel errors with a probability of \(P_{s}T_{e}\) and idle slot time can be calculated with a probability of (\(1-P_{tr})\). Here, \(T_{collision}\) and \(T_{e}\) are assumed to be the same. Here, \(P_{tr}\) and \(P_{b}\) can be interchanged. The equations for \(T_{success}\) and \(T_{collison}\) using basic and RTS/CTS access mechanisms are given in [8]. In the proposed model, under non-saturated traffic conditions, the four unknown parameters \(\tau , p_{tr}, p_{col}\) and \(q\) are related to each other and these can be evaluated numerically. Here \(P_{s}\) is the successful packet transmission probability.

The equation for throughput when the channel errors are considered becomes

$$\begin{aligned} S=\frac{P_{tr} P_s (1-P_e )E[P]}{P_{tr} P_s (1-P_e )T_{success} +P_{tr} (1-P_s )T_{collision} +(1-P_{tr} )*slottime+P_{tr} P_s P_e T_e } \end{aligned}$$
(30)

Where Slottime is the idle slot time and \(E[P]\) is the average packet payload size.

4 End-to-End Delay Analysis

The End-to-End delay refers to the delay for a successfully transmitted packet. The End-to-End delay is the time duration that a packet lasts in the system since it has been handled by the MAC layer until an acknowledgment of its successful reception is achieved.

In this section, the average End-to-End delay, also called as packet delay, in single hop Ad hoc networks is analyzed. In Bianchi’s model, the retry limit is not considered whereas in Chatzimisios’ model, the retransmission limit is taken into account. But, the collision probability in these two models is almost the same for the given parameters. These two models exaggerate the collision probability as the freezing of the backoff counter when other transmissions are going on in the channel is not considered. Some researchers calculated the average packet delay for basic and RTS/CTS access modes considering retry limits, but the transmission errors were ignored. Therefore, these models do not predict the 802.11 frame delay in an accurate way. In this paper, an accurate delay analysis is made considering transmission errors and self loop probability of every backoff state. Most of the previous research was concentrated on throughput enhancement. In many cases, improvement is obtained at the expense of delay degradation. It is therefore necessary to improve the delay performance as well as throughput.

In the proposed Markov chain model, at any backoff stage, the backoff counter of a node freezes each time the interfering neighboring nodes start transmitting a packet. When the backoff timer resets to zero, the node starts transmitting the packet. At this time, the backoff timers of all interfering neighboring nodes are immediately frozen. The average delay for a single-hop network can be calculated as the product of the average number of slots required for a successful transmission and the average time interval between two consecutive time counter decrements. For multi-hop networks, this product is to be multiplied with the average number of hops [21]. In this paper, an accurate delay analysis for IEEE 802.11 DCF using CWMIDB algorithm is obtained. A homogeneous network with \(n\) nodes is considered with packet arrival rate of \(\lambda \) packets/sec. To climax the effect of data rate on delay performance, the analysis is made for different data rates (1, 5.5 and 11 Mbps). Bianchi’s, Daneshgaran’s and Chatzimisios’ models overestimate the collision probability since neither of the models account for the probability that the backoff counter is frozen when there is activity in the channel. The average End-to-End delay calculation is not included in either Bianchi’s model or Daneshgaran’s model. The accurate delay analysis of IEEE 802.11 wireless network is done in Chatzimisios’ and Ziouva’s models but the analysis is limited to saturated conditions.

4.1 Mathematical Analysis of End-to-End Delay of CAD Protocol using CWMIDB Algorithm

A successful transmission may occur at one of the several backoff stages. The equation for average packet delay for successful transmission can be found in [4]. Let \(E[N_{c}]\) be the number of collisions of a frame until its successful reception. This is given by the following equation:

$$\begin{aligned} E\left[ {N_c } \right] =\frac{1}{P_s }-1 \end{aligned}$$
(31)

Each node spends some time before accessing the channel under busy channel conditions. This is called backoff time and is represented with \(E[BD]\). When the transmitted frame collides, each node has to wait for some time before sensing the channel again. Let this time be \(T_{\mathrm{o}}\). Therefore mean frame delay is the sum of average time spent by the node during collisions and during successful transmission and can be calculated as

$$\begin{aligned} E\left[ D \right] =E\left[ {N_c } \right] \left( {E\left[ {BD} \right] +T_{collision} +T_o } \right) +\left( {E\left[ {BD} \right] +T_{success} } \right) \end{aligned}$$
(32)

\(T_{\mathrm{o}}\) depends on the access method and equals to

$$\begin{aligned} T_o =\left\{ {\begin{array}{l} SIFS+ACK\_timeout \\ SIFS+CTS\_timeout \\ \end{array}} \right. \end{aligned}$$
(33)

4.1.1 Calculation of  E [BD]:

The average backoff delay depends on the value of its counter and the duration for which the counter freezes when the node detects transmissions from other nodes. Channel is busy when other nodes are transmitting and also during the time when the node A is transmitting.

Now, number of times that the node is idle is given by

$$\begin{aligned} E\left[ \psi \right] =\frac{1}{P_b }-1 \end{aligned}$$
(34)

When the counter of a node is at state \(b_{i,k}\), the average number of backoff slots \(E[X]\) required to reach state 0 without taking into account the time the counter is stopped is given by

$$\begin{aligned} E\left[ X \right] =\left[ {\sum _{i=0}^m {\sum _{k=1}^{W_i -1} {kb_{i,k} } } } \right] =\sum _{k=1}^{W_0 -1} {kb_{0,k} } +\sum _{k=1}^{W_m -1} {kb_{m,k} } +\sum _{i=1}^{m-1} {\sum _{k=1}^{W_i -1} {kb_{i,k} } } \end{aligned}$$
(35)

The above Eq. is valid for both saturated and non-saturated traffic conditions except that a term (\(W_{0}+1\))/2 is to be added for saturated conditions. In non-saturated conditions, the node remains in idle state until the packet arrives at the node’s buffer. Therefore, the post backoff stage delay need not be considered. In saturated traffic conditions, the node enters the post backoff stage to provide IPB delay, and hence the packet experiences this delay. But, to get the generalized Eq. for both situations, the average number of slots is calculated for backoff stages 0 to \(m\) and the average slots in the post backoff stage is added in saturation scenarios.

Based on equations of \(b_{0,0}, b_{i,k}\) and \(b_{m,k},\) the equation for \(E[X]\) becomes (36)

$$\begin{aligned} E\left[ X \right]&= \frac{b_{0,0} }{6\left( {1-P_b } \right) }\nonumber \\&\times \left[ {\frac{{\begin{array}{l} P_b \left( {1-q} \right) \left( {W_0^2 -1} \right) \left( {1-P_{eq} } \right) \left( {1-\left( {2P_{eq} } \right) ^{2}} \right) \left( {1-P_{eq}^2 } \right) \\ +P_{eq}^m \left( {2^{m+4}W_0^2 -1} \right) \left( {1-\left( {2P_{eq} } \right) ^{2}} \right) \left( {1-P_{eq}^2 } \right) +\,4P_{eq}^2 W_0^2 \left( {1-\left( {2P_{eq} } \right) ^{m-1}} \right) \\ \left( {1-P_{eq}^2 } \right) \left( {1-P_{eq} } \right) +16P_{eq} W_0^2 \left( {1-\left( {2P_{eq} } \right) ^{m-1}} \right) \left( {1-P_{eq}^2 } \right) \left( {1-P_{eq} } \right) \\ -\left[ {P_{eq}^2 \left( {1-\left( {P_{eq} } \right) ^{m-1}} \right) +P_{eq} \left( {1-P_{eq}^{m-1} } \right) } \right] \left( {1-P_{eq} } \right) \left( {1-\left( {2P_{eq} } \right) ^{2}} \right) \\ \end{array}}}{\left( {1-P_{eq} } \right) \left( {1-P_{eq}^2 } \right) \left( {1-\left( {2P_{eq} } \right) ^{2}} \right) }} \right] \nonumber \\ \end{aligned}$$
(36)

Let \(E[N_{fon}]\) be the average number of times that the node detects transmissions from other nodes and is given by

$$\begin{aligned} E[N_{fon} ]=\frac{E[X]}{\max (E[\psi ],1)}-1 \end{aligned}$$
(37)

Therefore, the average time \(E[S]\) that the counter stopped while listening to other nodes transmissions is

$$\begin{aligned} E\left[ S \right] =E\left\lfloor {N_{fon} } \right\rfloor \left( {P_s T_{success} +\left( {1-P_s } \right) T_{collision} } \right) \end{aligned}$$
(38)

Now, the average backoff delay \(E[BD]\) is

$$\begin{aligned} E\left[ {BD} \right] =E\left[ X \right] +E{\left\lfloor {N_{fon} } \right\rfloor } \left( {P_s T_{success} +\left( {1-P_s } \right) T_{collision} } \right) \end{aligned}$$
(39)

By substituting the above equations into the equation of \(E[D]\), the mean frame delay can be calculated.

The notations used in analytical analysis are listed in Table 1.

Table 1 Notations used in analytical analysis
Full size table

5 Results and Discussion

In this paper, a new CWMIDB algorithm is proposed for IEEE 802.11 DCF protocol. The throughput analysis for saturated and non-saturated traffic conditions under ideal and Rayleigh fading channel is carried out and it is compared with various existing backoff algorithms such as HB, BEB, DIDD etc. Most of the developed algorithms enhance the throughput at the expense of degradation in packet delay. The proposed CWMIDB algorithm greatly improves the system performance in terms of throughput as well as End-to-End delay.

5.1 Collision Probability

Figure 2 depicts how the collision probability depends on the number of nodes for different backoff algorithms. Compared to other models, the number of collisions reduces in the proposed model using CWMIDB algorithm. For a network with 25 nodes, the collision probability reduces by 8 % using CWMIDB algorithm when compared to the proposed model using BEB algorithm (CAD protocol). This reduction is even more when compared to Chatzimisios’, Ziouva’s and Bianchi’s models.

Fig. 2
figure 2

Collision probability as a function of number of nodes

Full size image

5.2 Saturation Throughput Analysis under Ideal Channel Conditions

The throughput is analyzed assuming saturated traffic load in ideal channel conditions i.e. the traffic at each node is saturated when \(q\rightarrow \)1 and ideal channel conditions occur when \(P_{e} = 0\). Figure 3 shows the resulting throughput using basic access and RTS/CTS mechanisms. The proposed CWMIBD algorithm is compared to HB, DIDD and BEB algorithms. CWMIDB algorithm is also compared with the proposed model with BEB algorithm. When the number of nodes increases, more collisions occur and hence throughput decreases. For 25 contending nodes, saturation throughputs of 0.7411, 0.6801 and 0.6408 Mbps are obtained under basic access mechanism using CWMIDB, the proposed model with BEB and DIDD algorithms respectively. That is, the throughput of the CWMIDB algorithm is improved by 8.97 % compared to the proposed model with BEB algorithm and 15.7 % compared to DIDD algorithm. Compared to the HB and legacy BEB algorithms, this improvement is 27.14 and 20.2 % correspondingly. Figure 3(b) portrays that RTS/CTS access mechanism achieves higher throughput compared to basic access mechanism due to minimum collisions and shorter collision time.

Fig. 3
figure 3

Saturation throughput as a function of number of nodes

Full size image

From the above analysis, it is clear that the CWMIDB algorithm consistently outperforms other backoff algorithms due to the presence of post backoff stage, backoff freezing states and the selection of contention window for each collision.

5.3 Non-Saturated Throughput Analysis Considering Transmission Errors

The HB and DIDD backoff algorithms were developed for saturated traffic and error-free channel conditions. So the throughput of CWMIDB algorithm under finite load and in erroneous channel conditions is now compared with Daneshgaran’s model (BEB algorithm) and with the developed CAD protocol using BEB algorithm. The data rate is taken as 1 Mbps and the size of MSDU is taken as 1,000 Bytes. Figure 4 depicts the variation of throughput against different packet arrival rates for different packet errors using basic access mechanism when \(n = 50\). Independent of packet arrival rate, the CWMIDB algorithm achieves higher throughput. However, when \(\lambda \) increases above 40 Pkts/s, the saturation behavior occurs. When packets arrive at a rate of 100 Pkts/s, throughput improvement using CWMIDB algorithm is 8.6 % higher compared to Daneshgaran’s model. As seen from the figure, the throughput performance of CWMIDB algorithm is better compared to that of the proposed model with BEB algorithm.

Fig. 4
figure 4

Non-saturation throughput as a function of \(\lambda \) for different packet errors using basic access mechanism

Full size image

The throughput as a function of packet arrival rate using RTS/CTS mechanism is plotted in Fig. 5. When the packet arrival rate exceeds 30 Pkts/s, the throughput enters saturation conditions. RTS/CTS mechanism is advantageous compared to basic access mechanism due to lesser packet collisions resulting in higher throughput.

Fig. 5
figure 5

Non-saturation throughput as a function of \(\lambda \) for different packet errors using RTS/CTS mechanism

Full size image

Figure 6 illustrates that the throughput increases with packet length. This is because all the packets have same headers independent of the payload information. So, compared to larger payload information, the overhead is more for smaller payloads and hence the throughput is less. As the packet length continues to increase, the throughput increases at a slower rate. There is no significant change in throughput when the packet length is above 1,500 bytes and it saturates when the packet length is greater than 2,000 bytes. For a packet size of 1,000 bytes, throughputs of 0.7226, 0.7031 and 0.6912 Mbps are obtained using CWMIDB, the proposed model with BEB and Daneshgaran’s model respectively for \(n = 25\). Therefore, the throughput of CWMIDB algorithm is 8 % higher compared to that of Daneshgaran’s model. Even in congested environments, i.e. when \(n = 50\), the performance of the proposed CWMIDB algorithm is good.

Fig. 6
figure 6

Non-saturation throughput as a function of packet length for two network sizes using basic access mechanism

Full size image

The accuracy of the proposed model can be observed under basic access mechanism. With basic access mechanism, the number of packet collisions increase which increases the freezing duration of other nodes.

5.4 End-to-End Delay Analysis in Error Prone Channel Conditions

Since the average End-to-End delay calculation is not included in Daneshgaran’s model, the delay performance of CWMIDB algorithm is compared to that of the CAD protocol with BEB algorithm. The number of nodes versus End-to-End delay for three data rates (1, 5.5 and 11 Mbps) under the two access mechanisms is plotted in Fig. 7. Results show that the End-to-End delay greatly depends on data rate. When the data rate increases, packet transmission time reduces and hence the delay drops significantly. The delay performance achievable by the RTS/CTS mechanism is always higher compared to basic access mechanism due to shorter packet collision duration.

Fig. 7
figure 7

Nodes versus End-to-End delay in erroneous channel for different data rates (\(\lambda = 100\) Pkts/s)

Full size image

For a network with 25 nodes under basic access mechanism, compared to BEB algorithm, the delay using CWMIDB algorithm reduces by 62.1, 62.1 and 62.8 % for data rates of 1, 5.5 and 11 Mbps respectively. This delay reduction is even more for large network sizes. Similarly, in a network with 25 nodes under RTS/CTS access scheme, using CWMIDB algorithm, the delay reduces by 61.2, 60.9 and 61.2 % when the data is transmitted at 1, 5.5 and 11 Mbps respectively.

The dependency of End-to-End delay on packet arrival rate is also observed. From Fig. 8, it is observed that the delay required to transmit the packet is very less using CWMIDB algorithm compared to BEB algorithm. This reduction is 61.8 % under basic access mechanism and 60.85 % under RTS/CTS mechanism for a packet arrival rate of 50 Pkts/s when the contending nodes are 25 and \(P_{e} = 10^{-1}\).

Fig. 8
figure 8

Packet rate versus End-to-End delay in erroneous channel for different packet arrival rates

Full size image

Finally, the delay variation with respect to packet length for three network sizes is observed and shown in Table 2 and Table 3. The delay increases with packet size because it takes a long time to transmit the large payload information. Also, the delay increases with number of nodes due to a higher number of collisions.

Table 2 Comparison of End-to-End delay for different packet lengths using basic access mechanism
Full size table
Table 3 Comparison of End-to-End delay for different packet lengths using RTS/CTS mechanism
Full size table

Table 2 shows the values of End-to-End delay for different packet sizes under basic access mechanism. In a network with 20 nodes, under basic access mechanism, to transmit a packet of 1,000 Bytes, the delay required using BEB algorithm is 0.7055 s. But using CWMIDB algorithm, only 0.2639 s is required to transmit the same data because this algorithm avoids channel capture effect and reduces the number of collisions. In other words, the delay is greatly reduced by 62.6 %. Similarly for the same combination, the delay reduces by 61.5 % under RTS/CTS mechanism. This can be observed from the Table 3. The parameters listed in Table 4 are used to analyze the performance of the CAD protocol with CWMIDB algorithm.

Table 4 Simulation parameters
Full size table

6 Conclusions

In this paper, a new CWMIDB algorithm for WLANs is proposed. The Markov chain model developed for the CAD protocol is used as a base for developing the CWMIDB algorithm. The proposed algorithm can be implemented with a slight modification to the current BEB algorithm used in the legacy DCF protocol. The main feature of this algorithm is to avoid channel capture and improve the performance of the wireless network. In this algorithm, the size of the contention window will not be doubled immediately after a collision. Instead, it will be selected based on the number of collisions. The collision probability has been analysed for the proposed algorithm. The effects of the number of nodes, packet arrival rate, packet size, packet error rate and data rate on the performance of the network have been analyzed. Results show that the proposed CAD protocol with CWMIDB algorithm provides an edge over the existing backoff algorithms in terms of throughput and delay. It is also observed that throughput increases and the average delay decreases under RTS/CTS mechanism, as compared to basic access mechanism. The performance of the CWMIDB algorithm is very efficient, especially when basic access mechanism is employed in highly congested environments.