基于非稳态MAB 的LEO 卫星跳波束时隙分配算法

林敏，阚鹏程，赵柏，程铭，杨绿溪

（1.南京邮电大学通信与信息工程学院，江苏 南京 210003；2.东南大学信息科学与工程学院，江苏 南京 211189）

0 引言

针对6G 网络中“泛在连接”的技术愿景，卫星通信因其通信覆盖范围大、不受地理条件限制、组网灵活等优点，被产业界和学术界认为是实现6G技术愿景的一种重要的通信方式[1]。在卫星通信中，低地球轨道（LEO,low earth orbit）卫星通信凭借其传输时延短、建设成本相对较低等特点，在近几年得到了较多的关注和发展[2]。随着SpaceX、OneWeb等公司低轨卫星星座建设计划的提出与实施，以及我国低轨卫星互联网星座的研究和部署，LEO 卫星通信成为卫星通信领域研究的焦点。

跳波束（BH,beaming hopping）技术以业务需求为驱动，通过在同一时刻只激活部分波束覆盖相应的地面小区，实现系统资源的合理分配和灵活调度，一经提出便得到了广泛的关注和研究[3-4]。文献[5-6]综合考虑了跳波束系统中波束重访时间和分簇尺寸等因素，以n阶差分容量最小化为目标建立相应的优化问题，采用凸优化方法求解得到时隙分配结果，并通过时隙分配进一步缓解了多波束卫星的同频干扰问题。然而，该方法采用离线静态资源分配，并不能很好地适应用户业务需求动态变化的场景。文献[7]则基于贪婪算法根据用户业务的需求分布灵活地分配星载资源，但是该算法未考虑服务公平性问题。文献[8]则在保证每个波束服务公平性的前提下，建立了最小化实时性服务数据包时延以及最大化非实时性服务数据包吞吐量的多目标优化问题，并基于深度强化学习实现了该多目标优化问题的动态求解。该方法虽然能很好地适应用户业务需求动态变化的场景，但仍然存在学习模型复杂度较高、对计算资源需求较高的问题。

多臂赌博机（MAB,multi-armed bandit）模型作为强化学习中实现探索和利用平衡的一类经典模型，因其具有在未知环境信息条件下也能实现动态优化的特点，在信道选择、推荐系统等领域得到了广泛的应用[9-11]。传统的MAB 模型依赖于平稳的奖励分布，文献[12]进一步研究了非稳态MAB 模型并提出了相应的求解算法，并且通过理论和实践证明，该求解算法能在保证收敛性的情况下很好地应用于奖励分布未知且随时间动态变化的场景，同时相比于深度强化学习等人工智能算法，其对计算资源的需求更低。

本文考虑LEO 跳波束卫星系统中地面小区业务需求分布不均以及动态变化的场景，在满足小区业务需求量的基础上建立以二阶差分容量为目标的最小化问题。由于小区业务需求的时变性，所建立的优化问题难以直接求解，因此本文首先提出波束等级组合方案生成算法以生成所有可能的波束等级组合方案；然后在固定波束等级组合方案的情况下，通过非稳态MAB 模型完成时隙的动态分配；最后以二阶差分容量最小化为准则选择最优波束等级组合方案，从而完成时隙分配与波束等级匹配的联合优化。由仿真结果可知，与单一等级方案和单一波束方案相比，本文算法能够进一步降低跳波束系统业务处理的归一化平均冗余度；同时相比于其余的时隙分配方案，本文算法在总业务需求量变化的同时能达到较高的系统吞吐量，并保持相对较低的波束平均重访时间。

1 系统模型

如图1 所示，本文研究LEO 跳波束卫星通信系统的前向链路传输场景，它由网络控制中心、配备跳波束控制器的LEO 卫星和地面小区组成，并采用兼容DVB-S2/S2X 协议的跳波束工作方式。综合考虑LEO 卫星所处的轨道高度以及移动性，本文将LEO 卫星在飞行过程中的总体覆盖区域划分为不同的观察窗口，并且在每个观察窗口内能够服务N个地面小区。为了提高系统的频谱利用效率，LEO 卫星在当前观察窗口内以全频率复用的方式同时生成K个点波束服务N个小区。由于星载资源较有限，在跳波束卫星通信系统中通常假设点波束数目远小于小区数目，即K≪N。基于上述的LEO卫星跳波束通信场景，本文将分别详细介绍小区业务模型、信道模型以及分等级波束模型。

