基于改进QPSO算法的GEO卫星时频资源调度

高 威，瞿连政，王 磊

(国防科技大学 信息通信学院，湖北 武汉 430014)

0 引言

静止轨道(Geostationary Orbit,GEO)通信卫星具有通信覆盖区域大、通信距离远、性能稳定、可在边远地区部署、不依赖于地面基础设施等优点，在国际国内通信、军事通信和移动通信等领域具有重要的作用[1]。随着通信任务需求的增多，不同用户间的通信请求可能存在时间窗口和频带冲突，对于短时间内的大量任务请求，手动计算卫星资源的调度方案变得非常复杂[2]。在卫星资源有限的情况下，如何设计有效的资源调度模型和算法来提高时频资源调度效率，保障通信任务完成并最大化系统效能成为当下研究的热点问题。

在调度模型与算法方面，文献[3]建立了基于任务资源匹配的整数规划模型，使用蚁群算法进行了求解；文献[4]采用任务优先级和时间灵活度加权的启发式信息，提出了加入虚拟任务的改进蚁群算法，具有较好的寻优能力和稳定性；文献[5]在max-min蚁群系统的基础上，提出了一种简化蚁群优化算法，设计了新的信息素模型使得算法具有更平衡的探索能力和开发能力；文献[6]分析了静态调度模型和动态调度模型的调度目标和约束条件，采用了改进的海洋捕食者算法求解卫星的任务调度；文献[7]将卫星资源调度问题转化为任务排序问题，并利用遗传算法求解最优任务序列。

在调度策略方面，文献[3]采用基于任务和资源优先级的“任务-资源”匹配规则；文献[4]提出了时频资源窗口更新方法，按照“低频带优先，时间靠前优先”的原则分配时频资源，但该方法计算复杂度较高；文献[7]采用时间步长调整的方式进行任务资源的匹配；文献[8]采用基于任务时间窗口更新的调度策略，分析了5种不同的时间窗口冲突情况，并给出了剩余任务时间窗口的更新方法；文献[9]将蚁群算法的路径点设置为任务的时间片，并设计了带偏好的卫星时间片切割策略。

综上所述，现有研究主要是将一维时间窗或二维时频块作为调度资源，采用以任务资源窗口更新[4,8-9]和任务资源匹配规则为核心的调度策略，建立数学规划模型或约束满足问题(Constraint Satisfaction Problem,CSP)模型，并利用改进的蚁群算法[3-5,9]、海洋捕食者算法[6]和遗传算法[7-8]等元启发式算法(Meta-heuristic Algorithm)进行求解。综合来看，任务资源窗口更新方法的计算复杂度较高；离散化编码的元启发式算法易陷入局部最优，而全局性能更好的连续型元启发式算法则不能直接用于时频资源调度问题，需要采用合适的编解码规则。针对GEO通信卫星的时频资源调度问题及现有研究存在的不足，本文所做的工作如下：

① 将卫星转发器的二维时频资源进行量化处理，建立了基于CSP的卫星时频资源调度模型，并设计了以任务序列生成和任务资源匹配为主要步骤的调度流程；

② 针对任务资源窗口更新方法计算复杂度高的问题，提出了基于资源矩阵更新的调度策略，将任务资源匹配过程转化为矩阵的Hadamard乘积计算，有效降低了任务资源匹配的计算复杂度，缩短了算法的执行时间；

③ 针对常用的蚁群算法和遗传算法易陷入局部最优的问题，提出了改进的量子粒子群算法，采用了实数编码、最小位置值解码和初始解优化方法，提升了算法的全局优化性能；

④ 对所提调度策略和改进算法进行了仿真实验，分析了不同量化带宽和调度策略对执行时间、调度结果的影响，对比分析了本文所提算法与当前几种典型的时频资源调度算法的性能差异。

1 GEO通信卫星资源调度模型

1.1 问题背景

