傳感器網絡中語義事件區域查詢處理

李英龍 朱藝華 呂明琪

(浙江工業大學計算機科學與技術學院 杭州 310023)(liyinglong@zjut.edu.cn)

傳感器網絡中語義事件區域查詢處理

李英龍 朱藝華 呂明琪

(浙江工業大學計算機科學與技術學院 杭州 310023)(liyinglong@zjut.edu.cn)

傳感器網絡可以看成是一個資源受限的無線分布式數據庫系統，如何設計低功耗高可靠的數據處理方法，從分布式的感知數據中獲取用戶感興趣的信息是一個挑戰性工作.現有的事件(區域)檢測方法大都基于原始的感知數據，處理大規模的原始感知數據的通信和時間開銷很大，然而這些原始數據由于本身的不精確性和不確定性，難以保證得到精確的處理結果.大多數情況，用戶并不關心這些原始感知數據或者網內過濾/融合時的數據形態，而是想得到類似自然語言的“有多嚴重？” 、“可信嗎？”等語義事件信息.此外，現有的事件區域檢測方法主要是利用鄰居協作來提高檢測的準確性，而鄰居協作需要大規模的網內數據交換，非常耗時耗能.鑒于上述問題，提出一種新的基于模糊方法的語義事件區域查詢處理方法，語義事件信息代替原始的感知數據用于網內過濾和融合，并設計了基于模糊方法的分布式語義事件信息表示、過濾和融合算法.基于真實數據集的仿真實驗表明了該方法在兼顧節能和可靠性方面有良好的表現.

語義事件信息；模糊方法；能量有效性；可靠性；傳感器網絡

傳感器節點計算、存儲、通信能力十分有限，尤其是能量供應受限，在很多應用中更換電池或者充電是難于做到的，因此無線傳感器網絡可以看成是一個資源受限(尤其能量有限)的無線分布式數據庫系統.如何設計節能而可靠的數據處理算法，從分布式的感知數據中獲取用戶感興趣的信息是一個挑戰性工作.由于傳感器網絡的通信開銷主要是用于數據傳輸，因此在滿足用戶精度要求下降低網絡數據傳輸量是一個有效的解決方法.此外，減少數據傳輸量還可以提高處理的響應速度，以及減少無線通信中的信號干擾.

事件(區域)檢測是傳感器網絡/物聯網應用中的一類非常重要的任務[1-15]，盡早地發現潛在事件并及時處理，可有效地減少災害損失.獲取事件信息可分為用戶主動查詢監控區域內的潛在事件信息，以及感知節點自發檢測并上報事件信息.目前這類研究主要包括基于單個節點的簡單事件檢測[5,11-12]和基于鄰居協作的復雜事件檢測[6,8,10]，這些方法在兼顧節能性、實時性和可靠性方面仍存在不少問題.

1) 單節點事件檢測.事件定義往往取決于具體的應用問題，也影響著事件檢測的效率.在感知節點稀疏部署(單個節點覆蓋區域內的冗余節點較少)且節點穩定可靠的情況下，單個節點就可以完成局部事件檢測.這種方法的最大優點是網內數據傳輸量少，處理也非常及時，但是結果的準確性難以保證，特別是對于用戶想查詢k個最嚴重事件區域的情況，往往不大適用.例如在煤礦安全監控系統中，感知節點用于監測瓦斯濃度，如圖1所示，標注有瓦斯濃度(%)數據的節點是值得關注的潛在事件節點.在單節點事件檢測方法中，top-3事件查詢的結果是{S1，S2，S3}，這些結果均來自同一個區域，而用戶的本意可能是查詢以S2，S8，S12為中心的事件區域.另一方面，單節點事件檢測由于缺少空間相關性信息分析，容易造成事件誤報，如圖1所示，孤立事件節點S16可能是一個誤報.

Fig. 1 Example of coal mine gas concentration monitoring圖1 煤礦瓦斯濃度監測示例

2) 鄰居協作事件檢測.在實際應用中，感知節點的部署會較為稠密，即有一定的冗余，這樣可以利用空間相鄰節點交換感知數據來提高事件檢測的準確性，這類代表性研究就是基于權重的“投票(voting)技術”[6-7].該方法的好處是可以減少單個異常節點的誤報以及事件區域的漏報，從而提高事件檢測的可靠性.例如圖1中，基于鄰居協作的top-3事件區域查詢能正確找出S2，S8，S12為代表的3個事件區域.然而此類事件檢測方法，需要大量相鄰節點之間的信息交換，對于實時性和節能性來說，代價非常高.

此外，現有的事件檢測方法大都基于原始的感知數據，處理大規模的原始感知數據的通信和時間開銷很大，而且這些原始數據由于本身的不精確性和不確定性，難以保證得到精確的結果.然而在實際應用中，用戶并不關心這些原始感知數據或者網內過濾/融合時的數據形態，而是想知道類似自然語言的“嚴重性” 、“可信度”等語義事件信息.

