AP 和 STAS

2023 研究生數學建模競賽A題

WLAN網絡通信信道接入策略建模 機理建模+蒙特卡洛仿真分析

背景

無線本地網絡（WLAN, wireless local area network）也即Wi-Fi廣泛使用，提供低成本、高吞吐和便利的無線通信服務。基本服務集（BSS, basic service set）是WLAN的基本組成部分。處於某一特定覆蓋區域內的站點（STA, station）與一個專職管理BSS的無線接入點（AP, access point）組成一個BSS，稱STA關聯到AP。常見的AP有無線路由器、Wi-Fi熱點等，移動電話、便攜式計算機、物聯設備等是STA。AP給STA發送信息數據叫作下行方向，反之是上行方向，本文將AP和STA統稱為網絡節點，每個網絡節點的發送和接收不能同時發生。各網絡節點共享通信信道，通過載波偵聽多址接入/退避（CSMA/CA, carrier sense multi-access and collision avoidance）的策略避免沖突，稱為分佈式協調功能（DCF, distributed coordination function）。

問題：

問題1: 假設AP發送包的載荷長度為1500Bytes（1Bytes = 8bits），PHY頭時長為13.6μs，MAC頭為30Bytes，MAC頭和有效載荷采用物理層速率455.8Mbps發送。AP之間的RSSI為-70dBm。大部分時候隻有一個AP能夠接入通信信道，信息數據傳輸一定成功。當兩個AP同時回退到0而同時發送信息數據時，存在同頻幹擾。假設並發時的SIR較低，導致兩個AP的信息數據傳輸都失敗。請對該2 BSS系統進行建模，用數值分析方法求解，評估系統的吞吐。（參數參考附錄4，可編寫仿真器驗證模型精確度）

問題2 假設兩個AP采用物理層速率275.3Mbps發送信息數據，並發時兩個終端接收到信息數據的SIR較高，兩個AP的信息數據傳輸都能成功。其他條件同問題1。請對該2 BSS系統進行建模，用數值分析方法求解，評估系統的吞吐。（參數參考附錄4，可編寫仿真器驗證模型精確度）

2.2 兩BSS不互聽

在AP密集部署時，同頻AP之間的距離遠，AP間RSSI低於CCA門限，不互聽。AP認為通信信道空閑，因此總是在退避和發送信息數據。這是Wi-Fi裡常見的隱藏網絡節點問題，詳見附錄。可以預見的是，有很大概率出現二者同時或先後開始發送信息數據的情況。接收機解調信號時，PHY頭的前面部分碼元用於Wi-Fi信號識別、頻率糾錯、定時等功能，叫作前導（Preamble）。如圖2.3所示，當信號包先到時，接收機先解信號包的Preamble並鎖定，幹擾包被視為幹擾，信號包是否接收成功由SIR決定；當幹擾包先到時，接收機先鎖定到幹擾包的Preamble，錯過信號包的Preamble，導致信號包無法解調。小信號屏蔽算法能有效解決這個問題，因為信號包RSSI一般大於鄰小區的幹擾包，接收機在信號包到達時轉為鎖定RSSI更大的信號包，此時信號包能否接收成功同樣也由SIR決定。由此可以得知，在SIR比較小的情況下，如果信號包和幹擾包在時間上有如圖2.3的交疊時，一定會導致本次傳輸的失敗。

問題3 假設AP間RSSI為-90dBm，AP發送包的載荷長度為1500Bytes，PHY頭時長為13.6μs，MAC頭為30Bytes，MAC頭和載荷采用物理層速率455.8Mbps發送。Bianchi模型假設理想通信信道，實際上，無線傳輸環境是復雜多變的，當有遮擋物或者人走動時，無線通信信道都可能會快速發生比較大的變化。實測發現，當僅有一個AP發送信息數據時，即便不存在鄰BSS幹擾，也會有10%以內不同程度的丟包。假設因通信信道質量導致的丟包率P_e=10%。當兩個AP發包在時間上有交疊時，假設SIR比較小，會導致兩個AP的發包均失敗。請對該2 BSS系統進行建模，盡量用數值分析方法求解，評估系統的吞吐。（參數參考附錄4和6，可編寫仿真器驗證模型精確度）

2.3 三BSS

