邊緣計算應用：傳感數(shù)據(jù)異常實時檢測算法

張 琪 胡宇鵬 嵇 存 展 鵬 李學慶

(山東大學計算機科學與技術學院 濟南 250101) (d.steven@sdu.edu.cn)

近年來，隨著互聯(lián)網(wǎng)、物聯(lián)網(wǎng)、云計算等技術的不斷發(fā)展與相互融合，我們已經(jīng)逐步進入“萬物互聯(lián)、全面感知”的互聯(lián)網(wǎng)新時代[1].近年來物聯(lián)網(wǎng)的發(fā)展導致了大量的數(shù)據(jù)傳感設備廣泛應用于不同的領域，例如金融與能源行業(yè)、化工與石油行業(yè)、生物和醫(yī)藥行業(yè)等等.這些傳感設備在改變?nèi)藗兊纳罘绞降耐瑫r也產(chǎn)生了海量的時序數(shù)據(jù)資源.以浙江省的電力網(wǎng)絡為例，截止目前整個網(wǎng)絡中已經(jīng)部署了2 000萬臺以上的智能電表設備，每臺電表以1 Hz為單位采集“時序”用電信息，全省一年采集的用電數(shù)據(jù)量已經(jīng)達到了拍字節(jié)規(guī)模(petabyte, PB)[2].

盡管傳感設備的類型各有不同，但其獲取的數(shù)據(jù)可以分為2類：1)實時狀態(tài)數(shù)據(jù).表示某個時刻運行狀態(tài)，例如速度、功率等；2)累加數(shù)據(jù).表示一定范圍內(nèi)的數(shù)據(jù)累加量，例如里程、熱消耗等.通常情況下，傳感器以一定的頻率采集數(shù)據(jù)，并將數(shù)據(jù)發(fā)送至相應的數(shù)據(jù)接收端.數(shù)據(jù)接收端將收到一組或多組在時間上存在嚴格先后順序的一組或多組觀測值序列，即“時間序列數(shù)據(jù)”.這些時序數(shù)據(jù)精準地記錄著某個具體參數(shù)的實時變化情況，并在一定的時間范圍內(nèi)反映該參數(shù)的發(fā)展趨勢和變化規(guī)律.因此基于傳感設備所采集的時間序列數(shù)據(jù)不僅為后續(xù)的數(shù)據(jù)趨勢展現(xiàn)等數(shù)據(jù)可視化工作提供了重要的數(shù)據(jù)來源，同時也是后續(xù)數(shù)據(jù)挖掘工作(分類、聚類、關聯(lián)、預測)的基礎與前提.

以中國空間技術研究院的衛(wèi)星總裝集成測試(assembly, integration and test, AIT)為例，針對整顆衛(wèi)星的AIT測試被分為11個不同的測試階段，每個測試階段平均需要高速采集5 000多個衛(wèi)星參數(shù)的“時序”狀態(tài)數(shù)據(jù).AIT測試人員，可以根據(jù)所獲取到的衛(wèi)星參數(shù)時序數(shù)據(jù)來判斷衛(wèi)星的某個具體部件的運轉狀態(tài)是否正常，而衛(wèi)星設計師們則可以根據(jù)衛(wèi)星在不同測試環(huán)節(jié)中的各個部件運轉狀態(tài)的匯總情況，得出相應的衛(wèi)星整體“健康度”分析結論.而得出正確的“整星分析”結論的前提條件是傳感器采集并傳輸?shù)臄?shù)據(jù)是可靠的.

但是在實際的數(shù)據(jù)采集場景中，傳感設備在數(shù)據(jù)采集與傳輸?shù)倪^程中，總是會出現(xiàn)一些異常，文獻[3]針對實際的傳感器數(shù)據(jù)集進行了數(shù)據(jù)異常檢測的相關研究，研究結果表明：通過傳感器獲取高質量的數(shù)據(jù)是一件非常困難的事情，因為故障的出現(xiàn)次數(shù)、頻率等都讓人無法預料，并且相應的數(shù)據(jù)清洗與校準工作也并不容易.

根據(jù)上述情況的介紹，我們希望采取從時間序列數(shù)據(jù)分析的角度，對傳感數(shù)據(jù)中出現(xiàn)的相應數(shù)據(jù)異常進行有效地識別，幫助后續(xù)的數(shù)據(jù)清洗工作對相應的數(shù)據(jù)異常進行有效的“平滑”操作，并保留傳感數(shù)據(jù)中正常的數(shù)據(jù)波動情況，從而為后續(xù)的時間序列數(shù)據(jù)挖掘研究工作提供高質量的來源數(shù)據(jù).

