基于人工蜂群算法的中继卫星任务调度研究

2015-10-14开彩红

电子与信息学报 2015年10期

开彩红肖瑶方青

基于人工蜂群算法的中继卫星任务调度研究

开彩红*①肖瑶①方青②

①(合肥工业大学计算机与信息学院合肥 230009)②(中国电子科技集团公司第三十八研究所合肥 230031)

研究中继卫星任务调度问题可以为跟踪与数据中继卫星系统(TDRSS)的任务计划编排提供科学合理的决策方法，任务调度模型的建立与调度算法的设计是中继卫星任务调度的两个关键问题。该文针对中继卫星任务调度问题特点，综合考虑中继卫星与用户航天器之间具有可见时间窗、用户提交的任务属性、中继卫星前向资源受限等约束条件，建立了中继卫星任务调度约束规划模型并提出基于人工蜂群(ABC)算法的中继卫星任务调度算法。最后，通过仿真数据分析，表明基于人工蜂群算法的中继卫星任务调度算法是一种有效的、合理的调度方法。

中继卫星任务调度；可见时间窗；任务属性；约束规划模型；人工蜂群算法

1 引言

跟踪与数据中继卫星系统(Tracking and Data Relay Satellite System, TDRSS)是指通过位于地球同步轨道的中继卫星，为中、低轨道的航天器与航天器之间、航天器与地面站之间提供数据中继、连续跟踪与轨道测控服务的系统。中继卫星任务调度是指系统管理中心根据用户提出的服务申请，合理地分配中继卫星系统资源，并在资源冲突时进行优化调度，以完成尽可能多的任务。随着航空航天领域中对地观测、军事侦察以及深空探测等技术的不断发展，中继卫星数据传输呈现大容量、高速率以及多样化中继任务的特点，TDRSS资源优化调度问题愈凸显得非常重要。

中继卫星任务调度问题是一个多约束的组合优化问题，需要考虑卫星间可见时间窗口、任务属性、卫星资源等方面的约束。中继卫星任务调度的目标是在满足可见时间窗口约束、任务属性约束、卫星资源有限的前提下，通过合理的安排任务执行顺序，以使得尽可能多的任务可以被成功执行，从而提高中继卫星通信资源的使用效率。近年来，出现了不少针对中继卫星任务调度模型和调度算法的研究。文献[3]是针对美国的中继卫星系统，采用并行机调度算法对中继卫星调度问题进行研究，其数学模型仅考虑中继卫星与用户航天器之间存在不多于两个可见时间窗口的情况。文献[4]是通过建立满足中继卫星约束问题(CSP)的模型，并对该模型进行求解得到调度方案。文献[5]提出一种基于任务时间灵活度的调度算法，其主要的思想是动态地调节已调度任务在时间窗口的位置，从而实现更多任务的调度。文献[6]是基于有效基因路径表示的改进遗传算法，通过定义合适的交叉与变异算子，来求解最优的调度方案。文献[7]是针对微波与激光混合链路中继卫星动态调度问题，采用启发式算法来求解最优调度方案。

研究中继卫星任务调度问题的关键在于建立有效的调度约束模型进而设计调度算法，从而能够在短时间内形成一种较优的任务编排方案，以满足工程应用需求。本文首先针对中继卫星与用户航天器之间可见时间窗约束、用户提交的任务属性和中继卫星资源的约束，建立了任务调度约束规划模型。通过合理地设计目标函数，使得规划模型以尽可能成功调度更多任务，并优先调度优先级高的任务为目标。基于所建立的中继卫星任务调度规划模型，本文提出了一种基于人工蜂群(Artificial Bees Colony, ABC)算法的中继卫星任务编排算法。通过在算法的迭代过程中对每个可行调度方案进行评估、邻域操作寻找局部最优调度方案，从而获得全局最优调度方案。最后通过仿真实验分析，表明所提算法在调度效率方面具有优势，能够有效地提高中继卫星的使用效率，且算法本身具有低复杂度的特点，因而适用于工程实践。

2 中继卫星任务调度模型

2.1 中继卫星任务调度问题描述