从用户的角度，当用户组网通信时，首先需要向卫星资源管理中心提交任务申请，提交信息包括用户位置、用网时间、申请带宽、业务类型及终端信息等，然后等待卫星资源管理中心分配资源并使用分配的资源开展通信业务；从卫星资源管理中心的角度，调度系统需要管理资源池和任务池，接收多个用户的任务资源申请，并根据资源池和任务池状态，选择合适的调度模型和调度算法进行资源调度，生成优化调度方案[6]。因此，决定资源调度性能的关键是调度模型和调度算法。通信卫星资源调度的架构如图1所示。

图1 通信卫星资源调度架构

将调度问题按调度周期进行划分，并对调度资源采用量化处理，其中调度周期的长度和通信资源划分的粒度可以灵活调整，以适用于不同的问题场景。从资源管理和分配的角度，卫星管理中心的资源调度系统主要进行的操作有：

① 执行上一周期结束时生成的调度方案。

② 监控资源池中资源的状态，将执行完任务后被释放的资源更新到资源池，对资源的状态进行标记。资源状态分为占用、已分配待使用、空闲和不可用等。

③ 监控任务池中任务的状态，删除无法执行的任务，接收新任务申请并更新到任务池。对任务的状态进行标记，分为执行结束、执行中、已分配资源待执行、拒绝执行和新接收待分配资源等。

④ 在调度周期结束时依据任务池、资源池状态，选择调度模型和调度算法进行资源调度，生成下一个周期的调度方案。

本文所研究的GEO通信卫星时频资源调度模型、算法及策略，主要适用于2种场景：① 在使用大张角波束的传统宽带通信卫星场景中，对固定的组网通信业务进行任务规划和资源调度；② 在使用多波束技术的高通量卫星场景中，可根据波束覆盖用户的情况，将多波束的资源调度问题分解为各个单波束内的资源调度子问题，实现对时隙和带宽资源的联合调度。主要聚焦于对第1个场景进行研究，但二维资源量化的框架与元启发式算法的应用模式，可以应用于第2种问题场景；在调度资源上，聚焦于时频资源调度，即时隙-带宽资源块与任务的匹配，而简化中心频率设置、载波分配或信道划分等情况。

1.2 时频资源量化

卫星转发器的资源存在时间、频率、功率等多个调度要素，本文以经过量化的二维时频资源作为调度资源。时频资源的量化处理方式[4,7-8,10-12]可适用于多种技术体制，如频分多址、时分多址和多频时分多址(Multi-frequency Time Division Multiple Access,MF-TDMA)等。

设定任务集合T与卫星转发器资源集合S是严格对应的。可将单波束覆盖范围内同频段用户终端的任务请求整合为任务集，而将该波束内的单个或多个转发器的可用时频资源整合为资源集。要求任务提交的资源申请以资源最小量化分辨率为单位，并表示为时频区间的集合。转发器的时频资源如图2所示，以1 MHz和1 h进行量化时，资源集可表示为{[0,4],[0,5]}，其中任务4占用的资源块可表示为{[1,3],[1,2]}。因此，可将时频资源调度问题抽象为数学上的二维装箱问题，该问题已被证明为是一个NP-Hard问题[13]。

图2 转发器的时频资源

本文主要研究无突发情况的静止调度场景，即不考虑卫星故障、任务插入和任务取消等突发情况。问题场景的基本假设为：① 调度期间所有待调度任务的用户均在转发器所属波束的覆盖范围内，且通信质量良好，不考虑用户终端的移动性；② 任务申请的时频资源块个数必须为整数，任务不能被分割执行；③ 任务经过调度尝试后的状态分为调度成功和调度失败2种，将调度成功的任务优先级之和作为调度效能指标，即调度收益；④ 当任务分配的时频资源不存在冲突时，转发器可同时执行多个任务。

1.3 基于CSP的调度模型

CSP可以描述为：给定一组变量及它们的值域，找到一个满足所有约束的变量的解，并尽可能使解的质量更优[14]。基于CSP的调度模型所使用的符号如下：

S={B,TE}表示转发器的时频资源总量；

