無線傳感器網絡離群時間序列檢測研究*

唐 琪，劉學軍

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

傳感器網絡[1]是由大量小型的、低成本和低功耗的傳感器節點組成，傳感器節點采集的異常數據稱為離群數據，這些離群數據往往代表某種異常事件的發生，例如火災的出現、入侵監測[2]，攻擊異常檢測[3]等。因此，在監測系統中，傳感器節點的離群數據往往更重要，也常常是監測的重點。離群數據檢測的基本算法有基于統計[4]的離群數據檢測方法，基于偏離的離群數據檢測方法，基于距離[5]的離群數據檢測方法和基于密度[6]的離群數據檢測方法等等。離群數據檢測包括單個離群數據點的檢測和時間序列離群數據的檢測，通常后者的復雜度遠遠高于前者。在無線傳感器網絡中，每個傳感器節點采集到的數據可以認為是一個時間序列，而所有傳感器節點采集到的數據被認為是一個時間序列數據集，通過時間序列進行離群數據檢測比單個離群數據點檢測往往更有意義，更有利于揭示異常事件的發生。但是，時間序列異常檢測算法的復雜度通常都很高，難以應用于無線傳感器網絡環境中。因此，本文通過將時間序列轉換成切比雪夫多項式，通過少數切比雪夫系數的比較來快速判斷兩個時間序列數據的相似性，從而發現異常的時間序列。該算法不僅適用于一維時間序列，也適用于多維時間序列。

本文后續內容安排如下:第1節介紹了相關的研究工作;第2節提出了一種基于切比雪夫多項式的無線傳感器網絡離群時間序列檢測算法;第3節通過實驗分析了無線傳感器網絡時間序列離群數據檢測算法的性能;第4節總結了全文。

1 相關研究

在無線傳感器網絡中，離群時間序列是那些與其他時間序列有較大偏差的時間序列，以至于引起這樣的懷疑，這些偏差并非隨機產生，而是產生于一種完全不同的方式。研究表明，利用切比雪夫系數的歐氏距離判定兩個時間序列的相似度，相對于離散傅里葉變換(Discrete Fourier Transform，DFT)[7]，離散小波變換(DiscreteWaveletTransform，DWT)[8]，自適應分段常數近似(Adaptive Piecewise Constant Approximation，APCA)[9]，分段聚合近似(Piecewise Aggregate Approximation，PAA)[10]，前者的算法精確度高于后面幾種算法。Yang Zhang[11]等人對傳感器網絡的離群點檢測技術進行了綜述，詳細地分析了傳感器網絡中離群點檢測的意義、應用領域以及相關算法等。Dang-Hoan Tran[12]等人提出了在無線傳感器網絡中利用DFT方法進行離群數據檢測，通過將時間序列轉變成頻域序列進行離群數據檢測。Yongzhen Zhuang[13]等人提出了在無線傳感器網絡中網絡異常清洗方法，通過對時間序列進行小波變換來檢測離群數據。ShengBo[14]等人提出了基于直方圖的離群點檢測研究算法，但是只適合一維數據，不適合多維數據。Kifer[15]等人提出了一種復雜的無參框架的離群數據檢測，適用于一維數據流，不適合高維數據流。

與以上研究不同，本文基于切比雪夫思想和歐氏距離，提出了一種新的快速無線傳感器網絡離群時間序列檢測算法(fast outlier time series detection algorithm，FODA)。

2 離群時間序列檢測算法FODA

2.1 網絡模型

本文要解決的問題是傳感器節點采集到的低維或高維數據構成的時間序列，通過切比雪夫思想快速檢測出離群時間序列，具體描述如下:

在無線傳感器網絡Y中，N個無線傳感器節點部署在區域D內，Y=(A，E)。A表示網絡中的傳感器節點集合A={Ai，i=1，…N}，E表示兩個在彼此通信范圍內的相連傳感器節點的虛擬邊。傳感器節點采集到的數據是一個長度為m，維數為d的多變量時間序列，存儲到時間窗口W中。將長度為ω的滑動窗口ω＜＜m放在時間序列的起始位置，此時滑動窗口對應時間序列上長度為ω的一段基本窗口，然后滑動窗口向后移，以時間序列的第2點為起始點，形成另一個長度為ω的基本窗口，依此類推，共得到m－1個長度為ω的基本窗口，這些基本窗口用S=(S1，S2，…，Sm－1)表示。本文利用滑動窗口、基本窗口檢測出離群時間序列。無線傳感器網絡結構如圖1所示。增大滑動窗口每次移動的距離，可以減少基本窗口的數量。

圖1 無線傳感器網絡結構

2.2 切比雪夫思想的基本概念