目前已有一些異常檢測算法被提出.從早期的基于統(tǒng)計的檢測算法[4]、基于距離的檢測算法[5-6]、基于密度的檢測算法[7]、基于神經(jīng)網(wǎng)絡的方法[8]、基于支持向量機的方法[9]以及聚類分析的方法[10]等.時序數(shù)據(jù)具有一些特殊的性質，異常檢測算法應該考慮其特性.如Fu所言，在時序數(shù)據(jù)領域，異常檢測的方法大部分都是基于模式識別與聚類進行異常檢測[11].Vlachos等人[12]提出了準確周期檢測的非參數(shù)方法并引進了時間序列新的周期距離策略.相似地，Keogh等人[13]通過檢測當前數(shù)據(jù)與預制數(shù)據(jù)模型之間是否存在較大差異，從而實現(xiàn)時序數(shù)據(jù)的異常檢測.Keogh等人[14]后來引入了一個基于檢測數(shù)據(jù)象征性版本的特定的重新排序策略.除了離線方法以外，還存在一些在線檢測算法.Chan等人[15]從多個時序數(shù)據(jù)生成了可理解的準確模型來進行異常檢測.Wei等人[16]利用時間序列位圖來進行異常檢測.Fujimaki等人[17]設計了一個應用于大量遙感數(shù)據(jù)的新穎的異常檢測系統(tǒng)，該系統(tǒng)主要利用相關向量的回歸和數(shù)據(jù)的自回歸進行異常檢測.周大鐲等人[18]在基于重要點(important point, IP)時間序列分割的基礎上，提出了基于k近鄰的局部異常檢測算法. Cai等人[19]通過構建分布式遞歸計算策略以及k近鄰快速選擇策略提出了一種新的時間序列數(shù)據(jù)異常檢測算法.

然而這些方法主要是針對單一傳感來源數(shù)據(jù)進行相應的異常監(jiān)測工作，而在傳感網(wǎng)絡中不同傳感來源數(shù)據(jù)之間往往存在著大量“已知”的相關關系，具有相關關系的傳感數(shù)據(jù)之間則肯定存在著一定的數(shù)據(jù)趨勢變化規(guī)律，這些變化規(guī)律可以幫助我們對相應的數(shù)據(jù)異常進行有效的識別.

此外，需要特別強調(diào)的是：目前常見的傳感數(shù)據(jù)異常檢測處理方式是利用相對成熟的云計算模型[20]以及常見的大數(shù)據(jù)處理產(chǎn)品：Hadoop[21]，Spark[22]等，將各種數(shù)據(jù)采集設備所獲取的數(shù)據(jù)直接傳輸?shù)皆朴嬎阒行倪M行數(shù)據(jù)存儲，并利用云計算中心強大的計算能力完成相應的異常檢測與數(shù)據(jù)清洗工作.這種方式也被稱為：基于云計算的集中式大數(shù)據(jù)處理模式.根據(jù)思科、國際數(shù)據(jù)公司(International Data Corporation, IDC)等機構的相關研究表明，到2020年連接到網(wǎng)絡的無線設備數(shù)量將達到500億臺，隨著邊緣設備數(shù)據(jù)量的增加，網(wǎng)絡邊緣設備產(chǎn)生的數(shù)據(jù)，受網(wǎng)絡帶寬與云數(shù)據(jù)中心計算能力的限制，已經(jīng)無法像過去那樣直接傳輸?shù)綌?shù)據(jù)中心進行相應的數(shù)據(jù)操作.因此需要對現(xiàn)有的集中式大數(shù)據(jù)處理模型進行相應的調(diào)整，將云計算模型的部分計算任務遷移到網(wǎng)絡邊緣設備上，在減緩網(wǎng)絡帶寬壓力的同時，降低數(shù)據(jù)中心的計算負載.

根據(jù)目前基于云計算的集中式大數(shù)據(jù)處理模式所面臨的限制和瓶頸，本文提出基于邊緣計算的分布式傳感數(shù)據(jù)異常檢測模型.利用邊緣計算的大數(shù)據(jù)處理思想，盡可能地將相應的數(shù)據(jù)在接近數(shù)據(jù)源的計算資源上進行相應地處理，在減輕網(wǎng)絡傳輸帶寬壓力的同時，提高了數(shù)據(jù)處理的整體效率.在分布式傳感數(shù)據(jù)異常檢測模型的基礎上，本文提出了基于時間序列的傳感數(shù)據(jù)異常檢測算法(anomaly detection of multi-source sensing data based on time series, ADMSD_TS).本算法將根據(jù)時間序列數(shù)據(jù)的離群距離測算以及時間序列之間的相關性對相應的傳感數(shù)據(jù)異常進行檢測.即通過對“單一”時間數(shù)據(jù)序列中離群點的識別以及對具有相關關系的“多源”時間序列之間的數(shù)據(jù)變化趨勢為檢測基礎，高效識別出多源傳感數(shù)據(jù)集中的相應數(shù)據(jù)異常.實驗結果顯示本算法性能良好，檢測時間短并且異常檢出率高.

1 問題定義

根據(jù)引言的介紹，本節(jié)將給出基于時間序列的數(shù)據(jù)異常檢測問題的相關定義.

定義1. 傳感器所采集并傳輸?shù)亩嘣磦鞲袛?shù)據(jù)，可以按照時間序列數(shù)據(jù)的形式，簡化表示為

TSm={S1,S2,…,Si,…,Sm},

(1)

Si={s1,s2,…,sj,…,sn},

(2)

其中,1≤i≤m,1≤j≤n,TSm表示多源傳感數(shù)據(jù)的時間序列表示數(shù)據(jù)集合，m表示集合內(nèi)的數(shù)據(jù)個數(shù).式(1)中Si表示單一傳感數(shù)據(jù)，在式(2)中n表示Si的長度.其中sj表示某個具體采集時刻的數(shù)據(jù)值，sj=(vj,tj)，tj表示sj的時間標簽，vj表示時刻tj的數(shù)據(jù)值，在時間序列中tj是嚴格遞增的.

