摘要：通過建立空間事件模型,擴展定義了空間事件復合算子及其語義;采用組合著色Petri網(wǎng)構造基于空間關系的復合事件檢測模型并提出基于該模型的檢測算法;通過應用實例驗證該檢測模型是一個簡潔、有效的復合事件檢測機制。

關鍵詞：空間復合事件 組合著色Petri網(wǎng) 復合事件檢測

復合事件及其檢測可以應用到股票交易、網(wǎng)絡管理、航空交通控制、指揮決策等領域。隨著空間信息的廣泛應用,在遠程監(jiān)控、LBS、Location-aware計算等領域,也需要實現(xiàn)與空間有關的事件檢測。傳統(tǒng)空間信息應用系統(tǒng)中與空間有關的復合事件檢測通過在應用處理邏穎嘈詞錄?觳獾拇?朧迪幀U庵紙餼齜槳覆煥?謔迪摯?擰⒖評┱溝耐ㄓ孟低場S捎諍芏嗍錄?蓖ㄓ玫?事件檢測機制應該是多個應用系統(tǒng)共享,否則系統(tǒng)的維護代價較大。

對復合事件檢測的研究最初是在主動數(shù)據(jù)庫領域中進行的[2]。Ode采用有窮自動機實現(xiàn)復合事件檢測。SAMOS采用著色Petri網(wǎng)對復合事件檢測,可以攜帶事件流及事件參數(shù)等復雜信息。但是SAMOS也沒有定義和說明Petri網(wǎng)的組合問題。為解決不滿足交換律的復合算子的沖突問題,文獻[5]引入了時序算子,提出TR-Petri網(wǎng)。文獻[2]引入部分檢測事件緩沖池和時間緩沖池對原子事件進行高效的過濾。在空間事件檢測方面目前尚未展開更多的研究工作,文獻[1]使用三元組{OID,TS,LOC}定義空間事件模型,支持簡單的空間謂詞檢測,但是這種方法是基于空間對象而不是基于事件本身的空間屬性。文獻[4]討論了從空間完整性約束導出數(shù)據(jù)庫ECA規(guī)則的方法,由于ECA條件和動作部分可以分別在數(shù)據(jù)庫中的查詢處理和事務處理技術中找到相應的解決方案,而事件部分研究的不是很多。本文將在此基礎上,研究基于空間關系的復合事件檢測機制。

1空間事件模型

在討論基于空間關系的復合事件檢測機制之前,首先必須形式化描述空間事件及空間事件復合算子。空間事件模型采用三元組來表示SE={EID,T,S},其中EID∈N表示事件標識;T∈N,表示等距離離散時間信息;S∈R×R表示參照坐標系統(tǒng)定義的坐標。空間對象和空間謂詞SP(SpatialPredicate)定義如下:

簡單線段L:Sbegin×Send,Sbegin,Send∈R×R,Sbegin和Send分別表示線段的起始點和結束坐標;坐標S在線段L上時IN(S,L)為真。

封閉區(qū)域Z:∪(L×N);坐標S在區(qū)域Z內(nèi)時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)。

空間事件的語義解釋函數(shù)Φ(SE):T×S→{True,False}定義為:Φ(SE(t,s))=True,ifaneventoftypeSEoccursattimetandlocations。

首先將傳統(tǒng)的事件復合算子語義擴展定義如下:

·非空間算子NSO(NonSpatialOperator)

OR(SE1,SE2)(t,s)=SE1(t,s)∨SE2(t,s)

方向和距離算子有參考事件或者區(qū)域,因此這些算子是不滿足交換律的。從定義來看,這些算子在時間上是以參考事件的出現(xiàn)為檢測起始事件的。

2基于組和著色Petri網(wǎng)的空間復合事件檢測模型

2.1檢測模型

傳統(tǒng)的Petri網(wǎng)對于公共事件表達式需要構造冗余的Petri網(wǎng),而且無法對位置信息進行檢測,需要對之改造和擴展。本文提出基于組合著色Petri網(wǎng)的復合事件檢測模型,既能夠利用復合事件的公共表達式,也可以在存儲較少事件歷史的情況下,保持積聚算子。

定義(1)——復合事件檢測組件Petri網(wǎng)CPN(ComponentPetriNet)

CPN的靜態(tài)結構是一個八元組,CPN=(P,PI,PO,T,A,C,E,W)相關含義如下:

P是庫所的有限集合。將每個原子事件對應到組件Petri網(wǎng)的一個輸入庫所,復合事件對應到組件Petri網(wǎng)的一個輸出庫所,則定義PIP為有限輸入庫所集合,定義PIP為有限輸出庫所集合。T是變遷的有限集合。AP×T∪T×P是連接變遷和庫所的弧的有限集合。C是標記類型(即顏色)的有限集合。E為弧函數(shù)。將每條弧映射到一個表達式、空間算子或者是缺省的單位權值。Eik表示由Pi到Tk或者Ti到Pk的弧函數(shù)。其中權值函數(shù)只作用在P×T,空間算子只作用在T×P。W:T→N變遷權值函數(shù),將每個變遷映射到一個自然數(shù)表示的權值。

定義(2)——組件Petri網(wǎng)的聯(lián)接變遷、聯(lián)接弧及標記向量

聯(lián)接變遷(ConnectionTransition)集合TOI為聯(lián)接輸出庫所和輸入庫所的變遷,聯(lián)接弧(ConnectionArc)集合AOI定義為AOIPO×TOI∪TOI×PI,同時定義PTI為聯(lián)接輸入庫所集合,PTO為聯(lián)接輸出庫所集合。令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所有輸出庫所的集合。[!--empirenews.page--]

定義(3)——組合著色Petri網(wǎng)CCPN(CompositionalColoredPetriNet)

CCPN的靜態(tài)結構是CCPN=(CPN,TOI,AOI)。

定義(4)——變遷的授權

稱變遷Tk是授權的,如果對i,Pi∈°Tk,mark(Pi).t≠0。授權變遷可被觸發(fā),觸發(fā)時同時執(zhí)行如下三個步驟:(1)如果Pi中標記數(shù)與Ai,k權值相等,mark(Pi)=0,對i,Pi∈°Tk,如果Pi中標記數(shù)小于權值,則將標記數(shù)累加并且?guī)焖槐Ａ糇罱臉擞浶畔?(2)如果Ak,i上未定義空間謂詞并且Pi中標記數(shù)與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網(wǎng)組合CCPN時,用聯(lián)接弧將組件Petri網(wǎng)的輸出庫所與一個聯(lián)接變遷聯(lián)接,同時將該聯(lián)接變遷通過聯(lián)接弧與另一個組件Petri網(wǎng)的輸入庫所相聯(lián)。這樣的連接不會影響組件Petri網(wǎng)自身的觸發(fā)過程,而其觸發(fā)又可以帶動整個CCPN的觸發(fā),從而簡潔、有效地組合成了更復雜的事件檢測Petri網(wǎng)。可以有兩種方式構成CCPN,即事件作為多個復合事件的組件事件,如圖1(a);或者復合事件作為進一步復合事件的一個組件事件,如圖1(b)。原子事件有可能對應到多個組件Petri網(wǎng)的輸入庫所,因此進行全局模式的事件檢測時,CCPN在遞歸觸發(fā)時需要將事件類型及其發(fā)生時刻、發(fā)生位置在網(wǎng)上傳播。這樣,對應于同樣的原子事件只需要一次檢測即可。對于復合事件也是一樣的策略,在每個CPN輸出庫所中都將檢測到的復合事件保存到事件鏈表中。

圖1CCPN組合方式

2.2空間復合事件檢測算法

構造完成CCPN模型后,本節(jié)給出全局模式下復合事件的檢測算法和CCPN中標記觸發(fā)并遞歸尋找授權變遷的算法。

算法(1)——設原子事件由數(shù)據(jù)庫內(nèi)核檢測,則全局模式下的復合事件檢測算法描述如下:

輸入:原子事件

輸出:檢測結果鏈表

forallCPNwhichcontainsprimitiveeventPEasinputplace

insertPEtodetectedlist;

PE.i:=inputplaceofPEinCPN;

foreverybroadcastinFindAndFire(PE.i);

foralloutputplaceofCPN

insertCEtodetectedlist

detectedlist中維護當前檢測到的事件鏈表。

算法終止性分析:首先復合事件集是有限的,并且復合事件的組件事件也是有限的,那么

(1)如果沒有任何變遷觸發(fā),FindAndFire過程將終止,具體見算法(2);

(2)FindAndFire算法遞歸次數(shù)有限,那么廣播事件次數(shù)有限;

(3)整個算法當FindAndFire算法終止后終止。

算法(2)——CCPN事件檢測算法

FindAndFire(mplace)

Foreachtransitionk

Forinputplacesoftransitionsk

i:=1;

Findfirstinputplace;

IF(m[i].t≠0){

Holdthelatestinformationorcomputecumula-tiveoperatorduetoN[i,k]}

WHILEfiringANDii:=i+1;

Searchotherinputplaceandt:=m[i];

IFt.t=0{{firing:=FALSE;}ELSE{IFt.t>m[l].t{l:=i;}}}}

IFfiring{

t:=m[l];

Firethetransition;

Foreachoutputplacesjoftransitionsk{

Broadcastforglobaldetectionorcomputer

spatialoperatorduetoN[i,k];

FindAndFire(j);}}