本文提出一種低功耗可靠的語義事件區域查詢處理方法.提出語義事件信息代替原始感知數據用于網內融合和傳輸，可明顯降低數據傳輸量.給出基于模糊方法的事件可信度測量方法和非均勻離散化的語義事件信息表示方法，并設計基于模糊方法的語義事件信息過濾和網內融合算法，最后從節能和可靠性等方面，基于真實數據的仿真實驗驗證了此方法的有效性.

1 模型與問題定義

1.1 網絡模型

在事件監測系統中，感知節點部署到監控區域內自組織形成一個連通的網絡.感知節點部署通常包括隨機部署、規則部署和按需部署3種方法，每種部署方法都有各自的適用場景.其中規則部署和按需部署由于人工干預，通常能保證一定的網絡連通性，而隨機部署則需要關注網絡的連通性，通常的做法是引入泊松點過程(Poisson point process)假設[16].泊松點過程是廣泛存在的，例如建模一個確定空間的星星數量或者描述皮氏培養皿中的細菌數等.本文網絡部署引入泊松點過程是因為它符合多數人對于“隨機部署”的直覺概念.

此外我們將監控區域基于地理位置邏輯劃分成若干網格，每個格內選擇一個格管理(grid manager,GM)節點，用于收集局部事件信息和管理局部網絡拓撲結構，被選中的GM可以更高的通信頻率形成一個以Sink節點為根的TAG[17]樹形路由結構GM-Tree，如圖2所示：

Fig. 2 Grid network model based on uniform Poisson point process—GM-Tree圖2 基于均勻泊松點過程的格網絡模型——GM-Tree

值得注意的是，我們的網格劃分是基于地理位置的邏輯劃分，不需要像分簇網絡[18]那樣需要專門的簇結構管理算法.網格的大小可以根據節點的通信半徑和監控區域的大小而定，基本原則是每個網格覆蓋較多的節點，以保證一定數量的空間相關性節點用于事件區域檢測.GM的選擇方法也很多，比如可以離格中心最近的節點作為GM，這樣可使得GM收集本地事件信息的總能耗少；或者選擇剩余能量最大的節點為GM，這樣有利于網絡能量均衡.可以根據實際情況選擇GM.

此外，基于地理位置的網絡模型具有良好的魯棒性和可擴展性.當一個節點移動或增加到某一個網格中時，節點可以根據其地理坐標(GPS定位裝置)計算得到其所屬的網格.當一個GM失效或者移動到另一個網格時，它周圍的節點能夠發現它的移動并且按一定方法選擇新的GM.

1.2 問題定義

定義1. 語義事件區域查詢(semantic event region query,SERQ).SERQ查詢監控區域內k最有可能發生的潛在事件區域位置及其語義信息，可形式化為一個四元組：

SERQ=(Γ,n,k,QType)，

其中，Γ為查詢覆蓋節點的集合，一般為監控區域的所有的節點；n為查詢的最近的采樣周期數，與采樣周期間隔長短有關，采樣周期間隔越長，n越?。籯為返回查詢結果的個數，在事件監控系統中，由于人力物力限制，往往只能同時處理k個潛在事件，如果沒有這個限制，則返回所有可能的潛在事件區域位置；QType是事件類型，事件類型決定了事件定義模型.

值得注意的是，一個事件監測系統通常有默認的事件類型，比如煤礦安全監控系統中通過監測瓦斯濃度發現潛在瓦斯爆炸事件、森林安全監控系統中查詢潛在火災事件、現代精細化農業管理中溫度和濕度感知節點常用于查找需要澆灌的事件等.節點在部署前一般被嵌入默認的事件可信度模型或事件概率模型，如果要更改查詢的事件類型，那么需要基站廣播新的事件模型給每個節點，以更新原來默認的事件模型.

定義2.SERQ的查詢結果rst也可用一個三元組形式化表示：

rst=(nodeID,sev,serc)，

其中，nodeID是相同或相似事件區域的代表性節點的位置，這個代表性位置監控區域內最接近真實潛在事件的位置；sev為語義事件變量(semantic event variable)，sev使用接近人類自然語言來描述一類嚴重程度的潛在事件語義信息，詳見2.3節中的語義事件信息表示方法；serc為語義事件區域可信度(semantic event region confidence)，用于表示潛在事件區域是否存在的可信度.

總體來說，在SERQ中，用戶不關心具體的感知數據，也不關心網內融合的數據格式，只關心最嚴重k個潛在事件的語義信息及其最可能的發生位置.

2 語義事件信息表示

2.1 感知數據清洗

事件檢測應該消除錯誤感知數據對事件分析的影響.錯誤數據通常有2個主要來源：1)失效節點;2)正常節點的噪音數據.一般來說，實時事件監測系統中采樣周期都相對較短，那么可以基于最近n(n≥1)次采樣周期內的感知數據來進行實時事件檢測分析.現有噪聲數據檢測方法，大都利用時空相關性分析來發現和消除錯誤感知數據，其中空間相關性分析需要大量的相鄰節點信息交換[14,19]，非常耗時耗能，因此我們只利用節點局部的時間相關性分析來消除錯誤數據.盡管這不能消除所有的錯誤數據，但可以消除大部分錯誤數據，而且幾乎沒有通信代價，非常適用于低功耗的實時事件檢測.