B=[Bstr,Bend]表示转发器的频率资源；

TE=[TEstr,TEend]表示转发器的时间资源；

RS={BS,DS}表示任务所需的带宽资源和时间资源，BS和DS分别表示未经过量化处理的带宽大小和时间长度；

Nb=(Bend-Bstr)/δB表示转发器资源进行量化后的频带个数，δB表示量化频带的带宽；

Nt=(TEend-TEstr)/δt表示转发器资源量化后的时间区间个数，δt表示量化时间的间隔；

T={T1,T2,…,Tj,…,TM}表示任务的集合，M为任务数量；

则基于CSP的卫星时频资源调度问题可以描述为一个变量、值域和约束的三元组：

SCH=〈X,D,C〉，

(1)

基于CSP的GEO通信卫星时频资源调度模型可以描述如下：

(2)

(3)

模型的目标函数设为最大化任务优先级之和，即调度成功的任务优先级之和越大，该调度方案的收益越高。其中，约束Cb表示频带资源限制约束，即分配给任务的起始频带必须在转发器的频带资源之内，同时必须留有任务执行所需带宽的余量；约束Ct表示时间约束，即分配给任务的时间区间必须在任务申请执行的时间范围之内；约束Ce表示资源冲突约束，即不同任务占用的资源块不能重叠。

2 基于资源矩阵更新的调度策略

针对传统的基于任务资源窗口更新[4,8]的调度策略计算复杂度高的问题，本文提出一种基于资源矩阵更新的调度策略，采用矩阵形式表示转发器的时频资源、调度方案和任务时频窗口，而将任务资源匹配过程转化为矩阵的乘积计算。

2.1 资源矩阵表示

将可用时频资源表示为一个m×n的0-1矩阵：

(4)

式中，m=Nb为量化频带的数目；n=Nt为量化时间的数目。rij=1表示资源块{[i-1,i],[j-1,j]}已被占用，为0则表示资源块空闲。将调度方案也表示为一个矩阵：

(5)

(6)

式中，ikjk为任务k在第ik个频带上的第jk个时频窗口矩阵。则任务k的时频窗口矩阵集可以表示为：

(7)

图3 任务的时频窗口矩阵集

2.2 资源矩阵更新

(1)当对任务k进行调度时，首先根据资源矩阵状态和任务需求特性判断任务k在第ik个量化频带的调度可能性：

(8)

(2)逐个取出任务k的时频窗口矩阵集中频带编号为ik的窗口矩阵，并将窗口矩阵与资源矩阵R做Hadamard乘积(即矩阵对应位置相乘)，并根据乘积矩阵E进行调度状态判断：

(9)

(10)

(3)每成功调度一个任务，则对该任务所在任务序列的资源矩阵和方案矩阵进行更新：

(11)

例如，有任务序列{5,2,1,4,…}，其中任务4的属性为{3,2,2,1,4}。假设已成功调度任务5,2,1，当任务4调度成功后，资源矩阵和方案矩阵更新方法如图4所示。

图4 资源矩阵和方案矩阵的更新

基于资源矩阵更新策略的调度流程为：

① 由元启发式算法生成任务序列，初始化该任务序列的资源矩阵和方案矩阵；

② 按任务序列的顺序依次选择任务，计算该任务的时频窗口矩阵集；

③ 按照式(8)判断任务的调度可能性，若不具备调度的可能性，则返回②；

④ 若具备调度可能性，则借鉴二维装箱问题中的BL准则[15]，按照“低频带优先，频带相同的时间靠前优先”的原则依次取出时频窗口矩阵，依据式(9)和式(10)检查是否可以调度；首次出现满足调度条件的时频窗口后，记录调度状态，并按式(11)更新资源矩阵和方案矩阵，转向②；

⑤ 所有任务遍历完毕后，输出该任务序列的调度方案，并计算调度收益和任务完成情况。

2.3 计算复杂度分析

(12)

