移動(dòng)數(shù)據(jù)庫(kù)中的事件檢測(cè)

摘要：為了有效檢測(cè)移動(dòng)計(jì)算環(huán)境中的事件，提出了基于Petri網(wǎng)的事件檢測(cè)方式CCPN。該方式能直觀靈活地建模事件，支持異步并發(fā)事件的檢測(cè)以及時(shí)序事件的檢測(cè)；討論了主機(jī)斷接以及移動(dòng)情況下的事件檢測(cè)。

關(guān)鍵詞：移動(dòng)數(shù)據(jù)庫(kù)； 事件檢測(cè)； 帶條中的彩色Petri網(wǎng)； 失序事件檢測(cè)； 斷接檢測(cè)； 移動(dòng)檢測(cè)

中圖分類號(hào)：TP311文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001－3695(2007)07－0108－03

移動(dòng)數(shù)據(jù)庫(kù)管理系統(tǒng)（MDBMS）是在移動(dòng)計(jì)算環(huán)境中進(jìn)行數(shù)據(jù)管理的數(shù)據(jù)庫(kù)系統(tǒng)，是傳統(tǒng)分布式DBMS的擴(kuò)展，可以被看做是客戶端與固定服務(wù)器節(jié)點(diǎn)動(dòng)態(tài)連接的分布式系統(tǒng)。因此，移動(dòng)數(shù)據(jù)庫(kù)管理系統(tǒng)還需要考慮諸多傳統(tǒng)計(jì)算環(huán)境下不需要考慮的問(wèn)題，包括如何適應(yīng)變化的網(wǎng)絡(luò)環(huán)境、對(duì)斷接操作的支持、對(duì)跨區(qū)長(zhǎng)事務(wù)的支持、對(duì)位置相關(guān)查詢的支持、對(duì)查詢優(yōu)化的特殊考慮，以及對(duì)提高有限資源利用率和對(duì)系統(tǒng)效率的考慮等[1~3]。

在移動(dòng)數(shù)據(jù)庫(kù)中引入主動(dòng)機(jī)制[4，5]，用事件做觸發(fā)器，能有效支持?jǐn)嘟硬僮饕约熬W(wǎng)絡(luò)環(huán)境變化的數(shù)據(jù)處理?；谑录囊?guī)則觸發(fā)機(jī)制能實(shí)現(xiàn)相關(guān)的主動(dòng)功能，因此事件的檢測(cè)是很重要的。在移動(dòng)計(jì)算環(huán)境中，基本事件的數(shù)量是巨大的，構(gòu)成復(fù)合事件的不同基本事件之間的關(guān)系是復(fù)雜的。要高效地檢測(cè)事件，就要根據(jù)移動(dòng)計(jì)算環(huán)境的特點(diǎn)和系統(tǒng)要求選擇合適的檢測(cè)方法。傳統(tǒng)的主動(dòng)數(shù)據(jù)庫(kù)給出了集中式或分布式系統(tǒng)的豐富的事件定義與描述[6，7]，考慮了事件的多種檢測(cè)方式[8~11]，但是它們沒(méi)有考慮移動(dòng)計(jì)算環(huán)境下事件的特點(diǎn)以及檢測(cè)方法的特殊要求。

1移動(dòng)數(shù)據(jù)庫(kù)中的事件檢測(cè)

移動(dòng)數(shù)據(jù)庫(kù)中，大量的事件分布在不同節(jié)點(diǎn)上，產(chǎn)生的事件具有分布、并發(fā)、異步、隨機(jī)、不確定的特點(diǎn)；事件源通常是移動(dòng)主機(jī)，事件的到達(dá)因網(wǎng)絡(luò)連接的不穩(wěn)定以及移動(dòng)主機(jī)的移動(dòng)而發(fā)生時(shí)延、失序的情況。本文提出的檢測(cè)方法應(yīng)該能夠高效地進(jìn)行分布式檢測(cè)、并發(fā)異步事件的檢測(cè)、失序事件的檢測(cè)以及斷接檢測(cè)、移動(dòng)檢測(cè)。在移動(dòng)計(jì)算環(huán)境中，事件分布在地理位置分散的節(jié)點(diǎn)中。其中有些節(jié)點(diǎn)是移動(dòng)節(jié)點(diǎn)。若用一個(gè)中心節(jié)點(diǎn)來(lái)探測(cè)基本事件，形成最后的復(fù)合事件表達(dá)式，那么這個(gè)節(jié)點(diǎn)將成為事件探測(cè)的瓶頸。本文提出一種分布式、移動(dòng)數(shù)據(jù)庫(kù)系統(tǒng)中事件探測(cè)的體系結(jié)構(gòu)。這種體系結(jié)構(gòu)將探測(cè)器CED配置在多個(gè)節(jié)點(diǎn)中，相互合作，共同構(gòu)成復(fù)合事件表達(dá)式。其探測(cè)器的分布如圖1所示。

