Performance Analysis of the IEEE 802.11 Distributed Coordination Function

1. $b_{i-1,0}\cdot p=b_{i,0}\to b_{i,0}=p^i{b}_{0,0}$
   $0<i<m$
   
   $b_{m-1,0}\cdot p=(1-p)b_{m,0}\to 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 ，寫成如下:
   
   $$p=1-(1-\tau {)}^{n-1}$$

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 的去使用等比級數和公式
      

      $$S_n=\frac{a_n(1-p^n)}{1-p}$$
      先將
      $b_{0,0}$ 提出後，前
      $n=0$ ~
      $m-1$ 項總和後會是
      $\frac{1(1-p^m)}{1-p}$ ，再加上
      $n=m$ 這項
      $\frac{p^m}{1-p}$ ，可以得到以下:
      
      $${\displaystyle \sum _{i=0}^m{b}_{i,0}=\frac{b_{0,0}}{1-p}}$$

   2. 現在將

      $b_{0,0}$ 透過已知所有 Markov chain 的路徑總和應為 1 的資訊替換為以下得到的
      $b_{0,0}$ :
      
      $$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}$$
      $$=\frac{b_{0,0}}{2}[W(\sum _{i=0}^{m-1}(2p{)}^i+\frac{(2p{)}^m}{1-p})+\frac{1}{1-p}]$$

      其中
      

      $$b_{i,k}=\frac{W_i-k}{W_i}\cdot \{\begin{array}{ll}(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{array}$$
      而透過
      ${\displaystyle \sum _{i=0}^m{b}_{i,0}=\frac{b_{0,0}}{1-p}}$ 及第一題的資訊可以將此項改寫為
      
      $$b_{i,k}=\frac{W_i-k}{W_i}{b}_{i,0}i\in (0,m),k\in (0,W_i-1).$$
      將
      $b_{0,0}$ 移至左，得到:
      
      $$b_{0,0}=\frac{2(1-2p)(1-p)}{(1-2p)(W+1)+pW(1-(2p{)}^m)}$$

   3. 最後替換

      $b_{0,0}$ 得到:
      
      $$\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)}}$$

   4. $(eg.W=32,m=3or5,n=3)$
      $$\tau (p)=\frac{2}{1+W+pW{\displaystyle \sum _{i=0}^{m-1}(2p{)}^i}}$$
      將
      $W=32,m=3orm=5,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$ 時所對應的值。