荊 心，張 璟

（1.西安工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安710021；2.西安理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，西安710048）

物聯(lián)網(wǎng)技術(shù)的發(fā)展，促生了大量的分布式應(yīng)用，其以事件通知作為系統(tǒng)運(yùn)行的數(shù)據(jù)來(lái)源，這些數(shù)據(jù)源將始終持續(xù)地發(fā)送出海量的原子事件.這些簡(jiǎn)單的原子事件需要被解釋、組合成高級(jí)的具有一定抽象含義的復(fù)雜事件后才能被高層應(yīng)用正確理解與使用.此類高層應(yīng)用以事件驅(qū)動(dòng)為核心，目標(biāo)在于發(fā)現(xiàn)現(xiàn)在正在發(fā)生著什么，其與以往的目標(biāo)在于發(fā)現(xiàn)過(guò)去發(fā)生了什么的基于數(shù)據(jù)庫(kù)的應(yīng)用存在本質(zhì)差別.由于信息的價(jià)值與時(shí)效性有較大關(guān)系，因此這類應(yīng)用更具實(shí)用價(jià)值［1］.基于事件驅(qū)動(dòng)應(yīng)用的一般架構(gòu)通常由發(fā)生器、接收器、CEP引擎三部分組成［2］.CEP引擎類似人類的大腦，是架構(gòu)中最復(fù)雜、最核心的部分，其負(fù)責(zé)對(duì)原子事件流進(jìn)行模式識(shí)別，發(fā)現(xiàn)蘊(yùn)含其中的因果、時(shí)序、邏輯等關(guān)系，并產(chǎn)生出新的復(fù)雜輸出事件.

近期，CEP技術(shù)在學(xué)術(shù)及業(yè)界都得到了廣泛的關(guān)注，以SASE［3］為代表的大量的CEP系統(tǒng)被提出.雖然這些CEP系統(tǒng)已經(jīng)具備了表達(dá)能力強(qiáng)大的規(guī)則語(yǔ)言，以及高效的實(shí)現(xiàn)模型和優(yōu)化算法.但是其仍然面臨著復(fù)雜的問(wèn)題，即數(shù)據(jù)源的并行處理與多事件模式的有效共享與關(guān)聯(lián).目前CEP處理引擎多采用集中處理方式，來(lái)自多個(gè)數(shù)據(jù)源的事件流合并后才能進(jìn)入，引擎隨后對(duì)每個(gè)已注冊(cè)的事件模式逐一匹配，由此事件流及事件模式均被線性化了.因此CEP引擎的工作方式完全是串行的.而在現(xiàn)實(shí)情況下，數(shù)據(jù)的接收與每個(gè)模式匹配的過(guò)程都應(yīng)該是并行的.引擎接收到的事件不應(yīng)經(jīng)歷排隊(duì)等待的過(guò)程，而應(yīng)直接路由給對(duì)應(yīng)的事件模式，同樣待匹配的模式也不應(yīng)等待其他模式的完成，而應(yīng)并行對(duì)同一輸入進(jìn)行處理.此外，相互關(guān)聯(lián)或模式相似的多個(gè)模式間的有效共享，以及共享后可能存在的沖突問(wèn)題（即共享節(jié)點(diǎn)可同時(shí)參與每個(gè)父模式的匹配，或一次僅允許參與某一個(gè)父模式的匹配，詳細(xì)見(jiàn)第三小節(jié)），在現(xiàn)有的CEP引擎中還未曾提及.僅通過(guò)增強(qiáng)規(guī)則語(yǔ)言的表達(dá)能力是無(wú)法解決這些問(wèn)題的，這是目前CEP引擎面臨的最大的挑戰(zhàn).

