唐 琪，劉學軍

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

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

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

1 相關(guān)研究

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

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

2 時空關(guān)聯(lián)分布式離群數(shù)據(jù)檢測算法

2.1 網(wǎng)絡結(jié)構(gòu)

2.1.1 簇的劃分

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

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

數(shù)據(jù)傳輸階段，傳感器節(jié)點連續(xù)采集數(shù)據(jù)，傳給簇頭，然后簇頭在進行必要的數(shù)據(jù)聚集和融合之后，發(fā)送到Sink節(jié)點。此階段持續(xù)一段時間后，進入下一輪，不斷地循環(huán)。分簇的無線傳感器網(wǎng)絡結(jié)構(gòu)如圖1所示。

圖1 分簇無線傳感器網(wǎng)絡結(jié)構(gòu)

2.1.2 網(wǎng)絡模型

2.2 數(shù)據(jù)預處理

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

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

2.3 基于時空關(guān)聯(lián)的分布式離群數(shù)據(jù)檢測算法

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

2.3.1 算法基本概念

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

定義1 數(shù)據(jù)對象Xi相對于數(shù)據(jù)對象Xp的加權(quán)距離:

其中ωl表示數(shù)據(jù)對象屬性l的權(quán)重，xil表示數(shù)據(jù)對象Xi在屬性l上的值，xpl表示數(shù)據(jù)對象Xp在屬性l上的值。

定義2 數(shù)據(jù)對象Xi的第k距離:

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

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

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

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

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

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

定義6 局部離群因子:

2.3.2 算法描述

(1)算法步驟詳述

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

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

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

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

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

(2)算法偽代碼

3 算法實驗分析

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

3.1.1 網(wǎng)絡能量消耗

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

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

3.1.2 精確度比較

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

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

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

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

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

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

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

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

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

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

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

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

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

4 總結(jié)與展望

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

［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］ 周賢偉，王培，覃伯平，等.一種無線傳感器網(wǎng)絡異常檢測技術(shù)研究［J］.傳感技術(shù)學報，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］ 張衛(wèi)旭，尉宇.基于密度的局部離群點檢測算法［J］.計算機與數(shù)字工程，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］ 姜旭寶，李光耀，連朔.基于變寬直方圖的無線傳感器網(wǎng)絡異常數(shù)據(jù)檢測算法［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協(xié)議的研究與改進［J］.計算機應用，2009，29(12):3241－3243.

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

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

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