這樣配置CED有兩個(gè)優(yōu)點(diǎn)：①CED盡可能接近事件源，減少因傳送事件而產(chǎn)生的帶寬消耗；②盡可能利用局域網(wǎng)的高帶寬構(gòu)成復(fù)合事件，則利用低帶寬遠(yuǎn)程傳送的事件減少?？傮w來(lái)說(shuō)，進(jìn)一步減少了帶寬的消耗。

2傳統(tǒng)事件檢測(cè)方式

在主動(dòng)規(guī)則中，復(fù)合事件檢測(cè)通常有以下幾種方式：

(1)基于事件樹(shù)的事件檢測(cè)。GEM系統(tǒng)[9]為基于樹(shù)的檢測(cè)方式。檢測(cè)方式的基本思想是由復(fù)合事件表達(dá)式構(gòu)造出相應(yīng)的匹配樹(shù)；在匹配樹(shù)中，葉子節(jié)點(diǎn)表示基本事件，內(nèi)部節(jié)點(diǎn)表示復(fù)合事件表達(dá)式；當(dāng)葉子節(jié)點(diǎn)所關(guān)聯(lián)的事件被檢測(cè)到時(shí)計(jì)算復(fù)合事件表達(dá)式，如果滿足，則產(chǎn)生新的復(fù)合事件。

(2)基于圖的檢測(cè)方法。它類似于基于樹(shù)的方式，在Snoop[10]中采用基于圖的檢測(cè)方式來(lái)實(shí)現(xiàn)復(fù)合事件的檢測(cè)。其檢測(cè)思想是對(duì)于每個(gè)復(fù)合事件模式構(gòu)造相應(yīng)的事件圖，葉子節(jié)點(diǎn)為原子事件，非葉子節(jié)點(diǎn)為操作節(jié)點(diǎn)；事件發(fā)生由底層節(jié)點(diǎn)向上流向它們的父節(jié)點(diǎn)，依此類推，檢測(cè)到盡可能多的復(fù)合事件。

(3)基于自動(dòng)機(jī)的事件檢測(cè)。在ODE對(duì)象數(shù)據(jù)庫(kù)中[13]，不帶參數(shù)的復(fù)合事件表達(dá)式類似于正則表達(dá)式，這樣可以用有限狀態(tài)自動(dòng)機(jī)建立復(fù)合事件模型。自動(dòng)機(jī)包含有限的狀態(tài)和遷移，每個(gè)狀態(tài)均對(duì)應(yīng)一個(gè)事件輸入域，在一個(gè)給定的狀態(tài)中，自動(dòng)機(jī)只處理在其事件輸入域中的事件。每個(gè)遷移均對(duì)應(yīng)一個(gè)事件域，這個(gè)事件域中的任何一個(gè)事件都可以使遷移發(fā)生。狀態(tài)又分為普通的和生成的兩種類型。普通狀態(tài)是生成事件的中間狀態(tài)，生成狀態(tài)導(dǎo)致一個(gè)新的事件被檢測(cè)到。

