2023年中国研究生数学建模竞赛（华为杯数学建模）A题 WLAN网络信道接入机制建模完整思路以及代码分享

2023年中国研究生数学建模竞赛A题（华为题目）

WLAN网络信道接入机制建模

1. 背景

无线局域网（WLAN, wireless local area network）也即Wi-Fi广泛使用，提供低成本、高吞吐和便利的无线通信服务。基本服务集（BSS, basic service set）是WLAN的基本组成部分。处于某一特定覆盖区域内的站点（STA, station）与一个专职管理BSS的无线接入点（AP, access point）组成一个BSS，称STA关联到AP。常见的AP有无线路由器、WiFi热点等，手机、笔记本、物联设备等是STA。AP给STA发送数据叫作下行方向，反之是上行方向，本文将AP和STA统称为节点，每个节点的发送和接收不能同时发生。各节点共享信道，通过载波侦听多址接入/退避（CSMA/CA, carrier sense multi-access and collision avoidance）的机制避免冲突，称为分布式协调功能（DCF, distributed coordination function）。

图1.1 WLAN网络

1.1 分布式信道接入和二进制指数退避

DCF机制提供了一种分布式、基于竞争的信道接入功能。可将每个节点接入信道进行数据传输的过程分为3个阶段，信道可用评估（CCA，clear channel assessment）、随机回退、数据传输。

（1）CCA：当一个节点打算发送时，首先进行一个固定时长的载波侦听，这个固定时长被称为DCF帧间距（DIFS，DCF inter-frame space），43μs。如果DIFS时段内接收到的信号能量强度（RSSI，received signal strength indication）低于CCA门限（-82dBm），判断信道为空闲，否则，判断信道为繁忙。

（2）随机回退：信道空闲时，可能有多个节点准备好了数据，为避免碰撞，节点从[0, CW-1]的均匀分布选取一个随机数作为回退数，等待该回退数个时隙长度slotTime（9μs），随机回退时段时长为回退数乘以slotTime。CW被称为竞争窗口（contention window）。如果信道在随机回退时段保持空闲，则节点开始一次数据传输。在随机回退时段节点持续监听信道，如果期间信道变繁忙，则节点将回退暂停，直到信道在一个DIFS时长重新变为空闲，再继续前面没有回退完的时间。

（3）数据传输：回退到0的节点发送一个数据帧，接收节点成功接收到数据之后等待短帧帧间距（SIFS, Short inter-frame space）16μs后，回复ACK确认帧（32μs）。如果发送节点收到ACK，则数据发送成功。如果发送数据帧没有被接收节点成功接收，或者ACK发送失败，或者ACK没有被发送节点收到，则数据传输失败，发送节点需要在等待超时后重传数据。等待超时时间ACKTimeout为65μs。

随机回退采用二进制指数退避算法确定回退时间。CW的初始值为CWmin，每次数据传输失败后重传数据帧时，CW翻倍。如果CW达到了CWmax，则保持此值，直到被重置为止。每次数据传输成功时CW重置，开始下一个数据帧的回退。若传输连续失败，重传次数达到r后，数据帧被丢弃，CW重置传输下一个数据帧。可见，重传r次时，无论成功还是失败，CW都会重置。

1.2 基于Markov chain的DCF机制建模和系统性能分析

对于单BSS，N个STA给AP发送上行数据，Bianchi（1998）最早基于Markov chain建模。Bianchi模型假设理想信道，不因信道质量差而丢包。当2个及以上节点同时回退到0发送数据时，由于碰撞而丢包。那么信道可能处于三种状态：空闲、成功传输、碰撞，如图1.2所示。将每个状态看作一个虚拟时隙，那么信道在三种虚拟时隙中转化。将退避器所处的阶数和随机回退数用二维Markov chain表示，推导节点在每个虚拟时隙的发送概率τ和发生碰撞的条件概率p，从而评估BSS的吞吐[1]。

图1.2 信道状态

