基于规则引擎的通讯卫星应急任务调度

刘 永，李子扬，窦 帅，周春城，李传荣+

(1.中国科学院光电研究院 中国科学院定量遥感信息技术重点实验室，北京 100094；2.中国科学院大学 电子电气与通信工程学院，北京 100049)

0 引 言

任务调度系统是卫星地面系统的重要组成部分，是进行卫星资源管理与分配的主要工具，负责卫星任务计划的编制、执行和控制调整，在卫星资源相对稀缺、用户的任务需求不能全部满足的情况下，实现卫星资源的合理分配与冲突资源的优化调度尤为重要[1,2]。随着航天事业的发展，卫星功能不断增强，卫星任务需求与任务调度模式不断演进[3]，使得调度规则发生变化，促使调度系统不断升级。传统方式使用配置文件或配置参数来增强系统的柔性和灵活性，但功能相对有限，难以适应具体调度规则的变化。因此建立一个柔性的、灵活性较高的任务调度系统，方便调度规则的修改和定制，降低调度系统的维护成本，是十分必要的。

为此本文将规则引擎技术应用于独占资源卫星任务调度中，通过规则引擎将调度规则从业务逻辑代码中分离出来，减少调度规则的变动对业务逻辑代码的影响，增强调度系统的柔性和灵活性，降低调度系统维护的风险及成本。同时设计基于权重的推理网构建方法，优化了推理网的结构，提高了调度系统的运行效率。

1 独占资源通讯卫星应急任务调度策略

根据任务调度模式的不同可将独占资源通讯卫星任务调度分为集中任务调度和应急任务调度[4,5]。集中任务调度是在本周的某固定时间对用户提交的下周的卫星资源使用申请进行集中处理的过程，按照规定，在集中调度时间点后提交的一般性卫星资源使用申请在本次调度周期中不予受理，但是由于突发的重要事件而产生的紧急卫星资源使用申请，需进行及时的特殊处理，这其中特殊处理被称为应急任务调度模式。

在集中任务调度模式中，任务调度响应的时间要求并不紧急，调度目标是在满足任务时效性的前提下实现调度任务的优先级之和最大，一般采用遗传算法等智能优化算法求解近似最优调度方案。应急任务调度模式是在集中任务调度方案的基础上进行的再调度，由于应急任务的突发性、紧急性及重要性，这类任务拥有较高的优先级和任务价值，所以采用基于优先级的调度策略，使优先级高的任务具有优先执行权。

本文调度的思路是当有应急任务提交时，在集中任务调度方案的基础上采用直接调度或冲突替换原则。直接调度原则为当应急任务满足卫星资源使用的各种约束，且申请的卫星资源处于空闲状态，则将该任务直接纳入卫星工作计划。冲突替换原则为应急任务满足卫星资源使用的各种约束，但申请的卫星资源处于被占用状态时，即应急任务与已有的卫星工作计划发生资源使用冲突，如果与应急任务产生冲突的计划数量为一，且应急任务的优先级大于计划的优先级，则用应急任务替换掉与之冲突的计划，反之则不予替换；如果与应急任务产生冲突的计划数量为多个时，并且应急任务的优先级大于所有与之冲突的计划的优先级，则用应急任务替换掉与之冲突的所有计划，反之则不予替换。这种替换虽然导致某些已经被调度的任务无法执行，但是从实际情况分析，紧急、重要的任务被优先执行是合理的。

2 规则引擎技术

规则引擎的定义请参见文献[6]。

Drools是用Java语言开发的规则引擎，其内部使用的模式匹配算法是Rete，速度快、效率高。它采用声明式的程序设计方式，比其它命令式的编程语言代码更简洁；可通过规则库高效解决业务规则变动问题，更灵活地适应各种变化的业务场景。

Drools的组成如图1所示。

图1 规则引擎的组成

各部分的作用如下：

(1)工作内存(Working Memory)：存放系统工作时要处理的数据对象(Fact)；

(2)规则库(Rule Base)：存放脚本语言编写的业务规则；

(3)模式匹配器(Pattern Matcher)：进行数据与规则的匹配，创建规则的执行实例，并将实例加入议程中；

(4)议程(Agenda)：存放所有的规则执行实例，并根据某种策略制定实例的执行顺序；

(5)执行引擎(Execution Engine)：执行议程中所有的规则执行实例。

