李 強(qiáng)，陳 琳

（1.西北工業(yè)大學(xué) 軟件與微電子學(xué)院，陜西 西安710129；2.西北工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，陜西 西安710129）

0 引 言

RFID作為一種先進(jìn)的自動(dòng)識(shí)別技術(shù)已經(jīng)廣泛應(yīng)用于諸如供應(yīng)鏈管理、產(chǎn)品流水線跟蹤、物品監(jiān)管、醫(yī)療監(jiān)控等領(lǐng)域。復(fù)雜事件處理［1］（complex event processing，CEP）是RFID的重要應(yīng)用，主要是通過(guò)將簡(jiǎn)單事件進(jìn)行關(guān)聯(lián)，得到語(yǔ)義更復(fù)雜的事件?，F(xiàn)有的RFID復(fù)雜事件處理假設(shè)數(shù)據(jù)是準(zhǔn)確的。實(shí)際上，由于讀寫(xiě)器本身和環(huán)境的影響，RFID數(shù)據(jù)流往往是不準(zhǔn)確的。不準(zhǔn)確的RFID數(shù)據(jù)流主要有下面3種情形：

（1）重復(fù)讀。為了更好地覆蓋RFID應(yīng)用的讀寫(xiě)區(qū)域，往往在一個(gè)邏輯點(diǎn)安裝多個(gè)天線或多個(gè)讀寫(xiě)器。當(dāng)一個(gè)帶標(biāo)簽的對(duì)象經(jīng)過(guò)這個(gè)區(qū)域時(shí)將可能產(chǎn)生很多對(duì)事件檢測(cè)無(wú)用的、重復(fù)的RFID記錄。

（2）拒真。拒真是只讀取對(duì)象已經(jīng)在讀寫(xiě)器的讀寫(xiě)范圍，但由于某些原因 （如反射，干擾等）讀寫(xiě)器不能給出該物品的標(biāo)簽信息。這樣的信息丟失使得事件檢測(cè)不能正確地給出符合條件的復(fù)雜事件。

（3）納偽。納偽是只本不應(yīng)該在讀寫(xiě)器讀寫(xiě)范圍的物品由于某些原因 （如信號(hào)反射、讀寫(xiě)器的讀寫(xiě)范圍較大等）而被該讀寫(xiě)器讀到。納偽數(shù)據(jù)的產(chǎn)生使得事件檢測(cè)給出錯(cuò)誤的復(fù)雜事件。

對(duì)于RFID數(shù)據(jù)流中的這些不準(zhǔn)確信息，應(yīng)用往往是在中間件層對(duì)數(shù)據(jù)進(jìn)行清洗和平滑，去除重復(fù)、納偽的標(biāo)簽信息，并盡量將拒真數(shù)據(jù)補(bǔ)齊。由于RFID數(shù)據(jù)量的巨大，對(duì)于數(shù)據(jù)流進(jìn)行一場(chǎng)掃描進(jìn)行數(shù)據(jù)清洗后再一次進(jìn)行復(fù)雜事件處理的代價(jià)是很大的。再由于復(fù)雜事件處理的實(shí)時(shí)性要求［2］，在數(shù)據(jù)清洗后進(jìn)行事件檢測(cè)有可能使一些復(fù)雜事件失去意義。針對(duì)上述問(wèn)題，本文提出在原始數(shù)據(jù)流上直接進(jìn)行復(fù)雜事件處理的方法，利用事件間的各種約束，在一遍掃描數(shù)據(jù)流的基礎(chǔ)上對(duì)原始數(shù)據(jù)流進(jìn)行清洗，同時(shí)進(jìn)行事件檢測(cè)，實(shí)驗(yàn)結(jié)果表明，該算法的CPU和內(nèi)存耗費(fèi)明顯優(yōu)于經(jīng)過(guò)數(shù)據(jù)清洗后的算法，且算法的吞吐量和原算法相當(dāng)。

1 概念描述及相關(guān)工作