問題4 考慮3BSS場景，如圖2.2（c）所示，其中AP1與AP2之間，AP2與AP3之間RSSI均為-70dBm，AP1與AP3之間RSSI為-96dBm。該場景中，AP1與AP3不互聽，AP2與兩者都互聽，可以預見的是，AP2的發送機會被AP1和AP3擠占。AP1與AP3由於不互聽可能同時或先後發送信息數據。假設三個AP發送包的載荷長度為1500Bytes，PHY頭時長為13.6μs，MAC頭為30Bytes，MAC頭和載荷采用物理層速率455.8Mbps發送。假設AP1和AP3發包時間交疊時，SIR較大，兩者發送均成功。請對該3BSS系統進行建模，盡量用數值分析方法求解，評估系統的吞吐。（參數參考附錄4和6，可編寫仿真器驗證模型精確度）

縮略語 AP access point 無線接入點 ACK Acknowledgement 確認 ACKTimeout 確認超時 BSS basic service set 基本服務集 CCA clear channel assessment 通信信道可用評估 CSMA/CA carrier sense multi-access and collision avoidance 載波監聽多址接入/退避 CW contention window 競爭窗口 DCF distributed coordination function 分佈式協調功能 DIFS DCF inter-frame space DCF幀間距 MAC medium access control 媒體控制 PHY physical 物理層 RSSI received signal strength indication 接收信號能量強度 SIFS short inter-frame space 短幀間距 SIR signal to interference ratio 信幹比 STA station 站點 WLAN wireless local area network 無線本地網絡

問題分析

這是一個涉及無線本地網絡（WLAN）的分佈式通信信道接入和性能分析的數學建模問題。首先，我們來進行一次內容梳理和分析。

背景知識：

無線本地網絡 (WLAN) – WLAN 提供低成本、高吞吐和便利的無線通信服務。 – 基本服務集 (BSS) 是 WLAN 的核心部分，包括站點 (STA) 和無線接入點 (AP)。例如，移動電話和便攜式計算機是 STA，無線路由器是 AP。 – 信息數據傳輸有兩個方向：上行（STA 到 AP）和下行（AP 到 STA）。 – 所有網絡節點共享通信信道，並采用 CSMA/CA 策略來避免沖突。這被稱為分佈式協調功能 (DCF)。

分佈式通信信道接入和二進制指數退避 – DCF 是一個基於競爭的通信信道接入功能，包括三個階段：通信信道可用評估 (CCA)、隨機回退和信息數據傳輸。 – CCA 通過監聽信號能量強度 (RSSI) 來確定通信信道是否空閑。 – 隨機回退通過選取一個隨機數從競爭窗口 (CW) 中來避免沖突。 – 信息數據傳輸包括發送信息數據幀和接收確認幀 (ACK)。 – 使用二進制指數退避算法確定回退時間。

基於 Markov 鏈的 DCF 策略建模 – Bianchi 提出瞭一個基於 Markov 鏈的建模方法，用於評估 BSS 的吞吐。 – Bianchi 模型假設理想通信信道，並且隻有當兩個或更多的網絡節點同時發送時才會發生碰撞。 – 基於 Markov 鏈的方法可以計算網絡節點在每個虛擬時隙的發送概率 τ 和碰撞概率 p。

2. 主要問題：

多 BSS 建模問題 – 隨著設備數量和網絡流量的增長，AP 的部署變得更為密集。 – 由於可用通信信道數有限，不同的 BSS 會復用相同的通信信道，這導致瞭同頻幹擾問題。 – 同頻幹擾是 WLAN 的一個重要問題，本題主要考慮這個問題。

兩 BSS 互聽 – 考慮瞭兩個 BSS 的互聽場景，主要是兩個 AP 向各自關聯的 STA 發送信息數據。 – 需要計算兩個 AP 並發時的信幹比 (SIR)。

隱藏網絡節點問題 – 隱藏網絡節點是指在一個網絡節點的通信區域內但在另一個網絡節點的通信區域外的網絡節點。 – 這可能導致兩個網絡節點同時發送信息數據，並在接收網絡節點處發生沖突。

3. 參數和模型：

• 附錄提供瞭隨機回退的詳細描述，展示瞭二進制指數退避的流程。
• Bianchi 模型使用二維 Markov 鏈來表示退避計數器和退避階數。
• 提供瞭通用的參數列表，包括 ACK 時長、SIFS 時長、DIFS 時長等。
• 為問題3和4提供瞭特定的參數，包括物理層速率、CWmin、CWmax 等。

分析：

難點：

1. WLAN 的分佈式通信信道接入和性能分析涉及多個復雜的參數和算法，如 Markov 鏈和二進制指數退避算法。

2. 必須考慮多個網絡節點之間的相互幹擾、通信信道復用、信幹比等問題。

3. 隱藏網絡節點問題增加瞭模型的復雜性，因為需要考慮網絡節點之間的相對位置和信號強度。

4. 必須合理選擇和調整參數，如競爭窗口大小、最大重傳次數等，以優化 WLAN 的性能。

建模方案：