根據(jù)上面單一傳感數(shù)據(jù)的時間序列表示形式Si，我們將引入滑動窗口(slide window, SW)[23]，用來存放Si的部分數(shù)據(jù)，設SW的長度為Lensw并忽略SW中時間序列數(shù)據(jù)的時間標簽，我們給出SW中時間序列數(shù)據(jù)的離群距離的定義.

定義2. SW中的部分時間序列數(shù)據(jù)可以簡化表示為

STn={v1,v2,…,vt,…,vn} (1≤t≤n),

(3)

(4)

(5)

1) 基本相關

基本相關也被稱為線性相關性，以熱力系統(tǒng)為例，熱功率P與輪軸轉動速度V所組成的二元時間序列TS2={P,V}，其中P=(p1,p2,…,pi,…,pn)與V=(v1,v2,…,vi,…,vn)(1≤i≤n)，如滿足vi≈kpi+b，則說明P，V之間存在二元線性相關性，并將其放入關系參數(shù)集合Ω2中，記為Ω2={P,V}.類似地，如三元時間序列數(shù)據(jù)TS3={S1,S2,S3}滿足三元線性相關性.則將其放入?yún)?shù)集合Ω3中，記為Ω3={S1,S2,S3}.

2) 組合相關

3) 轉換相關

① 指數(shù)模型.y=aeb x對等式兩邊進行取對數(shù)操作，轉換為lny=lna+bx，我們將原時間序列Y轉換為新的時間序列l(wèi)nY，并在隨后的DCD中檢測lnY與X的線性相關性.

③ 多項式模型.z=ax2+by+c，將原時間序列X進行乘方操作變?yōu)樾碌臅r間序列X2，然后在DCD中檢測Z與X2,Y的線性相關性.

2 傳感數(shù)據(jù)異常實時檢測算法

本文提出的ADMSD_TS算法將會從傳感數(shù)據(jù)本身的時序連續(xù)性檢測(temporal continuity detection, TCD)以及傳感數(shù)據(jù)之間的相關性檢測(data correlation detection, DCD)兩個方面，對傳感數(shù)據(jù)的異常進行相應地檢測.隨后對這2種不同的檢測結果進行相應地數(shù)據(jù)融合處理，完成最終的多源傳感數(shù)據(jù)異常檢測.本節(jié)將介紹基于傳感數(shù)據(jù)異常檢測的邊緣式數(shù)據(jù)處理架構以及ADMSD_TS算法的具體實現(xiàn).

2.1 基于邊緣計算的數(shù)據(jù)架構

在我們的前期研究工作中，我們提出了基于異構設備的數(shù)據(jù)提取模型，基于此模型從多個企業(yè)的物聯(lián)網(wǎng)數(shù)據(jù)源中提取各種形式的異構數(shù)據(jù)，并將這些多源異構數(shù)據(jù)保存到我們構建的一體化的工業(yè)大數(shù)據(jù)平臺(industrial big data platform, IBDP)中，IBDP支持從數(shù)據(jù)提取、到數(shù)據(jù)處理、再到數(shù)據(jù)挖掘與可視化的智能大數(shù)據(jù)分析全過程[24].

根據(jù)引言部分的描述，我們不難發(fā)現(xiàn)：線性增長的集中式云計算能力已經(jīng)無法滿足數(shù)據(jù)量急劇增長的邊緣數(shù)據(jù)的處理要求，此外將數(shù)據(jù)量持續(xù)增長的邊緣數(shù)據(jù)集中到某個或某幾個數(shù)據(jù)計算中心完成相應的數(shù)據(jù)計算任務，無論從技術上還是經(jīng)濟上來說，都將變得越來越不可行.根據(jù)文獻[25]中邊緣計算相關內(nèi)容的介紹以及系統(tǒng)架構的描述如圖1所示，我們考慮將IBDP的部分數(shù)據(jù)計算任務進行相應地遷移，并在相應的數(shù)據(jù)源附近建立邊緣層數(shù)據(jù)處理節(jié)點，“就近”完成相應的數(shù)據(jù)處理任務.以本文所研究問題的具體場景為例，我們考慮在傳感數(shù)據(jù)采集端附近，建立相應的邊緣層數(shù)據(jù)節(jié)點，在接收傳感數(shù)據(jù)的同時，完成相關數(shù)據(jù)的異常檢測任務.相應的系統(tǒng)整體架構如圖1所示:

Fig. 1 System architecture diagram圖1 系統(tǒng)整體架構圖

根據(jù)圖1的描述，我們將在數(shù)據(jù)采集層建立基于Storm的流數(shù)據(jù)處理結構，在進行數(shù)據(jù)接收的同時，對相應的傳感數(shù)據(jù)進行異常檢測.我們首先給出ADMSD_TS算法在Storm平臺上的拓撲結構，如圖2所示.

