一种基于双队列模型的分布式MTD接入方法*

曹 逊，王 聪，赵几航，吴 霞，姚远翔

（陆军工程大学，江苏 南京 210001）

0 引 言

机器到机器（Machine to Machine，M2M）通信是物联网（Internet of Things，IoT）中的重要组成部分，目标是在最少的人工干预下实现不同机器设备之间的自主通信[1]。据估计，到2025年，物联网设备的数量将接近200亿台[2]。长期演进网络（如LTE、5G）因其广泛覆盖、基础设施完善等优点，为大规模机器类型通信（massive Machine Type Communication，mMTC）提供了现实基础。然而，作为一种针对人与人（Human to Human，H2H）通信的技术，LTE网络部署M2M通信面临诸多挑战[3]，其中之一就是M2M通信中的MTDS密度通常非常高[4]，会引起激烈的竞争，并显著降低随机接入（Random Access，RA）过程的接入效率。因此，正确设计用于M2M通信的RA协议尤为重要[5]。为了缓解激烈的竞争，已有许多方案被提出，包括自适应调整退避参数。它又分为调整接入类禁止因子q[6-8]和统一退避窗口（Unified Backoff window，UB）大小[9]，需适当调整RA过程中分配的前导码（Random Access Preamble，RAP）数量和时隙长度[10-12]，或者将所有机器类型设备（Machine Type Device，MTD）进行分组等[13]。上述方法中，自适应调整接入等级限制（Access Class Barring，ACB）因子和退避窗口大小的方案更受关注。该方法的关键在于准确设置最佳参数，并随网络变化及时进行调整。一般来说，可以将其分为集中式方案[14-16]和分布式方案[17-20]。

在集中式方案中，基站（Base Station，BS）确定退避参数，然后将它们广播到网络中的所有MTD。以前的大多数工作[6,8,14,16-21]提出，BS根据实时网络状态来确定积压的MTD的数量（即网络中待接入的MTD）。例如，通过每个时隙[14]中的空闲RAP数量和每个时隙[16]中成功的RAP或冲突的RAP的数量来估计积压MTD数量，并估算最优参数，然后BS向网络中的每个MTD广播建议的退避参数。在接收到来自BS的消息后，MTDS随后相应地执行RA过程。在这些方法中，BS需要跟踪积压的MTDS的实时数量。这通常是时变的，很难捕获。网络状态信息的不准确可能导致网络性能从最优降级。此外，每个时隙的广播消息会给网络带来巨大的开销。

文献[22]对每个MTD建立了马尔科夫模型，分析其状态转移的稳态概率。研究发现，BS可以根据网络状态的统计信息（如每个MTD的平均分组到达速率、系统中的MTD数量）计算最优退避参数，而不是跟踪网络实时状态（如每时隙待接入的MTD请求数量）。通过BS确定的最优ACB参数，可以实现最佳的网络性能，如最大化吞吐量或最大化接入成功率。本文吞吐量定义为平均每时隙接入成功的请求数量。然而，作为一种集中式方法，BS需要每个MTD上传自己的分组到达速率。此外，当网络状态发生变化时，BS需要实时向范围内的设备广播最新的ACB参数。考虑到M2M通信中传输的数据包一般较短，这种集中式的方案会带来很大的信令开销。根据文献[18]，这个问题在MTD数量较大时会变得严重。

鉴于此，分布式算法更加适合mMTC场景下的通信。文献[17-18]分别提出了基于机器学习和博弈论或者优化分解的分布式方案。Hussain等人[19]提出一种基于强化学习的分布式时隙分配方案。文献[20]提出一种在海量M2M通信中保证不同业务类型的服务质量保证的迭代算法。文献[23]提出了一个新框架来保证H2H通信资源的高优先级，同时满足M2M通信的多样化需求。上述工作虽然都是分布式方案，但要么选择了无冲突的时隙，要么是为了满足不同M2M设备的业务需求，都无法实现网络的最大化吞吐量。此外，因缺乏显式表达式，大多数算法都需要迭代，造成分布式调整的效率较低。

