基于FSA的卫星任务规划流程定制平台设计

2015-01-01谷宏志

无线电工程 2015年1期

谷宏志

(中国电子科技集团公司第五十四研究所，河北石家庄050081)

0 引言

随着我国航天事业的发展，在轨的卫星种类越来越多，卫星数量不断增加，对卫星任务规划调度系统提出更高的要求。作为卫星运行控制中的核心环节，各航天大国均相继研发自己的卫星任务规划调度系统［1］。

商用的卫星任务规划软件系统有美国Veridian公司开发的GREAS(Generic Resource Event and Activity Scheduler)通用问题调度系统［2］和美国Analytical Graphics Inc推出的 STK(Satellite Tool Kit)卫星任务规划套件［3］。但由于卫星能力与应用特点差别较大，为了更好地与卫星载荷能力相匹配，通常需要研制面向某系列卫星的专有卫星任务规划系统。针对具体卫星的专用调度系统有Potter W等设计的 Landsat 7 调度系统［4］、Muraoka．H 等设计的ASTER调度系统等［5］。随着卫星载荷种类和能力的不断提升，参与卫星任务规划的资源也不断增加，原有单一流程的任务规划系统的弊端也逐渐显现，主要表现在软件普适性较差，且系统可扩展性、可伸缩性均较低。

本文通过在任务规划系统设计中引入有限状态自动机(FSA)模型，利用有限状态自动机的状态迁移特性，将原有单一流程的任务规划系统变成可定制流程的任务规划平台，通过面向不同任务匹配不同的规划流程和算法来有效地解决这些问题。

1 卫星任务规划流程建模

卫星任务规划流程可定制平台要求其能够与卫星任务规划业务流程紧密结合，且具有良好的可扩展性、灵活性和流程可定制性。

1．1 卫星任务规划流程特点分析

卫星任务规划过程一般可分为卫星载荷任务规划、地面测控接收资源规划、规划方案的人工编辑和地面测控接收资源更新等多个业务节点［6］，且上述多个节点之间可相互转化。针对不同卫星应用任务有不同的规划流程，如受到地面测控资源的使用约束，可先进行地面测控接收资源规划再进行卫星载荷动作规划，也可能由于受到卫星载荷使用约束的要求，需要先进行卫星载荷任务规划，然后再进行地面测控跟踪资源规划，并根据地面资源规划结果对卫星载荷动作规划结果进行调整，还可能按照上述方式迭代优化多次。常规的任务规划流程如图1所示。

图1 卫星任务规划流程

各节点的主要任务描述如下:

载荷任务规划节点:根据任务需求，依据载荷任务规划的约束条件和规划目标，选择合适的规划算法，对分配到卫星相关载荷上的任务进行规划，确定各载荷任务的执行时间和参数等。

地面资源规划节点:根据地面接收和测控的任务要求，依据地面接收和测控资源的使用约束和规划目标，选择合适的规划算法，对地面接收和测控资源的任务进行规划，确定地面各资源的任务执行时间和参数。

地面资源更新节点:由于受到地面资源动态变化的影响，在任务规划过程中，对资源发生的变化进行及时更新，确保卫星任务规划所使用到的地面资源的可用性。

方案人工编辑节点:根据按照相关算法完成的任务规划方案，由用户确定规划方案是否满足任务要求，对不满足任务要求的部分通过人机交互的方式进行修改，以确定最终的执行方案。

按照传统的卫星任务规划系统设计方式，一旦任务规划系统设计完毕，则任务规划流程就难以更改。在某个节点后增加一个业务节点或调整规划顺序，将付出较大的修改代价。鉴于此，通过引入有限状态自动机的概念设计卫星任务规划平台，使其能够搭载遗传算法［7］、贪婪算法［8］和禁忌搜索算法等算法服务，并可以灵活定制规划流程，从而适应多种载荷的卫星任务规划需求。

1．2 卫星任务规划有限状态自动机

有限状态自动机(Finite State Automaton，FSA)［9］是为研究有限内存的计算过程和计算流程提出的一种计算模型。有限状态自动机拥有有限数量的状态，每个状态可以迁移到零个或多个状态，输入字串决定执行哪个状态的迁移。有限状态自动机可以表示为一个有向图。

以目前最为常用的卫星任务规划节点为例，设计中将各节点看成FSA中的不同状态，则在卫星规划过程中，上一个状态可以根据不同的条件转化为多个可能的后续状态。所以，将卫星任务规划流程映射为一个非确定有限状态自动机，由以下5元组组成:

Q表示有穷状态集合，针对卫星规划流程可定制平台特点，所设计的自动机运行状态包括:“伺服悬停”、“载荷任务规划”、“地面资源规划”、“编辑方案”和“地面资源更新”等。

