無線傳感器網絡分布式離群數據檢測研究*

唐 琪，劉學軍

(南京工業大學電子與信息工程學院，南京211816)

在無線傳感器網絡中，偏離正常模式的感知數據被認為是離群數據。離群數據［1］的可能來源包括網絡中的噪聲、異常事件、惡意攻擊等等。在某些重要的傳感器網絡應用中，如火災監測、環境和棲息地檢測［2］、欺詐和入侵檢測［3］、目標追蹤、戰場觀測等，這些離群數據通常起著十分重要的作用。基于無線傳感器網絡的離群數據檢測技術也越來越受到人們的關注。離群數據檢測的算法有基于統計的、基于偏差的、基于聚類的、基于距離［4］的、基于密度［5－6］的等等。基于密度的離群數據檢測算法可以發現任意形狀的數據布局中的離群數據，它是根據讀數的所有維度計算讀數之間的距離，再通過局部離群因子來判定離群數據的存在與否，離群因子愈大，數據就更可能離群，反之則可能性愈小。無線傳感器網絡的離群點檢測分為集中式方法和分布式方法。集中式方法是將每個傳感器感知的數據直接傳送給Sink節點，Sink節點采用一定的算法對全部數據進行離群點檢測，該方法由于需要傳輸大量的數據，加快了能量的消耗。分布式方法是每個傳感器節點對感知數據進行本地檢測，做出本地判決，只把這種本地結論及其相關信息向Sink節點傳送，然后由Sink節點在更高層次上綜合多方面的數據進一步完成處理，獲得最終的判決結論，這種方法相對集中式方法節省了能量的消耗，提高了網絡的生存周期，從而延長了網絡的壽命。

本文提出了一種基于密度的分布式離群數據檢測算法，并通過引入時空關聯性有效提高了檢測精度。為了更精確地檢測到離群數據，在傳感器節點采集到的數據中，不同的屬性賦予了不同的權重。本文后續內容如下:第2節介紹了相關的研究工作;第3節提出了一種無線傳感器網絡分布式的離群數據檢測算法;第4節通過實驗分析了分布式離群數據檢測算法的性能;第5節總結了全文。

1 相關研究

離群點又名孤立點，偏差點，異常點等，是數據集中偏離大部分數據的數據，并懷疑這些數據的異常產生于不同的機制而不是產生于隨機因素。研究人員最開始提出了基于統計的離群點檢測算法，后來陸陸續續地提出了各種各樣的離群點檢測方法。Zhang Yang等人對傳感器網絡的離群點檢測技術進行了綜述，詳細地分析了傳感器網絡中離群點檢測的意義、應用領域以及相關算法等。SHENG Bo［7］利用直方圖提取分布特征，不需要傳輸網絡中的全部數據，降低了通信開銷，但該算法僅對一維數據適合，不適合多維數據。姜旭寶［8］等人提出了基于變寬的直方圖的異常數據檢測算法，通過數據聚合的方式將網絡中的動態感知數據聚合成變寬的直方圖來檢測出異常數據，避免不必要的數據傳輸，也有效降低了通信開銷。V.S.Kumar Samparthi［9］等人提出了基于核密度估計的分布式多維數據離群點檢測算法。張天佑等人提出的SLDF算法，適用于高維大數據集［10－11］的空間離群點檢測，但是，它只考慮了空間數據集的問題。

以上這些方法都只是從時間或空間的單一角度進行離群點檢測的研究，而本文在基于分簇的無線傳感器網絡環境中，綜合考慮了時間和空間的相關性以及屬性權重等方面，提出了基于密度的時空關聯的分布式離群數據檢測算法TSLOF(Time and Space Local Outlier Factors)。

2 時空關聯分布式離群數據檢測算法

2.1 網絡結構

2.1.1 簇的劃分

為實現無線傳感器網絡分布式離群數據檢測，本文采用的是LEACH協議［12］，它是一種典型的分簇路由協議，定義了“輪”的概念，每一輪有簇頭的形成和數據傳輸兩個階段。簇頭的形成階段:每一個傳感器節點從0到1隨機選取一個數，若小于這輪設定的門限值T(m)，則選為簇頭。T(m)的計算公式如下:

其中，p是節點成為簇頭的百分比，r是當前的輪數，G是在最后的rmod(1/p)輪中還沒有擔當簇頭的節點集合。

數據傳輸階段，傳感器節點連續采集數據，傳給簇頭，然后簇頭在進行必要的數據聚集和融合之后，發送到Sink節點。此階段持續一段時間后，進入下一輪，不斷地循環。分簇的無線傳感器網絡結構如圖1所示。

