翟小超

(西安電子科技大學(xué)數(shù)學(xué)與應(yīng)用數(shù)學(xué)，陜西西安 710071)

無線傳感網(wǎng)絡(luò)WSNs由大量微小、低消耗的傳感器節(jié)點通過無線通信連接構(gòu)成。許多網(wǎng)絡(luò)被部署在無人監(jiān)督的惡劣環(huán)境中。出于費用考慮，傳感器節(jié)點通常是低成本、低質(zhì)量的。傳感器的低質(zhì)量和惡劣的部署環(huán)境導(dǎo)致傳感器采集到的數(shù)據(jù)中存在大量的誤差、錯誤、丟失值、重復(fù)值和不一致數(shù)據(jù)。傳感網(wǎng)絡(luò)中數(shù)據(jù)本身的不可靠性使得難以將這些數(shù)據(jù)用于有意義的科學(xué)研究。異常值是導(dǎo)致網(wǎng)絡(luò)數(shù)據(jù)不可靠的主要原因之一，所以無線傳感網(wǎng)絡(luò)中數(shù)據(jù)的異常值檢測受到越來越廣泛的重視。

異常值檢測的研究源于數(shù)據(jù)挖掘領(lǐng)域?，F(xiàn)存文獻中存在大量的異常值檢測方法，例如支持向量機，聚類方法，統(tǒng)計學(xué)方法，基于臨近點的方法等［1］。在文獻［2］中，作者給出了一種支持向量機的異常值檢測方法。但這種方法需要每隔一段時間傳感器采集到足夠多的數(shù)據(jù)后才能對收集的數(shù)據(jù)進行檢測，不是一種實時的線上檢測方法。文獻［3～4］構(gòu)建了一個樸素貝葉斯分類器用于異常值檢測。這種方法實現(xiàn)了線上實時的異常檢測，且還可近似地預(yù)測網(wǎng)絡(luò)中的丟失數(shù)據(jù)。然而，這種方法僅適用于一維數(shù)據(jù);再次，這種方法事先需要一個訓(xùn)練集來學(xué)習(xí)分類器參數(shù)，大多數(shù)情況下一個好的訓(xùn)練集難以獲得。文獻［5］利用PCA技術(shù)識別出局部異常值。然而，PCA方法事先需要一個訓(xùn)練集來計算主元，且在選取合適主元時計算復(fù)雜度較高。文獻［6］給出了一種新的橢圓異常定義。當數(shù)據(jù)集的形狀是超橢球時，這種方法檢測的準確率比較高，然而，當數(shù)據(jù)集是不規(guī)則的幾何形狀時，檢測結(jié)果是不可信的。

在無線傳感網(wǎng)絡(luò)中，傳感器節(jié)點按照固定的時間間隔不斷地捕獲數(shù)據(jù)，傳感器捕獲的每一個數(shù)據(jù)都帶有一個唯一的時間戳。上述文獻中除了文獻［3～4］，均未考慮到傳感器采集到的數(shù)據(jù)本身在時間上的連續(xù)性。鑒于此，本文從傳感網(wǎng)絡(luò)數(shù)據(jù)在時間上的相關(guān)性角度出發(fā)，提出了一種針對無線傳感網(wǎng)絡(luò)的可變閾值異常值檢測方法，在無需事先獲取訓(xùn)練集的前提下，實現(xiàn)了對傳感器采集數(shù)據(jù)的線上實時的異常檢測。

針對本文模型作如下假設(shè):(1)網(wǎng)絡(luò)中傳感器采集數(shù)據(jù)的時間間隔不可過長，不超過5分鐘。(2)網(wǎng)絡(luò)中的數(shù)據(jù)符合馬爾科夫假設(shè)不會發(fā)生突變。

1 數(shù)據(jù)異常因子

在眾多異常值檢測方法中存在著一種既直觀又簡單的方法——利用相鄰點之間的距離來判斷異常值。如果當前數(shù)據(jù)點距離上一時刻數(shù)據(jù)點的距離超過某一范圍，就認為該點是一個異常點。

