高航

（北京工業(yè)大學(xué) 軟件學(xué)院，北京　100022）

無(wú)線傳感器網(wǎng)絡(luò)中復(fù)合事件檢測(cè)技術(shù)研究

高航

（北京工業(yè)大學(xué) 軟件學(xué)院，北京100022）

通過(guò)搜集和整理近些年來(lái)無(wú)線傳感器網(wǎng)絡(luò)中復(fù)合事件檢測(cè)技術(shù)方面的研究工作，討論了無(wú)線傳感器網(wǎng)絡(luò)中復(fù)合事件檢測(cè)領(lǐng)域的主要研究成果，從復(fù)合事件檢測(cè)的模型與技術(shù)的對(duì)比等方面進(jìn)行了深入的探討，為以后進(jìn)一步的研究提供了支持。最后分析了復(fù)合事件檢測(cè)技術(shù)的研究趨勢(shì)，并對(duì)該領(lǐng)域有待深入的研究難點(diǎn)和發(fā)展趨勢(shì)進(jìn)行了展望。

傳感器網(wǎng)絡(luò)；事件檢測(cè)；綜述；復(fù)合事件

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor networks，WSNs）由許多微小的設(shè)備構(gòu)成，這些微小的設(shè)備被叫做傳感器節(jié)點(diǎn)，部署在一片區(qū)域中。每個(gè)傳感器節(jié)點(diǎn)都由感知模塊、數(shù)據(jù)通信模塊和處理單元組成，這樣的構(gòu)成能夠使得這些傳感器節(jié)點(diǎn)有效的監(jiān)視周?chē)沫h(huán)境，相互通信并交換收集到的數(shù)據(jù)，從而能夠?qū)κ占饋?lái)的數(shù)據(jù)進(jìn)行局部處理并做出決策。當(dāng)然，在傳感器網(wǎng)絡(luò)監(jiān)測(cè)區(qū)域中，時(shí)常會(huì)有非正常數(shù)據(jù)行為產(chǎn)生，所以就產(chǎn)生了事件檢測(cè)的需求。傳感器網(wǎng)絡(luò)中的事件檢測(cè)技術(shù)近年來(lái)在多項(xiàng)應(yīng)用中都受到了廣泛關(guān)注，如軍事目標(biāo)追蹤和監(jiān)視、氣象災(zāi)害檢測(cè)、野生動(dòng)物監(jiān)測(cè)、自然災(zāi)害救助和醫(yī)療等。

事件檢測(cè)技術(shù)應(yīng)該能滿足以下幾點(diǎn)要求：實(shí)時(shí)性、高有效檢測(cè)率和低誤報(bào)警率［1］。然而，在典型的無(wú)線傳感器網(wǎng)絡(luò)中，傳感器節(jié)點(diǎn)是有諸多限制的，如有限的電量、計(jì)算能力和存儲(chǔ)能力，所以在考慮到傳感器節(jié)點(diǎn)的局限性的情況下，想提出一個(gè)完美的事件檢測(cè)模型是非常困難的。Kerman［2］等人將無(wú)線傳感器網(wǎng)絡(luò)中最常見(jiàn)的困難描述為：情境依賴性、應(yīng)用的嚴(yán)格性、繁雜的數(shù)據(jù)資源和網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。文中將無(wú)線傳感器網(wǎng)絡(luò)中前人所做的工作進(jìn)行總結(jié)，并在此基礎(chǔ)上進(jìn)行一定的分析與評(píng)價(jià)。Sensor networks，WSNs）是由許多無(wú)線傳感器節(jié)點(diǎn)構(gòu)成的，一種通過(guò)無(wú)線通信方式形成的分布式多跳自組織傳感網(wǎng)絡(luò)，它的末梢是可以感知和檢查外部世界的傳感器。WSNs中的傳感器通過(guò)無(wú)線方式通信，因此網(wǎng)絡(luò)設(shè)置靈活，設(shè)備位置可以隨時(shí)更改，還可以跟互聯(lián)網(wǎng)進(jìn)行有線或無(wú)線方式的連接。

1.2事件檢測(cè)