對于失效節點，它的大部分數據會明顯偏離正常的取值范圍，因為傳感器網絡應用中，感知節點常用于感知物理環境，正常情況下物理環境值通常在一個合乎常理的取值范圍R之內，比如說在精細化農業管理中，土壤鹽堿度的取值范圍通常為[0,80%]，如果某個鹽堿度感知節點的大部分采樣值超過100%，甚至是負值，那么該節點極有可能就是一個失效節點.此外，失效節點的感知數據通常不具備時間相關性或者標準差難以接受.對于失效節點的感知數據，應該被提前過濾，以免事件誤報.

對于正常工作的節點，其采集的大部分感知數據符合一個正常模式V，少部分采樣周期內的感知數據明顯偏離正常取值范圍R或者均值λ，這部分感知數據稱為噪聲數據.我們之前的研究[8]提出一種識別和消除噪音數據的方法(improved smoothing factor， ISF)，ISF方法可以根據精度需要，通過設定標準值閾值，消除那些明顯偏離均值的噪聲數據，可以有效提高事件區域檢測的可靠性.

2.2 事件可信度測量

模糊方法[20]是扎德(Lotfi Zadeh)教授在1965年創立的，它以相對的、魯棒的和易于理解的方式分析處理復雜系統中的不精確和不確定數據.語言變量代替數值變量用于描述系統的行為，這為人們處理不確定性問題和近似問題提供了一種新的解決方法[21].

其中，xi(i=1,2,…,m)是節點的感知數據，m為感知數據的維數，avg(xi)是每維感知數據的平均值.在2.1節中，數據清洗消除了大部分錯誤數據，我們可以用最近幾個采樣周期內的感知數據的平均值來定義事件點的可信度.ωi(i=1,2,…,m)是可調因子，用于調節各屬性對于事件概率的影響程度，ω1+ω2+…+ωm=1.fun和fi可在領域專家指導下設定.

其中，α是一個0～1之間的指定值，即α∈[0,1].通常α=0.5，表示最大不確定性的臨界值.

定義5. 事件的0.5-截集內的所有事件點稱為值得關注的的事件節點(noteworthy event node， NEN).

上述定義是為了提早過濾那些可信度較低的事件節點，即過濾那些安全的感知數據，以減少網內通信開銷.

2.3 語義事件信息表示

非均勻的事件可信度離散化方法：把NEN可信度ec的取值范圍[α,1)劃分成若干區間大小不等的子范圍Rsub，這種非均勻的劃分可以基于某種數學模型(如等差數列)，也可以在領域專家指導下設定，遵循的原則是ec越大，其所處的子范圍區間越小.

例1. NEN可信度ec的取值范圍為[0.5,1)，它被劃分為6個不均勻的子區間，如表1中第4列所示.事件可信度取值越靠近1的Rsub，其區間間隔大小越小(0.03)，越靠近α的子范圍區間間隔越大(0.16).這樣劃分的好處是可用較多的語言變量(表1中第1列)來描述較嚴重的語義事件信息，有助于事件信息網內融合時提高事件檢測的可靠性.

Table 1 Example of Semantic Event Information Description表1 語義事件信息表示示例

語義事件信息表示方法：根據非均勻的事件可信度離散化方法，可以得到若干個區間大小不等的子范圍，我們定義相同數量的語義事件變量sev.每個子范圍對應著一個語義事件信息變量及其語義解釋，如表1中第1列、第2列所示.每個sev描述同一類嚴重程度的事件信息，區間間隔越小的子范圍對應的sev描述越嚴重的事件信息.在實際應用系統設計時，GM節點還可以對語義事件變量進行二進制編碼，如表1中第3列所示，以進一步降低網內通信開銷.

例2. 在表1中，6個子范圍對應著6個sev，每個sev的語義解釋如表1中第2列所示，這些語義解釋可以幫助用戶容易地理解返回的結果信息，而不需要領域專家的指導.4個sev用于描述較為嚴重的事件信息，只有2個sev用來描述不重要的(事件可信度低于0.76)事件信息，這有利于提高事件信息表示的準確性.

3 語義事件區域信息查詢處理

3.1 格內語義事件區域信息處理

格內語義事件信息過濾和存儲的過程為：每個節點根據2.2節式(2)計算本地語義事件的可信度；再根據定義6過濾0.5-截集內的所有事件點，即非NEN被過濾；然后根據2.3節語義事件信息表示方法得到本地語義事件變量sev，并發送其nodeID和sev到本格GM，GM有一張列表List，存儲每個接收到的nodeID及其對應sev.

