作为地面网络覆盖盲区强有力的补充，低地球轨道(low earth orbit, LEO)卫星通信系统在偏远地区、应急任务、航海航空等场景有着广阔的应用。随着通信技术进步与多样化需求变革，新兴的低轨卫星星座具有宽带化、低时延、星地一体等特点。面对不均匀的用户分布，跳波束(beam hopping, BH)技术通过动态分配^[1]和时分复用等方法有效提高了卫星资源利用率。DVB-S2X蓝皮书^[2]提出实现BH操作的指南，同时从各种帧结构的格式出发验证了BH在蜂窝回程、机上连接等服务的可行性。由SatixFy建造的全数字载荷可控制波束在地球上的不同地点之间每秒切换1 000多次，并调整通信信号的强度以满足需求。Anzalchi等^[3]通过系统仿真评估了在Ka频段使用BH的优越性，最主要的优点在于可以根据用户需求动态调整带宽，使系统资源得到充分利用。对于低轨卫星星座而言，BH被认为是提高系统频谱效率最有效的方法之一^[4]。

正因为BH的灵活性，其资源分配方式具有很高的不确定性，且调度方案直接影响系统性能和计算复杂度。作为较早的星载数字通信卫星，SpaceWay通过循环的方式为每个下行链路波束提供队列^[5]。文献[6]提出对波束跳变周期和驻留时间进行优化，实现资源的高效利用。Ha等^[7]提出GEO卫星有效载荷的功率最小化可以通过联合预编码和波束跳跃设计来实现。以上关于BH的研究都面向高轨卫星，而低轨卫星的通信资源和业务需求随着卫星的快速移动而动态变化，对BH调度方案提出了更高的要求。

目前，已有较多学者对BH技术在LEO卫星通信系统中的应用展开了研究。BH的基本思想是将可视区域的单元分簇，簇内单元在给定时隙被波束访问。对于每一个波束，都有空间、时间、功率和频率等可分配的资源，其时隙和点位的分配是BH发挥关键作用的地方。为服务地面固定小区，文献[8]设计了一种按列分簇的波束调配方法，相较于随机和轮询调配，小区满足度均有较大程度的提高。文献[9]提出最高簇优先的空间聚类算法。文献[10]使用遗传算法解决流量需求的匹配问题。文献[11]针对波束服务公平性，最小化传输时延以及最大化通信容量，建立多目标优化问题模型，使用深度强化学习方法探索最优策略。上述研究从流量、时延、公平性等角度对BH架构下的资源分配进行了讨论，但对波束时隙的分配未给出具体策略。

为缓解传统频谱分配导致的资源短缺问题，文献[12]对基于认知的卫星通信网络提出分层的资源分配方案。考虑到不同波束差异化的频段偏好，作者将问题依次分解为频带选择、波束分配和时间功率分配。文献[13]提出LEO卫星共享现有地球静止轨道卫星系统的频谱资源以缓解频谱稀缺，利用BH的灵活性实现流量需求与供给的平衡。文献[14]采用宽窄波束动态结合的接入方案，点波束跳跃的信令信息由宽波束辅助获取，在业务量较小时具有较好的时延性能。虽然上述研究所提算法和方案具有一定的有效性，但缺少对同频信道干扰优化的讨论。频分复用下复用因子为1可以使带宽得到最大限度的利用，却存在严重的干扰问题。设计一种在全频复用模式下，既保证传输时延，且减少同频干扰的调度策略是有必要的。

本文面向LEO卫星通信系统，提出联合考虑排队时延和同频干扰的跳波束调度策略。针对满足通信需求和位置双重属性带来的分簇难题，采用流量需求分簇(traffic demand clustering, TDC)、时隙分配(time slot allocation, TSA)、波位匹配(beam position matching, BPM)的分解方案，为每颗LEO卫星计算上行链路的波束跳变策略。其中，将TSA完成后的波位匹配视为种群，建模为以同频干扰最小化为目标的优化问题。由于传统遗传算法的染色体交叉变异机制无法使模型目标得到优化，本文提出基于“自交叉”思想的“同时隙下簇内波位自交”染色体交叉机制。为了提高优化概率和收敛速度，算法引入二次交叉机制，在一定程度上减少了迭代次数。仿真实验证明，所提策略能够在资源分配周期内实现完整的波束调度，在保证较低排队时延的前提下，对全频复用的干扰有较为显著的优化作用。

