信息物理系统(Cyber-Physical Systems, CPS)是将计算过程和物理过程集成的系统, 利用嵌入式计算机和网络对物理过程进行监测和控制, 并通过反馈环实现计算和物理过程的相互影响^[1]. CPS概念自提出以来, 迅速在众多重要环节中承担关键任务, 广泛应用在智慧建筑^[2]、生产制造^[3]、交通运输^[4]、医疗健康^[5,6]和城市建设^[7]等领域. CPS本质就是构建一套赛博(Cyber)空间与物理(Physical)空间之间基于数据自动流动的状态感知、实时分析、科学决策、精准执行的闭环赋能体系, 解决生产制造、应用服务过程中的复杂性和不确定性问题, 提高资源配置效率, 实现资源优化^[8]. CPS监控是从物理设备产生的事件中感知关注场景并作出响应的过程, 是CPS的核心功能之一.

实时性是CPS的特点之一^[9], 为CPS监控带来了时间约束问题, 即从与监控关注场景相关的所有原子事件到达系统开始到触发关注场景关联的动作之间的时间间隔(也称为响应时间)不应超过其上界(这个上界称为截止期), 否则将造成严重的后果. 例如, 在智慧建筑CPS中, 存在诸多监控场景, 例如, 节能场景、环境舒适度调节场景和火灾监控场景等. 其中火灾监控场景具有时间约束要求, 国家标准GB4717-2005规定查询和处理数据等火灾报警操作不超过10 s. 这个10 s就是一个从事件发生到触发火灾报警动作的截止期, 错失截止期可能会造成火灾事故, 从而造成生命和财产损失. 这样的CPS监控场景还有很多, 比如高速列车故障控制系统、电网故障诊断系统等.

在这样的CPS监控中, 事件与动作之间的因果关系往往使用规则来描述. 针对监测到的事件, 判断某条规则所描述的事件模式是否满足, 从而得出动作的过程, 称为针对此条规则的推理过程, 上述对监控事件作出响应的过程, 可视为一系列规则推理过程的集合^[10]. 采用规则系统相较于过程式逻辑具有若干优势, 如规则灵活性更强(当业务需求变化时, 更新规则库中规则即可, 应用无需重新编译部署)、更直观易理解(例如智慧建筑中监控服务“当房间温度低于18度时, 则打开空调制热”)、更低的复杂度(规则具有一致性表示)等.

为此, 学者们对基于规则的CPS监控进行了探索. Sun等人^[11-13]使用基于Rete^[14]算法的规则引擎对大规模智能建筑产生的事件进行高效处理. Klein等人^[15]提出了一种结合ECA (Event-Condition-Action)^[16]和CEP (Complex Event Processing)^[17]的基于规则的方法来对CPS中产生的事件进行监控. 然而, 上述基于规则的CPS监控研究工作未考虑CPS监控的时间约束. 关于时间约束问题, 学者们也提出了一些方法, 如: 迭代推理^[18](如Anytime算法)、多重方法推理^[19](如Design-to-Time算法)和渐进式推理^[20,21](如GREAT算法和PRIMES算法). 这些方法为整个推理过程定义了截止期约束, 通过对推理运行时间与推理结果质量进行折中来满足这个截止期约束. 李想等^[22]介绍了一种面向物联网的实时复杂事件处理引擎, 该引擎采用一种启发式复杂事件处理算法来优先处理能够产生结果的任务, 缩短了复杂事件处理的响应时间, 同时介绍了一种复杂事件处理程序的最坏响应事件估算算法, 但忽略了各监控任务不同的紧迫度. Liu等人^[23]使用复杂事件处理技术来对智能电网中产生的事件进行处理. 然而, 上述工作主要是缩短了CPS监控的响应时间, 但不能使CPS监控尽可能地满足其时间约束.

