2019, Vol. 40
2. 上海微小卫星工程中心, 上海 201203;
3. 中国科学院大学, 北京 100039
2. Shanghai Engineering Center for Microsatellites, Shanghai 201203, China;
3. University of Chinese Academy of Sciences, Beijing 100039, China
卫星自主任务调度是解决在轨卫星资源能够合理分配和高效使用，最大限度完成用户提交的多个观测任务的重要手段，在整个卫星应用过程中起着关键作用，是影响卫星使用效能的主要因素之一。传统卫星的运行，其在轨活动都是由地面运控中心提前做好计划方案和相应任务指令[1-3]，然后经由合适的地面站上行链路上传至卫星并离线执行，这种方式要求任务明确且串行、星地通信时间充分以及运行环境相对稳定。由于卫星数量和任务需求日益增多，星地交互频繁，这种方式的运行成本较高，在动态环境下，例如观测区域上空出现云层、卫星故障、观测任务不定时上注、取消已安排任务及任务属性变化等时，地面任务规划与资源调度系统没有足够的时间对卫星进行规划方案调整，将导致观测任务无法完成。而网络条件下多星运行的任务执行，其数量级的工作量更是地面规划所不能承受的。
为了实现更加高效的空间设施建设，空间信息网络是未来的航天发展方向，一直以来是世界各国的研究重点，欧美等国已经提出了全球信息栅栏体系、星际互联网体系等结构模型[4-5]。我国从“十五”起也一直在进行体系架构论证和相关关键技术攻关。完善的空间信息网络中，卫星之间应具备传输时延小、在轨实时互联互通的能力。网络中的卫星能够响应用户多个任务，根据实时的任务信息、卫星状态信息、外部环境及其他约束条件，网内自主进行决策，控制卫星协同高效完成观测任务和数据下传。
本文在双层“BigMAC”的空间信息网络体系架构基础上[6]，进一步增加高轨卫星层，设计了“Sandwich”体系架构，为了突破单星的计算资源限制，最大化利用网络信息能力，提出了一种适用于分布式协同计算的调度算法[7-8]，以实现在轨自主调度网内卫星的协同计算。
1 在轨分布式任务自主调度问题研究 1.1 在轨分布式任务自主调度流程类似于传统卫星任务调度，以对地多目标观测为例，需要计算卫星-目标可观测窗口、调度运算、调姿判断等步骤，最终得出调度结果。星上分布式任务自主调度算法主要包含以下几个步骤：
1) 观测任务上传：根据用户需求，给卫星上传未来一段时间内需执行的多个观测任务的坐标点序列值；
2) 星上快速可视窗口数值计算，通过星上快速计算方法，以卫星本体轨道参数和输入观测任务目标点坐标序列，计算一段时间内(比如一周内)卫星与各目标位置的可视时间窗口；
3) 星上分布式任务调度：该过程以卫星-目标点可视时间窗口为输入参数，采用断链重连贪婪算法实现任务调度，将调度任务进行分割，子任务序列传送给周边辅星进行计算，并将调度结果返回主星，形成总体任务调度结果；
4) 引入导引律计算，对调度序列进行可行性分析，保障调度序列不存在因卫星姿态调整时间导致的观测任务冲突问题；
5) 判断迭代次数，当达到一定计算迭代次数后，对冲突观测任务进行随机选择，输出最终调度结果。
|
Download:
|
| 图 1 星上分布式任务自主调度流程图 Fig. 1 Flow chart of on-orbit distributed satellite scheduling | |
通信网络的出现使得计算能力的远程使用成为可能，目前存在几种主流的分布式计算技术，通过对不同分布式技术的分析和研究，选取适应于空间信息网络的分布式调度计算模型：
1) 远程过程调用。
远程过程调用(remote procedure call，RPC)(如图 2)是为了缓解最初的消息传递模型编程的琐碎性而提出的，它支持本地机的程序通过标准过程调用机制调用远程机的过程。基本思想是把本地的过程调用扩展到分布式环境中，当程序员使用RPC调用一个远程过程时，代码实际执行的是一个代理函数，代理过程的目的是编排输入参数，并把它们传送到远程服务器。
|
Download:
|
| 图 2 RPC模式 Fig. 2 RPC mode | |
该模式存在的缺点包括：①RPC是面向过程的一种方法，在应用中有很大的局限性，例如系统管理问题、系统安全问题等；②在通信过程中，远程与本地需要进行频繁的交互，而且调用必须是单向的；③RPC正确执行的前提是被调用的过程事先存在，这个要求限制了RPC在大型分布式系统中的应用，很多情况下，要调用的过程在远程节点上并不存在。下面的远程求值可以解决这个问题。
2) 远程求值。
远程求值(remote evaluation，REV)(如图 3)允许网络中的节点向远程节点发送子程序和参数信息，远程节点启动该子程序，一些初始请求可由该子程序发出，中间结果由该子程序处理，而不是发回源节点，子程序只是将最后的处理结果返回到源节点。
|
Download:
|
| 图 3 REV模式 Fig. 3 REV mode | |
3) 客户/服务器模式。
在客户/服务器(client/server，C/S)通信模式中，通信的实体双方有固定、预先定义好的角色：服务器提供服务，客户使用服务。这种模式隐含了一种严格的依赖关系：客户依赖服务器所提供的服务而工作。客户发出服务请求，然后在服务器上完成任务，最后服务器将处理结果返回到客户机(如图 4)。引入客户和服务器的角色，RPC模式和REV模式都是客户/服务器模式的一种。
|
Download:
|
| 图 4 客户/服务器模式 Fig. 4 Client/server mode | |
优点：①优化网络利用率，减少了网络流量；②响应时间较短；③通过把应用程序同它们处理的数据隔离，可以使数据具有独立性。缺点：①C/S模式的服务器若不能确切提供客户方所要求的服务，则客户就必须通过一系列的远程调用来获得它所需的服务，这就导致了服务响应的延迟和网络带宽的浪费；②因为计算环境中的处理器资源、软件资源和信息资源等都集中在服务器上，当客户请求较多时，服务器的效率会大大降低，客户请求的响应时间也会增大。
针对卫星网络特点，考虑信息传输延时等问题，计划对卫星进行对等设计，拟采用远程求值模式，被上注任务的目标星进行自主规划时，将相关算法分解，由相关输入参数设备发送给网络中拥有计算资源的卫星，分布式计算卫星根据输入参数和分解算法，对部分算法进行计算，实现任务规划算法的并行处理，最终将计算结果返回给目标星(如图 5所示)，由目标星进行合并处理，提高星上自主运算速率。
|
Download:
|
| 图 5 卫星自主规划算法分布式计算示意 Fig. 5 Distributed computing of satellite autonomous planning algorithm diagram | |
卫星在轨实时互联互通是实现卫星分布式协同的先决条件[9-10]，需要研究一种合适的空间信息网络体系，本文设计的“Sandwich”空间网络体系架构设计在“BigMAC”基础上增加GEO层卫星，即由3颗GEO卫星，15颗1 400 km轨道的LEO骨干节点卫星及144颗350 km轨道的接入节点热点卫星构成，骨干传输层间链路实时互通，同时对下层卫星任意时刻可完全覆盖，而144颗接入节点需要对现有系统及其他设备进行接入，如图 6所示。
|
Download:
|
| 图 6 “Sandwich”网络空间体系架构 Fig. 6 "Sandwich" space network architecture | |
GEO、LEO层之间主要以激光微波混合宽带实现网络骨干传输，如图 7所示。
|
Download:
|
| 图 7 GEO层骨干网络结构 Fig. 7 Backbone network structure of GEO layer | |
LEO卫星骨干层采用了3个轨道面，每轨5颗星的Walker星座设计，如图 8所示。以最少的轨道面与最少的星数实现了对200 km以上航天器的覆盖，与GEO卫星层互为补充。LEO卫星骨干层内部基于微波(Ka等频段)或者激光微波混合等方式构建互联互通的网络，在GEO层毁损时也能保证有限性能的骨干服务。利用LEO卫星骨干层实现较低时延的骨干业务传输，满足实时任务需求。
|
Download:
|
| 图 8 LEO层骨干网络结构 Fig. 8 Backbone network structure of LEO layer | |
基于将现有近地轨道尽可能多的接入进网络的需求，初步考虑一个350 km左右分布的热点卫星层，用于利用现有卫星对地的测控数传波束，尽可能地将它们接入系统，如图 9所示。
|
Download:
|
| 图 9 LEO接入层节点卫星结构 Fig. 9 Node satellite structure of LEO access layer | |
在轨大多数的对地观测卫星主要通过与地面站进行卫星的测控与数据传输。其测控与数传的波束角在60°内可以保证较高的数传速率，75°范围内可以通信，通信速率与通信质量较不稳定。
热点层应该与地面站以及骨干层的互联，实现全球全空域的在轨航天器的互通。为了实现接入，热点层的设计思路首先是需要对全球地面的覆盖以及对近地轨道航天器的覆盖。考虑轨道寿命，轨道高度不低于350 km。考虑到对尽量多的在轨航天器的易于接入，需要将卫星的运行轨道设计的尽量较低。所以热点层的设计是一个轨道寿命、空域覆盖、卫星数量之间的一个优化设计过程。
通过这样的3层“Sandwich”空间信息网路体系架构设计，结合已突破的激光通信、高速微波通信、星间快速路由等关键技术，可有效实现卫星在轨之间的互联互通，降低卫星对地面的依赖度。在满足卫星联通的同时，需要对网络传输延时进行相应仿真，只有低传输延时才能满足卫星在轨分布式协同调度的任务需求。
2.2 系统网络延时仿真分析在上述“Sandwich”空间信息网络架构下，低数据量传输通常使用LEO骨干层卫星进行传输，由于卫星处于高速移动过程，因此整个LEO骨干层网络拓扑也在不断变化，如图 10所示。
|
Download:
|
| 图 10 空间信息网络动态拓扑变换 Fig. 10 Transformation of spatial information network dynamic topology 注：两颗星间数字表征存在通信链路和该链路通信代价拟合值：距离、延迟、干扰强度等。 | |
采用Dijkstra(迪杰斯特拉)算法对最恶劣通信链路情况进行求解分析。Dijkstra算法是典型的单源最短路径算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。将卫星网络图 10连通状态看做一个无向图G=(V, E)，在无向图中，假设每条边E[i]的长度为W[i](边的长度表示各卫星间的通信距离)，最短路径就是找到由顶点V0(卫星sat1~sat6)到其余各点(卫星sat1~ sat6)的最短路径。
图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合(用S表示)，初始时S中只有一个源点，以后每求得一条最短路径，就将加入到集合S中，直到全部顶点都加入到S中，算法结束；第二组为其余未确定最短路径的顶点集合(用U表示)，按最短路径长度的递增次序依次把第二组的顶点加入S中。
算法步骤如下。
1) 初始时，S只包含源点，即S={v}，v的距离为0。U包含除v外的其他顶点，即U={其余顶点}，若v与U中顶点u有边，则〈u, v〉正常有权值，若u不是v的出边邻接点，则〈u, v〉权值为∞，本算法中设计为一个很大的值。
2) 从U中选取一个距离v最小的顶点k，把k加入S中，该选定的距离就是v到k的最短路径长度。
3) 以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短，则修改顶点u的距离值，修改后的距离值的顶点k的距离加上边的权。
4) 重复步骤2)和3)直到所有顶点都包含在S中。
通过对2017年5月21日全天86 400 s中每一秒钟的网络拓扑结构与最优路由路径计算分析，得出15颗骨干网卫星的空间信息网络构型在全天候所有时刻，如图 11所示，X、Y轴表示骨干网卫星编号1~15，Z轴表示任意两颗卫星端到端最优化传输距离。
|
Download:
|
| 图 11 全天候15颗卫星任意两星间最优路径最大距离 Fig. 11 Maximum distance of optimal path between any two of the 15 satellites during all-weather | |
仿真结果表明：任意两颗骨干网卫星之间最优路径的最大值为49 669.6 km，为卫星节点2到卫星节点9在时刻60 s时的最优传输路径值，信息最多经过7跳可以从源节点到达目的节点:
| $ \begin{array}{l} \;\;\;\;\;\;\;\;{t_{{\rm{ISL - Delay}}}} = (\sum {{D_{{\rm{ISL}}}}} )/C = \\ (49\;669.6 + 1\;400 \times 2)/(3 \times {10^5}) = 0.174{\rm{s}} \end{array} $ |
仿真结果显示任意两颗卫星之间传输延时最恶劣为0.175 s，相较于传统的中继卫星系统，其最优传输路径距离为72 000 km，最小传输延时为0.24 s，15颗卫星组成的骨干网络可以更加快速、有效的分发指令和回传信息。“Sandwich”体系架构也充分考虑了传输链路冗余等问题，保障了信息传输的可靠性。因此这样的空间信息网络体系架构可以有效支撑卫星在轨数据分布式协同计算，为在轨分布式任务调度提供理论基础。
3 分布式任务自主调度算法设计 3.1 分布式断链重连算法分布式断链重连调度算法通过对调度目标节点序列进行数学建模，根据目标位置结合卫星姿控导引等能力约束，以贪婪算法进行断链调度设计，形成多条断开的短调度序列，断开的链条通过一定规则舍弃部分无法连接的数字，从而相互连接起来，作为最终的输出[11]。
将分布式任务边界等物理约束简化后，得到相应的简化数学模型：输入一组待自主调度的数组，在断链重连算法下，寻求一条受物理约束的规划路径。这组输入数组可以被视为一条长链，而其中的每个数字都可以被视为这段链条上的一节。最终待规划的自主调度路径将由这段链条上的一节一节构成。由于受物理约束的限制，因此在初始输入数组上存在不满足物理约束限制条件的相邻数字，即链条上的相邻节，相互不能联通。初始的数组长链，形成了几段短而断的链条。在不满足物理约束限制条件的数字间就形成了一处处断点，使得整个链条分为了好几个小段。为满足最终分布式任务规划较优结果，需要将诸多断链重新连接，并使得最终输出的观测链条长度保持较长，保证总体调度算法输出结果较优。
分布式断链重连调度算法将通过贪婪算法对初始输入数组进行处理，形成数条断链。再在优化链条长度的思路下，对相邻两条链条进行连接：由少及多地舍弃无法连接的节点，在两条断链间选择新的连接节点方式，直至两条断链成功连接。再重复连接后续断链，直至完成所需任务调度规划。
分布式断链重连法的初始输入条件：1, 2, …, n，共计n个点(由小到大排列)，需要直接计算相邻两点之间的联通程度，若存在无法连接的情况，则形成断点，出现断链。
链条定义：除最初与最末两点外，两个“×”之间为同一链条。去一般化，结果如图 12所示。定义A链条起始点为As，A链条结束点为Ae；B链条起始点为Bs，B链条结束点为Be。断链重连算法的目标：将A链与B链成功连接，并对链条长度做期望优化(以极端情况为例，A、B链间任意的连接节点选择均不满足物理约束限制，即无法完成A、B链条的连接。在此种情况下，只能对A、B链条进行二选一)。
|
Download:
|
| 图 12 断链重连示意图 Fig. 12 Reconnection diagram of broken chain | |
丢1点(2种)
丢2点(3种)
丢x点(x+1种)
通过上述计算，寻找相应的A、B链条间的连接节点方式，将A、B链连接起来。可以将成功连接的链条称为新的A′链，向对后续的B′链持续进行断链重连算法计算，直至形成所需的任务调度规划。
断链重连算法的特性是能够对不同的观测链条进行重构重连，能够将离散的观测链条整合为同一的观测链条，因此可以有效地适用于分布式协同调度任务中：通过将长调度任务序列进行切割，发至其他辅助卫星协同计算，再以递归方式将结果返回并合并重组，形成最终调度结果，使用断链重连算法能够加快调度计算效率，降低单星计算负荷。
3.2 基于网络的分布式调度演示系统本文利用树莓派(Raspberry Pi，RPi)搭建了一套基于网络的地面演示验证系统，以验证分布式任务自主调度算法可行性。系统由一台计算机(主星)和两个树莓派(协同卫星)构成，采用socket通信协议模拟星间通信链路。主星在收到需观测的多个任务目标点后，利用分布式任务自主调度算法将调度任务切割成两段子目标，利用无线网络分别发送给协同卫星，协同卫星接收到数据后，利用分布式断链重连调度算法对分割后的子目标进行调度计算，并将计算结果返回给主星，主星进行调度结果整合，显示最终调度结果。
|
Download:
|
| 图 13 演示验证系统原理图 Fig. 13 Demonstration verification system schematic diagram | |
|
Download:
|
| 图 14 基于网络的分布式协同调度演示系统 Fig. 14 The distributed cooperative scheduling demonstration system based on network | |
为进一步验证调度算法在计算时间上的优势，进行调度算法效能仿真分析。当直接使用断链重连算法进行处理时，输入20个观测目标数据点，结果如图 15所示。
|
Download:
|
| 图 15 仿真调度结果 Fig. 15 The results of scheduling simulation | |
最终输出点为9点耗时时间为0.062 034 s，如图 15(a)所示。
经过分布式处理分割后，将20点分为前后两个链条，进行并行计算后，结果分别如图 15(b)、(c)所示。两组结果均为5点，将两结果数据连接后，剔除1点受物理约束无法连接的点外，最终结果为9个点，与直接计算结果一致。而计算时间为0.025 175 s与0.035 663 s(包含连接步骤)。
由此证明，在使用分布式并行计算后，可以在大致保持原有计算精度的情况下将计算时间由0.062 034 s压缩为0.035 663 s，节约42.51%的计算时间。
设计输入60个全球任务目标点，通过演示系统进行任务分发，协同卫星返回结果整合后共42个结果满足需求，调度结果所需计算时间同样减少一半左右，调度结果返回合并与显示情况如图 16所示。
|
Download:
|
| 图 16 调度结果返回合并与显示 Fig. 16 The returned and displayed result of scheduling | |
1) 通过网络传输延时仿真分析，其传输时延略优于传统中继方式，传输效能有利于满足分布式协同的要求；
2) 通过基于Raspberry Pi搭建的分布式调度演示系统，在考虑卫星姿态控制以及导引率等对任务调度的约束影响下，利用分布式断链重连算法实现了并行分布式计算能力，两星协同时任务调度周期缩短约一半。
根据以上结果，本文研究的方法可在网络条件下突破单星计算资源限制，面对多个任务的响应，可有效缩短卫星自主调度周期，提高整个空间网络的使用效率。该方法可适用于组网状态下面向多任务的各类对地观测、天基探测类卫星的在轨自主任务调度，具有重要应用意义。
| [1] |
BENSANA E, VERFAILLIE G, AGNōSE J C, et al. Exact and approximate methods for the daily management of an earth observation satellite[C]//Proceedings of the 4th International Symposium on Space Mission Operations and Ground Data Systems. Dordrecht: Kluwer Academic, 1996.
(  0)
|
| [2] |
HALL N G, MAGAZINE M J. Maximizing the value of a space mission[J]. European journal of operational research, 1994, 78(2): 224-241. DOI:10.1016/0377-2217(94)90385-9 ( 0)
|
| [3] |
MORRIS R A, DUNGAN J L, BRESINA J L. An information infrastructure for coordinating earth science observations[C]//Proceeding of the 2nd IEEE International Conference on Space Mission Challenges for Information Technology. Pasadena: IEEE, 2006.
( 0)
|
| [4] |
常青, 李显旭, 何善宝. 我国空间信息网发展探讨[J]. 遥测遥控, 2015, 36(1): 1-10. CHANG Qing, LI Xianxu, HE Shanbao. Confer on the evolution of earth-space integrated information network of China[J]. Journal of telemetry, tracking and command, 2015, 36(1): 1-10. DOI:10.3969/j.issn.2095-1000.2015.01.001 ( 0)
|
| [5] |
闵士权. 我国天基综合信息网构想[J]. 航天器工程, 2013, 22(5): 1-14. MIN Shiquan. An idea of China's space-based integrated information network[J]. Spacecraft engineering, 2013, 22(5): 1-14. DOI:10.3969/j.issn.1673-8748.2013.05.001 ( 0)
|
| [6] |
ZHANG Keke, XIA Lei, ZHANG Shengyu, et al. Double layer LEO satellite based "BigMAC" space information network architecture[C]//YU Quan. Space Information Networks. Singapore: Springer, 688: 217-231.
( 0)
|
| [7] |
SWEET N, KANEFSKY S. The C2 constellation a us air force network centric warfare program[C]//2004 Command and contral reseach and technology symposium.[S.l.], 2004.
( 0)
|
| [8] |
FARSEROTU J, PRASAD R. A survey of future broadband multimedia satellite systems, issues and trends[J]. IEEE communications magazine, 2000, 38(6): 128-133. DOI:10.1109/35.846084 ( 0)
|
| [9] |
SURHONE L M, TENNOE M T, HENSSONOW S F. InterPlaNet[M]. Echeveria: Betascript Publishing, 2010.
( 0)
|
| [10] |
MARTÍNEZ P, URIBE G G A, MOSQUERA P F L. OneWeb: plataforma de adaptación de contenidos web basada en las recomendaciones del W3C Mobile Web Initiative[J]. Ingenieria é investigación, 2011, 31(1): 117-126. ( 0)
|
| [11] |
潘志舟.基于任务复制和插入的分布式任务调度算法研究[D].武汉: 华中科技大学, 2015. PAN Zhizhou. Task-duplication and insertion based scheduling algorithm for heterogeneous computing environments[D]. Wuhan: Huazhong University of Science and Technology, 2015. ( 0)
|