“伺服悬停”状态(Halting State)是指当前没有新的任务需要规划，所以系统处于伺服等待状态。在这个状态下，系统将按时间周期检测是否有任务到达，如发现有任务到达，则向其他规划状态进行转化。

“载荷任务规划”状态(Satellite Scheduling State)表示正在调用载荷任务规划算法，面向地面目标，优化生成卫星载荷动作序列，且载荷任务规划算法尚未计算完毕。一旦载荷任务规划算法计算结果生成，则向其他规划状态进行转化。

“地面资源规划”状态(Resource Scheduling State)表示系统正在运行资源规划算法优化安排地面站跟踪接收资源、测控资源、中继星资源和传输资源等，保证观测数据能够尽早地传送到卫星数据处理中心，且地面资源规划算法尚未计算完毕。一旦地面资源规划算法计算结果生成，则向其他规划状态进行转化。

“编辑方案”状态(Plan Editing State)是人工发起的。该状态表示操作员需要暂停规划流程，开始对已经生成的卫星观测方案和地面资源工作方案进行手工编辑。在“载荷任务规划”、“地面资源规划”或“伺服悬停”状态，操作员可设置进入“编辑方案”状态，对自动化算法规划出的方案进行微调，使之更加符合操作员期望。进入到“编辑方案”状态后，所有自动化计算流程停止，直至操作员退出“编辑方案”状态。一旦操作员退出“编辑方案”状态，系统将自动进入方案编辑前正在运行的状态。

“地面资源更新”(Resource Updating State)是指系统更新可用的地面站跟踪接收资源、测控资源、中继星资源和传输资源等信息，是一种需要系统定期进入的状态，以更新随时间变化的各种可用地面资源信息。一旦资源更新完毕，系统将自动进入方案编辑前正在运行的状态。

Σ是有穷输入字母表。FSA根据接收到的字母确定其下一步转换的状态，该字母必须属于Σ。在卫星规划流程可定制平台中，Σ包括:“伺服悬停”、“卫星任务规划”、“地面资源规划”、“编辑方案”和“地面资源更新”等。一旦自动机接收相应的状态信息，则转化到对应的自动机运行状态上。

δ是状态转移函数，可表示为Q×Σ→2Q。其定义了有限状态自动机根据当前状态和接收到的状态信息确定下一步需要转换到什么状态。

q0表示自动机初始状态。在卫星任务规划流程可定制平台中，系统初始状态设定为“伺服悬停”状态。

F表示终结状态集合，F包含于Q。在卫星规划流程可定制平台中，终结状态集合只包括“伺服悬停”状态。系统完成正常规划后，将进入“伺服悬停”状态，等待下一批规划任务到达。如果最终自动机进入“伺服悬停”状态，代表输入状态信息是合法的。这也是检验定制流程是否合法的唯一标准。

在平台中定义一个3元组来描述状态关系的合法转换:

State_Change=(StateNow，Msg，StateNext)。其中:StateNow表示有限自动机当前处于的状态，StateNow∈Q;Msg表示当前自动机读入的新状态信息，Msg∈Σ;StateNext表示当前有限状态自动机读入新状态信息后将转换到的目标状态，StateNext∈Q。

基于上述有效状态转换关系描述，在卫星规划流程可定制平台中，设计状态转移函数图，如图2所示。

图2 卫星规划流程可定制平台状态转移

2 基于消息的卫星任务规划流程转换方法

图2表示了基于有限状态自动机的卫星规划流程可定制平台状态转换关系。通过消息队列(Message Queue)中间件［10］来实现上述状态转换机制。即当平台收到Message Queue发送来的消息时，根据消息内容决定将要进行转换的状态。消息内容包括要求自动机转换到“伺服悬停”状态、“载荷任务规划”状态、“地面资源规划”状态、“编辑方案”状态和“地面资源更新”状态等状态信息。

当有限状态自动机处于“伺服悬停”状态时，任务规划平台检测到有新的对地观测任务到达，则可向消息队列队尾添加“卫星载荷任务规划”消息，要求有限状态自动机由当前状态转换到“载荷任务规划”状态。同时任务规划平台对消息队列进行监测，如果发现消息队列不为空，则从消息队队列头取出消息进行解析。如果消息解析结果是“卫星载荷任务规划”，则自动机将当前状态由“伺服悬停”转换到“载荷任务规划”状态。同理，如果载荷任务规划完毕，需要启动地面资源规划流程，则可向消息队列队尾添加“地面资源规划”消息。当规划平台检测到消息队列队头消息为“地面资源规划”时，则自动机可将当前状态转换到“地面资源规划”状态。其余的状态转换方式以此类推。

但自动机是否可以转换到指定状态，需要根据有限状态自动机合法转换集合来进行验证。