1 系统模型

新兴LEO卫星网络架构基本包括空间段和地面段。空间段由大量LEO卫星和星间链路组成。地面段包括信关站、连接地面核心网的基础设施^[15]等。本文以一颗搭载BH天线载荷的LEO卫星为例，建立系统模型如图 1所示。卫星支持BH的有效载荷主要由透明转发器和相控阵天线^[16]组成，由于受到载荷限制，每颗卫星能够提供的波束数M远小于其可视范围内需要服务的波位数N^[17]。为提高频谱利用率，波束使用全频率复用。地面小区由六边形分层索引网格划分，将全球指定大小的六边形区域按照经纬度编码，根据既定算法对覆盖范围内的小区进行分簇。

1.1 业务需求模型

本文的波束资源调度主要面向上行链路的数据包转发。对于并不均匀的需求分布，需要建立适配波位大小的小区模型，作为卫星通信系统的需求输入。使用Uber开源的空间索引算法H3^[18]为业务需求建模。假设在卫星覆盖范围内，有N_c个小区，H3算法使用经纬度(lon_i, lat_i)表征第i个小区中心位置坐标。为计算小区间距离，使用大地坐标系与地心地固系转换公式得到小区中心地固系位置坐标

$ \left[\begin{array}{l} x_i \\ y_i \\ z_i \end{array}\right]=\left[\begin{array}{c} R_{\mathrm{e}} \cos \left(\mathrm{lat}_i\right) \cos \left(\mathrm{lon}_i\right) \\ R_{\mathrm{e}} \cos \left(\mathrm{lat}_i\right) \sin \left(\mathrm{lon}_i\right) \\ R_{\mathrm{e}} \cos \left(\mathrm{lat}_i\right) \end{array}\right], $

(1)

其中: R_e表示地球半径，约等于6 371 km。小区间距离通过

$ D_{i j}=\sqrt{\left(x_i-x_j\right)^2+\left(y_i-y_j\right)^2+\left(z_i-z_j\right)^2} $

(2)

计算得到。

LEO卫星的高速移动使得覆盖范围也发生着较快的变化，设置时间T作为卫星的资源重分配周期。在准静态周期T内，卫星通过窄波束轮询覆盖范围的用户，获取动态时变的用户需求^[19]。对于第i个小区，其数据包到达率服从参数为λ_i的泊松分布，在周期的{1, 2, 3, …, n, …, N_s}个时隙内，数据包到达队列为{λ_i¹, λ_i², λ³_i, …, λ_iⁿ}。由于小区需求分布可能近似，也可能存在较大差异，因此建立用户分布场景如图 2所示。图中六棱柱的高低代表用户需求量。对于不同的分布，需要合理的方案使得资源分配尽可能公平。

1.2 通信系统模型

搭载BH载荷的LEO卫星可以同时从卫星发射多条波束，总带宽为B，其中N_b个波束用于上行链路。在周期T内，卫星重新计算其相对地面小区的位置。周期内包含N_s个时隙，其时长T_s=T/N_s，编号为1, 2, 3, …, N_s。波束通过凝视方式为小区提供服务。

根据信道容量C和数据包到达时间，可计算当前时隙下各小区数据包的排队总时延。小区i的第k个数据包排队时延等于其开始服务的时刻t_i^s(k)与到达时刻t_i^a(k)的差值。

频分复用会使同频小区间存在信号干扰，而全频复用时，干扰达到最大。利用BH的空间和时间隔离特点，可将干扰优化到较小的情况。频分复用距离D的计算公式如下

$ D=\sqrt{3 N} R, $

(3)