图1 LEO 跳波束卫星通信系统模型

假设跳波束卫星通信系统的跳波束周期为TW，而卫星在跳波束周期内的每个时隙以数据包的形式向地面小区提供业务数据，且数据包大小均为Xbit/s。同时假设各个小区在t时隙到达的数据包个数为A(t)=[a1(t),a2(t),…,aN(t)]T，其中数据包的到达数量an(t)服从均值为λn(n=1,2,…,N)的泊松分布，则在该观察窗口中各个小区在一个跳波束周期内的业务需求量为

此外，各小区数据包达到后若不能及时处理则进入缓冲区队列等待，并将t时隙的缓冲区数据量表示为

在传统的跳波束卫星通信系统中，其单波束业务数据处理能力较固定，这可能会导致在跳波束时隙分配过程中存在以下2 种固有问题。1)当某些小区的业务需求量较大以至于接近甚至超过了单波束最大业务数据处理能力时，便需要卫星波束长期照射这些小区，这会导致其他小区业务处理不及时、数据包等待时延过长；2) 当某几个相邻小区的总业务需求量较低时，如果仍然使用单一等级波束在这些小区间进行跳变，则会占用过多的跳波束时隙，导致其余小区的业务需求量难以得到满足。针对上述问题，本文采用波束分级方法来进一步提高跳波束LEO 卫星通信系统的资源利用率[13-14]。具体来讲，本文考虑采用3 种等级的波束处理小区的业务数据包，如图2 所示。

图2 分等级波束示意

本文考虑3 种等级的波束，并分别记为L1、L2和L3。其中，L1等级波束覆盖1 个小区，L2等级波束覆盖7 个小区，L3等级波束覆盖19 个小区。综合考虑分等级波束增益差异性、卫星信号传播过程中的自由空间传输损耗以及雨衰等因素的影响，卫星下行信道可建模为[14]

图3 波束3 dB 角度计算示意

根据式(3)可以得出t时隙被Li等级波束k服务的小区n的输出信干噪比（SINR,signal to interference plus noise ratio）表达式为

其中，PT表示卫星发射功率；σ2=κTnoiseW表示噪声功率，其中κ、Tnoise和W分别表示玻耳兹曼常数、噪声温度和载波带宽；In(t)表示该小区在当前时隙受到来自其他被照射小区的同频干扰，其具体表达式为

其中，K为当前工作的波束集合，为波束k'服务的小区集合。进一步地，可以得到t时隙针对被照射小区n的数据包处理能力为

于是小区n经过一个跳波束周期后的总业务数据处理量为

2 问题建立与求解

2.1 问题建立

由小区业务模型和分等级波束模型可知，当部分小区业务数据量需求量较大时，应尽量采用L1等级波束以尽可能满足其业务需求；当部分小区业务数据量较小时，可考虑优先采用L2等级波束或L3等级波束对这部分小区进行合并，从而将更多的时隙资源分配给其余业务需求量较大的小区。因此，需要通过联合优化时隙分配与波束等级匹配以尽可能满足各小区在一个跳波束周期内的业务需求，本文以二阶差分容量最小化为目标函数，建立如下形式的联合优化问题

其中，C1 限定了每个小区的波束等级选取范围；C2 限定了时隙分配矩阵中每个元素的取值范围；C3 中表示小区n选择的Li等级波束所覆盖的小区数目，因此C3 表示在同一时隙服务地面小区的波束数不能超过多波束卫星的最大波束数目。

由于该问题为非线性整数规划问题，且由于小区业务需求的动态变化，直接求解该问题将变得十分困难。因此本文首先提出波束等级组合方案生成算法以生成所有可能的波束等级组合方案；然后在固定波束等级组合方案的情况下，通过非稳态MAB模型完成时隙的动态分配；最后根据二阶差分容量最小化为准则选择最优波束等级组合方案，从而完成时隙分配和波束等级匹配的联合优化。

2.2 波束等级组合方案生成算法

由于跳波束周期通常较短，且LEO 卫星过境时间有限，因此为了避免LEO 卫星波束等级的频繁切换，本文假设在一个跳波束周期中，每个小区只可以固定选择一种等级的波束。基于该假设，本文提出一种波束等级组合方案的生成算法以生成各个小区在一个跳波束周期内所有可能的波束等级组合，从而为后续的动态时隙分配提供先验知识。

