802.11協議精讀13：協議理論性能（Bianchi模型）－IT工程師數位筆記本

文章出處

序言

為了更好理解一些802.11的后續設計，我們需要深入了解一下802.11的協議性能。我們之前簡單描述了下協議性能的部分，這一段我們討論下具體數學模型下的802.11性能（Bianchi模型）。

Bianchi模型出自于論文《Performance Analysis of the IEEE 802.11 Distributed Coordination Function》，該論文在2000年的時候發表在JSAC（IEEE Journal on selected areas in communications）上，根據google scholar上的記錄，該論文的他引次數已經高達8267次（相應的資源：bianchi模型）。其實關于802.11的理論性能從協議剛開始出來的時候就有人研究，直到現在，這個問題還是在繼續研究中，該論文是這個領域中最為有代表性的一篇文章，故凡是做802.11協議的，都會閱讀理解這篇文章。

PS：本文并不是按照Bianchi原文以推導的形式給出，而是為了方便理解進行的倒敘。其中部分表述和定義如果存在一些錯誤，還請見諒。

Bianchi模型的假設

我們首先列舉一些Bianchi模型中，所設定的一些假設。

Single-cell Network：可以簡單認為是個單信道環境，即所有節點共享一個功能信道，并且這個網絡中，所有的節點都是互相可以監聽到對方的。The collision processes of the nodes can be decoupled：即無論節點重傳了幾次，其在傳輸時候的沖突概率都是一個定值，且都是相對獨立的。Channel conditions are ideal：信道是一個理想信道，即傳輸錯誤僅僅由于傳輸碰撞造成，與物理層的信道質量無關。且由于Single-cell的假設，所有節點都可以互相監聽，所以網絡中也沒有隱藏和暴露終端問題。Saturation throughput：Bianchi模型分析為飽和情況下的吞吐量，即任意一個節點都是假設有數據包的，不存在節點競爭到信道之后，沒有數據包待發送的情況出現。
No packet dropped：按照協議所述，如果數據包發送失敗，節點是可以發起重傳的。這個重傳次數上限為6次，如果超過該次數，那么就需要丟包。而在Bianchi模型中，保留的重傳次數上限為6次的這個設置，不過沒有設定6次以后進行丟包，而是一直保持在第6次這個zhu
MAC層效率（歸一化吞吐量）

在之前的一篇文章中，我們定義了MAC層的歸一化吞吐量為傳輸真實數據（Data）的時間占總傳輸時間（Overhead + Data）的比例。

在Bianchi模型中，其具體定義如下（部分表述有稍微修飾一下）

其中為歸一化吞吐量（注：本文討論的吞吐量都是系統的吞吐量，沒有具體到某一個節點的吞吐量上，而是所有節點整體的吞吐量），分子分母都是一個數學期望，實際上就是平均時間。分母代表的是Generic slot（這個后面我們說明，與DCF中的標準slot時間存在區別），分子定義的是在這個Generic slot內，傳輸數據的時間。不嚴格的說，其物理意義和我們之前一篇描述的定義是一樣的。

Generic Slot：這個是一個隨機選擇的時間，其與802.11中DCF的具體接入機制有關。一般意義上，我們理解其物理意義就是Backoff counter倒數1次的時間間隔。

如上圖為Generic slot的3種可能取值。其中 $\sigma$ 代表協議中的slot時間（比如802.11g中的9μs）， $T_{s}$ 為成功傳輸所花費的總時間， $T_{c}$ 為碰撞一次所花費的總時間。 $P_{tr}$ 為至少有一個節點準備發送的概率， $P_{s}$ 為成功傳輸的概率（實際上理解成只有1個節點傳輸的概率，如果有多個那么就會造成沖突）。我們進一步闡述如下：

情況1 — $\sigma$ ：若節點在Backoff過程中，經過1個slot，backoff counter未倒數到0。這個概率為 $1-P_{tr}$ ，消耗的時間就是一個slot，即 $\sigma$ 時間。
若節點經過這個slot，backoff counter正好倒數到0，那么節點就會發送數據（即概率 $P_{tr}$ ）。但是發送后，這里還存在兩種情況，一者發送成功，一者發送失敗。
情況2 - $T_{s}$ ：若節點成功發送該數據，那么損耗時間為 $T_{s}$ ，其對應概率為 $P_{tr}*P_{s}$ ，即不僅發送，且發送成功。情況3 - $T_{c}$ ：若節點發送數據，但是由于沖突（比如多個節點backoff counter倒數同時至0），那么這個數據幀是沒有無法成功被接收的，這個損耗的時間就是 $T_{c}$ 。其對應概率為 $P_{tr}*\left( 1-P_{s} \right)$ ，即雖然發送，不過發送失敗。
具體的 $T_{s}$ 和 $T_{c}$ 還與節點的工作模式有關（Basic模式或者RTS/CTS模式），我們分別解釋：

Basic模式：該模式的簡單流程如下圖：

其中 $T_{s}$ 和 $T_{c}$ 的時間如下：

