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

陰躲芬　龔華明

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

關鍵詞：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

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

1? Rete算法原理

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

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

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

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

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

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

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

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

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

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

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

2? 改進Rete算法的測試

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

實際運行的智慧家居系統(tǒng)的規(guī)則都是多輸入單輸出類型，其表達式如下：

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

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

3? 結(jié)語

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

參考文獻

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