对于单个任务序列T=[Ti]1×M，调度完M个任务所做的资源窗口更新操作次数的最大值为：

(13)

(14)

(15)

对于单个任务序列T=[Ti]1×M，调度完M个任务所做的调度判断次数和尝试次数的最大值为：

(16)

3 GEO通信卫星资源调度算法

量子粒子群算法是由文献[16]提出的一种优化算法，与标准PSO算法相比，该算法的优点是参数少便于控制、寻优能力较强，缺点是不适用于离散组合优化问题、初始解质量不高。在该算法的基础上，本文提出一种改进的量子粒子群优化(Improved Quantum-behaved Particle Swarm Optimization，IQPSO)算法，用于求解通信卫星时频资源调度问题。

3.1 改进的QPSO算法

3.1.1 编解码方式

为使QPSO算法能够解决离散组合优化问题，在粒子编解码上分别采用实数编码和最小位置值规则[17]解码。设粒子长度D等于任务数量M，对粒子进行实数编码，并利用连续域的粒子群进化方法进行种群更新；解码时，粒子第k个位置的值对应任务k的排序优先值，按优先值由小到大对任务进行排序，生成任务序列。

设粒子i的位置向量Xi=(xi1,xi2,…,xiM)，对应的解码向量即任务序列πi=(πi1,πi2,…,πiM)，利用粒子位置更新式进行位置更新后，粒子位置向量为：

X′i=(x′i1,x′i2,…,x′iM)，

(17)

则对应的解码向量为：

π′i=(π′i1,π′i2,…,π′iM)。

(18)

基于最小位置值的解码方法如图5所示。设种群中有粒子向量(此时M=6):(0.87,0.34,1.02,1.65,1.13,0.76)，则可生成对应的任务序列(2,6,1,3,5,4)，此任务序列对应的调度收益即为该粒子的适应度值。

图5 基于最小位置值的解码方法

3.1.2 初始解优化

(19)

设任务k的加权优先级为：

(20)

即任务的优先级越高，则加权优先级越高；任务优先级相同时，占用资源越少则加权优先级越高。初始种群中，粒子i的初始位置Xi的生成方法为：

Xi=(xi1,xi2,…,xik,…,xiM)，

(21)

(22)

式中，[Xmin,Xmax]表示粒子每一维搜索空间的取值范围。初始粒子种群中，加权优先级越高的任务初始位置值较小的概率越高，生成任务序列时位置靠前的概率越高。由于按任务序列调度具有“先到先占”的特点，加权优先级高的任务有更高概率被成功调度，因此相比于随机法能够生成更高质量的初始解，有助于加快算法的收敛。

3.1.3 种群进化

算法的种群进化方法[16]如下：

atri(t)=r1·Pi(t)+(1-r1)·G(t),r1～U(0,1)，

(23)

(24)

(25)

式中，u～U(0,1)表示随机因子；Pi(t)和G(t)分别表示个体最优位置和全局最优位置；atri表示粒子i的吸引子，该位置综合了个体信息和群体信息对粒子搜索的指导作用；C(t)表示每代种群的平均最优位置，该位置体现了算法的个体信息协作机制。

α称为收缩-扩张系数[16]，是算法中除种群数量、粒子维数和迭代次数以外唯一的参数。合理控制α能够调节算法的全局搜索能力和局部搜索能力，改善算法性能。文献[16]提出了固定参数和线性递减2种控制策略，并指出当系数维持较大的值时，算法跳出局部收敛的能力更强。系数递减策略如下：

(26)

式中，α2和α1表示收缩扩张系数的最大值和最小值；iter和Gmax表示算法的迭代次数和最大迭代次数。

3.2 基于IQPSO算法的调度流程

基于IQPSO算法的时频资源调度流程如图6所示。

图6 基于IQPSO算法的时频资源调度流程

基于IQPSO算法的时频资源调度流程为：

① 输入调度场景参数和算法参数，按照初始解优化方法生成初始粒子种群；

② 按照最小位置值解码规则对粒子进行解码，生成任务序列矩阵；