Bianchi模型获得了很高的精确度，很多工作在此基础上扩展，Chatzimisios（2002）研究了有最大重传次数限制的媒体接入控制（MAC，medium access control）层性能情况[2]。Huang和Ivan Marsic（2010）介绍了隐藏节点下网络模型和性能分析[3]。Chen（2007）分析了多速率MAC协议的性能[4]。基于Markov链求解τ和p的推导见附录和参考文献。吞吐是单位时间内发送数据有效载荷的比特数，单位bps。吞吐S可以由信道的利用率与物理层速率（单位bps）的乘积表示，

                  (1)

信道处于三种虚拟时隙的概率可由τ和p表示，空闲时隙的长度T**e是slotTime。成功传输和碰撞的传输时长T**s和T**c分别表示为

T**s = H + E[P] + SIFS + ACK + DIFS

T*c = H + E*[P] + DIFS + ACKTimeout* (2)

H为数据帧头，包括MAC层头和物理（PHY，physical）层头，E[P]为数据帧的有效载荷传输时长，E*[P]为发生冲突时较长数据帧的有效载荷传输时长，假设所有节点的数据帧长度一样，则E[P]与E*[P]相等。PHY头时长固定，MAC头和有效载荷的发送时长由其字节长度除以物理层速率得到。

2． WLAN组网中的多BSS建模问题

节点发送数据后，电磁波信号在自由空间中传播，随着距离的增加，能量衰减越严重。周围节点收到该信号后，根据RSSI是否高于CCA门限，判断信道为忙或闲。一个节点发出信号的RSSI高于CCA门限的区域叫作通信区域，位于该通信区域内的节点与该发送节点互听。随着设备数量、应用类型、网络流量的飞速增长，AP部署日趋高密，如企业办公、工厂、教育场景。如图2.2（a）所示，将信道号为36、44、52、60、149、157的六个信道分配给区域内12个BSS，由于可用信道数有限，不同的BSS复用同一个信道。同频AP（使用相同信道号的AP）之间通信区域存在重叠时，存在相互干扰问题，叫作同频干扰。同频干扰是WLAN组网最显著的干扰问题，本题不考虑异频干扰的情况。家庭或宿舍等单BSS场景中，STA距离AP较近，RSSI较强，互听，假设理想信道，不会因信道质量差而丢包，只有在2个及以上STA同时发送数据时导致碰撞而丢包。而在教学区等场景，同频多BSS场景的情况更复杂。

首先，并不是所有的节点之间都能互听。假定AP和STA的发射功率相同，由于节点间距离不同，信号衰减不同，因此RSSI不同。节点在DIFS时长侦听信号的RSSI > CCA门限时，节点才认为信道繁忙，否则认为信道空闲，启动随机回退，发送数据。其次，当有多个BSS的节点同时发送数据（叫作并发传输）时，其成功与否与信干比（SIR, signal to interference ratio）有关，若SIR足够高，则信号能被成功解调，若SIR很低，则信号解调失败。信干比是信号强度与干扰强度的比值，单位是dB，RSSI的单位是dBm，则SIR可以用信号RSSI与干扰信号RSSI的差值表示，本文中不考虑环境噪声。

发送节点间能否互听，并发传输时是否成功，是进行系统建模需要考虑的两个先决条件，前者决定了退避计数器能否回退，后者决定了一次并发传输是****成功还是失败，从而直接影响成功、失败和空闲三种状态之间的转换。

2.1 两BSS互听

考虑2个BSS互听的场景，仅下行，即两个AP分别向各自关联的STA发送数据，如图2.2（b）所示。以AP1->STA1方向的数据传输为例，其会受到相邻BSS2的干扰，对于STA1来说，AP1->STA1是信号，AP2->STA1是干扰。对于AP2->STA2情况类似。假设ACK一定能发送成功。根据节点之间的RSSI估算两个AP并发时的SIR，考虑不同的情景进行建模。

问题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，可编写仿真器验证模型精确度）

解答：

为了解决此问题，我们需要构建一个二维Markov链模型，考虑退避窗口大小和退避计数器数值，然后利用该模型计算出信道的利用率和系统的吞吐率。在此过程中，我们将遵循与Bianchi模型相似的步骤，但会做出一些调整以考虑到两个AP可能发生的干扰。

1. 二维Markov链模型：

