一種基于網線傳感器網絡的數據補全算法

讓 濤，王立松

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

一種基于網線傳感器網絡的數據補全算法

讓 濤，王立松

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

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

無線傳感網；數據異常；數據缺失；數據補全；Ioptspace算法

1 概 述

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

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

常用的缺失數據處理方法有如下四種：

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

(2)用全局變量或屬性的平均值替換所有的缺失數據，并作為屬性的一個新值[7]。這種方法適用于數據穩定的情況，考慮了感知數據在時間維度上連續變化的特點。

(3)缺失數據的K-近鄰估計方法[6]，用全局變量或屬性均值代替缺失值，不能有效地處理感知數據的非平穩變化。K-近鄰算法考慮了感知數據的空間相關性(在規定閾值內，由于數據的空間相關性，鄰居節點之間的數據值相差甚小)，用其鄰居節點的數據來估計缺失節點的值。

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

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

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

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中的非零特征值的平方根。

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

(2)

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

(3)

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

(4)

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

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

(5)

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

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

(6)

3 Ioptspace算法

3.1 Ioptspace算法描述

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

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

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

(7)

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

Ioptspace算法函數形式為：

[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為含缺失數據的樣本矩陣，0表示缺失處數據；niter為最大迭代次數，默認為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; /*循環次數記錄*/

/*調整對角陣與左/右奇異向量*/

(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算法性能分析

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

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

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

4 實 驗

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

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

(8)

4.1 實驗數據

文中在公用數據集上進行實驗分析，包括伯克利實驗室布置的無線傳感器網絡環境收集的數據集以及巴西圣塔倫Tapajos國家森林高塔上采集的氣象數據。對于伯克利實驗室數據，分別從電壓、濕度、溫度和亮度四個屬性進行實驗分析。對于巴西圣塔倫的氣象數據樣本，分別從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共十個屬性。同時，針對時間維度上的均勻變化，分別提取數據樣本對每個屬性的缺失進行數據補全估計。考慮到數據的空間相關性，基于空間相關性的缺失數據補全算法提取了兩組數據屬性：T64、T40、T10、T2屬性組和Ucup_64、Ucup_50、Ucup_40屬性組。同時，依據鄰居節點的當前數據值，估計當前節點在此刻的數據值。文中所提的Ioptspace算法不僅考慮時間相關性和空間相關性，同時對缺失數據進行整體屬性的缺失估計。

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

4.2 對比實驗

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

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

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

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

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

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

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

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

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

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

圖4 伯克利實驗數據樣本的Ioptspace算法實驗結果

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

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

圖5 巴西圣塔倫氣象數據的Ioptspace算法實驗結果

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

4.3 實驗結果分析

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

另外，隨著鄰居節點數的增加，基于空間相關性算法的估計誤差值也逐漸增大?？臻g相關性算法是基于空間相關性的，中心節點的鄰居節點增多，使得位置較遠的節點與中心節點的數據空間關聯性減弱，從而影響到當前節點的數值估計，使誤差變大。

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

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

5 結束語

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

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

[1] 魏巨巍.面向無線傳感器網絡的高效異常檢測算法研究[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] 徐蘇婭.基于無線傳感器網絡的數據異常檢測和補全算法研究[D].南京:南京航空航天大學,2012.

[5] 沈 雪.基于貝葉斯方法的缺失數據補全研究[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] 潘立強,李建中,駱吉洲.傳感器網絡中一種基于時-空相關性的缺失值估計算法[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] 潘立強,李建中.傳感器網絡中一種基于多元回歸模型的缺失值估計算法[J].計算機研究與發展,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”重點基礎研究發展計劃項目(2014CB744900,2014CB744903)

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

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