如圖1所示，數(shù)據(jù)點1，2，3，4，5 均是正常數(shù)據(jù)點，顯然數(shù)據(jù)點6是一個異常數(shù)據(jù)點。然而6，7之間的距離與6，5之間的距離基本一樣，若依照相鄰點間的距離來判斷異常點，7也將被檢測為異常，但觀察圖1會發(fā)現(xiàn)數(shù)據(jù)點7應(yīng)該是正常的，這樣數(shù)據(jù)點7則被誤報。為避免上述誤報，做如下定義。

圖1 異常值示意圖

定義1 (Normal Hop Distance)數(shù)據(jù)點obj(k)為傳感器在t時刻捕獲的數(shù)據(jù)，設(shè)t時刻之前捕獲的數(shù)據(jù)之中已被檢測為正常的，且在時間上距離obj(k)最近的數(shù)據(jù)點記為obj(i)，則當前數(shù)據(jù)點obj(k)的正常跳距離為

其中，式(1)中的距離dist(obj(k)，obj(i))表示數(shù)據(jù)點obj(k)到數(shù)據(jù)點obj(i)的馬氏距離。

其中，∑ =cov(D)為數(shù)據(jù)集D的協(xié)方差矩陣。

在計算兩個數(shù)據(jù)之間的距離時，通常采用的是歐氏距離，但歐氏距離在計算時，是將數(shù)據(jù)中的所有屬性都等同對待的，而馬氏距離在計算時，則會根據(jù)數(shù)據(jù)集自身的特點，調(diào)節(jié)各屬性對最終結(jié)果的貢獻率。對于一個二維數(shù)據(jù)，在歐氏距離下，數(shù)據(jù)點的δ鄰域是一個圓，而在馬氏距離下，數(shù)據(jù)點的δ鄰域是一個橢圓。如圖2所示，分別為數(shù)據(jù)集中同一個數(shù)據(jù)點，在馬氏距離與歐氏距離下的δ鄰域?？煽闯?，在馬氏距離下的δ鄰域所畫出的橢圓，其長軸方向正是數(shù)據(jù)集變化的主要方向，而短軸方向恰是數(shù)據(jù)集變化幅度最小的方向。即馬氏距離能提取數(shù)據(jù)集的特征，并將其體現(xiàn)在數(shù)據(jù)的δ鄰域上。因此，本文計算距離時均采用馬氏距離。

圖2 同一點在馬氏距離下的δ鄰域和在歐氏距離下的δ鄰域

定義2 (Outlier Factor)設(shè)傳感器在t時刻捕獲的數(shù)據(jù)點為obj(k)，則當前數(shù)據(jù)點obj(k)的異常因子為

其中，δ(k)為當前數(shù)據(jù)obj(k)對應(yīng)的動態(tài)閾值。

根據(jù)每個數(shù)據(jù)點異常因子的大小可將數(shù)據(jù)集D中的數(shù)據(jù)分為3種狀態(tài):

正常態(tài):若數(shù)據(jù)點obj(k)的異常因子 OF(k)∈［0，1］;

