讓 濤，王立松

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

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

讓 濤，王立松

(南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 210016)

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

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

1 概 述

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

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

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

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

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

(3)缺失數(shù)據(jù)的K-近鄰估計(jì)方法[6]，用全局變量或?qū)傩跃荡嫒笔е?，不能有效地處理感知?shù)據(jù)的非平穩(wěn)變化。K-近鄰算法考慮了感知數(shù)據(jù)的空間相關(guān)性(在規(guī)定閾值內(nèi)，由于數(shù)據(jù)的空間相關(guān)性，鄰居節(jié)點(diǎn)之間的數(shù)據(jù)值相差甚小)，用其鄰居節(jié)點(diǎn)的數(shù)據(jù)來估計(jì)缺失節(jié)點(diǎn)的值。

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

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

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

2 OptSpace算法原理

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

M=UΣVT

(1)

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

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

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

3 Ioptspace算法

3.1 Ioptspace算法描述

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

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

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

(7)

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

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

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

其中：S為一個(gè)r×r的矩陣；X為一個(gè)size(M_E,1)×r的矩陣；Y為一個(gè)size(M_E,2)×r的矩陣；M_E為含缺失數(shù)據(jù)的樣本矩陣，0表示缺失處數(shù)據(jù)；niter為最大迭代次數(shù)，默認(rèn)為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)

/*定義誤差表達(dá)式*/

(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結(jié)束*/

(14)end /*while結(jié)束*/

3.2 Ioptspace算法性能分析

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

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

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

4 實(shí) 驗(yàn)

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

文中采用根均方差作為對比實(shí)驗(yàn)的度量標(biāo)準(zhǔn)，計(jì)算式如下：

(8)

4.1 實(shí)驗(yàn)數(shù)據(jù)

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

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

4.2 對比實(shí)驗(yàn)

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

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

圖1 伯克利實(shí)驗(yàn)數(shù)據(jù)樣本的空間相關(guān)性算法實(shí)驗(yàn)結(jié)果

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

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

圖2 溫度屬性的空間相關(guān)性缺失

從圖2中可知，實(shí)驗(yàn)利用T60、T10和T2的數(shù)值估計(jì)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相關(guān)性的缺失數(shù)據(jù)補(bǔ)全算法比線性插值算法得到的檢測誤差更大。由于選取的距離間隔大：從2 m、10 m、40 m到60 m，空間距離增大導(dǎo)致空間相關(guān)性降低，使得檢測誤差比線性插值算法的檢測結(jié)果大。

圖3 風(fēng)速屬性的空間相關(guān)性缺失

從圖3可知,實(shí)驗(yàn)采用屬性Ucup_64和Ucup_40的數(shù)值估計(jì)得到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。同時(shí)，相比于溫度屬性的檢測誤差，風(fēng)速屬性的檢測誤差在整體上更小。無論是鄰居節(jié)點(diǎn)的數(shù)目，還是鄰居節(jié)點(diǎn)的空間距離，風(fēng)速屬性都比溫度屬性要小。因此，風(fēng)速屬性的檢測誤差更小，檢測效果更好。

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

圖4 伯克利實(shí)驗(yàn)數(shù)據(jù)樣本的Ioptspace算法實(shí)驗(yàn)結(jié)果

實(shí)驗(yàn)中，Ioptspace算法選取節(jié)點(diǎn)35為中心節(jié)點(diǎn)，節(jié)點(diǎn)1、2、33、34、36和37為鄰居節(jié)點(diǎn)，并對數(shù)據(jù)樣本屬性進(jìn)行整體補(bǔ)全。實(shí)驗(yàn)結(jié)果顯示，與線性插值算法和基于空間相關(guān)性的算法相比，Ioptspace算法的估計(jì)誤差更小；同時(shí)，對無噪聲數(shù)據(jù)和有噪聲數(shù)據(jù)，Ioptspace算法都很有效，估計(jì)效果都很好。

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

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

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

4.3 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

5 結(jié)束語

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

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

[1] 魏巨巍.面向無線傳感器網(wǎng)絡(luò)的高效異常檢測算法研究[D].南京:東南大學(xué),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)絡(luò)的數(shù)據(jù)異常檢測和補(bǔ)全算法研究[D].南京:南京航空航天大學(xué),2012.

[5] 沈 雪.基于貝葉斯方法的缺失數(shù)據(jù)補(bǔ)全研究[D].重慶:重慶大學(xué),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] 潘立強(qiáng),李建中,駱吉洲.傳感器網(wǎng)絡(luò)中一種基于時(shí)-空相關(guān)性的缺失值估計(jì)算法[J].計(jì)算機(jī)學(xué)報(bào),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] 潘立強(qiáng),李建中.傳感器網(wǎng)絡(luò)中一種基于多元回歸模型的缺失值估計(jì)算法[J].計(jì)算機(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

時(shí)間：2016-05-05

國家“973”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃項(xiàng)目(2014CB744900,2014CB744903)

讓 濤(1990-)，男，碩士研究生，研究方向?yàn)楹娇针娮酉到y(tǒng)安全性研究、無線傳感網(wǎng)絡(luò)；王立松，博士，副教授，研究方向?yàn)楹娇针娮酉到y(tǒng)安全性研究、無線傳感網(wǎng)、數(shù)據(jù)管理技術(shù)。

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