基于智能水滴算法的卫星信道资源调度研究

段超凡，王 锐,2

（1.国防科技大学气象海洋学院，长沙 410073；2.国防科技大学信息通信学院，武汉 430019）

0 引言

随着航天技术、材料技术、微电子和通信技术的不断发展，卫星作为空间信息获取的主要载体已经受到了业界的广泛关注，从功能角度可以分为通信卫星、遥感卫星、环境探测卫星和导航卫星等。自1957 年苏联发射了第一颗人造卫星斯普特尼克1号起，世界各国在争夺卫星空间资源上各展其能，发射了各式各样的卫星。

通信卫星作为空间卫星通信系统的重要组成部分，可以为地面用户提供良好的信息传输服务功能。单颗部署于地球同步轨道的卫星可以覆盖40%的地球面积，3颗卫星即可实现全球覆盖，使覆盖区域内处于任何位置的用户可以通过卫星实现实时通信，特别是对于基站难以覆盖的海上及偏远地区，卫星通信可以为这部分用户提供良好的通信服务。然而，由于卫星的星上资源有限，当地面用户的信息传输需求较大、超出卫星可最大服务用户的能力时，需要制定相应的策略，优先传输重要的信息。特别是针对多波束卫星，如何分配有限的卫星资源和卫星天线给完成不同优先级的信息传输任务，是卫星信道资源调度问题研究的重点。

研究人员针对上述问题提出了一系列的解决方法，通过地面指控中心集合各类信息传输需求提高卫星面对突发情况的快速响应能力，通过指控中心与卫星间的配合最大化完成信息传输任务。赵静等利用改进的NSGA 算法对微波/激光混合链路的多目标资源调度进行了研究，实验证明了该方法的有效性；田志新等提出利用有向图模型在线生成任务指令；贺川等利用最小时间窗口约束，将不同任务分配至不同的时间窗口。其他研究人员将信道资源调度问题抽象成整数规划模型、被曝模型和其他模型进行求解，均取得了较好的实验结果。

本文针对卫星信道资源调度问题，构建了多目标约束规划模型，利用智能水滴算法对该问题进行求解。在建模过程中考虑了不同用户的优先级和数据传输任务的特点，并对所提出的算法进行了实验验证。仿真结果表明，该算法能够为卫星分配合适的数据传输任务，有效解决卫星信道资源调度问题。

1 问题描述及建模

卫星信道资源调度问题受到信息传输任务的数量、优先级及任务时间窗等因素的约束，同时还需考虑到可用的卫星集合和有限的卫星天线及信道资源约束，可以抽象成多目标约束问题。解决该问题的主要思想是尽可能完成任务优先级较高的信息传输任务，并在此基础上尽可能多地完成信息传输任务，为了方便模型建立，作出如下定义：

记S为卫星节点，对于所有卫星节点，可表示为：

其中，表示可用的卫星数目。同时对于单颗卫星，根据卫星星上性能，构造其状态信息：

其中，为该卫星所分配的数据传输任务，为卫星天线资源集合，包含天线数目和数据传输速率，为卫星存储能量，每执行完一次数据传输任务需要消耗一定的星上能量。

记M为需要完成的数据传输任务，对于所有需要完成的任务，可以表示为：

其中，代表需要完成的数据传输任务数目。对于每个需要完成的数据任务，根据任务需求，构造其任务状态信息：

对于每个需要完成的传输任务，T,T分别为任务开始时间和任务结束时间，卫星需要在任务开始后，在任务结束前完成信息传输任务；t为执行该任务的任务开始时间；d为任务传输时间；p代表任务的优先级；E代表传输该任务所需要花费的星上能量；x表示该任务是否被执行，若任务被执行则x= 0，否则x= 1。

基于上述定义，建立卫星资源调度的多目标约束模型：

在本文中，优化的目标是优先完成优先级高的数据传输任务，也就是最小化不能完成任务的总共的优先级，共有三个约束条件。其中，约束条件1 代表每个数据传输任务只被完成一次；约束条件2代表卫星在执行数据传输任务前需要满足剩余能量约束；约束条件3代表每个任务的开始执行时间和完成时间需要在任务时间窗的范围之内。

2 基于智能水滴算法的卫星信道资源调度

智能水滴算法（intelligent water drops algorithm，IWD）是由Hamed Shah-Hosseini 于2007年提出的一种群体智能算法，该算法的设计思想来源于自然界中水流的运动。若只考虑重力对水流的影响，水滴将会从高处流向低处，水滴的运动轨迹是一条从起始点到终点的直线路径。然而在水滴的运动过程中会受到阻力和障碍物的影响，改变路径轨迹。在前人的研究工作中，智能水滴算法已经被应用于工程科学领域等众多问题的求解中，显示出巨大的优势。