圖1 分簇無線傳感器網絡結構

2.1.2 網絡模型

2.2 數據預處理

本文主要對傳感器節點采集的數據進行兩個方面的數據預處理。一方面是基準化。由于環境影響著傳感器節點采集的數據，有時，不同的節點采集的正常數據可能有較大的差異，在計算空間局部離群因子時，容易把某些差異較大的正常數據誤判為異常數據。為避免這種情況的發生，可以給每個傳感器的讀數指定一個基準值，傳感器節點采集的數據除以該基準值，就得到了它的計算值，這一過程被稱為基準化。離群點的計算是采用計算值進行的。每個傳感器節點都有獨立的基準值，通常取該節點正常讀數的平均值。通過基準化，可以降低將差異較大的正常數據誤判為異常數據的可能性，從而提高離群數據檢測的準確度。計算值的公式為:

另一方面是歸一化，即將有量綱的數據化為無量綱的數據，數值歸一到0和1之間。在某些傳感器網絡的應用中，節點接收到的數據是多維的，不同的屬性之間取值差異可能較大，在計算距離時，對各維的讀數進行歸一化，可以消除取值范圍不同、計量單位不同對結果帶來的不利影響。

2.3 基于時空關聯的分布式離群數據檢測算法

算法分為三個階段:第一階段為簇成員節點利用滑動窗口機制檢測時間離群數據并發給簇頭節點;第二階段為簇頭節點檢測簇成員節點之間的時空離群數據并發給Sink節點;第三階段為Sink節點檢測各個簇頭節點傳送來的離群數據并得到所期望的離群數據。

2.3.1 算法基本概念

采用滑動窗口機制［14］，假設一個窗口寬度為B，每隔Δ時間傳感器接收一個讀數，且是在正常情況下，一個窗口B的讀數數量為a個，即B=Δa。

定義1 數據對象Xi相對于數據對象Xp的加權距離:

其中ωl表示數據對象屬性l的權重，xil表示數據對象Xi在屬性l上的值，xpl表示數據對象Xp在屬性l上的值。

定義2 數據對象Xi的第k距離:

該定義通過研究每一個對象與被研究對象之間的距離并找出其數值上為第k大的距離，來確定一個針對被研究對象的個性化的局部空間區域的范圍，對于被研究對象密度較大的區域，該數值一般情況下較小;對于被研究對象密度較小的區域，該數值一般情況下則較大。對象Xi滿足:至少有與k個對象 Xq的加權距離滿足 dist(Xi，Xq，ω)≤dist(Xi，Xj，ω);最多有k－1個對象Xq的加權距離滿足dist(Xi，Xq，ω)＜dist(Xi，Xj，ω)。

定義3 數據對象Xi的第k距離鄰域:所有到數據對象Xi的加權距離小于或等于數據對象Xi的第k距離的數據對象的集合。記作:Nb(Xi)。該定義是以被研究對象為圓心，該數據對象的第k距離為半徑的區域內的所有數據對象的集合。

定義4 k是一個給定的自然數，對象Xi對于對象Xj的可達距離:

當對象Xi遠離對象Xj時，對象Xi關于對象Xj的可達距離就是它們之間的距離 dist(Xi，Xj，ω)，即dist(Xi，Xj，ω)＞k－distance(Xj)。當對象 Xi靠近對象Xj時，對象Xi關于對象Xj的可達距離就是對象Xj的k距離。

定義5 對象Xi的可達密度:

其中，Nb(Xi)為對象Xi的第k距離鄰域。該定義首先計算數據對象Xi的第k鄰域內的所有數據對象到數據對象Xi的所有距離之和，再計算其所有距離之和的平均值。可達密度使用了對象Xi的k近鄰的平均可達距離的倒數來度量密度對象Xi，反映了Xi附近的數據分布情況。顯然，當對象Xi的周圍分布稀疏時，其局部可達密度會相應比較小。

定義6 局部離群因子:

2.3.2 算法描述

(1)算法步驟詳述

第1階段，簇成員節點檢測時間離群數據:每個簇內的簇成員節點之間不進行互相通信，每個簇成員節點在一個窗口B中計算得到n'個時間局部離群因子TLOF(Xi)值最大的讀數，值TLOF(Xi)根據定義6求得。簇成員節點將檢測到的時間離群數據傳送給簇頭節點。