DataSpout接收采集到的傳感數(shù)據(jù)(data source)，并將其發(fā)送至各個TCDBolt，檢查傳感數(shù)據(jù)的時序連續(xù)性，如果通過DataSpout接收到的數(shù)據(jù)量大且參數(shù)類型繁多，還可以考慮通過數(shù)據(jù)劃分模塊(Partion)將數(shù)據(jù)進行相應的劃分，并將劃分后的數(shù)據(jù)傳送至TCDBolt進行時序連續(xù)性檢測.RelationSpout將接收用戶發(fā)送的傳感數(shù)據(jù)不同參數(shù)之間的關系模型集(relation source)，RelationSpout會將相應的關系模型發(fā)送至DCDBolt，用于DCDBolt檢測傳感數(shù)據(jù)之間的相關性，如果關系模型集相對龐大，則也可以考慮采用數(shù)據(jù)劃分模塊先將其劃分并再次發(fā)送至相應的DCDBolt.當TCDBolt完成時序相關性檢測之后，多個TCDBolt將向對應的DCDBolt發(fā)送相應的傳感數(shù)據(jù)，在DCDBolt進行數(shù)據(jù)相關性檢查.與此同時，TCDBolt也會將時序連續(xù)性的檢查結果發(fā)送至FusionBolt.等待DCDBolt中對應的相關性結果檢測完畢以后，DCDBolt也會將對應的相關性檢測結果發(fā)送至FusionBolt，完成最終的多源傳感數(shù)據(jù)異常檢測.用戶也可以向QuerySpout發(fā)送相應的查詢信息，QueryBolt會接收到用戶的查詢信息，并按照用戶的要求查詢相應的數(shù)據(jù)異常情況并進行輸出.需要說明的是，如果在硬件設備條件允許的情況下(大容量SSD磁盤陣列或者大容量的內(nèi)存)我們可以對DataSpout接收到的傳感數(shù)據(jù)進行復制，并分別向TCDBolt與DCDBolt進行發(fā)送，同時進行相應地相關性檢測與連續(xù)性檢測，并將檢測結果發(fā)送至FusionBolt進行相應的數(shù)據(jù)融合并完成多源傳感數(shù)據(jù)異常檢測.有關性能優(yōu)化的相關工作，將會在我們今后的研究中進行分析與討論.

Fig. 2 Topology diagram of ADMSD_TS圖2 ADMSD_TS拓撲結構圖

2.2 基于離群距離與序列相關性的異常檢測

本節(jié)介紹基于時序數(shù)據(jù)的離群距離以及序列相關性的異常檢測算法,該算法主要分為3步：1)對多元傳感數(shù)據(jù)進行數(shù)據(jù)相關性檢測(data correlation detection, DCD)；2)對一元傳感數(shù)據(jù)進行時序連續(xù)性檢測 (temporal continuity detection, TCD)；3)對前2步的異常檢測結果進行融合處理(fusion process, FP),獲取最終的檢測結果.

2.2.1 基于相對離群距離的數(shù)據(jù)異常檢測

算法1. 時間序列連續(xù)性檢測TCD.

輸入：時間序列數(shù)據(jù)TS、滑動窗口SW長度Lensw、子序列移動距離Lenmove、滑動窗口的最小長度閾值εsize以及相對離群距離閾值εdis；

輸出：異常參數(shù)集合Ωab.

①Ωab=?; /*初始化參數(shù)集合*/

② HashmapmapForTCD=newHashMap();

/*建立新的Haspmap用于存儲異常參數(shù)*/

③qTS=InitQueue(Lensw);

/*初始化異常數(shù)據(jù)隊列*/

④listSW=InitList(Lensw);

/*初始化滑動窗口列表*/

⑤ whileTS.length()>Lensw

⑦ for eachvivaluein SW

⑨t(yī)s=(vi-lenmove-1,vi+lenmove)；

⑩tssub={ts,vi,lenmove}；

tsub.length<εsize/*如果vt在tssub中的εsize依然大于εdis且tssub的長度已經(jīng)小于εsize*/

tssub.value+lenmove);

/*將異常參數(shù)存入Hashmap中*/

算法1主要利用傳感數(shù)據(jù)自身的時序連續(xù)性并通過計算相對離群距離，對傳感數(shù)據(jù)中可能出現(xiàn)的異常進行檢測.本算法可以檢測單源傳感數(shù)據(jù)的數(shù)據(jù)異常情況，檢測情況如圖3所示，通過TCD算法，可以檢測出該傳感數(shù)據(jù)在框1、框2、框3中的數(shù)據(jù)異常情況.

Fig. 3 Data abnormal detection for TCD圖3 TCD數(shù)據(jù)異常檢測

算法1只考慮了單源傳感數(shù)據(jù)內(nèi)在的時序連續(xù)性，而忽視了多源傳感數(shù)據(jù)之間的相關性.因此只利用TCD進行傳感數(shù)據(jù)的異常檢測，可能存在部分數(shù)據(jù)異常無法有效發(fā)現(xiàn)的問題.

2.2.2 基于參數(shù)相關性的數(shù)據(jù)異常檢測

傳感器獲取的傳感數(shù)據(jù)之間往往具有一定的相關性.我們可以利用傳感數(shù)據(jù)之間的相關性來判斷某個傳感數(shù)據(jù)在一定的時間范圍內(nèi)是否出現(xiàn)了異常.

下面我們以定義3中的基本相關為例(組合相關、轉換相關的處理流程與基本相關類似)，說明DCD的異常檢測流程.