定義2事件［4］。事件是周?chē)h(huán)境狀態(tài)變化的一種反映。當(dāng)周?chē)h(huán)境中的某個(gè)因素發(fā)生變化時(shí)，如亮度，即說(shuō)明周?chē)h(huán)境的狀態(tài)發(fā)生了改變，也就是發(fā)生了一個(gè)事件。事件可以分為簡(jiǎn)單事件和復(fù)合事件。

在充分查閱文獻(xiàn)并深刻理解的基礎(chǔ)上，本文結(jié)合現(xiàn)有的定義，提出了以下簡(jiǎn)單事件和復(fù)合事件的概念。

定義3簡(jiǎn)單事件。簡(jiǎn)單事件是指由周?chē)h(huán)境中的某一種因素發(fā)生變化所引起的狀態(tài)變化，它只對(duì)一種因素的變化產(chǎn)生反映。一個(gè)簡(jiǎn)單事件可以表示為：

1　相關(guān)介紹及定義

1.1無(wú)線傳感器網(wǎng)絡(luò)

定義1無(wú)線傳感器網(wǎng)絡(luò)［3］。無(wú)線傳感器網(wǎng)絡(luò)（Wireless

其中，E表示簡(jiǎn)單事件；H0：f（x）=0表示事件未發(fā)生，H1：f（x）=1表示事件發(fā)生，x表示引起事件發(fā)生的某一種環(huán)境因素。

定義4復(fù)合事件。復(fù)合事件相對(duì)簡(jiǎn)單事件而言，是指由周?chē)h(huán)境的多種因素發(fā)生變化所引起的狀態(tài)變化，復(fù)合事件的發(fā)生并不單單是由一種因素變化引起的，可以是由時(shí)間、空間、溫度、濕度等因素共同變化引起的。一個(gè)復(fù)合事件可以表示為：

與簡(jiǎn)單事件相同，E表示復(fù)合事件，H0：f（x0，x1，x2，…，xm）=0表示事件未發(fā)生，H1：f（x0，x1，x2，…，xm）=1表示事件發(fā)生，x0，x1，x2，…，xm表示引起事件發(fā)生的各種環(huán)境因素。

2　復(fù)合事件檢測(cè)研究現(xiàn)狀

眾多專家學(xué)者經(jīng)過(guò)研究后紛紛提出了自己的事件檢測(cè)模型，以下將按照復(fù)合事件檢測(cè)模型和技術(shù)分別進(jìn)行闡述。

2.1復(fù)合事件檢測(cè)模型研究現(xiàn)狀

1）統(tǒng)計(jì)學(xué)模型

Gupchup等人［5］提出了基于統(tǒng)計(jì)信號(hào)處理技術(shù)的復(fù)合事件檢測(cè)方法。他們使用主成分分析法 （Principal Component Analysis，PCA）來(lái)構(gòu)建一個(gè)特定觀察現(xiàn)象的緊湊模型，并把這個(gè)模型用來(lái)檢測(cè)周?chē)h(huán)境中發(fā)生的各種因素的變化，如季風(fēng)氣候、降雨等。Gupchup等人利用實(shí)際采集的測(cè)量值和模型預(yù)測(cè)值之間的差值來(lái)檢測(cè)收集到的數(shù)據(jù)流中離散事件的存在。實(shí)驗(yàn)結(jié)果表明該模型能夠使用傳感器節(jié)點(diǎn)的溫度模式來(lái)檢測(cè)降雨。

Meng等人［6］提出了一種壓縮感知稀疏事件檢測(cè)方法。該方法提出了無(wú)線傳感器網(wǎng)絡(luò)的兩個(gè)問(wèn)題。第一，在所有的傳感器節(jié)點(diǎn)中，只有一小部分是活動(dòng)節(jié)點(diǎn)；第二，不同事件可能會(huì)同時(shí)發(fā)生，并導(dǎo)致在對(duì)事件進(jìn)行分別檢測(cè)時(shí)產(chǎn)生干擾。為了解決這些問(wèn)題，Meng等人采納了邊際似然函數(shù)的最大化算法和貝葉斯框架下的一種啟發(fā)式算法。作者堅(jiān)持他們的方法相比傳統(tǒng)的線性規(guī)劃解法具有更高的檢測(cè)效率。