在自然界中，若不存在阻力和障碍物的影响，水流的路径将是一条理想路径，同时该从起点到终点的直线是最短路径，并且当水流受到障碍物的影响时，也会使改变的路径尽可能地接近于理想路径。每个水滴在进行路径选择时，将会受到路径中障碍物的影响，在该算法中考虑的是路径中的泥土量。路径中的泥土量越大，路径对水滴的阻力效果越大，水滴选择这条路径的概率也就越低。同时，当水滴经过路径时将会带走部分路径中的泥土量，使得后续水滴在进行路径选择时更有可能选择这条路径。水滴在进行路径选择时将根据概率选择下一步运动的路径，这在一定程度上避免了算法陷入局部最优。智能水滴算法主要分为四个阶段，分别是初始化阶段、路径选择阶段、局部泥土量更新阶段和全局泥土量更新阶段。

2.1 初始化阶段

在初始化阶段中，需要确定可利用进行数据传输的卫星集合，所需完成的数据传输任务集合，以及对应的相关参数；智能水滴的个数N，智能水滴的初始速度v，速度更新参数a、b、c，泥土量更新参数a、b、c，局部泥土量更新参数，全局泥土量更新参数和路径泥土量矩阵。

2.2 路径选择阶段

将每个卫星当做一个智能水滴，在初始状态时，每个卫星根据其拥有的天线数量及信道资源随机选取一个任务进行数据传输，并对应更新信道占用情况和任务执行情况。每个任务都被视作为路径中的节点，节点的选择概率计算为：

其中，为非负数，为防止该值为0。

根据每个备选节点（下一个可执行的数据传输任务）的选择概率，采用轮盘赌注的方法去选择下一个任务节点，并更新已访问节点和未访问节点。当前卫星的天线及信道资源被全部分配完成后，则构建生成了该卫星的任务调度方案，将剩余未执行的数据传输任务分配给后续各卫星直至生成所有的卫星任务分配方案，并计算各方案对应的目标函数值。

2.3 局部泥土量更新阶段

完成节点选择后，水滴将访问该节点。节点间的泥土量、水滴速度和卫星剩余星上能量等都将发生变化。假设在时刻，水滴位于节点p，并且在+1时刻运动到节点p，水滴的速度变化计算为：

路径中的泥土量变化为：

其中，Δ(p,p)为泥土量的变化量，ρ为局部泥土更新参数，是介于0到1的一个常数。

同时，水滴携带的泥土量更新为：

该值的计算由水滴的运动速度和运动时间共同决定，表示如下：

2.4 全局泥土量更新阶段

在每一次迭代中，根据水滴构成的可行解，计算目标函数值，并找到目标函数值最小的解作为该次迭代过程中的最优解，并将最优解路径中的泥土量矩阵作为下一次迭代的初始泥土量矩阵，全局泥土量更新计算为：

这样，在每一次迭代过程中都能获得本次迭代的最优解，并且将之与历史最优解进行对比，若获得的目标函数值小于全局最优解，则进行更新，当运行到最大迭代次数时，可以获得该问题的最优解输出。

3 仿真实验及结果分析

利用Maltab 仿真软件对所提出的卫星资源调度算法进行了实验验证，所设计的实验场景中包含3颗卫星用于完成数据传输任务，三颗卫星的天线数据传输速率分别为200 Mb/s，300 Mb/s和500 Mb/s，总共数据传输任务为64 个。仿真实验分别对每次迭代过程中未完成的任务数、任务执行时间等进行了分析。

从图1可以看出，随着迭代次数的增加，未完成的任务权值数逐渐减少。由于卫星天线及信道资源有限，难以做到完成所由任务，算法通过不断迭代有效降低了未完成任务的权值，达到了预计目标。

图1 未完成任务权值图

由于不同卫星的信息传输能力有所差异，传输能力强的卫星可以在较短时间内完成信息传输任务，但是在实验场景中仍不能通过单颗卫星完成所有的信息传输任务，需要通过3颗卫星共同配合减少总任务完成时间。从图2可以看出，随着迭代次数的增加，任务执行时间逐步降低。

图2 任务执行时间图

图3为任务执行甘特图，不同颜色色块代表卫星的任务执行次序，可以看出算法所规划的信息传输任务能够较好地利用卫星资源，保持各任务间不发生冲突的同时，最大化地利用有限的卫星资源。

图3 任务执行甘特图

4 结语

本文提出了基于智能水滴算法的卫星信道资源调度算法，在可以利用的卫星资源有限的情况下，优先执行任务优先级较高的数据传输任务，在保证数据传输任务不冲突的情况下，尽可能多地完成任务。所提出的智能水滴算法分为数据初始化、路径选择、局部泥土量更新和全局泥土量更新四个阶段，通过不断迭代优化调度方案，最后利用实验证明了算法的有效性。