第2階段:簇頭節點接收簇成員節點的時間離群數據，并計算這些數據的空間局部離群因子SLOF(Xi)，值SLOF(Xi)也是根據定義6求得。將時間局部離群因子和空間局部離群因子結合起來稱為時空局部離群因子TSLOF，如式(8)所示。通過降序排序，將每個簇的n個TSLOF值最大的候選離群數據傳送給Sink節點。

其中ρ∈［0，1］，決定了時間局部離群因子和空間局部離群因子的比例，ρ越大，時間局部離群因子所占的比例越大，ρ越小，空間局部離群因子所占比例越大。

第3階段:Sink節點接收到的n×M個離群數據，通過空間局部離群因子SLOF求得top－n個離群數據。

上述描述中的n'和n由用戶指定。

(2)算法偽代碼

3 算法實驗分析

在200 m×200 m的區域內隨機部署200個傳感器節點和一個基站Sink。分為兩種情況，一種是不分簇的網絡，另一種是5%的傳感器成為簇頭的網絡，都是單跳通信。設節點初始能量為0.5 J，發送和接收能耗均為0.395 nJ/bit，空閑能耗為0.039 nJ/bit，放大電路功耗 100 pJ/(bit·m2)，通信距離為50 m，仿真時間為1 000 s，數據分組大小為512 byte，MAC 層協議為 IEEE 802.11，ρ＜0.5，傳感器節點采集的數據維度d=2，以溫度、濕度為屬性數據。溫度的權值高于濕度的權值。

3.1.1 網絡能量消耗

以30 s為一個時間窗口，設節點采集異常讀數的速度為4個/s，在一個時間窗口內，傳感器節點采集的異常讀數總數為120個。圖2給出了無線傳感器網絡時空關聯的集中式和分布式離群數據檢測的能耗比較。時空關聯的集中式離群數據檢測是指在沒有分簇的無線傳感器網絡中時空關聯的離群數據檢測。從圖中可以看出，集中式離群數據檢測的無線傳感器網絡比時空關聯的分布式離群檢測無線傳感器網絡的能量消耗要快些，這是因為集中式離群數據檢測將大量數據的直接傳輸給Sink節點，而分布式離群數據檢測會將一部分數據傳輸給簇頭節點，再由簇頭將一小部分數據傳輸給Sink節點，因此，集中式離群數據檢測能量消耗過快。

圖2 分布式與集中式能耗對比

3.1.2 精確度比較

以30 s為一個時間窗口，傳感器節點采集到的異常讀數的速度分別為 1個/s，2個/s，4個/s，6個/s，8個/s，即在一個窗口內，傳感器節點采集的異常讀數總數分別為30個、60個、120個、180個、240個，對這5組數據集進行離群數據檢測，離群數據檢測的精確度采用式(9)的方法:

(1)時空關聯的分布式檢測算法與集中式檢測算法檢測精度對比

從圖3可知，當傳感器節點采集數據較少時，集中式離群數據檢測精度與分布式離群數據檢測精度相同;當傳感器節點采集數據較多時，集中式離群數據檢測精確度也只略好于分布式離群數據檢測精確度，分布式離群數據檢測保持了較高的檢測精度。主要原因是集中式離群數據檢測是在傳感器節點檢測離群數據之后，將所有時間離群數據直接傳送給Sink節點，而分布式離群數據檢測是經過簇頭的篩選之后再傳送給Sink節點，有可能會漏掉某些離群數據。

圖3 分布式算法與集中式算法精確度比較

(2)時空關聯的分布式檢測算法與只考慮空間的分布式檢測算法檢測精度對比

圖4顯示了時空關聯的分布式離群數據檢測算法(也稱為TSLOF算法)與只考慮空間的分布式離群數據檢測算法(也稱為SLOF算法)的檢測精度比較。由于TSLOF算法既考慮了傳感器節點的時間因素也考慮了空間因素，而SLOF算法只考慮了空間因素，忽略了傳感器節點的時間因素，因此前者檢測精確度高于后者檢測精確度。

圖4 TSLOF算法與SLOF算法精確度對比

3.1.3 TSLOF算法與OTOD算法性能比較

由于本文所提出的TSLOF算法與薛安榮等人提出的OTOD算法［15］都是無線傳感器網絡中考慮時空關聯性的異常數據檢測算法，兩者比較類似。因此實驗將兩種算法進行性能比較。