定義6. 語義事件區域可信度serc描述局部事件區域存在的可信度，這種可信度和格內NEN數量有直接的關系，本文提出一種幾乎沒有額外通信代價的基于格內NEN數量的serc計算方法：

其中，List.size為格內NEN數量.當某格內NEN數為零時，表明潛在事件和事件區域都不存在；當只有1個NEN時，表明是孤立的NEN，誤報的可能性比較大，這時serc=0.5；當格內有2個以上的NEN時，那么潛在事件事件區域的可信度非常高，這時躍階函數serc的基數設為0.9，并隨著NEN數增加而增加；當空間相關的NEN數量為4或以上時，那么潛在事件事件區域的必然存在，serc=1.從理論分析和實際應用角度上看，躍階函數serc的設計是比較可行的.

根據上述格內語義事件信息過濾和存儲過程描述，我們可以設計格內語義事件區域信息處理分布式算法如下：

算法1. Inner-GM_SERQ_Process.

輸入：SERQ查詢消息；

輸出：List(nodeID,sev)，sercofGM.

步驟1. 每個節點根據2.2節式(2)計算本地事件點可信度；

步驟2. 根據定義6過濾0.5-截集內的所有事件點，即非NEN被過濾.

步驟3. 每個NEN根據2.3節語義事件信息表示方法得到本地語義事件變量sev，并發送其nodeID和sev到本格GM；

步驟4.GM內的List存儲每個接收到的nodeID及其對應sev，并根據定義7中式(3)計算該格serc值.

Fig. 3 Example of inner-grid semantic event information processing圖3 格內語義事件信息處理的例子

例3. 算法1的一個運行例子如圖3所示，在某個格GM內，GM收集所有的NEN，在圖3中NEN為S1，S3，GM本身，這些NEN的語義事件點信息存儲在GM的List中.算法1根據定義6式(3)計算該格內存在事件區域的可信度為0.98.由于S1的語義信息最嚴重，因此它將作為該事件區域代表被發送給GM的父GM節點.

算法1時間復雜度分析如下：算法1中各NEN發送消息包時是分布式的，GM接收多個NEN事件消息包時是串行通信的.假設格內最大節點數為h，不考慮計算時間開銷，算法1的時間復雜度為Tt+h×Tr，其中Tt為傳感器節點發送一個消息包的時間，Tr為GM接收一個事件消息包的時間.

3.2 網內語義事件區域信息融合

這里說的網內是指GM-Tree格與格之間，包括葉子GM語義事件區域信息過濾傳輸，以及非葉子GM語義事件區域信息融合.

在給出網內語義事件區域信息融合算法之前，我們基于模糊方法中的t-余模運算[20]定義語義事件變量比較操作符，用于選舉格內代表性事件點.

定義7. 設U和V為2個事件語言變量，對于任意的可信度值x∈Rsub(U)和y∈Rsub(V)，如果x

例如，在表1中，Rsub(A)

定義8. 設U和V為2個語言變量，它們的可信度子范圍分別為Rsub(U)和Rsub(V)，如果Rsub(U)

Θ即為格內語義事件變量比較操作符.

引理1. 比較操作符Θ是t-余模運算.

證明. 對任意的語言變量sev(如A，B，C，D)且Rsub(sev)?[0,1]，函數Θ:sev×sev→sev，對于任意的語義事件變量A，B，C，D滿足4個條件：

1) 交換律Θ(A,B)=Θ(B,A)；

2) 結合律Θ(Θ(A,B),C)=Θ(A,Θ(B,C))；

3) 單調性A≤B，C≤D?Θ(A,C)≤Θ(B,D)；

4) 邊界條件Θ(A,0)=A.

由模糊方法[20]，可得Θ即為t-余模運算.

證畢.

此外，我們還要定義一個綜合排序函數，用于格間語義事件區域信息top-k融合.

定義9. 定義格間語義事件區域信息融合排序函數score(sev,serc)，score綜合考慮事件代表點可信度ec和事件區域可信度serc，一個score函數例子為

其中，ec(sev)計算sev對應可信度區間的中間值.根據表1可知：ec(A)=0.985,ec(B)=0.945，ec(C)=0.885等，ω用于調節ec和serc對于score的影響程度，一般來說，事件區域存在可信度較大的時候，用戶往往對sev更大的事件區域代表點感興趣，因此本文實驗設置ω=0.7.

網內語義事件區域信息融合過程可用算法2描述.

算法2. Inter-GM_SERQ_Process.

輸入：SERQ查詢消息；

輸出：topknodeID，sev，serc.

步驟1.

① for each葉子GM(i)*GM-Tree的葉子GM*

② ifGM(i).Listis null then*List為空*

③ break;

④ else

⑤ 利用定義8中的Θ操作符查找最大sev對應的List(j).nodeID；*最大sev的NEN為事件區域代表點*

⑦ endif

步驟2.