Drools在工作时通过模式匹配器将工作内存中的事实和规则库中的规则进行匹配，对匹配成功的规则创建执行实例，并将这些实例加入议程中。议程根据某种策略制定这些实例的执行顺序，形成实例的执行队列。执行引擎按照顺序依次执行。在执行过程中事实对象的状态会发生变化，即产生新的事实，使得某些未执行的实例失效而从队列中剔除，也可能形成新的执行实例加入队列中，形成一种动态的规则执行链[7-9]。

3 基于Drools规则引擎的独占资源通讯卫星应急任务调度系统

结合上述研究，将规则引擎技术应用于独占资源通讯卫星应急任务调度中，实现调度规则与应用程序的分离，提高系统的灵活性、可扩展性及易维护性，并对Drools规则引擎进行改进，优化了推理网的构建过程，提高了系统的工作效率。

3.1 系统结构

独占资源通讯卫星应急任务调度系统采用C/S架构，分为数据层、服务层、应用层。应用层主要为卫星控管中心提供申请信息管理、计划信息管理、调度规则管理和卫星资源管理等；服务层实现了系统运行中涉及的各类服务，包括规则推理服务、数据管理服务、任务调度服务等；数据层使用关系数据库为系统提供数据管理功能，数据库包括用户申请数据库、卫星工作计划数据库、卫星资源数据库、调度规则数据库，如图2所示。

图2 调度系统的结构

3.2 应急任务调度规则

规则库是基于规则引擎的系统的核心，是系统进行业务判断与决策的依据，规则库的质量对处理结果的准确性及系统的运行效率有着直接影响。因此要得到良好的卫星任务调度结果和系统工作效率，在建立调度规则库时，需要对应急任务模式下的调度规则进行精确的凝练和表达，对规则库的结构进行合理设计。

通过章节1中对应急任务调度场景的分析与调度思路的设计，结合卫星资源使用约束，凝练出如下13条应急任务调度规则：

规则1：如果申请的状态值为“null”，则申请的状态值由“null”转为“受理”；

规则2：如果状态值为“受理”的申请的用户目标不是当前用户中心的管理型号，则申请的状态值由“受理”转为“不受理”；

规则3：如果状态值为“受理”的申请的通信波段不在其申请的独占资源通讯卫星通信波段范围内，则申请的状态值由“受理”转为“不受理”；

规则4：如果状态值为“受理”的申请的任务持续时长小于2分钟，则申请的状态值由“受理”转为“不受理”；

规则5：如果状态值为“受理”的申请的服务开始时间早于系统当前时间，则申请的状态值由“受理”转为“不受理”；

规则6：如果状态值为“受理”的申请的用户目标是地面设备，则申请的状态值由“受理”转为“可视”；

规则7：如果状态值为“受理”的申请的卫星资源使用时段在独占资源通讯卫星与用户目标可视窗口内，则申请的状态值由“受理”转为“可视”；

规则8：如果状态值为“受理”的申请的卫星资源使用时段不在独占资源通讯卫星与用户目标可视窗口内，则申请的状态值由“受理”转为“不可视”；

规则9：如果状态值为“可视”的申请的卫星资源处于空闲状态，则申请的状态值由“可视”转为“纳入计划”；

规则10：如果状态值为“可视”的申请的卫星资源处于占用状态，则申请的状态值由“可视”转为 “冲突”；

规则11：如果状态值为“冲突”的申请的冲突对象是调度方案中卫星工作计划，且申请的优先级大于与其冲突的计划的优先级。则申请的状态值由“冲突”转为“纳入计划”，与其冲突的计划状态值由“计划”转为“被替代”；

规则12：如果状态值为“冲突”的申请的冲突对象是调度方案中卫星工作计划，且申请的优先级小于与其冲突的计划的优先级。则申请的状态值由“冲突”转为“拒绝纳入计划”；

规则13：如果申请的状态值为“纳入计划”，则调用卫星资源分配函数将申请写入计划表。

为了清楚表达上述规则间的联系及申请在规则推理过程中的状态变化情况，采用状态机图进行的表达如图3所示。

图3 申请的状态机

3.3 基于Drools规则语法的调度规则形式化表示

Drools采用原生的规则语言，规则结构简洁、可读性强[10]。规则的结构组成如图4所示。

图4 Drools规则结构

关键词rule标识一条规则的开始，其后是该规则名称，是规则在规则库中的唯一标识，具有唯一性；关键字attributes是规则属性，是可选项，用于对规则的行为进行限定；关键字when是规则条件(left side hand,LHS)部分开始的标识，LHS是一些逻辑表达式，用于判断；关键字then是规则结论部分(right side sand,RHS)开始的标识，RHS是一个Java语言代码块，是要执行的操作；关键字end表示规则的结束。