中继卫星任务调度是指在满足任务调度约束的前提下，在相对较短时间内得到一种最优的调度方案。中继卫星任务调度的约束包括以下几点：(1)中继卫星与用户航天器之间具有可见时间窗约束。中继卫星与用户航天器并非时时可见，只有当它们位于彼此的可见范围内，才能建立通信链路，即任务的执行时间必须在中继卫星与用户航天器之间的可见时间窗内。如图1所示，表示可见时间窗的开始时刻，表示可见时间窗的结束时刻，表示任务执行的持续时间(不包括服务准备和终止所需要的时间)。(2)任务属性约束。用户提交任务申请时，会提交任务的优先级、任务的持续时间、任务最早开始执行时间及任务最晚结束时间。进行任务调度时须考虑：执行任务的开始时间不小于任务最早开始时间；执行任务的结束时间不大于任务的最晚结束时间；当某个可见时间窗的时间长度小于任务的持续时间，由于本文所讨论的任务持续时间不允许拆分成多个子时间段，所以进行任务调度时必须选择其他时间长度比此任务持续时间长的可见时间窗(如图2所示，表示第个可见时间窗)。(3)对于中继卫星与用户航天器之间的某一条链路而言，同一时间最多只能有一个任务由该链路完成数据传输；与此同时考虑到卫星单址链路冲突的情况，在同一时刻任一颗用户航天器上最多只能有一条链路进行数据传输。

图1 中继卫星与用户航天器之间的可见时间窗

图2 可见时间窗长度小于任务持续时间

2.2中继卫星任务调度问题的约束规划模型

2.2.3任务调度模型中继卫星任务调度约束规划模型如下：

其中，适应度函数式(1)表明了调度的目标是确保更高优先级的、更多的任务能够调度成功，式中,分别代表任务的优先级和任务在该任务编排中执行时间的先后次序对适应度函数的贡献值，它们的乘积表明了优先级高的任务能够优先调度。约束条件式(2)表明若一个任务调度成功则该任务只能在一条链路上执行，否则该任务调度失败。约束条件式(3)指明在同一条链路上的所有调度成功的任务中，且表现为在这条链路上执行完任务之后执行任务，那满足这样的任务最多只能有一个，即表明了在一条链路上在同一时间最多只能为一个任务服务。约束条件式(4)确保了在同一条链路上执行的任务它们必须排成一个有序序列，也说明了一条链路在同一时刻最多只能执行一个任务。约束条件式(5)表明了调度成功的任务执行时仅能在一个可用时间窗口内进行。约束条件式(6)表明了若两个任务,(在之后执行) 在同一链路上执行时，任务的开始执行时间在任务执行完之后，进一步强调链路在同一时刻只能执行一个任务；若任务没有这层关系，由于恒成立，所以不等式式(6)仍然成立。约束条件式(7)表示两条链路,发生资源冲突时，分别在同一颗卫星的两条链路上任何两个任务均调度成功时，任务的执行时间是不能有重叠的，要么任务在任务之前执行即，或任务在任务之前执行即，表明了一颗卫星在同一时刻只能有一条链路为任务服务。约束条件式(8)和式(9)表明了调度成功任务的执行必须在一个可用时间窗内进行，其中约束条件式(8)表明任务的执行时间必须不小于该可用时间窗的开始时间即；约束条件式(9)表明任务的结束时间必须不大于该可用时间窗的结束时间。约束条件式(10)中表明任务的可执行时间必须在中继卫星与用户航天器之间的可见时间窗内，也只有在可见时间窗内才能执行任务，即进一步约束任务可执行时间。

3 基于人工蜂群(ABC)算法的中继卫星任务调度算法

3.1 人工蜂群算法概述

ABC算法是模拟蜜蜂行为提出的一种优化方法，它通过各人工蜂个体的局部寻优行为，最终在群体中使全局最优值凸显出来。该算法是一种迭代算法，算法中种群的各个个体寻找的蜜源代表一个可行解，采用适应度值来衡量该蜜源的蜂蜜含量及远近程度。通过在迭代过程中对每个解的质量进行适应度评估和邻域操作，从而得到局部的最优解，最终得到优化问题的全局最优解。ABC算法在许多优化问题中取得了成功的应用。接下来探索如何将ABC算法运用于解决中继卫星任务调度问题，并评估其调度决策的效率。