1. 使用 Bianchi 的 Markov 鏈模型作為基礎，考慮多網絡節點、多 BSS 和隱藏網絡節點的影響。

2. 根據提供的參數列表，設置和調整模型中的各個參數。

3. 使用二維 Markov 鏈來模擬網絡節點的退避計數器和退避階數。

4. 考慮通信信道復用和同頻幹擾的影響，計算各個網絡節點的發送和接收概率。

5. 根據模型的結果，評估 WLAN 的吞吐、延遲和其他性能指標。

綜上所述，這是一個涉及 WLAN 分佈式通信信道接入的復雜數學建模問題，需要考慮多個參數和算法，以及多網絡節點、多 BSS 和隱藏網絡節點的影響。通過合理的建模和參數調整，可以優化 WLAN 的性能。

1. 公式整理

1. 退避器的階數和隨機回退數的公式:

W_i = begin{cases} 2^i W_0 & text{if } 0 leq i leq m \ 2^m W_0 & text{if } m leq i leq r end{cases} 這裡的 W_i 表示退避窗口的大小，其中 i 是信息數據的發送次數（也稱為階數），r 是最大重傳次數，m 是最大退避階數。

2. Markov chain的一步狀態轉移概率公式:

P_{i,k,i,k+1} = 1 quad text{for } k in [0, W_i – 2] text{ and } i in [0, r] P_{0,k,i,0} = frac{1-p}{W_0} quad text{for } k in [0, W_0 – 1] text{ and } i in [0, r] P_{i,k,i-1,0} = frac{p}{W_i} quad text{for } k in [0, W_i – 1] text{ and } i in [1, r] P_{0,k|r,0} = frac{1}{W_0} quad text{for } k in [0, W_0 – 1] 這裡的 P_{i,k,j,l} 表示從狀態 i,k 轉移到狀態 j,l 的概率。

3. Markov chain的穩態解公式:

b_{i,0} = begin{cases} frac{2(1-p)}{1-2p(1-p^{r+1}) + W_0(1-p)(1-2p^{r+1})} & text{if } r leq m \ frac{2(1-p)W_0}{1-2p + (1-p^{m+1})(1-2p) + W_0(1-p)(1-2p^{r-m+1})} & text{if } m < r end{cases} 這裡的 b_{i,0} 表示二維Markov chain的穩態解。

4. 網絡節點在一個時隙發送信息數據幀的概率公式:

tau = b_{0,0} times frac{1-p^{r+1}}{1-p} 這裡的 tau 表示網絡節點在一個時隙發送信息數據幀的概率。

5. 某個時隙發生碰撞的概率公式:

p = 1 – (1-tau)^{N-1} 這裡的 p 表示在某個時隙發生碰撞的概率，N 是網絡節點數。

這些公式為WLAN網絡通信信道接入策略的建模提供瞭數學基礎，涉及二進制指數退避算法、Markov鏈的一步狀態轉移概率和穩態解等方面。

6. 隨機回退

隨機回退采用二進制指數退避算法來確定回退時間。核心概念包括：

• CW 的初始值為 CW_{text{min}} 。
• 每次信息數據傳輸失敗後， CW 會翻倍。
• 當 CW 達到 CW_{text{max}} 時，它保持不變。
• 每次信息數據成功傳輸後， CW 會重置。
• 如果連續失敗的重傳次數達到 r ，信息數據幀會被丟棄，並且 CW 會重置。

7. Bianchi模型

這是一個為IEEE 802.11協議提供分析的模型。核心公式包括：

競爭窗口 (CW) 的定義：

begin{align*} W_i &= 2^i W_0 quad &text{for } 0 leq i leq m \ W_i &= 2^m W_0 quad &text{for } m leq i leq r \ end{align*}

其中，i 表示信息數據的發送次數，或稱為階數；r 是最大重傳次數；m 是最大退避階數。

Markov 鏈的一步狀態轉移概率：

begin{align*} P_{i,k}^{i,k+1} &= 1 quad &text{for } k in [0,W_i-2], i in [0,r] \ P_{0,k}^{i,0} &= frac{1-p}{W_0} quad &text{for } k in [0,W_0-1], i in [0,r] \ P_{i,k}^{i-1,0} &= frac{p}{W_i} quad &text{for } k in [0,W_i-1], i in [1,r] \ P_{0,k}^{r,0} &= frac{1}{W_0} quad &text{for } k in [0,W_0-1] end{align*}

退避計數器的狀態轉移：

b_{i,0} = p^i cdot b_{0,0} quad text{for } 0 < i leq r

任意狀態 b_{i,k} 的表達式：