本節回顧了切比雪夫多項式的正交性和切比雪夫系數的計算。

定義1切比雪夫多項式[16]:切比雪夫多項式Pm(t)=cos[mcos(－1)(t)]，其中 t∈[－1，1]。因為cosmθ+cos(m－2)θ=2cosθcos(m－1)θ，切比雪夫多項式可以改寫為

如:P0(t)=1，P1(t)=t，P2(t)=2t2－1，P3(t)=4t3－3t，P4(t)=8t4－8t2+1

定義2設 t=cosθ，則 Pi(cosθ)=cos(iθ)，Pj(cosθ)=cos(jθ)。兩個切比雪夫的內積:

定義3給定切比雪夫多項式P0，…，Pm，將函數f(t)近似為:

切比雪夫多項式系數[17]:

2.3 時間序列的切比雪夫思想

定義4時間序列的切比雪夫逼近:時間序列 S={(t1，v1)，…，(tω，vω)}，其中－1≤t1＜…＜tω≤1(把時間標準化為[－1，1])。時間序列是一個離散函數，將離散函數化成連續函數，即:

那么 g(t)=vi，其中 t∈Ii(1≤i≤ω)。將時間序列轉換成的連續函數為，其中 t∈Ii(1≤i≤ω)。

時間序列的切比雪夫系數:

定義5長度均為ω的兩個一維時間序列為S1={(t1，v1)，…，(tω，vω)}和 S2={(t1，q1)，…，(tω，qω)}，兩個時間序列的歐氏距離:

定義6長度均為ω的兩個一維時間序列S1，S2的連續函數分別為f1(t)和f2(t)且fZ(t)=f1(t)－f2(t)，切比雪夫系數向量分別為和(T 為向量 C 的轉置)，兩個系數向量的歐式距離:

引理1Discby(C1，C2)≤Diseuc(S1，S2)。

證明

其中第二步由文獻[16]得到。

定義7d維的兩個時間序列S，R的切比雪夫向量系數分別為。兩個時間序列的切比雪夫向量系數的歐氏距離為:

根據引理1 得 Discby(C，D)≤Diseuc(S，R)。

定義8相似序列:對于兩個時間序列S，R，此兩個時間序列的切比雪夫系數向量分別為C，D。若Discby(C，D)＜ε，則稱時間序列S和R相似。記為similar(S，R)。進行相似度匹配時，我們采用滑動窗口機制，找出新數據窗口(滑動窗口)和歷史數據窗口(基本窗口)的相似度，并計算出相似度值。

定義9對于一個時間序列S，如果歷史數據窗口中，與之相似的時間序列數量小于一定的比例，那么時間序列S稱為離群時間序列即

其中R為與S相似的時間序列，H為時間窗口W中的歷史數據窗口。

2.4 算法描述

(1)算法步驟詳述

每個傳感器節點采集數據構成一個時間序列，在時間窗口中通過切比雪夫思想把時間序列化成時間區間在[－1，1]的連續函數，并計算連續函數的切比雪夫多項式系數，利用系數求兩個時間序列的相似度，最后利用定義9判定離群時間序列，將離群時間序列傳給Sink節點。

(2)算法偽代碼

將各個傳感器節點的離群時間序列傳給Sink節點

3 算法實驗分析

在100×100的區域內隨機部署101個傳感器節點(包括基站)。在無線傳感器網絡中，相對于數據無線發送接收來說，節點進行計算和儲存的能耗基本可以忽略不計，網絡的生存時間主要取決于數據傳輸。設節點初始能量為1 J，發送和接收能耗均為0.395 nJ/bit，空閑能耗為 0.039 nJ/bit.為了將數據傳輸的更遠，放大電路功耗為100 pJ/bit·m2，通信距離為50 m，仿真時間為1 000 s，數據大小為512 byte，無線傳感器網絡的協議為802.15.4。離群時間序列檢測算法的精確度如公式所示。

3.1 切比雪夫系數的選取

傳感器節點采集的數據以20 s為一個基本窗口，離群時間序列的速度為每100 s出現一次。對時間序列進行切比雪夫轉化，分別取系數的值為[0，25]中的整數.基于文獻[13]Yongzhen Zhuang等人提出了基于無線傳感器網絡中離散小波變換(DWT)離群數據檢測，圖2顯示了DWT算法與本文的FODA算法中切比雪夫系數選取的比較。切比雪夫系數與小波變換系數類似，取系數值在4到8之間時，檢測精確度在90%以上，取5左右時精確度最好。

圖2 切比雪夫和小波變換系數的選取比較

3.2 精確度比較

傳感器節點采集的數據以20 s為一個基本窗口，離群時間序列的速度分別為每100 s，200 s，300 s，400 s，500 s各一個。對這5組數據進行離群時間序列檢測。