此外, 学者们还通过改进典型的规则匹配Rete算法来缩短匹配时间以及进行一些功能扩展如模糊推理、事件处理和并行化等方面, 但未考虑Rete算法在推理过程中的时间约束问题. William Van Woensel等人^[24]提出了一种改进的Rete算法, 支持在内存受限环境下进行规则推理. 文献[25,26]对Rete的语法结构进行扩展, 即根据规则的and、or等逻辑操作将规则构建成一个抽象语法树, 并在语法树的基础上建立Rete网络, 逻辑操作符本身作为一个Rete节点参与事实匹配. 这种做法减少了规则拆分开销, 给规则匹配带来了便利. 文献[27]对规则中的条件进行了重排序. 规则中条件顺序是指规则条件中的各个约束的排列顺序, 它决定了条件的执行顺序, 是决定规则匹配效率的关键因素. Xiao等人^[28]将Beta内存分成若干单元, 每个单元分配一个id, 对事实用哈希函数计算索引, 索引号即为某个单元的位置, 通过索引快速找到相应单元进行匹配, 如果匹配不成功, 则将该对象组成一个新的单元加入相关内存. 孙新等人^[29]提出了一种基于共享度模型的改进Rete算法, 可以提升Rete网络的推理速度. Ju等人^[30]研究将 Rete算法在Apache Spark上进行并行化. 汪成亮等人^[31]提出了智能环境下分布式Rete算法, 将推理网络中的计算任务分布式地部署到最靠近参数采集的传感器节点中, 让这些传感器充分参与到推理计算工作中.

为此, 本文基于实时规则引擎建立了一个CPS的实时监控系统RTCPMS (Real-Time Cyber-Physical Monitoring System), 该系统采用Rete网络表示监控规则. RTCPMS将实时推理技术和CPS监控结合, 其核心是一个新的实时推理算法Rete-TC. Rete-TC算法引入了规则截止期, 通过基于优先级的Beta节点调度方法, 使得CPS监控的时间约束尽可能地被满足. 模拟实验与智慧建筑应用案例验证了RTCPMS系统的有效性, 且实验结果表明其核心算法Rete-TC的调度成功率优于传统的规则推理算法Rete.

本文接下来的组织结构如下: 第1节介绍了研究基础; 第2节介绍了Rete-TC实时规则推理算法; 第3节介绍了系统框架; 第4节进行了模拟实验评估; 第5节进行应用案例研究; 第6节进行总结了及下一步工作.

1 研究基础 1.1 术语和定义

在CPS中, 原子事件是不可再分的, 只存在发生和不发生两种状态, 其来源包括传感器或其他感知设备. 关注场景是按照定义在规则中的事件条件从原子事件中检测得到.

定义1. 原子事件(atomic event)

原子事件由属性类型名和属性组成, 可表示为(EventTypeName Attributes), 其中 EventTypeName表示事件的类型, Attributes = ((Name₁ Value₁), ···, (Name_n Value_n))表示事件的属性, 属性是有序的. 每个属性由属性名和属性值构成. 例如, 一个事件类型为“ClassA”的原子事件可以表示为“(ClassA (val₁ 365) (val₂ 928) (val₃ 153) (val₄ 497))”.

定义2. 约束(constraint)

约束可以表示为(Param₁ op Param₂). 它由Param₁, op和Param₂组成. 这里Param₁是事件属性名, 为变量; op为常见的逻辑操作符, 例如>, <, ==, >=, <=; Param₂可以是一个常量或一个变量(另一个事件的属性名). 当约束为“变量-op-常量”时, 它用于确定一个事件的属性和常量之间的关系, 称为常量约束, 例如, (Person.age > 15). 当约束为“变量-op-变量”时, 它用于确定事件属性关系, 称为变量约束, 例如, (C1.attr > C2. attr).

定义3. 事件条件(event condition)

事件条件可表示为:

(＄EventTypeBindName : EventTypeName (Constraint₁ OP Constraint₂ OP ···Constraint_n))

其中＄为变量绑定符，EventTypeBindName为事件对象绑定的变量名，用于支持将多个同类型事件对象绑定到不同的＄EventTypeBindName上 (因为同一事件对象在一条规则中可能出现多次). EventTypeName含义参见定义1. Constraint 参见定义2. OP指“and” (也表示为“&&”)，“or”(也表示为“||”)连接操作符. 事件条件有时也称为事件模式.

定义4. 实时规则(real-time rule)

实时规则由用户定义, 可表示监控场景. 规则由规则名、规则截止期、事件条件集和动作集组成. 其中事件条件集也称作左手部分(Left-Hand Side, LHS), 动作集也被称作右手部分(Right-Hand Side, RHS). 基于Drools^[32]规则语言, 我们定义的实时规则格式如下:

rule “name”

deadline n

when

事件条件1∪事件条件2∪···∪事件条件N

then

动作1∪动作2∪···∪ 动作N

end

“deadline n”表示规则的截止期为n秒, 截止期大小一般由应用确定. 如果n取0, 则表示规则无时间约束.