例如在熱力系統(tǒng)中，溫度恒定時，熱功率P與輪軸轉動速度V是線性相關的.根據(jù)Pearson線性相關系數(shù)計算公式，可以求出P與V的線性相關系數(shù)：

(6)

另外，利用最小二乘法來求解線性逼近函數(shù)y=kx+b：

(7)

(8)

根據(jù)定義3，可以將熱功率傳感數(shù)據(jù)與流速傳感數(shù)據(jù)以時間序列的形式表示為SP,SV. 利用式(6)驗證2個參數(shù)之間的線性相關性，并利用式(7)與式(8)來獲取熱功率P與輪軸轉動速度V的時間序列集合TS2={SP,SV}的二元線性模型的系數(shù)k與b.最后將TSm放入?yún)?shù)集合Ω2中，隨后在DCD檢測中驗證TS2中時序數(shù)據(jù)實測值之間是否滿足相應的線性相關性約束.

算法2. 基于數(shù)據(jù)相關性的異常檢測DCD.

輸入：參數(shù)集合Ωk列表、基于SW的傳感數(shù)據(jù)集合TS；

輸出：異常參數(shù)集合Ωa b.

①ΩR=ΩE=Ωa b=?; /*初始化參數(shù)集合*/

② HashmapmapForDCD=newHashMap();

/*建立新的Haspmap用于存儲異常參數(shù)*/

③qPare=InitQueue(Ωk);

/*初始化參數(shù)集合隊列*/

④listTS=InitList(TS);

/*初始化傳感數(shù)據(jù)集合列表*/

⑤ whileqPare.length()≠0

⑥item=qPare.Dequeue();

⑦ for each parameterpiinitem

⑨ end for

/*驗證相關時序數(shù)據(jù)是否滿足參數(shù)集合的約束*/

/*否則將參數(shù)并入ΩE*/

算法2主要利用傳感數(shù)據(jù)之間的相關性，對傳感數(shù)據(jù)中可能出現(xiàn)的異常進行檢測.但該算法只考慮了傳感數(shù)據(jù)之間的相關性，而忽視了傳感數(shù)據(jù)自身的時序連續(xù)性.因此只利用DCD進行傳感數(shù)據(jù)的異常檢測，可能存在2個問題：

1) 如果參數(shù)集合Ωk中元素較少，很難利用傳感數(shù)據(jù)的相關性對異常的傳感數(shù)據(jù)進行準確的定位.假設參數(shù)集合Ω2中只存在一組線性相關序列TS2={S1,S2}.經(jīng)過DCD的相關性檢測，我們發(fā)現(xiàn)傳感數(shù)據(jù)(S1,S2)中存在數(shù)據(jù)異常情況.如圖4中框1、框2、框4所示.根據(jù)圖4，我們只知道(S1,S2)中存在數(shù)據(jù)異常情況，但是到底是S1存在異常、還是S2存在異常、還是兩者全部存在數(shù)據(jù)異常則無法進行更加準確的異常數(shù)據(jù)定位.

2) 如果參數(shù)集合Ωk中所有參數(shù)同時發(fā)生異常，則相應數(shù)據(jù)異常可能無法被DCD成功檢測.根據(jù)圖4中框3所示，當TS2={SP,SV}中SP與SV同時出現(xiàn)數(shù)據(jù)異常，且出現(xiàn)異常的數(shù)據(jù)也滿足相應的二元線性模型的約束，則相應的數(shù)據(jù)異常在DCD中將無法被成功檢測.

Fig. 4 Data abnormal detection for DCD圖4 DCD數(shù)據(jù)異常檢測示意圖

2.2.3 ADMSD_TS算法實現(xiàn)

通過2.2.1節(jié)、2.2.2節(jié)的介紹，我們不難發(fā)現(xiàn)DCD與TCD均能對傳感數(shù)據(jù)的異常進行相應地檢測，但是這2個方法自身都存在著一些缺陷，可能導致相應的異常檢測結果出現(xiàn)偏差.因此在前2步檢測結果的基礎上，再次對DCD與TCD的異常檢測結果進行有效地數(shù)據(jù)融合處理(fusion process,FP)，從而得出更加準確的異常檢測結果.融合處理算法如算法3所示.

算法3. 異常檢測結果的融合操作Fusion Process.

輸入：異常ID列表listForAB，mapForTCD，mapForDCD，DCD算法中的ΩR;

輸出：異常結果集Ωresult.

①Ωresult=?; /*初始化異常結果集*/

②Ωdel=Ωadd=?; /*初始化2個臨時集合用于異常數(shù)據(jù)的整合*/

③ HashmapmapForResult=newHashMap();

/*建立新的Haspmap用于存儲異常結果*/

④ for eachabIDinlistForAB

⑤Ωm=mapForDCD.get(abID);

⑥Ωc=mapForTCD.get(abID);

⑦ ifΩm≠? &&Ωc≠?

⑧ for eachabminΩm

/*解決DCD中的問題1*/

⑨ ifabm?Ωc

⑩traverse(abm,Ωm);

/*尋找abi?{Ωk-abm}*/

/*利用TCD的數(shù)據(jù)異常，解決DCD的問題2*/

/*尋找abi∈Ωk-abc*/