$ \boldsymbol{I}=\left[\begin{array}{ccccc} 0 & 1 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 0 & 0 \\ \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & \cdots & 0 & 1 \\ 1 & 0 & \cdots & 1 & 0 \end{array}\right]_{N_c \times N_c}. $

(4)

其中: R为小区距离；N为单位区群中的小区数目，全频率复用N取1。

使用u_{i, j}表示小区i和小区j之间的距离是否大于最小频分复用距离，并建立如上邻接矩阵(4)。以小区中心点计算距离，若大于D说明2个小区可在同时隙通信，u_{i, j}值为1；反之为0，需要波束在不同的时隙提供服务。

1.3 BH资源调度问题描述

高速移动的大规模LEO卫星星座使得每个用户可能处于多颗卫星的可视范围内，面对快速变换的覆盖区域以及较为频繁的星间切换，需要为用户匹配卫星以达到传输时延、信道容量、功率能效及通信公平间的最优平衡。就服务质量而言，通常包括网络传播时延以及信道误码率2个主要指标。其中，卫星移动通信系统的传播时延取决于轨道高度和传输时延，本文以排队时延表征系统时延性能；传输信道误码率则由载波噪声比决定，其噪声与受到的干扰有关。

本文旨在通过资源调度方案提高LEO卫星的通信服务质量，主要包括对排队时延和同频干扰的优化，建立模型如下

$ \min \sum\limits_{k=1}^{N_s} \sum\limits_{i=1}^{N_c}\left[t_i^s(k)-t_i^a(k)\right], $

(5)

$ \min \frac{1}{2} \sum\limits_{t=1}^{N_s} I_{N_b}(t), $

(6)

约束条件为

$ p_i^t \leqslant p_j, \forall i \leqslant N_b, j \leqslant N_c, $

(7)

$ B_i=\Delta f, \forall i \leqslant N_b, $

(8)

$ t_i^s(k) \leqslant N_s, \forall i \leqslant N_c, $

(9)

$ \frac{\alpha P_i^r}{k T_t B_i F+I_{t o t}} \geqslant \frac{C}{N}, \quad \forall i \leqslant N_b, $

(10)

$ u_{i, j}=[0, 1], \forall i \leqslant N_c, j \leqslant N_c . $

(11)

资源调度的波束调配问题模型将排队总时延最小化和同一时隙干扰总和最小化作为优化目标。由于多目标优化无法同时达到最优，本文优先满足目标函数(5)，在时延达到理想值的前提下，再考虑减少波位间干扰，即目标函数(6)。优化目标时延和干扰是整个资源调配周期T内的最小化，因为单时隙下的优化无法保证全局最优。

约束条件中：约束式(7)表示各波束的发射功率不大于小区终端可提供的功率；约束式(8)说明系统使用全频率复用；约束式(9)限制了每个小区数据包的最晚服务时刻不能大于资源调度周期内的总时隙；约束式(10)是载噪比约束，公式右侧为系统满足通信性能的最低载噪比，卫星每个波束所接收到的载波功率与噪声功率比需要大于此值，才能保证信道误码率满足需求；约束式(11)是小区i和小区j是否可同时隙通信的关系取值约束。

2 基于改进遗传算法联合时延和干扰的BH调度策略

对于卫星波束的调度，可将问题分解为小区分簇以及簇内波位的服务顺序。由于分配策略与小区的通信需求和波位的服务间距有关，所以不能直接对小区进行划分。这是一个由时隙、需求和波位组成的三维体系，无法使用单一的优化算法进行求解。本文通过解耦合，将BH调度策略分解为TDC、TSA和BPM 3个步骤。先保证排队时延尽可能小，再对小区与完成TSA的需求进行匹配，最小化波束间的同频干扰。通过优化算法实现每一步的目标，最终形成LEO卫星的波束调度策略。具体流程图如图 3所示。

2.1 TDC