由此，文中針對(duì)以往CEP研究在上述方面的不足，結(jié)合文獻(xiàn)［4］中Petri網(wǎng)的并行處理能力，對(duì)其庫(kù)所和變遷計(jì)算進(jìn)行了時(shí)間擴(kuò)展（使其能夠支持時(shí)間窗口及時(shí)序檢測(cè)的要求），綜合了有色Petri網(wǎng)的化簡(jiǎn)能力，提出了一個(gè)11元組的復(fù)雜事件檢測(cè)模型CEP-PN（CEP Petri Net），該模型能夠?qū)崿F(xiàn)多數(shù)據(jù)流的并行接收與處理.給出了該模型可構(gòu)造的基礎(chǔ)網(wǎng)結(jié)構(gòu)，以及由這些網(wǎng)結(jié)構(gòu)構(gòu)造出事件模式的一般方法.通過(guò)Petri網(wǎng)基本性質(zhì)證明了合并計(jì)算網(wǎng)能夠得到與獨(dú)立計(jì)算網(wǎng)完全相同的計(jì)算結(jié)果，并給出了多個(gè)事件模式的合并算法.

1 有色Petri網(wǎng)事件檢測(cè)模型

Petri網(wǎng)是一種直觀的圖形化并行系統(tǒng)建模工具［5］.由于使用Petri網(wǎng)中的庫(kù)所表示事件，變遷表示操作符，可以很輕易的構(gòu)造出事件模式，因此用其對(duì)于復(fù)雜事件檢測(cè)進(jìn)行建模具有天然的優(yōu)勢(shì)［6－7］.標(biāo)準(zhǔn)的有色Petri網(wǎng)能實(shí)現(xiàn)對(duì)大多數(shù)操作符的建模，但是還無(wú)法對(duì)時(shí)間約束、選擇與消耗策略、非事件等CEP具有的特殊方面進(jìn)行建模，因此文中對(duì)標(biāo)準(zhǔn)網(wǎng)進(jìn)行了時(shí)間擴(kuò)展，提出了如下的Petri網(wǎng)模型（CEP-PN），用于形式化描述復(fù)雜事件的檢測(cè)過(guò)程.

定義1 CEP-PN是一個(gè)11元組：CEP-PN＝（P，T，A，C，W ，M，U，G，E，Pin，Pout），且滿足以下條件為

① 其中（P，T，A）是一個(gè)網(wǎng)，P、T、A分別表示庫(kù)所、變遷和弧的有限集，且滿足下列條件：

P∪T≠Φ∧P∩T＝Φ∧A?×T）∪（T×P）；

②C是顏色的一個(gè)有限集合C＝｛c1，c2…cn｝，代表事件類型，可包括原子與復(fù)合事件類型；

③W：A→L（C）＋，W描述弧上消耗或產(chǎn)生的托肯數(shù)和顏色；

M：P→L（C），M描述庫(kù)所上托肯的顏色及數(shù)量，是CEP-PN的標(biāo)識(shí)；

L（C）表示定義在顏色集C上的一個(gè)非負(fù)整數(shù)系數(shù)線性函數(shù)，L（C）＋表示系數(shù)不全為0的L（C），即L（C）＋＝b1c1＋b2c2＋……＋bkck，bi（i＝1，2，…，k）均為非負(fù)整數(shù)，且b1＋b2＋……＋bk≠0；

④U：P→L（C），表示庫(kù)所中各托肯的失效時(shí)間，U與M 形式相同但作業(yè)不同，其中bi為零則表示不失效.M中的ci為托肯顏色，而bi為托肯數(shù)量，U與之不同的是ci為托肯顏色，而bi表示時(shí)間窗口單元；

⑤G表示守衛(wèi)函數(shù)，描述了事件屬性的約束條件，是與輸入庫(kù)所顏色相關(guān)的布爾表達(dá)式.

⑥E表示變遷操作表達(dá)式，描述了如何計(jì)算輸出事件的屬性值.

⑦Pin?P，Pout?P，且滿足Pin≠Φ∧Pout≠Φ∧Pin＝P－Pout∧｛?∈Pout｜p·＝Φ｝，是網(wǎng)的輸入庫(kù)所與輸出庫(kù)所，除去輸入庫(kù)所外的其他庫(kù)所均可作為輸入庫(kù)所，其中：p·＝｛t｜t∈P∪T∧（p，t）∈A｝；

⑧ 對(duì)t∈T，如果p∈·t→M（p）≥W（p，t）∧G（t）＝ture，那么變遷t在標(biāo)識(shí)M 有發(fā)生權(quán)（M［t＞），在標(biāo)識(shí)M下發(fā)生變遷t，產(chǎn)生一個(gè)新的標(biāo)識(shí) M’（M［t＞ M’）

