802.11ax系统中基于传输延迟的多用户调度与资源分配算法

陈发堂 张志豪 李平安

（重庆邮电大学通信与信息工程学院，重庆 400065）

1 引言

基于802.11ax的无线局域网支持三种多用户传输方式：MU-MIMO、OFDMA 以及联合MU-MIMO 和OFDMA［1］，支持IEEE 802.11ax 标准的AP 可以同时向多个STA 提供无线连接，即上下行多用户传输，为了进一步提高IEEE 802.11ax网络性能，以满足用户对具有高吞吐、高服务质量及低延时等特点的高清直播、VR/AR等应用的传输需求［2］，最近部分研究集中在多用户传输上［3-4］。其中上行链路基于OFDMA 的多用户传输分为调度接入和随机接入［5］；在调度接入中，通常由AP 使用载波侦听多路访问/冲突避免机制竞争接入信道，然后在上行多用户调度中为各STA 分配带宽等资源［6］，同时要保证一帧传输中所有站点的传输时间相同，所以数据不足的用户需要传输空数据来填充帧持续时间，虽然该方案具有较强的抗重叠干扰能力和易于同步等优点［7-8］，但由于每组传输用户间数据量大小不一的问题也会导致系统吞吐量性能降低和设备能量浪费等问题［9］。因此，系统性能很大程度上取决于带宽和功率资源如何分配，以及调度策略中考虑的影响因素，比如各站点队列缓冲长度、信道状态、传输延迟等。

802.11ax 主要是为了在超密集的无线网络中提供高效的通信，在超密集设备部署场景下，由于大量的基站和海量接入站点，潜在的高数据包冲突率会严重降低WLAN 的通信效率，MAC 层的访问控制和资源分配是关注的主要问题，在基于随机接入的传输方式中，大量用户同时访问接入点造成较高的冲突率，因此需要限制同时访问的站点数量，而在基于调度接入的传输方式中，对于多用户同时访问的情况，需要进行用户分组和资源块的调度，以实现一定时间段内更多用户的传输和系统吞吐量的保证。802.11ax 系统中OFDMA 实现的特性使得调度和资源分配问题不同于移动蜂窝网络，在802.11ax 系统的多用户调度和资源分配方面，目前有学者做了部分研究，主要集中多用户接入性能分析优化和系统吞吐量的提升方面［10-11］。在［12］中，针对下行链路基于OFDMA 的多用户传输系统中最小吞吐量约束的资源调度问题，提出了一种基于加权最大最小公平性的调度策略，最大化了可实现吞吐量和约束吞吐量之间的最小比值。在［13］中，针对最大化系统吞吐量问题，将带宽内RU 分配给用户和用户组，提出了一种基于分治的调度算法，并且证明了该算法在松弛约束使得单用户分配到多个RU 的情况下是最优的；进而针对原优化问题，提出了一种基于贪婪和递归的算法有效地解决调度与资源分配（Schedule and Resource Allocation，SRA）问 题。在［14］中，针 对802.11ax 系统上行链路的RU 和功率控制联合分配问题，采用漂移加惩罚的方法提出了两种在平均功率约束下的最小延迟调度策略，达到了在各站点平均功率受限的情况下最小化站点排队数据包平均队列长度的目的。在［15］中，针对802.11ax 中基于OFDMA 调度接入的上行传输链路提出一种考虑优先级和缓冲数据的RU 分配调度算法，采用比例增益闭环反馈控制器，同时考虑了优先级和公平性，在网络密集的情况下，将服务质量信息与站点内的缓冲数据信息相结合，更有效地对数据流分配资源。在［16］中，针对OFDMA 系统中上行链路多用户传输资源调度问题，使用典型效用函数并加入新的约束条件，使得经典调度算法适应802.11ax 的新特性，对最大和速率、比例公平和最短剩余处理时间的优化问题提出优化调度算法。在［17］中，针对802.11ax 标准中基于OFDMA 的多用户MAC 框架提出调度算法，通过考虑带宽内资源块配置、网络节点的调制编码方案（Modulation and Code Scheme，MCS）级别和网络节点的流量负载来最大化整个网络的吞吐量。在［18］中，针对密集场景下多用户调度问题分析组内STA 数量与单位资源效率之间的函数关系，在此基础上提出了一种可变组大小的自适应STA 分组算法，提高了超密集无线网络中整个系统和每个STA 的BSR发送效率和吞吐量。在［3］中，针对802.11ax 网络多用户传输中有效利用上行信道的问题，提出一种基于传输延迟的用户调度和资源分配算法，根据可实现传输时间进行用户聚类，对具有相似传输延迟的用户分组在一个传输时隙里传输，避免传输帧里无效的数据填充，可以有效地利用信道进行UL-MU 传输。

