基于規(guī)則推理的實時信息物理監(jiān)控系統(tǒng)①

彭 程,喬 穎,王宏安

1(中國科學院軟件研究所,北京 100190)

2(中國科學院大學,北京 100049)

信息物理系統(tǒng)(Cyber-Physical Systems,CPS)是將計算過程和物理過程集成的系統(tǒng),利用嵌入式計算機和網(wǎng)絡對物理過程進行監(jiān)測和控制,并通過反饋環(huán)實現(xiàn)計算和物理過程的相互影響[1].CPS概念自提出以來,迅速在眾多重要環(huán)節(jié)中承擔關鍵任務,廣泛應用在智慧建筑[2]、生產(chǎn)制造[3]、交通運輸[4]、醫(yī)療健康[5,6]和城市建設[7]等領域.CPS本質就是構建一套賽博(Cyber)空間與物理(Physical)空間之間基于數(shù)據(jù)自動流動的狀態(tài)感知、實時分析、科學決策、精準執(zhí)行的閉環(huán)賦能體系,解決生產(chǎn)制造、應用服務過程中的復雜性和不確定性問題,提高資源配置效率,實現(xiàn)資源優(yōu)化[8].CPS監(jiān)控是從物理設備產(chǎn)生的事件中感知關注場景并作出響應的過程,是CPS的核心功能之一.

實時性是CPS的特點之一[9],為CPS監(jiān)控帶來了時間約束問題,即從與監(jiān)控關注場景相關的所有原子事件到達系統(tǒng)開始到觸發(fā)關注場景關聯(lián)的動作之間的時間間隔(也稱為響應時間)不應超過其上界(這個上界稱為截止期),否則將造成嚴重的后果.例如,在智慧建筑CPS中,存在諸多監(jiān)控場景,例如,節(jié)能場景、環(huán)境舒適度調節(jié)場景和火災監(jiān)控場景等.其中火災監(jiān)控場景具有時間約束要求,國家標準GB4717-2005 規(guī)定查詢和處理數(shù)據(jù)等火災報警操作不超過10 s.這個10 s就是一個從事件發(fā)生到觸發(fā)火災報警動作的截止期,錯失截止期可能會造成火災事故,從而造成生命和財產(chǎn)損失.這樣的CPS監(jiān)控場景還有很多,比如高速列車故障控制系統(tǒng)、電網(wǎng)故障診斷系統(tǒng)等.

在這樣的CPS監(jiān)控中,事件與動作之間的因果關系往往使用規(guī)則來描述.針對監(jiān)測到的事件,判斷某條規(guī)則所描述的事件模式是否滿足,從而得出動作的過程,稱為針對此條規(guī)則的推理過程,上述對監(jiān)控事件作出響應的過程,可視為一系列規(guī)則推理過程的集合[10].采用規(guī)則系統(tǒng)相較于過程式邏輯具有若干優(yōu)勢,如規(guī)則靈活性更強(當業(yè)務需求變化時,更新規(guī)則庫中規(guī)則即可,應用無需重新編譯部署)、更直觀易理解(例如智慧建筑中監(jiān)控服務“當房間溫度低于18度時,則打開空調制熱”)、更低的復雜度(規(guī)則具有一致性表示)等.

為此,學者們對基于規(guī)則的CPS監(jiān)控進行了探索.Sun 等人[11-13]使用基于Rete[14]算法的規(guī)則引擎對大規(guī)模智能建筑產(chǎn)生的事件進行高效處理.Klein 等人[15]提出了一種結合ECA (Event-Condition-Action)[16]和CEP(Complex Event Processing)[17]的基于規(guī)則的方法來對CPS 中產(chǎn)生的事件進行監(jiān)控.然而,上述基于規(guī)則的CPS監(jiān)控研究工作未考慮CPS監(jiān)控的時間約束.關于時間約束問題,學者們也提出了一些方法,如:迭代推理[18](如Anytime算法)、多重方法推理[19](如Designto-Time算法)和漸進式推理[20,21](如GREAT算法和PRIMES算法).這些方法為整個推理過程定義了截止期約束,通過對推理運行時間與推理結果質量進行折中來滿足這個截止期約束.李想等[22]介紹了一種面向物聯(lián)網(wǎng)的實時復雜事件處理引擎,該引擎采用一種啟發(fā)式復雜事件處理算法來優(yōu)先處理能夠產(chǎn)生結果的任務,縮短了復雜事件處理的響應時間,同時介紹了一種復雜事件處理程序的最壞響應事件估算算法,但忽略了各監(jiān)控任務不同的緊迫度.Liu 等人[23]使用復雜事件處理技術來對智能電網(wǎng)中產(chǎn)生的事件進行處理.然而,上述工作主要是縮短了CPS監(jiān)控的響應時間,但不能使CPS監(jiān)控盡可能地滿足其時間約束.

