我的雲端生活網 - Life+

Thursday, July 9, 2009

分散式系統的複雜事件處理

David C. Luckham 和 Brian Frasca 在 1998 年 Complex Event Processing in Distributed Systems 文章中提出在分散式系統處理複雜事件的方法。分散式系統意味了在許多機器之間有大量的訊息交換。而複雜事件意味了在許多基礎事件之上,要藉由許多額外的知識才能取得的高層次事件,或是抽象事件。

基本層次的訊息、事件系統存在著一些問題。第一是要由網路上許多線路來偵測事件的發生;第二是代表事件發生的訊息量非常大;第三是為了製作事件的產生與偵測,通常在建立系統時將事件模型固定在系統中,使事件的偵測與使用變得比較不彈性。而系統中許多事件的發生可能造成系統的卡死或「當機」;無法準確判斷系統事件的類型,是大問題。為了處理這些問題,他們使用多層次事件觀點來處理事件的抽象化。基本上是將系統的活動分解再分解。

系統事件的層次分解,以生產線為例,可分為下層是通訊層、以及上層是工作流層。通訊層處理基本的通訊工作,包括廣播訊息、分派訊息、接收訊息、控制訊息等等。而生產線工作流層次,則需要若干事件有:產生大量訊息、載入大量訊息、消化大量訊息等等。「載入大量訊息」是一項虛擬事件,是由廣播訊息、分派訊息、接收訊息、和接受訊息等基礎事件組合成的。

在以訊息為本的分散式系統中,對於大量訊息,需要有過濾和映射的功能。過濾是指從儲存的事件中找到符合某個複雜事件組合樣式的一組事件。映射是指把一組事件當做輸入而產生另一些事件當做結果。於是,系統的抽象事件階層由下往上有下列構成:
  1. 分散式系統軟硬體裝置。
  2. 基本事件層。
  3. 過濾事件層:從基本事件層或過濾事件層,取出符合複雜事件樣式的抽象事件。
  4. 映射事件層:從過濾事件層取出符合複雜事件樣式的抽象事件。
實作上需要處理一些項目:
  1. 因果事件。
  2. 事件過濾和映射的演算法。
  3. 由抽象層反推,解決基本層發生的錯誤。
他們的實作,用有向圖表達事件的因果網路,以各種事件為節點、而因果關係為箭頭線。我個人感覺,本文談當事件的過濾和映射處理方面,相當有 partial evaluation 的概念,或許相當適合以函數式語言實作。

Tuesday, July 7, 2009

用 RFID 建立物際網路

曾有物品放在某處忘了帶走的經驗嗎?如果在物品和你身上貼了 RFID 標籤,在你離開大樓時, RFID 網路會傳送 SMS 訊息提醒你有物品忘了帶走。 Evan Welbourne 等人 2009 年在 Building the Internet of Things Using RFID: The RFID Ecosystem Experience 文章,介紹他們已經在校園實作的 RFID 環境和根據 RFID 事件為基礎的應用服務。

環境

在華盛頓大學電機學院建物區域中,他們在門和走廊安裝了 44 個讀寫機。並提供 RFID kiosk 服務站,徵請自願者自行取用 RFID 標籤,貼在他們的物件上;而且讓這些自願者在穿著上貼了 RFID 標籤。

他們的系統著重在,將讀寫機讀取的低層次訊息轉換為高層次有意義的資訊。讀寫機直接讀到的訊息不外乎 (tag ID, antenna ID, time) 這一組資料。但人們需要的資訊是,哪一批低層次的資料可以有個合理及有意義的解釋。他們開發了三種工具來協助轉換低層次資料。 Tag Manager 提供使用者將標籤和貼附標籤的物件的對應關係編寫到系統中。 Place Manager 提供使用者為每一支天線命名,指派為有意義的地名。 Scenic Event Editor 提供使用者指定要從低層次資料抽取出的高層次資訊;使用到一種劇本式圖型語言。

他們又開發了 Physical Access Control ,讓使用者能調整標籤讀取的方針,藉以供安全和隱私的控制。

應用服務

由以上的環境架構,他們能夠實作多種 RFID-based 應用程式。 Search Engine for Things 藉由查詢一件物品最近的讀取記錄,找到物品的位置。 Rfidder 提供社交應用程式的功能,將即時更新的人地資訊加到社交網路中,並與 Twitter 連繫。 Personal Trends 提供使用者瀏覽他的物品使用趨勢:例如,哪些時候多帶著安全帽進辦公室,表示他騎車上班的次數多瀕繁。 Event-Based Desktop Search 是在 Google Desktop Search 中做的外掛程式,根據 RFID 事件紀錄查尋物品或地點:例如,可查詢上次和某一位人士會面的地點。

未處理問題

建立物際網路,意味了會大量讀取許多 RFID 事件,對系統承載力有所負擔。接下來面臨的問題是,要如何解決事件讀取的密度。另一個問題是要解決 RFID 事件的低讀取率。

相關文章

Cascadia: A System for Specifying, Detecting, and Managing RFID Events

Monday, July 6, 2009