1.2 Rete推理算法 1.2.1 Rete基本概念

Rete是一个经典且高效的规则匹配算法, 已被广泛应用到许多主流的规则推理引擎中. Rete 算法作为一种前向链推理算法, 其核心思想是采用增量匹配的概念, 根据内容动态构造匹配树, 以达到显著降低计算量的效果. 目前主流规则推理引擎(例如Drools)使用Rete算法. Rete算法将规则转换成Rete网络, 表示各种规则条件间的数据依赖. 当事实或事件对象进入系统后, 它将在Rete网络上匹配传播, 直到抵达规则的终止节点, 即完成一条规则的匹配, 进而触发该规则预定义动作. Rete网络包括两部分: Alpha网络和Beta 网络. Alpha网络包括4类节点: 根节点(Alpha root node)、类型节点(Object type node)、条件节点(Alpha node)和Alpha内存节点(Alpha memory node). 根节点是所有事实或事件对象进入Rete网络的入口, 是一个虚节点, 无实际意义. 类型节点是根节点的直接子节点, 保存了规则中事实或事件对象对应的类型. 如果某对象类型的模式有条件约束, 则该约束会进入Alpha 网络形成条件节点, 完成事实或事件中属性的常量约束测试(例如, 检查属性 Person.age > 15), 这样可以过滤掉大部分无意义的事实或事件对象. Alpha内存(Alpha memory)节点是Alpha网络的最后一层节点, Alpha内存存储所有通过常量约束测试的事实对象, 也称为Alpha匹配(Alpha Match, AM). Beta 网络包含3类节点: 连接节点(Beta node)和终止节点(Terminal node)和Beta网络根节点(Beta root node). 连接节点的输入来自上一级的Beta节点和Alpha内存节点, 负责执行变量约束测试(例如, C1.attr > C2.attr), 即判断两个事实或事件对象在某一属性值上的关系, 通过该测试的事实或事件数据被称为部分匹配(Partial Match, PM), 即成功匹配了规则的一部分约束但还没完全匹配所有约束的部分事实或事件数据, 每个Beta节点都保存着通过上一级Beta节点变量约束测试的PM数据, 并使用这些数据完成本节点的变量约束测试, 之后将匹配结果传递给下一级Beta节点, 直至抵达规则终止节点; 规则终止节点是出度为0的节点, 是Rete 网络的叶子节点, 也是一条规则的最后一个节点, 当事实或事件数据到达该节点时, 表明该条规则被触发. Beta网络根节点为一个虚节点, 不具有实际意义.

1.2.2 Rete网络构建流程

假设有规则集Ri(1 ≤ i ≤ N), Rete网络构建流程如下:

(1) 建立Rete网络的根节点Alpha root node和Beta网络根节点Beta root node;

(2) 处理规则Ri;

(3) 处理Ri中的事件条件Cj(1 ≤ j ≤ n), 假如Cj不存在于Alpha网络中, 则将Cj作为Alpha(j)节点插入Alpha网络;

(4) 对Cj中的变量约束, 新建Beta节点, 该Beta节点的左输入是上一级的Beta节点(如果是第一个Beta节点, 左输入为Beta root node节点), 右输入是当前Cj的事件对象的Alpha(j);

(5) 重复(3) ~ (4)处理完所有事件条件;

(6) 重复(2) ~ (5)处理完所有规则.

由于本文所提Rete-TC (Timing Constraints)算法重点改进Rete算法的Beta网络部分, 下面将举例对Rete中的Beta网络部分进行重点介绍, Alpha网络不再详细赘述.

假设有如下规则:

rule “R1”

when

　＄1 : C1 (attr1 == 120 && attr2 == 220)

　＄2 : C2 (attr1 == 55 && attr2 == ＄1.attr2)

　＄3 : C3 (attr1 == $2.attr1 && attr2 == ＄2.attr2)

then

　Actions

end

rule “R2”

when

　＄1 : C1 (attr1 == 120 && attr2 == 220)

　＄2 : C2 (attr1 == 55 && attr2 == $1.attr2)

　＄4 : C4 (attr1 == $1.attr1)

　＄5 : C5 (attr2 == $2.attr2)

then

　Actions

end

rule “R3”

when

　＄1 : C1 (attr1 == 120 && attr2 == 220)

　＄2 : C2 (attr1 == 55 && attr2 == ＄1.attr2)