首先考虑2 种特殊波束等级组合方案，即单一等级方案和单一波束方案。在这2 种方案中，各个小区在一个跳波束周期内均采用同一种波束等级（L1等级或L3等级），不存在多种波束等级并存的场景，此时，退化为传统的跳波束时隙分配问题或单波束场景。

然后考虑更一般的情况，即部分小区选择L2等级波束，而部分小区选择L1等级波束。此时对波束等级组合方案的分析将变得复杂，因为尽管在一个跳波束周期中各个小区只能选择一种等级的波束，但是小区对L2等级波束的选择可能在不同时隙上存在重叠，如图4 所示。

图4 混合波束等级示意

从图4 可知，从单个时隙来看，当1～7 号小区选择L2等级波束时，其余小区均只可以选择L1等级波束。从整个跳波束周期来看，12～14 号小区对应的波束等级依然有可能为L2等级波束，因为它们的波束与1～7 号小区对应的波束并不在同一个时隙被照射。因此，该波束等级组合方案依然是可行的。波束等级组合方案生成算法首先要处理混合波束等级在不同时隙下的重叠问题。对此，本文首先提出关键小区和有效关键小区的概念。

关键小区为可能处于波束覆盖中心且波束等级的选择将影响周围小区波束等级选择的小区。以图4 为例，当1 号小区在一个跳波束周期内对应的波束等级为L2等级时，可以通过L2等级波束覆盖方式得出，其周围2～7 号小区将至少有3 个小区选择L2等级波束，并且1 号小区可以处在波束覆盖中心，因此认为1 号小区为关键小区。同理，2～7 号小区均可作为关键小区。

有效关键小区为在一个跳波束周期中能够处于波束覆盖中心的关键小区。仍然以图4 为例，尽管1～7 号小区为关键小区，但是在图4 所示的波束等级组合方案中，有效关键小区只有1 号小区和4 号小区，因为它们在一个跳波束周期中能够处于波束覆盖中心。

通过有效关键小区的概念可知，图4 中重叠问题来自在一个跳波束周期中选择了2 个关键小区，同时也可以借此计算出混合了L2等级波束的所有可能的波束等级组合方案的数量。具体来讲，当有效关键小区数量为1 时，可能的波束组合方案数量为对应的7 种方案分别是1～7 号小区各自作为选择L2等级波束的有效关键小区，而其余小区选择L1等级波束。因此通过改变有效关键小区的数量，可以得出混合了L2等级波束的所有可能的波束组合方案的数量应为

本文提出的波束等级组合方案生成算法的基本流程如下。首先，确定有效关键小区集合C以及集合元素个数M；然后，依次从集合C中选取1 个元素、2 个元素等，直到M个元素全部被取出，并根据每次选取结果确定其余小区的波束等级组合；最后，将所有波束等级组合汇总，得出所有的波束组合方案集合S。需要说明的是，尽管前文在引入关键小区时以混合了L2等级波束小区的情况为例，但是通过改变有效关键小区集合C中的元素，该算法仍然适用于前文所述的2 种特殊波束组合方案的生成。该算法流程如算法1 所示。

算法1波束等级组合方案生成算法

初始化有效关键小区集合C，集合C元素数量M，波束等级组合方案集合S

2.3 动态时隙分配算法

当生成波束等级组合方案集合S后，本节将针对集合S中的每个具体波束等级组合方案s进行跳波束时隙分配。由于小区业务需求量是动态变化的，因此传统的凸优化求解方法将不再适用。本文提出基于非稳态MAB 模型的求解算法。与传统MAB 模型类似，在非稳态MAB 模型的动作空间中也包含多个摇臂，而玩家每次只能从动作空间中选择一个摇臂，并获得相应的奖励。因此，在正式求解非稳态MAB 模型之前，应首先定义该模型的动作空间以及奖励设置，具体如下。

1) 动作空间

当固定一种波束等级组合方案后，动作空间为该方案下所有跳波束图案构成的集合，每种跳波束图案对应该动作空间中的一个动作（摇臂）。以图5 为例，假设本文选择的波束等级组合方案为1～7 号小区在整个跳波束周期内选择L2等级波束，而其余小区选择L1等级波束，同时假设每个时隙可同时服务的最大波束数量K=3，则图5(a)～图5(c)均为该波束等级组合方案下可能的3 种跳波束图案，该波束等级组合方案下所有可能的跳波束图案数量应为种，即从8～19 号小区中任选2 个L1等级波束小区与1～7 号小区相组合的组合数量。