此外,學者們還通過改進典型的規(guī)則匹配Rete算法來縮短匹配時間以及進行一些功能擴展如模糊推理、事件處理和并行化等方面,但未考慮Rete算法在推理過程中的時間約束問題.William Van Woensel 等人[24]提出了一種改進的Rete算法,支持在內存受限環(huán)境下進行規(guī)則推理.文獻[25,26]對Rete的語法結構進行擴展,即根據(jù)規(guī)則的and、or 等邏輯操作將規(guī)則構建成一個抽象語法樹,并在語法樹的基礎上建立Rete網(wǎng)絡,邏輯操作符本身作為一個Rete節(jié)點參與事實匹配.這種做法減少了規(guī)則拆分開銷,給規(guī)則匹配帶來了便利.文獻[27]對規(guī)則中的條件進行了重排序.規(guī)則中條件順序是指規(guī)則條件中的各個約束的排列順序,它決定了條件的執(zhí)行順序,是決定規(guī)則匹配效率的關鍵因素.Xiao 等人[28]將Beta內存分成若干單元,每個單元分配一個id,對事實用哈希函數(shù)計算索引,索引號即為某個單元的位置,通過索引快速找到相應單元進行匹配,如果匹配不成功,則將該對象組成一個新的單元加入相關內存.孫新等人[29]提出了一種基于共享度模型的改進Rete算法,可以提升Rete網(wǎng)絡的推理速度.Ju等人[30]研究將 Rete算法在Apache Spark上進行并行化.汪成亮等人[31]提出了智能環(huán)境下分布式Rete算法,將推理網(wǎng)絡中的計算任務分布式地部署到最靠近參數(shù)采集的傳感器節(jié)點中,讓這些傳感器充分參與到推理計算工作中.

為此,本文基于實時規(guī)則引擎建立了一個CPS的實時監(jiān)控系統(tǒng)RTCPMS (Real-Time Cyber-Physical Monitoring System),該系統(tǒng)采用Rete網(wǎng)絡表示監(jiān)控規(guī)則.RTCPMS 將實時推理技術和CPS監(jiān)控結合,其核心是一個新的實時推理算法Rete-TC.Rete-TC算法引入了規(guī)則截止期,通過基于優(yōu)先級的Beta節(jié)點調度方法,使得CPS監(jiān)控的時間約束盡可能地被滿足.模擬實驗與智慧建筑應用案例驗證了RTCPMS系統(tǒng)的有效性,且實驗結果表明其核心算法Rete-TC的調度成功率優(yōu)于傳統(tǒng)的規(guī)則推理算法Rete.

本文接下來的組織結構如下:第1節(jié)介紹了研究基礎;第2節(jié)介紹了Rete-TC實時規(guī)則推理算法;第3節(jié)介紹了系統(tǒng)框架;第4節(jié)進行了模擬實驗評估;第5節(jié)進行應用案例研究;第6節(jié)進行總結了及下一步工作.

1 研究基礎

1.1 術語和定義

在CPS中,原子事件是不可再分的,只存在發(fā)生和不發(fā)生兩種狀態(tài),其來源包括傳感器或其他感知設備.關注場景是按照定義在規(guī)則中的事件條件從原子事件中檢測得到.

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

原子事件由屬性類型名和屬性組成,可表示為(EventTypeName Attributes),其中 EventTypeName表示事件的類型,Attributes = ((Name1Value1),···,(NamenValuen))表示事件的屬性,屬性是有序的.每個屬性由屬性名和屬性值構成.例如,一個事件類型為“ClassA”的原子事件可以表示為“(ClassA (val1365)(val2928)(val3153)(val4497))”.

定義2.約束(constraint)

約束可以表示為(Param1op Param2).它由Param1,op和Param2組成.這里Param1是事件屬性名,為變量;op為常見的邏輯操作符,例如>,<,==,>=,<=;Param2可以是一個常量或一個變量(另一個事件的屬性名).當約束為“變量-op-常量”時,它用于確定一個事件的屬性和常量之間的關系,稱為常量約束,例如,(Person.age >15).當約束為“變量-op-變量”時,它用于確定事件屬性關系,稱為變量約束,例如,(C1.attr >C2.attr).

定義3.事件條件(event condition)

事件條件可表示為:

(＄EventTypeBindName:EventTypeName(Constraint1OP Constraint2OP ···Constraintn))

其中＄為變量綁定符，EventTypeBindName為事件對象綁定的變量名，用于支持將多個同類型事件對象綁定到不同的＄EventTypeBindName上 (因為同一事件對象在一條規(guī)則中可能出現(xiàn)多次).EventTypeName含義參見定義1.Constraint參見定義2.OP指“and” (也表示為“&&”)，“or”(也表示為“||”)連接操作符.事件條件有時也稱為事件模式.

定義4.實時規(guī)則(real-time rule)

實時規(guī)則由用戶定義,可表示監(jiān)控場景.規(guī)則由規(guī)則名、規(guī)則截止期、事件條件集和動作集組成.其中事件條件集也稱作左手部分(Left-Hand Side,LHS),動作集也被稱作右手部分(Right-Hand Side,RHS).基于Drools[32]規(guī)則語言,我們定義的實時規(guī)則格式如下:

“deadlinen”表示規(guī)則的截止期為n秒,截止期大小一般由應用確定.如果n取0,則表示規(guī)則無時間約束.

