摘 要: 通過建立空間事件模型，擴展定義了空間事件復合算子及其語義；采用組合著色Petri網構造基于空間關系的復合事件檢測模型并提出基于該模型的檢測算法；通過應用實例驗證該檢測模型是一個簡潔、有效的復合事件檢測機制。
關鍵詞: 空間復合事件 組合著色Petri網 復合事件檢測
?
復合事件及其檢測可以應用到股票交易、網絡管理、航空交通控制、指揮決策等領域。隨著空間信息的廣泛應用，在遠程監控、LBS、Location-aware計算等領域，也需要實現與空間有關的事件檢測。傳統空間信息應用系統中與空間有關的復合事件檢測通過在應用處理邏輯中直接編寫事件檢測的代碼實現。這種解決方案不利于實現開放的、可擴展的通用系統。由于很多事件是通用的，事件檢測機制應該是多個應用系統共享，否則系統的維護代價較大。
對復合事件檢測的研究最初是在主動數據庫領域中進行的[2]。Ode采用有窮自動機實現復合事件檢測。SAMOS采用著色Petri網對復合事件檢測，可以攜帶事件流及事件參數等復雜信息。但是SAMOS也沒有定義和說明Petri網的組合問題。為解決不滿足交換律的復合算子的沖突問題，文獻[5]引入了時序算子，提出TR-Petri網。文獻[2]引入部分檢測事件緩沖池和時間緩沖池對原子事件進行高效的過濾。在空間事件檢測方面目前尚未展開更多的研究工作，文獻[1]使用三元組{OID, TS, LOC }定義空間事件模型，支持簡單的空間謂詞檢測，但是這種方法是基于空間對象而不是基于事件本身的空間屬性。文獻[4]討論了從空間完整性約束導出數據庫ECA規則的方法，由于ECA條件和動作部分可以分別在數據庫中的查詢處理和事務處理技術中找到相應的解決方案，而事件部分研究的不是很多。本文將在此基礎上，研究基于空間關系的復合事件檢測機制。
1 空間事件模型
在討論基于空間關系的復合事件檢測機制之前，首先必須形式化描述空間事件及空間事件復合算子。空間事件模型采用三元組來表示SE={EID,T,S}，其中EID∈N表示事件標識；T∈N，表示等距離離散時間信息；S∈R×R表示參照坐標系統定義的坐標。空間對象和空間謂詞SP(Spatial Predicate)定義如下：
簡單線段L: Sbegin×Send, Sbegin, Send∈R×R, Sbegin和Send分別表示線段的起始點和結束坐標；坐標S在線段L上時IN(S,L)為真。
封閉區域Z:∪(L×N)；坐標S在區域Z內時IN(S,Z)為真。
假設方向關系是參照坐標系統定義的，即North方向與y軸方向一致，East方向與x軸方向一致。令b表示對象的MBR，則b可以通過其左下角坐標(b.xl,b.yl)和右上角坐標(b.xu, b.yu)定義。如果以s為目標，b和s1分別是參考矩形和參考點，那么采用基于投影的方向模型，s相對于b、s1的方向關系謂詞可以由North-South方向(N,S)s,b、(N,S)s,s1和East-West方向(E,W)s,b、(E,W)s,s1的組合定義。其中，(N,S)s,b和(E,W)s,b可以通過下面的公式定義，(N,S)s,s1和(E,W)s,s1可以采用類似方式定義：
如果將(N,S)s1,s2和(E,W)s1,s2的組合記作(N,S,E,W)s1,s2，那么基于四元組(N,S,E,W)s1,s2的不同取值可以定義s1相對于s2的16種方向關系，如NW(s1,s2)=(1,0,0,1)。
空間事件的語義解釋函數Φ(SE):T×S→{True,False}定義為：Φ(SE(t,s))=True，if an event of type SE occurs at time t and location s。
首先將傳統的事件復合算子語義擴展定義如下：
· 非空間算子NSO(NonSpatial Operator)
方向和距離算子有參考事件或者區域，因此這些算子是不滿足交換律的。從定義來看，這些算子在時間上是以參考事件的出現為檢測起始事件的。
2 基于組和著色Petri網的空間復合事件檢測模型
2.1檢測模型
傳統的Petri網對于公共事件表達式需要構造冗余的Petri網，而且無法對位置信息" title="位置信息">位置信息進行檢測，需要對之改造和擴展。本文提出基于組合著色Petri網的復合事件檢測模型，既能夠利用復合事件的公共表達式，也可以在存儲較少事件歷史的情況下，保持積聚算子。
定義(1)——復合事件檢測組件Petri網CPN(Component Petri Net)
CPN的靜態結構是一個八元組,CPN=(P,PI,PO,T,A, C,E,W)相關含義如下：
P是庫所的有限集合。將每個原子事件對應到組件Petri網的一個輸入庫所，復合事件對應到組件Petri網的一個輸出庫所，則定義PI
P為有限輸入庫所集合，定義POP為有限輸出庫所集合。T是變遷的有限集合。AP×T∪T×P是連接變遷和庫所的弧的有限集合。C是標記類型(即顏色)的有限集合。E為弧函數。將每條弧映射到一個表達式、空間算子或者是缺省的單位權值" title="權值">權值。Eik表示由Pi到Tk或者Ti到Pk的弧函數。其中權值函數只作用在P×T，空間算子只作用在T×P。W: T→N變遷權值函數，將每個變遷映射到一個自然數表示的權值。
定義(2)——組件Petri網的聯接變遷、聯接弧及標記向量
聯接變遷(Connection Transition)集合TOI為聯接輸出庫所和輸入庫所的變遷，聯接弧(Connection Arc)集合AOI定義為AOIPO×TOI∪TOI×PI，同時定義PTI為聯接輸入庫所集合，PTO為聯接輸出庫所集合。令Pi∈P，mark(Pi)=(t,s)表示Pi中當前標記的值，其分量分別標記為mark(Pi).t和mark(Pi).s。當mark(Pi).t=0時表示Pi中當前無標記。令Tk∈TOI∪T, °Tk表示Tk所有輸入庫所的集合, Tk°表示Tk所有輸出庫所的集合。
定義(3)——組合著色Petri網CCPN(Compositional Colored Petri Net)
CCPN的靜態結構是CCPN=(CPN,TOI,AOI)。
定義(4)——變遷的授權
稱變遷Tk是授權的，如果對
i，Pi∈°Tk, mark(Pi).t≠0。授權變遷可被觸發，觸發時同時執行如下三個步驟：(1)如果Pi 中標記數與Ai,k權值相等，mark(Pi)=0, 對i,Pi∈°Tk，如果Pi中標記數小于權值，則將標記數累加并且庫所只保留最近的標記信息；(2)如果Ak,i上未定義空間謂詞并且Pi中標記數與Ai,k權值相等，則mark(Pj)=Ekj(MAX{Eik(mark(Pi))|對i，Pi∈°Tk}), 對j，Pj∈Tk°, 其中MAX{(a1,b1),(a2,b2),…,(an,bn)=a,b}，1≤k≤n,1≤i≤n,ai≤ak；(3)如果Ai,k上定義的SP為真，則mark(Pj)=Ekj(MAX{Eik(mark(Pi))|對i，Pi∈°Tk}), 對j，Pj∈Tk°, 其中MAX{(a1,b1),(a2,b2),…,(an,bn)=a,b}，1≤k≤n,1≤i≤n, ai≤ak；如果Ak,i上定義的SP為假，則mark(Pi)=0, 對i, Pi∈°Tk。
使用組件Petri網組合CCPN時，用聯接弧將組件Petri網的輸出庫所與一個聯接變遷聯接，同時將該聯接變遷通過聯接弧與另一個組件Petri網的輸入庫所相聯。這樣的連接不會影響組件Petri網自身的觸發過程，而其觸發又可以帶動整個CCPN的觸發，從而簡潔、有效地組合成了更復雜的事件檢測Petri網。可以有兩種方式構成CCPN，即事件作為多個復合事件的組件事件，如圖1(a)；或者復合事件作為進一步復合事件的一個組件事件，如圖1(b)。原子事件有可能對應到多個組件Petri網的輸入庫所，因此進行全局模式的事件檢測時，CCPN在遞歸" title="遞歸">遞歸觸發時需要將事件類型及其發生時刻、發生位置在網上傳播。這樣，對應于同樣的原子事件只需要一次檢測即可。對于復合事件也是一樣的策略，在每個CPN輸出庫所中都將檢測到的復合事件保存到事件鏈表" title="鏈表">鏈表中。
2.2 空間復合事件檢測算法
構造完成CCPN模型后，本節給出全局模式下復合事件的檢測算法和CCPN中標記觸發并遞歸尋找授權變遷的算法。
算法(1)——設原子事件由數據庫內核檢測，則全局模式下的復合事件檢測算法描述如下：
輸入：原子事件
輸出：檢測結果鏈表
for all CPN which contains primitive event PE as input place
insert PE to detected list;
PE.i:= input place of PE in CPN;
for every broadcast in FindAndFire(PE.i);
for all output place of CPN
insert CE to detected list
detected list中維護當前檢測到的事件鏈表。
算法終止性分析：首先復合事件集是有限的，并且復合事件的組件事件也是有限的，那么
(1)如果沒有任何變遷觸發，FindAndFire過程將終止，具體見算法(2)；
(2)FindAndFire算法遞歸次數有限，那么廣播事件次數有限；
(3)整個算法當FindAndFire算法終止后終止。
算法(2)——CCPN事件檢測算法
FindAndFire(mplace)
For each transition k
For input places of transitions k
i:=1;
Find first input place;
IF (m[i].t≠0) {
Hold the latest information or compute cumulative operator due to N[i,k]}
WHILE firing AND i ＜NP DO{
i:= i+1;
Search other input place and t:=m[i];
IF t.t = 0 {{firing:=FALSE; }ELSE {IF t.t ＞m[l].t { l:=i; }}}}
IF firing {
t:=m[l];
Fire the transition;
For each output places j of transitions k{
Broadcast for global detection or computer
spatial operator due to N[i,k];
FindAndFire(j);}}
其中SpatialOperate(mplace)為空間算子計算算法，輸入為變遷位置，輸出布爾型。對于二元SO，輸入庫所只保留最近的參考事件，如果變遷所有輸入庫所中的事件滿足空間算子，則返回TRUE，否則返回FALSE。本文不詳細列出。
2.3 應用實例
本實驗過程包括：用戶使用事件規范語言定義復合事件，經過復合事件編譯器編譯成功后存入數據庫，并由CCPN構造器構造檢測復合事件的組合著色Petri網存入數據庫。當數據庫內核中的原子事件檢測器檢測到原子事件發生后，通知CCPN檢測器進行復合事件檢測，檢測結果通知應用程序，應用程序根據復合事件的發生調用ECA規則執行器執行下一步操作，用戶也可以在應用程序中對數據庫中的復合事件進行查詢、更新等維護操作。圖2為復合事件E4=OR(E1, NE(E2, E3))的全局模式檢測實例。首先將該復合事件編譯，然后構造CCPN，如圖2(a)所示。最后進行復合事件檢測。使用原子事件生成器按時間順序產生事件類型為0～10的隨機事件，事件的位置信息也是隨機的，為了演示方便，將位置范圍控制在地圖可見區域。原子事件中構成復合事件的組件事件插入到組件事件列表中，每次插入則調用基于CCPN的復合事件檢測器檢測。由于采用Recent事件消耗策略，對于檢測到的組件事件E2，如果多次出現，則只保留最近的，用于復合事件E4的檢測。檢測到NE(E2,E3)后，也消耗掉E2，E3，為了更清楚地演示，只在刪除E2時置Eid為“D”標識。對于檢測到的組件事件和復合事件的空間位置信息，在地圖上進行了顯示，圖2(b)是針對實驗數據的運行界面。
需要指出的是，實驗假定時間軸等距離。實際情況中事件的發生并非按照等距離時間間隔" title="時間間隔">時間間隔，因此可以設定一個時間間隔閾值，根據事件發生的最小間隔來調整該閥值，這樣就可以轉換成等距離時間間隔的情況。另外實驗中也沒有考慮事件檢測本身所要消耗的計算時間延遲。同時聯接變遷和聯接弧也可能在事件檢測時間中造成一定的延遲。
針對現有的主動數據庫事件檢測機制難以滿足空間事件檢測的需求，本文建立了空間事件模型，在該模型基礎上定義了基于空間關系的事件復合算子及其語義，并證明該定義對于復合運算是封閉的；為了簡化構造復合事件檢測Petri網，本文采用組合著色Petri網構造了復合事件檢測模型，充分利用復合事件公共表達式，簡化Petri網的構造；提出基于CCPN的檢測算法；通過應用實例驗證該檢測模型是一個簡潔、有效的復合事件檢測機制。
本文沒有考慮分布式環境下的空間事件檢測機制，分布式環境下要考慮原子事件的并發性。全局模式下的事件采用鏈表簡單結構管理，下一步將引入更好的數據結構以提高檢測效率。同時空間算子的描述能力還不夠強，不能滿足更多用戶的需求。將CCPN檢測系統與空間數據庫相結合，充分利用空間數據庫的查詢處理機制還需要做大量的工作。
參考文獻
1 Xiaoyan Chen, Ying Chen,Fangyan Rao.An Efficient Spatial Publish/Subscribe System for Intelligent Location Based Services. San Diego USA： DEBS′03 2003
2 A. Hinze. Efficient filtering of composite events. In Proceed-ings of the BNCOD British National Conference on Datbases,London, UK, 2003
3 Jorn W. Janneck, Robert Esser, Higher-order Petri net modeling - techniques and applications Workshop on Software Engineering and Formal Methods, Adelaide, Australia：Petri Nets 2002
4 熊 偉，張 巨，景 寧.從空間完整性約束導出觸發器ECA規則. 計算機科學，2003;30(10):207～209
5 左萬利.復合時序事件及其基于Petri網的檢測.系統工程學報，2003;18(3):262～267