2023 “华为杯” 中国研究生数学建模竞赛（A题）深度剖析|数学建模完整代码+建模过程全解全析

状态空间为{s(t),b(t)},s(t)表示退避阶数,b(t)表示随机退避计数器值。1.计算碰撞概率p时,并发传输不一定失败,需要考虑SIR导致成功或失败的概率。节点退避过程的Markov链模型与问题1完全一致,状态空间和状态转移概率也不变。●τ表示节点随机退避到0时的发送概率,可以从Markov链的稳态分布得到。(1) 扩展为三状态Markov链,状态空间S={s1,s2,s3}明确定义三状态

qq_25834913

2702人浏览 · 2023-09-24 11:52:53

qq_25834913 · 2023-09-24 11:52:53 发布

让我们一起看看研赛的A题呀！

问题一：

1.使用Markov链描述节点的退避过程

●节点按照二进制指数增backoff算法进行随机退避,退避计数器和退避阶数呈Markov过程
●Bianchi等在论文中证明了这个退避过程可以用一个二维离散时间Markov链建模
●Markov链能准确描述节点退避状态随时间的概率分布和转移规律

2.计算节点发送概率τ和碰撞概率p

●τ表示节点随机退避到0时的发送概率,可以从Markov链的稳态分布得到
●p表示至少还有一个节点同时发送导致碰撞的概率,根据节点总数和τ的关系可求得
●两者互相关联,需要联立方程组求解

3.计算不同状态时隙长度

●时隙长度需要考虑数据传输时间、SIFS、ACK等不同因素
●不同状态(成功、失败、空闲)下时隙长度不同

4.利用状态概率和时隙长度计算吞吐率

吞吐率受状态概率和各状态时隙长度的影响
利用吞吐率公式可以计算出整个系统的性能
反映了Markov链建模、参数设定和性能度量之间的关系

建立节点退避过程的Markov链模型

参考Bianchi模型,对每个AP建立一个退避过程的Markov链模型。状态空间为{s(t),b(t)},s(t)表示退避阶数,b(t)表示随机退避计数器值。
一共有m+1个退避阶数,每个阶数i对应的竞争窗口大小为 $W_i=2^i*W_0$ , $W_0$ 为初始阶数的竞争窗口大小。
那么状态转移概率为:
$P{i,k|i,k-1}=1, i∈[0,m],k∈[1,Wi-1] P{0,k|i,0}=(1-p)/W0, i∈[0,m],k∈[0,W0-1] P{i,k|i-1,0}=p/Wi, i∈[1,m],k∈[0,Wi-1]$

计算节点发送概率τ和碰撞概率p

在稳态下,可以得到节点发送概率:
$τ=b_{00}/(1-p)$
其中b00为状态{0,0}的稳态概率。
碰撞概率p为至少还有一个节点发送的概率:
$p=1-(1-τ)^(N-1)$
将两个方程组合可以求解出τ和p。
计算不同状态的时隙长度

$T_s = 数据传输时间 + SIFS + ACK \ T_c = 数据传输时间 + ACK超时 \ T_e = DIFS$

计算系统吞吐率

$\frac{P_sT_s}{P_sT_s+P_cT_c+P_eT_e} \cdot$ 速率
其中Ps为成功概率,Pc为失败概率,Pe为空闲概率。
通过求解Markov链可以计算出这三个概率,从而求出系统吞吐率S。

matlab

% 参数设置
W0 = 16;   % 初始竞争窗口大小
m = 5;     % 最大退避级数 
N = 2;     % AP节点数量
p_col = 0.1; % 并发传输发生碰撞概率
Ts = 60;   % 成功传输时隙长度
Tc = 100;  % 失败传输时隙长度 
Te = 50;   % 空闲时隙长度
rate = 455.8e6; % 传输速率

% 求解τ和p
syms tau p;
b00 = (1-p)*(1-2*p)/(W0*(1-(2*p)^(m+1))*(1-p)+(1-2*p)*(1-p^(m+1))); 
tau = b00/(1-p);
eqn1 = tau == (1 - (1-tau)^(N-1))*p_col;
eqn2 = solve(eqn1,p);
p = double(eqn2);
tau = double(solve(eqn1,tau));

% 计算状态概率
Ps = 1 - tau^N;
Pc = 1 - (1-tau)^N - N*tau*(1-tau)^(N-1); 
Pe = (1-tau)^N;

% 计算吞吐率
S = Ps*Ts/(Ps*Ts + Pc*Tc + Pe*Te)*rate

在这里插入图片描述

问题二：