3.2基于人工蜂群算法的中继卫星任务调度

3.2.1解的描述运用ABC算法进行中继卫星任务调度时，一个解代表了所有待执行任务的一个有序排列，比如，待执行的任务共有个，则调度问题的一个解就代表了这个任务的一个有序排列(,表示任务编号，)。对解所确定的任务排列，我们进行任务编排(具体的任务编排方法见第3.2.3节)，从而确定按照解所确定的任务排序中，有哪些任务可以被成功调度，每个成功调度任务的开始执行时间等。进而，可以计算得出解所对应的适应度函数值(具体的计算方法见第3.2.2节)。ABC算法的最优解就是使得适应度函数最大的解，其对应的任务编排即为最优调度方案。

3.2.3对解()的任务编排及解的初始化在应用ABC算法进行中继卫星任务调度时，对解进行任务编排的过程就是对全体任务的有序排列(,表示任务编号)中每个任务顺次进行是否可成功调度判定、计算任务执行时间的过程。按照解()确定的任务顺序，从第1个任务开始，我们执行下述调度判定和任务执行时间计算步骤，直至第个任务。其中任务就是任务序列中第个任务，为便于描述，下面用代表任务。则对任务进行执行时间编排的步骤如下：

(5)在选择可用时间窗的过程中，若出现多个可用时间窗的开始时间相同则随机选择一个可用时间窗进行进一步判断；若遍历完该任务所有的可用时间窗也没有找到一个可用时间窗为其服务，则标记该任务调度失败。

3.2.4解的邻域操作在ABC算法搜索过程中，为了判断一个解的附近是否存在一个比当前解更优的解，需要通过某种方法获取该解，该方法称为邻域操作方法，得到的解称为邻域解。ABC算法中解的邻域操作(包括3.2.5节介绍的二次邻域操作)是一个局部寻优的过程，所以选择一个较好的邻域操作对于提高算法性能具有积极意义。通过数据仿真测试，本文采用选择一个任务随机插入的邻域操作方法。具体操作如下：从当前解中抽取一个任务，然后随机插入一个位置，这样得到的解即为当前解的邻域解，图3表示了该邻域操作方法(以编号为09的10个任务为例)。对于邻域操作产生的新解，我们可以按照第3.2.3节中介绍的任务编排方法，对从任务插入位置开始的所有任务重新进行任务编排。图4和图5表示其它两种常见的操作方法(选择两个任务交换位置法和选择个任务随机插入法)。

3.2.5解的二次邻域操作为了能够进一步提高算法找到最优解的速度，基于最优解以比较大的概率落在较优解附近的特点，我们引入了一个基于适应度值的二次邻域操作过程，即从种群中选择一些较优解，然后判断这些解的附近是否存在一个更优的邻域解。本文采用锦标赛的选择方式来选择较优的解来进行二次领域操作。即从该种群中随机抽取两个解(,)，计算它们对应的适应度值(,)。如果，选择；否则选择。

图3 选择一个任务随机插入图4 选择两个任务交换位置图5 选择k(k=3)个任务随机插入

3.2.7 ABC算法应用ABC算法进行中继卫星任务调度的步骤如下：

(2)按照第3.2.4节所介绍的邻域操作方式，为种群中每个解生成一个邻域解。如果，则设置,；否则。

(4)根据(3)得到的解邻域集合，对每个解的邻域集合进行判断。若某个解()的邻域集合是非空的，即，则从该解的邻域解集合中选择一个最好的邻域解，即满足,，然后作如下判断：如果，则设置,；否则，并清空集合。

4 仿真及结果分析

4.1仿真场景