/*將異常結果存入Hashmap中*/

融合處理算法將前2步DCD與TCD所獲取的傳感數(shù)據(jù)異常結果集進行了相應地融合，其基本步驟如下：

算法行①～③完成相應數(shù)據(jù)變量的初始化操作.

算法行④～⑥獲取同一個abID的DCD檢測異常集Ωm以及TCD檢測異常集Ωc.

通過算法1～3的介紹，本文提出的ADMSD_TS算法實現(xiàn)如算法4所示.

算法4. 基于時間序列的多源傳感數(shù)據(jù)異常檢測算法ADMSD_TS.

輸入：時間序列數(shù)據(jù)TS、滑動窗口SW長度Lensw、子序列移動距離lenmove、滑動窗口的最小長度閾值εsize以及相對離群距離閾值εdis；

輸出：異常結果集Ωresult.

①Ωresult=?; /*初始化異常結果集*/

② HashmapmapForTCD=newHashMap();

/*建立新的Haspmap存儲TCD的異常集合*/

③ HashmapmapForDCD=newHashMap();

/*建立新的Haspmap存儲DCD的異常集合*/

④ HashmapmapForResult=newHashMap();

/*建立新的Haspmap存儲融合后的異常結果*/

⑤ whileTS.length()>Lensw

⑥mapForTCD=TCD(TSlen)；

/*TCD檢測*/

⑦mapForDCD=DCD(TSlen)；

/*DCD檢測*/

⑧mapForResult=Fusion(mapForTCD,mapForDCD)； /*異常數(shù)據(jù)融合處理*/

⑨ end while

⑩ ReturnmapForResult. /*輸出異常數(shù)據(jù)集，算法結束*/

2.3 ADMSD_TS算法性能分析

1) TCD復雜度分析.TCD的計算時間與滑動窗口SW長度Lensw以及子序列移動距離lenmove有關.由于最小長度閾值εsize、相對離群距離閾值εdis的限制，子序列的平均移動次數(shù)k將為某個固定常數(shù)，TSm中的m一般也為某個固定常數(shù).TCD的計算復雜度為O(k×m×Lensw×lenmove)，考慮到k與m為固定常數(shù)，而Lensw?n且Lenmove?n，TCD的計算復雜度在最壞情況下不超過O(n2).

3) FP復雜度分析.FP主要對TCD與DCD的異常檢測結果，進行相應地優(yōu)化操作，補充TCD與DCD未能發(fā)現(xiàn)的數(shù)據(jù)異常，同時也剔除了不存在異常的相應數(shù)據(jù).根據(jù)算法3的詳細流程，F(xiàn)P的計算復雜度為O(n2)

3 實驗研究

3.1 實驗環(huán)境

硬件環(huán)境：浪潮英信NF5270M4服務器、至強E5V4處理器、16 GB內(nèi)存、2TB硬盤.

軟件環(huán)境：JRE1.7.0_13，ZooKeeper-3.4.6，Storm0.9.1.

操作系統(tǒng)：CentOS6.5.

數(shù)據(jù)集：濟南市政供暖系統(tǒng)中394棟樓宇的16 909個住戶，預處理后的數(shù)據(jù)集為該規(guī)模下的住戶供暖情況數(shù)據(jù)集(data of Jinan municipal steam heating system, JMSHSD).

在數(shù)據(jù)收集過程中，每個樓宇的發(fā)送器每個小時聚合了該樓宇中每個房間的數(shù)據(jù)，然后將這些數(shù)據(jù)傳送給數(shù)據(jù)接收器.當一個接收器接收的數(shù)據(jù)達到閾值，或者接收器等待時間達到閾值.接收器一次將當前其接收的數(shù)據(jù)全部傳輸?shù)轿覀冾A設的DataSpout端口，并將相關數(shù)據(jù)分發(fā)至TCDBolt開始進行時序連續(xù)性檢測.當TCDBolt完成時序相關性檢測之后，多個TCDBolt將向對應的DCDBolt發(fā)送相應的傳感數(shù)據(jù)，在DCDBolt進行數(shù)據(jù)相關性檢查.與此同時，TCDBolt也會將時序連續(xù)性的檢查結果發(fā)送至FusionBolt.等待DCDBolt中對應的相關性結果檢測完畢以后，DCDBolt也會將對應的相關性檢測結果發(fā)送至FusionBolt，進行相應的異常數(shù)據(jù)集融合操作并完成最終的多源數(shù)據(jù)異常檢測的最終結果.

數(shù)據(jù)根據(jù)處理方式的不同，其相應處理平均時間對比如表1所示，其中云計算的接收數(shù)據(jù)規(guī)模較大，帶寬壓力較高，其網(wǎng)絡傳輸時間明顯比邊緣計算要長.由于云中心節(jié)點的計算能力相對較強，與邊緣計算相比，其DCD所消耗的時間較短.在TCD與FP步驟中，由于受到數(shù)據(jù)規(guī)模及帶寬的壓力，云計算的處理時間相對較高.因此通過綜合的比較與分析，邊緣計算的異常檢測性能更好.

Table 1 Comparison of Time-Consuming in Each Step表1 各階段耗費時間對比

3.2 異常檢測結果分析

本節(jié)我們對傳感數(shù)據(jù)異常檢測的實驗結果分析主要分為2個步驟：