③ 逐个对任务序列进行调度，生成各粒子的调度方案并计算各调度方案的收益，即为对应的粒子的适应度值；

④ 更新种群中粒子的个体最优位置和全局最优位置；

⑤ 按照式(23)和式(24)计算粒子的吸引子位置和个体平均最优位置；

⑥ 按照式(25)更新粒子的位置，生成下一代种群；

⑦ 判断算法的迭代终止条件，若不符合则转向②；若符合则结束算法的执行；

⑧ 输出资源调度结果。

4 仿真实验

4.1 仿真场景和参数设置

仿真场景选择GEO通信卫星Ku频段转发器,带宽资源总量为48 MHz，调度时间周期为24 h，最小量化带宽为1 MHz，最小量化时间区间为1 h，则最小量化时频资源块的总量为1 152个。任务集的生成方法参照了文献[4]，以任务集中任务k为例描述如下：

② 任务的申请带宽(单位MHz)在取值范围内随机生成，但需要做向上取整的处理，即不足1 MHz的部分按1 MHz处理，并假设任务的最大可申请带宽为16 MHz，则申请带宽的值域为：{1,2,…,16}。申请时间区间的长度也相同方法进行处理，申请时间区间的值域为{1,2,3,4}。

⑤ 任务数量分别设置小规模(30)、中规模(50,80)和大规模(100)共4种情况，实时任务占比为20%。每种数量规模分别随机生成5个任务集，共20个任务集，且确保每个任务集的平均优先级均为5.5。而后按照1 MHz和8 MHz的量化带宽分别生成20个算例，共40个算例。其中，以任务数量为100的10个算例为例，其基本特性如表1所示。

表1 算例的特征

4.2 计算复杂度对比分析

为了分析资源矩阵更新(Resource Matrix Update，RMU)方法对资源匹配过程的计算复杂度的影响，并与传统的任务资源窗口更新方法(Task Resource Window Update，TRWU)进行比较，使用以下算法进行对比分析：

① 基础蚁群算法ACO[18]；

② 由文献[4]提出的改进蚁群算法ACO-TB(Ant Colony Optimization based on Time and Bandwidth)；

③ 由文献[8]提出的改进遗传算法GA；

④ 标准粒子群算法PSO[19]；

⑤ 本文提出的使用RMU的改进算法IQPSO。当使用TRWU方法时，记为QPSO(TRWU)。

每种算法分别使用TRWU和RMU方法进行实验，各算法的参数如表2所示。

表2 算法的参数

算法的种群数量设置为与任务数量相等，迭代次数均为100次。在量化带宽为1 MHz和8 MHz的情况下，分别对30,50,80,100个任务的5个算例运行10次并取算法执行时间的平均值，结果如表3、图7和图8所示。

表3 不同算法的平均执行时间

图7 不同算法的平均运行时间(量化带宽1 MHz)

图8 不同算法的平均执行时间(量化带宽8 MHz)

由表3、图7和图8可以看出：

① GA，PSO和IQPSO算法的执行时间基本相近，且均小于相同条件下的ACO和ACOTB，说明这3种算法在计算复杂度上要低于ACO和ACOTB。

② 相比于TRWU方法，算法在使用RMU方法时，执行时间均有效降低。当量化带宽为8 MHz，同一算法使用RMU和TRWU方法时，所获得的执行时间的改善幅度为51%～84%；当量化带宽为1 MHz时，这一改善幅度为82%～88%，可见本文所提的RMU方法在处理大量冲突时具有更明显的优势。

③ 不同的量化带宽对执行时间也有较大影响。当量化带宽由8 MHz变为1 MHz时，算法使用TRWU的执行时间增加5.6～9倍，使用RMU的执行时间增加2～-6.7倍。这是由于提高量化带宽分辨率后，任务间冲突加剧，导致算法的执行时间大幅增加。