其中代表物理層頭部的傳輸時間， SIFS 和 DIFS 都是協議給定的幀間間隔， ACK 為協議給定的ACK幀的傳輸時間， $\delta$ 為電磁波傳播延遲（DATA-ACK過程由于是一來一回，所以傳播延遲是兩個）。 $E\left[ P \right]$ 為payload的期望，代表數據包（MSDU）傳輸時間的均值。 $E\left[ P^{*} \right]$ 代表的是發生沖突時，沖突中較長數據幀的均值，因為沖突只有在較長數據幀發送完之后，信道才被釋放。

RTS/CTS模式：該模式的簡單流程如下圖：

其中 $T_{s}$ 和 $T_{c}$ 的時間如下：

其中 RTS 和 CTS 代表其數據幀對應的傳輸時間。上圖中我們可以發現，RTS/CTS模式下，雖然傳輸時間是相應增加了（由于引入了RTS/CTS握手），但是沖突損耗是減少了。該設計能夠保證，這個在節點較多的情況下（即碰撞概率較大的情況下），RTS/CTS的性能受到較小的影響。

本文為了簡化，我們直接假設所有節點的數據包大小是一個定值，從而 $E\left[ P \right]$ 就等于傳輸這個數據包所花費的時間，且 $E\left[ P \right] =E\left[ P^{*} \right]$ 。（在bianchi原文中沒有進行該假設，只是為了簡化本文的敘述，所以我們做數據包大小為定值的假設）

綜合以上的Generic slot和其對應時間，我們可以具體給出歸一化吞吐量的具體計算公式。

其中分母就是Generic slot的均值（即事件概率乘以其對應時間），分子為在一個Generic內，成功傳輸數據（MSDU）部分的時間。

傳輸概率（ $P_{tr}$ ）和成功傳輸概率（ $P_{s}$ ）

前面我們給出了歸一化吞吐量的表達式，該式中，由于 $T_{s}$ 和 $T_{c}$ 中的參數都是協議給定。為了計算吞吐量，我們只要求出概率 $P_{tr}$ 和 $P_{s}$ 就行了。

$P_{tr}$ ：其物理意義是至少有一個節點，在這個slot內準備傳輸。這里 $\tau$ 指的是發送概率，

指的是總的競爭節點數目（由于假設是one-cell network，并且飽和吞吐量，所以所有節點都在競爭信道）。我們可以這樣理解 $P_{tr}$ 的物理意義： $\left( 1-\tau \right)$ 代表其中某

個節點沒有發送的概率， $\left ( 1-\tau \right )^{n}$ 所有節點都沒有發送的概率，所以其反面， $1-\left ( 1-\tau \right )^{n}$ 就是至少有

個節點可以發送的概率了。

$P_{s}$ ：這個實際上是個條件概率，物理意義是在有節點發送的前提下（即分母的 $P_{tr}$ ），成功傳輸的概率（即有且只有一個節點正在傳輸）。分子我們可以這樣理解： $\tau^{1} * \left( 1-\tau \right) ^{n-1}$ ，其中 $\tau^{1}$ 代表代表有

個節點正在發送， $\left( 1-\tau \right) ^{n-1}$ 代表其余 n-1

個節點都沒有發送，即有且只有一個節點發送，那么才沒有沖突。又是因為這個節點沒有固定下來說，具體某一個節點，所以要做個排列組合，即一共

個節點，即

中情況，所以分子再乘以

。

上面我們介紹了 $P_{tr}$ 和 $P_{s}$ 的具體表達式，其中是節點數目，所以一般也是給定的。所以最后剩下來的參數就是 $\tau$ 了，我們需要對該參數進行分析。

發送概率（ $\tau$ ）和沖突概率（

）

通過以上分析，我們最終只要知道每一個節點的發送概率 $\tau$ 就可以求出吞吐量了，但是這個 $\tau$ 就沒有那么好求了，其主要是源于802.11協議中，發送和沖突是互相影響的。發送概率 $\tau$ 中包含了沖突概率，而沖突概率中也包含了發送概率 $\tau$ 。

以下我們描述一下bianchi模型中具體分析的過程。bianchi模型實際上采用了一個二維的Markov chain，具體如下圖：

我們先簡單說明下其中的一些參數，然后在具體討論。每一橫行代表的是一次Backoff過程，每一縱行代表的是一次二進制指數增加CW窗口大小的過程。以第1行為例說明如下：

狀態 $\left( 0,W_{0}-1 \right)$ ，

代表是第0次的Backoff過程（即CW窗口是默認大小）， $W_{0}-1$ 代表Backoff counter選取數值為 $W_{0}-1$ （由于CW范圍是從0開始，所以最大數值為 CW-1

）， $W_{0}$ 就是第0次Backoff時候的CW大小。
狀態 $\left( 0,W_{0}-1 \right)$ 轉移至 $\left( 0,W_{0}-2 \right)$ 代表了1次Backoff counter的回退（如圖中紅色1標識），其概率為

