随机多址接入分布式排队的优先级调度方法

王文鼐，杨继海，吴 炜，王 斌

(1.南京邮电大学通信与信息工程学院，江苏 南京 210003 2.南京邮电大学宽带无线通信与传感网技术教育部重点实验室，江苏 南京 210003)

大容量无线传感终端的高效接入是当前物联网应用的技术挑战之一［1］。5G无线通信系统混合接入了大规模机器通信（Massive Machine Type Communication，mMTC）、增强移动宽带（Enhanced Mobile Broadband，eMBB）和超可靠低延迟通信（Ultra-Reliable and Low Latency Communications，uRLLC）等业务，而现有的随机接入物理信道（Physical Random Access Channel，PRACH）技术基于ALOHA方法，并不区分终端类型，难以保证差异化服务质量，比如低接入时延需求［2］。

现有mMTC接入在重负载时易发生拥塞，表现为冲突概率和接入时延急剧升高。为减少接入系统的并发终端数量，文献［3］在访问类限制（Access Class Barring，ACB）中引入终端接入概率和访问时限制来减少并发数。文献［4］在ACB的基础上，通过非正交多址和动态调扩资源的技术手段，以提升接入容量和成功率。文献［5］对增强接入限制（Enhanced Access Barring，EAB）设计了不同类别终端的接入时限窗口，通过分类来控制并发数。文献［6］提出一种终端分组方法，由基站利用分组寻呼将并发终端调配到不同的接入时段，以减小瞬时并发量。文献［7］则基于分布式排队（Distributed Queuing，DQ）技术，对争占共享信道失败的终端按序退避，并以树型分割方式指数缩减并发量，以提高总体接入效率。这些限制需求和扩大供给的方法，主要针对单一业务场景。

针对混合业务接入，文献［8］为高优先级终端的争占请求预留固定的前导码，方便调控和降低uRLLC业务的接入时延。文献［9］通过检测前导码的信号功率来区分不同终端，通过为有时延约束的终端提供更高的访问优先级以降低冲突概率和缩短接入时延。此外，文献［10］提出上行链路无授权的接入算法，可在低负载时满足有时延限制性需求的终端接入。这些技术方法大多基于ALOHA技术，不能有效地解决重负载时的不平稳问题。本文设计了一种基于DQ的优先级接入方案，在不影响总体性能的前提下，降低高优先级终端的接入时延。

DQ具有稳定的系统吞吐性能，其饱和吞吐量与并发终端数无关［11］。DQ最初面向CATV同轴电缆的随机多址接入，近年来被扩展到各类无线接入网络，包括 LTE［7］和 LoRa［12］等。

DQ 系统由共享同一信道的集中式协调站（通常为基站）和多个接入终端组成，协调站负责侦听终端的占用请求信号并将竞争结果以广播方式反馈给所有终端，终端依此退避重试或发送数据。

传统DQ将信道划分为固定时长的重复帧，包括竞争时隙、数据时隙和反馈时隙［13］。竞争时隙用于解决争占冲突，一般由3个短时长的小时隙（Mini-Slot，MS）组成，每个 MS有 3种争占状态：成功（仅有一个终端占用）、失败（一个以上终端占用）和空闲（没有占用请求），如图1所示。数据时隙由争占成功的终端以排队方式无冲突地依次发送数据。

图1中竞争时隙和数据时隙由终端（上行）占用，反馈时隙由协调站（下行）占用。带内结构中，上下行之间设置相对较短的保护时隙，用于容纳信道传播时延和避免信号收发干扰。应用于LTE等小区体制时，可将PRACH前导码用作MS，并由基站分配正交的时频资源块用作数据时隙和反馈时隙［7］。

图1 包含3个MS的DQ帧结构

DQ使用分布式冲突解决队列（Contention Resolution Queue，CRQ）来解决争占冲突，使用分布式数据传输队列（Data Transmission Queue，DTQ）来调度数据时隙的无冲突占用。终端在3个MS之中等概率择其一发送占用请求，收到反馈后判定所选MS的状态，成功时按序进入DTQ并在确定的数据时隙发送数据，失败时则退避进入CRQ重试。

显然，如果某一终端争占MS的成功概率高于其他终端，则该终端就能优先发送数据。这是本文设计的技术着手点。

DQ规定了一个传输启用时段（Enabled Transmission Interval， ETI），在该时段内新到的终端占用请求需要等待该时段结束。ETI内所有待发数据的终端，在下一个ETI开始时并发。所以，DQ实际上存在3个串联的排队队列，分别为ETI缓冲队列、CRQ和DTQ。

ETI缓冲队列的服务容量不受限，等待用户全部进入CRQ。DTQ的服务容量取决于数据时隙的带宽占比，排队性能接近理想的 M／D／1。而 CRQ是一个损失返回的多服务员排队系统，是DQ调度的关键，它对系统吞吐性能和接入时延起到决定性作用。文献［11］给出了CRQ冲突解决时长的数学期望 L（N），如下所列