(1)傳感器節點采集的數據維度d=1。由文獻[16]可以得知，利用PAA和切比雪夫思想進行時間序列相似性判定時，切比雪夫思想比PAA更好。圖3顯示了PAA的離群時間序列檢測與FODA算法檢測在一維數據上的精確度比較，實驗證明在一維數據上，FODA算法比PAA的離群時間序列檢測精度稍高。本文利用切比雪夫多項式進行無線傳感器網絡環境中的離群數據檢測，目前，尚未見類似的工作。

圖3 一維時間序列數據，PAA算法與FODA算法精度比較

(2)傳感器節點采集的數據維度d=4時。圖4顯示了PAA的離群時間序列檢測與FODA算法檢測在4維數據上的精確度比較。同上述一樣，實驗證明在多維數據上，FODA算法比PAA算法的離群時間序列的檢測精確度較高。

圖4 多維時間序列數據，PAA算法與FODA算法精度比較

3.3 CPU速度比較

傳感器節點采集的數據維度d=1。比較了FODA算法和PAA算法的時間效率。由圖5可以看出，FODA算法所消耗的CPU時間低于PAA的離群時間序列檢測所消耗的CPU時間。

圖5 一維時間序列數據，PAA算法與FODA算法速度比較

取傳感器節點采集的數據維度d=4，對FODA算法和PAA算法的時間效率進行了仿真。如圖6所示，FODA算法所消耗的CPU時間也低于PAA的離群時間序列檢測所消耗的CPU時間。

圖6 多維時間序列數據，PAA算法與FODA算法速度比較

從上述兩組仿真實驗可以看出，FODA算法在速度方面優于PAA算法。主要原因是:PAA算法的時間復雜度是O(N)，其中N為時間序列的長度。而FODA算法的時間復雜度是O(n)，其中，n為切比雪夫系數個數，而n遠遠小于N，因此FODA算法執行速度明顯快于PAA的離群時間序列檢測算法。

4 總結與展望

本文提出的無線傳感器網絡離群時間序列檢測算法，不僅適用于低維的離群時間序列數據檢測，而且適用于高維的離群時間序列數據檢測，同時保持了較高的檢測精度。本文利用切比雪夫多項式系數判定兩個時間序列的相似度能夠快速的檢測離群時間序列。通過實驗驗證了上述結論。接下來的工作是為了節省網絡能量消耗，我們考慮無線傳感器網絡分簇的問題并將提出的算法與實際應用結合起來。

[1]任豐原，黃海寧.無線傳感器網絡[J].軟件學報，2003，14(7):1282－1291.

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

[3]楊黎斌，慕德俊，蔡曉妍.基于核聚類的無線傳感器網絡異常檢測方案[J].傳感技術學報，2008，21(8):1442－1447.

[4]孫金花，胡建.基于分型理論的離群點檢測[J].計算機工程，2011，37(3):33－35.

[5]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.

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

[7]Faloutsos C，Ranganathan M，Manolopoulos Y.Fast Subsequence Matching in Time-Series Databases[C].Proc.SIGMOD，1994:419－429.

[8]Wu Y，Agrawal D，Abbadi A.A Comparison of DFT and DWT Based Similarity Search in Time-Series Databases[C].Proc.CIKM，2000:488－495.

[9]Keogh E，Chakrabarti K，Pazzani M，et al.Locally Adaptive Dimensionality Reduction for Indexing Large Time Series Databases[C].Proc.ACM SIGMOD，2001:151 –162.

[10]Keogh E，Chakrabarti K，Pazzani M，et al.Dimensionality Reduction for Fast Similarity Search in Large Time Series Databases[J].Journal of Knowledge and Information Systems，2000:263－286.

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

[12]Dang-Hoan Tran，Jin Yang.Decentralized Change Detection in Wireless Sensor Network Using DFT-Based Synopsis[C].The 12thIEEE International Conference，2011:226－235.

[13]Zhuang Yongzhen，Chen Lei.In-Network Outlier Cleaning for Data Collection in Sensor Networks[C].Proceedings of Very Large Data Bases，2006.

[14]Sheng Bo，Li Qun，Mao Weizhen.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.

[15]Kifer D，Ben-David S，Gehrke J.Detecting Change in Data Streams[C].In Proceedings of the Thirtieth International Conference，2004:180－191.

[16]Cai Yuhan，Raymond Ng.Indexing Spatio-Temporal Trajectories with Chebyshev Polynomials[C].Proc.ACM SIGMOD，2004:599－610.

[17]Mason J C，Handscomb D C.Chebyshev Polynomials[M].Chapman and Hall/CRC，2011，9.