定義中①～⑦描述了CEP-PN的靜態(tài)結(jié)構(gòu)，而⑧描述了網(wǎng)運(yùn)行的動(dòng)態(tài)行為.

2 基本Petri網(wǎng)結(jié)構(gòu)

由于CEP中事件模式的基本構(gòu)件是事件操作符，因此使用CEP-PN對(duì)其進(jìn)行建模，從而構(gòu)造出來(lái)的基本網(wǎng)結(jié)構(gòu)，可作為構(gòu)造事件模式Petri計(jì)算網(wǎng)實(shí)例的原子部件.如果按照操作數(shù)的數(shù)目對(duì)事件操作符進(jìn)行分類，其可以被自然劃分為雙操作數(shù)與單操作數(shù)兩類.因此CEP-PN對(duì)事件操作符的建模也可分為兩類，即雙輸入變遷與單輸入變遷結(jié)構(gòu)（分別如圖1（a）～ （b）所示）.基本網(wǎng)的輸出可作為另一個(gè)基本網(wǎng)的輸入，由此可以將基本網(wǎng)關(guān)聯(lián)起來(lái)，從而形成目標(biāo)計(jì)算網(wǎng)（如圖1（e）所示）.

在圖1（a）中，A、B庫(kù)所上都只有一種顏色，該基本網(wǎng)實(shí)現(xiàn)簡(jiǎn)單，但當(dāng)使用其去構(gòu)造復(fù)雜的事件模式時(shí)，將產(chǎn)生龐大的網(wǎng)結(jié)構(gòu).為精簡(jiǎn)Petri網(wǎng)整體規(guī)模，可以對(duì)雙輸入變遷結(jié)構(gòu)中的庫(kù)所，按照CEPPN的定義進(jìn)行合并（如圖1（c）所示）.合并后的庫(kù)所具有兩種顏色，可同時(shí)接收并存儲(chǔ)兩類事件.圖1（d）為對(duì)圖1（e）進(jìn)行合并后的Petri網(wǎng)實(shí)例，前者與后者比較庫(kù)所數(shù)量明顯減少，且網(wǎng)結(jié)構(gòu)更加緊湊.

使用CEP-PN共享相同的庫(kù)所節(jié)點(diǎn)時(shí)將面臨兩種選擇，即并發(fā)與沖突（分別如圖1（f）、1（g）所示）.在并發(fā)情況下共享節(jié)點(diǎn)將參與每個(gè)子模式的匹配，因此在構(gòu)造時(shí)需對(duì)該節(jié)點(diǎn)進(jìn)行復(fù)制.而在沖突情況下，共享節(jié)點(diǎn)每次僅能夠參與某一個(gè)子模式的匹配，因此在構(gòu)造時(shí)需要對(duì)該節(jié)點(diǎn)進(jìn)行合并.需要注意的是，在合并方式中還可以存在反饋結(jié)構(gòu)，即共享節(jié)點(diǎn)上的事件實(shí)際上不被消耗，從而重復(fù)多次參與子模式的匹配（如圖1（g）中的圓弧線所示）.基本網(wǎng)具體采用何種構(gòu)造方式進(jìn)行聯(lián)接，將由事件模式的消耗策略決定.

圖1 基本Petri網(wǎng)結(jié)構(gòu)Fig.1 The basic structure of Petri net

3 多事件模式的合并

CEP系統(tǒng)中存在大量事件模式合并的情況.由于無(wú)法使用一條規(guī)則定義整個(gè)系統(tǒng)的運(yùn)行，一個(gè)復(fù)雜的情景通常需要先由多條規(guī)則分別定義出來(lái)，然后經(jīng)過(guò)合并才能形成.另外，在一條規(guī)則內(nèi)部，同樣需要經(jīng)歷先構(gòu)造出基本網(wǎng)結(jié)構(gòu)，然后合并的過(guò)程.合并后的Petri計(jì)算網(wǎng)，能夠有效減小CEP系統(tǒng)的整體運(yùn)行規(guī)模，提高系統(tǒng)運(yùn)行效率.由此，以下給出事件模式合并的語(yǔ)義與算法.