本文根据文献[22]对MTD设备在网络中状态的分析，建立马尔科夫状态转移图，分析得到各个状态的稳态概率，推导吞吐量的显式表达式，提出了一种新的分布式算法。通过这种算法，每个MTD可以根据自身的统计信息估计网络中的设备数量，进而确定最优ACB参数，可实现最大化网络吞吐量。具体来说，在同质网络中，每个MTD具有相同的数据包到达速率，每个设备根据相同的初始ACB参数计算自己一段时间内的接入成功率（本文接入成功率定义为一段时间接入成功的请求数量与总的发起的请求数量的比值），再根据一个显式表达式估算系统中的设备总数，进而确定最佳ACB参数，从而实现最大化网络吞吐量。

根据上述描述，初始ACB参数和估计区间大小的设置对该算法性能有重要影响。这两个参数的选择应当保证在估计值的准确性和估计所需时间之间取得平衡。在较长的估计区间下，MTD可以更准确估计网络参数，实现更大的网络吞吐量。但时，如果MTD数量变化较快，估计的数量就会不准确，无法实现最大化吞吐量。与D-ACB方案[16]和EPBACB方案[17]比较发现，中心式算法虽然也可以更新每时隙的最优退避参数，但它们信令开销较大，无法实现最大化吞吐量。相比之下，所提出的分布式方案可以在更低的信令开销下实现更大的吞吐量。

本文安排如下：第1节介绍系统模型和分析；第2节根据传输成功率的隐式表达式，提出最优退避参数的估计算法；第3节进行性能仿真分析；最后总结全文。

1 系统模型和初步分析

为了简化分析，考虑存在n个MTD试图接入单BS的场景。根据现行标准，MTD设备的RA过程分为4步，如图1所示。

第1步：MTD先从RAP池中随机选择一个RAP将其发送至BS。因RAP之间的正交性，选择不同RAP的设备之间互不干扰。

第2步：BS对每个收到的RAP生成随机接入响应（Random Access Response，RAR）消息，为每个RAP分配时频资源块（Resource Block，RBs）并广播到每个MTD。

第3步：每个MTD根据BS广播的RAR消息，在指定的RB上向BS发起其接入请求。注意，mMTC场景下，大量选择了相同RAP的MTD在同一RB上发起接入，此时BS不能区分这些MTD发生冲突。

第4步：BS给每个成功解码的接入请求设备发送竞争解决消息，其他竞争失败的设备将退避一段时间。

为了缓解RA过程中的冲突问题，已经提出了很多方案，其中ACB方案和退避算法应用最广。简单来说，ACB机制是通过BS向所有MTD广播一个ACB因子q，q∈(0,1]。所有MTD在选择RAP发送前都要先生成一个0～1的随机数与q比较，只有小于q时，设备才可以执行RA过程。退避算法则是给每个接入失败的MTD加上一个退避时间，即失败后的MTD不能立即再次发起接入，要在[0,W-1]范围内随机选择一个值Ws，在再次执行RA之前等待Ws时隙。

文献[21]针对M2M通信的RA过程，为每个设备建立双重队列模型。如图2所示，每个MTD包含一个数据队列和一个请求队列。数据队列存储每个MTD到达的数据包，当数据队列非空时，MTD将产生接入请求，即请求队列非空。需要注意，请求队列最多只能有一个请求。当请求成功传输至BS时，将同时清空数据队列和请求队列。

基于图2的双队列模型，分析每个MTD在每个时隙可能处于下列3种状态——通过ACB校验并传输成功状态T、未通过ACB校验为状态0、通过ACB校验但传输失败进入退避状态Ws。根据上述分析，可得马尔科夫状态转移图，见图3。

分析图3，当MTD通过ACB校验且请求传输成功时，则设备保持在状态T。设MTD请求传输成功概率为p，则保持在状态T的概率为qp，q为ACB因子。当设备通过ACB校验但请求传输失败，则设备均匀散布到W个退避窗口上，概率为q(l-p)/W。此外，当设备没有通过ACB校验时，则从T转移到状态0，概率为l-q+q(l-p)/W。当设备处于状态0时，意味着设备ACB校验失败，将于下一时隙再次接入，并以概率qp转移到状态T。若传输失败，则同样等概率转移到退避状态，概率为q(l-p)/W。其他情况则保持在状态0不变。处于退避状态的设备以概率l每时隙向上一状态转移。