ODE數(shù)據(jù)庫(kù)中使用的有限狀態(tài)自動(dòng)機(jī)表示事件，能直觀地表達(dá)現(xiàn)實(shí)中的事件，建立自動(dòng)機(jī)并據(jù)此檢測(cè)事件。但是純粹的自動(dòng)機(jī)不檢測(cè)帶參數(shù)的事件，不能表示事件的時(shí)序關(guān)系，不能檢測(cè)并發(fā)事件，這不符合分布式系統(tǒng)的需求。Snoop只提供簡(jiǎn)單的時(shí)間模型，把事件看做一個(gè)確定的時(shí)間點(diǎn)，原子事件根據(jù)定義來(lái)確定時(shí)間點(diǎn)，而復(fù)合事件的時(shí)間則根據(jù)其語(yǔ)義來(lái)定義時(shí)間點(diǎn)，這比較適合應(yīng)用于集中式系統(tǒng)或局域網(wǎng)。GEM考慮了事件發(fā)生與檢測(cè)之間的延遲，并通過(guò)指定最大能容忍的延遲來(lái)處理事件檢測(cè)的失序。但它假定了存在一個(gè)良好的全局同步時(shí)鐘，這不適合于沒(méi)有集中管理以及存在時(shí)鐘漂移的大規(guī)模松耦合的分布式系統(tǒng)。由于沒(méi)有考慮不可預(yù)知的延遲，不能有效進(jìn)行移動(dòng)數(shù)據(jù)庫(kù)中的斷接檢測(cè)和移動(dòng)檢測(cè)。

3移動(dòng)數(shù)據(jù)庫(kù)中采用擴(kuò)展的基于Petri網(wǎng)的事件檢測(cè)方式

3．1復(fù)合事件的CCPN模型

（4）依次下去，直到到達(dá)一個(gè)表示此事件模型且沒(méi)有向外的遷移庫(kù)所，則檢測(cè)成功。

CCPN不僅能夠很直觀地表達(dá)復(fù)合事件，還能表達(dá)事件的規(guī)則。基本事件對(duì)應(yīng)于Petri網(wǎng)的模型如圖2所示，其他事件都可以由此推導(dǎo)出來(lái)。

在移動(dòng)數(shù)據(jù)庫(kù)中使用CCPN建模事件，有著其他方式所沒(méi)有的優(yōu)點(diǎn)：

（1）通過(guò)復(fù)制庫(kù)所可以實(shí)現(xiàn)一個(gè)事件的多次復(fù)用，減少了事件冗余。

（2）由圖2所示的符號(hào)來(lái)表示同時(shí)發(fā)生的事件、相繼發(fā)生的事件等，可以實(shí)現(xiàn)異步并發(fā)事件的檢測(cè)。

（3）用令牌表達(dá)事件，并通過(guò)Petri網(wǎng)傳遞參數(shù)，可以表達(dá)事件的時(shí)序關(guān)系。

（4）由幾個(gè)基本事件構(gòu)成的一個(gè)簡(jiǎn)單復(fù)合事件又可構(gòu)成更復(fù)雜的復(fù)合事件，因此可用一個(gè)庫(kù)所表示一個(gè)復(fù)合事件來(lái)構(gòu)成更復(fù)雜的復(fù)合事件，簡(jiǎn)化了事件的Petri網(wǎng)模型。

4對(duì)失序事件的檢測(cè)

事件發(fā)生的時(shí)刻及事件之間發(fā)生的先后關(guān)系，表明了大量的基本事件是如何構(gòu)成相關(guān)的復(fù)合事件的，因此基于時(shí)序事件的事件檢測(cè)要求各節(jié)點(diǎn)的時(shí)鐘同步。而移動(dòng)數(shù)據(jù)庫(kù)系統(tǒng)中，沒(méi)有集中統(tǒng)一的管理。節(jié)點(diǎn)之間松散耦合，各節(jié)點(diǎn)的時(shí)鐘偏頻和漂移會(huì)造成節(jié)點(diǎn)間的時(shí)鐘不同步，節(jié)點(diǎn)移動(dòng)與不穩(wěn)定連接使事件發(fā)生到事件檢測(cè)之間產(chǎn)生不可預(yù)測(cè)的延遲，這些情況會(huì)造成事件檢測(cè)失序。為了避免這種事件檢測(cè)錯(cuò)誤，下面討論如何在移動(dòng)數(shù)據(jù)庫(kù)中處理失序事件的檢測(cè)。