1) 利用本文提出的異常檢測算法(ADMSD_TS)，對數(shù)據(jù)集JMSHSD中的部分傳感數(shù)據(jù)(累計熱量、熱功率、累計流量、流速以及溫差)進行相應的異常檢測，并利用數(shù)據(jù)檢測結果對ADMSD_TS算法及其內(nèi)部的TCD,DCD操作檢測的結果進行詳細的分析.

選取數(shù)據(jù)集JMSHSD中部分傳感數(shù)據(jù)(累計熱量、熱功率、累計流量、流速以及溫差)共計100 000條，相關傳感數(shù)據(jù)的參數(shù)描述如表2所示.傳感數(shù)據(jù)部分實際觀測值如表3所示.根據(jù)相應的熱力學原理對表3的部分傳感數(shù)據(jù)進行簡單的分析，不難發(fā)現(xiàn)Pi和ΔWi/Δti以及si和Δvi/Δti可能具有線性相關性，隨后我們利用相關系數(shù)的計算公式對上述傳感數(shù)據(jù)進行了相應的計算. 計算結果顯示：P和ΔW/Δt的相關系數(shù)為0.880，S和ΔV/Δt的相關系數(shù)為0.926.因此它們都滿足線性相關的約束.

Table 2 Sensor Data Parameter Description

Table 3 Sensor Data Correlation Description

利用本文提出的ADMSD_TS算法進行異常數(shù)據(jù)檢測，檢測結果如表4所示.根據(jù)檢測結果：在100 000條傳感數(shù)據(jù)中，總共有560條P，W或PW異常數(shù)據(jù)，452條V，s或Vs異常數(shù)據(jù)以及213條T異常數(shù)據(jù).異常數(shù)據(jù)總數(shù)可以表示為ADsum，成功檢測出的異常數(shù)據(jù)可以表示為ADcor，則異常數(shù)據(jù)的檢測精度ADpre的計算為

(9)

DCD只能發(fā)現(xiàn)560條異常數(shù)據(jù)中的430條(ADpre=0.77)以及452條中的382條異常數(shù)據(jù)，而且對于單一序列T，DCD則無法發(fā)現(xiàn)其中的異常數(shù)據(jù). 而TCD能發(fā)現(xiàn)560條異常數(shù)據(jù)中的476條、452條異常數(shù)據(jù)中的354條，并能夠對其發(fā)現(xiàn)的異常數(shù)據(jù)進行精確的定位.而本文提出的ADMSD_TS算法能夠對DCD以及TCD的數(shù)據(jù)檢測結果進行相應的數(shù)據(jù)融合操作，從而有效地避免了上述2個方法所存在的缺陷，因此ADMSD_TS算法的檢測結果要明顯好于前面的2個相對單一的異常數(shù)據(jù)檢測方法.

Table 4 Anomaly Detection Results

2) 基于數(shù)據(jù)集JMSHSD中的全部傳感數(shù)據(jù)，分別利用本文提出的異常檢測算法(ADMSD_TS)與基準方法(AD_IP[18]，AD_KNN[19])進行傳感數(shù)據(jù)異常檢測，并對實驗結果進行比較與分析.

我們選取數(shù)據(jù)集JMSHSD中近一年的全部傳感數(shù)據(jù)共計2 016 983條，并將全部數(shù)據(jù)以月為單位分別利用ADMSD_TS，AD_IDP以及AD_KNN進行數(shù)據(jù)異常檢測.隨后計算異常數(shù)據(jù)檢測精度ADpre的平均值，最后得到的異常數(shù)據(jù)檢測結果如圖5所示：

Fig. 5 Comparison of abnormal detection precision圖5 異常數(shù)據(jù)檢測精度對比

根據(jù)圖5所示的異常數(shù)據(jù)檢測精度比較，不難發(fā)現(xiàn)ADMSD_TS算法的檢測結果要明顯好于AD_IDP與AD_KNN.以上2個對比方法雖然分別采用基于時間序列重要點分割以及基于快速選擇策略的k-近鄰搜索去尋找相應的異常數(shù)據(jù)，但是上述方法并沒有很好地利用多源時間序列之間“廣泛”存在的相關關系對時間序列數(shù)據(jù)的變化趨勢進行準確地判斷，從而無法對多源相關數(shù)據(jù)異常進行有效地識別.因此上述方法的異常數(shù)據(jù)檢測精度與ADMSD_TS算法相比，具有相對明顯的差距.

4 結 論

本文提出了一種新的基于離群距離與序列相關性的異常檢測算法，該算法采用邊緣計算的處理模型，通過對參數(shù)之間的相關性與參數(shù)自身的時序連續(xù)性對相應的傳感數(shù)據(jù)進行檢測.通過在濟南市政供暖數(shù)據(jù)集上的進行的算法驗證，本算法具有處理速度快、異常檢出率高的特性.未來我們還將繼續(xù)優(yōu)化該算法的邊緣計算模型，并希望能將該檢測算法推廣到更廣泛的實時數(shù)據(jù)應用場景中.

[1] Shi Weisong, Sun Hui, Cao Jie, et al. Edge computing—An emerging computing model for the Internet of everything era[J]. Journal of Computer Research and Development, 2017, 54(5): 907-924 (in Chinese)

