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

高航

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

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

高航

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

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

傳感器網(wǎng)絡；事件檢測；綜述；復合事件

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

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

1.2事件檢測

定義2事件［4］。事件是周圍環(huán)境狀態(tài)變化的一種反映。當周圍環(huán)境中的某個因素發(fā)生變化時，如亮度，即說明周圍環(huán)境的狀態(tài)發(fā)生了改變，也就是發(fā)生了一個事件。事件可以分為簡單事件和復合事件。

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

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

1　相關介紹及定義

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

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

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

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

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

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

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

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

1）統(tǒng)計學模型

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

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

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

2）概率模型

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

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

3）人工智能和機器學習模型

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

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

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

1）基于事件樹的復合事件檢測

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

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

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

基于事件樹的復合事件檢測時遞歸進行的，首先為復合事件構(gòu)造事件求值樹，其次針對復合事件中的簡單事件進行檢測，即葉子節(jié)點，進而通知父節(jié)點，直到檢測到復合事件或沒有父節(jié)點。

2）基于圖的復合事件檢測

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

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

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

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

3）基于自動機的復合事件檢測

某些復合事件的表達式是不帶參數(shù)的，類似于正則表達式，針對這樣的復合事件，可以直接采用有窮自動機來表示事件。

Gehani等人在其研究的文獻中介紹了劍橋大學研究組在傳統(tǒng)自動機基礎上加入時間模型和參數(shù)化機制的復合事件檢測框架。在大規(guī)模的分布式系統(tǒng)中，因為缺乏集中管理及存在時間漂移問題等，很難確定兩個事件的發(fā)生順序。劍橋大學研究組基于這一問題研究出復合事件檢測器，該檢測器采用規(guī)則結(jié)構(gòu)的簡單自動機，同時它還支持時間模型、參數(shù)化機制和并發(fā)事件模型等。

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

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

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

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

3　分析與評價

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

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

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

4　結(jié)束語

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

［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稿件編號：201503308

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