基于改进Rete算法的复杂事件推理引擎的研究与实现

阴躲芬　龚华明

摘   要：复杂事件推理引擎是智慧家居中间件系统的核心部分，其运行效率的高低直接影响到中间件系统的性能和最终的服务效果。本文首先深入研究了Rete算法的原理，结合实际分析了智能家居中间件系统的特性，并在此基础上，提出了一种Rete算法的改进算法，该算法能明显缩短系统的运行时间、有效提高运行效率，给用户带来更完美的使用体验。

关键词：Rete算法  智慧家居  中间件  运行效率  实时性

中图分类号：TP311.13;TP18                     文献标识码：A                        文章编号：1674-098X（2019）06（c）-0088-03

Abstract：Complex event reasoning engine is the core part of smart home middleware system. Its running efficiency directly affects the performance of middleware system and the final service effect. Firstly， this paper deeply studies the principle of Rete algorithm， and analyses the characteristics of smart home middleware system. On this basis， an improved algorithm of Rete algorithm is proposed. This algorithm can significantly shorten the running time of the system， effectively improve the running efficiency， and bring users a more perfect use experience.

Key Words： Rete algorithm; Smart home; Middleware; Operating efficiency; Real-time

智慧家居中间件系统的主要功能是实时采集遍布于家庭各个角落的传感器数据，经过数据融合形成复杂事件以供上层应用服务使用，其核心就是复杂事件推理引擎。复杂事件推理引擎的运行效率直接影响到中间件系统的性能和最终的服务效果。本文将在传统Rete算法的基础上，提出一种改进算法，以提高系统的实时性和运行效率，降低系统的功耗，达到更完美的服务效果。

1  Rete算法原理

Rete算法作为一种基于前向规则的快速匹配算法，其匹配速度与规则的数目无关[1]。Rete 算法有8种节点类型，具体包括根节点（RootNode）、类型节点（TypeNode）、左输入适配节点、Alpha 节点、合并节点（JoinNode）、Eval 节点、非节点（NotNode）、终端节点（TerminalNode）[2]。其中根节点是一个虚拟节点，是Rete算法匹配网络的入口;类型节点对所有进入网络的事实（Facts）进行过滤，确保在Rete网络只有与“类型”值相同的事实才能在网络中流通;Alpha节点又叫单输入节点，用于事实属性的判定，仅当事实的属性与Alpha节点中的属性值匹配时才能继续在网络中流通;BetaNode 又叫双输入节点，包括合并节点和非节点，用于完成对象的对比即完成规则的检查;终端节点表示某条规则已经和所有的条件相匹配，当有多个规则存在时，允许有多个终端节点[2]。经典Rete算法模型如图1所示。

Rete 算法作为一种经典的模式匹配算法，在产生式系统中有着广泛的应用[4]，但是智能家居系统有着不同于其他产生式系统的特殊性，具体如下。

（1）实时性要求较高。智能家居系统要求能高效的处理原子事件，快速通过推理引擎得出复杂事件，以满足用户的美好体验，即使需要处理的事件很多也必须满足其实时性要求。所有在确保事件与规则匹配的准确性的前提下，执行时间越短越好。

（2）规则具有关联性。智能家居系统中大多数规则之间都有一定的关联性，并不是独立存在的，比如某些场景会具有共同的规则，如“空气质量差”和“火灾”都会匹配CO2浓度大于10%和O2浓度小于15%这两个规则。在智能家居系统中可以运用这些规则的关联性来提高改进算法的匹配效率。

（3）匹配逻辑有变化。传统的Rete算法的匹配逻辑只有 “等于”，而智能家居系统的匹配逻辑大部分不等于匹配（如烟雾浓度小于等于2），所以必须修改Rete算法中的匹配逻辑以适用于智能家居系统。

基于上述对于智能家居系统特性的分析和Rete算法的原理，特提出以下的改进思路。

（1）复用节点，优化推理网络。

如图1所示，传统Rete 算法推理网络的每一个规则都有独立的Alpha 网络和 Beta 网络。本文利用智能家居中规则的关联性对具有共同规则的节点进行合并，这样即可精简节点又能提高匹配速度。改进后的 Rete算法模型如图2所示。