在每一个资源调度周期内，卫星首先通过窄波束轮询，获得覆盖范围中各小区的业务通信需求。由于系统使用全频率复用，各波束带宽相同；且载波接收功率取决于终端所能提供的发射功率，为方便建模，假设上行链路终端发射功率相同，信道容量相等。为使波束间的服务时差更小，本文为每个波束分配需求总和近似的N_c/N_b个小区。如果直接将小区按需求和进行分配，无法对同时隙下的波位距离进行优化。因此，调度策略的第一步，是将所有需求集合进行分簇，不涉及波位。

具体分簇方法为：将需求集合中的元素按照顺序排列，正反向依次为波束分配元素，可以保证N_b个簇内的需求总和大致相等。分簇伪代码如表 1所示。

2.2 TSA

第一阶段完成后，需求集合被等分为N_b个簇，接下来需要对每个簇内的服务时隙进行分配。关于时隙的分配可以有多种方式，如非跳跃服务(non-hopping services, NHS)、单时隙均分(single slot equalization, SSE)和多时隙非均分(multi-slot non-equalization, MSNE)等。所提3种TSA示意图如图 4所示，不同的方式具有各自的优点、缺点及适应场景。

NHS为基础的TSA方案，每个波束将其集群内的小区一次性顺序服务完，当前小区未服务完成的时候波束不发生跳跃。整个服务周期内，波束一共切换N_c/N_b次。这种方式的优点是终端无需多次接入波束，切换后可直接通信至服务完成。但存在明显的不足之处，一方面簇内小区的公平性很差，最后服务的小区需要排队较长时间；另一方面系统总时延无法保证。

SSE使用较为简单的单时隙跳跃方法，解决了NHS方案存在的不公平问题。波束对簇内小区循环服务，每个时隙跳变一次，周期为N_c/N_b。小区内终端需要随着每一个周期结束重新接入卫星。可能存在的问题是对于需求分布差异较大的地区，高需求和低需求的排队时延差异较大。

MSNE时隙的分配与需求相关，周期内的每个小区分得的时隙数量由需求量与信道容量的关系决定。首先计算各小区数据包到达率与信道容量的比值，然后根据结果，按比例分配资源调度周期内的时隙，波束根据所分得的时隙，循环服务各小区。这种方法使需求量大的小区一次被服务多个时隙，在保证公平性的同时减少了波束的跳变次数。

不同的TSA方法会带来不同的排队时延，在实际调度中，需要综合考虑系统公平性与波束跳变次数，以达到较优的性能。

2.3 BPM

对于完成TSA的需求集合，还需要将每个元素与波位对应。期望目标是在较小排队时延的前提下，优化时隙间的同频干扰。将所有可能的匹配结果方案数定义为Z，设小区需求共有X个等级，平均有Y=N_c/X个小区处于同一等级。对簇内每个元素的匹配方法为：从同等级小区中任选一个小区。根据排列组合原理，第1个簇的匹配方法存在Y^N_c/N_b个可能结果，第2个簇的匹配方法存在(Y-1)^N_c/N_b个可能结果，由此递归，所有波束的匹配结果可能值如下

$ \begin{aligned} Z & =Y^{N_c / N_b} \times(Y-1)^{N_c / N_b} \times \cdots \times 1 \\ & =(Y!\quad)^{N_c / N_b} . \end{aligned} $

(12)

当N_c取值为100，X取值为10时，对有5个BH的卫星而言，BPM方案数Z的值约为3.6×10²⁶。若对每个资源调度周期的波位匹配都采用穷举法，计算量十分巨大。因此，本文采用遗传算法的思想，针对完成TSA后的需求分簇进行BPM的问题求解。

遗传算法通过模拟自然选择和遗传过程中的繁殖、杂交、突变等现象，达到择优遗传、种群优化的目标。其优点在于无需全局遍历，而是根据优胜劣汰的自然法则，对每一代有限的个体进行“进化”，从而找到最优解。从计算复杂度的角度看，遗传算法要优于全局遍历，对计算资源宝贵的卫星载荷而言是一个合适的选择。图 5为基于改进遗传算法的波位干扰优化流程图。

