唐 琪，劉學(xué)軍

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

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

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

1 相關(guān)研究

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

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

2 離群時(shí)間序列檢測(cè)算法FODA

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

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

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

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

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

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

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

如: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θ)。兩個(gè)切比雪夫的內(nèi)積:

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

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

2.3 時(shí)間序列的切比雪夫思想

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

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

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

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

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

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

證明

其中第二步由文獻(xiàn)[16]得到。

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

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

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

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

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

2.4 算法描述

(1)算法步驟詳述

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

(2)算法偽代碼

將各個(gè)傳感器節(jié)點(diǎn)的離群時(shí)間序列傳給Sink節(jié)點(diǎn)

3 算法實(shí)驗(yàn)分析

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

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

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

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

3.2 精確度比較

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

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

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

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

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

3.3 CPU速度比較

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

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

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

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

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

4 總結(jié)與展望

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

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

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

[3]楊黎斌，慕德俊，蔡曉妍.基于核聚類的無線傳感器網(wǎng)絡(luò)異常檢測(cè)方案[J].傳感技術(shù)學(xué)報(bào)，2008，21(8):1442－1447.

[4]孫金花，胡建.基于分型理論的離群點(diǎn)檢測(cè)[J].計(jì)算機(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]薛安榮，鞠時(shí)光，何偉華，等.局部離群點(diǎn)挖掘算法研究[J].計(jì)算機(jī)學(xué)報(bào)，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.