唐 琪，劉學(xué)軍

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

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

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

1 相關(guān)研究

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

以上這些方法都只是從時間或空間的單一角度進(jìn)行離群點檢測的研究，而本文在基于分簇的無線傳感器網(wǎng)絡(luò)環(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)絡(luò)結(jié)構(gòu)

2.1.1 簇的劃分

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

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

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

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

2.1.2 網(wǎng)絡(luò)模型

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

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

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

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

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

2.3.1 算法基本概念

采用滑動窗口機(jī)制［14］，假設(shè)一個窗口寬度為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的可達(dá)距離:

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

定義5 對象Xi的可達(dá)密度:

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

定義6 局部離群因子:

2.3.2 算法描述

(1)算法步驟詳述

第1階段，簇成員節(jié)點檢測時間離群數(shù)據(jù):每個簇內(nèi)的簇成員節(jié)點之間不進(jìn)行互相通信，每個簇成員節(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)隨機(jī)部署200個傳感器節(jié)點和一個基站Sink。分為兩種情況，一種是不分簇的網(wǎng)絡(luò)，另一種是5%的傳感器成為簇頭的網(wǎng)絡(luò)，都是單跳通信。設(shè)節(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)絡(luò)能量消耗

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

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

從圖3可知，當(dāng)傳感器節(jié)點采集數(shù)據(jù)較少時，集中式離群數(shù)據(jù)檢測精度與分布式離群數(shù)據(jù)檢測精度相同;當(dāng)傳感器節(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)絡(luò)中考慮時空關(guān)聯(lián)性的異常數(shù)據(jù)檢測算法，兩者比較類似。因此實驗將兩種算法進(jìn)行性能比較。

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

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

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

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

4 總結(jié)與展望

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

［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)絡(luò)異常檢測技術(shù)研究［J］.傳感技術(shù)學(xué)報，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］.計算機(jī)學(xué)報，2007，30(8):1455－1463.

［6］ 張衛(wèi)旭，尉宇.基于密度的局部離群點檢測算法［J］.計算機(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)絡(luò)異常數(shù)據(jù)檢測算法［J］.計算機(jī)應(yīng)用，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ìn)［J］.計算機(jī)應(yīng)用，2009，29(12):3241－3243.

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

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

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