Scheduling_Channel_Access_Based_on_Target_Wake_Time_Mechanism_in_802.11ax_WLANs

一、基本信息

题目：Scheduling_Channel_Access_Based_on_Target_Wake_Time_Mechanism_in_802.11ax_WLANs

作者：Qinghua Chen Yi-Hua Zhu （Zhejiang University of Technology）

发布：IEEE Transaction On Wireless Communications(VOL.20,No.3March 2021)

背景：802.11无线局域网密集部署的趋势使得设计一个有效、高效的信道接入方案迫在眉睫。下一代无线局域网的IEE 802.11ax标准引入了OFDMA（正交频分多值），支持在RUs（多资源单位）的下行和上行多用户传输。

目的：将多用户传输与目标唤醒时间机制相结合，提出了基于TWT的调度信道接入（SCAT）方案。

结论：该方案在吞吐量、信道利用率和能量效率等方面均优于现有方案。

关键词： IEEE 802.11ax standard, WLANs, target wake time, orthogonal frequency division multiple access (OFDMA).

二、介绍

传统的电源管理：IEEE802.11引入的电源管理机制，允许不参与数据传输的基站（STAs）通过关闭收发器的电源，在省电模式（PSM）或休眠模式下运行。

TWT机制：IEEE802.11ah标准引入，大大改进了传统的电源管理。在此机制下，用户可以与AP协商TWT会话，在此期间，用户保持清醒状态来发送/接收数据。

广播TWT协议（broadcast TWT）：支持AP对一组用户共享的TWT会话进行调度，使得多个用户可以在每个TWT会话中通过不同的RUs同时向AP传输数据。

目标信标（Target beacon）：一种特殊类型的信标帧，用于通知STA使用了TWT协议。

单行的TWT和广播TWT包含一组通用的参数：TWT(STA在TWT会话中下一次唤醒的时间)、最小唤醒持续时间和TWT唤醒间隔时间。此外，广播协议使用下一个目标信标（NTB）和收听间隔（LI）参数。

​ 下图是AP和sta之间广播TWT协议操作的例子。

​ 协议包含如下参数：STA1的NTB1指向第二个信标，LI1 = 2；STA2的NTB2指向第四个信标，LI2 = 2；STA3的NTB3指向第六个信标，LI3= 3；所有STA1会在2、4、6醒来，STA2会在4、6、8醒来，STA3会在6、9、12醒来。

​ 如图所示，STA1在第二个信标被唤醒，得到TWT的参数，记为t1，TWT唤醒间隔记为t2（这两个参数表示下一个TWT会话会从当前目标信标的t1的偏移量开始，连续会话的时间间隔为t2）。因此，STA1在（t0 + t1）加入会话，这个会话结束后，STA1会在t0 + t1 + it2 （i = 1， 2， …）唤醒，为了在AP宣布新的目标信号（图中的第四个）之前加入连续的会话。后续STA2在第四个目标信标醒来，与STA1共享会话，在第六个目标信标，STA3醒来，也加入共享。

​ 从结果来看，在第二个信标之后的会话，由于只有STA1被唤醒，所以只有Ru2被使用；在第4个信标后，此时STA1和STA2使用相同的RU，导致了Ru2的冲突，在第六个目标信标后的会话中，三个STA都被唤醒，而RU1又存在冲突。当STA的数量大于Rus时，碰撞是不可避免的，所以本文提出方案的主要思想就是设计一个合理的LI、RU分配方案，避免碰撞的发生，提高吞吐量。

贡献

• 提出了一种基于TWT的信道调度接入方案（SCAT），支持AP为STA找到最佳的NTB和LIS，以便能按时访问信道，提高吞吐量。（在SCAT中，AP的目标就是让每个目标信标唤醒的STA数量不超过但是要很接近RUs的数量），SCAT通过将OFDMA机制中的多用户传输能力与TWT机制相结合，实现了无争用信道接入。
• 建立了一个数学模型来推导由休眠（DAFS）引起的延迟、在一段时间内到达STA的数据包的期望数量和被研究802.11ax的吞吐量。

三、相关工作

​ 为了节省能源，人们使用过各种各样的方法。比如优化调度信号源的唤醒时间，使同一信标下的最大STA数量最小；利用中国剩余定理提出了一种异步省电协议产生唤醒频率，同时唤醒所有接收组播消息的STA。但是上面的方法只考虑使用一个信道，而802.11ax标准引入OFDMA支持多个子信道（RUs）,因此，上面这些方案应用到802.11ax中的效果就不好。

