彭 程,喬 穎,王宏安

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

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

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

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

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

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

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

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

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

1 研究基礎(chǔ)

1.1 術(shù)語和定義

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

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

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

定義2.約束(constraint)

約束可以表示為(Param1op Param2).它由Param1,op和Param2組成.這里Param1是事件屬性名,為變量;op為常見的邏輯操作符,例如>,<,==,>=,<=;Param2可以是一個常量或一個變量(另一個事件的屬性名).當約束為“變量-op-常量”時,它用于確定一個事件的屬性和常量之間的關(guān)系,稱為常量約束,例如,(Person.age >15).當約束為“變量-op-變量”時,它用于確定事件屬性關(guān)系,稱為變量約束,例如,(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秒,截止期大小一般由應(yīng)用確定.如果n取0,則表示規(guī)則無時間約束.

1.2 Rete 推理算法

1.2.1 Rete 基本概念

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

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

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

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

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

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

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

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

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

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

根據(jù)上述規(guī)則建立的Rete網(wǎng)絡(luò)如圖1所示.圖1中左半部分β1～β6為Beta網(wǎng)絡(luò)中的Beta節(jié)點,也稱作連接節(jié)點.連接節(jié)點的輸入來自上一級的Beta節(jié)點(β1節(jié)點為Beta網(wǎng)絡(luò)中第一個節(jié)點,其左輸入為Beta根節(jié)點)和Alpha內(nèi)存節(jié)點,負責(zé)執(zhí)行變量約束測試.例如,β2節(jié)點的輸入來自上一級的Beta節(jié)點β1和Alpha內(nèi)存節(jié)點AM2,負責(zé)執(zhí)行變量約束測試“C2:attr2 == $1.attr2”.β3節(jié)點的左輸入來自于β2和Alpha內(nèi)存節(jié)點AM3,負責(zé)執(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)絡(luò)根節(jié)點到某個規(guī)則終止節(jié)點之間相連的Beta節(jié)點構(gòu)成的路徑.

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

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

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

1.2.3 Rete算法的匹配過程

Rete 網(wǎng)建立后,事件對象從Alpha 根節(jié)點進入網(wǎng)絡(luò),如果相關(guān)的Alpha 常量約束測試通過,則激活后繼相關(guān)Beta節(jié)點.Beta網(wǎng)絡(luò)中的激活有兩種方式,如果Beta節(jié)點接收到左輸入Beta節(jié)點傳遞來的部分匹配(Partial Match,PM),稱為左激活.左激活發(fā)生時,Beta節(jié)點會遍歷其相關(guān)的Alpha內(nèi)存中的Alpha匹配(AM)和新到來的PM進行變量約束測試;如果Beta節(jié)點接受右輸入Alpha網(wǎng)絡(luò)傳遞過來的AM,稱為右激活.此時,Beta節(jié)點會遍歷該節(jié)點的PM和輸入的AM進行變量約束測試.左激活和右激活中的變量約束測試如果通過則產(chǎn)生新的部分匹配(PM)向后繼Beta節(jié)點傳遞并激活相關(guān)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)絡(luò)中Beta節(jié)點的處理是按Beta節(jié)點激活時間順序處理,即FCFS (First Come First Service)的方式,這會造成時間約束強的監(jiān)控場景中的Beta節(jié)點無法得到及時處理,從而無法盡可能滿足監(jiān)控場景的時間約束.例如,假設(shè)規(guī)則1的規(guī)則路徑節(jié)點集RP1 ={β1,β2,β3,β6},規(guī)則2的規(guī)則路徑節(jié)點集RP2 = {β1,β2,β4,β7}.規(guī)則1代表的是建筑節(jié)能監(jiān)控場景(例如,當房間無人時,關(guān)閉燈光和空調(diào)).規(guī)則2代表的是建筑火災(zāi)監(jiān)控場景(例如,當監(jiān)控到房間發(fā)生火災(zāi)時,立刻進行報警等).顯然規(guī)則2 比規(guī)則1 具有更強的時間約束.假設(shè)β4代表火災(zāi)監(jiān)控場景中的某個條件,此時發(fā)生的事件使得β4 被激活,但β4 會被放置在激活隊列的隊尾,而Rete算法按照激活隊列的中Beta節(jié)點激活順序依次處理.這可能會造成時間約束強的監(jiān)控場景(例如,火災(zāi)監(jiān)控場景)得不到及時處理.

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

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

