荊 心，張 璟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

定義中①～⑦描述了CEP-PN的靜態(tài)結構，而⑧描述了網(wǎng)運行的動態(tài)行為.

2 基本Petri網(wǎng)結構

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

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

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

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

3 多事件模式的合并

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

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

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

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

根據(jù)以上定義可以很容易的證明多模式合并后的可達性.例如：可將如圖1（a）所示的網(wǎng)記為＜a；b＞→ab，則＜a；b；d＞→abd事件模式，可視為＜a；b＞→ab與＜ab；d＞→abd兩個基本網(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導致M0→M1可達，σ2導致M1→M2可達，則一定存在σ＝σ1＋σ2導致M0→M2可達，其中M1是合并網(wǎng)的一個可覆蓋標識.

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

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

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

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

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

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

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

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

⑦直到與運行事件模式列表全部匹配完畢.

4 實驗與分析

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

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

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

5 結 論

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

［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］ 黃毅，鄭力，向晴.基于復雜事件處理的RFID輔助實時生產(chǎn)監(jiān)控［J］.清華大學學報：自然科學版，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］.計算機研究與發(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中間件中復合事件檢 測研 究［J］.電子學報，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］.西安工業(yè)大學學報，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）