4．1時(shí)鐘同步

只有各節(jié)點(diǎn)的時(shí)鐘同步，才能得到事件的準(zhǔn)確時(shí)戳，因而時(shí)鐘同步是解決事件失序的基礎(chǔ)。

本系統(tǒng)采用NTP（Network Time Protocol）將大規(guī)模分布式固定網(wǎng)絡(luò)劃分為多個(gè)網(wǎng)段。在每個(gè)網(wǎng)段內(nèi)部，設(shè)置時(shí)間服務(wù)器節(jié)點(diǎn)，時(shí)間按服務(wù)器[15，16]的等級(jí)Stratum傳播。Stratum－1在頂層，由外部UTC （Universal Time Coordinated）接入，而Stratum－2則從Stratum－1獲取時(shí)間，Stratum－3從Stratum－2獲取時(shí)間，依此類推。按照離外部UTC源的遠(yuǎn)近將所有服務(wù)器歸入不同的Stratum中，所有這些服務(wù)器在邏輯上形成階梯式的架構(gòu)。Stratum－1的時(shí)間服務(wù)器是整個(gè)系統(tǒng)的基礎(chǔ)，每個(gè)無(wú)線信號(hào)覆蓋網(wǎng)絡(luò)中的移動(dòng)主機(jī)MH是該層次結(jié)構(gòu)的最底層，移動(dòng)主機(jī)的時(shí)鐘通過(guò)軟件同步方法與其上層——移動(dòng)支持節(jié)點(diǎn)MSS同步。這樣無(wú)論原子事件還是復(fù)合事件都會(huì)被指派一個(gè)同步的時(shí)戳，并用偏序關(guān)系“”表示一個(gè)事件確切發(fā)生在另一個(gè)事件之前，以及全序關(guān)系“π”表示時(shí)間間隔交疊的情況。這樣就可把事件看做是良序序列，用于檢測(cè)。

4．2時(shí)間窗口

當(dāng)移動(dòng)主機(jī)從一個(gè)無(wú)線網(wǎng)絡(luò)移動(dòng)到另一個(gè)無(wú)線網(wǎng)絡(luò)，或連接狀態(tài)在連接與斷接之間交替時(shí)，事件發(fā)生與檢測(cè)之間有一個(gè)不可預(yù)測(cè)的延遲，會(huì)導(dǎo)致檢測(cè)到的事件失序。為此引入時(shí)間窗口。

時(shí)間窗口表示事件存儲(chǔ)在事件序列中的時(shí)間，超過(guò)這個(gè)時(shí)間，此事件的記錄則會(huì)被拋棄。它表示一個(gè)時(shí)間范圍，有三個(gè)參數(shù)，即窗口的起始時(shí)間TWB、終止時(shí)間TWE和窗口的大小TWL。其中，TWE=TWB+TWL。

時(shí)間窗口的大小可由系統(tǒng)默認(rèn)或程序員來(lái)指定。前者是靜態(tài)不變的，不能隨著網(wǎng)絡(luò)傳輸情況的變化而改變；后者可以通過(guò)一定的算法動(dòng)態(tài)設(shè)置窗口。窗口設(shè)置過(guò)大，會(huì)在事件隊(duì)列中存儲(chǔ)過(guò)多失效事件；過(guò)小，會(huì)使許多復(fù)合事件檢測(cè)不到。本文利用軟件時(shí)鐘同步方法，在每個(gè)同步周期，MSS向MH廣播一定數(shù)目的、帶有自己時(shí)間戳的消息包，動(dòng)態(tài)計(jì)算時(shí)間窗口。假定連續(xù)的網(wǎng)絡(luò)同步消息包的網(wǎng)絡(luò)延遲是統(tǒng)計(jì)獨(dú)立的，設(shè)某一MH收到n個(gè)MSS的消息包，則時(shí)間窗口設(shè)置為



5移動(dòng)檢測(cè)和斷接檢測(cè)

移動(dòng)檢測(cè)或斷接檢測(cè)是指MH在移動(dòng)過(guò)程中或發(fā)生斷接的情況時(shí)如何檢測(cè)其事件的發(fā)生。移動(dòng)檢測(cè)方法或斷接檢測(cè)方法是將移動(dòng)或斷接發(fā)生后所產(chǎn)生的事件傳送至MH原來(lái)所處的Cell中，并與先前發(fā)生的事件復(fù)合。