图5 动作空间示例

2) 奖励设置

奖励设置直接影响非稳态MAB 模型的决策效果。考虑到跳波束时隙分配的基本要求是尽可能满足每个小区的实际业务需求，因此本文的奖励设置将围绕小区实际业务需求量和数据包处理量来展开。具体来讲，假设所选定的动作空间中包含Q个摇臂，且在t时隙选择了第q个摇臂，且该摇臂中包含的小区n的当前缓冲区数据包个数为φn（t），同时该小区新到达数据包个数为an(t)，且在当前摇臂下计算出该小区的数据包处理能力为，则针对该小区的瞬时奖励的具体表达式为

其中，β为大于 1 的乘性系数；Cn=为该小区在当前动作空间下的参考数据包处理能力。同时，由于单个摇臂通常包含多个小区，因此需要进一步对这些小区的瞬时奖励求平均以得到该摇臂的归一化动作奖励，则第q个摇臂在t时隙的奖励表达式为

其中，Numq表示该摇臂包含的小区数量。

3) 非稳态MAB 模型的求解

首先，给定动作空间A，该动作空间包含的摇臂数量为QA，则基于前文的奖励设置，通过折扣上界置信区间（D-UCB,discounted upper confidence bound）算法进行非稳态MAB 决策，从而得出该动作空间下的时隙分配方案[12]。

具体来讲，首先，在t时隙计算出该动作空间下第q个摇臂的折扣期望奖励为

2.4 最优波束等级组合方案选择

利用D-UCB 算法可得出给定动作空间下的最优时隙分配方案。在这之前，需要选择最优动作空间以确定最优波束等级组合方案。本节考虑以二阶差分容量最小化为准则选择最优波束等级组合方案。具体流程如下。首先，从波束等级组合方案集合S中选择一种波束等级组合方案s；然后，基于非稳态MAB 模型完成该方案下的时隙分配；接着，根据时隙分配结果计算方案s下小区业务需求量和实际处理量的二阶差分容量，即最后，选择二阶差分容量最小的方案作为最优波束等级组合方案，从而完成时隙分配与波束等级匹配的联合优化。

考虑到不同波束等级组合方案s下的时隙分配是互相独立的，因此可以并行执行动态时隙分配。最终，可将本文所提时隙分配和波束等级联合优化算法流程总结为图6。

图6 时隙分配和波束等级匹配联合优化算法流程

3 仿真结果与分析

3.1 场景和参数设置

本文采用的仿真工具为MATLAB R2022a，并且在仿真时，假设LEO 卫星工作于Ka 频段，覆盖区域内包含19 个小区。其余仿真参数如表1 所示。

表1 仿真参数

3.2 仿真结果与分析

在进行仿真结果分析之前，本文先引入以下性能评估指标。

系统吞吐量。每轮实验中传输的数据包总数。

波束重访时间。跳波束所分配的时隙之间的间隔时间，重访时间过长将会影响用户终端的同步[4]。

系统归一化平均冗余度。当方案s完成时隙分配后，通过计算该方案下实际业务处理量与实际业务需求量的差值并在归一化后取平均，即可得出该方案下的系统归一化平均冗余度，该指标可以直观反映出系统资源的利用情况，其表达式为

1) 混合波束等级方案优势分析

首先，为了体现混合波束等级带来的优势，本文考虑了以下6 种场景。①所有小区需求均较低；②所有小区需求均较高，但都未超过单一等级波束最大处理能力；③大部分小区需求较低，剩余小区需求较高；④大部分小区需求较高，剩余小区需求较低；⑤中心小区需求较低，剩余小区需求较高；⑥中心小区需求较高，剩余小区需求较低。

然后，分别绘制了不同场景下混合波束等级方案、单一波束方案和单一等级（L1）方案下的系统归一化平均冗余度曲线，如图7 所示。

图7 不同场景下系统归一化平均冗余度对比