臨界態(tài):若數(shù)據(jù)點obj(k)的異常因子 OF(k)∈(1，trustvalue］;

異常態(tài):若數(shù)據(jù)點obj(k)的異常因子 OF(k)∈(trustvalue，+∞］。

其中，trustvalue是一個＞的參數(shù)。

在實際部署的網(wǎng)絡(luò)中，傳感器可能受到各種未知的影響，從自然界中捕獲的實時數(shù)據(jù)常常會呈鋸齒狀上升或下降，即數(shù)據(jù)處于不確定的波動中。在這些波動中，有些數(shù)據(jù)的波動處于合理的范圍;而有些波動則較嚴重，是由異常值導(dǎo)致的。有鑒于此，本文在正常態(tài)與異常態(tài)之間引入臨界態(tài)，并通過參數(shù)trustvalue來控制臨界態(tài)的大小。參數(shù)trustvalue的值越小檢測越嚴格，參數(shù)trustvalue的值越大檢測越寬松。在現(xiàn)實使用中，可根據(jù)網(wǎng)絡(luò)部署環(huán)境和實際檢測的需要來調(diào)節(jié)參數(shù)trustvalue。

本文借用無罪推定的法律原則，即任何人在被宣判有罪之前都推定為無罪，只有那些處于異常態(tài)的數(shù)據(jù)才被認為是異常值。

2 檢測方法

在定義1和2的基礎(chǔ)上，給出本文的檢測策略和動態(tài)閾值δ(k)的更新方法。

對于t時刻采集到的數(shù)據(jù)obj(k)，在已知對應(yīng)的閾值δ(k)的情況下可得到異常因子OF(k)，并通過異常因子來判斷當前數(shù)據(jù)所處的狀態(tài)。若obj(k)處于異常態(tài)則認為其是一個異常值，否則認為其是一個正常值。然后，利用前一時刻數(shù)據(jù)obj(k－1)所處的狀態(tài)和當前數(shù)據(jù)所處的狀態(tài)，以及當前的閾值δ(k－1)，確定下一時刻的閾值。依照上述策略，即可實現(xiàn)對傳感器采集數(shù)據(jù)的線上實時的檢測。其具體實現(xiàn)包括如下步驟:

步驟1 部署傳感網(wǎng)絡(luò)，開始采集數(shù)據(jù);

步驟2 傳感器采集到初始m個數(shù)據(jù)后，計算δ(m);

步驟3 根據(jù)設(shè)定的動態(tài)閾值更新更新機制得到δ(m+1);

步驟4 傳感器捕獲到第i個數(shù)據(jù)obj(i)，計算OF(i)，然后判斷第i個數(shù)據(jù)所處的狀態(tài)，如果第i個數(shù)據(jù)處于異常態(tài)，判定obj(i)是一個異常值;

步驟5 根據(jù)設(shè)定的更新機制，利用obj(i－1)的狀態(tài)，obj(i)的狀態(tài)以及當前的δ(i)，得到下一時刻的閾值δ(i+1);

步驟6 重復(fù)步驟4和步驟5直到傳感器停止采集數(shù)據(jù)。

其中，步驟2中假設(shè)傳感器節(jié)點采集到的前m個數(shù)據(jù)都是正常的，δ(m)可取為

經(jīng)典馬爾科夫假設(shè)認為，下一時刻的狀態(tài)僅與當前時刻狀態(tài)有關(guān)，而與以前狀態(tài)無關(guān)。但將其應(yīng)用于本模型時仿真效果并不好。這里假設(shè)下一時刻的狀態(tài)僅與當前時刻的狀態(tài)和前一時刻的狀態(tài)有關(guān)，而與前一時刻之前的狀態(tài)無關(guān)。分析傳感網(wǎng)絡(luò)中數(shù)據(jù)集的特征，同時進行大量的仿真實驗，制定了如圖3所示的閾值更新機制。

圖3 動態(tài)閾值更新機制

假設(shè)當前數(shù)據(jù)為obj(i)，已知前一個數(shù)據(jù)的狀態(tài)，當前數(shù)據(jù)狀態(tài)和當前閾值，按照圖3所示的更新規(guī)律，給出如下的更新方法:(1)數(shù)據(jù)obj(i－1)處于正常態(tài)，數(shù)據(jù)obj(i)處于臨界態(tài)，新閾值δ(i+1)在閾值δ(i)的基礎(chǔ)上適度增大。(2)數(shù)據(jù)obj(i－1)處于正常態(tài)，數(shù)據(jù)obj(i)處于異常態(tài)，新閾值保持不變。(3)數(shù)據(jù)obj(i－1)處于臨界態(tài)，數(shù)據(jù)obj(i)處于異常態(tài)，新閾值δ(i+1)在閾值δ(i)的基礎(chǔ)上適度增大。(4)數(shù)據(jù)obj(i－1)處于臨界態(tài)，數(shù)據(jù)obj(i)處于正常態(tài)，新閾值維持不變。(5)數(shù)據(jù)obj(i－1)處于異常態(tài)，數(shù)據(jù)obj(i)處于臨界態(tài)，新閾值維持不變。(6)數(shù)據(jù)obj(i－1)處于異常態(tài)，數(shù)據(jù)obj(i)處于正常態(tài)，新閾值δ(i+1)在閾值δ(i)的基礎(chǔ)上減小。(7)數(shù)據(jù)obj(i－1)處于正常態(tài)，數(shù)據(jù)obj(i)處于正常態(tài)，新閾值δ(i+1)在閾值δ(i)的基礎(chǔ)上適度減小。(8)數(shù)據(jù)obj(i－1)處于異常態(tài)，數(shù)據(jù)obj(i)處于異常態(tài)，新閾值 δ(i+1)在閾值δ(i)的基礎(chǔ)上增大。(9)數(shù)據(jù)obj(i－1)處于臨界態(tài)，數(shù)據(jù)obj(i)處于臨界態(tài)，新閾值δ(i+1)應(yīng)等于當前NHD(i)。

相比現(xiàn)有技術(shù)，本文模型具有如下優(yōu)點:(1)在無需訓(xùn)練集的條件下，實現(xiàn)了對傳感器數(shù)據(jù)的線上實時的檢測。(2)可通過調(diào)節(jié)參數(shù)trustvalue來調(diào)節(jié)檢測的松緊度，以適應(yīng)各種不同環(huán)境下的檢測要求。(3)在檢測數(shù)據(jù)過程中，無需額外的數(shù)據(jù)通信，故適用于多種拓撲的無線傳感器網(wǎng)絡(luò)，包括在動態(tài)的網(wǎng)絡(luò)。

3 仿真實驗

仿真實驗是在一臺4 GB內(nèi)存，賽揚雙核2.6 GHz，32位Win7操作系統(tǒng)下，使用Matlab 2010b進行的。在仿真實驗中，取m=5，即假設(shè)傳感器初始采集到的前5個數(shù)據(jù)均是正常的。采用人工生成的數(shù)據(jù)集D來檢測本文算法。數(shù)據(jù)集D如圖4所示，共包含400條數(shù)據(jù)。首先，對數(shù)據(jù)集添加一定數(shù)目的隨機噪聲點后得到帶有噪聲的數(shù)據(jù)集，然后對新數(shù)據(jù)集使用本文的算法進行檢測，以此來檢驗算法的性能。

圖4 生成數(shù)據(jù)D集示意圖

圖5 閾值動態(tài)變化示意圖

生成的數(shù)據(jù)集D由中心相同短軸相同長軸不同的2個橢圓構(gòu)成，數(shù)據(jù)從文中圖4紅星處開始也在此處結(jié)束，正好形成2個完整的橢圓。生成數(shù)據(jù)集中相鄰點之間的距離變化趨勢分8個階段:(1)始逐漸減小。(2)逐漸增大。(3)逐漸減小。(4)逐漸增大。(5)逐漸減小。(6)逐漸增大。(7)逐漸減小。(8)逐漸增大。這一趨勢恰與上圖中閾值動態(tài)變化總體趨勢吻合。而圖5中躍出點恰好是仿真時加入的隨機噪聲點。

圖6 數(shù)據(jù)集D添加100個噪聲后檢測結(jié)果

為數(shù)據(jù)集D加入100個隨機噪聲后，新數(shù)據(jù)集包含300個正常數(shù)據(jù)點和100個噪聲點，噪聲在數(shù)據(jù)集中所占比例為25%。圖6為參數(shù)trustvalue=3.0時的檢測結(jié)果，其中圓圈表示加入的噪聲點，星形表示數(shù)據(jù)集中被檢測為異常的數(shù)據(jù)點，藍點表示數(shù)據(jù)集中被檢測為正常的數(shù)據(jù)點。因此，外紅圈內(nèi)紅星表示該點是噪聲點且被檢測為異常點，即該噪聲點被正確檢出，外紅圈內(nèi)藍點表示該點是正常點但被檢測為異常點，即該點被誤報，只有紅星的點表示噪聲點被檢測為正常點，即該點被漏報，只有藍點表示非噪聲點被檢測為正常點，即正常點被檢測為正常點。觀察圖5可知，檢測出101個異常點，噪聲全被檢出，有一個正常數(shù)據(jù)點被誤報。

表1 仿真實驗結(jié)果匯總表

將仿真實驗結(jié)果匯總結(jié)果如表1所示。對于數(shù)據(jù)集D，在噪聲比不超過50%的情況下，本文算法檢出率均保持在95%以上，且誤報率維持在2%以下，說明本文的檢測方法在絕大多數(shù)情況下能快速有效地檢測出網(wǎng)絡(luò)中的異常值。

4 結(jié)束語

本文從時間上相鄰數(shù)據(jù)點的間距這一直觀角度出發(fā)，構(gòu)建新的異常值檢測模型。首先，定義了新的異常因子，并以此將數(shù)據(jù)分為正常、異常、臨界3種狀態(tài)。然后，利用異常因子構(gòu)建了一個基于動態(tài)閾值的異常值檢測模型，并給出了動態(tài)閾值的更新方法。本文的檢測方法在無需訓(xùn)練集的條件下，實現(xiàn)了線上實時的異常值檢測。仿真實驗表明，算法在數(shù)據(jù)集中噪聲比不超過50%的情況下檢出率保持在95%以上，同時誤報率維持在2%以下。本方法在實際應(yīng)用中還存在如下問題:(1)參數(shù)trustvalue的取值問題。(2)傳感網(wǎng)絡(luò)中異常值檢測大多都是針對網(wǎng)絡(luò)的時間相關(guān)性和空間相關(guān)性建模，本文模型中并未利用到相鄰傳感器數(shù)據(jù)之間的相關(guān)性，若在模型中引入相鄰傳感器數(shù)據(jù)之間的相關(guān)性，是否能進一步提高算法的檢測精度。(3)如何在現(xiàn)有檢測的方法的基礎(chǔ)上，實現(xiàn)對臨界態(tài)數(shù)據(jù)的再判定，以減少臨界態(tài)數(shù)據(jù)的漏檢。

［1］Zhang Y，Meratnia N，Havinga P JM.Outlier detection techniques for wireless sensor network:a survey［J］.IEEE Communications Surveys＆ Tutorials，2010(12):159 －170.

［2］Rajasegarar S，Leckie C，Palaniswami M，et al.Quarter sphere based distributed anomaly detection in wireless sensor networks［C］.IEEE International Conference on Communications，2007.

［3］Elnahrawy E，Nath B.Context－ aware sensors［J］.EWSN，2004，29(20):7 －93.

［4］Janakiram D，Adi Mallikarjuna Reddy V，Phani Kumar A V U.Outlier detection in wireless sensor networks using bayesian belief networks［C］.Delhi，India:In Proceedings of the First International Conference on Communication System Software and Middleware(COMSWARE)，2006(1):1 －6.

［5］Chatzigiannakis V，Papavassiliou S，Grammatikou M，et al.Hierarchical anomaly detection in distributed large－scale sensor networks［C］.11th IEEE Symposium on Computers and Communications，2006:761 －767.

［6］Rajasegarar S，Bezdek J C，Leckie C，et al.Elliptical anomalies in wireless sensor networks［J］.ACM Transactions on Network，2010(6):1 －28.

［7］Miao X，Jiankun H，Song H，et al.Scalable hyper－ grid k －NN－based online anomaly detection in wireless sensor networks［J］.IEEE Transactions on Parallel Distribut System，2013(24):1661－1670.

［8］Moshtaghi M，Bezdek JC，Havens T C，et al.Streaming analysis in wireless sensor networks［J］.Wireless Communication Mobile Computer，2012(6):763 －771.

［9］Burbeck K，Nadjm －Tehrani S.Adaptive real－ time anomaly detection with incremental clustering［R］.Informations Secures Technology Report，2007(12):56 －67.

［10］Moshtaghi M，Leckie C，Karunasekera S，et al.Incremental elliptical boundary estimation for anomaly detection in wireless sensor networks［C］.Vancouver，BC，Canada:In Proceedings of the 11th IEEE International Conference on Data Mining(ICDM)，2011(12):467 －476.

［11］Hill D，Minsker B，Amir E.Real－time bayesian anomaly detection for environmental sensor data［C］.Venice，Italy:In Proceedings of the Congress－International Association for Hydraulic Research(IAHR)，2007.