Vu等人［7］提出了無(wú)線傳感器網(wǎng)絡(luò)中復(fù)合事件及報(bào)警的實(shí)時(shí)高效節(jié)能k-監(jiān)督事件檢測(cè)問(wèn)題 （Timely Energy-efficient k-Watching Event Detection problem，TEKWED）。為了解決該問(wèn)題，他們提出了一種能夠檢測(cè)事件并進(jìn)行實(shí)時(shí)報(bào)警的機(jī)制?；谶@種機(jī)制，他們又提出了一種考慮了傳感器網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和路由能力的算法，該算法建立了一套各有優(yōu)點(diǎn)的檢測(cè)事件集合，包括短通知時(shí)間、能源節(jié)約和時(shí)間報(bào)警應(yīng)用中報(bào)告要求的可調(diào)諧質(zhì)量。

2）概率模型

Li等人［8］進(jìn)行了復(fù)合事件的研究，并提出了一種用于3D環(huán)境監(jiān)測(cè)應(yīng)用中的非閾值復(fù)合事件監(jiān)測(cè)方法。作者使用節(jié)能的方法收集來(lái)自傳感器網(wǎng)絡(luò)的數(shù)據(jù)映射的時(shí)間序列，通過(guò)匹配數(shù)據(jù)的時(shí)空數(shù)據(jù)模式檢測(cè)復(fù)合事件。

Zoumboulakis等人提出了一種傳感器網(wǎng)絡(luò)中監(jiān)測(cè)復(fù)合事件的方法，他們把復(fù)合事件定義成一系列隱藏人們所關(guān)注模型或圖案的數(shù)據(jù)點(diǎn)集，并且堅(jiān)持認(rèn)為目前存在的技術(shù)不足以監(jiān)測(cè)這些復(fù)雜的模型或圖案。受時(shí)間序列數(shù)據(jù)挖掘技術(shù)的啟發(fā)，作者提出了一種用符號(hào)集近似算法將原生實(shí)值感覺(jué)數(shù)據(jù)轉(zhuǎn)變?yōu)榉?hào)表示的方法，并且利用距離度量進(jìn)行字符串比較。

3）人工智能和機(jī)器學(xué)習(xí)模型

Bahrepour等作者研究了事件監(jiān)測(cè)中機(jī)器學(xué)習(xí)技術(shù)所扮演的角色，并提出了使用無(wú)線傳感器網(wǎng)絡(luò)檢測(cè)災(zāi)難性事件的方法。具體而言，該方法主要基于運(yùn)行在每個(gè)傳感器節(jié)點(diǎn)上的決策樹(shù)分類器來(lái)進(jìn)行事件檢測(cè)，并且在傳感器節(jié)點(diǎn)檢測(cè)到的結(jié)果中采用投票機(jī)制來(lái)形成決策。作者們解釋了選擇決策樹(shù)的原因是作為if-then-else規(guī)則，決策樹(shù)的簡(jiǎn)單和明確的表達(dá)形式滿足了資源受限的無(wú)線傳感器網(wǎng)絡(luò)的要求。

Abadi等人［1］提出了REED（Robust，Efficient Filtering and Event Detection），一種用于傳感器網(wǎng)絡(luò)中穩(wěn)定高效過(guò)濾和事件檢測(cè)的系統(tǒng)。他們的方法擴(kuò)展了傳感器網(wǎng)絡(luò)內(nèi)部的用于高效執(zhí)行多謂詞過(guò)濾查詢的TinyDB查詢處理器。該方法有3個(gè)主要特點(diǎn)：在有限的RAM中運(yùn)行，能夠在節(jié)點(diǎn)群中分擔(dān)存儲(chǔ)壓力，對(duì)于丟包率和節(jié)點(diǎn)故障具有容錯(cuò)性。傳統(tǒng)的傳感器網(wǎng)絡(luò)數(shù)據(jù)庫(kù)系統(tǒng)并不能做到這一點(diǎn)，這讓該方法適用于大范圍的事件檢測(cè)應(yīng)用。