假設(shè)當前存在這樣一個建筑火災(zāi)監(jiān)控場景:當房間4個角落的煙霧傳感器和溫度傳感器值同時超過閾值時,則表示房間發(fā)生嚴重的火災(zāi).該火災(zāi)監(jiān)控場景必須在3 s 內(nèi)監(jiān)測到并觸發(fā)火災(zāi)報警相關(guān)的行動,否則將造成嚴重的損失.上述建筑火災(zāi)監(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é)點調(diào)度方法,使得CPS監(jiān)控盡可能滿足時間約束.

2.1 Beta節(jié)點調(diào)度

規(guī)則的截止期代表了該條規(guī)則的緊迫度.所以,具有更早截止期的規(guī)則應(yīng)優(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é)點對應(yīng)的規(guī)則無時間約束要求.

2.2 Rete-TC算法描述

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

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

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

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

Rete-TC算法過程為先調(diào)用算法2 Rete-TC網(wǎng)絡(luò)構(gòu)造,之后調(diào)用算法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)絡(luò)構(gòu)造輸入:Rule Set輸出:Rete-TC網(wǎng)絡(luò)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)絡(luò)中,其父節(jié)點為Beta(j-1)和Alpha(j):13: end if 14: end if 15: end for 16: end for 17:調(diào)用算法1進行Beta節(jié)點優(yōu)先級計算

算法3.Rete-TC匹配輸入:Events輸出:fired rules 01: while true do 02: if root->alphaNodes[event->eventtype] then //事件類型對應(yīng)的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é)點關(guān)聯(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)生的大量事件中對關(guā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ī)則庫存放領(lǐng)域?qū)＜抑贫ǖ谋O(jiān)控規(guī)則;事件庫存放由安捷實時數(shù)據(jù)庫系統(tǒng)發(fā)布的原子事件.規(guī)則解析模塊將規(guī)則庫中的規(guī)則翻譯成Rete-TC網(wǎng)絡(luò);基于Rete-TC的實時推理模塊從事件庫中取出事件在Rete-TC網(wǎng)絡(luò)上傳遞,進行規(guī)則匹配,匹配成功的規(guī)則輸出到?jīng)Q策和反饋模塊.決策和反饋模塊執(zhí)行規(guī)則中預(yù)設(shè)的動作,例如觸發(fā)一個報警或給用戶反饋.

圖4 RTCPMS的架構(gòu)

4 實驗評估

4.1 實驗設(shè)置

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

4.2 成功率

我們對Rete-TC和Rete的成功率進行對比,實驗結(jié)果如圖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ī)則截止期內(nèi)規(guī)則對應(yīng)的Beta節(jié)點未處理完情況,從而導(dǎo)致Rete-TC和Rete 觸發(fā)的部分規(guī)則錯失截止期.當輸入的原子事件規(guī)模超過3.0×105時,大量規(guī)則觸發(fā),激活隊列中的Beta節(jié)點數(shù)激增,Rete-TC和Rete在規(guī)則截止期內(nèi)未能處理完相關(guān)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的匹配時間進行對比,實驗結(jié)果如圖6所示.從圖6得知,在相同的原子事件規(guī)模輸入下,Rete-TC相比Rete匹配時間略微增加,也就是說,本文在Rete-TC算法增加的Beta節(jié)點優(yōu)先級調(diào)度特性對處理原子事件的效率的影響非常小.另外,由于Rete-TC算法本質(zhì)上是改變了處理Beta節(jié)點的順序,不會對推理結(jié)果正確性產(chǎn)生影響.每次實驗也驗證了Rete-TC和Rete的推理結(jié)果是完全一致的.

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

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

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

5 應(yīng)用案例

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

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

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

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

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

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

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

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

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

圖9 案例運行結(jié)果

6 總結(jié)

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

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

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

致謝.在此,我們向?qū)Ρ疚牡墓ぷ鹘o予幫助的中國科學(xué)院軟件研究所人機交互技術(shù)與智能信息處理實驗室的姚乃明博士、冷昶博士和馬翠霞老師以及評閱此文的各位專家表示感謝.