RFID原始數(shù)據(jù) （簡(jiǎn)單事件）是一個(gè)三元組： （RID，OID，time）。RID是讀寫(xiě)器的標(biāo)識(shí)，在應(yīng)用中為某邏輯點(diǎn)；OID是要識(shí)別的對(duì)象的標(biāo)識(shí)，這個(gè)標(biāo)識(shí)在全球是唯一的，且要遵循相關(guān)標(biāo)準(zhǔn)；time為讀寫(xiě)器讀取標(biāo)簽的時(shí)間。

復(fù)雜事件則是將原始事件通過(guò)一定的規(guī)則和實(shí)際應(yīng)用的邏輯關(guān)聯(lián)起來(lái)構(gòu)成的事件。復(fù)雜事件具有更豐富的語(yǔ)義，可以為上層應(yīng)用提供更多的信息。

復(fù)雜事件檢測(cè)早在主動(dòng)數(shù)據(jù)庫(kù)領(lǐng)域已經(jīng)進(jìn)行了廣泛研究［3］，但應(yīng)用于RFID數(shù)據(jù)流卻是最近幾年［4－6］，這些模型和方法中，假設(shè)處理的數(shù)據(jù)是經(jīng)過(guò)數(shù)據(jù)清洗，復(fù)雜事件處理引擎再處理這些數(shù)據(jù)。由于前期數(shù)據(jù)主要是去除重復(fù)［7］、納偽［8］事件，沒(méi)有結(jié)合到復(fù)雜事件查詢本身的語(yǔ)義和現(xiàn)實(shí)場(chǎng)景的信息。RFID應(yīng)用場(chǎng)景中，數(shù)據(jù)清洗往往是在前端數(shù)據(jù)采集上進(jìn)行。文獻(xiàn) ［9］提出了一種基于概率統(tǒng)計(jì)模型的數(shù)據(jù)清洗模型，通過(guò)事件的統(tǒng)計(jì)信息調(diào)整滑動(dòng)窗口的大小，來(lái)保證數(shù)據(jù)的完整性和動(dòng)態(tài)性。文獻(xiàn) ［10］提出了一種用SQL－TS來(lái)定義清洗規(guī)則清洗方法，但此方法假設(shè)RFID數(shù)據(jù)存儲(chǔ)于RMDB中，其操作均為離線，比如離線查詢與離線清洗，因此不能用于實(shí)時(shí)的復(fù)雜事件處理。

2 RFID數(shù)據(jù)清洗及復(fù)雜事件示例

RFID數(shù)據(jù)流中，簡(jiǎn)單事件序列可表示復(fù)雜事件，當(dāng)然須在合理的時(shí)間窗口內(nèi)。下面介紹經(jīng)典的SASE［11］算法：

SASE算法以其基于NFA的特點(diǎn)，在處理方法上面具有更大的靈活性，且可以對(duì)大數(shù)據(jù)量可實(shí)施優(yōu)化。在SASE算法中，一個(gè)查詢對(duì)應(yīng)一個(gè)自動(dòng)機(jī)，可將不同簡(jiǎn)單事件分散在不同自動(dòng)機(jī)中，狀態(tài)間遷移通過(guò)對(duì)象引用來(lái)完成［12］。當(dāng)NFA達(dá)到末態(tài)，可根據(jù)對(duì)象引用回溯輸出復(fù)雜事件。圖1是SASE方法示例。其中簡(jiǎn)單事件用小寫(xiě)字母表示，事件類(lèi)型用大寫(xiě)字母表示，小寫(xiě)字母的下標(biāo)表示簡(jiǎn)單事件的時(shí)間戳，如bi表示事件類(lèi)型為B且時(shí)間戳為i的簡(jiǎn)單事件。

下面使用一個(gè)最為常見(jiàn)的RFID應(yīng)用場(chǎng)景說(shuō)明RFID數(shù)據(jù)清洗及復(fù)雜事件處理過(guò)程。