④ 本文提出的IQPSO(RMU)相比于主要对照算法ACO-TB(TRWU)，在1 MHz量化带宽下，时间改善程度为88%～91%，在8 MHz量化带宽下，时间改善程度为80%～89%，可见本文算法能够有效降低现有调度算法的计算复杂度，缩短算法的执行时间。

4.3 算法优化性能分析

本小节设置算法终止条件为阈值条件，即设最大、最小迭代次数为200和100，当算法的优化解连续50次迭代没有改善时，则终止算法执行。ACO，ACOTB依照文献[4]以及GA依照文献[8]的设置均采用TRWU方法，PSO，IQPSO则采用本文提出的RMU方法。以8 MHz量化带宽为例，使用5种算法对20个算例运算10次并取平均值，结果如表4所示。

表4 算法的优化结果(量化带宽8 MHz)

由表4可以看出：

① 本文所提IQPSO算法在4种任务规模下，调度收益的平均值和最优值均为最优；

② IQPSO在任务数量30，50和GA算法在任务数量为80，100时，完成任务数量指标最优，推测GA算法更善于处理占用资源块较少的任务，因此能够实现更多任务的调度；

③ 执行时间指标上，PSO和IQPSO在所有任务规模情况下为最优。当任务规模增大时，PSO由于陷入局部最优，因此迭代次数和执行时间均低于IQPSO，但调度收益和完成任务数量也更差。在相同任务规模情况下，IQPSO的平均执行时间为ACOTB的12%～14%，GA的20%～22%。

综上，IQPSO算法对比现有几种算法，可以在更短的执行时间内，在调度收益指标上取得更优的结果，同时完成任务数量也较好。

以任务集100_1和100_6为例，分别采用了1 MHz和8 MHz的带宽量化方式，5种算法分别执行10次并取最好的一次结果，其收敛曲线如图9所示。

图9 最佳执行的收敛曲线

由图9可以看出：① 在相同量化带宽情况下，PSO算法由于缺乏针对性的优化机制，易陷入局部最优解，ACO-TB和GA算法持续优化能力较强，本文所提IQPSO算法的全局优化能力则相对更优，能够不断跳出局部收敛；② 对同一任务集生成的算例100_1和100_6，当量化带宽由8 MHz变为1 MHz时，各算法的调度收益均得到有效提升，可见较小的量化尺度能够发现更多的资源碎片加以利用，但结合表4可知，提升量化带宽分辨率也会带来执行时间的增加。

量化带宽为1 MHz和8 MHz时，算法调度完成的任务数量如图10和图11所示。

图10 算法调度完成的任务数量(量化带宽1 MHz)

图11 算法调度完成的任务数量(量化带宽8 MHz)

由图10和图11可以看出：① 从任务规模看，当任务规模较小(30)时，各算法完成任务数量基本一致，且由于资源相对充足，任务间资源冲突相对较少，任务完成率接近100%。当任务规模增大时，随着任务资源需求和任务间冲突增加，完成任务数量虽提升，但完成率总体在下降。② 从算法对比来看，IQPSO和GA能够调度成功更多的任务数量，ACOTB次之，而ACO和PSO相对较差。③ 从量化带宽看，同等任务数量情况下，量化带宽为1 MHz时算法的调度方案能够完成更多的任务。

5 结束语

本文针对GEO通信卫星时频资源调度问题，提出了以资源矩阵更新为核心的调度策略，相比于传统的任务资源窗口更新方法，有效降低了计算复杂度，在同等条件下使算法执行时间减少51%～88%。在此基础上，设计了采用实数编码、最小位置值解码和初始解优化的IQPSO算法，对比ACO-TB[4]和GA[8]算法，在提升优化解质量的同时，算法执行时间减少78%～88%。本文所提的调度策略和改进算法对于利用连续型元启发式算法解决通信卫星时频资源调度问题具备一定的参考意义。通过本文的工作可以发现，单目标优化情况下，算法对调度收益和任务完成数量2个指标并不能很好的兼顾，下一步将主要针对多目标情况下的卫星资源调度问题进行研究。