定義2 設(shè)CEP-PN為一個(gè)網(wǎng)，如果存在t∈T，使M［t＞M′，則稱M′為從M直接可達(dá)的.如果存在變遷序列t1，t2，…tn（記為σ）和標(biāo)識(shí)序列 M1，M2，…Mn使得 M［t1＞ M1［t2＞ M2…Mn－1［tn＞Mn（記為M［σ＞Mn），則稱Mn為從M 可達(dá)的.從M可達(dá)的一切標(biāo)識(shí)的集合記為R（M），規(guī)定M∈R（M）.

定義3 設(shè)CEP-PN為一個(gè)網(wǎng)，M1和M2是網(wǎng)的兩個(gè)標(biāo)識(shí).如果 ?p∈P 都有M1（p）≤M2（p），則稱M1被M2覆蓋，記作M1≤M2.

定義4 設(shè)CEP-PN為一個(gè)網(wǎng)，M為網(wǎng)的一個(gè)標(biāo)識(shí).若 ?M′∈R（M0），使得M≤M′，則稱M 為CEP-PN的一個(gè)可覆蓋標(biāo)識(shí).

根據(jù)以上定義可以很容易的證明多模式合并后的可達(dá)性.例如：可將如圖1（a）所示的網(wǎng)記為＜a；b＞→ab，則＜a；b；d＞→abd事件模式，可視為＜a；b＞→ab與＜ab；d＞→abd兩個(gè)基本網(wǎng)連接形成的合并網(wǎng).記其初始狀態(tài)為M0，a；b發(fā)生為M1，ab；d發(fā)生為M2，由于M1∈R（M0），且M2∈R（M1）：M2∈R（M0），因此R（M1）R（M0）.即如果變遷序列σ1導(dǎo)致M0→M1可達(dá)，σ2導(dǎo)致M1→M2可達(dá)，則一定存在σ＝σ1＋σ2導(dǎo)致M0→M2可達(dá)，其中M1是合并網(wǎng)的一個(gè)可覆蓋標(biāo)識(shí).

對(duì)于任意兩個(gè)網(wǎng)A、B，如果存在一個(gè)公共可覆蓋標(biāo)識(shí)M，使得M ∈RA（M0），且M ∈RB（M0），則A與B是可以合并的，其中RA（RB）為A（B）初始標(biāo)識(shí)的可達(dá)標(biāo)識(shí)集合.根據(jù)以上結(jié)論可知，＜a；b；c；d，a；b；c；e＞ 兩個(gè)網(wǎng)是可以直接合并的（稱為前結(jié)合模式），＜a；b；c；d，b；c；e＞ 亦是可以合并的（稱為中間結(jié)合模式，后者網(wǎng)b；c可視為前者網(wǎng)a；b；c的特殊子模式），而 ＜a；b；c，e；b；c＞ 是不能直接合并的（稱為后結(jié)合模式），由于a；b的變遷t1與e；b的變遷t2不是同一個(gè)變遷，因此不存在共同的可覆蓋標(biāo)識(shí)，但該類情況可采用后面先合并的方式，即將模式重寫(xiě)為 ＜a；（b；c），e；（b；c）＞ 的形式，以（b；c）為模式起始進(jìn)行網(wǎng)合并，而后才將前面的庫(kù)所與由合并形成的結(jié)果庫(kù)所輸入到一個(gè)變遷上去.后結(jié)合模式面臨一定的風(fēng)險(xiǎn)，即當(dāng)前事件不滿足條件時(shí)，后事件的檢測(cè)將浪費(fèi)計(jì)算資源.

兩個(gè)獨(dú)立的網(wǎng)合并時(shí)會(huì)面臨兩種情況：并發(fā)與沖突（如圖1（f）與1（g）所示）.并發(fā)情況下，合并庫(kù)所采用復(fù)制模式產(chǎn)生出多個(gè)中間結(jié)果，同時(shí)用于每個(gè)事件模式的匹配.而沖突情況下，合并庫(kù)所采用共享模式，僅參與多個(gè)事件模式匹配中的一條.系統(tǒng)使用模式的策略如下：對(duì)位于一條規(guī)則中的基本網(wǎng)結(jié)構(gòu)和串聯(lián)結(jié)構(gòu)，采用連接模式合并，前結(jié)合與中間結(jié)合采用共享模式合并，后結(jié)合采用復(fù)制模式合并，對(duì)位于多條規(guī)則中的網(wǎng)則均采用復(fù)制模式合并.多事件模式合并算法為