并发传输时SIR较高,导致两个AP的数据传输都能成功。
所以建模过程与问题1基本一致,主要差别在以下两个方面:
1.计算碰撞概率p时,并发传输不一定失败,需要考虑SIR导致成功或失败的概率。
可以设置一个并发成功概率Ps_col,则有:
$p = 1 - (1-τ)^(N-1) * Ps_col$
2.计算不同状态概率时,成功概率Ps需要考虑并发成功的情况:
$Ps = (1 - τ)^N + C_N^2 * tau^2 * Ps_col$
Pc和Pe的计算与问题1相同。
其余建模过程不变,最后可以求得问题2下的系统吞吐率。

则对应的建模过程为节点的Markov链模型
节点退避过程的Markov链模型与问题1完全一致,状态空间和状态转移概率也不变
计算节点发送概率 $\tau$ 和碰撞概率 $p$

$\tau = \frac{b_{0,0}}{1-p}\\ p= 1 - (1-\tau)^{N-1} \cdot P\text{scol}$

其中 $P\text{scol}$ 表示并发传输成功概率。
不同状态时隙长度

(与问题1相同)

计算状态概率
$P_e = (1-\tau)^N \ P_c = 1 - (1-\tau)^N - N\tau(1-\tau)^{N-1} \ P_s = (1 - \tau)^N + C_N^2 \tau^2 P\text{scol}$

计算系统吞吐率

吞吐率公式与问题1也完全一致。
与问题1相比,主要改变是:
1.p的计算考虑并发成功概率
2.Ps的计算增加并发成功概率项
在这里插入图片描述

则相应的计算代码为：

% 参数设置
W0 = 16; 
m = 5;
N = 2;
p_col = 0.9; % 并发传输成功概率 
Ts = 60;
Tc = 100;
Te = 50;
rate = 455.8e6;

% 求解τ和p
syms tau p;
b00 = (1-p)*(1-2*p)/(W0*(1-(2*p)^(m+1))*(1-p)+(1-2*p)*(1-p^(m+1)));
tau = b00/(1-p);
eqn1 = tau == (1 - (1-tau)^(N-1))*p_col;  
eqn2 = solve(eqn1,p);
p = double(eqn2);
tau = double(solve(eqn1,tau));

% 计算状态概率 
Ps_col = 0.9; % 并发成功概率
Pe = (1-tau)^N; 
Pc = 1 - (1-tau)^N - N*tau*(1-tau)^(N-1);
Ps = (1 - tau)^N + nchoosek(N,2)*tau^2*Ps_col;

% 计算吞吐率
S = Ps*Ts/(Ps*Ts + Pc*Tc + Pe*Te)*rate

问题3

问题3中,两个AP间RSSI为-90dBm,不互听,存在隐藏节点问题。并考虑了信道误码率Pe导致的传输失败。

建模步骤如下:
1.仍然建立节点的Markov链模型,描述退避过程。
2.计算节点发送概率τ和碰撞概率p。τ的计算与前两题相同
a.p考虑并发传输失败概率
3.计算不同状态时隙长度Ts、Tc、Te,与前两题相同。
4.计算状态概率:空闲概率Pe考虑信道误码率
a.失败概率Pc考虑交叠传输失败概率
b.成功概率Ps为剩余概率
5.利用上述参数计算系统吞吐率S
相比前两题,问题3建模的主要不同:
(1) 引入信道误码率Pe
(2) 失败概率Pc考虑交叠传输失败
(3) 成功概率Ps作为剩余概率

具体而言，相应的建模为：

1.节点的Markov链模型
(与前两题相同)
2.计算节点发送概率 $\tau$ 和碰撞概率 $p$

$\tau = \frac{b{0,0}}{1-p} \\ p = 1 - (1-\tau)^{N-1} \cdot P{c\text{col}}$

3.状态时隙长度
(与前两题相同)
4.计算状态概率
$P_e = (1-\tau)^N \cdot (1-P_{e\text{chan}}) \\ P_c = [1 - (1-\tau)^N - N\tau(1-\tau)^{N-1}] \cdot P_{c\text{over}} \\ P_s = 1 - P_e - P_c$

5.系统吞吐率
(与前两题相同)
其中,
$P_{e_\text{chan}}$ 表示信道误码率,
$P_{c_\text{over}}$ 表示交叠传输失败概率。
在这里插入图片描述

% 参数设置
W0 = 16;  
m = 5;
N = 2; 
p_col = 0.2; % 并发传输失败概率
pe_chan = 0.1; % 信道误码率
pc_over = 0.5; % 交叠传输失败概率
Ts = 60;
Tc = 100;
Te = 50;
rate = 455.8e6;