⑨ do{

⑩ for each非葉子GM(i)*收集完子GM語義信息消息包*

例4. 算法2的一個運行例子如圖4所示.葉子GM節點GM(1)，GM(2)，GM(3)，GM(7) 把其語義事件區域信息(nodeID，sev，serc)發送給非葉子GM(8)節點，這些信息存儲在GM(8) 的Listp中.GM(8)根據定義10中式(4)計算Listp中的語義事件區域信息的綜合得分，然后根據SERQ中的k值，返回查詢結果，k=1，2，3時的查詢結果分別為{(5,B,0.94)}，{(5,B,0.94)，(11,C,0.98)}和{(5,B,0.94)，(11,C,0.98)，(37,D,1.0)}.

Fig. 4 Example of inter-grid semantic event region information fusion圖4 格間語義事件區域信息融合的例子

1)SERQ時間復雜度分析.SERQ時間復雜度即為算法2和算法1總的時間復雜度，設GM-Tree的最大度數為q，GM-Tree的層數為p.不考慮計算時間開銷，之前我們得到算法1的時間復雜度為Tt+h×Tr，其中h為格內最大節點數.同理，我們考慮分布式發送和串行接收的情況，SERQ的時間復雜度為 (Tt+h×Tr)+(Tt+q×Tr)×(p-1)，即為p×Tt+((p-1)×q+h)×Tr.由于h，p，q的值都比較小，因此SERQ的時間開銷非常低.

2)SERQ結果可靠性分析.我們沒有考慮所有的空間相關性，比如格與格邊界節點的空間相關性，也不做嚴格的事件區域邊界檢測，因此，SERQ的結果不是精確的，但是由于在SERQ的GM-Tree中，我們定義了格大小設置原則，即保證格內有一定數量的節點，使得格內節點的空間相關性足夠判斷一個事件區域是否存在，也即SERQ考慮了網內NEN的主要空間相關性，因此結果的可靠性比較高.如果我們考察所有的空間相關性以及做嚴格的事件區域邊界檢測，那么網內信息交換通信開銷很大[1,6]，將退化成現有的類似投票方法.

4 實驗結果與分析

4.1 實驗設置

仿真實驗平臺為OMNET++[22]，它是國際認可度很高的開源多協議網絡仿真軟件.實驗數據來自部分真實數據LUCE[23]，我們已經下載了該真實數據集，包括88個有效節點的位置數據和感知數據(節點號、溫度、濕度、光照、風向等)，節點分布在450 m×300 m的感知區域，感知節點和GM的通信半徑分別為50 m和80 m時的一個基于GM-Tree的網絡如圖5所示.我們主要使用其中的溫度T(temperature)和濕度H(humidity)來描述潛在火災事件.另外，為了更好地模擬事件的時空相關性，以及考察網絡中不同NEN比例對于算法的影響，我們基于Intel Lab Data[24]合成了部分數據.

其中，Tn和Hn是最近n個采用周期內的溫度和濕度值.實驗時n=5，avg(Tn) 和avg(Hn)分別表示最近n個采樣周期內的平均溫度值和平均濕度值，Tig和Hig是火災事件的臨界值，本實驗設置Tig和Hig分別為100°C和10%.

據我們檢索傳感器網絡/物聯網相關文獻，并沒有發現可以進行比較的同類方法，因此我們選擇2類代表性的事件處理方法進行比較評估，其中集中式查詢可以得到精確的事件信息結果，而基于投票的方法是目前事件檢測最常用的一種空間相關技術.為公平起見，下述2種方法中，非值得關注的事件節點同樣被提前過濾.

1) 集中式查詢(central)方法.在集中式查詢處理中，所有值得關注的潛在事件節點將最近5個周期的感知數據的平均值傳輸到Sink，然后Sink利用全局的拓撲信息來計算得到相對精確的潛在事件區域信息.

Fig. 5 Real-world network with 4.4 nodes per gird圖5 真實網絡—每個格平均覆蓋節點4.4個

2) 投票方法(voting).事件發生具有空間相關性，投票技術的核心就是相鄰節點相互交換信息來驗證事件的發生和事件區域的可信度;然后進行網內融合，返回k個最嚴重的事件區域.在投票方法中，通常需要距離因素確定投票權重，所以節點的地理位置信息也被傳輸.同樣為公平起見，非值得關注事件節點不參與到相鄰信息交換過程中.

評估指標有2個：

1) 數據傳輸量

在無線通信中，數據傳輸耗能占總通信耗能開銷的大部分，此外數據傳輸量對實時性也有很大影響，因此我們把數據傳輸量作為一個重要評估指標.

本實驗中，nodeID設為8位整數(INTERGER)，sev為8位字符(CHAR)，溫度T、濕度H、地理位置坐標數據、serc等都是32位實數(因為是32位的實驗平臺).我們不考慮消息包中的包頭、校驗碼等占位信息.

2) 準確性

我們定義SERQ查詢結果的準確性acc(accuracy)：

4.2 數據傳輸量