①將預(yù)加入CEP引擎運(yùn)行Petri網(wǎng)中的用戶事件模式分解為多個(gè)（FirstPlace，Transition，Second Place，Out put Place）四元組，根據(jù)其中的操作符類型生成相應(yīng)的基本網(wǎng)結(jié)構(gòu)；

②將該事件模式產(chǎn)生基本網(wǎng)結(jié)構(gòu)單元，依次采用連接模式進(jìn)行合并，直到最后；

③采用從頭比對(duì)的方法，將該事件模式與運(yùn)行Petri網(wǎng)中事件模式列表中的其他模式進(jìn)行逐一比較，如果未發(fā)現(xiàn)同類庫(kù)所存在，則將其直接加入到運(yùn)行Petri網(wǎng)中；

④ 如果發(fā)現(xiàn)新事件模式的首庫(kù)所與某運(yùn)行事件模式從首庫(kù)所開(kāi)始匹配，則采用前結(jié)合方式合并相同的子模式部分；

⑤ 如果發(fā)現(xiàn)新事件模式的首庫(kù)所與某運(yùn)行事件模式從其中間某庫(kù)所開(kāi)始匹配，則采用中間結(jié)合方式合并相同的子模式部分；

⑥ 如果發(fā)現(xiàn)新事件模式與某運(yùn)行事件模式存在中間部分匹配，則采用后結(jié)合方式合并；

⑦直到與運(yùn)行事件模式列表全部匹配完畢.

4 實(shí)驗(yàn)與分析

由于目前沒(méi)有開(kāi)源的以有色Pertri網(wǎng)為模型的CEP引擎，因此選擇以自動(dòng)機(jī)為模型的SASE原型系統(tǒng)進(jìn)行比較.與SASE進(jìn)行比較的其他重要原因在于，自動(dòng)機(jī)模型是CEP社區(qū)最為流行的模式匹配方法，因此通過(guò)兩者的比較能夠清楚的發(fā)現(xiàn)兩種基礎(chǔ)實(shí)現(xiàn)思想的優(yōu)缺點(diǎn).為確保準(zhǔn)確測(cè)試兩者的性能，文中構(gòu)造了相同的環(huán)境.首先事件模式采用了SASE提供的檢測(cè)三支價(jià)格相等的股票序列的示例，然后讓兩個(gè)系統(tǒng)使用同一個(gè)事件發(fā)生器作為輸入，并檢查兩者具有完全相同的輸出.顯然在輸入、輸出相同的情況下，占用越少時(shí)間、空間的系統(tǒng)性能越好，系統(tǒng)吞吐量則越大.

如果一個(gè)原子事件未參與復(fù)合而被過(guò)濾掉了，那么其顯然不會(huì)充分占用計(jì)算時(shí)間.為最大限度的估算系統(tǒng)的計(jì)算能力，本實(shí)驗(yàn)的事件發(fā)生器產(chǎn)生三支股票事件各3，000個(gè)，并使得其全部參與計(jì)算，最終復(fù)合出3，000個(gè)匹配結(jié)果.為研究多模式在并發(fā)數(shù)據(jù)環(huán)境下的性能，復(fù)制事件模式從10倍至50倍.復(fù)制模式可以保證兩個(gè)系統(tǒng)使用同一輸入，同時(shí)輸出一致的結(jié)果.例如：50個(gè)事件模式時(shí)，兩者均輸出150，000個(gè)復(fù)雜事件.如圖2所示，當(dāng)同時(shí)運(yùn)行的模式數(shù)量小于20時(shí)，SASE運(yùn)行較快，但隨著模式數(shù)量的增加，SASE處理時(shí)長(zhǎng)的增長(zhǎng)速度明顯高于CEP系統(tǒng).其主要原因在于，隨著注冊(cè)模式的增加，在SASE中活動(dòng)的自動(dòng)機(jī)數(shù)量快速增長(zhǎng)，使得用于檢索活動(dòng)狀態(tài)的索引的效率持續(xù)降低，而Petri網(wǎng)系統(tǒng)可以通過(guò)在其庫(kù)所和變遷上創(chuàng)建更多的并發(fā)進(jìn)程有效降低處理時(shí)間.由此可知，當(dāng)并發(fā)模式數(shù)量較少時(shí)，自動(dòng)機(jī)模型執(zhí)行高效.相反，Petri網(wǎng)模型則具有較好的運(yùn)行效率.