% 求解τ和p
syms tau p;
b00 = (1-p)*(1-2*p)/(W0*(1-(2*p)^(m+1))*(1-p)+(1-2*p)*(1-p^(m+1)));
tau = b00/(1-p);
eqn1 = tau == (1 - (1-tau)^(N-1))*p_col;
eqn2 = solve(eqn1,p);  
p = double(eqn2);
tau = double(solve(eqn1,tau));

% 计算状态概率
Pe = (1-tau)^N * (1-pe_chan);
Pc = (1 - (1-tau)^N - N*tau*(1-tau)^(N-1)) * pc_over;
Ps = 1 - Pe - Pc;

% 计算系统吞吐率
S = Ps*Ts/(Ps*Ts + Pc*Tc + Pe*Te)*rate

节点退避过程的Markov链建模与前两题相同,这是基础。
计算p时需要考虑并发传输失败概率 $Pc_col$ 。这里多引入一个参数描述交叠传输失败概率。
计算Pe时加入信道误码率 $Pe_chan$ ,反映信道质量导致的传输失败率。
计算Pc时加入交叠传输失败概率 $Pc_over$ ,反映交叠传输所致的失败率。
Ps作为剩余概率计算,保证状态概率和为1。
吞吐率公式形式不变,利用修改后的状态概率计算。

问题4

1.建立三状态Markov链,表示三个AP的传输状态。
2.计算状态间的转移概率:
●AP1和AP3不互听,同时传输的概率较大
●AP2与两者都互听,其传输机会较少
●考虑AP1和AP3先后发送导致失败的概率
3.计算每个状态的时隙长度:
●成功传输、失败传输、空闲时隙
4.利用状态概率和时隙长度计算系统吞吐率
问题4主要难点在于:
(1)建立三状态Markov链描述三个AP的传输
(2)计算复杂的状态间转移概率
(3)处理AP1和AP3先后发送的情况

明确定义三状态Markov链的状态含义,表示不同AP的传输情况。
状态转移概率的计算较为复杂,需要考虑不同AP间是否互听的情况。
AP1和AP3不互听可能同时发送,需考虑两者先后发送导致失败的概率。
AP2与两者均互听,其发送机会相对较少,转移概率需要合理设定。
计算状态时隙长度时,要区分成功发送、碰撞失败和空闲情况。
利用状态概率和时隙长度计算吞吐率公式与之前相同。
转移概率难以准确确定,可先做合理假设,并通过仿真调整参数。
理想化简化无法完全描述复杂无线信道,但可反映整体趋势。
实现过程可基于matlab编程,从简单场景逐步扩展复杂性。
可从二状态Markov链扩展到三状态Markov链,逐步添加细节。

1.定义三状态Markov链
状态空间: $S = \{s_1, s_2, s_3\}$
$s_1$ - 仅AP1发送
$s_2$ - 仅AP2发送
$s_3$ - AP1和AP3同时发送
2.状态转移概率
$\quad - \text{AP1发送后再发送概率} \\ P(s2|s1) \quad - \text{AP1结束后AP2发送概率}\\ P(s3|s1) \quad - \text{AP1结束后AP3也发送概率}\\ P(s1|s2) \quad - \text{AP2结束后AP1发送概率}\\ P(s2|s2) \quad - \text{AP2发送后再发送概率}\\ P(s3|s2) \quad - \text{AP2结束后AP3也发送概率}\\ P(s1|s3) \quad - \text{AP1和AP3结束后AP1再发送概率}\\ P(s2|s3) \quad - \text{AP1和AP3结束后AP2发送概率}\\ P(s3|s3) \quad - \text{AP1和AP3结束后两者再同时发送概率}$

3.时隙长度 $T_s$ , $T_c$ , $T_e$
4.利用以上参数计算吞吐率 $S$

在这里插入图片描述

% 参数设置
Ts = 60;    % 成功传输时隙长度
Tc = 100;   % 失败传输时隙长度  
Te = 50;    % 空闲时隙长度
rate = 455.8e6; 

% 状态转移概率矩阵
P = [0.7 0.2 0.1;   % P(s1|s1) P(s2|s1) P(s3|s1) 
     0.3 0.5 0.2;   % P(s1|s2) P(s2|s2) P(s3|s2)
     0.2 0.1 0.7];  % P(s1|s3) P(s2|s3) P(s3|s3)

% 平稳态概率  
pie = [0.4 0.3 0.3];  

% 计算吞吐率
Ps = pie(1); 
Pc = pie(2) + pie(3)*0.3;   % AP1和AP3先后发送失败概率为0.3
Pe = 1 - Ps - Pc;
S = Ps*Ts/(Ps*Ts + Pc*Tc + Pe*Te)*rate