# Performance Analysis of the IEEE 802.11 Distributed Coordination Function

1. $b_{i-1,0} \cdot p = b_{i,0} \rightarrow b_{i,0} = p^ib_{0,0}$ $\space \space \space \space 0<i<m$
$b_{m-1,0} \cdot p = (1-p)b_{m,0} \rightarrow b_{m,0} = \frac {p^m}{1-p}b_{0,0}$

前面第一項透過論文圖 4 可知道 $b_{i-1,0} \cdot p = b_{i,0}$ ，而第二項透過圖可以知道 $b_{m,0}$ 可由 $p\cdot (b_{m,0} + b_{m-1,0})$ 得到，因此寫成 $b_{m,0} = p\cdot (b_{m,0} + b_{m-1,0})$ ，移項過後 $(1-p) \cdot b_{m,0} = p\cdot b_{m-1,0}$

2. $p = 1 - (1-\tau)^{n-1}$

p 為碰撞機率，而碰撞是因為多個 statation 同一時間要送，因此 p 可設為 1 減去其他 n-1 個 station 皆沒要送: $(1-\tau)^{n-1}$，而 $\tau$ 就代表 station 要送，而送的時機是 backoff time counter 為 0 ，寫成如下:
\begin{equation}
p = 1 - (1-\tau)^{n-1}
\end{equation}

3. $\tau = \displaystyle\sum_{i=0}^{m}b_{i,0} = \frac {b_{0,0}}{1-p} = \frac {2(1-2p)}{(1-2p)(W+1)+pW(1-(2p)^m)}$

現在我們想要的是 $\tau$ ，代表 station 要送的時機，而送的時機是 backoff time counter 為 0，總和 $i = 0$ ~ $m$ 個也就是 $\displaystyle\sum_{i=0}^{m}b_{i,0}$

1. 透過第一題得出的 close from 的去使用等比級數和公式
\begin{equation}
S_n = \frac {a_n(1-p^n)}{1-p}
\end{equation}
先將 $b_{0,0}$ 提出後，前 $n = 0$ ~ $m - 1$ 項總和後會是 $\frac {1(1-p^m)}{1-p}$ ，再加上 $n = m$ 這項 $\frac {p^m}{1-p}$ ，可以得到以下:
\begin{equation}
\displaystyle\sum_{i=0}^{m}b_{i,0} = \frac {b_{0,0}}{1-p}
\end{equation}
2. 現在將 $b_{0,0}$ 透過已知所有 Markov chain 的路徑總和應為 1 的資訊替換為以下得到的 $b_{0,0}$ :
\begin{equation}
1 = \sum_{i=0}^{m} \sum_{k=0}^{W_i-1} b_{i,k} = \sum_{i=0}^{m} b_{i,0} \sum_{k=0}^{W_i-1} \frac{W_i - k}{W_i} = \sum_{i=0}^{m} b_{i,0} \frac{W_i + 1}{2}
\end{equation}

\begin{equation}
= \frac{b_{0,0}}{2} \left[ W \left( \sum_{i=0}^{m-1} (2p)^i + \frac{(2p)^m}{1-p} \right) + \frac{1}{1-p} \right]
\end{equation}

其中
\begin{equation}
b_{i,k} = \frac{W_i - k}{W_i} \cdot
\begin{cases}
(1 - p) \sum_{j=0}^{m} b_{j,0} & \text{if } i = 0 \\
p \cdot b_{i-1,0} & \text{if } 0 < i < m \\
p \cdot (b_{m-1,0} + b_{m,0}) & \text{if } i = m
\end{cases}
\end{equation}
而透過 $\displaystyle\sum_{i=0}^{m}b_{i,0} = \frac {b_{0,0}}{1-p}$ 及第一題的資訊可以將此項改寫為
\begin{equation}
b_{i,k} = \frac{W_i - k}{W_i} b_{i,0} \quad i \in (0, m), \quad k \in (0, W_i - 1).
\end{equation}
將 $b_{0,0}$ 移至左，得到:
\begin{equation}
b_{0,0} = \frac {2(1-2p)(1-p)}{(1-2p)(W+1)+pW(1-(2p)^m)}
\end{equation}
3. 最後替換 $b_{0,0}$ 得到:
\begin{equation}
\tau = \displaystyle\sum_{i=0}^{m}b_{i,0} = \frac {b_{0,0}}{1-p} = \frac {2(1-2p)}{(1-2p)(W+1)+pW(1-(2p)^m)}
\end{equation}

4. $(eg. W=32,\space m = 3 \space or \space 5, \space n = 3)$

\begin{equation}
\tau(p) = \frac {2}{1+W+pW\displaystyle\sum_{i=0}^{m-1}(2p)^i }
\end{equation}
將 $W = 32,\space m = 3\space or\space m = 5,\space n = 3$ 代入後得到 $\frac{2}{33+32p(1+2p+4p^2)}$ 及 $\frac{2}{33+32p(1+2p+4p^2+8p^3+16p^4)}$ ， 透過論文中提到的
> Once independence is assumed, and p is supposed to be a constant value

由於 p 為機率必小於 1 ，隨著次方增大，該值會越來越小並漸漸失去影響。

在程式碼中我嘗試計算 $\tau$ 在不同 $W, m, n, p$ 時所對應的值。