　＄4 : C4 (attr1 == ＄1.attr2)

　＄3 : C3 (attr1 == ＄2.attr1 and attr2 == ＄2.attr2)

then

　Actions

end

根据上述规则建立的Rete网络如图1所示. 图1中左半部分β1~β6为Beta网络中的Beta节点, 也称作连接节点. 连接节点的输入来自上一级的Beta节点(β1节点为Beta网络中第一个节点, 其左输入为Beta根节点)和Alpha内存节点, 负责执行变量约束测试. 例如, β2节点的输入来自上一级的Beta节点β1和Alpha内存节点AM2, 负责执行变量约束测试“C2 : attr2 == $1.attr2”. β3节点的左输入来自于β2和Alpha内存节点AM3, 负责执行变量约束测试“C3 : attr1 == $2.attr1”和“C3 : attr2 == $2.attr2”. 其中β1和β2节点为R1、R2和R3规则共享, β4节点为规则R2和R3共享.

定义5. 规则路径

从Beta网络根节点到某个规则终止节点之间相连的Beta节点构成的路径.

定义6. 规则路径节点集RP

规则路径节点集为某条规则的规则路径上所有Beta节点的集合. 例如, 图1中的规则R1的路径节点集RP_R1 = {β1, β2, β3}.

1.2.3 Rete算法的匹配过程

Rete网建立后, 事件对象从Alpha根节点进入网络, 如果相关的Alpha常量约束测试通过, 则激活后继相关Beta节点. Beta网络中的激活有两种方式, 如果Beta节点接收到左输入Beta节点传递来的部分匹配(Partial Match, PM), 称为左激活. 左激活发生时, Beta节点会遍历其相关的Alpha内存中的Alpha匹配(AM)和新到来的PM进行变量约束测试; 如果Beta节点接受右输入Alpha网络传递过来的AM, 称为右激活. 此时, Beta节点会遍历该节点的PM和输入的AM进行变量约束测试. 左激活和右激活中的变量约束测试如果通过则产生新的部分匹配(PM)向后继Beta节点传递并激活相关Beta节点.

激活的Beta节点存放在Beta节点激活队列中, 如图2所示. 激活的Beta节点按激活时间依次存入Beta激活队列的队尾, 后续依次从Beta激活队列的队首取出Beta节点进行处理, 即按照FCFS (First Come First Service)的方式处理.

1.2.4 Rete算法的局限性

Rete网络中Beta节点的处理是按Beta节点激活时间顺序处理, 即FCFS (First Come First Service)的方式, 这会造成时间约束强的监控场景中的Beta节点无法得到及时处理, 从而无法尽可能满足监控场景的时间约束. 例如, 假设规则1的规则路径节点集RP1 = {β1, β2, β3, β6}, 规则2的规则路径节点集RP2 = {β1, β2, β4, β7}. 规则1代表的是建筑节能监控场景(例如, 当房间无人时, 关闭灯光和空调). 规则2代表的是建筑火灾监控场景(例如, 当监控到房间发生火灾时, 立刻进行报警等). 显然规则2比规则1具有更强的时间约束. 假设β4代表火灾监控场景中的某个条件, 此时发生的事件使得β4被激活, 但β4会被放置在激活队列的队尾, 而Rete算法按照激活队列的中Beta节点激活顺序依次处理. 这可能会造成时间约束强的监控场景(例如, 火灾监控场景)得不到及时处理.

1.3 基于规则的监控场景表示

假设当前存在这样一个建筑火灾监控场景: 当房间4个角落的烟雾传感器和温度传感器值同时超过阈值时, 则表示房间发生严重的火灾. 该火灾监控场景必须在3 s内监测到并触发火灾报警相关的行动, 否则将造成严重的损失. 上述建筑火灾监控场景可用规则表示如下:

rule “Room fire alarm”

deadline 3

when

　$j :J (temp>55 && smoke >100)

　$g:G (temp>55 &&smoke>100)

　$e:E (temp>55 && smoke >100)

　$b:B (temp>55 && smoke >100)

then

　Raise fire alarm

end

2 Rete-TC实时规则推理算法

当前可用规则表示监控场景,在规则推理中常使用Rete算法, 但Rete算法未考虑规则的截止期, 执行具有更晚截止期的规则可能会延迟具有较早截止期的规则, 这样可能会造成时间约束强的规则错失截止期, 从而无法尽可能满足监控场景的时间约束.