1.2 Rete 推理算法

1.2.1 Rete 基本概念

Rete是一個經(jīng)典且高效的規(guī)則匹配算法,已被廣泛應用到許多主流的規(guī)則推理引擎中.Rete算法作為一種前向鏈推理算法,其核心思想是采用增量匹配的概念,根據(jù)內容動態(tài)構造匹配樹,以達到顯著降低計算量的效果.目前主流規(guī)則推理引擎(例如Drools)使用Rete算法.Rete算法將規(guī)則轉換成Rete網(wǎng)絡,表示各種規(guī)則條件間的數(shù)據(jù)依賴.當事實或事件對象進入系統(tǒng)后,它將在Rete網(wǎng)絡上匹配傳播,直到抵達規(guī)則的終止節(jié)點,即完成一條規(guī)則的匹配,進而觸發(fā)該規(guī)則預定義動作.Rete網(wǎng)絡包括兩部分:Alpha網(wǎng)絡和Beta網(wǎng)絡.Alpha網(wǎng)絡包括4類節(jié)點:根節(jié)點(Alpha root node)、類型節(jié)點(Object type node)、條件節(jié)點(Alpha node)和Alpha內存節(jié)點(Alpha memory node).根節(jié)點是所有事實或事件對象進入Rete網(wǎng)絡的入口,是一個虛節(jié)點,無實際意義.類型節(jié)點是根節(jié)點的直接子節(jié)點,保存了規(guī)則中事實或事件對象對應的類型.如果某對象類型的模式有條件約束,則該約束會進入Alpha網(wǎng)絡形成條件節(jié)點,完成事實或事件中屬性的常量約束測試(例如,檢查屬性 Person.age >15),這樣可以過濾掉大部分無意義的事實或事件對象.Alpha內存(Alpha memory)節(jié)點是Alpha網(wǎng)絡的最后一層節(jié)點,Alpha內存存儲所有通過常量約束測試的事實對象,也稱為Alpha匹配(Alpha Match,AM).Beta網(wǎng)絡包含3類節(jié)點:連接節(jié)點(Beta node)和終止節(jié)點(Terminal node)和Beta網(wǎng)絡根節(jié)點(Beta root node).連接節(jié)點的輸入來自上一級的Beta節(jié)點和Alpha內存節(jié)點,負責執(zhí)行變量約束測試(例如,C1.attr >C2.attr),即判斷兩個事實或事件對象在某一屬性值上的關系,通過該測試的事實或事件數(shù)據(jù)被稱為部分匹配(Partial Match,PM),即成功匹配了規(guī)則的一部分約束但還沒完全匹配所有約束的部分事實或事件數(shù)據(jù),每個Beta節(jié)點都保存著通過上一級Beta節(jié)點變量約束測試的PM數(shù)據(jù),并使用這些數(shù)據(jù)完成本節(jié)點的變量約束測試,之后將匹配結果傳遞給下一級Beta節(jié)點,直至抵達規(guī)則終止節(jié)點;規(guī)則終止節(jié)點是出度為0的節(jié)點,是Rete網(wǎng)絡的葉子節(jié)點,也是一條規(guī)則的最后一個節(jié)點,當事實或事件數(shù)據(jù)到達該節(jié)點時,表明該條規(guī)則被觸發(fā).Beta網(wǎng)絡根節(jié)點為一個虛節(jié)點,不具有實際意義.1.2.2 Rete網(wǎng)絡構建流程

假設有規(guī)則集Ri(1 ≤i≤N),Rete網(wǎng)絡構建流程如下:

(1)建立Rete網(wǎng)絡的根節(jié)點Alpha root node和Beta網(wǎng)絡根節(jié)點Beta root node;

(2)處理規(guī)則Ri;

(3)處理Ri中的事件條件Cj(1 ≤j≤n),假如Cj不存在于Alpha網(wǎng)絡中,則將Cj作為Alpha(j)節(jié)點插入Alpha網(wǎng)絡;

(4)對Cj中的變量約束,新建Beta節(jié)點,該Beta節(jié)點的左輸入是上一級的Beta節(jié)點(如果是第一個Beta節(jié)點,左輸入為Beta root node節(jié)點),右輸入是當前Cj的事件對象的Alpha(j);

(5)重復(3)～(4)處理完所有事件條件;

(6)重復(2)～(5)處理完所有規(guī)則.

由于本文所提Rete-TC (Timing Constraints)算法重點改進Rete算法的Beta網(wǎng)絡部分,下面將舉例對Rete 中的Beta網(wǎng)絡部分進行重點介紹,Alpha網(wǎng)絡不再詳細贅述.

假設有如下規(guī)則:

根據(jù)上述規(guī)則建立的Rete網(wǎng)絡如圖1所示.圖1中左半部分β1～β6為Beta網(wǎng)絡中的Beta節(jié)點,也稱作連接節(jié)點.連接節(jié)點的輸入來自上一級的Beta節(jié)點(β1節(jié)點為Beta網(wǎng)絡中第一個節(jié)點,其左輸入為Beta根節(jié)點)和Alpha內存節(jié)點,負責執(zhí)行變量約束測試.例如,β2節(jié)點的輸入來自上一級的Beta節(jié)點β1和Alpha內存節(jié)點AM2,負責執(zhí)行變量約束測試“C2:attr2 == $1.attr2”.β3節(jié)點的左輸入來自于β2和Alpha內存節(jié)點AM3,負責執(zhí)行變量約束測試“C3:attr1 == $2.attr1”和“C3:attr2 == $2.attr2”.其中β1和β2節(jié)點為R1、R2和R3規(guī)則共享,β4節(jié)點為規(guī)則R2和R3共享.

定義5.規(guī)則路徑

從Beta網(wǎng)絡根節(jié)點到某個規(guī)則終止節(jié)點之間相連的Beta節(jié)點構成的路徑.

定義6.規(guī)則路徑節(jié)點集RP

規(guī)則路徑節(jié)點集為某條規(guī)則的規(guī)則路徑上所有Beta節(jié)點的集合.例如,圖1中的規(guī)則R1的路徑節(jié)點集RPR1= {β1,β2,β3}.

圖1 Rete網(wǎng)絡示例

1.2.3 Rete算法的匹配過程

Rete 網(wǎng)建立后,事件對象從Alpha 根節(jié)點進入網(wǎng)絡,如果相關的Alpha 常量約束測試通過,則激活后繼相關Beta節(jié)點.Beta網(wǎng)絡中的激活有兩種方式,如果Beta節(jié)點接收到左輸入Beta節(jié)點傳遞來的部分匹配(Partial Match,PM),稱為左激活.左激活發(fā)生時,Beta節(jié)點會遍歷其相關的Alpha內存中的Alpha匹配(AM)和新到來的PM進行變量約束測試;如果Beta節(jié)點接受右輸入Alpha網(wǎng)絡傳遞過來的AM,稱為右激活.此時,Beta節(jié)點會遍歷該節(jié)點的PM和輸入的AM進行變量約束測試.左激活和右激活中的變量約束測試如果通過則產(chǎn)生新的部分匹配(PM)向后繼Beta節(jié)點傳遞并激活相關Beta節(jié)點.

激活的Beta節(jié)點存放在Beta節(jié)點激活隊列中,如圖2所示.激活的Beta節(jié)點按激活時間依次存入Beta激活隊列的隊尾,后續(xù)依次從Beta激活隊列的隊首取出Beta節(jié)點進行處理,即按照FCFS (First Come First Service)的方式處理.

1.2.4 Rete算法的局限性

Rete網(wǎng)絡中Beta節(jié)點的處理是按Beta節(jié)點激活時間順序處理,即FCFS (First Come First Service)的方式,這會造成時間約束強的監(jiān)控場景中的Beta節(jié)點無法得到及時處理,從而無法盡可能滿足監(jiān)控場景的時間約束.例如,假設規(guī)則1的規(guī)則路徑節(jié)點集RP1 ={β1,β2,β3,β6},規(guī)則2的規(guī)則路徑節(jié)點集RP2 = {β1,β2,β4,β7}.規(guī)則1代表的是建筑節(jié)能監(jiān)控場景(例如,當房間無人時,關閉燈光和空調).規(guī)則2代表的是建筑火災監(jiān)控場景(例如,當監(jiān)控到房間發(fā)生火災時,立刻進行報警等).顯然規(guī)則2 比規(guī)則1 具有更強的時間約束.假設β4代表火災監(jiān)控場景中的某個條件,此時發(fā)生的事件使得β4 被激活,但β4 會被放置在激活隊列的隊尾,而Rete算法按照激活隊列的中Beta節(jié)點激活順序依次處理.這可能會造成時間約束強的監(jiān)控場景(例如,火災監(jiān)控場景)得不到及時處理.

圖2 Rete 網(wǎng)中Beta節(jié)點處理順序示例

1.3 基于規(guī)則的監(jiān)控場景表示

假設當前存在這樣一個建筑火災監(jiān)控場景:當房間4個角落的煙霧傳感器和溫度傳感器值同時超過閾值時,則表示房間發(fā)生嚴重的火災.該火災監(jiān)控場景必須在3 s 內監(jiān)測到并觸發(fā)火災報警相關的行動,否則將造成嚴重的損失.上述建筑火災監(jiān)控場景可用規(guī)則表示如下:

2 Rete-TC實時規(guī)則推理算法

當前可用規(guī)則表示監(jiān)控場景,在規(guī)則推理中常使用Rete算法,但Rete算法未考慮規(guī)則的截止期,執(zhí)行具有更晚截止期的規(guī)則可能會延遲具有較早截止期的規(guī)則,這樣可能會造成時間約束強的規(guī)則錯失截止期,從而無法盡可能滿足監(jiān)控場景的時間約束.

為了克服上述Rete算法的缺點,基于Rete,我們提出了一種適用于實時監(jiān)控的實時推理算法Rete-TC(Timing Constraints).Rete-TC算法引入了規(guī)則截止期,通過基于優(yōu)先級的Beta節(jié)點調度方法,使得CPS監(jiān)控盡可能滿足時間約束.