（2）去除非节点。

经典Rete算法中的非节点主要用于处理产生式系统中某些事件之間存在一种“非”的情况。比如牛奶和餐桌的位置关系，只有牛奶在餐桌上和不在餐桌上这两种情况，那么在规则库里，某些产生式的推理条件可能就需要牛奶不在餐桌上这种“非”类型的关系。而在智能家居中间件系统中的复杂事件推理引擎中，数值关系都是可比较的，所以“非”可以使用其他的数值关系来代替，如氧气浓度<15%的非条件就是氧气浓度>=15%。所以在智能家居中间件系统的复杂事件推理引擎中可以去除非节点以提高简化推理网络，提高运行效率。

（3）并行化操作。經典的Rete算法中事件与规则的匹配一般都是串行化进行的，匹配效率不高，不适用于实时性要求高的应用场景。由于智能家居中间件系统的复杂事件推理引擎的特殊性，本文将复杂规则进行拆分，得到若干原子规则，与底层传来的原子事件直接进行匹配，最终各原子事件的匹配结果在终端节点进行汇总，完成规则的激活。这样既可以将原子事件与原子规则进行并行化匹配，又可以节约原来将原子事件形成复杂事件的步骤。并行化操作将大大提高匹配的效率，缩短推理时间，进一步满足智能家居系统对实时性的要求。并行化操作如图3所示。

2  改进Rete算法的测试

为了测试改进 Rete 算法的性能，本文将在Visual Studio 2017环境下进行传统Rete算法和改进Rete算法的性能对比，主要是通过固定规则个数的情况下改变事件个数来比较两种算法的执行效率。

实际运行的智慧家居系统的规则都是多输入单输出类型，其表达式如下：

其中，表示一条复杂规则中的原子规则之间的逻辑关系。本文从实际运行的智慧家居系统的规则库中随机抽取1000条作为测试系统的规则库，从事件库中随机抽取1000、1500、2000、2500、3000条事件作为事件库来进行两种算法的执行时间的对比。其结果如图4所示。

由图4可知，与经典的Rete算法相比，本文提出的Rete改进算法在执行时间方面优势明显，并且随着事件数量的增多，优势也越来越明显。显而易见，在实际的智慧家居系统的运行环境下，随着事件数量的急剧增大，改进的Rete算法的执行效率将会越来越高，更能满足智能家居系统的实时性要求，给用户带来更完美的体验。

3  结语

本文根据智能家居系统的实时性要求高和规则之间的关联性强以及不存在“非节点”的特性，提出了一种改进的Rete算法，并通过实验证明改进的Rete算法能有效的缩短推理时间，提高推理引擎的执行效率，更适用于智能家居系统。

参考文献

[1] Pallavi  M  S，  Vaisakh  P，  Reshna  N  P.  Implementation  of RETE algorithm  using  course  finder  system[C]//2016  International  Conference  on  Data  Mining  and  Advanced  Computing.2016（96）：100.

[2] Ronszcka A F， Banaszewski R F， Linhares R R， et al. Notification-Oriented and Rete Network Inference： A Comparative Study[A]//Systems， Man， and Cybernetics[C].2015.

[3] Jin-Yu Guo， Chipan Hwang， Mu-Song Chen. Using GPU to Shorten the Match Time of  Rule  Reasoning  Based  on  Rete  Algorithm[A]//International  Symposium  on Computer， Consumer and Control[C].2016.

[4] Kawakami T， Yoshihisa T， Yanagisawa Y， et al. A Rule Processing Scheme Using the Rete Algorithm in Grid Topology Networks[A]//IEEE， International Conference on Advanced Information NETWORKING and Applications. IEEE[C].2015.

[5] Ha Le-Thai，Adi Xhakoni，Georges Gielen. A column-and-row-parallel CMOS image sensor with thermal  and 1/fnoise suppression techniques. //ESSCIRC Conference 2016： 42nd European Solid-State Circuits Conference. 2016.