为了克服上述Rete算法的缺点, 基于Rete, 我们提出了一种适用于实时监控的实时推理算法Rete-TC (Timing Constraints). Rete-TC算法引入了规则截止期, 通过基于优先级的Beta节点调度方法, 使得CPS监控尽可能满足时间约束.

2.1 Beta节点调度

规则的截止期代表了该条规则的紧迫度. 所以, 具有更早截止期的规则应优先处理.

建立了Beta节点的优先级计算方法:

$ {\rm P}\left( \beta \right) = \mathop {\min }\limits_{r \in \mathop R\nolimits_\beta } \left\{ {deadline\left( r \right)} \right\} $

(1)

其中, r为一条规则, r∈R_β, R_β是规则的路径节点集中包含β的规则集合. 例如, 图1中的规则R1路径节点集RP_R1 = {β1, β2, β3}. deadline(r)表示规则r的截止期; P(β)越小, β节点的优先级越大. Beta节点处理按照Beta节点的优先级从大到小的顺序进行, 从而使得具有更早截止期的规则将被优先触发. 另外, 当P(β)为0时, β节点按照激活时间顺序放入激活队列的末尾, 表示该Beta节点对应的规则无时间约束要求.

2.2 Rete-TC算法描述

Rete-TC算法有3部分组成, 分别是算法1 Beta节点优先级计算、算法2 Rete-TC网络构造算法、算法3 Rete-TC匹配, 各算法伪码如下. 算法1按照公式(1)计算每条规则产生的Beta节点的优先级, 优先级作为每个β节点的属性. 算法1在算法2 Rete-TC网络构造算法中调用.

按照式(1)Beta节点的优先级计算方法, 图3中的β4节点将依据优先级进入到激活队列中的相应位置(具体位置可由β4节点的优先级与激活队列中已有的Beta节点的优先级比较决定, 最终激活队列中Beta节点优先级从队首到队尾优先级递减), 从而β4代表的具有强时间约束要求的火灾监测场景可以获得优先处理.

算法2. Rete-TC网络构造算法完成Rete-TC网络构造, 与Rete网络构造区别是增加Beta节点优先级计算(在Rete网络构造的结尾处即第17行通过调用算法1实现). 由此可见, β节点优先级在Rete-TC网络构造完成时已确定. 算法2中第4~6行完成Alpha网络的构造. 第7~14行完成Beta网络的构造. 算法3 Rete-TC 匹配完成规则推理, 在Rete匹配算法的基础上主要增加了第5、12和15行Beta节点激活队列更新维护模块UpdateAtiveNodesByPriority, 其余保持不变.UpdateAtiveNodesByPriority模块内部主要采用红黑树数据结构, 支持在O(logN)时间复杂度内对优先级队列中元素进行排序(N为优先级队列中Beta节点个数), 相较于Rete算法中对激活的Beta节点管理采用的FIFO数据结构(时间复杂度为O(1)), 匹配时间虽略有增加, 但影响不大, 我们在实验评估环节进行了验证分析. 算法3中第2~8行完成Alpha节点处理, 第9~17行完成Beta节点处理.

Rete-TC算法过程为先调用算法2 Rete-TC 网络构造, 之后调用算法3进行Rete-TC匹配.

算法1. Beta节点优先级计算

输入: Rule Set

输出: The priority of each Beta node

01: 　 for Riin Rule Set do

02: 　　 for βi generated by Ri do

03: 　　　The priority of βi← Equation(1)

04: 　　 end for

05: 　 end for

算法2. Rete-TC 网络构造

输入: Rule Set

输出: Rete-TC网络

01: 　Create alpha root node and beta root node

02: 　 for i = 1; i ≤ RuleNum; i++ do

03: 　　 for j = 1;j < ConditionNum of R i; j++ do

04: 　　　 if Condition_j不在 Alpha网络 then

05: 　　　　将Condition_j作为Alpha(j)节点插入Alpha网络

06: 　　　 end if

07: 　　　 if j ≥2 then

08: 　　　　 if j == 2 then

09: 　　　　　将Beta(1)节点插入到Beta网络, 左输入为Beta root node和右输入为Alpha(1)

10: 　　　　 end if

11: 　　　　 if j > 2 then

12: 　　　　　将Beta(j)节点插入Beta 网络中, 其父节点为Beta(j–1)和Alpha(j):

13: 　　　　 end if

14: 　　　 end if

15: 　　 end for

16: 　 end for

