基于規則推理的實時信息物理監控系統①

彭 程,喬 穎,王宏安

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

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

信息物理系統(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](如Designto-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 = ((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上 (因為同一事件對象在一條規則中可能出現多次).EventTypeName含義參見定義1.Constraint參見定義2.OP指“and” (也表示為“&&”)，“or”(也表示為“||”)連接操作符.事件條件有時也稱為事件模式.

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

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

“deadlinen”表示規則的截止期為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網絡不再詳細贅述.

假設有如下規則:

根據上述規則建立的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的路徑節點集RPR1= {β1,β2,β3}.

圖1 Rete網絡示例

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節點激活順序依次處理.這可能會造成時間約束強的監控場景(例如,火災監控場景)得不到及時處理.

圖2 Rete 網中Beta節點處理順序示例

1.3 基于規則的監控場景表示

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

2 Rete-TC實時規則推理算法

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

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

2.1 Beta節點調度

規則的截止期代表了該條規則的緊迫度.所以,具有更早截止期的規則應優先處理.

建立了Beta節點的優先級計算方法:

其中,r為一條規則,r∈Rβ,Rβ是規則的路徑節點集中包含β的規則集合.例如,圖1中的規則R1 路徑節點集RPR1= {β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代表的具有強時間約束要求的火災監測場景可以獲得優先處理.

圖3 Rete-TC 網中Beta節點處理順序示例

算法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 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 RTCPMS的架構

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.

表1 規則集的參數

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

其中,Nsuccess表示在規則截止期前觸發的規則數,Ntotal表示所有觸發的規則數.

匹配時間的定義如下:

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

4.2 成功率

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

圖5 Rete-TC和Rete的成功率

當原子事件數量小于1.0×105,Rete-TC和Rete 下觸發的所有規則都滿足截止期.當輸入的原子事件規模大于1.0×105,激活隊列中的Beta節點的數量增多,Rete-TC和Rete 都會出現在規則截止期內規則對應的Beta節點未處理完情況,從而導致Rete-TC和Rete 觸發的部分規則錯失截止期.當輸入的原子事件規模超過3.0×105時,大量規則觸發,激活隊列中的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的推理結果是完全一致的.

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

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

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

4.4 截止期討論

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

5 應用案例

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

圖7 建筑CPS監控示意

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

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

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

根據上述監控需求,我們制定規則,如表2所示.

表2 智慧建筑監控規則

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

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

圖9 案例運行結果

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監控方法需要事先由領域專家制定規則,不適應于復雜的動態場景的自適應監控.隨著機器學習的廣泛使用,將機器學習與規則進行結合也是一個有潛力的研究方向.

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