圖2 與SASE系統(tǒng)的比較Fig.2 Comparison with the SASE system

5 結(jié) 論

通過(guò)對(duì)有色Petri網(wǎng)進(jìn)行時(shí)間擴(kuò)展，使其能夠較好的用于CEP事件模式的建模，以前、中、后三種結(jié)合模式進(jìn)行連接的基本網(wǎng)結(jié)構(gòu)，能夠形式化、準(zhǔn)確的表達(dá)事件模式.給出的Petri計(jì)算網(wǎng)自動(dòng)合并算法，能夠?qū)崿F(xiàn)多個(gè)獨(dú)立事件模式的關(guān)聯(lián)共享，由此降低系統(tǒng)計(jì)算資源的利用，提高系統(tǒng)整體的運(yùn)行效率.通過(guò)與目前流行的CEP引擎的比較與分析可知，Petri網(wǎng)系統(tǒng)在多模式并行執(zhí)行時(shí)具有更好的性能，將能夠有效應(yīng)對(duì)大量事件并行輸入與多模式并行處理的實(shí)際情況.

［1］ CUGOLA G，MARGARA A.Processing Flows of Information：From Data Stream to Complex Event Processing［J］.ACM Computing Surveys（CSUR），2012，44（3）：15.

［2］ CUGOLA G，MARGARA A.Complex Event Processing with T-Rex［J］.Journal of Systems and Software，2012，85（8）：1709.

［3］ AGRAWAL J，DIDOA Y，GYLLSTROM D，et al.Efficient Pattern Matching over Event Streams［C］／／Proceedings of the 2008ACM SIGMOD International Conference on Management of Data.Vancouver：ACM，2008：147.

［4］ 黃毅，鄭力，向晴.基于復(fù)雜事件處理的RFID輔助實(shí)時(shí)生產(chǎn)監(jiān)控［J］.清華大學(xué)學(xué)報(bào)：自然科學(xué)版，2013，53（5）：721.HUANG Yi，ZHENG Li，XIANG Qing.RFID Integrated Real－Time Manufacturing Monitoring Based on Complex Event Processing［J］.Journal of Tsinghua University：Science and Technology，2013，53（5）：721.（in Chinese）

［5］ 程蘇珺，王永劍，孟由，等.PMTree：一種高效的事件流模式匹配方法［J］.計(jì)算機(jī)研究與發(fā)展，2013，49（11）：2481.CHENG Su－Jun，WANG Yong－jian，MENG You，et al.PMTree：An Efficient Pattern Matching Method for Event Stream Processing ［J］.Journal of Computer Research and Development，2013，49（11）：2481.（in Chinese）

［6］ 葉蔚，黃雨，趙文，等.基于Petri網(wǎng)的 RFID中間件中復(fù)合事件檢 測(cè)研 究［J］.電子學(xué)報(bào)，2009，36（B12）：1.YE Wei，HUANG Yu，ZHAO Wen，et al.Research on Complex Event Detection in RFID Middleware Based on Colored Petri Net［J］.Acta Electronica Sinica，2009，36（B12）：1.（in Chinese）

［7］ 王中生，楊盛泉.Petri網(wǎng)的總線型DCS的通信機(jī)制［J］.西安工業(yè)大學(xué)學(xué)報(bào)，2010，30（3）：281.WANG Zhong－sheng，YANG Sheng－quan.Research of Communication Mechanism in Bus Topology DCS System Based on Petri Net［J］.Journal of Xi’an Technological University，2010，30（3）：281.（in Chinese）