基于改進(jìn)Rete算法的復(fù)雜事件推理引擎的研究與實(shí)現(xiàn)

陰躲芬　龔華明

摘? ?要：復(fù)雜事件推理引擎是智慧家居中間件系統(tǒng)的核心部分，其運(yùn)行效率的高低直接影響到中間件系統(tǒng)的性能和最終的服務(wù)效果。本文首先深入研究了Rete算法的原理，結(jié)合實(shí)際分析了智能家居中間件系統(tǒng)的特性，并在此基礎(chǔ)上，提出了一種Rete算法的改進(jìn)算法，該算法能明顯縮短系統(tǒng)的運(yùn)行時(shí)間、有效提高運(yùn)行效率，給用戶(hù)帶來(lái)更完美的使用體驗(yàn)。

關(guān)鍵詞：Rete算法? 智慧家居? 中間件? 運(yùn)行效率? 實(shí)時(shí)性

中圖分類(lèi)號(hào)：TP311.13;TP18? ? ? ? ? ? ? ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A? ? ? ? ? ? ? ? ? ? ? ? 文章編號(hào)：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

智慧家居中間件系統(tǒng)的主要功能是實(shí)時(shí)采集遍布于家庭各個(gè)角落的傳感器數(shù)據(jù)，經(jīng)過(guò)數(shù)據(jù)融合形成復(fù)雜事件以供上層應(yīng)用服務(wù)使用，其核心就是復(fù)雜事件推理引擎。復(fù)雜事件推理引擎的運(yùn)行效率直接影響到中間件系統(tǒng)的性能和最終的服務(wù)效果。本文將在傳統(tǒng)Rete算法的基礎(chǔ)上，提出一種改進(jìn)算法，以提高系統(tǒng)的實(shí)時(shí)性和運(yùn)行效率，降低系統(tǒng)的功耗，達(dá)到更完美的服務(wù)效果。

1? Rete算法原理

Rete算法作為一種基于前向規(guī)則的快速匹配算法，其匹配速度與規(guī)則的數(shù)目無(wú)關(guān)[1]。Rete 算法有8種節(jié)點(diǎn)類(lèi)型，具體包括根節(jié)點(diǎn)（RootNode）、類(lèi)型節(jié)點(diǎn)（TypeNode）、左輸入適配節(jié)點(diǎn)、Alpha 節(jié)點(diǎn)、合并節(jié)點(diǎn)（JoinNode）、Eval 節(jié)點(diǎn)、非節(jié)點(diǎn)（NotNode）、終端節(jié)點(diǎn)（TerminalNode）[2]。其中根節(jié)點(diǎn)是一個(gè)虛擬節(jié)點(diǎn)，是Rete算法匹配網(wǎng)絡(luò)的入口;類(lèi)型節(jié)點(diǎn)對(duì)所有進(jìn)入網(wǎng)絡(luò)的事實(shí)（Facts）進(jìn)行過(guò)濾，確保在Rete網(wǎng)絡(luò)只有與“類(lèi)型”值相同的事實(shí)才能在網(wǎng)絡(luò)中流通;Alpha節(jié)點(diǎn)又叫單輸入節(jié)點(diǎn)，用于事實(shí)屬性的判定，僅當(dāng)事實(shí)的屬性與Alpha節(jié)點(diǎn)中的屬性值匹配時(shí)才能繼續(xù)在網(wǎng)絡(luò)中流通;BetaNode 又叫雙輸入節(jié)點(diǎn)，包括合并節(jié)點(diǎn)和非節(jié)點(diǎn)，用于完成對(duì)象的對(duì)比即完成規(guī)則的檢查;終端節(jié)點(diǎn)表示某條規(guī)則已經(jīng)和所有的條件相匹配，當(dāng)有多個(gè)規(guī)則存在時(shí)，允許有多個(gè)終端節(jié)點(diǎn)[2]。經(jīng)典Rete算法模型如圖1所示。

Rete 算法作為一種經(jīng)典的模式匹配算法，在產(chǎn)生式系統(tǒng)中有著廣泛的應(yīng)用[4]，但是智能家居系統(tǒng)有著不同于其他產(chǎn)生式系統(tǒng)的特殊性，具體如下。

（1）實(shí)時(shí)性要求較高。智能家居系統(tǒng)要求能高效的處理原子事件，快速通過(guò)推理引擎得出復(fù)雜事件，以滿(mǎn)足用戶(hù)的美好體驗(yàn)，即使需要處理的事件很多也必須滿(mǎn)足其實(shí)時(shí)性要求。所有在確保事件與規(guī)則匹配的準(zhǔn)確性的前提下，執(zhí)行時(shí)間越短越好。

（2）規(guī)則具有關(guān)聯(lián)性。智能家居系統(tǒng)中大多數(shù)規(guī)則之間都有一定的關(guān)聯(lián)性，并不是獨(dú)立存在的，比如某些場(chǎng)景會(huì)具有共同的規(guī)則，如“空氣質(zhì)量差”和“火災(zāi)”都會(huì)匹配CO2濃度大于10%和O2濃度小于15%這兩個(gè)規(guī)則。在智能家居系統(tǒng)中可以運(yùn)用這些規(guī)則的關(guān)聯(lián)性來(lái)提高改進(jìn)算法的匹配效率。

（3）匹配邏輯有變化。傳統(tǒng)的Rete算法的匹配邏輯只有 “等于”，而智能家居系統(tǒng)的匹配邏輯大部分不等于匹配（如煙霧濃度小于等于2），所以必須修改Rete算法中的匹配邏輯以適用于智能家居系統(tǒng)。

