基于遗传算法的小卫星任务调度

夏 磊，俞能海

(中国科学技术大学中国科学院电磁空间信息重点实验室，安徽合肥230027)

0 引言

过去的十几年内，现代小卫星由于其独特的优势，逐步得到了国内外研究者的青睐，小卫星的数量也在不断的增加，然而用于控制接收小卫星数据的地面站数量却不多。目前学术型地面站在世界范围内的分布主要集中在北美以及欧洲等国家，我国仅台湾NCKU［1］拥有一个自己的低成本学术型地面站。国内对于卫星通信技术的研究主要集中在军事领域［2］，在民用［3］和学术科研领域各大科研院所还未重视，然而伴随着小卫星技术的不断成熟发展，高校以及科研院所的自主卫星通信系统将逐步得到发展，因此学术型地面站网络与小卫星网络的信息交互，特别是在任务调度方面具有十分重要的研究意义。传统的卫星任务调度 (SRS，Satellite Range Scheduling)问题一直是卫星地面站交互的研究重点，美国的Barbulescu［4］等人对于传统的卫星调度问题进行了详细的研究，针对美国空军卫星控制网络 (Air Force Satellite Control Network)实际应用场景进行分析，证明了这种SRS问题在多站多星的应用环境下属于NP难问题，同时针对卫星调度的几种求解算法进行了性能分析。李玉庆［5］提出了改进遗传算法来求解卫星测控任务调度问题，文献 ［6－8］也对传统卫星任务调度问题进行了分析研究。

与传统AFSCN等卫星通信系统不同的是，适用于小卫星通信系统的地面站网络被称为学术型地面站网络，这类地面站主要被科研机构用于对小卫星进行操控，数据下载等操作，具有冲突窗口多、非盈利、低成本等特点，小卫星的调度问题目前还没有过多的研究。文中在充分分析了小卫星学术地面站任务调度问题的前提下，在对比了传统地面站网络和学术型地面站网络的不同点后，针对学术型地面站网络与小卫星任务调度中出现的冗余调度问题进行了研究，定义了冗余调度公平性函数，并证明了其对于调度的公平性。选取Cubsat［9］体系中三个地面站和四颗小卫星进行仿真实验，利用STK工具得到卫星与地面站的通信时间窗口，基于遗传算法对可通信时间窗口进行优化调度。文中的研究将会为我国未来小卫星事业的发展奠定一定的理论基础。

1 问题分析与建模

卫星任务调度(SRS)问题作为NP难问题与传统地面上job－shop调度问题的主要区别在于存在着几大限制:窗口限制，资源限制和任务限制。由于LEO卫星的运行特点，小卫星和地面站的通信受到可见窗口的限制，如图1所示得出可见分析:地理可见，表示地面站刚好进入到卫星的扫描边缘，但是此时的地面站还不可以进行通信，只是地理意义上的可见;仰角可见，卫星继续运行，当卫星和地面站达到仰角可见范围是，地面站开始对卫星进行跟踪和姿态调整，这里需要一定的重构时间，这段时间不可通信;通信可见，在进行了一定的调整之后，地面站与卫星将建立稳定的通信链路，为可通信窗口时间段 T4－T3。

图1 卫星任务调度可见时间窗口Fig．1 Contact window of SRS problem

在一个调度时间周期内，通常一个星期，LEO卫星可能会与同一个地面站存在许多可通信窗口，但是由于卫星通信受到例如太阳直射，云层厚度等多方面干扰，不同时间段的可通信时间窗口效率受到这些因素的影响，Spangelo［10］等人对于星站通信效率进行了细致的研究，因此在问题的分析建模中，不同星站的窗口效率是文中最终优化调度的重点影响因素。

由于可通信时间窗口在给定卫星参数以及地面站参数之后已经固定，只需要对调度任务进行数学建模:

参数说明:tstart:任务最早开始时间;tend:任务最晚结束时间;dur:任务需求的持续时间;Uu:任务的发起者;Ss:任务指向的执行卫星;TGOS:卫星与地面站可通信时间开始时刻;TLOS:卫星与地面站可通信时间结束时刻;Tij(wm):地面站j为任务i在某时间窗口wm内提供的服务时间;Tsj(wm):地面站j和卫星s的可通信时间窗口wm的通信时间;Ps:卫星权重;Esj(wm):地面站j和卫星s的可通信时间窗口wm的通信效率。

2 冗余调度

学术地面网络与传统地面网存在这许多不同点，最明显的一个不同就是学术网主要承担的是一些非商业性质的研究任务，所有接入者均希望最大化使用自己的卫星资源，希望自己得到的服务时间充分，并不在乎具体是哪个地面站提供的服务，但是由于小卫星的数量增加和一箭多星技术成熟，使得多颗卫星同时覆盖一个地面站的情况相较于传统的卫星地面站网络而言出现频率更多，从而产生大量的冲突窗口，地面站在提供服务的时候存在选择性问题，传统 FGN(Federated Ground Network)网络［11－12］考虑任务需求卫星的权重进行冲突窗口的调配(如图2所示)，但是单纯的以卫星权重作为调度的衡量标准会使得权重大的请求会占用非常多的可通信窗口以至于一些卫星权重比较低的请求无法被调度，相同卫星权重的任务之间的窗口调度为随机调度，对于这种非盈利的学术研究请求，需要考虑公平性问题，德国研究小组Schmidt［13］等人针对该问题提出了冗余调度的概念，即对于冲突造成的冗余窗口如何分配。

图2 冲突窗口的调度问题Fig．2 Contact window confliction scheduling

文献［11］以每颗卫星分配的通信窗口数目进行公平性定义，这种定义方式在一定程度上可以体现任务调度的公平性，但是由于不同通信窗口的通信时间不同，简单的以调度窗口数目为评判标准是不充分的，文中以每一颗卫星最终分配到的服务时间来进行公平性的判别，在时间粒度上重新定义了公平性函数，公平函数值越小则公平性越大，对公平性的判断进行了数学分析，证明了在任务需求卫星优先级相同的前提下，不同任务请求最终分配到的服务时间越相近则越公平。定义每一颗小卫星最终调度分配的服务时间:

定义公平函数:

最终的优化目标则是在保障星站利用度函数值大的情况下，尽可能的减小公平函数的函数值。

假设两颗小卫星最终调度后的服务时间分别为Tsat_1和Tsat_2，公平函数计算结果为:

如果小卫星1与小卫星2存在可视窗口上的冲突，那么在调度的时候就存在一个冲突时间重分配的问题，这里假设小卫星1在最公平调度分配下让出一部分时间 t给小卫星2，那么新的公平函数值为:

分三种情况讨论证明:

(1)若Tsat_1=Tsat_2

明显可知f'≥f，也就是说倘若最终调度结果中，小卫星1和小卫星2分配的服务时间是相等的话，那么定义的公平函数将会是最小值，如果这时候再从小卫星1的调度时间里抽调服务时间给小卫星2，那么将会使得公平函数值变大，破坏公平性。

(2)若 Tsat_1≤Tsat_2

则f'≥f，当最终调度结果小卫星1的服务时间已经小于小卫星2分配的服务时间时，如果再从小卫星1里面调度服务时间给小卫星2，那么明显的会破坏公平性，公平函数值变大。

(3)若 Tsat_1≥Tsat_2

则有f'≤f，如果最终调度结果小卫星1的服务时间比小卫星2的服务时间长，此时可以再不扩大公平函数值的前提下抽调一部分卫小星1的服务时间给小卫星2，也就是冲突窗口的时间分配一部分给服务时间少的卫星，会提高公平性。

3 目标函数设定

前文中对小卫星地面站调度问题进行数学建模，冗余调度分析，考虑到学术性小卫星使用上的公平性原则，对于每一颗小卫星的任务在卫星权重上做出相等的前提假设。优化目标设置为等卫星权重下的小卫星与地面站网络利用效率与小卫星最终分配服务时间公平性函数的组合，通过调节每一个优化目标的权重值，使得最终的优化目标达到最好效果。