17: 调用算法1进行Beta节点优先级计算

算法3. Rete-TC匹配

输入: Events

输出: fired rules

01: 　 while true do

02: 　　 if root->alphaNodes[event->eventtype]then 　　　　//事件类型对应的Alpha类型节点存在

03: 　　　 while alpha condition node not empty do

04: 　　　　 if Alpha node constant constraints test pass then // Alpha节点常量测试通过

05: 　　　　　 UpdateAtiveNodesByPriority(child beta node) //依据优先级将Alpha节点关联的子Beta节点添加到Beta节点激活队列

06: 　　　　 end if

07: 　　　 end while

08: 　　 end if

09: 　　 if head of Beta node activeated queue then //从Beta节点的激活队列取队首且不为空

10: 　　　 if Beta node’s alpha match not empty then //该Beta节点Alpha匹配不为空

11: 　　　　doRightActivatedHandle(am, Beta node) //进行右激活处理

12: 　　　　 UpdateAtiveNodesByPriority (child beta node) //依据优先级更新Beta节点激活队列

13: 　　　 elif Beta node’s partial match not empty then //该Beta节点部分匹配不为空

14: 　　　　doLeftActivatedHandle(am, Beta node) //进行左激活处理

15: 　　　　 UpdateAtiveNodesByPriority (child beta node) //依据优先级更新Beta节点激活队列

16: 　　　 end if

17: 　　 end if

18: 　 end while

3 系统框架

RTCPMS系统框架如图4所示. RTCPMS基于实时规则推理, 从CPS产生的大量事件中对关注的场景进行实时监控. RPCPMS主要由事件抽取器、实时数据库系统、实时监控推理引擎和决策与反馈控制模块组成.事件抽取器持续采集CPS传感器产生的数据并抽取事件存入安捷(Agilor)^[33]实时数据库系统. 实时监控推理引擎通过Agilor提供的发布/订阅接口来访问实时数据库中的事件. 实时监控推理引擎由规则库、事件库、规则解析模块和基于Rete-TC的实时推理模块组成. 规则库存放领域专家制定的监控规则; 事件库存放由安捷实时数据库系统发布的原子事件. 规则解析模块将规则库中的规则翻译成Rete-TC网络; 基于Rete-TC的实时推理模块从事件库中取出事件在Rete-TC网络上传递, 进行规则匹配, 匹配成功的规则输出到决策和反馈模块. 决策和反馈模块执行规则中预设的动作, 例如触发一个报警或给用户反馈.

4 实验评估 4.1 实验设置

CPS的场景千变万化, “事件风暴”^[34]是应用中存在的一类常见场景. 在这类场景中, 大量事件往往在一个较短的时间窗口内集中发生. 我们的模拟实验在此场景下开展. 通过对Rete-TC和Rete算法进行对比, 来验证本文所提Rete-TC算法的有效性. 本次实验的规则集共包含50条规则. 每个规则的事件模式数为1至8个, 事件类型120种, 原子事件数10万到30万. 每个事件具有2到4个属性, 每个属性的属性值符合均匀分布U[0, 1000], 各规则的截止期由应用需求决定, 一般设置后不再改变, 这里假设截止期服从均匀分布U[1, 10], 所有的原子事件模拟产生.

规则集的参数情况见表1.

我们使用成功率和匹配时间两个度量指标. 成功率的定义如下:

$ Success\;Ratio = {N_{\rm {success}}}/{N_{\rm {total}}} $

(2)

其中, N_success表示在规则截止期前触发的规则数, N_total表示所有触发的规则数.

匹配时间的定义如下:

$\begin{split} &Match\;Time = {\rm {Rete - TC}}\;\;{\text{或}}\\ &{\rm {Rete}}{\text{处理完指定输入规模下的所有事件所需时间}} \end{split} $

(3)

实验环境使用Intel(R) Core(TM) i7-8750H CPU @2.20 GHz, 16 GB内存和Windows 10.

4.2 成功率

我们对Rete-TC和Rete的成功率进行对比, 实验结果如图5所示. 图5展示了在输入的原子事件规模从1.0×10⁵到3.0×10⁵范围变化时, Rete-TC和Rete的成功率变化情况.