综上所述，目前的研究主要集中在RU 的划分、分配组合及用户分组方面，在考虑系统和速率或者其他效用时没有把不同用户负载情况下的传输延迟作为影响因素，所以，本文考虑在其基础上优化帧填充和信道利用率，提出一种基于站点传输延迟的多用户调度和资源分配算法，以有效地提高信道利用率和平衡系统吞吐量性能。

2 系统模型

2.1 基于调度接入的上行多用户传输过程与资源分配指示

不同于移动蜂窝网络中的OFDMA 系统，在时域上划分帧，帧内划分时隙，时隙内划分符号，频域上划分资源块（Resource Block，RB）以构成时频资源，发送前将调制编码等处理后的数据映射到资源栅格内，接收端进行解资源映射，在指定的时频资源区域接收数据；802.11ax系统中AP 和STA 之间的数据传输是基于物理层协议数据单元（Physical layer Protocol Data Unit，PPDU）的，一次上下行传输的PPDU 里包含了多个用户的数据信息。另外，对于上行OFDMA 系统的接收端来说，因为各站点传输数据大小和无线链路的信道质量优劣，实际上很难做到严格意义的时间同步［6］，所以在上行多用户传输过程中，需要由AP 调度各个无线站点的数据发送。

上行链路中基于OFDMA 调度接入的过程是：AP竞争接入信道后获得一次传输机会，持续时间不定，请求待传输数据的各STA 上报BSR 和CSI信息，AP 调度上行多用户传输完成后使用触发帧（Trigger Frame，TF）帧下发资源指示信息，STA 根据TF帧中的指示在分配到的RU 上发送上行待传输数据，AP 接收到上行数据帧后用多用户块确认帧（Multiple Block Acknowledgement，MBA）统一对各站点进行确认回复［19］，如图1所示。

图1 中DIFS（Distributed Inter-Frame Spacing）为分布式帧间间隙，BSRP（Buffer Status Report Polling）为缓冲区状态报告轮询，是基于调度接入的上行多用户传输中接入点先发起传输的下行帧，各站点收到此帧后将信道状态信息和缓冲区状态信息上报给接入点；SIFS（Short Inter-Frame Space）为短帧间间隔，MU-BA 为站点回复的确认帧。由图1 可以看出，传输时间内数据长度不够的站点需要进行帧填充，造成时频资源浪费，所以，在调度接入模式下，一次传输时间内的传输效率和信道利用率等性能主要取决于AP 如何选择该轮传输的STA 和RU、功率等可用资源的分配。

AP 下发的触发帧中包含了调度和资源分配信息，有传输时长、带宽内RU 划分方式、STA/RU 匹配信息、MCS、空间流、发射功率等指示信息［20］。图2显示了在触发帧的HE-SIGB 字段中用户区域的资源分配指示，包括带宽内RU 划分和调度用户编号及其他指示信息。

上行多用户传输中还支持基于OFDMA 的随机接入（Uplink OFDMA Random Access，UORA），该方式具有信令开销低、无需上报传输要求和认证关联后即可接入信道等优点，但是UORA 机制并没有考虑到用户的满意度［21］；并且使用该方式的前提是在每次下发的TF 帧指示中存在供STA 随机接入的资源单元（Random Access Resource Unit，RA-RU），如果没有就不支持此方式，严格按照调度接入方式传输，所以下文在上行接入时只考虑基于调度接入方式的多用户传输。

2.2 基于传输延迟的OFDMA 系统上行链路传输模型