圖5顯示了TSLOF算法和OTOD算法的能量消耗比較。從圖5可以看出，TSLOF能耗明顯低于OTOD算法。主要原因是:OTOD算法中，各節點需要將其潛在的離群數據通過多跳傳送到Sink節點，因此，需要傳輸大量的數據，而TSLOF算法中，各簇成員節點將其時間離群數據傳送給它的簇頭，簇頭對數據進行處理、融合，再將少量時空離群數據傳給Sink節點。顯然，TSLOF算法的能耗明顯低于OTOD算法。

圖5 TSLOF算法與OTOD算法能耗對比

我們也對TSLOF算法和OTOD算法的檢測精度進行了比較。從圖6可以看出，兩種算法的檢測精度比較接近。但是，OTOD算法是通過與相鄰節點的比較來判定一個節點的數據是否為異常數據，當該節點的相鄰節點都為全局離群數據時，可能會將該節點的離群數據誤判為正常數據，在這種情況下，OTOD算法的檢測精度會大大下降。本文提出的TSLOF算法由于時空離群點的判定是在簇頭節點實現的，可以避免上述問題。

圖6 TSLOF算法與OTOD算法精確度對比

4 總結與展望

本文提出的無線傳感器網絡時空關聯的分布式離群數據檢測算法，與集中式離群數據檢測算法相比節省了能量消耗，同時也保持了較高的檢測精度，時空關聯的分布式離群數據檢測精確度高于只考慮空間因素的分布式離群數據檢測精確度，并且通過實驗驗證了這幾點。在實際應用中，可以通過調整ρ的大小來確定時間和空間因素所占比重的大小。接下來的工作是將我們提出的算法與實際應用相結合，并考慮簇之間的權重問題，使離群數據檢測算法的準確率得到更有效的提高。

［1］ Zhang Yang，Nirvana Meratnia，Paul Havinga.Outlier Detection Techniques for Wireless Sensor Networks:A Survey［J］.IEEE Communications Surveys ＆ Tutorials，2010，12(2):1－12.

［2］ Annie H Liu，Julian J Bunn，K Mani Chandy.Sensor Networks for the Detection and Tracking of Radiation and Other Threats in Cities［C］//The 10th International Conference on Information Processing in Sensor Networks.Chicago:IPSN，2011:1－12.

［3］ 周賢偉，王培，覃伯平，等.一種無線傳感器網絡異常檢測技術研究［J］.傳感技術學報，2007，20(8):1870－1874.

［4］ Vu N H，Gopalkrishnan V.Efficient Pruning Schemes for Distance-Based Outlier Detection［C］//Proc.of the European Conference on Machine Learning and Knowledge Discovery in Databases.2009:160－175.

［5］ 薛安榮，鞠時光，何偉華，等.局部離群點挖掘算法研究［J］.計算機學報，2007，30(8):1455－1463.

［6］ 張衛旭，尉宇.基于密度的局部離群點檢測算法［J］.計算機與數字工程，2010，38(10):11－14.

［7］ Sheng Bo，Li Qun，Mao Wei-zhen.Outlier Detection in Sensor Networks［C］//Proc of the 8th ACM International Symposium on Mobile Ad hoc Networking and Computing.New York:ACM Press，2007:219－228.

［8］ 姜旭寶，李光耀，連朔.基于變寬直方圖的無線傳感器網絡異常數據檢測算法［J］.計算機應用，2011，31(3):694－697.

［9］ Kumar Samparthi V S，Harsh K Verma.Outlier Detection of Data in Wireless Sensor Networks Using Kernel Density Estimation［J］.International Journal of Computer Applications，2010，5(7):26－32.

［10］ Subramaniam S，Palpanas T，Papadopoulos D.Online Outlier Detection in Sensor Data Using Non-Paramemer Model［C］//Prnc of the 32th International Conference on Very Large Data Bases，2006:187－198.

［11］ Angiulli F，Pizzuti C.Outlier Mining in Large Highdimensional Data Sets［J］.IEEE Transactions on Knowledge and Data Engineering，2005，17(2):203－215.

［12］陳雪嬌，李向陽.WSN中LEACH協議的研究與改進［J］.計算機應用，2009，29(12):3241－3243.

［13］孫雨耕，周寅，邊桂年，等.無線傳感器網絡中一種能量有效的分簇組網算法［J］.傳感技術學報，2007，20(2):377－381.

［14］杜威，鄒先霞.基于數據流的滑動窗口機制的研究［J］.計算機工程與設計，2005，26(11):2922－2924.

［15］薛安榮，李明.無線傳感器網絡中異常讀數檢測算法研究［J］.計算機應用研究，2010，27(9):3452－3455.