考虑中继卫星的单址天线的任务调度问题，通信链路为前向链路，仿真时间为00:00:0023:59:59。从卫星工具箱(Satellite Tool Kits, STK)[15]中导出一颗中继卫星(TDRS-1)和4颗用户航天器(ALOS,JB-3 2,NAVSTAR 58,YAOGAN 4)，它们的轨道参数如表1所示。根据中继卫星和各用户航天器的轨道参数，可以计算出中继卫星与各用户航天器之间的可见时间窗[16]。表2列出了中继卫星TDRS-1与用户航天器ALOS之间可见时间窗，其它用户航天器与中继卫星之间的可见时间窗就不再一一列出。假设有20个任务申请服务，各个任务的申请服务请求的约束条件如表3所示，任务编号记为Task1,Task2,,Task20。根据用户提交的任务约束、中继卫星和用户航天器之间的可见时间窗，可以得到任务的可用时间窗。表4显示了任务(Task1)的可用时间窗，其它的任务可用时间窗就不再一一列出。

4.2结果分析

利用基于ABC算法得到的最优调度结果如表5，表6所示(种群规模=30, 阈值=200, 迭代次数=1000，二次邻域搜索循环次数=30，选择一个任务随机插入的邻域操作方式)。其中表5是调度成功的任务情况表，表6是调度失败的任务情况表。在表6指明的任务调度失败的原因中，时间冲突是指中继卫星与用户航天器在这段时间内不可见，即不能进行数据中继；资源冲突是指该任务抢占卫星资源(中继卫星、用户航天器)失败。

基于ABC算法的调度结果分析如下：(1)调度的目标是完成尽可能多任务，且优先级高的任务优先安排调度，考虑中继卫星单址天线任务调度如Task19调度失败，Task18, Task4, Task14调度成功，因为Task19抢占资源失败。(2)任务的执行必须在中继卫星和用户航天器的可见时间窗内，且也必须满足用户提交的时间约束，如Task16由于在该段时间内中继卫星与用户航天器不能彼此可见，所以Task16调度失败。(3)中继卫星与用户航天器之间可能具有多个可见时间窗，但任务的执行只能在一个可见时间窗内完成，因此当时间窗长度小于任务的持续时间长度时应考虑其它的时间窗，且同一时刻一颗卫星最多只能为一个任务服务，Task13和Task17因为竞争资源失败未能调度成功。

接下来将基于ABC算法与基于有效基因路径表示的改进遗传算法[6]调度结果作比较，有关有效基因路径表示的改进遗传算法描述和操作请参考文献[6]。表7(迭代次数为1000、种群规模为30)显示了ABC算法与该遗传算法相比较的结果，其中Minimuma, Maximumb, Averagec分别表示算法运行20次得到所有最优解中适应度值的最小值、最大值、平均值。从数据分析中可以看出，就中继卫星任务调度问题而言，ABC算法能够以较少的运算时间得到更高的适应度函数值，亦即得到中继星资源使用率更高的任务调度方案，其效果相对文献[6]提出的算法较好。

表1卫星的轨道参数

轨道参数TDRS-1ALOSJB-3 2NAVSTAR 58YAOGAN 4 轨道偏心率0.0000000.0001290.0005130.0077060.001523 轨道长半轴(km)42166.3007063.7846813.44626558.5287023.275 轨道倾角0.08398.15697.02855.95197.873 近地点角0.000103.22198.901298.298119.840 升交点赤经88.184184.813114.87825.940187.747 平均近点角282.837256.915261.27960.940240.434 平均运动(revs/d)1.003014.595715.30492.005714.7548

表2 中继卫星TDRS-1与用户航天器ALOS之间的可见时间窗

时间窗口开始时间结束时间持续时间 104:01:0904:59:3400:58:25 205:38:5606:37:5100:58:55 307:15:2908:17:1801:01:49 408:48:3512:34:4603:46:11 513:03:1414:06:1801:03:04 614:43:1015:42:2600:59:16 716:21:3717:20:0100:58:24 817:59:1318:58:2900:59:16 919:35:2220:38:2801:03:06 1021:06:5523:59:5902:53:04

表3各个任务的参数

