摘 要: 通過建立空間事件模型,，擴(kuò)展定義了空間事件復(fù)合算子及其語義；采用組合著色Petri網(wǎng)構(gòu)造基于空間關(guān)系的復(fù)合事件檢測模型并提出基于該模型的檢測算法,；通過應(yīng)用實(shí)例驗(yàn)證該檢測模型是一個(gè)簡潔,、有效的復(fù)合事件檢測機(jī)制。
關(guān)鍵詞: 空間復(fù)合事件 組合著色Petri網(wǎng) 復(fù)合事件檢測
?
復(fù)合事件及其檢測可以應(yīng)用到股票交易,、網(wǎng)絡(luò)管理,、航空交通控制、指揮決策等領(lǐng)域,。隨著空間信息的廣泛應(yīng)用,，在遠(yuǎn)程監(jiān)控、LBS,、Location-aware計(jì)算等領(lǐng)域,，也需要實(shí)現(xiàn)與空間有關(guān)的事件檢測。傳統(tǒng)空間信息應(yīng)用系統(tǒng)中與空間有關(guān)的復(fù)合事件檢測通過在應(yīng)用處理邏輯中直接編寫事件檢測的代碼實(shí)現(xiàn),。這種解決方案不利于實(shí)現(xiàn)開放的,、可擴(kuò)展的通用系統(tǒng)。由于很多事件是通用的,，事件檢測機(jī)制應(yīng)該是多個(gè)應(yīng)用系統(tǒng)共享,，否則系統(tǒng)的維護(hù)代價(jià)較大。
對復(fù)合事件檢測的研究最初是在主動數(shù)據(jù)庫領(lǐng)域中進(jìn)行的[2],。Ode采用有窮自動機(jī)實(shí)現(xiàn)復(fù)合事件檢測,。SAMOS采用著色Petri網(wǎng)對復(fù)合事件檢測，可以攜帶事件流及事件參數(shù)等復(fù)雜信息,。但是SAMOS也沒有定義和說明Petri網(wǎng)的組合問題,。為解決不滿足交換律的復(fù)合算子的沖突問題，文獻(xiàn)[5]引入了時(shí)序算子,，提出TR-Petri網(wǎng),。文獻(xiàn)[2]引入部分檢測事件緩沖池和時(shí)間緩沖池對原子事件進(jìn)行高效的過濾。在空間事件檢測方面目前尚未展開更多的研究工作,，文獻(xiàn)[1]使用三元組{OID, TS, LOC }定義空間事件模型,，支持簡單的空間謂詞檢測,，但是這種方法是基于空間對象而不是基于事件本身的空間屬性。文獻(xiàn)[4]討論了從空間完整性約束導(dǎo)出數(shù)據(jù)庫ECA規(guī)則的方法,，由于ECA條件和動作部分可以分別在數(shù)據(jù)庫中的查詢處理和事務(wù)處理技術(shù)中找到相應(yīng)的解決方案,，而事件部分研究的不是很多。本文將在此基礎(chǔ)上,，研究基于空間關(guān)系的復(fù)合事件檢測機(jī)制,。
1 空間事件模型
在討論基于空間關(guān)系的復(fù)合事件檢測機(jī)制之前，首先必須形式化描述空間事件及空間事件復(fù)合算子,?？臻g事件模型采用三元組來表示SE={EID,T,S}，其中EID∈N表示事件標(biāo)識,；T∈N,，表示等距離離散時(shí)間信息；S∈R×R表示參照坐標(biāo)系統(tǒng)定義的坐標(biāo),?？臻g對象和空間謂詞SP(Spatial Predicate)定義如下：
簡單線段L: Sbegin×Send, Sbegin, Send∈R×R, Sbegin和Send分別表示線段的起始點(diǎn)和結(jié)束坐標(biāo)；坐標(biāo)S在線段L上時(shí)IN(S,L)為真,。
封閉區(qū)域Z:∪(L×N),；坐標(biāo)S在區(qū)域Z內(nèi)時(shí)IN(S,Z)為真。
假設(shè)方向關(guān)系是參照坐標(biāo)系統(tǒng)定義的,，即North方向與y軸方向一致,，East方向與x軸方向一致。令b表示對象的MBR,，則b可以通過其左下角坐標(biāo)(b.xl,b.yl)和右上角坐標(biāo)(b.xu, b.yu)定義,。如果以s為目標(biāo)，b和s1分別是參考矩形和參考點(diǎn),，那么采用基于投影的方向模型,，s相對于b、s1的方向關(guān)系謂詞可以由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種方向關(guān)系,，如NW(s1,s2)=(1,0,0,1),。
空間事件的語義解釋函數(shù)Φ(SE):T×S→{True,False}定義為：Φ(SE(t,s))=True，if an event of type SE occurs at time t and location s,。
首先將傳統(tǒng)的事件復(fù)合算子語義擴(kuò)展定義如下：
· 非空間算子NSO(NonSpatial Operator)
方向和距離算子有參考事件或者區(qū)域,，因此這些算子是不滿足交換律的,。從定義來看，這些算子在時(shí)間上是以參考事件的出現(xiàn)為檢測起始事件的,。
2 基于組和著色Petri網(wǎng)的空間復(fù)合事件檢測模型
2.1檢測模型
傳統(tǒng)的Petri網(wǎng)對于公共事件表達(dá)式需要構(gòu)造冗余的Petri網(wǎng),，而且無法對位置信息" title="位置信息">位置信息進(jìn)行檢測，需要對之改造和擴(kuò)展,。本文提出基于組合著色Petri網(wǎng)的復(fù)合事件檢測模型,，既能夠利用復(fù)合事件的公共表達(dá)式，也可以在存儲較少事件歷史的情況下,，保持積聚算子,。
定義(1)——復(fù)合事件檢測組件Petri網(wǎng)CPN(Component Petri Net)
CPN的靜態(tài)結(jié)構(gòu)是一個(gè)八元組,CPN=(P,PI,PO,T,A, C,E,W)相關(guān)含義如下：
P是庫所的有限集合。將每個(gè)原子事件對應(yīng)到組件Petri網(wǎng)的一個(gè)輸入庫所,，復(fù)合事件對應(yīng)到組件Petri網(wǎng)的一個(gè)輸出庫所,，則定義PI
P為有限輸入庫所集合，定義POP為有限輸出庫所集合,。T是變遷的有限集合,。AP×T∪T×P是連接變遷和庫所的弧的有限集合。C是標(biāo)記類型(即顏色)的有限集合,。E為弧函數(shù)。將每條弧映射到一個(gè)表達(dá)式,、空間算子或者是缺省的單位權(quán)值" title="權(quán)值">權(quán)值,。Eik表示由Pi到Tk或者Ti到Pk的弧函數(shù)。其中權(quán)值函數(shù)只作用在P×T,，空間算子只作用在T×P,。W: T→N變遷權(quán)值函數(shù)，將每個(gè)變遷映射到一個(gè)自然數(shù)表示的權(quán)值,。
定義(2)——組件Petri網(wǎng)的聯(lián)接變遷,、聯(lián)接弧及標(biāo)記向量
聯(lián)接變遷(Connection Transition)集合TOI為聯(lián)接輸出庫所和輸入庫所的變遷，聯(lián)接弧(Connection Arc)集合AOI定義為AOIPO×TOI∪TOI×PI,，同時(shí)定義PTI為聯(lián)接輸入庫所集合,，PTO為聯(lián)接輸出庫所集合。令Pi∈P,，mark(Pi)=(t,s)表示Pi中當(dāng)前標(biāo)記的值,，其分量分別標(biāo)記為mark(Pi).t和mark(Pi).s。當(dāng)mark(Pi).t=0時(shí)表示Pi中當(dāng)前無標(biāo)記,。令Tk∈TOI∪T, °Tk表示Tk所有輸入庫所的集合, Tk°表示Tk所有輸出庫所的集合,。
定義(3)——組合著色Petri網(wǎng)CCPN(Compositional Colored Petri Net)
CCPN的靜態(tài)結(jié)構(gòu)是CCPN=(CPN,TOI,AOI)。
定義(4)——變遷的授權(quán)
稱變遷Tk是授權(quán)的,，如果對
i,，Pi∈°Tk, mark(Pi).t≠0,。授權(quán)變遷可被觸發(fā)，觸發(fā)時(shí)同時(shí)執(zhí)行如下三個(gè)步驟：(1)如果Pi 中標(biāo)記數(shù)與Ai,k權(quán)值相等,，mark(Pi)=0, 對i,Pi∈°Tk,，如果Pi中標(biāo)記數(shù)小于權(quán)值，則將標(biāo)記數(shù)累加并且?guī)焖槐Ａ糇罱臉?biāo)記信息,；(2)如果Ak,i上未定義空間謂詞并且Pi中標(biāo)記數(shù)與Ai,k權(quán)值相等,，則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網(wǎng)組合CCPN時(shí),，用聯(lián)接弧將組件Petri網(wǎng)的輸出庫所與一個(gè)聯(lián)接變遷聯(lián)接，同時(shí)將該聯(lián)接變遷通過聯(lián)接弧與另一個(gè)組件Petri網(wǎng)的輸入庫所相聯(lián),。這樣的連接不會影響組件Petri網(wǎng)自身的觸發(fā)過程,，而其觸發(fā)又可以帶動整個(gè)CCPN的觸發(fā)，從而簡潔,、有效地組合成了更復(fù)雜的事件檢測Petri網(wǎng),。可以有兩種方式構(gòu)成CCPN,，即事件作為多個(gè)復(fù)合事件的組件事件,，如圖1(a)；或者復(fù)合事件作為進(jìn)一步復(fù)合事件的一個(gè)組件事件,，如圖1(b),。原子事件有可能對應(yīng)到多個(gè)組件Petri網(wǎng)的輸入庫所，因此進(jìn)行全局模式的事件檢測時(shí),，CCPN在遞歸" title="遞歸">遞歸觸發(fā)時(shí)需要將事件類型及其發(fā)生時(shí)刻,、發(fā)生位置在網(wǎng)上傳播。這樣,，對應(yīng)于同樣的原子事件只需要一次檢測即可,。對于復(fù)合事件也是一樣的策略，在每個(gè)CPN輸出庫所中都將檢測到的復(fù)合事件保存到事件鏈表" title="鏈表">鏈表中,。
2.2 空間復(fù)合事件檢測算法
構(gòu)造完成CCPN模型后,，本節(jié)給出全局模式下復(fù)合事件的檢測算法和CCPN中標(biāo)記觸發(fā)并遞歸尋找授權(quán)變遷的算法,。
算法(1)——設(shè)原子事件由數(shù)據(jù)庫內(nèi)核檢測，則全局模式下的復(fù)合事件檢測算法描述如下：
輸入：原子事件
輸出：檢測結(jié)果鏈表
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中維護(hù)當(dāng)前檢測到的事件鏈表,。
算法終止性分析：首先復(fù)合事件集是有限的,，并且復(fù)合事件的組件事件也是有限的，那么
(1)如果沒有任何變遷觸發(fā),，F(xiàn)indAndFire過程將終止,，具體見算法(2)；
(2)FindAndFire算法遞歸次數(shù)有限,，那么廣播事件次數(shù)有限,；
(3)整個(gè)算法當(dāng)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)為空間算子計(jì)算算法,，輸入為變遷位置,，輸出布爾型。對于二元SO,，輸入庫所只保留最近的參考事件,，如果變遷所有輸入庫所中的事件滿足空間算子，則返回TRUE,，否則返回FALSE,。本文不詳細(xì)列出。
2.3 應(yīng)用實(shí)例
本實(shí)驗(yàn)過程包括：用戶使用事件規(guī)范語言定義復(fù)合事件,，經(jīng)過復(fù)合事件編譯器編譯成功后存入數(shù)據(jù)庫,，并由CCPN構(gòu)造器構(gòu)造檢測復(fù)合事件的組合著色Petri網(wǎng)存入數(shù)據(jù)庫。當(dāng)數(shù)據(jù)庫內(nèi)核中的原子事件檢測器檢測到原子事件發(fā)生后,，通知CCPN檢測器進(jìn)行復(fù)合事件檢測，檢測結(jié)果通知應(yīng)用程序,，應(yīng)用程序根據(jù)復(fù)合事件的發(fā)生調(diào)用ECA規(guī)則執(zhí)行器執(zhí)行下一步操作,，用戶也可以在應(yīng)用程序中對數(shù)據(jù)庫中的復(fù)合事件進(jìn)行查詢、更新等維護(hù)操作,。圖2為復(fù)合事件E4=OR(E1, NE(E2, E3))的全局模式檢測實(shí)例,。首先將該復(fù)合事件編譯，然后構(gòu)造CCPN,，如圖2(a)所示,。最后進(jìn)行復(fù)合事件檢測。使用原子事件生成器按時(shí)間順序產(chǎn)生事件類型為0～10的隨機(jī)事件,，事件的位置信息也是隨機(jī)的,，為了演示方便，將位置范圍控制在地圖可見區(qū)域,。原子事件中構(gòu)成復(fù)合事件的組件事件插入到組件事件列表中,，每次插入則調(diào)用基于CCPN的復(fù)合事件檢測器檢測,。由于采用Recent事件消耗策略，對于檢測到的組件事件E2,，如果多次出現(xiàn),，則只保留最近的，用于復(fù)合事件E4的檢測,。檢測到NE(E2,E3)后,，也消耗掉E2，E3,，為了更清楚地演示,，只在刪除E2時(shí)置Eid為“D”標(biāo)識。對于檢測到的組件事件和復(fù)合事件的空間位置信息,，在地圖上進(jìn)行了顯示,，圖2(b)是針對實(shí)驗(yàn)數(shù)據(jù)的運(yùn)行界面。
需要指出的是,，實(shí)驗(yàn)假定時(shí)間軸等距離,。實(shí)際情況中事件的發(fā)生并非按照等距離時(shí)間間隔" title="時(shí)間間隔">時(shí)間間隔，因此可以設(shè)定一個(gè)時(shí)間間隔閾值,，根據(jù)事件發(fā)生的最小間隔來調(diào)整該閥值,，這樣就可以轉(zhuǎn)換成等距離時(shí)間間隔的情況。另外實(shí)驗(yàn)中也沒有考慮事件檢測本身所要消耗的計(jì)算時(shí)間延遲,。同時(shí)聯(lián)接變遷和聯(lián)接弧也可能在事件檢測時(shí)間中造成一定的延遲,。
針對現(xiàn)有的主動數(shù)據(jù)庫事件檢測機(jī)制難以滿足空間事件檢測的需求，本文建立了空間事件模型,，在該模型基礎(chǔ)上定義了基于空間關(guān)系的事件復(fù)合算子及其語義,，并證明該定義對于復(fù)合運(yùn)算是封閉的；為了簡化構(gòu)造復(fù)合事件檢測Petri網(wǎng),，本文采用組合著色Petri網(wǎng)構(gòu)造了復(fù)合事件檢測模型,，充分利用復(fù)合事件公共表達(dá)式，簡化Petri網(wǎng)的構(gòu)造,；提出基于CCPN的檢測算法,；通過應(yīng)用實(shí)例驗(yàn)證該檢測模型是一個(gè)簡潔,、有效的復(fù)合事件檢測機(jī)制,。
本文沒有考慮分布式環(huán)境下的空間事件檢測機(jī)制,，分布式環(huán)境下要考慮原子事件的并發(fā)性。全局模式下的事件采用鏈表簡單結(jié)構(gòu)管理,，下一步將引入更好的數(shù)據(jù)結(jié)構(gòu)以提高檢測效率,。同時(shí)空間算子的描述能力還不夠強(qiáng)，不能滿足更多用戶的需求。將CCPN檢測系統(tǒng)與空間數(shù)據(jù)庫相結(jié)合,，充分利用空間數(shù)據(jù)庫的查詢處理機(jī)制還需要做大量的工作,。
參考文獻(xiàn)
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 熊 偉，張 巨,，景 寧.從空間完整性約束導(dǎo)出觸發(fā)器ECA規(guī)則. 計(jì)算機(jī)科學(xué),，2003;30(10):207～209
5 左萬利.復(fù)合時(shí)序事件及其基于Petri網(wǎng)的檢測.系統(tǒng)工程學(xué)報(bào)，2003;18(3):262～267