802.11協議精讀13：協議理論性能（Bianchi模型）

02-03

序言

為了更好理解一些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模型中，其具體定義如下（部分表述有稍微修飾一下）

其中 $S$ 為歸一化吞吐量（註：本文討論的吞吐量都是系統的吞吐量，沒有具體到某一個節點的吞吐量上，而是所有節點整體的吞吐量），分子分母都是一個數學期望，實際上就是平均時間。分母代表的是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}$ 的時間如下：

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

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

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

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

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

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

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

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

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

$P_{tr}$ ：其物理意義是至少有一個節點，在這個slot內準備傳輸。這裡 $tau$ 指的是發送概率， $n$ 指的是總的競爭節點數目（由於假設是one-cell network，並且飽和吞吐量，所以所有節點都在競爭信道）。我們可以這樣理解 $P_{tr}$ 的物理意義： $left( 1-tau right)$ 代表其中某 $1$ 個節點沒有發送的概率， $left ( 1-tau right )^{n}$ 所有節點都沒有發送的概率，所以其反面， $1-left ( 1-tau right )^{n}$ 就是至少有 $1$ 個節點可以發送的概率了。

$P_{s}$ ：這個實際上是個條件概率，物理意義是在有節點發送的前提下（即分母的 $P_{tr}$ ），成功傳輸的概率（即有且只有一個節點正在傳輸）。分子我們可以這樣理解： $tau^{1} * left( 1-tau right) ^{n-1}$ ，其中 $tau^{1}$ 代表代表有 $1$ 個節點正在發送， $left( 1-tau right) ^{n-1}$ 代表其餘 $n-1$ 個節點都沒有發送，即有且只有一個節點發送，那麼才沒有衝突。又是因為這個節點沒有固定下來說，具體某一個節點，所以要做個排列組合，即一共 $n$ 個節點，即 $n$ 中情況，所以分子再乘以 $n$ 。

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

發送概率（ $tau$ ）和衝突概率（ $p$ ）

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

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

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

狀態 $left( 0,W_{0}-1 right)$ ， $0$ 代表是第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標識），其概率為 $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}$ ）。
若發送失敗（即概率 $p$ ），如圖中紅色3標識，那麼需要首先調節CW窗口大小（指數為2增長），即 $W_{0}$ 變為 $W_{k}$ ，在第二輪中， $k=1$ 。然後節點需要在更新後的CW窗口大小 $W_{1}$ 中選擇一個隨機數（概率為 $1/ W_{1}$ ），並轉移至該狀態（比如轉移到狀態 $left( 1,1 right)$ ，其轉移概率為 $p / W_{1}$ ）。

在Bianchi模型中，假設是沒有丟包過程的。而二進位指數回退並不是上限無窮的增加CW窗口，其有個最大次數 $m$ 次，在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次等等），所以我們需要對轉移到這些狀態的概率做一個累加，即：

其中 $m$ 代表CW最多增加 $m$ 次， $i$ 是個index，代表第 $i$ 次Backoff過程， $b$ 代表狀態， $b_{i,0}$ 代表第 $i$ 次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$ 和下面的聯立表達還有一個參數帶入的步驟，具體可以參考論文，這裡直接跳躍到下面的結果了）：

我們看到上面的表達中， $p$ 表達式中包含 $tau$ ，同樣 $tau$ 中表達式也包含 $p$ 。故我們需要採用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窗口大小，因為更大的窗口大小就意味著更多的回退次數，從而消耗更多的時間。

本文為原創文章，如需轉載須註明出處和原文鏈接。

歡迎大家關注我們的微信公眾號：無線技術大講堂，請搜索公眾號（must_wireless）。