一種基于網(wǎng)線傳感器網(wǎng)絡的數(shù)據(jù)補全算法

讓 濤，王立松

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

一種基于網(wǎng)線傳感器網(wǎng)絡的數(shù)據(jù)補全算法

讓 濤，王立松

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 210016)

無線傳感網(wǎng)絡在人類社會生活中的應用越來越廣泛。同時，無線傳感網(wǎng)絡在應用中也存在諸多問題，其中包括數(shù)據(jù)異常和和數(shù)據(jù)丟失的問題。由于分布環(huán)境的影響，加上無線傳感網(wǎng)絡自身的局限性，如何有效地實現(xiàn)丟失數(shù)據(jù)的補全成為了重要的研究課題。傳統(tǒng)的無線傳感網(wǎng)絡數(shù)據(jù)補全方法針對缺失數(shù)據(jù)，根據(jù)時間或空間的相關性，主要從其單一屬性進行缺失估計，而不是從整體上對數(shù)據(jù)樣本進行多個屬性的缺失估計。據(jù)此，文中提出一種基于OptSpace的改進算法—Ioptspace算法，同時考慮時間相關性和空間相關性，把傳感網(wǎng)絡收集的數(shù)據(jù)規(guī)范化為矩陣，并從整體上對其進行補全。實驗結果表明，與線性插值算法、基于空間相關性算法相比，所提出的Ioptspace數(shù)據(jù)補全算法估計準確率更高，具有更好的效果。

無線傳感網(wǎng)；數(shù)據(jù)異常；數(shù)據(jù)缺失；數(shù)據(jù)補全；Ioptspace算法

1 概 述

無線傳感器網(wǎng)絡(Wireless Sensor Network)是由大量傳感器節(jié)點所構成。WSN能夠協(xié)作地執(zhí)行信息的實時監(jiān)測、感知和采集任務，并對數(shù)據(jù)進行處理，傳送到用戶終端[1]。由于傳感器的電源和存儲能力的限制，加上部署環(huán)境的特殊性，經(jīng)常存在數(shù)據(jù)的異常、錯誤和丟失等問題，導致無線傳感器網(wǎng)絡在應用中可信度降低。于是一系列數(shù)據(jù)異常檢測方法[2-3]、數(shù)據(jù)補全方法應運而生。文中提出一種改進的Ioptspace數(shù)據(jù)補全算法。

由于無線傳感器網(wǎng)絡的傳感器節(jié)點屬性、分布環(huán)境等的限制[4]，網(wǎng)絡中不可避免地會出現(xiàn)感知數(shù)據(jù)的缺失問題。缺失數(shù)據(jù)是指數(shù)據(jù)源中某條記錄存在一個或多個屬性值為空，也就是不完整數(shù)據(jù)[5]。如果直接丟棄缺失數(shù)據(jù)，不做任何分析，很可能得到不完整的原始數(shù)據(jù)信息；如果不對缺失數(shù)據(jù)進行補全，則無法被用到現(xiàn)有的一些分析工具中，如決策樹、K平均聚類算法等[6]。不對缺失數(shù)據(jù)進行適當?shù)奶幚?，會增加運算難度，降低分析結果的準確性和可靠性，甚至造成嚴重的后果。

常用的缺失數(shù)據(jù)處理方法有如下四種：

(1)將存在缺失數(shù)據(jù)的記錄直接丟棄[7]。這種方法對原始數(shù)據(jù)信息不作任何分析，破壞原始數(shù)據(jù)信息的完整性，影響分析結果甚至導致錯誤,造成網(wǎng)絡資源的浪費。

(2)用全局變量或?qū)傩缘钠骄堤鎿Q所有的缺失數(shù)據(jù)，并作為屬性的一個新值[7]。這種方法適用于數(shù)據(jù)穩(wěn)定的情況，考慮了感知數(shù)據(jù)在時間維度上連續(xù)變化的特點。

(3)缺失數(shù)據(jù)的K-近鄰估計方法[6]，用全局變量或?qū)傩跃荡嫒笔е担荒苡行У靥幚砀兄獢?shù)據(jù)的非平穩(wěn)變化。K-近鄰算法考慮了感知數(shù)據(jù)的空間相關性(在規(guī)定閾值內(nèi)，由于數(shù)據(jù)的空間相關性，鄰居節(jié)點之間的數(shù)據(jù)值相差甚小)，用其鄰居節(jié)點的數(shù)據(jù)來估計缺失節(jié)點的值。