以3.2中的rule7为例，其对应“Drools”规则引擎的代码如下：

rule “IsvisiableRule” //规则名称

salience 10 //规则优先级

no-loop true //不能被同一事实再次激活

when

$app: Application(station==accepted); //申请状态

$vw: VisiableWindow($app.satelliteID== satelliteID,$app.usertargetcode==user,$app.starttime>= starttime, $app.endtime<=endtime); //受理的申请是否在可视窗口内

Then

$app.setStation (“visible”); //状态修改为可视

update($app); //更新申请状态

end

其中规则属性使用的是salience(优先级策略，salience值越大表示规则的优先等级越高)、no-loop(值为true时，该规则不会被同一事实再次激活)，分别用于解决规则冲突和规则库死循环问题。

3.4 基于Drools的任务调度规则引擎的改进

Drools中使用的是目前效率最高的Forward-Chaining推理算法Rete。Rete算法将规则库构建成推理网的形式，以达到显著降低计算量的效果，并且Rete算法利用推理引擎的时间冗余性和产生式规则结构相似性的特点，在推理网的构建中实现状态保存机制和节点共享机制，极大提高了Drools的工作效率[11,12]。

在实验的过程中发现，Drools中的节点共享机制并非广泛意义上的共享，其对规则结构有着较严格的要求。下面给出3个规则组，每个规则组中都有两条规则，并且规则中的匹配条件相同，不同在于规则中的匹配条件排列顺序不同。

规则组一：

rule “rule_1”

when