式中，N为并发终端总数，m为MS数量，P（k｜N）＝C（N，k）pkqN-k是仅有 k个终端选中一个 MS的概率，C（N，k）为N取k的排列组合系数，p＝1／m为单个终端选中某个MS的概率，q＝1-p。

式（2）右侧包含L（N）项，移到左侧可以得到其迭代计算式。由于涉及多项排列组合，L（N）不能表示为解析形式的初等函数，所以数值计算是求解DQ性能的可行方法。

DQ系统引入优先级接入的基本思路是，将用户分为高优先级终端（High-Priority End-Device，HE）和低优先级终端（Low-Priority End-Device，LE）两类。这种分类可以是预定配置的，也可以由用户根据业务类型选择不同的终端类型或工作模式。

HE以等概率在3个MS中选择2个同时发送占用请求，LE则限制选择一个MS。如此，在一次争占过程中，HE的机会是LE的2倍。与传统DQ一致，争占成功的终端进入DTQ，因此LE无需做出任何功能调整。

HE每次争占选择2个MS，所以第1次失败返回后占据2个CRQ位置，连续2次失败后占据3个CRQ位置，连续k次失败占据k＋1个 CRQ位置。LE争占失败后只会占用1个CRQ位置，所以HE的实际争占机会远大于LE。

HE争占成功后，多占的CRQ位置存在两种可能，其一由该HE独占，其二与其他终端共占。两种情况的CRQ调度依然有效，第一种空占会产生少量的CRQ吞吐量减小。考虑到CRQ通常先于DTQ完成服务，所以DQ原有排队规则也无需调整。

比较特殊的是，当HE选占的2个MS都成功时，将产生一次DTQ空占和一次数据时隙闲置。解决办法是，协调站在侦听到2个MS被同一终端占用时，在反馈信息中将第2个MS强制设置为冲突状态，可以避免DTQ空占和数据时隙闲置。考虑到占用请求包含终端签名信息，协调站的这种功能扩展不难实现。

以上优先级DQ（DQ with Priority，DQ-P）的功能扩展设计，仅限HE终端，DQ协调站和排队规则的简单性基本得到保留。但是，当DQ-P接入多个HE时，占用请求总数随冲突次数的线性增长可致CRQ冲突解决时长增大，最终对系统性能产生不利影响。为此，DQ-P需要设置合理的HE占比。图2描述了DQ-P的典型接入时序，用以说明冲突解决过程和HE占比分析。

图2示例所描述的4个终端（H1、L1至L3）和一个协调站（C），其中 H1为 HE，L1至 L3为 LE。

协调站C侦听3个MS（MS-1至MS-3）状态，成功表示为1、失败为X、空闲为0。反馈时隙广播状态，内容“1-X-X”表示MS-1成功、MS-2失败、MS-3失败。终端发出占用请求后需要接收反馈时，则在图中复制MS状态，否则略去以示进入节电状态。

图2 DQ-P的接入冲突解决示例

在第（1）帧中，H1选择 MS-2和 MS-3（标记为R（H1）），L1、L2和 L3分别选择 MS-1、MS-3 和 MS-2（标记为R（L1） 至R（L3）），数据时隙空闲。

从反馈内容“1-X-X”可知，L1争占成功，失败的 H1和 L3经CRQ退避到第（2）帧重试，L2和H1经CRQ退避到第（3）帧重试。

在第（2）帧中，L1经DTQ占用数据时隙（标记为D（L1））；
H1再次选择了2个 MS，其中1个成功；
L3选择的 MS-1与 H1重叠，所以经CRQ退避到第（4）帧重试。

在第（3）帧中，H1占用数据时隙（标记为D（H1））并放弃原有计划的占用请求（图2中“弃占”所示），L2争用成功。

第（4）和第（5）帧同法处理，无需赘述。

图2中的箭头曲线表示退避重试，H1在竞争成功后，其后争占机会不再使用。图3描述了3个MS状态和CRQ长度随时间的变化。

图3 DQ-P的MS状态及CRQ队长（L）变化示例

图3中，斜线填充方框表示竞争成功的MS，空白方框表示空闲MS，加粗方框表示竞争失败的MS，框中字母和数字表示终端编号或签名。起始输入框内有4个终端，其中，终端a为HE，其他为LE。初始时，CRQ长度 L＝0。第（1）帧后，终端2竞争成功，L＝2表示有2组终端退避重试。第（4）帧后，终端4竞争成功，所以L＝0。

图2和图3所描述的特例，仅是各种随机争占中的一种情况。DQ-P的总体性能是各种随机情况的统计平均，数值仿真是一种较为简单有效的观测与分析手段。

如前所述，功能扩展的HE终端比LE多了一次选择MS的机会，而争占成功时放弃预分配的争占机会。如果HE终端占比过大，可致CRQ解决冲突时效严重下降。一个简单的控制措施是，为系统设置HE数量上限，或者为终端的优先级工作模式设置合理的切换比率。