(4)缺失數(shù)據(jù)的模型預測方法[7]，這種方法分析已收集的正確數(shù)據(jù)的內(nèi)在關系，并以此建立預測模型。缺失數(shù)據(jù)可以根據(jù)預測模型進行預測估計。

對于WSN的數(shù)據(jù)缺失問題，HalatchevM等在文獻[8]中給出WARM算法。該算法根據(jù)關聯(lián)規(guī)則找到出現(xiàn)數(shù)據(jù)缺失節(jié)點的關聯(lián)節(jié)點，再用該關聯(lián)節(jié)點的數(shù)據(jù)值替換缺失值。在WARM的改進算法—CARM算法[9]中，JiangN等利用關聯(lián)規(guī)則分析流數(shù)據(jù)，根據(jù)多個數(shù)據(jù)源節(jié)點找出其頻繁模式，以此模式估計缺失值。WARM算法和CARM算法雖然能有效地處理離散數(shù)據(jù)，但其對關聯(lián)規(guī)則中的閾值設定依賴性大，因此未能普遍應用。針對WARM算法和CARM算法的局限性[10]，學者們先后提出三個數(shù)據(jù)補全算法，包括線性插值(LIN)算法、空間相關性(MR)算法以及LM算法。LIN算法依據(jù)的是數(shù)據(jù)的時間相關性，MR算法考慮了數(shù)據(jù)的空間相關性。LM根據(jù)數(shù)據(jù)的具體情況選擇LIN算法或者MR算法。文獻[11]提出了如何用最少數(shù)據(jù)建立數(shù)據(jù)估計模型的算法，雖然能節(jié)省資源，但降低了估計的準確度。文獻[12]提出將WSN劃分成簇圖，利用最少的傳感器節(jié)點的觀測值，實現(xiàn)對該監(jiān)測區(qū)域內(nèi)的任意位置進行數(shù)值估計。此算法主要研究在不考慮感知數(shù)據(jù)的估計誤差情況下，實現(xiàn)使用最少的傳感器來得到感知數(shù)據(jù)。文獻[13]中指出，對于較短時間間隔內(nèi)平穩(wěn)變化的感知數(shù)據(jù)，線性插值算法[10]能實現(xiàn)較好性能的估計。然而，對于非線性相關的數(shù)據(jù)樣本的缺失數(shù)據(jù)，基于時空相關性的缺失數(shù)據(jù)補全算法具有更好的補全效果。

針對部分數(shù)據(jù)已知的感知信息，KeshavanRH等[14]提出一種OptSpace矩陣補全算法，進行重新構建。據(jù)此，文中提出一種改進算法——Ioptspace算法。通過把傳感器網(wǎng)絡收集的數(shù)據(jù)樣本當成矩陣從整體上對其進行補全，而不是對某一屬性或某幾個數(shù)據(jù)屬性分別進行補全，同時結合了時間相關性和空間相關性進行分析。實驗和分析結果表明，Ioptspace算法可以有效地解決WSN缺失數(shù)據(jù)的補全問題。

2 OptSpace算法原理

假設存在一個秩為r(r?m,n)的m×n的矩陣M，m×r的矩陣U，r×n的矩陣V以及r×r的對角陣Σ，滿足以下關系：

M=UΣVT

(1)

式中：U的列是MM*的特征向量；V的列是M*M的特征向量；Σ對角矩陣中的非零元素是MM*或M*M中的非零特征值的平方根。

為了表示收集數(shù)據(jù)樣本中的未缺失的或者正常的那些數(shù)據(jù)屬性，假設有一個矩陣E，它是矩陣M的一子集，如式(2)所示。

(2)

ME是包含M子集E的矩陣，未知的元素用0填充，元素0表示缺失或異常數(shù)據(jù)，具體如式(3)所示。

(3)

子集E是隨機的并且不唯一。確定ME后，對ME進行奇異值分解，可以得到式(4)：

(4)

其中，σi(σ1≥σ2≥…≥0)是奇異值，與特征值類似。

