移動數據庫中的事件檢測

摘要：為了有效檢測移動計算環境中的事件，提出了基于Petri網的事件檢測方式CCPN。該方式能直觀靈活地建模事件，支持異步并發事件的檢測以及時序事件的檢測；討論了主機斷接以及移動情況下的事件檢測。

關鍵詞：移動數據庫； 事件檢測； 帶條中的彩色Petri網； 失序事件檢測； 斷接檢測； 移動檢測

中圖分類號：TP311文獻標志碼：A

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

移動數據庫管理系統（MDBMS）是在移動計算環境中進行數據管理的數據庫系統，是傳統分布式DBMS的擴展，可以被看做是客戶端與固定服務器節點動態連接的分布式系統。因此，移動數據庫管理系統還需要考慮諸多傳統計算環境下不需要考慮的問題，包括如何適應變化的網絡環境、對斷接操作的支持、對跨區長事務的支持、對位置相關查詢的支持、對查詢優化的特殊考慮，以及對提高有限資源利用率和對系統效率的考慮等[1~3]。

在移動數據庫中引入主動機制[4，5]，用事件做觸發器，能有效支持斷接操作以及網絡環境變化的數據處理。基于事件的規則觸發機制能實現相關的主動功能，因此事件的檢測是很重要的。在移動計算環境中，基本事件的數量是巨大的，構成復合事件的不同基本事件之間的關系是復雜的。要高效地檢測事件，就要根據移動計算環境的特點和系統要求選擇合適的檢測方法。傳統的主動數據庫給出了集中式或分布式系統的豐富的事件定義與描述[6，7]，考慮了事件的多種檢測方式[8~11]，但是它們沒有考慮移動計算環境下事件的特點以及檢測方法的特殊要求。

1移動數據庫中的事件檢測

移動數據庫中，大量的事件分布在不同節點上，產生的事件具有分布、并發、異步、隨機、不確定的特點；事件源通常是移動主機，事件的到達因網絡連接的不穩定以及移動主機的移動而發生時延、失序的情況。本文提出的檢測方法應該能夠高效地進行分布式檢測、并發異步事件的檢測、失序事件的檢測以及斷接檢測、移動檢測。在移動計算環境中，事件分布在地理位置分散的節點中。其中有些節點是移動節點。若用一個中心節點來探測基本事件，形成最后的復合事件表達式，那么這個節點將成為事件探測的瓶頸。本文提出一種分布式、移動數據庫系統中事件探測的體系結構。這種體系結構將探測器CED配置在多個節點中，相互合作，共同構成復合事件表達式。其探測器的分布如圖1所示。

這樣配置CED有兩個優點：①CED盡可能接近事件源，減少因傳送事件而產生的帶寬消耗；②盡可能利用局域網的高帶寬構成復合事件，則利用低帶寬遠程傳送的事件減少。總體來說，進一步減少了帶寬的消耗。

2傳統事件檢測方式

在主動規則中，復合事件檢測通常有以下幾種方式：

(1)基于事件樹的事件檢測。GEM系統[9]為基于樹的檢測方式。檢測方式的基本思想是由復合事件表達式構造出相應的匹配樹；在匹配樹中，葉子節點表示基本事件，內部節點表示復合事件表達式；當葉子節點所關聯的事件被檢測到時計算復合事件表達式，如果滿足，則產生新的復合事件。

(2)基于圖的檢測方法。它類似于基于樹的方式，在Snoop[10]中采用基于圖的檢測方式來實現復合事件的檢測。其檢測思想是對于每個復合事件模式構造相應的事件圖，葉子節點為原子事件，非葉子節點為操作節點；事件發生由底層節點向上流向它們的父節點，依此類推，檢測到盡可能多的復合事件。

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

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

3移動數據庫中采用擴展的基于Petri網的事件檢測方式

3．1復合事件的CCPN模型

（4）依次下去，直到到達一個表示此事件模型且沒有向外的遷移庫所，則檢測成功。

CCPN不僅能夠很直觀地表達復合事件，還能表達事件的規則。基本事件對應于Petri網的模型如圖2所示，其他事件都可以由此推導出來。

在移動數據庫中使用CCPN建模事件，有著其他方式所沒有的優點：

（1）通過復制庫所可以實現一個事件的多次復用，減少了事件冗余。

（2）由圖2所示的符號來表示同時發生的事件、相繼發生的事件等，可以實現異步并發事件的檢測。

（3）用令牌表達事件，并通過Petri網傳遞參數，可以表達事件的時序關系。

（4）由幾個基本事件構成的一個簡單復合事件又可構成更復雜的復合事件，因此可用一個庫所表示一個復合事件來構成更復雜的復合事件，簡化了事件的Petri網模型。

4對失序事件的檢測

事件發生的時刻及事件之間發生的先后關系，表明了大量的基本事件是如何構成相關的復合事件的，因此基于時序事件的事件檢測要求各節點的時鐘同步。而移動數據庫系統中，沒有集中統一的管理。節點之間松散耦合，各節點的時鐘偏頻和漂移會造成節點間的時鐘不同步，節點移動與不穩定連接使事件發生到事件檢測之間產生不可預測的延遲，這些情況會造成事件檢測失序。為了避免這種事件檢測錯誤，下面討論如何在移動數據庫中處理失序事件的檢測。

4．1時鐘同步

只有各節點的時鐘同步，才能得到事件的準確時戳，因而時鐘同步是解決事件失序的基礎。

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

4．2時間窗口

當移動主機從一個無線網絡移動到另一個無線網絡，或連接狀態在連接與斷接之間交替時，事件發生與檢測之間有一個不可預測的延遲，會導致檢測到的事件失序。為此引入時間窗口。

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

時間窗口的大小可由系統默認或程序員來指定。前者是靜態不變的，不能隨著網絡傳輸情況的變化而改變；后者可以通過一定的算法動態設置窗口。窗口設置過大，會在事件隊列中存儲過多失效事件；過小，會使許多復合事件檢測不到。本文利用軟件時鐘同步方法，在每個同步周期，MSS向MH廣播一定數目的、帶有自己時間戳的消息包，動態計算時間窗口。假定連續的網絡同步消息包的網絡延遲是統計獨立的，設某一MH收到n個MSS的消息包，則時間窗口設置為



5移動檢測和斷接檢測

移動檢測或斷接檢測是指MH在移動過程中或發生斷接的情況時如何檢測其事件的發生。移動檢測方法或斷接檢測方法是將移動或斷接發生后所產生的事件傳送至MH原來所處的Cell中，并與先前發生的事件復合。

6結束語

本文討論了移動數據庫中基于Petri網的事件檢測方式，以及在移動條件下特殊的檢測技術。事件檢測是實現主動功能中最重要的一步，進一步的工作是要對移動數據庫規則的條件給予評價，并執行產生的不同于傳統數據庫的觸發事務。

參考文獻：

[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]楊進才，胡學萱，胡金柱.移動數據庫中的事件及描述:2005中國計算機大會論文集[C].北京:清華大學出版社，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－hui， 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.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文”