调度需要满足下面限制条件:

∃wm存在可通信窗口;

Topreation_start≥tstart调度后任务执行开始时间要在任务最早开始时间之后;

Toperation_end≤tend调度后任务执行结束时间要在任务最迟完成时间之前;

Toperation_end－Toperation_start≥dur调度后任务执行总时间需满足任务持续时间要求;

{Toperation_end，Toperation_start}∈∪{TGOS，TLOS}调度后任务的调度时间需要存在于某个可通信窗口内。

从定义的优化目标函数中可以看出，在小卫星权重相同的前提下最大化小卫星与地面站网络的利用度，同时保障不同任务之间的调度公平性，P值越大，说明调度结果越好，一方面需要增加调度结果中窗口的利用度，另一方面则需要减减小公平函数的值。

4 仿真实验

卫星任务调度问题属于NP难解问题［4］，伴随着卫星，地面站以及任务请求数量的增加，问题的求解复杂度十分的高，并且传统的贪婪算法等并没有办法求解出一个全局最优解，对于该种调度问题，Barbulescu［4］对遗传算法在求解该类问题上进行了性能分析，实验证明了遗传算法可以得到比较优良的全局优化解，文中选取遗传算法来求解相对全局最优的解，对可通信窗口进行二进制编码，以及优化选择种群个体进行遗传操作，定义遗产算法的迭代次次数为结束指标进行仿真。通过从世界上现役小卫星网络Cubesat系统中的地面站和小卫星中选取3个地面站，4颗卫星［14］，具体参数如表 1，表 2所示，利用STK软件得出他们的可通信时间窗口，这些可通信窗口时间为T3－T4时间段，可进行直接通信的时间，随机赋予每一个通信窗口的卫星－地面站通信效率值(0－100)，定义观测时间为24小时，定义每一颗小卫星的任务需求时间段为24小时的观测周期内，每一颗小卫星需求15个完整的星站通信窗口。

表1 学术型地面站参数Table 1 Parameter of academic ground stations

表2 小卫星参数Table 1Parameter of small satellites

定义优化目标函数为:

对遗传算法进行参数设置，种群数量设置为40，杂交概率1，变异概率0．2，定义最大迭代次数300。图3为遗传算法优化过程中优化目标的典型进化曲线，可以看出，伴随着迭代次数的增加，50次迭代后，种群的适应值基本达到收敛，但是由于是多目标函数的优化问题，所以后面的迭代存在一定的波动，迭代结束后得到一组相对最优调度结果。由于遗传算法得出的结果并不是一定是全局最优解，这里进行了多组相同参数下的仿真实验，并分别对他们最终的适应值进行比较，仿真结果数值如图4显示，仿真结果可以看出第五组的仿真调度结果最终的目标函数值最大，从而选取第五组优化结果作为最终调度结果。图5为第五组优化调度后小卫星与地面站之间窗口分布甘特图。

图3 遗传算法优化目标进化曲线Fig．3 A typical curve of genetic algorithm

图4 五组遗传算法优化调度结果数据对比Fig．4 Comparision of the five groups’result

图5 第五组优化调度甘特Fig．5 Gantt chart of the fifth scheduling result

五组遗传算法最终的优化目标值、小卫星服务时间均方差和星站总效率值如图4所示，可以看出第五组优化目标函数值最大，第三组优化结果在本次仿真中最差，从图4中可以看出最终调度结果中地面站对于四颗卫星提供服务时间的均方差，以及最终调度后目标函数中星站效率的值。从图中数据可以分析出，虽然第四组的各星服务时间均方差值最小，但是由于对于公平性优化目标的比重参数设置，综合考虑调度后的星站总效率和公平性两方面因素，选取第五组仿真优化调度结果是最合适的。

5 结语