在矩陣ME的基礎上得到矩陣Tr(ME)，奇異值是遞減排列并且減少的特別快，所以Tr(ME)的元素可以通過前r大的奇異值近似描述。大多數(shù)情況下，全部奇異值之和的99%以上是由前10%甚至1%的奇異值的和占據(jù)，如式(5)所示：

(5)

其中：(mn/|E|)是縮放因子，它可以表示大多數(shù)缺失數(shù)據(jù)的情況；Tr(ME)是ME在秩為r的集合上的正交投影。

通過對Tr(ME)進行奇異值分解的多次迭代過程來減少Tr(ME)和M的誤差，直至誤差的給定要求被滿足。誤差表示為：

(6)

3 Ioptspace算法

3.1 Ioptspace算法描述

OptSpace算法主要思想：已知部分數(shù)據(jù)集，據(jù)此來構造新矩陣，然后計算新矩陣的補全數(shù)據(jù)與缺失數(shù)據(jù)的誤差值，最后重復迭代過程，直至原始矩陣和新矩陣的誤差值滿足設定的閾值范圍。

在OptSpace算法的基礎上，提出一種改進算法—Ioptspace算法。在Ioptspace算法中，無線網(wǎng)傳感器節(jié)點的感知數(shù)據(jù)集轉(zhuǎn)化為矩陣來處理，矩陣的行屬性表示數(shù)據(jù)屬性，矩陣的列屬性表示數(shù)據(jù)樣本。OptSpace算法的補全值與缺失值的誤差計算公式如式(2)所示，其含義為：誤差值表示的是真實值誤差與缺失數(shù)據(jù)屬性的平方和。在OptSpace算法中，誤差值并不能反映感知數(shù)據(jù)某一屬性的真實值與估計值之間的誤差，而僅僅考慮達到給定條件的情況和感知數(shù)據(jù)屬性的誤差。

Ioptspace算法誤差的表達如式(7)：

(7)

為了保證數(shù)據(jù)屬性估計值的正確性，誤差必須滿足式(3)中所示的兩個條件：數(shù)據(jù)屬性自身的誤差與數(shù)據(jù)屬性整體的誤差。

Ioptspace算法函數(shù)形式為：

[XSY]=Ioptspace(M_E,r,niter,tol1,tol2)

其中：S為一個r×r的矩陣；X為一個size(M_E,1)×r的矩陣；Y為一個size(M_E,2)×r的矩陣；M_E為含缺失數(shù)據(jù)的樣本矩陣，0表示缺失處數(shù)據(jù)；niter為最大迭代次數(shù)，默認為50；tol1,tol2為迭代的終止條件;r為重建矩陣的秩。

Ioptspace算法偽代碼如下：

(1)niter=50;tol1=1e-6;tol2=1e-6

(2)r=guessRank(M_E);

/*初始化對角陣與左/右奇異向量*/

(5)[XSY]=svds(Tr(M_E),r)

(6)i=1; /*循環(huán)次數(shù)記錄*/

/*調(diào)整對角陣與左/右奇異向量*/

(8)X=X+w;Y=Y+z;

S=getoptS(X,Y,Tr(M_E),E)

/*定義誤差表達式*/