在零售業(yè)中 （如沃爾瑪、麥德龍等），檢測(cè)一個(gè)物品被出售的過(guò)程可以用SASE語(yǔ)言描述為如下的事件查詢Q1：

EVENT SEQUENCE （SHELF＿READING shfr，

COUNTER＿READING corr，EXIT＿READING extr）

WHERE shfr.OID ＝corr.OID ＝extr.OID

WITHIN 1hour

圖1 SASE方法框架

這個(gè)查詢的意思是：一小時(shí)內(nèi)物品被先后 （SEQ定義）貨架上、結(jié)賬處和出口被讀寫(xiě)器讀到，則該物品通過(guò)了合法的零售邏輯。如果物品的標(biāo)簽信息只在貨架和出口處被讀到，而未在結(jié)賬處未被讀到，則要報(bào)警說(shuō)明物品可能被盜 （即非事件）。在這里物品在貨架、結(jié)賬處和出口被讀到的信息就是所謂的簡(jiǎn)單事件，而通過(guò)上面的語(yǔ)言檢測(cè)到的序列則是我們感興趣的復(fù)雜事件。SASE檢測(cè)上面的復(fù)雜事件的模型是NFA。

例如，當(dāng)前時(shí)間窗口的RFID數(shù)據(jù)流為：S1＝ （a1，1；a2，2；a1，3；a2，4；a1，5；b1，6；b1，7；c1，8；d2，9；b2，11；c2，12），其中Ei，j表示標(biāo)識(shí)為i的標(biāo)簽在j時(shí)刻被讀寫(xiě)器讀到，E為事件類(lèi)型。對(duì)于RFID數(shù)據(jù)流S1，有3個(gè)事件類(lèi)型，分別為A，B，C。a1，1表示編號(hào)為1的物品在時(shí)刻1被A處的讀寫(xiě)器讀到。數(shù)據(jù)流S1主要存在的不準(zhǔn)確性是重復(fù)讀和納偽的數(shù)據(jù)。對(duì)上S1進(jìn)行數(shù)據(jù)清洗，得到的數(shù)據(jù)流S′1＝ （a1，1；a2，2；b1，6；c1，8；b2，11；c2，12）。事件查詢 Q1在S′1上所得到的復(fù)雜事件為：（a1，1→b1，6→c1，8），（a2，2→b2，11→c2，12）。

3 集成數(shù)據(jù)清洗的事件檢測(cè)引擎

可以看到，這里的數(shù)據(jù)清洗去除了不確定的信息，但存在的問(wèn)題是：RFID數(shù)據(jù)流可能為很多應(yīng)用程序使用，每個(gè)應(yīng)用程序所提交的查詢是不一樣的，如有的是計(jì)算聚集，有的復(fù)雜事件處理，復(fù)雜事件處理的事件模式又可能不一樣。這就導(dǎo)致單一的數(shù)據(jù)清洗算法不適用多個(gè)RFID的應(yīng)用。且數(shù)據(jù)清洗和復(fù)雜事件處理分別要掃描一次數(shù)據(jù)流，這就加重了系統(tǒng)的資源的開(kāi)銷(xiāo)。我們?cè)O(shè)計(jì)了一個(gè)集成數(shù)據(jù)清洗的復(fù)雜事件檢測(cè)模型，其架構(gòu)如圖2所示。

“事件定義”模塊是用來(lái)定義用戶感興趣的模式，可使用如SASE或Cayuga等事件檢測(cè)語(yǔ)言描述，當(dāng)前我們主要針對(duì)的是SASE語(yǔ)言定義的查詢；“清洗邏輯解析器”則根據(jù)事件查詢模式和實(shí)際應(yīng)用的規(guī)則生成數(shù)據(jù)清洗的檢測(cè)規(guī)則，實(shí)際應(yīng)用規(guī)則是指將應(yīng)用場(chǎng)景抽象為一個(gè) （有向）圖的模型，根據(jù)物品在圖上點(diǎn)與點(diǎn)間移動(dòng)的統(tǒng)計(jì)信息得到一定的規(guī)則，將這些規(guī)則應(yīng)用于數(shù)據(jù)清洗和事件檢測(cè)。“事件檢測(cè)算法”里面集成了清洗規(guī)則和事件檢測(cè)模型，常見(jiàn)的模型有NFA，圖模型和Petri網(wǎng)，用戶也可以插入自己定義的算法，本文使用的是和SASE類(lèi)似的NFA模型。結(jié)合清洗規(guī)則事件檢測(cè)算法如算法1所示。