$app: Application (UserID==“GD”, satelliteID==“A”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(satelliteID==“B”,UserID==“GD”)；

Then

{Code}

End

规则组二：

rule “rule_1”

when

$app: Application(satelliteID==“A”，UserID==“GD”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(satelliteID==“B”,UserID==“GD”)；

Then

{Code}

End

规则组三：

rule “rule_1”

when

$app:Application(UserID==“GD”, satelliteID==“A”)；

Then

{Code}

End

rule “rule_2”

when

$app:Application(UserID==“GD”, satelliteID==“B”)；

Then

{Code}

End

3个规则组对应的推理网如图5所示。

图5 推理网

Root Node是所有对象进入推理网的入口；Type Node进行对象类型的判断，只有类型匹配成功的对象才能进入下一个节点。Alpha Node又称单输入节点，用来对单一的对象进行条件判断，对应着规则中的逻辑判断。当规则有多个逻辑判断，对应的Alpha Node会串联在一起。对象在满足当前Alpha Node对应的逻辑判断后才能进入下一个Alpha Node；Adapter Node将单个对象转为单对象数组。Terminal Node表示对象与规则完全匹配。

从图5看出UserID==“GD”节点在规则组三的推理网中实现了规则间的共享，但在规则组一、二中没能实现共享，使得规则组三的推理网较其它两组节点更少，系统存储开销更小，工作效率更高。3个规则组的实现的功能相同，但形成的推理网结构不同，说明规则中逻辑判断的排列顺序不会影响规则的功能，但会影响推理网的结构，进而影响系统性能。

产生这种现象的原因是Drools在构建推理网时，如果一条规则中有多个逻辑判断，那么它们对应的Alpha Node在推理网中的连接顺序与其在规则中的排列顺序是一致的，在这里称为基于顺序的连接方式。规则组一的推理网中，两个UserID==“GD”节点的内存中存储的数据对象并不相同(rule_1的UserID==“GD”节点中存储的是满足自身逻辑判断的数据对象，rule_2的UserID==“GD”节点中存储的是满足satelliteID==“B”节点和自身逻辑判断的数据对象)，此时二者是两个同名不同质的Alpha Node，不能合并为一个共享节点，规则组二同理。所以规则组一、组二中虽然有相同的逻辑判断，但由于规则原生结构的限制，使推理网中的同名节点不能共享。

综上所述，Drools中这种基于顺序的连接方式，使推理网的结构与规则的结构形成强关联性，不具备节点连接时的动态调整能力，导致某些相同的Alpha Node没能实现共享。针对这一问题本文提出基于权重的连接方式：在构建推理网时，如果一条规则中有多个逻辑判断，权重大的逻辑判断对应的Alpha Node会获得优先连接权。具体改进方法为：首先统计规则库中所有的逻辑判断总数，然后将相同的逻辑判断归为一类并统计其数量，最后计算各类逻辑判断的权重。计算方法为λi=(ni/N)，其中λi表示逻辑判断i的权重值，ni表示规则库中逻辑判断i的个数，N表示规则库中逻辑判断总数。这样各类逻辑判断都拥有自己的权重值。在构建推理网时，对于一条规则中的多个逻辑判断，Rete算法根据其权重值从大到小的顺序依次获取并构建对应的Alpha Node。这种基于权重的连接方式，使推理网的结构摆脱了规则原生结构的限制，充分利用规则库中相同逻辑判断在数量上的特征，并将这种特征用于推理网的构建过程中，使相同的逻辑判断可以实现共享，降低推理网结构的冗余性，提高推理效率。

3.5 调度系统驱动数据及其表示

系统进行调度工作使用的数据包括：卫星可视窗口(用户目标与独占资源通讯卫星之间的可视时段)、卫星工作计划、用户任务申请，其中前二者称为卫星系统资源状态事实，第三个称为待调度事实。为实现调度系统对数据的处理及数据在数据库中的有效存储与管理，需要对用户申请、可视窗口、卫星工作计划3类数据进行规范化表示。根据Java面向对象的编程特点，分别建立用户申请类、可视窗口类、卫星工作计划类，每个类具有各自的属性及其对应的getter和setter方法。例如用户申请表示形式见表1。

表1 用户申请

4 实 验

由于应急任务的特殊性，所以应急任务调度模式是一种实时调度，采用的是“申请-响应”的调度方式。下面两组实验，分别使用基于Drools改进前、后的任务调度系统对一天内(24 h)接收的50条应急申请进行调度，验证调度系统的性能，并对Drools规则引擎改进前后的性能进行对比。其中实验组1中的50条应急申请满足卫星资源使用各种约束且与卫星工作计划无冲突；实验组2中的50条应急申请满足卫星资源使用各种约束但与卫星工作计划有冲突，其中，25条申请优先级大于计划，25条申请优先级小于计划。

4.1 实验环境与数据概述

本文实验的原型系统在eclipse中开发，规则引擎为Drools6.5，数据库为MySQL8.0，服务器为TomCat7.0，运行平台为windows10，CPU:Intel i3-3110M 2.4GHz。

实验中包括4颗通讯卫星，10颗用户卫星，使用的数据有卫星间可视窗口、用户申请、卫星工作计划，其中卫星间的可视窗口数据通过卫星星历计算得出，用户申请由模拟实际用户申请程序生成，卫星工作计划由集中任务调度程序生成。

4.2 实验结果

系统运行时间的统计结果和申请处理结果如图6和表2所示。

图6是两组实验中50条应急申请的处理时间的折线图，表2是处理时间统计出的均值和方差及申请调度的结果。对实验结果从以下4个方面进行分析：①从Drools改进前后系统的运行时间进行对比分析，可以看出改进后的系统运行时间效率相比改进前提高了5%左右，说明文中提出的改进方法提高系统性能，规则数量越多，相同的逻辑判断越多，效率的提升越明显；②从两组实验对照角度分析，可以看出系统在处理有冲突的申请用时比无冲突的多，但是差距在20 ms内，说明系统在处理资源使用冲突时，

图6 系统运行时间折线

表2 系统运行时间特征及申请调度结果统计

具有良好的优化调度效率；③从系统处理50条申请的时间方差角度分析，方差在5 ms2上下，说明系统运行的稳定性较好；④从申请调度后纳入计划的结果分析，实验组1中50条无冲突的申请全部纳入计划，实验组2中50条有冲突的申请，其中优先级大于计划的25条纳入了计划，优先级小于计划的25条没有纳入计划，调度结果跟预期设想的结果一致，说明系统调度结果可靠。

5 结束语

本文将规则引擎技术应用于独占资源通讯卫星应急任务调度中，实现了调度规则与业务逻辑代码的分离，便捷了调度规则的集中管理与修改，降低了调度规则变动对系统造成的影响，提高了系统的灵活性和适用性。同时设计基于权重的连接方法对Drools规则引擎进行改进，优化了推理网的构建过程，降低了推理网中节点冗余问题，提高了系统的运行效率。实验结果表明，基于改进的Drools规则引擎的独占资源通讯卫星应急任务调度方法切实可行。在处理卫星资源使用冲突时如何通过规则引擎实现用户申请窗口的滑动，进一步提高申请调度成功率，将是我们下一步的工作。