本文研究基于OFDMA 的单服务组上行链路传输中用户调度和资源分配问题。考虑在IEEE 802.11ax 网络中UL-MU 传输场景，其中AP 同时接收来自多个站点的上行信号，当基本服务组（Basic service set，BSS）中AP 成功竞争到信道获得传输机会（Transmit opportunity，TXOP）后，该AP 调度BSS内的STA 进行上行（Up link，UL）或下行（Down link，DL）多用户传输［22］，如果在一帧内不能调度完所有STA，则在TXOP Limit 时长内，进行连续多帧传输，TXOP 时间内每帧传输的持续时长是动态调整的，由AP 执行完调度后根据每组用户的传输延迟决定。

上行传输链路模型为BSS 内有K个用户，假设信道总带宽B划分为N个RU，每个子信道n∈{1，2，…，N}的带宽为W，且有W=B/N，802.11ax为了使调度多用户传输时更加灵活而支持不同大小RU 的组合划分，设每个RU 由S个子载波组成，由于不同大小RU 里导频子载波数量不一致，所以用于传数据的子载波也不一样。假设一次TXOP内传输M帧数据，由于每次调度传输前能通过各STA 上报的CSI 获得所有用户设备到接入点的信道状态信息，结合指示用户分配的功率值pk，n及资源块分配指示值αk，n，可以计算出传输帧m内用户k在资源块n上可实现的数据传输速率为［23］

其中Ns为资源块中用于传数据子载波的数量，hk，n，s为信道频率响应，αk，n，s(m)为指示m帧内RUn的子载波s是否分配给用户k的变量，β表示香农容量与实际速率之间的速率差距，取值范围为：0 ＜β＜1，根据标准一般取值为0.5［24］，pk，n，s(m)为AP 指 示STA 的发射功率，记表示用户k在RUn的子载波s上的信道增益。

由于在频域资源分配和指示调制编码方案时是以RU 为单位的，同一RU 内采用相同的调制编码方式［20］，所以，可以认为：

那么，用户k对应的传输速率为：

由于AP 可以获得各STA 的缓冲区状态，每个用户维护一个单独的队列，数据包的大小是一个随机的到达过程，这个过程在用户和传输帧之间是独立的［7］，设Ak(m)表示用户k，k∈(1，2…K)在传输帧m内到达的数据包大小，Qk(m)为用户k当前队列长度，Rk(m)为用户k的传输速率，Ttx(m)为帧传输时长。下一轮待传输的数据量为［25］：

可以计算每个站点传输数据需要的时间，记为传输延迟：

同时，系统吞吐量可以定义为：

其中qk(m)表示站点k在传输时间Ttx(m)内的传输数据量。

定义每帧传输的信道利用率为：

其中ηdata为传输组信道利用率，即帧传输时间内用作数据传输的时间与总时间的比值，ηpad为填充效率，即填充部分与总传输时间的比值。

由图1 可以看出，并非每个STA 发送给AP 的UL 数据帧都具有相同的传输时长，为了保证UL 多用户传输同时结束，那些UL 数据无法填满整个传输时长的STA 需要添加额外的填充，来保证各用户UL 传输时长相同［9］。由于帧填充部分对于接收端来说是无效信息，所以，根据传输延迟来进行用户分组调度对于优化帧填充是至关重要的，可以减少无效信息的发送，提升信道利用率。

3 用户分组及RU数量确定算法

在RU-STA 匹配之前，需要确定每帧传输中的站点集合及频域资源的划分方式，参照文献［3］中用户分组算法，确定在密集场景中每帧传输的用户分组，进一步对分组完成后每个用户组的组内RUSTA匹配和功率分配进行优化。

AP 和站点k之间的信道状态用gk(m)表示，进一步根据IEEE 802.11ax 中规定的MCS 计算站点的上行最大数据传输速率，根据映射函数和站点队列大小Qk计算出每个站点的上行传输延迟为在计算tk的基础上确定上行传输的每组站点，将需要相似传输时间的站点聚类在一起，以增加IEEE 802.11ax 网络UL-MU 传输的信道利用率。