2.2復(fù)合事件檢測(cè)技術(shù)研究現(xiàn)狀

1）基于事件樹(shù)的復(fù)合事件檢測(cè)

基于事件樹(shù)的復(fù)合事件檢測(cè)實(shí)際上是將復(fù)合事件通過(guò)一定的方法構(gòu)造成一棵匹配樹(shù)，該樹(shù)的所有葉子節(jié)點(diǎn)表示原子事件，而葉子節(jié)點(diǎn)的父節(jié)點(diǎn)表示復(fù)合事件。

Samani等人提出了一種分布式系統(tǒng)中普遍事件監(jiān)視語(yǔ)言（Generalized events Monitoring language，GEM），該系統(tǒng)假定存在一個(gè)良好同步的全局時(shí)鐘。事件的發(fā)生和檢測(cè)之間存在一定的延遲，這樣可能導(dǎo)致檢測(cè)到的事件失序。為避免發(fā)生錯(cuò)誤的檢測(cè)，GEM采取在檢測(cè)階段來(lái)處理這種延遲。采用基于樹(shù)的機(jī)制來(lái)檢測(cè)復(fù)合事件，關(guān)鍵的步驟是為事件表達(dá)式創(chuàng)建一棵事件求值樹(shù)，使得其結(jié)構(gòu)匹配事件表達(dá)式，以及處理延遲。如圖1。

圖1　事件求值樹(shù)結(jié)構(gòu)Fig.1　Structure of event evaluation

基于事件樹(shù)的復(fù)合事件檢測(cè)時(shí)遞歸進(jìn)行的，首先為復(fù)合事件構(gòu)造事件求值樹(shù)，其次針對(duì)復(fù)合事件中的簡(jiǎn)單事件進(jìn)行檢測(cè)，即葉子節(jié)點(diǎn)，進(jìn)而通知父節(jié)點(diǎn)，直到檢測(cè)到復(fù)合事件或沒(méi)有父節(jié)點(diǎn)。

2）基于圖的復(fù)合事件檢測(cè)

基于圖的復(fù)合事件檢測(cè)方法與基于事件樹(shù)的復(fù)合事件檢測(cè)方法類似，在Snoop中采用的就是基于圖的復(fù)合事件檢測(cè)方法，事件由葉子節(jié)點(diǎn)發(fā)生，然后向上追溯到父節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)表示的是簡(jiǎn)單事件，父節(jié)點(diǎn)表示的是事件的一系列操作。

Chakravarthy等人提出了Snoop復(fù)合事件檢測(cè)系統(tǒng)，該系統(tǒng)假設(shè)所有的事件之間存在全序全系，并且事件的發(fā)生和檢測(cè)之間不存在延遲。簡(jiǎn)單事件發(fā)生在確定的時(shí)間點(diǎn)，而復(fù)合事件發(fā)生的事件則由復(fù)合事件內(nèi)最后一個(gè)簡(jiǎn)單事件的發(fā)生時(shí)間來(lái)確定。

圖2　全局事件歷史Fig.2　Global event history

該系統(tǒng)引入事件歷史，如上圖2，在知道全局事件歷史的情況下，可以通過(guò)計(jì)算得到任意復(fù)合事件的歷史，該方法的原理為給每一個(gè)復(fù)合事件構(gòu)造事件歷史圖，當(dāng)事件發(fā)生時(shí)就將相應(yīng)參數(shù)存儲(chǔ)到相應(yīng)的葉子節(jié)點(diǎn)，然后傳給父節(jié)點(diǎn)，選擇相對(duì)應(yīng)的算法進(jìn)行操作，直到到達(dá)根節(jié)點(diǎn)。

3）基于自動(dòng)機(jī)的復(fù)合事件檢測(cè)

某些復(fù)合事件的表達(dá)式是不帶參數(shù)的，類似于正則表達(dá)式，針對(duì)這樣的復(fù)合事件，可以直接采用有窮自動(dòng)機(jī)來(lái)表示事件。