考虑b[i,j]作为在第i次重试，退避计数器为j时，一个AP的概率。其中，0≤i≤r 和 0≤j≤CWmin​×2i−1。其中r是最大的重传次数。

转移概率:

• 从i,j到i,j−1: 当信道是空闲的时候，每个时间槽，退避计数器减一。
• 从i,0到i−1,CW: 当一个AP试图传输但另一个AP也正在传输，导致冲突。

1. 求解发送概率τ: 对于一个AP，尝试发送的概率为: τ=∑i=0r​b[i,0]
2. 求解冲突概率p: 当两个AP都试图发送时，它们之间会发生冲突。这可以表示为: p=2τ(1−τ)
3. 系统吞吐率: 设E[P]为有效载荷的传输时长，可以计算为: E[P]=(MAC_头+载荷长度)×8/物理层速率 成功的传输时间为: Ts=H+E[P]+SIFS+ACK+DIFS 与提供的数据，我们有： H=PHY_头+MAC_头=13.6μs+30Bytes×8bits/Byte/455.8Mbps

使用提供的参数值和上述方程式，我们可以计算Ts。冲突的传输时间Tc也可以使用类似的方式计算。

1. 信道的利用率: η=Ts+Pidle​×SLOT_时长+Ptr​×TcPtr​×Ts​

其中，���Ptr​是信道被使用的概率（两个AP中的一个正在尝试发送），而�����Pidle​是信道空闲的概率。

1. 吞吐率S: S=η×E[P]×物理层速率
2. 平衡方程与求解: 使用上述转移概率和边界条件，可以为每个i,j设置平衡方程。这组方程可以使用矩阵方法或迭代方法求解，从而得到b[i,j]的每个值。

最终，上述模型可以用来估算系统的吞吐率。此外，为了验证模型的精确度，可以编写仿真器来模拟整个过程并与理论值进行比较。

代码如下：完整件附录：

问题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的****交叠时，一定会导致本次传输的失败。

解答：

针对问题2，与问题1不同的是，当两个AP同时发送数据时，由于SIR较高，两个AP的数据传输都能成功。这意味着没有发生碰撞，从而系统的吞吐量将更高。

以下是针对该场景的数学模型：

1. 定义和假设

1. 数据包的载荷长度为 L=1500×8 bits，因为1Bytes = 8bits。
2. 物理层速率为 R=275.3 Mbps。
3. 一个数据帧的传输时间为: Tframe​=（L+MACheader​×8）/ R​ 其中 MACheader​=30 Bytes。
4. 一个完整的数据帧交换周期为: Tcycle​=Tframe​+SIFS+ACK+DIFS 其中 SIFS = 16μs, ACK = 32μs, DIFS = 43μs。
5. 当两个AP同时发送数据时，由于SIR较高，两个AP的数据传输都能成功，所以没有碰撞和重传。

2. 吞吐量的计算

系统吞吐量（S）定义为单位时间内成功传输的有效载荷位数。因此，对于该系统： S=T/cycle​L​

这里我们假设两个AP间的时间分配是公平的，即两者在等长的时间间隔内交替发送数据。因此，上述吞吐量应该是每个AP的吞吐量。如果你想知道整体系统的吞吐量，你应该乘以2。

问题3

假设AP间RSSI为-90dBm，AP发送包的载荷长度为1500Bytes，PHY头时长为13.6μs，MAC头为30Bytes，MAC头和载荷采用物理层速率455.8Mbps发送。Bianchi模型假设理想信道，实际上，无线传输环境是复杂多变的，当有遮挡物或者人走动时，无线信道都可能会快速发生比较大的变化。实测发现，当仅有一个AP发送数据时，即便不存在邻BSS干扰，也会有10%以内不同程度的丢包。假设因信道质量导致的丢包率。当两个AP发包在时间上有交叠时，假设SIR比较小，会导致两个AP的发包均失败。请对该2 BSS系统进行建模，尽量用数值分析方法求解，评估系统的吞吐。（参数参考附录4和6，可编写仿真器验证模型精确度）

解答：

问题****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，可编写仿真器验证模型精确度）解答：

完整思路以及源代码见附录：

附录：