C={{s1，s2…sk}|sk∈S}表示上行多用户传输的站点组合，Δt=|ti-tj|，si≠sj∈C，表示每一组中任意两个站点的传输延迟差，需要使得分组完成后组内所有站点的最大传输延时最小化，表述为问题（8）：

其中NAP表示一个AP 支持的最大连接数，ti，tj为同一组站点的传输延迟，由此提出下面用户分组算法：

通过求解上述问题，可以将传输延迟相近的站点组合在一起，上述优化问题的求解可以重复执行，直到网络中所有站点都分成不同的组，分组完成的结果用集合C'={C1，C2…}表示。

进一步需要确定频域资源划分方式，本文不考虑用户优先级，所有站点业务类型相同，所以假设带宽内RU 的大小一致，考虑带宽平均分配的情况，针对分组完成的每个用户组，给出每组中每帧传输的RU 数量确定算法，其中Nn表示RU 由n个子载波组成时，给定带宽可以划分的RU数量。

通过上述算法可以确定该帧传输过程中RU 数量，站点分组和RU 划分完成之后，需要在帧传输时间内将RU 分配给该组站点，最小化帧填充比例，提高信道利用率。

4 RU-STA匹配算法

分组完成后对RU 和STA 的匹配过程及每帧传输用户的功率进行优化，考虑将带宽平均划分为等大小RU 的情况，实际上802.11ax 支持不同大小RU的组合划分，考虑最基本的划分方式使得所提算法容易扩展到其他不同带宽的场景中。

设G(m)={{k…}；{n…}|k∈K，n∈N}为传输帧m内传输的用户组和RU 的匹配集合，TG(m)=|Tk1，n1-Tk2，n2|为同一传输帧的用户集合里任意两用户的传输时延差，其中k1 ≠k2；n1 ≠n2 ∈G(m)。根据文献［9］中定理：对于任意一组站点k∈K={1，2…K}，每帧的传输时长Ts(m)满足TG-min(m) ≤Ts(m) ≤TG-max(m)，针对给定的Qk(m)和Rk(m)，使得Dsys最大化的最优传输时长和TG-min(m)是等价的［9］。即每组传输时长以组内最短传输时长为准，这样每组用户不存在无效填充内容，但显然不利于组内其他用户传输和动态调整传输帧持续时长。

所以，要达到最大化信道利用率的目的，就要使得RU-STA 匹配后组内用户间的传输延迟差最小化，即优化问题为：

约束条件为：

C3：TG(m)=|Tk1，n1-Tk2，n2|，k1 ≠k2，n1 ≠n2 ∈G(m)其中约束条件C1 表示带宽内任何一个资源单元最多被分配给一个用户，也就是在基于OFDMA 的多用户传输中，多个用户不能复用一个资源单元，C2表示指示给每个用户的发送功率值不能超过其最大功率限制，C3 中TG(m)表示传输帧m内用户集合中任意两用户的传输时延差，并且不同用户占用的是不同的资源单元，不会出现计算同一用户在不同资源块上的传输延迟差或者同一资源块上不同用户的传输延迟差。

针对上述问题，提出RU-STA 匹配算法，具体步骤如下：

（1）记用户集合为U，随机生成用户位置Pk，计算路径损耗PLk，信道衰落，得到信道增益矩阵G[k*n]，计算传输速率Rk。

（2）各用户随机生成一定大小的传输队列Qk。

（3）计算集合中每个用户在不同RU 上的传输延迟T[k*n]。

（4）求解问题（9）得到用户站点配对集合Ui，查找Ui内传输时间最长的Ti-max，计算Ti-max-Tk为站点k的帧填充时长。

（5）计算子用户组内的传输效率ηdata，ηpad。

（6）直到用户集合为空时，算法结束，得到匹配完成的集合。

在上述算法步骤（4）中，求解问题（9）是找到一组匹配结果使得用户间传输延迟差最小，等价于求解在m·n维的矩阵中找出不同行不同列的方差最小的一组值，即：

针对此问题，利用穷举搜索法的复杂度较高，对于m·n维的矩阵，需要穷举[min(m，n)]!次，针对RU 数量或站点较多的场景并不适用，所以提出一种复杂度低，同时可以求得近似全局最优解的算法。