(施巍松, 孫輝, 曹杰, 等. 邊緣計算:萬物互聯(lián)時代新型計算模型[J]. 計算機研究與發(fā)展, 2017, 54(5): 907-924)

[2] Wang Xiaqing, Fang Zicheng, Wang Peng, et al. A distributed multi-level composite index for KNN processing on long time series[C] //Proc of the 21st Int Conf on Database Systems for Advanced Applications. Berlin: Springer, 2017: 215-230

[3] Sharma A B, Chen Haifeng, Ding Min, et al. Fault detection and localization in distributed systems using invariant relationships[C] //Proc of the 43th Int Conf on Dependable Systems and Networks (DSN). Piscataway, NJ: IEEE, 2013: 1-8

[4] Barnett V, Lewis T. Outliers in Statistical Data[M]. New York: Wiley, 1994: 20-29

[5] Knox E M, Ng R T. Algorithms for mining distancebased outliers in large datasets[C] //Proc of the 24th Int Conf on Very Large Data Bases. San Francisco: Morgan Kaufmann, 1998: 392-403

[6] Knorr E M, Ng R T. Finding intensional knowledge of distance-based outliers[J]. Journal of Very Large Data Bases, 1999, 99(12): 211-222

[7] Ramaswamy S, Rastogi R, Shim K. Efficient algorithms for mining outliers from large data sets[C] //Proc of the 29th Int Conf on Management of Data. New York: ACM, 2000: 427-438

[8] Markou M, Singh S. Novelty detection: A review—part 2: Neural network based approaches[J]. Signal Processing, 2003, 83(12): 2499-2521

[9] Mour?o-Miranda J, Hardoon D R, Hahn T, et al. Patient classification as an outlier detection problem: An application of the one-class support vector machine[J]. Neuroimage, 2011, 58(3): 793-804

[10] Wang J S, Chiang J C. A cluster validity measure with outlier detection for support vector clustering[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2008, 38(1): 78-89

[11] Fu T-C. A review on time series data mining[J]. Engineering Applications of Artificial Intelligence, 2011, 24(1): 164-181

[12] Vlachos M, Philip S Y, Castelli V. On periodicity detection and structural periodic similarity[C] //Proc of the SIAM Int Conf on Data Mining. Society for Industrial and Applied Mathematics. Philadelphia: SIAM, 2005: 449-460

[13] Keogh E, Lonardi S, Chiu B Y. Finding surprising patterns in a time series database in linear time and space[C] //Proc of the 8th Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2002: 550-556

[14] Keogh E, Lin J, Lee S -H, et al. Finding the most unusual time series subsequence: Algorithms and applications[J]. Knowledge and Information Systems, 2007, 11(1): 1-27

[15] Chan P K, Mahoney M V. Modeling multiple time series for anomaly detection[C] //Proc of the 5th IEEE Int Conf on Data Mining. Piscataway, NJ: IEEE, 2005: 90-97

[16] Wei Li, Kumar N, et al. Assumption-free anomaly detection in time series[C] //Proc of the 17th Int Conf on Scientific and Statistical Database Management. Piscataway, NJ: IEEE, 2005: 237-242

[17] Fujimaki R, Yairi T, Machida K. An anomaly detection method for spacecraft using relevance vector learning[C] //Proc of the Advances in Knowledge Discovery and Data Mining. Berlin: Springer, 2005: 785-790

[18] Zhou Dazhuo, Liu Yuefen, Ma Wenxiu. Time series anomaly detection[J]. Journal of Computer Engineering and Applications, 2008, 44(35): 145-147 (in chinese)

(周大鐲, 劉月芬, 馬文秀. 時間序列異常檢測[J]. 計算機工程與應用, 2008, 44(35): 145-147)

[19] Cai Lianfang, Thornhill N F, Kuenzel S, et al. Real-time detection of power system disturbances based onk-nearest neighbor analysis[J]. IEEE Access, 2017, 5(3): 5631-5639

[20] Armbrust M, Fox A, Griffith R, et al. A view of cloud computing[J]. Communications of the ACM, 2010, 53(4): 50-58

[21] Shvachko K, Kuang H, Radia S, et al. The hadoop distributed file system[C] //Proc of the 26th Symp on Mass Storage Systems and Technologies (MSST). Piscataway, NJ: IEEE, 2010: 1-10

[22] Zaharia M, Chowdhury M, Franklin M J, et al. Spark: Cluster computing with working sets[J]. HotCloud, 2010, 15(1): 10-17

[23] Moon Y S, Whang K Y, Loh W K. Duality-based subsequence matching in time-series databases[C] //Proc of the 17th Int Conf on Data Engineering. Piscataway, NJ: IEEE, 2001: 263-272

[24] Ji Cun, Shao Qingshi, Sun Jiao, et al. Device data ingestion for industrial big data platforms with a case study[J]. Sensors, 2016, 16(3): Article No.279

[25] Fang Wei. Paradigm shift from cloud computing to fog computing and edge computing[J]. Journal of Nanjing University of Information Science & Technology, 2016, 8(5): 404-414 (in Chinese)

(方巍. 從云計算到霧計算的范式轉變[J]. 南京信息工程大學學報, 2016, 8(5): 404-414)