任务优先级持续时间(s)最早开始时间最晚结束时间服务的卫星 Task12300009:40:0013:45:00ALOS Task23200007:00:0012:44:00ALOS Task33270010:30:3014:00:00ALOS Task41240012:10:0014:00:00ALOS Task54240009:00:0013:20:00ALOS Task62180016:09:0018:30:00JB-3 2 Task75240000:40:0009:00:00JB-3 2 Task82300007:45:0017:40:00JB-3 2 Task95180017:40:0023:00:00JB-3 2 Task106210015:40:0020:30:00JB-3 2 Task117420018:00:0020:56:00NAVSTAR 58 Task127360007:40:0021:40:00NAVSTAR 58 Task138300014:30:0017:10:00NAVSTAR 58 Task143270012:10:0015:47:00NAVSTAR 58 Task155540014:30:0017:10:00NAVSTAR 58 Task166180007:00:0008:30:00YAOGAN 4 Task176300004:34:0018:00:00YAOGAN 4 Task182330010:23:0014:41:00YAOGAN 4 Task193240010:23:0014:41:00YAOGAN 4 Task203300010:00:0021:00:00YAOGAN 4

表4任务(Task1)的可用时间窗

可用时间窗开始时间结束时间服务的卫星 109:40:0012:34:46ALOS 211:19:5512:11:42ALOS

表5基于ABC算法调度成功的任务情况

任务优先级执行任务的开始时刻持续时间(s)服务的卫星(用户航天器和中继卫星)执行任务的先后顺序 Task7504:42:202400JB-3 2, TDRS-11 Task8207:50:153000JB-3 2, TDRS-12 Task2308:48:352000ALOS, TDRS-13 Task5409:21:552400ALOS, TDRS-14 Task1210:01:553000ALOS, TDRS-15 Task3310:51:553000ALOS, TDRS-16 Task18211:36:553300YAOGAN 4, TDRS-17 Task4113:03:142400ALOS, TDRS-18 Task14313:43:142700NAVSTAR 58, TDRS-19 Task20314:48:453000YAOGAN 4, TDRS-110 Task15515:38:455400NAVSTAR 58, TDRS-111 Task6217:58:421800JB-3 2, TDRS-112 Task11718:28:424200NAVSTAR 58, TDRS-113 Task10619:38:422100JB-3 2, TDRS-114 Task12720:13:423600NAVSTAR 58, TDRS-115 Task9521:13:421800JB-3 2, TDRS-116

表6调度失败的任务情况

任务调度失败原因 Task16时间冲突 Task13资源冲突 Task17资源冲突 Task19资源冲突

表7 ABC算法与遗传算法[6]的比较

算法MinimumaMaximumbAveragec算法运行平均时间(ms)调度成功的平均任务数 ABC算法120812341223.727.85916 遗传算法 99710631051.968.37212

5 结束语

根据中继卫星任务调度问题的特点，综合考虑中继卫星与用户航天器之间具有可见时间窗、提交的任务约束、中继卫星前向资源受限等约束条件，建立了一个调度约束规划模型，基于这个模型提出了一种基于ABC算法的中继卫星任务调度方法。仿真结果表明：ABC算法能够有效解决中继卫星任务调度问题；通过与基于有效基因路径表示的改进遗传算法任务调度结果相比较，从调度成功的任务数、算法的运行时间以及适应度函数值3方面考虑，得之其性能比该改进的遗传算法较好。在将来，我们也将与其它启发式算法作比较。

[1] Teles J, Samii M V, and Doll C E. Overview of TDRSS[J]., 1995, 16(12): 67-76.

[2] 王家胜. 中国数据中继卫星系统及其应用拓展[J]. 航天器工程, 2013, 22(1): 1-6.

Wang Jia-sheng. China’s data relay satellite system and its application prospect[J]., 2013, 22(1): 1-6.

[3] Rojannasoonthon S, Bard J F, and Reddy S D. Algorithms for parallel machine scheduling: a case study of the tracking and data relay satellite system[J]., 2003, 54(8): 806-821.

[4] 方炎申, 陈英武, 顾中舜. 中继卫星调度问题的CSP模型[J]. 国防科技大学学报, 2005, 27(2): 6-10.

Fang Yan-shen, Chen Ying-wu, and Gu Zhong-shun. CSP model of the relay satellite scheduling[J]., 2005, 27(2): 6-10.

[5] 陈理江, 武小悦, 李云峰. 基于时间灵活度的中继卫星调度算法[J].航空计算技术, 2006, 36(4): 48-51.

Chen Li-jiang, Wu Xiao-yue, and Li Yun-feng. Scheduling algorithm for relaying satellite based on temporal flexibility [J]., 2006, 36(4): 48-51.