上述算法中，根据每组的传输延迟矩阵进行匹配，每组第一个用户选择传输延迟大小居中的RU，接下来依次遍历每个用户，每一轮用户选择与上一轮传输延迟相差最小但不重复的RU，直到组内所有用户与RU 完成匹配，得到一组传输延迟值，以组内最大传输延迟为基准，其他用户均需要进行帧填充，从而计算每一组用户的帧填充效率。

5 功率控制算法

在用户分组算法中，可以得到TXOP 内每次传输的子用户组，进而根据匹配算法得到RU 与STA的匹配信息和用户组的传输延迟，在每组用户中，传输时间小于组内最大传输时间Ti-max的用户要进行填帧填充，所以我们可以在功率分配阶段进行优化，进一步减小用户帧填充的比例，问题描述为：

约束条件为：

其中C1 表示每个用户的发射功率小于功率限制，C2 表示组内在功率分配阶段优化后的传输时间要小于组内最大传输时间。

上述目标函数中分母TG(m)max在匹配完成时是固定值，要最小化帧填充效率，就要使得分子中TG(m)max-Tk的值最小化，即每个用户的传输延迟无限接近组内最大传输延迟值，但是，这样使得每帧的持续时长增大，并且降低系统吞吐量，因为对于固定大小数据包，增大传输时长意味着传输速率降低；显然以最大传输延迟为指标是不合适的，所以在一定范围内通过调整发射功率值，提高传输速率，使得传输延迟较大的用户的传输时长向传输延迟较小的用户靠近。

针对上述问题，提出功率分配算法，具体步骤如下：

（1）输入：匹配完成后每个子用户组Ui的用户编号和传输延迟向量Ti。

（2）遍历每一个用户组Ui中的传输延迟Tk(m)，执行下面步骤：

（3）如果用户Ui，k的传输时间大于组内最小传输时间，即Tk(m) ＞TG(m)min，并且发射功率小于最大功率限制pk(m) ≤Pk-max(m)，那么增加发射功率，使得Tk(m)=TG(m)min，此时得到优化后的发射功率

（5）当所有用户的功率优化完毕时得到该用户组新的传输延迟值，计算帧填充效率ηpad和系统吞吐量Dsys，算法结束。

（6）输出：优化后的发射功率和传输延迟。

6 仿真及结果分析

仿真条件为基本服务组内的站点均匀分布在半径为100 m 的圆内，STA 与AP 最小距离为1 m，站点之间最小距离为8 m，且各站点的业务类型相同，假设每个用户的数据在一帧内可以传输完成，分组传输时每组用户不存在重复情况，连续多帧传输时为同组同用户不断生成数据进行传输，仿真参数如表1。

表1 仿真参数表Tab.1 Simulation parameters

其中β表示香农容量与实际速率之间的速率差距，Ldata表示每轮传输的数据长度。在密集场景下20 MHz 带宽内每组用户为9 个，无线信道模型为独立的瑞利多径组成的频率选择性信道，每个多径分量呈现平坦衰落，且AP 与站点之间的信道状态在一个TXOP 内保持不变［14］；在连续多帧传输仿真中每次生成不同的信道增益矩阵，其中路径损耗模型为：

PL0为1 m 距离时的参考路径损耗，a为路径损耗指数［25］，dk为STA 与AP 之间的距离；平均分配功率情况下各用户发射功率为pk=0.3 W，每个用户最大发射功率约束设置为pk-max=0.5W，噪声功率谱密度N0=1.1565 × 10-8W/Hz，首轮传输用户数据包大小设置为1.5*108Bytes左右，速率比值β=0.5。

仿真参考算法为随机分配算法（Random Allocation，RA）、轮询算法（Round Robin，RR）［9］、最大速率匹配算法（Maximum Rate match，MR）［16，26］，本文算法为分组匹配算法（Grouping Matching，GM）、GM和功率优化算法（GM+Power Allocation，GMP），其中RA，RR，MR，GM 算法在没有执行功率优化的情况下都是假设所有站点的功率平均分配，即所有站点的初始发射功率相同。