参考文献［11］迭代求解，本文提出的DQ-P有相似结果，如下所列

式中，x和 i为 LE终端数，y和 j为 HE终端数，P（i，j｜x，y）是给定 x个 LE 和 y个 HE 条件下一个MS 被 i个 LE 和 j个 HE 选中概率（且 i≤x，j≤y），即状态（i，j｜x，y）的随机平稳概率。

定义p＝1／m为LE选中一个MS的概率，q＝1-p为LE未选中一个MS的概率。再定义u＝2／m为HE选中一个MS的概率，v＝1-u为HE未选中一个MS的概率。图4描述了MS状态转移情况。

图4 DQ-P中MS状态转移图

图4 中，状态（0，1｜x，y）（对应概率为 qxvy-1u）表示一个MS仅被一个HE选中，相应地，状态（i，j＋1｜x，y）将以 δ概率转移到状态（i，j｜x，y），其中， δ＝1- ［1-P（0，1 ｜x，y）］m-1。

所以

将式（5）至式（8）代入式（4）可得 L（x，y）迭代计算式。同传统DQ一样，L（x，y）没有直接的初等函数解析表达，需要使用数值仿真法来揭示DQ-P性能。

仿真计算时，为所有终端设计争占状态记录（cstate），初始为0，成功时置1。计算算法的伪代码如算法1所示。

算法1 DQ-P仿真算法

算法1中，第1行为m个争占终端集合的初始化，其后在第9～16行通过随机选择来分配终端。第2～3行针对成功争占的HE，重新构造并发终端集合。第4行处理空闲MS，第5行处理单个终端争占成功的情况。第18～19行以递归方式遍历退避分支，并计入到总的冲突解决时长中。

需要说明的是，仿真计算的冲突解决时长，以固定时长的DQ帧为单位。终端待发数据超出DQ帧容量限制时，通过分片延后发送，不会影响随机接入的冲突解决时长计算。函数size（N）表示集合N的元素个数，randint（0， m-1）为区间［0， m-1］内一致分布的伪随机数生成函数。

图5给出了冲突解决时长（L）随终端总数（N）的实验结果，其中理论值取自文献［11］，仿真程序使用Python编写，重复2 000次实验进行平均，随机数种子取自计算机的系统实时钟。

图5 DQ-P的冲突解决时长仿真结果

从图5可见，没有高优先级终端（n＝0），即DQP退化为传统DQ时，冲突解决时长（三角符）与理论值（直线）完全重合。当n＝4时，L明显增大，并在N＜8时，存在L＞N。换言之，图5预示HE终端数占比大于50%时，CRQ排队时长可能超过DTQ。这是DQ-P适用条件的上界，是配置HE占比的限制性指标。如果允许终端在LE和HE之间切换工作模式，则HE时间占比应小于50%。

算法1所列仿真算法可以很容易地对所有终端的接入时延进行跟踪和统计计算。图6给出了终端总数固定（N＝100）时，在高优先级终端数（n）变化的情况下，平均冲突解决时长和HE接入时长的缩减比（R）。仿真计算结果同样为2 000次重复随机实验的统计平均。

图6 DQ-P优先级终端时延缩减效果的仿真结果

图6中，三角符表示CRQ冲突解决时长，当HE大于30（占比大于30%）时，其值超过并发终端总数（N＝100）。所以，为保证优先级业务得到有效支持，合理的高优先级终端占比，或者终端工作于高优先接入模式的时间占比，其值应在30%以下。

图6中，方形符表示的HE接入时延（LHE）显著小于菱形符号表示的LE时延（LLE）。HE的缩减比R定义为

从图6可见，随着HE数量增长，R值呈下降趋势，但总体大于45%。在HE数量稀少（小于1%）时，接入时延平均值可以压缩60%以上。R值越大，表明HE延时越小。图6横坐标为HE数量（占比），其值增大后，冲突退避次数越大，时延越大，R值变小。仿真结果与DQ-P设计目标吻合，即，将争占概率加倍后，总体上能有效减小高优先级终端（HE）的接入时延。

本文提出了一种DQ优先级（DQ-P）随机多址接入方法，允许高优先级终端（HE）选择2个不同的竞争时隙同时发送接入请求，以提高终端争占共享信道的成功概率。文中设计了HE的接入控制时序，给出了冲突解决的典型过程和数值分析的仿真计算算法，进一步通过仿真实验分析了冲突解决时长和接入时延的统计结果。结果发现，HE接入时延可以缩小45%以上。DQ-P功能扩展主要涉及高优先级终端，可以兼容DQ中已有的协调者和普通终端，保持DQ良好的重负载平稳特性。进一步可参考DQ-P方法，优化5G mMTC或LoRaWAN的接入调度算法，以提升有延时约束物联网业务的服务性能。