文中通过对于传统卫星调度问题进行详细的研究和分析，结合近十几年小卫星的发展，对学术型地面站网络和低轨小卫星网络的调度问题进行了分析和研究。对于学术型地面站网络中非盈利特性以及共享资源使得在小卫星任务调度中存在的冗余调度问题进行了研究，提出了时间粒度上的公平函数的概念，定义公平函数，在学术小卫星任务调度中，综合考虑星站之间通信效率和公平性问题进行了最终优化目标函数的定义，对于该问题采用效果最好的遗传算法进行仿真调度实验。仿真结果显示遗传算法对于这种多约束限制的卫星调度问题有着很好的解决问题的能力。

［1］ HSIAO F B，LIU H P，CHEN C C．The Development of a Low－cost Amateur Microsatellite Ground Station for Space Engineering Education［J］．Global J of Engng Educ，2000，4(01):83－88．

［2］ 吴文敬，韩颖，张桢．综合应急指挥调度系统的设计与实现［J］．通信技术，2013，46(04):103－105，108．WU Wen－jing，HAN Ying，ZHANG Zhen．Design and Implementation of Integrated Emergency Command＆Control System［J］．Communications Technology，2013，46(04):103－105，108．

［3］ 卢亮，张婷，邓磊．北斗导航民用市场分析研究［J］．通信技术，2013，46(05):101－103．LU Liang，ZHANG Ting，DENG Lei．Study on Civilian Market of Beidou Satellite Navigation［J］．CommunicationsTechnology，2013，46(05):101－103．

［4］ BARBULESCU L，WATSON J P，WHITLEY LD，et al．Scheduling Space-ground Communications for the Air Force Satellite Control Network［J］．Journal of Scheduling，2004，7(01):7－34．

［5］ 李玉庆，王日新，徐敏强，等．基于改进遗传算法的一类多资源测控调度问题研究［J］．宇航学报，2012，33(01):85－90．LI Yu－qing，WANG Ri－xin，XU Min－qiang，et al．An Improved Genetic Algorithm for a Class of Multi－Resource Range Scheduling Problem［J］．Journal of Astronautics，2012，33(01):85－90．

［6］ 李云峰．卫星—地面站数传调度模型及算法研究［D］．湖南:国防科学技术大学，2008．LI Yun－feng．Research on Satellite－Ground Station Data Transmission Scheduling Models and Algorithms［D］．Hunan:National University of Defense Technology，2008．

［7］ 姚锋，邢立宁．求解卫星地面站调度问题的演化学习型蚁群算法［J］．系统工程与电子技术，2012，34(11):2270－2274．YAO Feng，XING Li－ning．Learnable Ant Colony Optimization Algorithm for Solving Satellite Ground Station Scheduling Problems［J］．Systems Engineering and Electronics，2012，34(11):2270－2274．

［8］ 张红旗．基于贪婪算法的卫星地面站资源调度方法［J］．无线电工程，2010，40(12):4－6．ZHANG Hong－qi．Resource Scheduling Method of Satellite Ground Station based on Greedy Algorithm［J］．Radio Engineering，2010，40(12):4－6．

［9］ Wikipedia．CubeSat［DB/OL］．(2013－02－03)［2013－09－11］．http://en．wikipedia．org/wiki/CubeSat．

［10］ SPANGELO S，CUTLER J，KLESH A，et al．Models and Tools to Evaluate Space Communication Network Capacity［J］．Aerospace and Electronic Systems，IEEE Transactions，2012，48(03):2387－404．

［11］ JUNG－HYUN L，MYUNG WS，CHUNG D，et al．Multi－satellite Control System Architecture and Mission Scheduling Optimization［C］//Aerospace Conference．USA:IEEE，2012:1－13．

［12］ KOTA S L，GIAMBENE G，KIM S．IJSC＆N，Special Issue on‘hybrid/integrated Satellite-terrestrial Networks’［J］．International Journal of Satellite Communications and Networking，2011，29(03):187－90．

［13］ SCHMIDT M，SCHILLING K．A Scheduling System with Redundant Scheduling Capabilities［C］//International Workshop for Planning and Scheduling in Space．Pasadena:AAAI，2009:12－18．

［14］ James Cutler．Small Satellite Survey［DB/OL］．(2009－10－11)［2013－09－11］．http://gs．engin．umich．edu．