2023 “华为杯”研赛A题，建模解析，小鹿学长带队指引全代码文章与思路

小鹿学长联合20多位国二以上的好队友，共同提供了进阶版精华包呀，有兴趣的同学可以点击下面链接看看～～
link：（进阶版）2023 研赛A题，华为杯建模解析，小鹿学长带队指引全代码文章与思路
我是小鹿学长，就读于上海交通大学，截至目前已经帮200+人完成了建模与思路的构建的处理了～

## 题目重述

1. 当多个BSS共享同一个信道时,存在同频干扰问题。给出两个BSS互听的场景,要求对不同的SIR情况建模求解系统吞吐。

2. 当BSS不互听时会产生隐藏节点问题。给出两个BSS不互听的场景,要求建模求解系统吞吐,考虑信道质量导致的丢包率。

3. 给出三BSS的场景,其中两个BSS不互听,要求建模求解系统吞吐。

## 问题一
好的,我给出问题1的建模思路和关键公式:

1. 建立退避过程的二维Markov链模型。状态空间为{s(t),b(t)},s(t)表示退避阶数,b(t)表示退避计数器值。一步转移概率如Bianchi模型。

2. 求解Markov稳态分布$b_{i,k}$

首先考虑从状态$b_{i-1,0}$转移到$b_{i,0}$的步长:

- $b_{i-1,0}\to b_{i,0}$  
- $b_{i-1,0}\to b_{i,1}\to b_{i,0}$ 
- ...
- $b_{i-1,0}\to b_{i,W_i-1}\to...\to b_{i,1}\to b_{i,0}$

因为从$b_{i-1,0}$到$b_{i,0}$的转移概率是$p/W_i$,所以上面$W_i$种步长的概率求和为:

$b_{i,0} = b_{i-1,0} \cdot (p/W_i + p/W_i + ... + p/W_i) = p \cdot b_{i-1,0}$

同理,从成功状态转移到$b_{0,k}$的步长有$r+1$种,每种的概率是$(1-p)/W_0$,求和可得:

$b_{0,k} = (1-p) \cdot \sum\limits_{j=0}^{r}b_{j,0} \cdot \dfrac{W_0-k}{W_0}$

综合两种情况,可以得到$b_{i,k}$的表达。

3. 求解碰撞概率$p$

碰撞发生的条件是至少有2个节点在同一时隙传输,假设总节点数是$N$,单个节点传输概率为$\tau$,则$p$可表示为:

$p = 1 - P(\text{均不传输}) = 1 - (1-\tau)^{N-1}$

其中节点传输概率$\tau$可以用稳态概率表示:

$\tau = \sum\limits_{i=0}^{r}b_{i,0}$

4. 将$p$和$\tau$联立求解。

5. 根据节点处于三种状态(成功、碰撞、空闲)的稳态概率,计算吞吐量公式。

```python
import numpy as np

# 模型参数
N = 50 # 总节点数 
W0 = 16 # 最小竞争窗口大小
Wm = 1024 # 最大竞争窗口大小
r = 6 # 最大重传次数
phy_rate = 455.8e6 # 物理层速率 

header = 30 # MAC帧头长度
phy_header = 13.6e-6 # PHY帧头时长
SIFS = 16e-6 # SIFS时隙时长
DIFS = 43e-6 # DIFS时隙时长  
ACK = 32e-6 # ACK帧时长
slotTime = 9e-6 # slot时长
ACKTimeout = 65e-6 # ACK超时时长

payload = 1500*8 # 数据帧载荷长度

# 初始化
p = 0.1  
m = int(np.log2(Wm/W0))
b00 = 2*(1-p)*(1-2*p)/((1-2*p)*(1-p**(r+1)) + W0*(1-p)*(1-(2*p)**(r+1)))
tau = b00*(1-p**(r+1))/(1-p)

```

## 问题二
问题2的建模思路与公式如下:

1. 同样建立二维Markov链模型,状态空间为{s(t), b(t)}。

2. 求解Markov稳态分布$b_{i,k}$

从状态$b_{i-1,0}$转移到$b_{i,0}$的步长共有$W_i$种,每种步长的概率都是$p/W_i$,求和可得:

$b_{i,0} = b_{i-1,0} \cdot (p/W_i + p/W_i + ... + p/W_i) = p \cdot b_{i-1,0}$

从成功状态转移到$b_{0,k}$的步长有$r+1$种,每种步长概率是$(1-p)/W_0$,求和可得:  

$b_{0,k} = (1-p) \cdot \sum\limits_{j=0}^{r} b_{j,0} \cdot \dfrac{W_0-k}{W_0}$

综合两种情况,可以得到$b_{i,k}$的表达:

$b_{i,k}=\begin{cases}
p\cdot b_{i-1,0}\cdot \dfrac{W_i-k}{W_i}, & 0<i<r\\
(1-p)\cdot \dfrac{W_i-k}{W_i}\cdot \sum\limits_{j=0}^{r}b_{j,0}, & i=0
\end{cases}$

3. 求解碰撞概率$p$ 

单节点传输概率$\tau$由稳态概率求和:

$\tau = \sum\limits_{i=0}^{r} b_{i,0}$

$N$个节点同时传输概率,需要扣除成功并发传输的概率:

$p = 1 - P(\text{均不传输}) - P(\text{成功并发})$ 

展开可得$p$的表达式。

请您检查我的详细推导,提出修改意见。非常感谢您的耐心指导!

4. 与问题1不同的是,这里考虑了高SIR导致并发传输成功的情况。

定义$P_s$为并发传输成功概率。

则碰撞概率修正为:

$$p = 1 - (1-\tau)^{N-1} - C_N^2 \tau^2 P_s(1-\tau)^{N-2}$$

5. 求解吞吐量时,并发传输成功的情况需单独计算时长。

```python
import numpy as np

# 模型参数
N = 50  
W0 = 32
Wm = 1024
r = 5
phy_rate = 275.3e6

header = 30  
phy_header = 13.6e-6
SIFS = 16e-6
DIFS = 43e-6
ACK = 32e-6
slotTime = 9e-6
ACKTimeout = 65e-6

payload = 1500*8  

# 初始化
p = 0.1  
m = int(np.log2(Wm/W0))

def get_b00(W0, Wm, r, p):
  if r <= m:
    numerator = 2*(1-p)*(1-2*p)
    denominator = (1-2*p)*(1-p**(r+1)) + W0*(1-p)*(1-(2*p)**(r+1))
```