圖2 集成數(shù)據(jù)清洗的復(fù)雜事件檢測(cè)引擎架構(gòu)

算法1：結(jié)合清洗規(guī)則的事件檢測(cè)算法

輸入：原始RFID數(shù)據(jù)流，事件pattern，清洗規(guī)則，時(shí)間窗

輸出：復(fù)雜事件

（1）建立一個(gè)Hash－table，記錄原始事件的TagID和狀態(tài)；

（2）對(duì)pattern中的每個(gè)事件類(lèi)型，建一堆棧；

（3）對(duì)于每一個(gè)原始事件，通過(guò)哈希函數(shù)將其映射到Hash－table中對(duì)應(yīng)位置；如果該位置上有數(shù)據(jù)，且當(dāng)前狀態(tài)和新?tīng)顟B(tài)的交為pattern的字串，則更新?tīng)顟B(tài)。如果沒(méi)有狀態(tài)改變，則可知當(dāng)前數(shù)據(jù)為重復(fù)數(shù)據(jù)；如果狀態(tài)發(fā)生改變且不是pattern的字串，則可判斷當(dāng)前數(shù)據(jù)為false positive，丟棄；

（4）將pattern字串對(duì)應(yīng)的事件放入堆棧，更新前驅(qū)指針；

（5）當(dāng)Hash－table狀態(tài)達(dá)到終態(tài)時(shí) （滿足查詢），當(dāng)前事件通過(guò)TagID搜索對(duì)應(yīng)的堆棧前向指針將復(fù)雜事件輸出；

（6）清空已輸出事件對(duì)應(yīng)的?？臻g和 Hash－table；／／可以使用批處理的刪除方法避免內(nèi)存抖動(dòng)

（7）重復(fù)步驟 （3）－（6），直至整個(gè)窗口的數(shù)據(jù)被處理完。

4 實(shí)驗(yàn)與分析

為了驗(yàn)證上面的事件檢測(cè)引擎的性能，我們?cè)O(shè)計(jì)了一個(gè)數(shù)據(jù)生成器 （RFID的實(shí)驗(yàn)數(shù)據(jù)沒(méi)有標(biāo)準(zhǔn)集，且從設(shè)備中采集大量的數(shù)據(jù)所需的周期很長(zhǎng)）。數(shù)據(jù)生成器模擬的是一個(gè)超市的環(huán)境。實(shí)驗(yàn)采用的復(fù)雜事件查詢是Q1。所有算法用C＋＋實(shí)現(xiàn)，硬件環(huán)境是PC Pentium IV 2.8GHz CPU，1GB內(nèi)存。我們主要對(duì)比兩個(gè)算法：一個(gè)算法是在數(shù)據(jù)清洗后進(jìn)行事件檢測(cè)，但沒(méi)有用到一些邏輯規(guī)則［13］；另外一個(gè)算法是直接在原始數(shù)據(jù)流上進(jìn)行事件檢測(cè)［14］，但用到了一些統(tǒng)計(jì)信息和邏輯規(guī)則對(duì)數(shù)據(jù)進(jìn)行清洗。算法對(duì)比的指標(biāo)為CPU時(shí)間耗費(fèi)和內(nèi)存占用率。本文用到的統(tǒng)計(jì)信息是基于這樣的觀察：物品從貨架到結(jié)賬處的時(shí)間近似服從正態(tài)分布，當(dāng)拿到一個(gè)物品在貨架上的讀數(shù)后，可以通過(guò)這樣的統(tǒng)計(jì)信息推斷物品在結(jié)賬處的可能時(shí)間，那么在結(jié)賬點(diǎn)時(shí)間前的重復(fù)數(shù)據(jù)就可只保留一次，而結(jié)賬點(diǎn)后的非出口處物品被其他讀寫(xiě)器交叉讀到的數(shù)據(jù)都可過(guò)濾掉，這就同時(shí)達(dá)到了數(shù)據(jù)清洗和事件處理的目的。

