唐 琪，劉學軍

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

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

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

1 相關(guān)研究

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

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

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

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

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

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

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

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

本節(jié)回顧了切比雪夫多項式的正交性和切比雪夫系數(shù)的計算。

定義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設(shè) t=cosθ，則 Pi(cosθ)=cos(iθ)，Pj(cosθ)=cos(jθ)。兩個切比雪夫的內(nèi)積:

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

切比雪夫多項式系數(shù)[17]:

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

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

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

時間序列的切比雪夫系數(shù):

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

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

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

證明

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

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

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

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

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

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

2.4 算法描述

(1)算法步驟詳述

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

(2)算法偽代碼

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

3 算法實驗分析

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

3.1 切比雪夫系數(shù)的選取

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

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

3.2 精確度比較

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

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

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

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

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

3.3 CPU速度比較

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

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

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

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

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

4 總結(jié)與展望

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

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

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

[3]楊黎斌，慕德俊，蔡曉妍.基于核聚類的無線傳感器網(wǎng)絡(luò)異常檢測方案[J].傳感技術(shù)學報，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.