Gehani等人在其研究的文獻(xiàn)中介紹了劍橋大學(xué)研究組在傳統(tǒng)自動(dòng)機(jī)基礎(chǔ)上加入時(shí)間模型和參數(shù)化機(jī)制的復(fù)合事件檢測(cè)框架。在大規(guī)模的分布式系統(tǒng)中，因?yàn)槿狈泄芾砑按嬖跁r(shí)間漂移問(wèn)題等，很難確定兩個(gè)事件的發(fā)生順序。劍橋大學(xué)研究組基于這一問(wèn)題研究出復(fù)合事件檢測(cè)器，該檢測(cè)器采用規(guī)則結(jié)構(gòu)的簡(jiǎn)單自動(dòng)機(jī)，同時(shí)它還支持時(shí)間模型、參數(shù)化機(jī)制和并發(fā)事件模型等。

自動(dòng)機(jī)包含有限的狀態(tài)和遷移，狀態(tài)是自動(dòng)機(jī)模型用來(lái)匹配時(shí)序相關(guān)的復(fù)合事件的方法；遷移分為兩種，強(qiáng)遷移表示剛檢測(cè)過(guò)的事件與下一個(gè)事件之間的偏序關(guān)系，弱遷移表示剛檢測(cè)過(guò)的事件與下一事件之間的全序關(guān)系?；谧詣?dòng)機(jī)的復(fù)合事件檢測(cè)的基本原理是為每個(gè)復(fù)合事件構(gòu)造自動(dòng)機(jī)，得到相應(yīng)的狀態(tài)集和遷移集，并根據(jù)這些條件進(jìn)行匹配，若最后獲得一個(gè)沒(méi)有向外遷移的生成狀態(tài)，就代表復(fù)合事件檢測(cè)成功。

4）基于Petri網(wǎng)的復(fù)合事件檢測(cè)

基于Petri網(wǎng)的復(fù)合事件檢測(cè)技術(shù)主要原理就是根據(jù)復(fù)合事件構(gòu)造出Petri網(wǎng)，此項(xiàng)技術(shù)多用在RFID領(lǐng)域中，但由于也涉及到復(fù)合事件檢測(cè)，所以本文簡(jiǎn)單介紹一下。

基于Petri網(wǎng)的復(fù)合事件檢測(cè)的主要過(guò)程為對(duì)每個(gè)新發(fā)生的事件模型構(gòu)造Petri網(wǎng)，簡(jiǎn)單事件作為輸入，輸出表示復(fù)合事件。發(fā)生過(guò)的事件都被標(biāo)記，并作為輸入，則表標(biāo)記事件的輸入事件同樣也被標(biāo)記，如此重復(fù)，直到獲得一個(gè)時(shí)間模型，且該事件模型沒(méi)有向外遷移的庫(kù)，則檢測(cè)成功。

3　分析與評(píng)價(jià)

Meng等人的研究結(jié)果雖然揭示了無(wú)線傳感器網(wǎng)絡(luò)的兩大問(wèn)題，也給出了相應(yīng)的解決方案，但并沒(méi)有有力的實(shí)驗(yàn)表明該方案是確實(shí)有效的；Zoumboulakis等人復(fù)合事件定義成一系列隱藏人們所關(guān)注模型或圖案的數(shù)據(jù)點(diǎn)集，提出了一種用符號(hào)集近似算法將原生實(shí)值感覺(jué)數(shù)據(jù)轉(zhuǎn)變?yōu)榉?hào)表示的方法，但是這樣會(huì)加大計(jì)算量，而對(duì)于資源受限的傳感器節(jié)點(diǎn)來(lái)說(shuō)，這明顯是無(wú)法承受的。

GEM考慮了事件發(fā)生與檢測(cè)之間的延遲，但其假設(shè)存在一個(gè)良好的全局同步時(shí)鐘，而這一假設(shè)并不適用于大規(guī)模的分布式系統(tǒng)；Snoop只提供了簡(jiǎn)單的時(shí)間模型，根據(jù)語(yǔ)義來(lái)確定復(fù)合事件的時(shí)間點(diǎn)，這比較適合應(yīng)用于集中式系統(tǒng)或局域網(wǎng)；有限狀態(tài)自動(dòng)機(jī)雖然能夠直觀的表達(dá)事件，但純粹的自動(dòng)機(jī)并不檢測(cè)帶參數(shù)的事件，不能表示事件的時(shí)序關(guān)系。