6結(jié)束語(yǔ)

本文討論了移動(dòng)數(shù)據(jù)庫(kù)中基于Petri網(wǎng)的事件檢測(cè)方式，以及在移動(dòng)條件下特殊的檢測(cè)技術(shù)。事件檢測(cè)是實(shí)現(xiàn)主動(dòng)功能中最重要的一步，進(jìn)一步的工作是要對(duì)移動(dòng)數(shù)據(jù)庫(kù)規(guī)則的條件給予評(píng)價(jià)，并執(zhí)行產(chǎn)生的不同于傳統(tǒng)數(shù)據(jù)庫(kù)的觸發(fā)事務(wù)。

參考文獻(xiàn)：

[1]PHATAK S H， NATH B. Transaction－centric reconciliation in disconnected client－server databases[J]. Mobile Networks and Applications， 2004，9(5):459－471.

[2]KIN W. Modern database system[M]. New York: ACM Press， 1995:435－455.

[3]KUMAR V， PRABHU N， DUNHAM M H. TCOT: a timeout－based mobile transaction commitment protocol[J]. IEEE Transactions on Computers， 2002，5(10):1212－1218.

[4]PATON N W， DIAZ O. Active database systems[J]. ACM Computing Surveys， 1999，31(1):64－102.

[5]WIDOM J， FINKELSTEIN S J. Set－oriented production rules in relational database system: proc.of the ACM SIGMOD International Conference on Management of Data[C].New York: ACM Press， 1990:254－265.

[6]GALTON A， AUGUSTO J C. Two approaches to event definition: Lecture Noets in Computer Science vol 2453[C].France:[s.n.]， 2002:547－556.

[7]HULL R， JACOBS D. Language constructs for programming active database: proc.of the 17th Int.Conf.on VLDB[C].San Francisco: Morgan Kaufmann Publishers Inc.， 1991:455－467.

[8]GATZIU S， DITTRICH K R. SAMOS: an active object－oriented database system[J]. IEEE Quarterly Bulletin on Data Engineering: Special Issue on Active Databases， 1992，15(124):23－26.

[9]SAMANI M， SLOMAN M， GEN M. A generalised event monitoring language for distributed systems[J]. IEE / IOP/BCS Distributed Systems Engineering， 1997，4(2):96－108.

[10]CHAKRAVARTHY S， RASAD V K， ANWAR E， et al. Anatomy of a composite event detector， Technical Report UF－CIS－TR－93－039[R]. Gainesville: University of Florida， 1993.

[11]PIETZUCH P R， SHAND B， BACON J. A framework for event composition in distributed systems: proc.of the 4th ACM/IFIP/USENIX International Conference on Middleware，LNCS 2672[C].Brazil:[s.n.]， 2003:62－82.

[12]楊進(jìn)才，胡學(xué)萱，胡金柱.移動(dòng)數(shù)據(jù)庫(kù)中的事件及描述:2005中國(guó)計(jì)算機(jī)大會(huì)論文集[C].北京:清華大學(xué)出版社，2005.

[13]GEHANI N H， JAGADISH H V， SHMUELI O. Event specification in an active object－oriented database: proc.of the ACM SIGMOD International Conference on Management of Data[C].New York: ACM Press， 1992:81－90.

[14]AL－SHAER E， ABDEL－WAHAB H M， Maly K. HiFi: a new monitoring architecture for distributed systems management: proc.of International Conference on Distributed Computing Systems[C].1999.

[15]JUN Su－nmi， YU Dong－h(huán)ui， KIM Y H， et al. A time synchronization method for NTP: proc.of the 16th Int. Conf. on RTCSA[C].Hong Kong:[s.n.]， 1999:466－473.

[16]GUREWITZ O， CIDON I， SIDI M. Network time synchronization using clock offset optimization: proc.of the 11th IEEE International Conference on Network Protocols[C].Atlanta:[s.n.]， 2003:212－221.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文”