其中SpatialOperate(mplace)為空間算子計算算法,輸入為變遷位置,輸出布爾型。對于二元SO,輸入庫所只保留最近的參考事件,如果變遷所有輸入庫所中的事件滿足空間算子,則返回TRUE,否則返回FALSE。本文不詳細列出。

2.3應用實例

本實驗過程包括:用戶使用事件規(guī)范語言定義復合事件,經(jīng)過復合事件編譯器編譯成功后存入數(shù)據(jù)庫,并由CCPN構造器構造檢測復合事件的組合著色Petri網(wǎng)存入數(shù)據(jù)庫。當數(shù)據(jù)庫內(nèi)核中的原子事件檢測器檢測到原子事件發(fā)生后,通知CCPN檢測器進行復合事件檢測,檢測結果通知應用程序,應用程序根據(jù)復合事件的發(fā)生調(diào)用ECA規(guī)則執(zhí)行器執(zhí)行下一步操作,用戶也可以在應用程序中對數(shù)據(jù)庫中的復合事件進行查詢、更新等維護操作。圖2為復合事件E4=OR(E1,NE(E2,E3))的全局模式檢測實例。首先將該復合事件編譯,然后構造CCPN,如圖2(a)所示。最后進行復合事件檢測。使用原子事件生成器按時間順序產(chǎn)生事件類型為0～10的隨機事件,事件的位置信息也是隨機的,為了演示方便,將位置范圍控制在地圖可見區(qū)域。原子事件中構成復合事件的組件事件插入到組件事件列表中,每次插入則調(diào)用基于CCPN的復合事件檢測器檢測。由于采用Recent事件消耗策略,對于檢測到的組件事件E2,如果多次出現(xiàn),則只保留最近的,用于復合事件E4的檢測。檢測到NE(E2,E3)后,也消耗掉E2,E3,為了更清楚地演示,只在刪除E2時置Eid為“D”標識。對于檢測到的組件事件和復合事件的空間位置信息,在地圖上進行了顯示,圖2(b)是針對實驗數(shù)據(jù)的運行界面。[!--empirenews.page--]

圖2應用實例演示

需要指出的是,實驗假定時間軸等距離。實際情況中事件的發(fā)生并非按照等距離時間間隔,因此可以設定一個時間間隔閾值,根據(jù)事件發(fā)生的最小間隔來調(diào)整該閥值,這樣就可以轉換成等距離時間間隔的情況。另外實驗中也沒有考慮事件檢測本身所要消耗的計算時間延遲。同時聯(lián)接變遷和聯(lián)接弧也可能在事件檢測時間中造成一定的延遲。

針對現(xiàn)有的主動數(shù)據(jù)庫事件檢測機制難以滿足空間事件檢測的需求,本文建立了空間事件模型,在該模型基礎上定義了基于空間關系的事件復合算子及其語義,并證明該定義對于復合運算是封閉的;為了簡化構造復合事件檢測Petri網(wǎng),本文采用組合著色Petri網(wǎng)構造了復合事件檢測模型,充分利用復合事件公共表達式,簡化Petri網(wǎng)的構造;提出基于CCPN的檢測算法;通過應用實例驗證該檢測模型是一個簡潔、有效的復合事件檢測機制。

本文沒有考慮分布式環(huán)境下的空間事件檢測機制,分布式環(huán)境下要考慮原子事件的并發(fā)性。全局模式下的事件采用鏈表簡單結構管理,下一步將引入更好的數(shù)據(jù)結構以提高檢測效率。同時空間算子的描述能力還不夠強,不能滿足更多用戶的需求。將CCPN檢測系統(tǒng)與空間數(shù)據(jù)庫相結合,充分利用空間數(shù)據(jù)庫的查詢處理機制還需要做大量的工作。

參考文獻

1XiaoyanChen,YingChen,FangyanRao.AnEfficientSpatialPublish/SubscribeSystemfor

IntelligentLocationBasedServices.SanDiegoUSA:DEBS´032003

2A.Hinze.Efficientfilteringofcompositeevents.InProceed-ingsoftheBNCODBritishNational

ConferenceonDatbases,London,UK,2003

3JornW.Janneck,RobertEsser,Higher-orderPetrinetmodeling-techniquesandapplications

WorkshoponSoftwareEngineeringandFormalMethods,Adelaide,Australia:PetriNets2002

4熊偉,張巨,景寧.從空間完整性約束導出觸發(fā)器ECA規(guī)則.計算機科學,2003;30(10):207～209

5左萬利.復合時序事件及其基于Petri網(wǎng)的檢測.系統(tǒng)工程學報,2003;18(3):262～267