我們考察圖5中4種不同NEN比例(10%，20%，30%，50%)的網絡情況對于SERQ，voting，central的節能性能影響.對于相同NEN比例的網絡情況，調整NEN節點的分布，重復做實驗10次，分別計算得到它們平均數據傳輸量.上述4種不同NEN比例的網絡情況下，SERQ，voting，central三種方法的平均數據傳輸量如圖6所示.

現象1. 上述4種NEN比例的網絡環境下，SERQ的平均數據傳輸量都是最少的，central最大，voting介于它們之間.在30%NEN網絡中，SERQ的平均數據傳輸量大概是voting的43.5%，以及約是central的14.9%;在50%NEN網站中，SERQ的平均數據傳輸量大概是voting的39.6%，以及約是central的10.4%.在4種NEN比例的網絡環境下，SERQ的平均數據傳輸量大概是voting的44.7%，以及約是central的18.7%.

解釋.在實驗對比時，為盡可能地公平，我們都使用GM-Tree作為主干路由結構.在central方法中，沒有要求傳輸原始感知數據，而是同樣經節點處理后的節點事件概率值，此外還假設Sink或基站有全局的網絡拓撲信息，而不用傳輸地理位置信息;在voting方法中，沒有要求考察所有的鄰居空間相關性，比如網格邊界節點的鄰居協作就沒有進行處理，嚴格意義上說本文的對比方法voting是一種改良版，相比傳統voting方法的數據傳輸量更少.在這些設置下，我們的SERQ方法仍然具有數據傳輸量上的較大優勢，這主要：得益于采用了網內語義事件信息表示、過濾和融合的方法，這種方法可以減少原始感知數據直接或間接地參與到網內融合，有效地減少了數據傳輸量，此外，通過設置GM，在格內語義事件信息收集和融合時，不用傳遞地理位置信息.

現象2. 在每個不同NEN比例的網絡中，SERQ和voting的數據傳輸量都隨著k值的增加而較為緩慢地增長，而central始終保持不變.

Fig. 6 Data transmission comparison of three methods in 20 girds based network圖6 20個網格劃分下3種方法的數據傳輸量比較

解釋.顯而易見，central方法和k無關，因此它的數據傳輸量保持不變；而SERQ和voting方法中，k值的大小直接影響了網內融合時過濾的程度，而且k越小，過濾的事件區域信息越多，相應地總數據傳輸量越小，k增加時網內信息融合過程中需要保護的信息較多，因而網內數據傳輸量會增加.

現象3. 隨著NEN比例的增加，SERQ，voting，central的平均數據傳輸量都有相應的增加.

解釋. NEN比例增加，參與傳輸和融合的事件節點和事件區域都在增長，最容易理解的就是在central方法中，需要傳輸數據的節點增加，轉發跳數也在增加，這必然導致整個網絡數據傳輸量的增加.同理，在SERQ和voting中，增加的NEN可能出現在網絡的任何位置，顯而易見，增加的NEN信息需要參與傳輸和融合，這會增加數據傳輸量；此外如果增加的NEN位置遠離Sink或基站，網內傳輸的總跳數也會增加.

此外，我們還考察了每個格覆蓋節點數量對SERQ性能的影響，對于圖5，每個格平均覆蓋節點數為4.4；當GM通信半徑增加到100 m時，圖5可劃分成12個網格，這時每個網格平均覆蓋節點數為7.3，與圖5中20網格網絡實驗的設置和方法一樣，我們考察圖5中12個網格網絡中SERQ，voting，central方法的節能性.同樣4種NEN比例的網絡環境下，上述3種方法的數據傳輸量對比結果和20個網格網絡大致相同，在4種NEN比例的網絡環境下，SERQ的平均數據傳輸量約是voting的38.7%，以及central的17.7%左右，如圖7所示.其中原因和現象1的解釋相似，不再重復.

Fig. 7 Average data transmission comparison of 10%,20%,30% and 50% NENs in 12 girds based network圖7 12格網絡中4種NEN比例下平均數據傳輸量對比

4.3 準確度

同樣地，我們考察圖5網絡中3種不同NEN比例(10%，30%，50%)的網絡情況對于SERQ查詢結果準確性的影響.相同NEN比例的情況，重復做實驗10次，計算得到誤報數、漏報數和準確度的平均值.

這里說的誤報(false positive)有2種情況：1)孤立節點被當成事件區域；2)原本是1個事件區域，由于所處的格不同而被當成2個事件區域.漏報(false negative)是指由于SERQ算法的原因，那些原本屬于查詢結果的事件區域，沒有出現在結果集中，值得注意的是，如果SERQ中用戶指定的k值比實際事件區域數量小，而造成的漏報，我們不計入SERQ漏報性能評估，因為用戶不需要那么多查詢結果，這與SERQ算法無關.

在上述3種NEN比例情況下的事件區域誤報數和漏報數如表2～4所示:

Table 2 Average Number of False Positive and False Negative with 10% NEN

Table 3 Average Number of False Positive and False Negative with 30% NEN

Table 4 Average Number of False Positive and False Negative with 50% NEN