​ 目前，在基于802.11ax无线局域网新MU功能的TWT机制中，为TWT机制设置合适的NTB和LIS的研究进展甚微，本文提出的SCAT填补了在这一方面的空白。

四、SCAT方案的提出

1 概念

​ 假设AP最多可以给STA分配m个可用的RUs，那么在每一个会话中唤醒的STA不能超过m个。因此，让STA将其LI设置为下面集合中的一个元素。

​ 下面举个例子：假设有11个STA和4个RUs。STA请求LIs如下表所示。根据下表的配对方式生成了一个树状图，可以看见一个目标信标不是所有的STA都被唤醒。

​ 如果让AP优先分配自己的资源，重新分配NTB和Li如下表。再从生成的树状图来看，所有的目标信标都有唤醒的STA，从而提高了通道的利用率。

2 时间表的树形表示

本文用T来表示表示LI调度树，Ti（i = 1,2,…）表示它的m字树，sk在调度树中位置（lk）由下面公式计算，y_k 是请求的LI。

​ 在表1中，Ru1被分配给了S4和S2，通过上面公式计算，它们分别为与第二层和第四层

​ 表2也一样。

​ 公式4，对于Li为yk的sk，它每yk个信标唤醒一次，因此平均每个信标唤醒1/yk次，反映了所有STA的唤醒时间不超过1的事实。这就保证了将一个STA分配到调度树的一个子树叶子上，可以保证在每个信标上，子树中不超过一个STA被唤醒。

​ 公式5保证了每个信标传输时间不超过m个sta被唤醒，使得信道被无争用访问。

3 LI调度优化问题

睡眠延迟（DAFS）

​ 当两个数据包在相同的LI到达，那么后一个数据的睡眠延迟可以由下列公式求出。

剩余到达时间（RAT）

​ 当两个数据包在不同的LI到达，那么可以将后一个数据包剩余到达时间定义为从前一个LI失效的瞬间到后一个数据包到达STA的瞬间的时间周期。

假设

一个数据包的RAT可能跨过不止一个LI，做出以下两个假设

1. s_k 具有概率密度函数(pdf)a^(K) 和累积分布函数A^(k) (x)，k = 1, 2, ……,n
2. 报文到达两个sta的时间是独立的，也就是说，当k1 ≠ k2,T_i^K1 与T_i^(k2) 独立。

第一个数据包pdf和cdf的推导

综上，对于第一个数据包DAFS的cdf如下

由此推导出pdf

后面数据包pdf和cdf的推导

这时我们需要考虑到式6和7的情况

分别对两种情况进行推导，并给出两个命题

1. 第j个数据包DAFS的CDF
2. 在δ时间内有i个数据包到达sta

综上，我们可以求出cdf，并推导出pdf

​ 通过上面推导出来的pdf和cdf，我们可以计算第j个数据包期望的DAFS。在给定的时间δ，每个数据包到达sta的平均DAFS如下。

命题2

​ 在δ时间内有i个数据包到达sta的概率

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-v4eiqOPN-1658973971500)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220722162947704.png)]

推导过程

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8iROh80w-1658973971500)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220722163932927.png)]

综上，在时间段δ到达STA sk的预期包数为

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-S6dusLlT-1658973971500)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220722164030000.png)]

​ 802.11ax标准中的UORA机制支持无竞争的信道访问，发送过程如下图所示。

​ 首先AP向STA发送一个TF帧，其中携带者Ru的各种信息（包括定时RUs和随机访问RUs）；其次STA在收到TF后，等待一个SIFS，然后通过不同的RUs向AP发送一个数据包；最后AP等待SIFS向STA发送一个ACK确认收到了报文

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-F37699yN-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220722165638288.png)]

​ 那么总共经历的时间Γ如下。其中t_TF (m)、t_SIFS 和t_ACK 分别代表TF、SISF和ACK的持续时间。t_PHY 表示序文与物理层头部的一段时间。L为MPDU的长度（Mac protocol data unit）。r是STA的应用数据率

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-7H4GdKKO-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220725151208318.png)]

​ 为了让下一个TWT会话在LI交付期间到达STA的所有数据包，需要满足以下条件。h^(K) （y_k σ）是在 LI y_k 期间到达s_k 的数据包数，θ表示一个TWT会话周期

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SkcDrAOQ-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220725152411828.png)]

​ 因此，从sk发送到AP的总比特数：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RxHOo6WA-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220725152924120.png)]