2.3.1 种群初始化

设一个种群中包含N_g个个体，卫星某次覆盖范围内完成TSA后的需求分簇如图 6(a)所示，图中数值为各小区的数据包泊松到达率。随机将各波束的时隙需求与相对应的波位匹配，作为初始种群中的个体，其中一个个体的染色体如图 6(b)所示。具体初始化方法为将小区编号序列随机化N_g次，每一次从前向后对每个需求分簇匹配波位，得到包含随机个体的初始种群，完成种群的初始化。

2.3.2 适应度计算与复制

使用遗传算法进行BPM是为了优化1.3节式(6)中的干扰总和。通过式(3)和式(4)可以计算出个体在同时隙下的干扰之和$ \frac{1}{2} \sum\limits_{t=1}^{N_s} \boldsymbol{I}_{N_b}(t)$。计算步骤如下：

对于时隙t，设N_b个波束服务的小区集为{N^t₁, N^t₂, …, N^t_Nb}。根据邻接矩阵(4)，逐一判断小区集内每个小区与其他小区间是否存在干扰，若I_{Nx^t, Ny^t}=1，则I_Nb(t)的值累加一，反之不变。最后累计N_s内所有时隙的波束干扰I_Nb(t)，得到该个体的时隙干扰和。

由于SSE和MSNE 2种TSA方式是周期性的，因此只需要计算时隙周期内的干扰之和I_k即可。将I_k作为遗传算法的适应度值，从父代种群中筛选并轮盘赌复制优秀个体，生成候选种群。此时，所有小区同时隙的波位干扰总和值相对较小。

2.3.3 自交叉

BPM的优化目标是减少同时隙下的同频干扰，为提高种群中个体的适应度值，将产生干扰的波位替换为同需求大小的其余波位，替换之后的干扰和有概率减小，且一定不会增加。经过多次迭代，最终完成对干扰的优化。传统的染色体杂交是2个个体间的片段交换，无法实现减少同时隙内干扰和的目的。因此，提出染色体自交叉思想，直接对影响系统性能的染色体片段进行自交换。此外，为了减少迭代次数，提出二次交叉的思想，在一次遗传操作中，以概率p₁交叉1次，再以概率p₂交叉第2次，同一迭代过程中的2次交叉可以提升高适应度个体的出现概率，在一定程度上加快了收敛速度。染色体自交叉的伪代码如表 2所示。

其中: 输入参数pop_copyed表示完成复制后的种群；I_set为种群中每个个体存在干扰的小区组合; 输出完成自交叉操作的种群集合pop_crossed; find_cross函数功能为寻找存在干扰进行自交叉的2个波位，结果存储在cross_index列表中; pop_copyed、pop_crossed分别表示复制后和交叉后的个体; change函数进行交换波位操作。

2.3.4 时间复杂度分析

采用改进遗传算法的BPM为迭代过程，假设迭代次数为M次，对于单次迭代过程，时间复杂度分析如下：种群初始化和染色体复制过程运行时间为常数，可忽略不计。适应度函数需计算每个个体在N_s个时隙下所有波束间的干扰和，因此复杂度为O(N_g×N_s×N_b²)。染色体自交叉操作是随机过程，由于引入二次交叉概念，单个个体的自交叉概率为p₁×p₂，其复杂度为O(p₁×p₂)，则种群所有个体自交叉的时间复杂度为O(N_g×p₁×p₂)。由于p₁、p₂均小于1，所以染色体自交叉过程的复杂度小于适应度函数计算过程。因此，改进遗传算法的时间复杂度为O(M×N_g×N_s×N²_b)。

3 仿真与结果分析 3.1 系统场景设置

为验证上述资源调度方案的有效性，对一颗LEO卫星的BH分配过程进行仿真。首先使用H3搭建2种用户模型，区别在于需求分布是否均匀。然后对2种分布的用户进行TSA讨论。最后在不同小区波束比的条件下，验证遗传算法对于同频干扰的优化。系统具体参数如表 3所示。