2.1 Beta節(jié)點調度

規(guī)則的截止期代表了該條規(guī)則的緊迫度.所以,具有更早截止期的規(guī)則應優(yōu)先處理.

建立了Beta節(jié)點的優(yōu)先級計算方法:

其中,r為一條規(guī)則,r∈Rβ,Rβ是規(guī)則的路徑節(jié)點集中包含β的規(guī)則集合.例如,圖1中的規(guī)則R1 路徑節(jié)點集RPR1= {β1,β2,β3}.deadline(r)表示規(guī)則r的截止期;P(β)越小,β節(jié)點的優(yōu)先級越大.Beta節(jié)點處理按照Beta節(jié)點的優(yōu)先級從大到小的順序進行,從而使得具有更早截止期的規(guī)則將被優(yōu)先觸發(fā).另外,當P(β)為0時,β節(jié)點按照激活時間順序放入激活隊列的末尾,表示該Beta節(jié)點對應的規(guī)則無時間約束要求.

2.2 Rete-TC算法描述

Rete-TC算法有3部分組成,分別是算法1 Beta節(jié)點優(yōu)先級計算、算法2 Rete-TC網(wǎng)絡構造算法、算法3 Rete-TC匹配,各算法偽碼如下.算法1 按照公式(1)計算每條規(guī)則產(chǎn)生的Beta節(jié)點的優(yōu)先級,優(yōu)先級作為每個β節(jié)點的屬性.算法1在算法2 Rete-TC網(wǎng)絡構造算法中調用.

按照式(1)Beta節(jié)點的優(yōu)先級計算方法,圖3中的β4節(jié)點將依據(jù)優(yōu)先級進入到激活隊列中的相應位置(具體位置可由β4節(jié)點的優(yōu)先級與激活隊列中已有的Beta節(jié)點的優(yōu)先級比較決定,最終激活隊列中Beta節(jié)點優(yōu)先級從隊首到隊尾優(yōu)先級遞減),從而β4代表的具有強時間約束要求的火災監(jiān)測場景可以獲得優(yōu)先處理.

圖3 Rete-TC 網(wǎng)中Beta節(jié)點處理順序示例

算法2.Rete-TC網(wǎng)絡構造算法完成Rete-TC網(wǎng)絡構造,與Rete網(wǎng)絡構造區(qū)別是增加Beta節(jié)點優(yōu)先級計算(在Rete網(wǎng)絡構造的結尾處即第17行通過調用算法1 實現(xiàn)).由此可見,β節(jié)點優(yōu)先級在Rete-TC網(wǎng)絡構造完成時已確定.算法2 中第4～6行完成Alpha網(wǎng)絡的構造.第7～14行完成Beta網(wǎng)絡的構造.算法3 Rete-TC匹配完成規(guī)則推理,在Rete匹配算法的基礎上主要增加了第5、12和15行Beta節(jié)點激活隊列更新維護模塊UpdateAtiveNodesByPriority,其余保持不變.UpdateAtiveNodesByPriority模塊內部主要采用紅黑樹數(shù)據(jù)結構,支持在O(logN)時間復雜度內對優(yōu)先級隊列中元素進行排序(N為優(yōu)先級隊列中Beta節(jié)點個數(shù)),相較于Rete算法中對激活的Beta節(jié)點管理采用的FIFO數(shù)據(jù)結構(時間復雜度為O(1)),匹配時間雖略有增加,但影響不大,我們在實驗評估環(huán)節(jié)進行了驗證分析.算法3 中第2～8行完成Alpha節(jié)點處理,第9～17行完成Beta節(jié)點處理.

Rete-TC算法過程為先調用算法2 Rete-TC網(wǎng)絡構造,之后調用算法3進行Rete-TC匹配.

算法1.Beta節(jié)點優(yōu)先級計算輸入: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網(wǎng)絡構造輸入:Rule Set輸出:Rete-TC網(wǎng)絡01: Create alpha root node and beta root node 02: for i = 1;i ≤ RuleNum;i++do 03: for j = 1; j 2 then 12: 將Beta(j)節(jié)點插入Beta網(wǎng)絡中,其父節(jié)點為Beta(j-1)和Alpha(j):13: end if 14: end if 15: end for 16: end for 17:調用算法1進行Beta節(jié)點優(yōu)先級計算