如何在一台機器同時開啟兩個以上的msnv9.0

修改Windows的登錄碼
HKEY_LOCAL_MACHINE\SOFTWARE\Microsoft\Windows Live\Messenger
如果沒有 MultipleInstances,可自行新增一個,MultipleInstances 將 數值資料(DWORD 32-位元)改為1

Friday, July 3, 2009

事件處理詞表

David C. Luckham 在 Complex Event Processing 社群網站發佈一份按照邏輯順序編排的事件處理詞表。許多有關 event processing 的研究,例如, Hu等人於 2008 年 Complex Event Processing in RFID Middleware: A Three Layer Perspective 文章,用語大都參考這一份詞表。

摘錄

事件:任何已發生或打算要發生的事。

事件物件:用來表達事件的結構:例如訂單是事件物件,用來表達訂購事件。

虛擬事件:未實際發生,但需要用來象徵實際事件的事件;多半來自想像或模擬。

事件類型:事件物件的種類。

事件時間:屬於事件的時間值。

時間間隔:由二個事件時間所限定的一段時間;二個事件時間是指時間間隔的開始時間和結束時間。

即時事件:事件的時間間隔小於單位時間;也就是說,事件的開始時間和結束時間是同一個。

抽象事件:用來為一組事件做摘要、做註解的事件。

複雜事件:是一個抽象事件,所摘要、解釋的事件對象是它的成員。

衍生事件:被產生而做為一項結果,要再對其他事件做處理,的事件。

複合事件:是複雜事件,也是衍生事件,是用到如事件的分離、結合、順序等等運算方法將基本事件結合而成的事件。複合事件自然包含了從所衍生的基本事件。

Thursday, July 2, 2009

RFID中介軟體如何處理複雜的事件?

Hu等人於 2008 年 Complex Event Processing in RFID Middleware: A Three Layer Perspective 文章裏提到:現在已經有一些中介軟體處理 RFID 事件的過濾和匯總等功能,例如有 BEA 、 Sun 、 Singularity 和 Logicalloy 等公司的產品;不過,作者們注意到 EPCglobal Network 的架構,在 Application Level Events 和 EPC Information Service 之間有一個叫做 EPC Capture Application 的層次。他們說,在 EPC Capture Application 層次, RFID 中介軟體應該運作一些複雜的功能,為了處理特定的商務流程而處理較複雜的 RFID 事件。

架構分為三個層次,由下層到上層依序為:
  1. 邏輯結構: RFID 事件源自讀寫機探測到的基本事件,而複雜的事件是由一些基本事件組成,或者,複雜事件也可以由另外一些複雜事件組成。
  2. 時間限制:在複雜事件結構中,可以加上時間限制的屬性。
  3. 事件偵測:應用前二層的產物,藉由複雜事件分析,向上回報究竟發生了哪些事件類型。

這篇文章對事件結構做了初步的正規描述,並使用 Petri Net 為處理工具。對第一層,邏輯結構方面,使用 Petri Net 延伸的模型 Composite Event Structure-layer Net 。對時間限制層面,使用 structured token and transition mark 處理。對事件偵測層面,使用 Petri Net 著色方法處理;但是本文尚未討論到 Petri Net 著色方法的細節。

邏輯結構

每一個基本事件,按照 EPCglobal 的說法,是讀寫機探測並回報在什麼時候「看見」了哪個 tag 。用大寫字母 A, B, ... 表示每一個基本事件的類型。於是,用到以下六項運算,可以處理許多基本事件之間的各種基本邏輯關係:
  1. 彙總: (A, n) 表示進來 n 個 A 事件。
  2. 分離: (A | B) 表示進來的事件是 A 或 B 。
  3. 結合: (A & B) 表示 A 和 B 二事件都進來。
  4. 否定: (~ A) 表示 A 事件沒有進來。
  5. 順序: (A; B, t) 表示依序有 A 和 B 二事件,而且二事件的間距在 t 時間區段之內。
  6. 內在: Within(A, t) 表示 A 事件在 t 時間區間之內進來。

事件的間距定義是,對事件 e 有一對參數 [Start e, End e] ,表示事件發生的時間和結束的時間。事件 e 自己發生的時間長度是 (Start e - End e) 。二事件 A, B 有 (A; B, t) 順序,代表:
(A & B) [0 < Start A - End B < t]
即為 A, B 二事件除了同時發生之外,加上 A, B 的時間有些差距。

而事件 A 在 t 時間之內發生, Within(A, t) ,可以改寫成:
(A, 1)[Start A - End A > t]
(註:以上二式都是文章中的原文照列,不過看起來有一些矛盾的疑問。)
即為發生了一件 A 事件,並且此事件持續了有 t 時間區段那麼久。

所以,事件的順序關係是結合關係的特例,而內在關係是彙總關係的特例。

以上所指六項運算符號,扣除二項特例,可以有四種 Petri Net 圖型表達彙總、分離、結合、以及否定等關係。

時間限制