​ 我们可以计算在一个TWT会话时间（θ），网络的吞吐量。
接下来我们的目标就是去解决吞吐率最大化的问题。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-IKlcUq2d-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220725153058248.png)]

4 优化问题的解

种群初始化

​ 随机生成M染色体，每条染色体是由一棵由m棵二叉子树组成的调度树，调度数中的所有叶子节点满足下面约束。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nhycvHQE-1658973971501)(C:%5CUsers%5C14645%5CAppData%5CRoaming%5CTypora%5Ctypora-user-images%5Cimage-20220725155121517.png)]

​ 生成初试调度树的算法：

选择操作

​ 采用Roulette Whee轮转法，按照一定的概率选取M条染色体，这些染色体将[0, 1]区间按照一定的间隔分开。然后在这[0,1]区间中产生M个随机数，第i个区间的随机数将第i条染色体复制到下一代，从而使M条染色体复制到下一代。（为了在进化的过程中逐步提高适应度，可以将一代中适应度最大的染色体直接传递给下一代，称为精英染色体）

交叉操作

​ 在两棵调度数中T1、T2中，各随机随机选取一个子树TA、TB，子树的节点记为c1、c2，然后根据一定的规则交换这两个子树，生成新的两棵调度树T1’、T2’。
​ 交叉规则: 如果c1 不等于 c2，假如c1 > c2，那么从c1所属子树TA中随机选取c2个结点组合成TB的格式放在T1’中；T2’中新的子树则是从TB中选取c1个结点（这时TB中的节点数量肯定不够，所以空位由不在T2’中的STA自动补齐）组合成TA的格式放在T2’中。如果c1等于c2，就是互相交换位置即可。
​ 注意：如果最后的产生的新树不满足TMP中的约束条件，就直接替换成算法1中生成的树。

变异操作

​ 在每一代中我们从[0,1]随机选择一个数字，如果该数小于0.01，那么就用算法1随机生成树进行替代。

5 性能评估

仿真设置

​ 假设一个WLAN由一个AP和n个sta组成，在物理层和MAC层均采用IEEE 802.11ax协议，提供支持MU功能的OFDMA机制，sta工作在TWT模式下，传输、接收、闲置和休眠模式下运行时的功率分别设置为1400、1340、1270和220 mw。

​ 假设到达STA sk的数据包服从概率为λk的泊松分布，第j个包DAFS的pdf如下

性能比较

参数对SCAT性能影响

​ 参数包括STAs的数量、RUs的数量、到达sta包的速率、TWT会话持续的时间以及包的延迟界限

​ n（sta的数量）

​ 下图可以看出，SCAT在吞吐量、EE和信道的利用率方面均优于其他方案；SCAT的吞吐量随着n的增加而增加（在n <40时，存在吞吐量急剧增加的情况，这因为在sta较少的情况下SCAT努力唤醒信标内活跃的STA，但是不会超过RU的数量，保证了上行MU传输不存在信道争用）；当n > 20，SCAT占用最小的DAFS，反映了SCAT优化问题中约束条件中的包延迟约束的有效性。

​ m（RUs的数量）

​ SCAT在各种情况下的性能依然是最好的，当m较小时（m < 9）吞吐量显著增加的原因是是因为更多的sta可以一次访问信道（SCAT是自适应的，当更多的RUs可用时，在TWT会话中调度更多活动sta，而其他方案没有这样的适应性，所以它们的吞吐量不能从RUs数量的增加中受益）；当m较大时，SCAT的吞吐量无法进一步提高，这是因为SCAT的sta已经成功的交付了它们的包，当m足够让sta交付包时，由于sta的缓冲区没有更多的包，即使还有更多的可用RUs，吞吐量也无法进一步提高，信道利用率也因此降低。

λ（包到stas的概率）

​ 随着λ增大，吞吐率呈波动状态增加，因为一个较大的λ意味着更高的吞吐量，当RUs的数量足够时就可以交付，但是如果λ过大就会造成吞吐量下降。

五、结论

​ 本文针对信道接入的调度问题，提出了将目标唤醒时间（TWT）机制与IEEE 802.11ax标准提供的多用户传输能力相结合的SCAT。
​ 利用遗传算法，得到了SCAT优化问题的解决方案，使得AP能够唤醒不超过接近每个目标信标上的终端数量的sta，从而这些终端可以在不同终端上同时向AP传输而不发生争用，提高了吞吐量、通道利用率和能源效率。