基于上述對(duì)于智能家居系統(tǒng)特性的分析和Rete算法的原理，特提出以下的改進(jìn)思路。

（1）復(fù)用節(jié)點(diǎn)，優(yōu)化推理網(wǎng)絡(luò)。

如圖1所示，傳統(tǒng)Rete 算法推理網(wǎng)絡(luò)的每一個(gè)規(guī)則都有獨(dú)立的Alpha 網(wǎng)絡(luò)和 Beta 網(wǎng)絡(luò)。本文利用智能家居中規(guī)則的關(guān)聯(lián)性對(duì)具有共同規(guī)則的節(jié)點(diǎn)進(jìn)行合并，這樣即可精簡(jiǎn)節(jié)點(diǎn)又能提高匹配速度。改進(jìn)后的 Rete算法模型如圖2所示。

（2）去除非節(jié)點(diǎn)。

經(jīng)典Rete算法中的非節(jié)點(diǎn)主要用于處理產(chǎn)生式系統(tǒng)中某些事件之間存在一種“非”的情況。比如牛奶和餐桌的位置關(guān)系，只有牛奶在餐桌上和不在餐桌上這兩種情況，那么在規(guī)則庫(kù)里，某些產(chǎn)生式的推理?xiàng)l件可能就需要牛奶不在餐桌上這種“非”類(lèi)型的關(guān)系。而在智能家居中間件系統(tǒng)中的復(fù)雜事件推理引擎中，數(shù)值關(guān)系都是可比較的，所以“非”可以使用其他的數(shù)值關(guān)系來(lái)代替，如氧氣濃度<15%的非條件就是氧氣濃度>=15%。所以在智能家居中間件系統(tǒng)的復(fù)雜事件推理引擎中可以去除非節(jié)點(diǎn)以提高簡(jiǎn)化推理網(wǎng)絡(luò)，提高運(yùn)行效率。

（3）并行化操作。經(jīng)典的Rete算法中事件與規(guī)則的匹配一般都是串行化進(jìn)行的，匹配效率不高，不適用于實(shí)時(shí)性要求高的應(yīng)用場(chǎng)景。由于智能家居中間件系統(tǒng)的復(fù)雜事件推理引擎的特殊性，本文將復(fù)雜規(guī)則進(jìn)行拆分，得到若干原子規(guī)則，與底層傳來(lái)的原子事件直接進(jìn)行匹配，最終各原子事件的匹配結(jié)果在終端節(jié)點(diǎn)進(jìn)行匯總，完成規(guī)則的激活。這樣既可以將原子事件與原子規(guī)則進(jìn)行并行化匹配，又可以節(jié)約原來(lái)將原子事件形成復(fù)雜事件的步驟。并行化操作將大大提高匹配的效率，縮短推理時(shí)間，進(jìn)一步滿(mǎn)足智能家居系統(tǒng)對(duì)實(shí)時(shí)性的要求。并行化操作如圖3所示。

2? 改進(jìn)Rete算法的測(cè)試

為了測(cè)試改進(jìn) Rete 算法的性能，本文將在Visual Studio 2017環(huán)境下進(jìn)行傳統(tǒng)Rete算法和改進(jìn)Rete算法的性能對(duì)比，主要是通過(guò)固定規(guī)則個(gè)數(shù)的情況下改變事件個(gè)數(shù)來(lái)比較兩種算法的執(zhí)行效率。

實(shí)際運(yùn)行的智慧家居系統(tǒng)的規(guī)則都是多輸入單輸出類(lèi)型，其表達(dá)式如下：

其中，表示一條復(fù)雜規(guī)則中的原子規(guī)則之間的邏輯關(guān)系。本文從實(shí)際運(yùn)行的智慧家居系統(tǒng)的規(guī)則庫(kù)中隨機(jī)抽取1000條作為測(cè)試系統(tǒng)的規(guī)則庫(kù)，從事件庫(kù)中隨機(jī)抽取1000、1500、2000、2500、3000條事件作為事件庫(kù)來(lái)進(jìn)行兩種算法的執(zhí)行時(shí)間的對(duì)比。其結(jié)果如圖4所示。

由圖4可知，與經(jīng)典的Rete算法相比，本文提出的Rete改進(jìn)算法在執(zhí)行時(shí)間方面優(yōu)勢(shì)明顯，并且隨著事件數(shù)量的增多，優(yōu)勢(shì)也越來(lái)越明顯。顯而易見(jiàn)，在實(shí)際的智慧家居系統(tǒng)的運(yùn)行環(huán)境下，隨著事件數(shù)量的急劇增大，改進(jìn)的Rete算法的執(zhí)行效率將會(huì)越來(lái)越高，更能滿(mǎn)足智能家居系統(tǒng)的實(shí)時(shí)性要求，給用戶(hù)帶來(lái)更完美的體驗(yàn)。

3? 結(jié)語(yǔ)

本文根據(jù)智能家居系統(tǒng)的實(shí)時(shí)性要求高和規(guī)則之間的關(guān)聯(lián)性強(qiáng)以及不存在“非節(jié)點(diǎn)”的特性，提出了一種改進(jìn)的Rete算法，并通過(guò)實(shí)驗(yàn)證明改進(jìn)的Rete算法能有效的縮短推理時(shí)間，提高推理引擎的執(zhí)行效率，更適用于智能家居系統(tǒng)。

參考文獻(xiàn)

[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.