現象4. 表2～4沒有出現事件區域漏報，而出現少量的誤報.表2中的誤報主要是孤立NEN引起的誤報，10%的NEN，在k=2時，10組實驗有1個誤報；k=3時，10組實驗共有3個誤報；k=4時，10組實驗共有10個誤報；k=5時，10組實驗共有16個誤報.表4中，50% NEN的情況，這時的誤報是原本屬于1個事件區域被誤報成2個或更多的事件區域，如在k=3，4，5時，10組實驗分別有4，6，11個誤報.

解釋. 只要SERQ查詢中k值夠大，那么SERQ不會漏報潛在事件區域，也就是說除非用戶在SERQ查詢中設置較小k值，這會漏報一些潛在事件，但這種漏報和SERQ方法無關.

SERQ可能會有誤報，那些serc=0.5的事件區域內只有1個NEN，因此可能是一個誤報.如表2中，10%的NEN的情況，整個網絡中NEN數量較少，存在孤立NEN的概率較高，因此SERQ算法在k較大時，誤報的可能性增加.NEN的比例為50%時，網絡中有一半的NEN，這時的空間相關性比較復雜，事件區域往往橫跨幾個網格，尤其是本實驗的20網格，網格區域較小，事件區域更容易包含在幾個網格中，在SERQ中，由于不做嚴格的事件邊界檢測，而是以網格劃分事件區域(節能考慮)，因此在表4中，這種誤報出現的次數增加.

總體來說，SERQ結果的準確度很高，隨著k的增加和NEN比例的增加，準確度有所下降.

NEN比例不大的情況下，k值越小，SERQ會優先選擇那些serc大且事件區域代表點可信度高的事件區域，那些孤立的NEN由于serc小，幾乎沒有機會成為SERQ的結果.就像現象4中解釋的一樣，NEN比例較大時，事件區域可能會橫跨幾個網格，會造成一些誤報，從而降低了SERQ的準確度，但是從多組實驗看來，除非NEN分布完全沒有空間性規律(這也是不符合實際的)，否則SERQ的總體準確度還是非常高的.

5 總 結

本文探討了傳感器網絡中如何節能而可靠地獲取事件信息的問題，提出一種低功耗可靠的語義事件區域查詢處理方法.我們沒有利用全部的空間相關性進行事件信息確認，也不進行嚴格的事件區域邊界檢測，因為這些操作追求高可靠性而付出的時間和能耗代價非常高.本文借鑒了模糊方法中關于處理不精確性問題的思想，語義事件信息代替原始的感知數據用于網內事件信息的融合，并設計了基于模糊理論的分布式語義事件信息表示、過濾和融合算法.基于真實數據的仿真實驗驗證了所提出的方法在節能和可靠性方面的預期效果.

如何在可靠性、實時性和節能性之間取得最佳平衡以及本文所涉及的一些函數和參數在實際應用系統的設計等問題都值得進一步研究.

[1]Wu Tao, Cheng Qi. Online dynamic event region detection using distributed sensor networks[J]. IEEE Trans on Aerospace and Electronic Systems, 2014, 50(1): 393-405

[2]Dziengel N, Seiffert M, Ziegert M, et al. Deployment and evaluation of a fully applicable distributed event detection system in wireless sensor networks[J]. Ad Hoc Networks, 2016, 37(1): 160-182

[3]Xue Wenwei, Luo Qiong, Pung H K. Modeling and detecting events for sensor networks[J]. Information Fusion, 2011, 12(1): 176-186

[4]Amato G, Chessa S, Gennaroa C, et al. Querying moving events in wireless sensor networks[J]. Pervasive and Mobile Computing, 2015, 16(1): 51-75

[5]Ding Lei, Guo Ge. Distributed event-triggered H consensus filtering in sensor networks[J]. Signal Processing, 2015, 108(1): 365-375

[6]Brass P, Na H S, Shin C S. Local event boundary detection with unreliable sensors: Analysis of the majority vote scheme[J]. Theoretical Computer Science, 2015, 607(1): 96-112

[7]Ding Min, Cheng Xiuzhen. Robust event boundary detection in sensor networks—A mixture model approach[C] //Proc of the 28th IEEE Int Conf on Computer Communications. Piscataway, NJ: IEEE, 2009: 2991-2995

[8]Li Yinglong, Chen Hong, Zhao Suyun, et al. Efficient event prewarning for sensor networks with multi microenvironments[C] //Proc of the 19th European Conf on Parallel Processing. Berlin: Springer, 2013: 382-393

[9]Iqbal A, Murshed M. A hybrid wireless sensor network framework for range-free event localization[J]. Ad Hoc Networks, 2015, 27(1): 81-98

[10]Masud M, Christopher L, Shanika K. An adaptive elliptical anomaly detection model for wireless sensor networks[J]. Computer Networks, 2014, 64(1): 195-207

[11]Yang H, Chung C W, Kim M H. An efficient top-kquery processing framework in mobile sensor networks[J]. Data & Knowledge Engineering, 2016, 102(1): 78-95

