翟小超

(西安電子科技大學數學與應用數學，陜西西安 710071)

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

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

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

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

1 數據異常因子

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

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

圖1 異常值示意圖

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

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

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

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

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

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

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

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

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

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

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

其中，trustvalue是一個＞的參數。

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

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

2 檢測方法

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

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

步驟1 部署傳感網絡，開始采集數據;

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

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

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

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

步驟6 重復步驟4和步驟5直到傳感器停止采集數據。

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

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

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

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

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

3 仿真實驗

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

圖4 生成數據D集示意圖

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

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

圖6 數據集D添加100個噪聲后檢測結果

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

表1 仿真實驗結果匯總表

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

4 結束語

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

［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.