從上述分析可以看出，目前存在的復(fù)合事件檢測(cè)模型和技術(shù)都沒(méi)有完美解決無(wú)線傳感器網(wǎng)絡(luò)中事件檢測(cè)的問(wèn)題，所以在無(wú)線傳感器網(wǎng)絡(luò)中復(fù)合事件檢測(cè)方面仍需要進(jìn)一步努力。

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

隨著事件檢測(cè)的廣泛應(yīng)用，復(fù)合事件檢測(cè)日益引起人們的關(guān)注，遇到的問(wèn)題也越來(lái)越多，而且由于無(wú)線傳感器網(wǎng)絡(luò)的諸多限制，要構(gòu)建一個(gè)充分考慮到這些限制的事件檢測(cè)模型并不是一項(xiàng)容易的工作。本文搜集整理了復(fù)合事件檢測(cè)領(lǐng)域內(nèi)現(xiàn)有的研究工作，并在此基礎(chǔ)上，針對(duì)每項(xiàng)有代表性的工作進(jìn)行了一定的分析與評(píng)價(jià)，應(yīng)當(dāng)說(shuō)，復(fù)合事件檢測(cè)的發(fā)展遠(yuǎn)不止于此，希望本文的工作能夠?yàn)槲磥?lái)的復(fù)合事件檢測(cè)研究提供一定的幫助。

［1］Adabi D，Madden S，Lindner W.REED：Robust，Efficient FilteringandEventDetectioninSensorNetworks［C］. Proceedings of the 31st Very Large Databases Conference，2008：769-780.

［2］Kerman M C，Jiang W，Blumberg A F，Buttrey S E.Event Detection Challenges，Methods，and Applications in Natural and Artificial Systems［C］.Proceeding of the International CommandandControlResearchandTechnology Symposium，2009：1-19.

［3］Jennifer Y，Biswanath M，Dipak G.Wireless sensor network survey［J］.Computer Networks，2008，52（12）：2292-2330.

［4］Chinh T V，Raheem A B，Li Y S.Composite event detection inwirelesssensornetworks［C］.IEEEInternational Performance，Computing，and Communications Conference，2007：264-271.

［5］Gupchup J，Burns R，Terzis A，Szalay A.Model-Based EventDetection in Wireless Sensor Networks［C］.Proceedings of the Workshop on Data Sharing and Interoperability on the World-Wide Sensor Web，2008.

［6］Meng J，Li H，Han Z.Sparse event detection in wireless sensor networks using compressive sensing［C］.Proceeding of Conference on Information Sciences and Systems，2009：181-185.

［7］Vu C T，Beyah R A，Li Y.Composite Event Detection in Wireless Sensor Networks［C］.Proceeding of the IEEE International Performance，Computing，and Communications Conference，2007：264-271.

［8］Li M，Liu Y，Chen L.Non-Threshold based Event Detection for 3D Environment Monitoring in Sensor Networks［C］. Proceedingsofthe27thInternationalConferenceon Distributed Computing Systems，2007：1-9.

Research on composite event detection in wireless sensor networks

GAO Hang
（Beijing University of Technology，School of Software Engineering，Beijing 100022，China）

Through collecting and sorting out research works in composite event detection of wireless sensor networks，this article discusses main research findings in the field of composite event detection，compares models and techniques in composite event detection and explores them deeply to support further study.In the end，the article analyzes the research trends of composite event detection and puts forward difficult and key points in the research of this field.

wireless sensor；event detection；summary；composite event

TP302

A

1674－6236（2016）03-0115-03

2015-03-23稿件編號(hào)：201503308

高 航（1988—），男，山西定襄人，碩士研究生。研究方向：嵌入式計(jì)算與物聯(lián)網(wǎng)。