我們生成了兩類(lèi)數(shù)據(jù)集：一類(lèi)是RFID數(shù)據(jù)流中含有重復(fù)的標(biāo)簽，另外一類(lèi)是RFID數(shù)據(jù)流中存在納偽的數(shù)據(jù)。在這兩類(lèi)數(shù)據(jù)上，數(shù)據(jù)清洗和復(fù)雜事件處理的性能對(duì)比如圖3和圖4所示。

從圖3和圖4可以看出，數(shù)據(jù)清洗后進(jìn)行復(fù)雜事件處理的算法比直接在原始數(shù)據(jù)流上進(jìn)行事件檢測(cè)的算法要占用很多的內(nèi)存。這是因?yàn)?，?shù)據(jù)清洗要單獨(dú)占系統(tǒng)的資源，復(fù)雜事件處理一遍數(shù)據(jù)流要占用系統(tǒng)資源。兩次掃描數(shù)據(jù)流且沒(méi)有利用一些參考信息是占用更多系統(tǒng)資源的主要原因。

圖5和圖6為兩種算法CPU時(shí)間耗費(fèi)對(duì)比。

在進(jìn)行數(shù)據(jù)清洗時(shí)，RFID數(shù)據(jù)要時(shí)往往要求保證順序性，這是因?yàn)镽FID數(shù)據(jù)的順序?qū)δ承┍O(jiān)控場(chǎng)景是很關(guān)鍵的 （如在醫(yī)療監(jiān)控場(chǎng)景中，醫(yī)務(wù)人員操作的順序?qū)︶t(yī)療事故的鑒定很關(guān)鍵）。保證數(shù)據(jù)流的順序性需要額外的系統(tǒng)開(kāi)銷(xiāo)。本文借鑒文獻(xiàn) ［15］的算法來(lái)保證數(shù)據(jù)的順序。

實(shí)驗(yàn)中設(shè)定納偽數(shù)據(jù)的比例為1%和4%是因?yàn)榧{偽數(shù)據(jù)在實(shí)際應(yīng)用中不可能占整個(gè)數(shù)據(jù)的大部分，否則這個(gè)RFID應(yīng)用的設(shè)計(jì)就是失敗的，但由于RFID讀寫(xiě)器和環(huán)境的影響，系統(tǒng)肯定會(huì)存在一定比例的納偽數(shù)據(jù)。重復(fù)數(shù)據(jù)是RFID的主要特性之一。所以本文關(guān)注RFID的這兩類(lèi)數(shù)據(jù)特征。實(shí)驗(yàn)中采用的規(guī)則除了一些統(tǒng)計(jì)特性外，還有就是對(duì)整個(gè)應(yīng)用場(chǎng)景的抽象：我們把一個(gè)應(yīng)用場(chǎng)景抽象成一個(gè)有向圖，利用有向圖邊間的關(guān)系，對(duì)RFID的數(shù)據(jù)流進(jìn)行過(guò)濾，達(dá)到快速檢測(cè)事件和去除冗余的中間結(jié)果的目的。

5 結(jié)束語(yǔ)

本文利用事件查詢的語(yǔ)義約束和實(shí)際應(yīng)用的邏輯規(guī)則，在原始的數(shù)據(jù)流上進(jìn)行事件檢測(cè)，避免了一般的事件處理算法先進(jìn)行簡(jiǎn)單的數(shù)據(jù)清洗，再進(jìn)行事件檢測(cè)所帶來(lái)的巨大系統(tǒng)資源開(kāi)銷(xiāo)；然后我們編程實(shí)現(xiàn)了該方法并且將其集成到復(fù)雜事件處理引擎中；最后通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了本文所提方法的正確性與高效性。下一步的主要工作是將復(fù)雜事件處理引擎加入到更為底層的RFID中間件中，通過(guò)真實(shí)場(chǎng)景所遇到的問(wèn)題進(jìn)一步完善我們的復(fù)雜事件處理引擎。

［1］GU Yu，YU Ge，ZHANG Tiancheng.RFID complex event processing techniques ［J］.Journal of Computer Science and Frontiers，2007，1 （3）：255－267 （in Chinese）［谷峪，于戈，張?zhí)斐?RFID復(fù)雜事件處理技術(shù) ［J］.計(jì)算機(jī)科學(xué)與探索，2007，1 （3）：255－267.］