根据上述分析，可以得到各个状态的稳态概率：

式中：p为请求成功传输的稳态概率。在同质网络中，所有MTD的成功传输概率相同。从式（1）可以看出，只有一个设备处于状态T，其他设备只能处于状态0或退避状态时，设备才可以接入成功。

先分析RA过程的吞吐量和平均接入时延性能。考虑系统中共包含N个MTD和R个RAP可用，前导码的选择是随机的，所以每个前导码可以视为被n=N/R个MTD选择。又因为RAP之间的正交性，选择不同前导码的设备之间互不干扰，只需要考虑选择同一前导码的设备之间的竞争关系。下面都将前导数量R设为1，系统内设备数量设为n。结合分析，在单个RAP情况下，一个MTD要接入成功，其他MTD要么数据队列为空，要么数据队列非空但处于退避状态或未通过ACB检验处于状态T或0。

根据文献[21]，可以得到单RAP系统中每个设备接入请求的成功传输稳态概率p的隐式表达式和吞吐量的表达式：

在单个RAP前提下，如果有某个设备接入请求成功传输，则其他所有竞争设备一定没有通过ACB校验，因此可以推导出单个MTD接入成功率的关于ACB因子q和设备数量n之间的显式表达式：

对式（4）关于q和n求偏导，可以得到q=1/n或q=1-e-1/n。根据泰勒公式可知，在n数量较大时，二者相等，此时p取最大值e-1，即每个前导码可以实现的最大吞吐量为e-1。据此可知，单个RAP条件下MTD接入请求成功传输的概率最大值为e-1。将此结果代入式（2），可得：

可以得到最大化成功率时的最佳ACB参数q*和W*应满足：

式中：n为系统中总的设备数量；λ为每个设备数据包到达速率。本文假设为同质网络，所有设备λ相等。另外，因为λ为统计参数，每个MTD可以轻易获取。

根据上述分析，只要知道系统中所有待接入的MTD数量n和每个MTD数据包的到达速率λ，就可以确定最佳的ACB因子q*和W*。简单的思想是通过BS统计MTD的数量，再根据MTD的反馈获知λ，确定最佳ACB因子后再广播到所有设备。

2 分布式吞吐量优化算法

根据最优退避参数的闭合公式，本文讨论了一种基于BS的集中式方法。但是，M2M通信的数据包普遍较短，而集中式算法的信令开销较大，在mMTC场景下得不偿失。因此，将针对每个单独的MTD提出一种分布式方法，每个MTD独立确定自己的最佳ACB参数，以优化网络吞吐量。

在同质网络环境中，假设所有MTD具有相同的数据包到达速率，先考虑只有单个RAP的情况，即系统中可用RAP数量为1，竞争设备数量为n。根据式（6），每个MTD既可以调整ACB因子q，也可以调整退避窗口W的大小。本文假设给定退避窗口大小W，则最佳ACB因子q*可以确定为

每个MTD的数据包到达速率λ可知，退避窗口W大小给定时，为了确定最佳ACB因子q*，需要知道MTD的总数n。

根据式（5），可以得到n的表达式为

从式（2）可知，只要给定系统初始的q和W，n数量和数据包到达速率λ保持不变，就可以得到稳定的请求传输成功率p。只要根据给定的q和W，每个MTD统计自己一段时间Te内总的发起接入请求数nt与传输成功接入请求数ns之间的比值，就可得到接入请求成功传输的稳态概率的估计值：

将式（9）代入式（8），可得：

将式（10）代入式（7），可得：

据此，可以得到最佳ACB因子的估计值。为了简化计算，本文将退避窗口W的大小设置为1，则每个MTD的最佳ACB因子估计值为：

根据上述分析，得到分布式MTD最佳ACB因子确定算法。

输入：数据包到达速率λ；在估计时间T内成功传输的请求数量ns(T)和总传输数量nt(T)；初始ACB因子q；

1：在初始ACB因子q条件下，运行T个时隙；