图4中每组从左到右的不同柱分别对应标识中从上到下的标识；显示了在密集场景中需要分组的情况下连续多组传输中每组的信道利用率。可以看出在每组中GM 算法和GMP 算法的信道利用率值都高于参考算法，RA 和RR 算法由于没有参考每个用户的传输延迟情况，所以表现出较大的随机性，MR 算法选取传输延迟较小的匹配方案使得信道利用率有所提升；并且本文算法在分组完成后连续多组中的性能没有出现较大波动。

图5 显示了分组完成后经过RU-STA 匹配和功率控制的一组用户中每个用户的数据帧传输效率，即每个用户数据传输时长占总时长的比例。可以看出随机分配算法和轮询算法中由于带宽内不同频段上信道状态相差较大，所以每个用户的填充效率有很大波动，组内用户间差距较大，而本文算法根据传输延迟经过匹配后，每个用户的填充效率有较大提升的同时组内用户间也具有更大稳定性；经过功率分配后帧填充效率得到进一步提升。

图6 显示了分组完成后经过RU-STA 匹配和功率控制的一组用户中每个用户的数据传输速率。可以看出多次生成不同数据和信道状态条件下的仿真结果，统一表现为MR 算法根据用户侧信道增益矩阵选择信道状态最好的RU，优先选择的用户传输速率较大，导致组内后选择的用户传输速率的降低；RA 和RR 算法组内用户间传输速率波动情况明显，不同用户的速率差较大。本文算法与参考算法相比，虽然部分用户的传输速率有所降低，但组内每个用户的传输速率稳定在固定区间内，从整个系统来看，在提升了信道利用率的情况下并没有造成系统吞吐量的降低，并且保证了每个用户传输速率的稳定性。

图7 显示了连续200 帧传输过程中，一组用户在每一传输帧中的信道利用率随着帧数量增加的变化趋势，其中每个点是连续十帧取均值的结果。可以看出本文算法和Max Rate 算法都保持了长期稳定性，而RA 和RR 算法在不同时期的信道利用率波动较大；从信道利用率的大小来看，本文GM 算法和GMP 算法相比参考MR 算法有10%的提升，相比RA 和RR 算法有15%左右的提升。另外，在使每组传输的平均时延最小化的同时，图5 中分析信道利用率（数据部分传输占用时长/总传输时长）时，就是分析无效数据填充部分传输时长占总数据传输时长的变化，因此，信道利用率的提高就意味着每组无效填充部分的减小，进而每组平均传输时长减小，导致在一定时间长度的传输机会内，可以完成更多帧数据的传输，也就是系统时延不断减小。

7 结论

本文结合BSR 和CSI 信息对802.11ax 系统中上行链路多用户传输进行用户分组，进而针对每组用户基于传输延迟提出RU-STA 匹配算法，可有效降低每帧传输过程中无效信息的填充，在功率分配阶段，以最大化信道利用率为目标，同时考虑系统吞吐量，对每个用户的发射功率进行优化，在功率限制范围内提高了信道利用率的同时保证组内用户传输速率的均衡。仿真表明，本文算法与参考算法相比，连续多帧传输情况下信道利用率平均提升15%上下。所以，本文算法通过对上行多用户传输的帧填充进行优化，可以有效提升在帧填充效率和信道利用率方面的系统性能。

本研究结合802.11ax 标准，基于OFDMA 调度接入的多用户过程，给出每帧传输的调度结果，所以从流程上分析，本文算法是有条件应用在商用设备上或者无线电平台上测试的；从研究中所做出的假设条件分析，其中带宽划分为等大小的资源单元，这是最基本的划分方式，可容易扩展到协议中支持的其他不同大小资源块相互组合的划分方式，其中传输速率按照香农公式计算，在进行资源分配指示时，需要将其换算成不同速率对应的调制编码方案，其中仿真条件中各用户上行数据的长度设定在一定范围内，并且每个用户之间存在一定大小的差异，符合实际场景需求，综上所述，本文算法适合并且有条件应用在商用设备或者相关测试平台。