［2］LEE C H，CHUNG C W.Efficient storage scheme and query processing for supply chain management using RFID ［C］.Proc of the 27th ACM SIGMOD Conf.New York：ACM，2008：291－302.

［3］Roussos G.Enabling RFID in retail［J］.IEEE Computer，2006，39 （3）：25－30.

［4］LI M，LIU M，DING L P，et al.Event stream processing with out－of－order data arrival［C］.27th ICDCS Workshops.Los Alamitos，CA：IEEE Computer Society，2007：67－74.

［5］Chandramouli B，Goldstein J，Maier D.High－performance dynamic pattern matching over disordered streams［J］.PVLDB，2010，3 （1）：220－231.

［6］Johnson T，Muthukrishnan S，Rozenbaum I.Monitoring regular expressions on out－of－order streams ［C］.Proc of the 23rd ICDE Conference.Los Alamitos，CA：IEEE，2007：1315－1319.

［7］LIU M，LI M，Golovnya D，et al.Sequence pattern query processing over out－of－order event streams ［C］.Proc of the 25th ICDE Conference.Los Alamitos，CA：IEEE，2009：784－795.

［8］Re C，Letchner J，Balazinska M，et al.Event queries on correlated probabilistic streams［C］.Proc of the 27th ACM SIGMOD Conference.New York：ACM，2008：715－728.

［9］Shawn R Jeffery，Minos Garofalakis，Michael Franklin.Adaptive cleaning for RFID data streams ［C］.Proc of the 20th VLDB.Seoul Korea：ACM，2006：163－174.

［10］RAO Jun，Sangeeta Doraiswamy，Hetal Thakkar，et al.A deferred cleansing method for RFID data analytics ［C］.Proc of the 20th VLDB.Seoul Korea：ACM 2006：175－186.

［11］WU E，DIAO Y，Rizvi S.High－performance complex event processing over streams［C］.Proc of the 25th ACM SIGMOD Conference.New York：ACM，2006：407－418.

［12］CHEN Yuan，LI Zhanhuai，CHEN Qun.Complex event processing over unreliable RFID data streams ［J］.Journal of Application Research of Computers，2009，26 （7）：2537－2539（in Chinese）.［陳遠(yuǎn)，李戰(zhàn)懷，陳群.不可靠RFID數(shù)據(jù)上的復(fù)雜事件處理研究 ［J］.計(jì)算機(jī)應(yīng)用研究，2009，26（7）：2537－2539.］

［13］MEI Y，Madden S.ZStream：A cost－based query processor for adaptively detecting composite events［C］.Proceedings of the 35th SIGMOD International Conference on Management of Data.New York：ACM，2009：193－206.

［14］Aleri CEP 3.0 ［EB／OL］.［2010－06－01］.http：／／www.aleri.com／.

［15］WANG F，LIU S，LIU P，et al.Bridging physical and virtual worlds：Complex event processing for RFID data streams ［C］.10th International Conference on Extending Database Technology.Berlin Heidelberg，Germany：Springer，2006：588－607.