（因為不存在碰撞）。
當Backoff counter倒數至0后，即轉移至狀態 $\left( 0,0 \right)$ 時，節點可以發送數據。
若發送成功（即概率 1-p

），如圖中紅色2標識，就需要重新在CW窗口內選擇一個隨機數（即某個隨機數被選中的概率為 $1/ W_{0}$ ），并轉移到該狀態（比如轉移到狀態 $\left( 0,1 \right)$ ，其轉移概率為 $\left( 1-p \right) / W_{0}$ ）。
若發送失敗（即概率

），如圖中紅色3標識，那么需要首先調節CW窗口大小（指數為2增長），即 $W_{0}$ 變為 $W_{k}$ ，在第二輪中， k=1

。然后節點需要在更新后的CW窗口大小 $W_{1}$ 中選擇一個隨機數（概率為 $1/ W_{1}$ ），并轉移至該狀態（比如轉移到狀態 $\left( 1,1 \right)$ ，其轉移概率為 $p / W_{1}$ ）。
在Bianchi模型中，假設是沒有丟包過程的。而二進制指數回退并不是上限無窮的增加CW窗口，其有個最大次數

次，在bianchi模型中。如果節點第m次回退后，還是發送失敗，則不增加CW窗口大小，而是直接在這一輪設置的CW大小（ $W_{m}$ ）中，直接選擇一個隨機數進行重傳（這個概率就是 $p / W_{m}$ ）。

更一般的我們用數學標識即是下面的式子：

下面我們先表示沖突概率

由于Bianchi模型中，已經假設節點之間的沖突過程是相對獨立的。假設我現在是某個節點，我已經處于發送狀態，所以剩余的 n-1 個節點都不能夠發送（即概率 $\left( 1-\tau \right) ^{n-1}$ ），如果有任意一個也處于發送狀態（即概率 $1-\left( 1-\tau \right) ^{n-1}$ ），那么就會發生沖突。

最終我們考慮發送概率 $\tau$ ，參考下圖

協議規定，如果節點Backoff counter倒數到0，那么就可以進行發送。由于節點可能處在不同的backoff狀態（即初次傳輸，重傳1次，重傳2次等等），所以我們需要對轉移到這些狀態的概率做一個累加，即：

其中代表CW最多增加次，是個index，代表第次Backoff過程，代表狀態， $b_{i,0}$ 代表第次Backoff counter倒數到0。因為每一次發送完之后，節點都必須要轉移到狀態 $\left( 0,0 \right)$ 。所以我們可以直接計算轉移到狀態 $b_{0,0}$ 的條件概率。即如果發送沒有發生沖突（即概率 1-p ），狀態轉移至 $b_{0,0}$ 的概率（即 $\frac{b_{0,0}}{1-p}$ ）。

最后我們表示出 $b_{0,0}$ 狀態時候的穩態概率即可

這個概率的物理意義有些繁雜，我們就不進行展開了，最終我們可以計算發送概率為：

從而獲得以下的一個聯立的方程（其中上式的 $\tau$ 和下面的聯立表達還有一個參數帶入的步驟，具體可以參考論文，這里直接跳躍到下面的結果了）：

我們看到上面的表達中，表達式中包含 $\tau$ ，同樣 $\tau$ 中表達式也包含。故我們需要采用fix-point的方法，才可以對其進行求解。具體求解方法我們在下一篇文章中進行討論。

結果分析

以下我們直接參考Bianchi論文中給出的結果，大致說明一下：

上圖橫軸代表節點數目（節點數目從0到50），縱軸代表歸一化吞吐量（即范圍從0~1，圖中是從0.5開始繪制）。圖中一共繪制5組結果：

$\triangle$ 代表Basic模式下，初始的CW窗口設置為32，CW窗口可以回退增大3次。
$\square$ 代表Basic模式下，初始的CW窗口設置為32，CW窗口可以回退增大5次。
$\circ$ 代表Basic模式下，初始CW窗口設置為128，CW窗口可以回退增大3次。

從這三組值的對比上可以看出，節點數越多，Basic模式的性能越差。其基本原因就是沖突概率的增加。通過增加CW窗口大小的方法，能夠一定程度上避免沖突問題，所以能夠緩解隨著節點數增加，而造成的吞吐量下降。初始設置更大的CW比增加回退次數要更有效一些。

$\ast$ 代表RTS/CTS模式下，初始的CW窗口設置為32，CW窗口可以回退增大3次。
$\diamond$ 代表RTS/CTS模式下，初始的CW窗口設置為128，CW窗口可以回退增大3次。

在RTS/CTS模式下，可以發現其吞吐量相比Basic模式，能夠在節點數較多的時候，受到較小的影響，其基本原因在于沖突損耗上。Basic模式沖突一次是損失了一個數據幀的時間，而RTS/CTS模式下，沖突一次僅僅損耗了一個RTS時間。同時我們還可以看到，由于沖突損失較小的情況下，我們沒有必要設置更大的CW窗口大小，因為更大的窗口大小就意味著更多的回退次數，從而消耗更多的時間。

看文倉www.92to.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20161217/72748.html

文章列表