如果自动机由当前状态转换到消息队列中指定的目标状态的情况在有限状态自动机合法转换集合中没有描述，则称为自动机状态转换异常。自动机状态转换异常是以消息队列方式实现有限状态自动机不可避免的问题。产生自动机状态转换异常的原因可分为以下2种:

①消息生成渠道多源化导致的自动机状态转换异常。如假定当前自动机的状态为“载荷任务规划”状态，且消息队列为空。而这时地面资源更新事件发生，于是“地面资源更新”状态消息被添加到消息队列。任务规划平台检测到消息队列不为空，于是取出消息，解析为“地面资源更新”，要求自动机转换到“地面资源更新”状态。由有限状态自动机合法转换集合可知，自动机无法从“载荷任务规划”状态直接转换到“地面资源更新”状态，从而产生自动机状态转换异常。

②程序异常导致的自动机状态转换异常。如消息队列异常，导致消息队列内各消息次序错乱或错误消息出现，使得自动机无法由当前状态转换到消息指定的目标状态，从而产生自动机状态转换异常。

针对第1种情况，在设计中采用消息转发机制来进行异常处理，即如果自动机可由当前状态转换到消息要求的目标状态，则进行转换;否则将消息重新添加到消息队列队尾，自动机状态保持不变。如上例中，自动机当前状态为“载荷任务规划”状态，但消息为“地面资源更新”，导致了自动机状态转换异常。由于“地面资源更新”消息无法被处理，于是将其添加到消息队列队尾，从而继续开始处理消息队列中消息。当载荷任务规划完毕后，任务规划平台向消息队列添加“地面资源规划”消息，从而自动机可转换到“地面资源规划”状态，当地面资源规划完毕后，任务规划平台向消息队列添加“伺服悬停”消息，从而自动机转化为“伺服悬停”状态。这时，“地面资源更新”消息可被处理，于是自动机状态转换异常被消除。

而针对第2种情况，即程序异常导致的自动机状态转换异常，可采用消息丢弃的方式进行处理。自动机将丢弃非合法转换的消息，并上报该异常，从而保证自动机总是处于合法的状态中。

3 卫星任务规划可定制流程设计

卫星任务规划可定制流程设计中的难点在于判定流程是否合法，主要包括:自动机状态转换流程是否可达、是否存在死锁或活锁、是否能够正确完成等几个方面。

规划流程中每一个节点都代表了一个需要完成的动作，为了完成特定功能，要求每一个节点都能够被顺利地激活。可达性分析主要就是为了判定用户定制流程内的每一个节点是否均能够被激活。如果某个节点不可达，则可分为3种情况:① 无输入迁移，也无输出迁移，即活动是一个单独的单元;② 无输入迁移，有输出迁移，即活动只有输出没有输入;③有输入迁移，没有输出迁移，即活动只有输入没有输出。如果对上述3种情况进行排除，即可完成可达性分析。

流程的死锁是指流程总是在一部分活动中运转而不能执行其他活动，即流程中存在不能激活的活动，从而不能完成整个预定流程。

流程的活锁是指某个活动由于输入迁移条件不断得到满足而陷入无限循环的执行导致整个流程不能结束。

对于死锁、活锁的分析可以借鉴数据库事务处理中的分析思路，通过分析节点之间是否有多余回路，以及通过仿真模拟的方式，分析死锁与活锁发生的可能性。

流程正确性分析主要是判断流程执行完毕时是否合乎最初设计的目标，是否能够顺利完成既定任务。通常这个过程需要规划人员的参与。针对模拟的规划数据进行计算，再与预期结果相比，从而调整规划流程，使之更加符合规划人员预期。

4 任务规划流程定制演示

模拟运行结果如图3所示。

图3 卫星任务规划流程可定制平台实验演示

采用SOA技术构建了系统框架［11］，设计并实现的卫星任务规划流程可定制平台实验系统。系统中流程定义及状态转移采用XML文件描述［12］。

仿真演示中定制的卫星任务规划流程为“伺服悬停”—“资源更新”—“载荷任务规划10”—“地面资源规划3”—“伺服悬停”。其中，流程中数字代表该节点运行次数，即自环路运行。该过程模拟了一般卫星任务规划的主要流程。首先，系统处于“伺服悬停”状态，当接收到新的对地观测任务时，系统进行资源更新，然后启动载荷任务规划10次，地面资源规划3次，以进行迭代寻优，最终进入“伺服悬停”状态，完成一次自动规划过程。

通过平台运行流程演示可以看到，实验系统按照设定的流程完成了卫星任务规划过程，验证了利用FSA模型设计的卫星任务规划系统的可行性，为后续实际工程应用奠定了技术基础。