[12]Li Yinglong, Yang Lianghuai, Lü Mingqi. Event-driven approximate top-kqueries in sensor networks with multi microenvironments[J]. Chinese Journal of Electronics, 2015, 24(2): 373-378

[13]Saleh O, Sattler A. Distributed complex event processing in sensor networks[C] //Proc of the 14th IEEE Int Conf on Mobile Data Management. Piscataway, NJ: IEEE, 2013: 23-26

[14]Xu Xiaolong, Geng Weijian, Yang Geng, et al. An efficient fault-tolerant event and event boundary detection algorithm for wireless sensor networks[J]. Journal of Computer Research and Development, 2014, 51(5): 997-1008 (in Chinese)(徐小龍, 耿衛建, 楊庚, 等. 高效容錯的無線傳感器網事件及其邊界檢測算法[J]. 計算機研究與發展, 2014, 51(5): 997-1008)

[15]Shi Shengfei, Zhang Wei, Li Jianzhong. A complex event detection algorithm based on correlation analysis[J]. Journal of Computer Research and Development, 2014, 51(8): 1871-1879 (in Chinese)(石勝飛, 張偉, 李建忠. 一種基于模式匹配與相關性分析的事件檢測算法[J]. 計算機研究與發展, 2014, 51(8): 1871-1879)

[16]Streit R L. Poisson Point Processes: Imaging, Tracking, and Sensing[M]. Berlin: Springer, 2010: 1-78

[17]Madden S, Franlin M J, Hellerstein J M, et al. TAG: A tiny aggregation service for ad-hoc sensor networks[C] //Proc of the 5th Symp on Operating Systems Design and Implementation. New York: ACM, 2002: 131-146

[18]Zhu Jiang, Lung C H, Srivastava V. A hybrid clustering technique using quantitative and qualitative[J]. Ad Hoc Networks, 2015, 25(1): 38-53

[19]Zhang Yang, Meratnia N, Havinga P. Outlier detection techniques for wireless sensor networks: A survey[J]. IEEE Communications Surveys & Tutorials, 2010, 12(1): 159-170

[20]Galindo J. Handbook of Research on Fuzzy Information Processing in Databases[M]. Hershey, Pennsylvania: IGI Global, 2008

[21]Kapitanova K, Son S H, Kang K D. Using fuzzy logic for robust event detection in wireless sensor networks[J]. Ad Hoc Networks, 2012, 10(1): 709-722

[22]OpenSim Ltd.. Discrete event simulator[EB/OL]. [2011-03-27]. http://www.omnetpp.org

[23]Martin V. Sensorscope: Sensor networks for environmental[DB/OL]. [2011-04-17]. http://sensorscope.epfl.ch/index.php/Environmental_Data

[24]Samuel M. Intel Lab Data[DB/OL]. [2011-05-18]. http://db.csail.mit.edu/labdata/labdata.html

Semantic Event Region Query Processing in Sensor Networks

Li Yinglong, Zhu Yihua, and Lü Mingqi

(College of Computer Science & Technology, Zhejiang University of Technology, Hangzhou 310023)

Sensor networks can be viewed as resources constrained distributed database systems, of which a significant challenge is to develop reliable, energy-efficient methods to extract useful information from distributed sensor data. Most of the existing event (region) detection approaches rely on using raw sensory data, which results in a large amount of data transmission as well as is time-consuming. However, it is difficult to ensure accurate results due to the imprecision and uncertainty of the raw sensor data. In many cases, users neither care about these raw sensory data nor pay attention to the data format during in-network filtering or fusion, but want to get natural language-like semantic event information, such as “how serious it is”, “is it credible?” Moreover, the main technique of the existing event detection is neighboring cooperation, which requires great data exchange between neighboring nodes. It is costly in terms of energy and time. This paper proposes a novel fuzzy methodology based semantic event region query processing approach. Semantic event information instead of raw sensor data is used for in-network fusion, and fuzzy method based distributed semantic event information description, filtering and fusion approaches are devised. The experimental evaluation based on real data set show that the proposed approach has good performance in terms of energy efficiency and reliability.

semantic event information; fuzzy methodology; energy efficiency; reliability; sensor network

Li Yinglong, born in 1981. PhD and lecturer. Member of CCF. His main research interests include data processing and mobile computing in sensor networks.

Zhu Yihua, born in 1961. PhD and professor. Senior member of CCF. His main research interests include the Internet of things (IoT), wireless networks, and network coding.

Lü Mingqi, born in 1981. PhD and lecturer. Member of CCF. His main research interests include ubiquitous computing, data mining.

2016-08-15；

2016-12-20

國家自然科學基金項目(61502421，61432015)；浙江省自然科學基金項目(LY15F020026，LY15F020025) This work was supported by the National Natural Science Foundation of China (61502421, 61432015) and the Natural Science Foundation of Zhejiang Province of China (LY15F020026, LY15F020025).

朱藝華(yhzhu@zjut.edu.cn)

TP391; TP393