当原子事件数量小于1.0×10⁵, Rete-TC和Rete下触发的所有规则都满足截止期.当输入的原子事件规模大于1.0×10⁵, 激活队列中的Beta节点的数量增多, Rete-TC和Rete都会出现在规则截止期内规则对应的Beta节点未处理完情况, 从而导致Rete-TC和Rete触发的部分规则错失截止期. 当输入的原子事件规模超过3.0×10⁵时, 大量规则触发, 激活队列中的Beta节点数激增, Rete-TC和Rete在规则截止期内未能处理完相关Beta节点的情况激增, Rete-TC和Rete的成功率趋于零. 总体上, 随着原子事件数的增加, Rete-TC和Rete的成功率降低, 但是Rete-TC成功率均高于Rete.

Rete-TC依据式(1)对Beta节点的优先级进行计算, 充分考虑了各规则不同重要性, 其激活队列中的Beta节点按优先级排序, 这样时间约束强的规则得到及时处理, 从而使得各触发规则尽可能满足截止期约束. 相反, Rete激活队列中的Beta节点按激活时间排序, 未考虑Beta节点所在规则的截止期, 忽略了各规则不同重要性, 执行具有更晚截止期的规则可能会延迟具有较早截止期的规则, 这样可能会造成时间约束强的规则错失截止期, 不利于各触发规则满足截止期约束.

4.3 匹配时间

我们对Rete-TC和Rete的匹配时间进行对比, 实验结果如图6所示. 从图6得知, 在相同的原子事件规模输入下, Rete-TC相比Rete匹配时间略微增加, 也就是说, 本文在Rete-TC算法增加的Beta节点优先级调度特性对处理原子事件的效率的影响非常小.另外,由于Rete-TC算法本质上是改变了处理Beta节点的顺序, 不会对推理结果正确性产生影响. 每次实验也验证了Rete-TC和Rete的推理结果是完全一致的.

在相同的原子事件输入规模下, Rete-TC相比Rete匹配时间略增的原因讨论如下:

Rete-TC中激活的Beta节点优先级队列的数据结构采用红黑树, 支持在O(logN)时间复杂度内对优先级队列中元素进行排序, 其中N为优先级队列中Beta节点个数. 而Rete算法中对激活的Beta节点进行管理采用FIFO数据结构, 时间复杂度为O(1). 在本文的实验环境下Rete-TC中Beta节点优先级激活队列中Beta节点最大数量级约为10⁴, Beta节点优先级队列单次操作时间约为10^–6 s, Rete-TC算法用于维护Beta节点优先级队列的时间数量级约为10^–2 s, 所以Rete-TC相比Rete匹配时间略增.

4.4 截止期讨论

规则的截止期通常由应用需求确定, 确定后一般不再改变. 但也可能存在某些特殊场景, 例如由于监控外部环境或者监控需求发生特殊变化, 规则截止期需动态改变, 下面对此问题给出一种解决思路. 解决思路为: (1) 在Rete-TC网络建立阶段采用哈希表建立每个Beta节点关联的规则集合, Rete-TC匹配运行阶段直接使用即可. (2) 在Beta节点激活队列更新维护模块UpdateAtiveNodesByPriority中获取准备进入激活队列的Beta节点关联的规则集合中各规则最新截止期. (3) 在Beta节点激活队列更新维护模块UpdateAtiveNodesByPriority中对准备进入激活队列的Beta节点的优先级按照式(1)进行计算, 之后按UpdateAtiveNodesByPriority原有逻辑运行即可. 由于步骤(2)和(3)计算过程简单, 对Beta节点激活队列更新维护模块的运行时间开销影响小. 关于动态截止期的问题后续可进一步深入研究.

5 应用案例

随着CPS的快速发展, 建筑CPS逐渐兴起, 传统的建筑正在演变成集环境感知、实时分析、科学决策和精准执行功能于一体的智慧建筑. 以建筑CPS的监控为例, 如图7所示. 图7中建筑物理环境蕴含的隐性数据通过环境感知转换为显性数据, 进而能够在信息空间进行实时分析, 从而将显性数据转换为有价值的信息. 信息经过综合处理形成最优决策对物理空间实体进行精确调节. 图7中有3类场景需要监控, 分别是火灾场景、节能场景和环境舒适度调节场景. 其中, 火灾场景具有时间约束. 节能场景和环境舒适度调节场景只需尽可能快监控即可, 时间约束较为宽松, 错失截止期不会造成严重后果. 每个场景都由一系列原子事件所喻示. 例如, 房间内温度升高事件和烟雾产生事件可能喻示火灾发生. 房间内检测到无人事件且用电设备运行中事件喻示识别到潜在的节能场景, 需进行节能管理, 否则会造成能源浪费.