3.2 性能分析

波束调配的第一阶段是对需求的分簇，各波束所分需求是否相等对总时延有着较为明显的影响。由图 7可知，在同一组用户数据包待传输且TSA方式相同的前提下，需求均分的总时延均值为2.05 ms，不均分时延在3.63 ms左右。此外，通过对不同泊松到达的数据流仿真，需求均分方式下时延方差约为0.001 4，而不均分最高达到0.338 4，可知需求均分的时延更为稳定；而不均分的分簇，时延受每个时刻等待传输的具体数据包数量影响较大，稳定性能较差。

由上述分析可知，选择均分的需求分簇方式使系统时延较小，可将时延平均减少43%。分簇完成后，需要对每个簇内的需求进行TSA，不同的分配方式影响着系统平均排队时延和终端的接入次数。本文通过对不同的用户分布格局进行仿真，探究TSA对时延的影响，结果如图 8所示。其中数据集1的小区需求差异较大，分布不均；数据集2的需求近似且分布均匀。从图 8可以看出，不论是哪种用户分布，SSE下的排队时延明显优于其他2种方式。均分情况下SSE相较于MSNE和NHS时延分别降低4.2%和8.2%。但与MSNE相比，因为每个时隙都会发生波束跳变，使用SSE终端的波束接入次数更加频繁。

考虑到部分地区的用户分布极为不均，高需求小区的通信队列可能远远长于低需求小区，其排队时延也会相对较长，因此根据需求分配时隙是相对公平的选择。表 4展示了SSE和MSNE 2种分配方式对不同用户分布下的最高需求和最低需求的时延对比。时延比越小，说明公平性越好。表中白色数据是数据集1的部分时延表征，其卫星覆盖范围内用户需求差异较大；灰色数据取值于数据集2，用户分布相对均匀。由表 4可以看出，2种情况下MSNE的公平性均优于SSE，且在用户分布极度不均时，MSNE对时延比的优化效果更为明显。

综合比较图 8和表 4，可以看出MSNE和SSE 2种TSA方式各有优缺点。在一个资源调度周期内，使用SSE系统平均排队时延较低；但对于用户需求极度不均的情况，MSNE方式可以减少终端的接入次数以及提高不同用户间的通信公平性。因此，面对实际的用户场景，可以根据需求选择合适的方法。

接下来对完成TSA的波束簇使用改进遗传算法进行BPM，并选取随机匹配和模拟退火^[20]的方法作为对比算法。其中模拟退火算法主要步骤为：1)初始温度下随机生成初始解，即一种需求与波位的随机匹配结果，并计算与干扰相关的适应度函数；2)扰动生成新解，计算适应度增量Δ，若Δ < 0，接受增量，反之根据Metropolis准则有条件接受；3)按照衰减函数降温，重复上一个步骤；4)当温度降至终止温度时，终止循环，得到最优解。

对不同的小区波束比，为小区需求随机生成1 000种泊松到达的组合，取所有结果的平均值作为时隙干扰和，仿真结果如图 9所示。由图可知，不同小区波束比情况下，改进遗传算法的干扰优化结果均优于其他2种方法，相较于模拟退火，遗传算法时隙干扰和降低约32.2%，相比于随机匹配，降低约58.1%，且不会随着小区波束比增加而升高。

4 结论

本文针对LEO卫星一个资源分配周期内的波束调度问题，以排队时延和同频干扰最小化作为优化目标建立资源调度优化模型。通过对问题的解耦合提出TDC、TSA和BPM的调度策略，并对每一步设计合适的优化算法，形成一套关于BH时隙和点位分配的完整策略。首先，对卫星覆盖范围内的所有需求采用均分的方法分簇；然后，根据实际用户需求，选择SSE或MSNE的TSA方式；最后通过改进遗传算法对需求与波位进行匹配。仿真结果表明，本文提出的方案可以使波束在资源分配周期内完成调度，且验证了改进遗传算法的有效性，实现时延和干扰的双重优化。