算法3.Rete-TC匹配輸入:Events輸出:fired rules 01: while true do 02: if root->alphaNodes[event->eventtype] then //事件類型對應的Alpha類型節(jié)點存在03: while alpha condition node not empty do 04: if Alpha node constant constraints test pass then //Alpha節(jié)點常量測試通過05: UpdateAtiveNodesByPriority(child beta node)//依據(jù)優(yōu)先級將Alpha節(jié)點關聯(lián)的子Beta節(jié)點添加到Beta節(jié)點激活隊列06: end if 07: end while 08: end if 09: if head of Beta node activeated queue then //從Beta節(jié)點的激活隊列取隊首且不為空10: if Beta node’s alpha match not empty then //該Beta節(jié)點Alpha匹配不為空11: doRightActivatedHandle(am,Beta node)//進行右激活處理12: UpdateAtiveNodesByPriority (child beta node)//依據(jù)優(yōu)先級更新Beta節(jié)點激活隊列13: elif Beta node’s partial match not empty then //該Beta節(jié)點部分匹配不為空14: doLeftActivatedHandle(am,Beta node)//進行左激活處理15: UpdateAtiveNodesByPriority (child beta node)//依據(jù)優(yōu)先級更新Beta節(jié)點激活隊列16: end if 17: end if 18: end while

3 系統(tǒng)框架

RTCPMS系統(tǒng)框架如圖4所示.RTCPMS基于實時規(guī)則推理,從CPS產(chǎn)生的大量事件中對關注的場景進行實時監(jiān)控.RPCPMS主要由事件抽取器、實時數(shù)據(jù)庫系統(tǒng)、實時監(jiān)控推理引擎和決策與反饋控制模塊組成.事件抽取器持續(xù)采集CPS傳感器產(chǎn)生的數(shù)據(jù)并抽取事件存入安捷(Agilor)[33]實時數(shù)據(jù)庫系統(tǒng).實時監(jiān)控推理引擎通過Agilor提供的發(fā)布/訂閱接口來訪問實時數(shù)據(jù)庫中的事件.實時監(jiān)控推理引擎由規(guī)則庫、事件庫、規(guī)則解析模塊和基于Rete-TC的實時推理模塊組成.規(guī)則庫存放領域專家制定的監(jiān)控規(guī)則;事件庫存放由安捷實時數(shù)據(jù)庫系統(tǒng)發(fā)布的原子事件.規(guī)則解析模塊將規(guī)則庫中的規(guī)則翻譯成Rete-TC網(wǎng)絡;基于Rete-TC的實時推理模塊從事件庫中取出事件在Rete-TC網(wǎng)絡上傳遞,進行規(guī)則匹配,匹配成功的規(guī)則輸出到?jīng)Q策和反饋模塊.決策和反饋模塊執(zhí)行規(guī)則中預設的動作,例如觸發(fā)一個報警或給用戶反饋.

圖4 RTCPMS的架構

4 實驗評估

4.1 實驗設置

CPS的場景千變萬化,“事件風暴”[34]是應用中存在的一類常見場景.在這類場景中,大量事件往往在一個較短的時間窗口內集中發(fā)生.我們的模擬實驗在此場景下開展.通過對Rete-TC和Rete算法進行對比,來驗證本文所提Rete-TC算法的有效性.本次實驗的規(guī)則集共包含50條規(guī)則.每個規(guī)則的事件模式數(shù)為1至8個,事件類型120種,原子事件數(shù)10萬到30萬.每個事件具有2到4個屬性,每個屬性的屬性值符合均勻分布U[0,1000],各規(guī)則的截止期由應用需求決定,一般設置后不再改變,這里假設截止期服從均勻分布U[1,10],所有的原子事件模擬產(chǎn)生.

規(guī)則集的參數(shù)情況見表1.

表1 規(guī)則集的參數(shù)

我們使用成功率和匹配時間兩個度量指標.成功率的定義如下:

其中,Nsuccess表示在規(guī)則截止期前觸發(fā)的規(guī)則數(shù),Ntotal表示所有觸發(fā)的規(guī)則數(shù).

匹配時間的定義如下:

實驗環(huán)境使用Intel(R)Core(TM)i7-8750H CPU@2.20 GHz,16 GB內存和Windows 10.

4.2 成功率

我們對Rete-TC和Rete的成功率進行對比,實驗結果如圖5所示.圖5展示了在輸入的原子事件規(guī)模從1.0×105到3.0×105范圍變化時,Rete-TC和Rete的成功率變化情況.

圖5 Rete-TC和Rete的成功率

當原子事件數(shù)量小于1.0×105,Rete-TC和Rete 下觸發(fā)的所有規(guī)則都滿足截止期.當輸入的原子事件規(guī)模大于1.0×105,激活隊列中的Beta節(jié)點的數(shù)量增多,Rete-TC和Rete 都會出現(xiàn)在規(guī)則截止期內規(guī)則對應的Beta節(jié)點未處理完情況,從而導致Rete-TC和Rete 觸發(fā)的部分規(guī)則錯失截止期.當輸入的原子事件規(guī)模超過3.0×105時,大量規(guī)則觸發(fā),激活隊列中的Beta節(jié)點數(shù)激增,Rete-TC和Rete在規(guī)則截止期內未能處理完相關Beta節(jié)點的情況激增,Rete-TC和Rete的成功率趨于零.總體上,隨著原子事件數(shù)的增加,Rete-TC和Rete的成功率降低,但是Rete-TC 成功率均高于Rete.