为了验证RTCPMS系统的有效性, 我们以北京市建筑设计研究院有限公司某大楼作为案例研究对象. 该大楼总共有13层, 每层有25个房间, 每个房间大约20个传感器. 其中的某个房间的传感器布局如图8所示.

以该大楼的3个监控场景需求为例. (1)关于火灾监控场景. 我们在位置A–J处部署一个温度传感器和一个烟雾传感器. 如果房间4个角落的传感器感知的数据同时超出阈值, 这表明该房间已发生严重火灾; 每个房间有两个防火门, 当火灾蔓延到防火门的时候, 防火门需要及时关闭. (2)关于环境健康参数方面的智能控制场景. 在K–M位置处, 我们部署环境健康相关的监控传感器来收集PM25、温度和湿度的数据. (3)关于节能管理场景. 在O–U的位置, 我们部署人员探测传感器, 当探测到无人时, RTCPMS自动关闭灯光、空调和空气净化器. (1)应最大化地满足时间约束, (2)(3)需尽可能快的处理.

根据上述监控需求, 我们制定规则, 如表2所示.

传感器产生的事件由采集程序进行采集并存储在实时数据库中. 大型建筑的火灾场景是一种典型的事件风暴场景, 当火灾发生时, 在短时间内, 用于火灾监控的各类传感器将上报大量事件, 如温度超标、烟雾浓度超标等.

应用案例的实验结果如图9所示. 图9中RTCPMS使用Rete-TC算法, RTCPMS-WITHOUT-TC使用Rete算法. 当原子事件数在1.0×10⁵至2.5×10⁵范围内, RTCPMS可以使得火灾报警规则在截止期内触发. RTCPMS-WITHOUT-TC只能确保原子事件数在1.0×10⁵至2.0×10⁵范围内, 火灾报警规则在截止期内触发. 当输入的原子事件数超过2.5×10⁵时, RTCPMS和RTCPMS-WITHOUT-TC都会发生规则错失截止期情况. 但RTCPMS处理火灾报警类规则的成功率始终高于RTCPMS-WITHOUT-TC (平均高12%). 从这个智慧建筑的应用案例可以看出, 本文建立的RTCPMS系统可以更有效的满足CPS监控的时间约束.

6 总结

CPS是将计算过程和物理过程集成的系统, 利用嵌入式计算机和网络对物理过程进行监测和控制, 并通过反馈环实现计算和物理过程的相互影响. CPS监控是从物理设备产生的事件中感知关注场景并作出响应的过程, 是CPS的核心功能之一. 在CPS监控中, 事件与动作之间的因果关系往往使用规则来描述. 采用规则系统相较于过程式逻辑具有若干优势, 为此, 学者们提出了基于规则的CPS监控方法, 然而CPS的实时性为CPS监控带来了时间约束问题. 目前已有的基于规则的CPS监控方法未考虑CPS监控场景的时间约束, 仅仅利用各种优化技术来缩短监控的响应时间. 为此, 本文基于实时规则引擎建立了一个CPS的实时监控系统RTCPMS. 该系统采用Rete网络表示监控规则.

RTCPMS将实时推理技术和CPS监控结合, 其核心是一个新的实时推理算法Rete-TC. Rete-TC算法引入了规则截止期, 通过基于优先级的Beta节点调度方法, 使得CPS监控的时间约束尽可能地被满足. 模拟实验与智慧建筑应用案例验证了RTCPMS系统的有效性, 且实验结果表明其核心算法Rete-TC的调度成功率优于传统的规则推理算法Rete.

CPS中, 由于传感器扰动, 可能会产生不精确的事件, 当前基于规则推理的CPS监控不适用于此场景. 下一步的研究中, 我们将基于Rete-TC, 研究实时的模糊推理技术, 来支持对不精确的事件进行实时监控, 从而提升CPS实时监控的鲁棒性. 另外, 当前基于规则的CPS监控方法需要事先由领域专家制定规则, 不适应于复杂的动态场景的自适应监控. 随着机器学习的广泛使用, 将机器学习与规则进行结合也是一个有潜力的研究方向.

致谢. 在此, 我们向对本文的工作给予帮助的中国科学院软件研究所人机交互技术与智能信息处理实验室的姚乃明博士、冷昶博士和马翠霞老师以及评阅此文的各位专家表示感谢.