由图7 可知，在各种场景下，混合波束等级方案均保持了较低的系统平均冗余度。在场景①中，由于所有小区业务需求均较低，因此单一波束方案即可满足要求；在场景②中，由于所有小区需求均较高且都未超过单一等级波束最大处理能力，因此场景②下采用单一等级（L1）波束进行跳变即可达到最低系统归一化平均冗余度；在其余场景中，由于混合等级波束方案可以通过波束等级匹配来空出时隙以满足其余业务需求量较大的小区，因此当小区间业务差距较大时，混合波束等级方案依然可以表现出较低的系统归一化平均冗余度。

2) D-UCB 算法参数分析

对于D-UCB 算法来说，折扣因子γ的选取将直接影响该算法的性能。当γ=1.0时，D-UCB 算法将退化为传统UCB 算法，并适用于奖励分布稳定已知的情况；当γ=0时，D-UCB 算法则完全依赖于历史的奖励，只根据瞬时奖励做出决策。因此本文分别考虑了γ=0、γ=0.5以及γ=1.0这3种典型情况下系统吞吐量随总业务需求量的变化情况，如图8 所示。

图8 不同折扣因子下系统吞吐量变化对比

由图8 可知，当γ=0时，D-UCB 算法在总业务需求量较高时难以保证稳定的性能，且系统吞吐量始终难以满足业务需求量的要求；当γ=0.5和γ=1.0时，D-UCB 算法下的系统吞吐量均能保持稳定增长，且前者性能相对更高，这也反映出当奖励非稳定时，通过对历史奖励的选择性利用，可以让D-UCB 算法保持较好的效果。

3) 不同算法性能对比分析

为了验证本文所提出的基于非稳态MAB 模型的动态时隙分配算法的性能，本节考虑将该算法与平均时隙分配算法、贪婪时隙分配算法以及ε时隙分配算法进行对比，其中对比算法的具体介绍如下。

平均时隙分配算法。在跳波束周期中的每个时隙依次选择一个小区进行时隙分配。

贪婪时隙分配算法。在跳波束周期中的每个时隙选择当前缓冲区数据包数量最大的小区进行时隙分配。

ε时隙分配算法。在跳波束周期中的每个时隙按照1-ε的概率对D-UCB 算法进行时隙分配，否则依旧选择当前小区进行时隙分配。

最后，本文对比了不同算法下系统吞吐量情况，如图9 所示。

图9 不同算法下系统吞吐量对比

由图9 可知，随着总业务需求量的增加，平均时隙分配算法不能充分实现波束等级和时隙资源的灵活分配，因此其系统吞吐量始终较低；贪婪时隙分配算法只注重当前时隙的缓冲区数据情况，其决策从整个跳波束周期来看未必最优，因此其吞吐量相对较低；ε时隙分配算法的性能在总业务需求量较低时比较接近本文算法，但由于其决策时仍然存在一定的随机性，因此该算法仍然存在一定的性能损失；相比这3 种算法，本文算法的系统吞吐量随着总业务需求量的增加仍然能保持较稳定的增长，同时在总业务需求量较高时也能保持相对较好的性能。

4) 波束重访时间变化分析

波束重访时间也是衡量跳波束系统性能的一个重要指标。为了衡量本文算法的波束重访时间，本节进行了50 次实验，并统计每次实验下的波束平均重访时间，最终结果如图10 所示。

图10 波束平均重访时间变化

由图10 可知，本文算法的波束平均重访时间始终保持在300 ms 以内，且大部分情况下可以保持在250 ms 左右，因此能够基本满足跳波束系统的同步性能要求[5]。

4 结束语

本文研究了LEO 跳波束卫星系统中的时隙分配和波束等级联合优化问题，从而在小区业务需求时变性和空间不均匀性的情况下实现卫星资源的灵活分配。相比于已有的跳波束算法，本文借助于非稳态MAB 模型实现了在不依赖于环境信息以及较高计算资源下的动态时隙分配，且通过采用分等级波束技术实现了波束覆盖范围与小区业务需求的匹配。仿真结果表明，相比单一波束方案和单一等级波束方案，本文所提混合波束等级方案的系统平均冗余度均不超过20%；当总业务需求量从1 200 Mbit/s 增长到3 600 Mbit/s 时，本文所提动态时隙分配算法依然能保证较高的系统吞吐量，并将波束平均重访时间控制在300 ms 以内，从而提高了LEO跳波束卫星系统的资源利用率。