Rete-TC 依據(jù)式(1)對Beta節(jié)點的優(yōu)先級進行計算,充分考慮了各規(guī)則不同重要性,其激活隊列中的Beta節(jié)點按優(yōu)先級排序,這樣時間約束強的規(guī)則得到及時處理,從而使得各觸發(fā)規(guī)則盡可能滿足截止期約束.相反,Rete激活隊列中的Beta節(jié)點按激活時間排序,未考慮Beta節(jié)點所在規(guī)則的截止期,忽略了各規(guī)則不同重要性,執(zhí)行具有更晚截止期的規(guī)則可能會延遲具有較早截止期的規(guī)則,這樣可能會造成時間約束強的規(guī)則錯失截止期,不利于各觸發(fā)規(guī)則滿足截止期約束.

4.3 匹配時間

我們對Rete-TC和Rete的匹配時間進行對比,實驗結果如圖6所示.從圖6得知,在相同的原子事件規(guī)模輸入下,Rete-TC相比Rete匹配時間略微增加,也就是說,本文在Rete-TC算法增加的Beta節(jié)點優(yōu)先級調度特性對處理原子事件的效率的影響非常小.另外,由于Rete-TC算法本質上是改變了處理Beta節(jié)點的順序,不會對推理結果正確性產(chǎn)生影響.每次實驗也驗證了Rete-TC和Rete的推理結果是完全一致的.

圖6 Rete-TC和Rete的匹配時間

在相同的原子事件輸入規(guī)模下,Rete-TC相比Rete匹配時間略增的原因討論如下:

Rete-TC 中激活的Beta節(jié)點優(yōu)先級隊列的數(shù)據(jù)結構采用紅黑樹,支持在O(logN)時間復雜度內對優(yōu)先級隊列中元素進行排序,其中N為優(yōu)先級隊列中Beta節(jié)點個數(shù).而Rete算法中對激活的Beta節(jié)點進行管理采用FIFO數(shù)據(jù)結構,時間復雜度為O(1).在本文的實驗環(huán)境下Rete-TC 中Beta節(jié)點優(yōu)先級激活隊列中Beta節(jié)點最大數(shù)量級約為104,Beta節(jié)點優(yōu)先級隊列單次操作時間約為10-6s,Rete-TC算法用于維護Beta節(jié)點優(yōu)先級隊列的時間數(shù)量級約為10-2s,所以Rete-TC相比Rete匹配時間略增.

4.4 截止期討論

規(guī)則的截止期通常由應用需求確定,確定后一般不再改變.但也可能存在某些特殊場景,例如由于監(jiān)控外部環(huán)境或者監(jiān)控需求發(fā)生特殊變化,規(guī)則截止期需動態(tài)改變,下面對此問題給出一種解決思路.解決思路為:(1)在Rete-TC網(wǎng)絡建立階段采用哈希表建立每個Beta節(jié)點關聯(lián)的規(guī)則集合,Rete-TC匹配運行階段直接使用即可.(2)在Beta節(jié)點激活隊列更新維護模塊UpdateAtiveNodesByPriority 中獲取準備進入激活隊列的Beta節(jié)點關聯(lián)的規(guī)則集合中各規(guī)則最新截止期.(3)在Beta節(jié)點激活隊列更新維護模塊UpdateAtive-NodesByPriority 中對準備進入激活隊列的Beta節(jié)點的優(yōu)先級按照式(1)進行計算,之后按UpdateAtive-NodesByPriority 原有邏輯運行即可.由于步驟(2)和(3)計算過程簡單,對Beta節(jié)點激活隊列更新維護模塊的運行時間開銷影響小.關于動態(tài)截止期的問題后續(xù)可進一步深入研究.

5 應用案例

隨著CPS的快速發(fā)展,建筑CPS 逐漸興起,傳統(tǒng)的建筑正在演變成集環(huán)境感知、實時分析、科學決策和精準執(zhí)行功能于一體的智慧建筑.以建筑CPS的監(jiān)控為例,如圖7所示.圖7中建筑物理環(huán)境蘊含的隱性數(shù)據(jù)通過環(huán)境感知轉換為顯性數(shù)據(jù),進而能夠在信息空間進行實時分析,從而將顯性數(shù)據(jù)轉換為有價值的信息.信息經(jīng)過綜合處理形成最優(yōu)決策對物理空間實體進行精確調節(jié).圖7中有3類場景需要監(jiān)控,分別是火災場景、節(jié)能場景和環(huán)境舒適度調節(jié)場景.其中,火災場景具有時間約束.節(jié)能場景和環(huán)境舒適度調節(jié)場景只需盡可能快監(jiān)控即可,時間約束較為寬松,錯失截止期不會造成嚴重后果.每個場景都由一系列原子事件所喻示.例如,房間內溫度升高事件和煙霧產(chǎn)生事件可能喻示火災發(fā)生.房間內檢測到無人事件且用電設備運行中事件喻示識別到潛在的節(jié)能場景,需進行節(jié)能管理,否則會造成能源浪費.

圖7 建筑CPS監(jiān)控示意

為了驗證RTCPMS系統(tǒng)的有效性,我們以北京市建筑設計研究院有限公司某大樓作為案例研究對象.該大樓總共有13層,每層有25個房間,每個房間大約20個傳感器.其中的某個房間的傳感器布局如圖8所示.