b_{i,k} = frac{W_i-k}{W_i} cdot b_{i,0} quad text{for } 0 leq i leq r, 0 leq k leq W_i-1

所有穩態概率之和：

1 = sum_{i=0}^{r} b_{i,0} cdot frac{W_i+1}{2}

b_{0,0} 的表達式：

begin{cases} b_{0,0} = frac{2(1-p)}{1-2p(1-p^{r+1})+W_0(1-p)(1-2p^r)} & text{for } r leq m \ b_{0,0} = frac{2(1-p)}{1-2pW_0(1-2p^m)+2^m(1-p)(1-2p^r)} & text{for } m < r end{cases}

網絡節點在一個時隙發送信息數據幀的概率：

tau = b_{0,0} cdot frac{1-p^{r+1}}{1-p}

條件碰撞概率：

p = 1 – (1-tau)^{N-1}

這些公式為我們提供瞭一個描述 CSMA/CA 協議性能的框架。在給定的網絡和流量條件下，可以使用這些公式來計算網絡的吞吐量、延遲等關鍵性能指標。

8. 隱藏網絡節點問題

隱藏網絡節點是當一個網絡節點位於其他網絡節點的通信范圍之外但仍在目標接收網絡節點的通信范圍內的情況。這可能導致信息數據傳輸的沖突。

9. 發包時長計算公式

給定物理層的頭、MAC頭和有效載荷的長度，信息數據幀的傳輸時間可以使用以下公式計算： t = t_{text{phy}} + t_{text{mac header}} + t_{text{payload}} = t_{text{phy}} + frac{L_{text{mac header+payload}}}{text{rate}}

這些公式為IEEE 802.11 WLAN的通信信道接入策略提供瞭數學描述，並通過Bianchi模型為性能分析提供瞭基礎。

問題1的分析、建模和求解

假設AP發送包的載荷長度為1500Bytes（1Bytes = 8bits），PHY頭時長為13.6μs，MAC頭為30Bytes，MAC頭和有效載荷采用物理層速率455.8Mbps發送。AP之間的RSSI為-70dBm。大部分時候隻有一個AP能夠接入通信信道，信息數據傳輸一定成功。當兩個AP同時回退到0而同時發送信息數據時，存在同頻幹擾。假設並發時的SIR較低，導致兩個AP的信息數據傳輸都失敗。請對該2 BSS系統進行建模，用數值分析方法求解，評估系統的吞吐。（參數參考附錄4，可編寫仿真器驗證模型精確度）

這是一個復雜的問題，所以讓我們分步驟進行。首先，我們需要建立模型，然後求解，最後可以使用仿真進行驗證。

1. 模型建立

a. 單個AP的信息數據幀傳輸時間計算

首先，計算單個AP發送信息數據幀的時間。根據題目中的信息數據和“發包時長計算公式”，我們有： t = t_{text{phy}} + frac{L_{text{mac header+payload}}}{text{rate}} t = 13.6mu s + frac{30 times 8 + 1500 times 8}{455.8 times 10^6}

b. 退避時間計算

使用二進制指數退避算法，初始退避時間是在 [0, CW_min-1] 范圍內隨機選擇的。每次傳輸失敗，CW 會翻倍，直到達到 CW_max。

c. 沖突概率

由於兩個AP可能同時退避到0並嘗試發送，我們需要計算這種沖突的概率。當沖突發生時，兩個AP都會因為低SIR而導致傳輸失敗。

d. 總吞吐計算

吞吐定義為單位時間內成功傳輸的信息數據量。考慮到DIFS、SIFS、ACK、退避和信息數據幀傳輸時間，我們可以計算總吞吐為： text{Throughput} = frac{text{Payload size}}{text{Total time for a successful transmission}}

2. 求解

現在，我們可以代入參數求解。

a. 單個AP的信息數據幀傳輸時間

t = 13.6mu s + frac{30 times 8 + 1500 times 8}{455.8 times 10^6}

b. 退避時間

在最壞的情況下，退避時間是 CW_max * SLOT_time。

c. 沖突概率

由於大部分時間隻有一個AP可以接入通信信道，沖突的可能性是低的。但是，當兩個AP都退避到0時，沖突的概率為1。

d. 總吞吐

text{Throughput} = frac{1500 times 8}{t + text{DIFS} + text{SIFS} + text{ACK} + text{退避時間}}

使用上面的公式和給定的參數，我們可以求解吞吐。

3. 吞吐量數值計算

為瞭驗證模型的準確性，我們可以編寫一個仿真程序，模擬兩個AP的信息數據傳輸流程，並記錄成功傳輸的信息數據量和時間，從而計算吞吐，並與模型預測的結果進行比較。

現在，讓我們計算吞吐。