對一個事件 e ,將它對應事件類型的集合表示為 S e 。則加上時間限制的結構是一個三元詞組 (Start e, End e, S e) :例如,進來一個事件 (epc, r, t) ,則做出一個 token 為 (t, t, {(epc, r, t)}) 。
(註:此例中 (epc, r, t) 也有些疑問,在此也暫以原文照列。)
做成這樣的 token 是為了使 Petri Net 中 Guard 位置計算比較方便。

其他人的相關作品

Siemens RFID 中介軟體使用宣告式的語言,可撰寫規則,用到邏輯和時間限制的運算語法。事件偵測以圖論為基礎。

SAMOS 以 Colored Petri Net 做事件偵測的機制。

Esper 是一件開源軟體,處理複雜事件和事件串流的架構。用到類似 SQL 的語言表達複雜事件,並使用自動狀態機做事件偵測。

Wednesday, July 1, 2009

ALE 相容資料處理

為了跟隨 EPCglobal 組織制定的 Application Level Event 標準, Byun 等人在 Data Stream Processing Based on ALE-Compliant RFID Middleware 文章裏提出一項有效的資料處理法。由於每一台讀寫機有不同的製造商及協定,他們將讀寫器歸類、整理在一些 master node 下,先由讀寫器讀到資料並送給 master node ,再讓 master node 將原資料轉換成 EPC 和 URN 。這樣的處理有幾項好處:適合 ALE 的規定,整合各種不同類型的讀寫器,並且不只適用於 RFID 讀寫器、也適用於其他 sensor network 。

例如,感應器分四種類型:
  1. 水量感應器: A 廠製造,感應電導率、水溫、氯含量、酸度和渾度。
  2. 水位感應器: B 廠製造,感應水位。
  3. 水質感應器: C 廠製造,感應瞬時水質、累積水質、瞬間水速、累積時間。
  4. 雷擊感應器: D 廠製造,感應雷擊並產生警訊。

不同的感應器有不同的協定,以水位感應器來說,只有一個水位值;而水質感應器必須提供四個值。對於不同數目的資料,本文以下列資料格式表達資料部份:
開頭記號、全長、 master node 代碼、 sensor 代碼、命令、資料、檢查碼、尾端記號。
假設 master node 代碼是 0x0B , sensor 代碼是 0x02 ,命令是 "send" 、代碼是 43 ,而資料是 10 02 83 84 01 00 01 01 00 00 00 58 6F BD 3F F9 02 15 D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 BE 8B 10 ,檢查碼是 03 6B ,資料開頭記號是 02 ,尾端記號是 03 ,則合起來的資料為:

02 29 0B 02 43 10 02 83 84 01 00 01 01 00 00 00 58 6F BD 3F F9 02 15 D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 BE 8B 10 03 6B 03

以上資料是感測器送到 master node 的資料。

Master node 要將由原資料加上標頭,並轉換為 EPC 和 URN ,符合 EPCglobal 的規定。 EPC 標頭欄位基本上是對應於感應器的製造商和機器類型等資訊的數字,假設水位感應器標頭是 36000002 ,水質感應器標頭是 36000003 。 EPC 的資料欄位是從原資料取出資料欄位,例如對水位資料,取出水位欄的值;對水質資料,取出四個欄位的值。

由前例,從水位感應器送來資料為 02 29 0B 02 43 10 02 83 84 01 00 01 01 00 00 00 58 6F BD 3F F9 02 15 D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 BE 8B 10 03 6B 03 ,加上標頭成為 EPC 是 36 00 00 02 10 02 83 84 01 00 01 01 00 00 00 58 6F BD 3F F9 02 15 D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 BE 8B 10 。

再使用前例,假設是從水質感應器送來的資料,並且 master node 想要傳送有關第三欄位的資訊。假設第三欄位值是 58 6F BD 3F F9 02 15 D0 ,則應取出第三欄位的值,加上標頭,得 EPC 是 36 00 00 03 58 6F BD 3F F9 02 15 D0 。

水位感應器的 URN 格式為:
urn:sensor:com:waterlevel:[值]
欄位 "com" 是製造商公司。

水質感應器有四個欄位, URN 格式為:
urn:sensor:com:waterflux:[值 1].[值 2].[值 3].[值 4]
用 "." 做間隔,區分各欄位值。

按照前二例,水量感應的 EPC 是 36 00 00 02 10 02 83 84 01 00 01 01 00 00 00 58 6F BD 3F F9 02 15 D0 00 00 00 00 00 00 00 00 00 00 00 00 00 00 BE 8B 10 , URN 是 urn:sensor:b:waterlevel:586FBD3FF90215D0。假設水質感應的 EPC 是 36 00 00 03 20 20 20 20 30 2E 30 20 6D 33 2F 68 20 20 31 34 39 37 35 37 2E 35 32 20 6D 33 20 20 30 2E 30 30 30 20 6D 2F 73 20 37 35 39 33 3A 33 30 00 0 , URN 是 urn:sensor:c:waterflux:20202020302E30206D332F68.20203134393735372E3532206D33.2020302E303030206D2F73.20373539333A3330000 。

Blog Archive