圖8 大樓某房間中的傳感器布局

以該大樓的3個監(jiān)控場景需求為例.(1)關于火災監(jiān)控場景.我們在位置A-J處部署一個溫度傳感器和一個煙霧傳感器.如果房間4個角落的傳感器感知的數(shù)據(jù)同時超出閾值,這表明該房間已發(fā)生嚴重火災;每個房間有兩個防火門,當火災蔓延到防火門的時候,防火門需要及時關閉.(2)關于環(huán)境健康參數(shù)方面的智能控制場景.在K-M位置處,我們部署環(huán)境健康相關的監(jiān)控傳感器來收集PM25、溫度和濕度的數(shù)據(jù).(3)關于節(jié)能管理場景.在O-U的位置,我們部署人員探測傳感器,當探測到無人時,RTCPMS 自動關閉燈光、空調和空氣凈化器.(1)應最大化地滿足時間約束,(2)(3)需盡可能快的處理.

根據(jù)上述監(jiān)控需求,我們制定規(guī)則,如表2所示.

表2 智慧建筑監(jiān)控規(guī)則

傳感器產(chǎn)生的事件由采集程序進行采集并存儲在實時數(shù)據(jù)庫中.大型建筑的火災場景是一種典型的事件風暴場景,當火災發(fā)生時,在短時間內,用于火災監(jiān)控的各類傳感器將上報大量事件,如溫度超標、煙霧濃度超標等.

應用案例的實驗結果如圖9所示.圖9中RTCPMS使用Rete-TC算法,RTCPMS-WITHOUT-TC 使用Rete算法.當原子事件數(shù)在1.0×105至2.5×105范圍內,RTCPMS可以使得火災報警規(guī)則在截止期內觸發(fā).RTCPMS-WITHOUT-TC 只能確保原子事件數(shù)在1.0×105至2.0×105范圍內,火災報警規(guī)則在截止期內觸發(fā).當輸入的原子事件數(shù)超過2.5×105時,RTCPMS和RTCPMS-WITHOUT-TC 都會發(fā)生規(guī)則錯失截止期情況.但RTCPMS處理火災報警類規(guī)則的成功率始終高于RTCPMS-WITHOUT-TC (平均高12%).從這個智慧建筑的應用案例可以看出,本文建立的RTCPMS系統(tǒng)可以更有效的滿足CPS監(jiān)控的時間約束.

圖9 案例運行結果

6 總結

CPS是將計算過程和物理過程集成的系統(tǒng),利用嵌入式計算機和網(wǎng)絡對物理過程進行監(jiān)測和控制,并通過反饋環(huán)實現(xiàn)計算和物理過程的相互影響.CPS監(jiān)控是從物理設備產(chǎn)生的事件中感知關注場景并作出響應的過程,是CPS的核心功能之一.在CPS監(jiān)控中,事件與動作之間的因果關系往往使用規(guī)則來描述.采用規(guī)則系統(tǒng)相較于過程式邏輯具有若干優(yōu)勢,為此,學者們提出了基于規(guī)則的CPS監(jiān)控方法,然而CPS的實時性為CPS監(jiān)控帶來了時間約束問題.目前已有的基于規(guī)則的CPS監(jiān)控方法未考慮CPS監(jiān)控場景的時間約束,僅僅利用各種優(yōu)化技術來縮短監(jiān)控的響應時間.為此,本文基于實時規(guī)則引擎建立了一個CPS的實時監(jiān)控系統(tǒng)RTCPMS.該系統(tǒng)采用Rete網(wǎng)絡表示監(jiān)控規(guī)則.

RTCPMS 將實時推理技術和CPS監(jiān)控結合,其核心是一個新的實時推理算法Rete-TC.Rete-TC算法引入了規(guī)則截止期,通過基于優(yōu)先級的Beta節(jié)點調度方法,使得CPS監(jiān)控的時間約束盡可能地被滿足.模擬實驗與智慧建筑應用案例驗證了RTCPMS系統(tǒng)的有效性,且實驗結果表明其核心算法Rete-TC的調度成功率優(yōu)于傳統(tǒng)的規(guī)則推理算法Rete.

CPS中,由于傳感器擾動,可能會產(chǎn)生不精確的事件,當前基于規(guī)則推理的CPS監(jiān)控不適用于此場景.下一步的研究中,我們將基于Rete-TC,研究實時的模糊推理技術,來支持對不精確的事件進行實時監(jiān)控,從而提升CPS實時監(jiān)控的魯棒性.另外,當前基于規(guī)則的CPS監(jiān)控方法需要事先由領域專家制定規(guī)則,不適應于復雜的動態(tài)場景的自適應監(jiān)控.隨著機器學習的廣泛使用,將機器學習與規(guī)則進行結合也是一個有潛力的研究方向.

致謝.在此,我們向對本文的工作給予幫助的中國科學院軟件研究所人機交互技術與智能信息處理實驗室的姚乃明博士、冷昶博士和馬翠霞老師以及評閱此文的各位專家表示感謝.