[6] Fang Yan-shen and Chen Ying-wu. Constraint programming model of TDRSS single access link scheduling problem[C].2006 International Conference on Machine Learning and Cybernetics (ICMLC), Dalian, 2006: 948-951.

[7] 赵卫虎, 赵静, 赵尚弘, 等. 微波与激光混合链路中继卫星动态调度快速启发式算法[J]. 中国激光, 2014, 41(9): 1-7.

Zhao Wei-hu, Zhao Jing, Zhao Shang-hong,. Dynamic scheduling fast heuristic algorithm for data relay satellite with microwave and laser hybird links[J]., 2014, 41(9): 1-7.

[8] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical report TR06. Computer Engineering Department, Engineering Faculty, Erciyes University, 2005.

[9] Karaboga D and Basturk B.On the performance of artificial bee colony (ABC) algorithm[J]., 2008, 8(1): 687-697.

[10] Abu-Mouti F S and El-Hawary M E. Overview of artificial bee colony (ABC) algorithm and its applications[C]. 2012 IEEE International Systems Conference(SysCon), Vancouver, 2012: 1-6.

[11] Karaboga D, Gorkemli B, Ozturk C,. A comprehensive survey: artificial bee colony (ABC) algorithm and applications[J].,2014, 42(1): 21-57.

[12] Yi Yu-jiang and He Ren-jie. A novel artificial bee colony algorithm[C]. Intelligent Human-Machine Systems and Cybernetics (IHMSC), Hangzhou, 2014: 271-274.

[13] Kojima M, Nakano H, and Miyauchi A. An artificial bee colony algorithm for solving dynamic optimization problems [C]. Evolutionary Computation (CEC), Cancun, 2013: 2398-2405.

[14] Liang Yun-chia, Chen A H L, and Nien Yung-hsiang. Artificial bee colony for workflow scheduling[C]. 2014 IEEE Congress on Evolutionary Compution(CEC), Beijing, 2014: 558-564.

[15] STK User’s Manual Version 6.0.1 for PCS[M]. USA, Analytical Graphics, Inc., 2005: 144-152.

[16] 李于衡, 孙恩昌, 易克初.中继卫星与用户星双向跟踪关系及策略[J].西安电子科技大学学报(自然科学版), 2007, 34(1): 6-10.

Li Yu-heng, Sun En-chang, and Yi Ke-chu. On the tracking strategies and space geometrical relationship between a TDRS and user satellites[J]., 2007, 34(1): 6-10.

Relay Satellite Scheduling Based on Artificial Bee Colony Algorithm

Kai Cai-hong①Xiao Yao①Fang Qing②

①(,,230009,)②(.38,,230031,)

Research on the relay-satellite scheduling problem provides scientific decision-making methods for the task planning of the Tracking and Data Relay Satellite Systems (TDRSS). How to develop a reasonable scheduling model and design the scheduling algorithm according to the model are two key issues to address. In this paper, according to the characteristics of the relay satellite scheduling problem, incorporating the constraints brought by the visible time window between the relay satellite and the user spacecraft, mission attributes submitted by users, and the limited resources of the relay satellite, a scheduling programming model is established. Furthermore, a scheduling algorithm based on the Artificial Bee Colony (ABC) algorithm is proposed. Finally, the simulation data analysis shows that the scheduling algorithm based on the ABC algorithm is an effective and reasonable scheduling method.

Relay satellite scheduling; Visible time windows; Mission attributes; Constraint programming model; Artificial Bee Colony (ABC) algorithm

TN927

1009-5896(2015)10-2466-09

10.11999/JEIT150144

2015-01-27；改回日期：2015-05-28；

2015-07-17

开彩红 chkai@hfut.edu.cn

国家自然科学基金(61202459, 61571178)

The National Natural Science Foundation of China (61202459, 61571178)

开彩红：女，1982年生，副教授，研究方向为无线通信与网络通信、网络体系结构和协议、网络系统性能分析与评价.

肖瑶：男，1990年生，硕士生，研究方向为无线通信与网络通信.

方青：男，1972年生，研究员级高级工程师，研究方向为卫星通信系统.