2：统计T时隙内总共发起的接入请求的数量nt(T)和成功传输的接入请求数量ns(T)；

3 仿真结果与分析

仿真采用事件驱动型仿真。在单个RAP条件下，当n个MTD试图接入BS且只有一个设备通过ACB校验选择前导码时，接入请求才可以传输成功。系统中每个MTD的数据分组到达服从参数为λ的伯努利过程。MTD先以初始q运行一段时间，统计接入请求传输成功率，并估算系统中设备数量，再以估算最佳ACB参数。运行一段时间后，再次估算最佳ACB参数，以适应网络状态变化。

从分布式最优ACB因子估计算法可以看出，估计时间T和初始ACB因子q是两个关键参数。图4给出了当估计时间T和数据包到达速率λ一定时，估计设备数量与实际真实数量之间的比较曲线，以及估计估计最优ACB因子与理论最优ACB因子之间的比较。需要说明的是，估计时间T=105个时隙，实际设备数量n=100，分析最佳ACB因子q*=0.01，λ=0.08。

从图4可以看出，在初始ACB因子较小时（远小于最优ACB因子q*=0.01），即使估计时间较长（T=105个时隙），算法依然无法准确估计系统中的MTD数量，导致估算的最优ACB参数与分析获得的最优ACB参数差距较大，系统无法实现最大化网络吞吐量；当初始ACB因子接近q*时，可以十分准确地估计出系统中的MTD数量，计算出最接近q*的估计；当初始q较大时（q＞0.1以上），估计的MTD数量开始出现抖动，偏离最优值，但整体表现依然优于q较小时。根据式（4），当q较小时，在n=100固定的情况下，p的最大值也无法达到最优值e-1。每个时隙只有极少部分、甚至没有设备可以通过ACB校验，若想要获取准确的接入成功率，需要非常长的一段时间。而当q较大时，每时隙可以通过的设备数量较多，可以在较短时间内获取较为准确的成功率，进而准确估算系统中MTD的数量。但是，如果初始q过大，则可能导致长时间没有设备接入成功，系统始终处于拥塞状态。随着数据队列积压的数据增加，初始成功率降低，导致无法准确估算MTD数量。从图5可以看出：q较小时，无论n如何变化，p始终保持较低；q较大时（处于最优ACB参数附近），随着n增加，成功率p可以处于较大位置，与前面分析的情况一致。

图6进一步给出了在初始ACB因子q固定时，随着估计时间T变化的算法表现。在q=0.001时，随着T增加，估计设备数量越来越接近真实值。但是，可以明显看出，从估计时间较少提升到3×104时隙时，性能提升较大，可以较为准确地估计出MTD数量，并给出接近最佳ACB因子的。但是，随着估计时间的继续增加，性能没有明显提升，因为系统中的ACB因子已经调整到最优ACB因子附近，无法进一步增加网络吞吐量。

图7将本文方法与两种经典集中式方法进行比较，可以发现所提方法可以始终保持较高的吞吐量表现。这是因为在系统内MTD数量较为稳定时，本文方法通过长时间观察可以准确估计出系统中的MTD数量。此外，集中式算法需要MTD与BS之间的额外通信，会增加信令开销。相比之下，本文的分布式算法由每个MTD自行决定ACB参数，无需BS频繁广播更新，可以节约一部分的信令开销。

4 结 语

本文针对同质mMTC场景，以最大化网络吞吐量为目标，提出了一种分布式最优ACB因子确定算法。通过分析与仿真发现，该算法的初始ACB因子q和估计时间T对其性能有较大影响。通过仿真表明，在系统内MTD数量较为稳定，且估计时间和初始q选择较为恰当时，算法可以较为准确地估计出系统中的MTD数量，计算出接近最优ACB因子的近似值，实现最大化网络吞吐量。与传统集中式算法相比，该算法有较低的信令开销，且吞吐量更好。但是，该方法也存在潜在的问题。因为ACB参数由每个MTD自行决定，某些MTD可能会故意设置较高的ACB因子以获取更高的接入优先级，会导致网络资源分配的公平性变差。如何解决这一问题有待进一步研究。