(9)a=norm((XSY'-M_E).*E,'fro');

err1=a/sqrt(|E|);

(10)err2=sqrt(((XSY')ij-(M_E)ij)2)

/*比較誤差與終止條件直到小于終止條件*/

(11)if( err1

(12)break

(13) end /*if結束*/

(14)end /*while結束*/

3.2 Ioptspace算法性能分析

不同的數(shù)據(jù)補全算法的性能不同，文中選取了兩種比較方法進行性能分析，即線性插值算法和基于空間相關性的數(shù)據(jù)補全算法。假設數(shù)據(jù)的維度為n，數(shù)據(jù)的樣本數(shù)為m，缺失數(shù)據(jù)的樣本數(shù)為k。線性插值算法的時間復雜度最低，為O(k)，實現(xiàn)簡單。然而，基于空間相關性的缺失數(shù)據(jù)補全算法，由于其數(shù)值估計要考慮鄰居節(jié)點的數(shù)值，故算法的效率依賴于鄰居節(jié)點的個數(shù)，也與每個鄰居節(jié)點的距離等因素相關。若當前節(jié)點的鄰居節(jié)點數(shù)為l，則基于空間相關性的缺失數(shù)據(jù)補全算法的時間復雜度為O(knl)。Ioptspace算法既考慮時間相關性和空間相關性，又從整體上對數(shù)據(jù)缺失數(shù)據(jù)進行估計，故其時間復雜度最高，為O(mn+m2)。

如上所述三種算法各有其優(yōu)缺點，適用范圍也不相同。

如果數(shù)據(jù)樣本主要特點表現(xiàn)為時間相關性，那么就使用線性插值算法進行缺失數(shù)據(jù)估計；數(shù)據(jù)樣本主要特點表現(xiàn)為空間相關性，那么就使用基于空間相關性的缺失數(shù)據(jù)補全算法進行缺失數(shù)據(jù)估計；如果數(shù)據(jù)樣本的整體屬性都有缺失，并且數(shù)據(jù)樣本的時間相關性特點與空間相關性特點都不明顯，那么就可以采用Ioptspace算法實現(xiàn)缺失數(shù)據(jù)的補全。

4 實 驗

根均方差(RootMeanSquareError，RMSE)可以反映算法對缺失數(shù)據(jù)的補全效果。當根均方差較小時，對缺失數(shù)據(jù)的估計值較準確，誤差更小。

文中采用根均方差作為對比實驗的度量標準，計算式如下：

(8)

4.1 實驗數(shù)據(jù)

文中在公用數(shù)據(jù)集上進行實驗分析，包括伯克利實驗室布置的無線傳感器網(wǎng)絡環(huán)境收集的數(shù)據(jù)集以及巴西圣塔倫Tapajos國家森林高塔上采集的氣象數(shù)據(jù)。對于伯克利實驗室數(shù)據(jù)，分別從電壓、濕度、溫度和亮度四個屬性進行實驗分析。對于巴西圣塔倫的氣象數(shù)據(jù)樣本，分別從T64、T40、T10、T2、press、h2o_64m、Usonic_64、WD_64、Ucup_64和Ucup_50共十個屬性進行實驗分析，并針對不同的對比方法提取不同的屬性組進行實驗?？紤]到線性插值算法的時間相關性特點，提取了T64、T40、T10、T2、press、h2o_64m、Usonic_64、WD_64、Ucup_64和Ucup_50共十個屬性。同時，針對時間維度上的均勻變化，分別提取數(shù)據(jù)樣本對每個屬性的缺失進行數(shù)據(jù)補全估計?？紤]到數(shù)據(jù)的空間相關性，基于空間相關性的缺失數(shù)據(jù)補全算法提取了兩組數(shù)據(jù)屬性：T64、T40、T10、T2屬性組和Ucup_64、Ucup_50、Ucup_40屬性組。同時，依據(jù)鄰居節(jié)點的當前數(shù)據(jù)值，估計當前節(jié)點在此刻的數(shù)據(jù)值。文中所提的Ioptspace算法不僅考慮時間相關性和空間相關性，同時對缺失數(shù)據(jù)進行整體屬性的缺失估計。

氣象數(shù)據(jù)來自于塔上67 m高度處的氣象數(shù)據(jù)，主要包括熱量土壤、水分、水蒸氣、二氧化碳和呼吸通量等。由于這些變量大部分沒有人工填充，可以計算出凈生態(tài)系統(tǒng)交換量、二氧化碳的存儲量以及總初級生產(chǎn)力等。變量中僅對二氧化碳存儲量進行填充，以防止凈生態(tài)系統(tǒng)的交換失衡。氣象數(shù)據(jù)樣本分布在2000年6月29日至2004年3月11日期間，采樣周期較長，近三年半的時間。一共采集到64 992條數(shù)據(jù)記錄，其中每隔30 min采集一次。數(shù)據(jù)記錄主要包括溫度、濕度、熱量、二氧化碳濃度等屬性，多達50個。在屬性方面，文中分別選取了不同高度處的溫度、壓力、水蒸氣、風速等屬性進行實驗。而在時間方面，在2000-2004年間，每年選取相關的數(shù)據(jù)樣本進行實驗。

4.2 對比實驗

對于伯克利實驗室數(shù)據(jù)，采用線性插值算法進行實驗。實驗選取節(jié)點35的鄰居節(jié)點1、2、33、34、36、37，以其為感知數(shù)據(jù)樣本。以溫度、濕度和電壓三個屬性分別進行缺失數(shù)據(jù)的估計。對于節(jié)點37，分別對不同采樣間隔和不同缺失數(shù)據(jù)個數(shù)兩種情況進行實驗。伯克利實驗數(shù)據(jù)每隔31 s采集一次數(shù)據(jù)樣本，其采樣周期很短。因此，線性插值算法分別以0.5 min、2 min、4 min、6 min、8 min和10 min六種不同的采樣間隔的數(shù)據(jù)樣本進行實驗，所有的數(shù)據(jù)樣本均包含200個缺失數(shù)據(jù)。另外，缺失數(shù)據(jù)個數(shù)從25到100，依次以15遞增，采樣間隔均為31 s。由于采樣間隔很短，因此受到溫度和濕度的變化的影響很小。實驗顯示，線性插值算法的根均方差較小，估計效果比較準確。

對于伯克利實驗數(shù)據(jù)樣本和巴西圣塔倫的氣象數(shù)據(jù)樣本，采用基于空間相關性的缺失數(shù)據(jù)補全算法進行實驗。此算法考慮空間相關性，利用感知數(shù)據(jù)的空間相關性進行缺失數(shù)據(jù)估計。圖1～3分別展示了在伯克利實驗數(shù)據(jù)樣本和巴西圣塔倫的氣象數(shù)據(jù)樣本的實驗結果。

圖1 伯克利實驗數(shù)據(jù)樣本的空間相關性算法實驗結果

如圖1所示，從2到10，依次以2遞增地選取鄰居節(jié)點數(shù)。實驗結果表明，空間相關性算法與線性插值算法相比，實驗結果較差。由于傳感器節(jié)點的地理位置相對較遠，導致空間關聯(lián)性較弱。另外，數(shù)據(jù)樣本的采樣間隔僅為31 s，導致樣本本身的時間關聯(lián)性更強。因此，與線性插值算法相比，基于空間相關性的缺失數(shù)據(jù)補全算法的估計效果較差。

對于巴西圣塔倫的氣象數(shù)據(jù)樣本，分別選取了溫度和風速兩個屬性進行實驗。實驗中，分別對2 m、10 m、40 m和60 m高度的空氣溫度進行實驗，表示為T2、T10、T40和T60。以節(jié)點T40為中心節(jié)點，其余為鄰居節(jié)點，鄰居節(jié)點數(shù)目為3。對2000-2004年的數(shù)據(jù)樣本，依據(jù)空間相關性采用鄰居節(jié)點的數(shù)值估計中心節(jié)點的數(shù)據(jù)值，分別統(tǒng)計實驗結果，如圖2所示。對于風速屬性，Ucup_40、Ucup_50和Ucup_64分別表示為杯型測力計在40 m、50 m、64 m高度處測得的風速大小，實驗結果如圖3所示。

圖2 溫度屬性的空間相關性缺失

從圖2中可知，實驗利用T60、T10和T2的數(shù)值估計T40的數(shù)值，在2000-2004年間，每年數(shù)據(jù)樣本的檢測誤差分別為0.591 2、0.431 5、0.821 5、0.401 2和0.202 5，總體樣本的平均檢測誤差率為0.489 5?；诳臻g相關性的缺失數(shù)據(jù)補全算法比線性插值算法得到的檢測誤差更大。由于選取的距離間隔大：從2 m、10 m、40 m到60 m，空間距離增大導致空間相關性降低，使得檢測誤差比線性插值算法的檢測結果大。

圖3 風速屬性的空間相關性缺失

從圖3可知,實驗采用屬性Ucup_64和Ucup_40的數(shù)值估計得到Ucup_50的數(shù)值。如圖所示，2001-2004年數(shù)據(jù)樣本的檢測誤差分別為0.262 1、0.159 8、0.728 3、0.534 2和0.480 9，其中2001年的檢測誤差最小，2002年的檢測誤差最大，總體數(shù)據(jù)樣本的平均誤差為0.433 1。同時，相比于溫度屬性的檢測誤差，風速屬性的檢測誤差在整體上更小。無論是鄰居節(jié)點的數(shù)目，還是鄰居節(jié)點的空間距離，風速屬性都比溫度屬性要小。因此，風速屬性的檢測誤差更小，檢測效果更好。

圖4為Ioptspace算法在伯克利實驗數(shù)據(jù)樣本的缺失數(shù)據(jù)補全效果。

圖4 伯克利實驗數(shù)據(jù)樣本的Ioptspace算法實驗結果

實驗中，Ioptspace算法選取節(jié)點35為中心節(jié)點，節(jié)點1、2、33、34、36和37為鄰居節(jié)點，并對數(shù)據(jù)樣本屬性進行整體補全。實驗結果顯示，與線性插值算法和基于空間相關性的算法相比，Ioptspace算法的估計誤差更?。煌瑫r，對無噪聲數(shù)據(jù)和有噪聲數(shù)據(jù)，Ioptspace算法都很有效，估計效果都很好。

圖5為巴西圣塔倫氣象數(shù)據(jù)的Ioptspace算法實驗結果。

圖5 巴西圣塔倫氣象數(shù)據(jù)的Ioptspace算法實驗結果

實驗中，Ioptspace算法選取2000-2004年間的數(shù)據(jù)樣本。在無噪聲和有噪聲的條件下，對10個不同的屬性T64、T40、T10、T2、press、h2o_64m、Usonic_64、WD_64、Ucup_64和Ucup_50分別進行實驗。圖5中帶方塊虛線展示了有噪聲條件下的實驗結果，帶六邊形虛線則展示了無噪聲條件下的實驗結果。

4.3 實驗結果分析

實驗結果顯示，隨著采樣間隔的增大，線性插值算法的每個數(shù)據(jù)屬性的RMSE都在逐漸增大，即每個屬性的估計誤差逐漸在增大。因為線性插值算法是基于時間相關性的，隨著采樣間隔的變化，屬性間的時間關聯(lián)性也會發(fā)生變化。因此，缺失數(shù)據(jù)屬性的估計誤差也會受到影響。

另外，隨著鄰居節(jié)點數(shù)的增加，基于空間相關性算法的估計誤差值也逐漸增大。空間相關性算法是基于空間相關性的，中心節(jié)點的鄰居節(jié)點增多，使得位置較遠的節(jié)點與中心節(jié)點的數(shù)據(jù)空間關聯(lián)性減弱，從而影響到當前節(jié)點的數(shù)值估計，使誤差變大。

線性插值算法針對單個屬性進行缺失估計，而基于空間相關性的缺失數(shù)據(jù)補全算法，主要針對空間位置相鄰的幾個數(shù)據(jù)屬性進行缺失值估計。不同于此兩種算法，Ioptspace算法將感知數(shù)據(jù)集轉(zhuǎn)化為矩陣來處理，矩陣的行屬性表示數(shù)據(jù)屬性，矩陣的列屬性表示數(shù)據(jù)樣本。另外，Ioptspace算法通過把傳感器網(wǎng)絡收集的數(shù)據(jù)樣本當成矩陣從整體上對其進行補全，而不是對某一個或某幾個屬性分別進行補全，實現(xiàn)同步地對不同的屬性的缺失值進行估計。

實驗結果表明，與線性插值算法和基于空間相關性的算法相比，Ioptspace缺失數(shù)據(jù)補全算法的檢測誤差更小，檢測的正確率更高，整體檢測結果更好。同時，在無噪聲和有噪聲條件下的數(shù)據(jù)樣本實驗結果顯示，Ioptspace算法都很有效，估計效果都很好。

5 結束語

文中提出了一種改進的WSN缺失數(shù)據(jù)的補全Ioptspace算法，同時考慮時間相關性和空間相關性，把感知數(shù)據(jù)集轉(zhuǎn)化為矩陣來處理，并從整體上對其進行補全，而不是對某一屬性或某幾個數(shù)據(jù)屬性分別進行補全。實驗結果表明，與線性插值算法、基于空間相關性算法相比，所提出的Ioptspace數(shù)據(jù)補全算法具有更高的精確度和正確率，實驗效果更好。

Ioptspace算法雖然可以比較正確地對缺失數(shù)據(jù)進行估計，但是仍存在局限性。在重組矩陣的秩不唯一和樣本矩陣不滿足奇異值分解的情況下，該算法的效果不夠理想。在將來的工作中，會進行深入的探討研究，以期找到解決方法。

[1] 魏巨巍.面向無線傳感器網(wǎng)絡的高效異常檢測算法研究[D].南京:東南大學,2011.

[2] Markou M,Singh S.Novelty detection:a review-part 1:statistical approaches[J].Signal Processing,2003,83(12):2481-2497.

[3] Hodge V J,Austin J.A survey of outlier detection methodologies[J].Artificial Intelligence Review,2004,22(2):85-126.

[4] 徐蘇婭.基于無線傳感器網(wǎng)絡的數(shù)據(jù)異常檢測和補全算法研究[D].南京:南京航空航天大學,2012.

[5] 沈 雪.基于貝葉斯方法的缺失數(shù)據(jù)補全研究[D].重慶:重慶大學,2011.

[6] Troyanskaya O,Cantor M,Sherlock G,et al.Missing value estimation methods for DNA microarrays[J].Bioinformatics,2001,17(6):520-525.

[7] Kantardzic M.Data mining concepts,models,methods,and algorithms[M].2nd ed.[s.l.]:[s.n.],2011.

[8] LeGruenwald M H.Estimating missing values in related sensor data streams[C]//Proceedings of the 11th international conference management of data.[s.l.]:[s.n.],2005:83-94.

[9] Jiang N,Gruenwald L.Estimating missing data in data streams[M]//Advances in databases:concepts,systems and applications.Berlin:Springer,2007:981-987.

[10] 潘立強,李建中,駱吉洲.傳感器網(wǎng)絡中一種基于時-空相關性的缺失值估計算法[J].計算機學報,2010,33(1):1-11.

[11] Li Y,Ai C,Deshmukh W P,et al.Data estimation in sensor networks using physical and statistical methodologies[C]//Proc of 28th international conference on distributed computing systems.[s.l.]:IEEE,2008:538-545.

[12] Zhang H,Moura J M F,Krogh B.Estimation in sensor networks:a graph approach[C]//Proceedings of the 4th international symposium on information processing in sensor networks.[s.l.]:IEEE Press,2005.

[13] 潘立強,李建中.傳感器網(wǎng)絡中一種基于多元回歸模型的缺失值估計算法[J].計算機研究與發(fā)展,2009,46(12):2101-2110.

[14] Keshavan R H,Montanari A,Oh S.Matrix completion from a few entries[J].IEEE Transactions on Information Theory,2010,56(6):2980-2998.

A Novel Algorithm for Completion of Missing Data in Wireless Sensor Networks

RANG Tao，WANG Li-song

(School of Computer Science and Technology,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

In recent years,wireless sensor networks are widely used to promote the development and progress of human social life.However,the limitations of WSN and the influence of distribution environment conditions result in that the perception data of WSN exists problems about abnormality and loss which seriously affect the WSN application.The full complement of missing data still needs to be resolved.In wireless sensor networks,the method used in data completion mainly considers about the time correlation or spatial correlation,and only can estimate a single missing data attribute,but it fails to estimate multiple attributes of data samples.For this problem,an improved Ioptspace algorithm based on OptSpace is put forward to solve the problem.This algorithm,simultaneously considering both time and spatial correlation,fully complements data collected by the sensor network as a matrix.Experiments show that compared with the data completion method of linear interpolation and spatial correlation,the estimation effect and accuracy of Ioptspace algorithm is better.

wireless sensor networks;data anomaly;data missing;data completion;Ioptspace algorithm

2015-07-29

2015-11-05

時間：2016-05-05

國家“973”重點基礎研究發(fā)展計劃項目(2014CB744900,2014CB744903)

讓 濤(1990-)，男，碩士研究生，研究方向為航空電子系統(tǒng)安全性研究、無線傳感網(wǎng)絡；王立松，博士，副教授，研究方向為航空電子系統(tǒng)安全性研究、無線傳感網(wǎng)、數(shù)據(jù)管理技術。

http://www.cnki.net/kcms/detail/61.1450.TP.20160505.0817.058.html

TP301.6

A

1673-629X(2016)05-0040-06

10.3969/j.issn.1673-629X.2016.05.009