基于空間結構的無線傳感器網絡缺失值估計方法

李微微，馬衛

（南京旅游職業學院，江蘇南京，211000）

0 引言

無線傳感器網絡（Wireless Sensor Networks，WSNs）是一種全新的信息獲取和處理技術，其在軍事、環境監測、災難救援、工業控制、智能家居等諸多領域得到廣泛應用，是信息領域的研究重點。無線傳感器節點通常直接暴露在外部環境中，天氣狀況、傳感器器件自身穩定性、人為因素等等原因都會導致通信鏈路的頻繁斷接，從而導致采集到的感知數據在傳輸中存在數據丟失或者數據異常的現象。

傳統針對缺失數據的處理方法包括三類：一是直接刪除缺失數據；二是不對數據進行任何處理，直接使用目前的算法；三是對缺失數據進行填充。第一類方法雖然簡單，易用，但是隨著“大數據時代”的到來，數據的稀疏特性越來越嚴重，缺失數據量也逐漸增多，丟棄缺失數據項不但影響數據的整體特征，甚至會嚴重影響數據挖掘的結果，使操作人員做出錯誤的判斷，造成重大人為損失。而第二類方法，則必須面臨傳統的數據挖掘算法都是針對完全數據進行處理這一現狀，需要對經典算法進行相應修改后方能使之適用于缺失數據，更為重要的是這種修改任務繁重，有些甚至是無法實現的。此外，雖然目前出現了一些針對不完全數據的分析算法，但通常存在算法復雜度高、處理效果不佳等問題。因此對缺失數據進行填充是不完全數據處理的最理想方法。所謂不完全數據填充值得是通過其他已知輔助信息，運用特定方法或模型，求出最接近缺失數據的一個或者多個預測值，之后用預測值對缺失數據進行填充，獲得完整數據集，并使得數據集應盡量趨近于原始數據集。

近年來，研究人員針對WSNs的數據恢復問題提出了一系列的模型和算法，并取得了可見成效。如Nan提出了基于相關規則挖掘的傳感數據恢復方法；Li等人提出了基于物理和統計模型的傳感數據恢復方法；2010年，潘立強等人提出了基于時空相關的傳感數據估計算法。值得一提的是，WSNs數據的相鄰時間點間具有較強的相關性，例如溫度傳感器和光照強度傳感器的前后時間點之間就存在一定程度的關聯性，而這種在時間軸上的平滑演化效應可以在數學模型上即是典型的低秩結構。通常，這種低秩結構在WSN數據中，可以通過矩陣分解的方法得到使用，如仵博等人便利用非負矩陣分解的方法對WSNs收集到的數據進行壓縮，并取得了良好的效果。然而，需要注意的是，WSNs中除了存在時間上的關聯外，傳感器節點與節點之間還存在空間上的關聯，例如溫度傳感器中位置鄰近的傳感器相比間隔較遠的傳感器，其溫度變化規律將更為相似，因此當這個溫度傳感器出現數據缺失時，鄰近的傳感器的數值顯然更具參考作用。同時肖甫等人的研究也證明在矩陣補全中，引入更為嚴格的約束將會信息恢復的準確性。

本文針對WSNs數據缺失問題，提出一種基于空間結構約束的矩陣補全方法。該方法在進行數據恢復的同時，不僅考慮到了WSNs時間上的關聯，而且添加了空間上的結構約束。實驗證明本文方法能顯著提高數據恢復的準確度。

1 方法

1.1 矩陣補全

若M中無噪或僅包含高斯噪聲，且?分布均勻且足夠大，公式（2）的最小值唯一且會與公式（1）的最小值相吻合，可以精確地恢復出目標矩陣?。但若觀測數據受到噪聲影響，存在部分遠超正常范圍的數據，公式（2）則為：

1.2 基于結構約束的矩陣補全

低秩結構意味著M的行與列之間存在線性相關，但這種相關性通常不是結構化的。因此當矩陣M存在某種結構關系時，我們可以通過增加正則化項的方式來約束矩陣補全的解空間，使其更加接近真實值。在本文面對的傳感器網絡數據中，其天然的帶有空間上的結構約束，而在數學上，我們可以將這種結構信息表示為圖結構。

上式中包含了不可微分項，因此需要借助交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）進行求解，ADMM將原問題的目標函數進行等價分解為若干個較易找到局部解的子問題，從而得到原問題的全局解，是解決可分離凸規劃問題的一種簡單有效的方法。

其中式（5）的可分離函數為：

2 實驗

2.1 數據介紹

為了衡量實驗方法的有效性，本文采用Intel伯克利實驗室的Inter Indoor項目采集的真實傳感器數據集(http://db.lcs.mit.edu/labdata/labdata.html)進行實驗。Inter Indoor項目是在40m×30m的室內部署了54個Mica2Dot傳感器，每隔30s采集一次感知數據。本文選用溫度數據進行實驗。

2.2 結構矩陣構建

在本文中，我們分別選用了兩種稀疏化處理的方法：（1）閾值法，將距離矩陣中大于一定閾值的兩個節點視為不存在連接（本文取得閾值是0.35），這樣就只保留了節點中存在緊密關系的連接。（2）最近鄰法，根據距離矩陣，選取節點周邊連接最緊密的K個節點構建連接，值得注意得是這樣構建的結構矩陣，其每個節點的度都為k。此外，為方便優化過程，本文選擇的構建的結構矩陣并不帶權重，即存在連接該連接邊為1，反之則為0。

3 實驗結果

本文還將所提算法與經典的基于時空相關性的LM(Linear interpolation Model，LM)算法和傳統的最近鄰插值法 NNI（Nearest Neighbor Interpolation，NNI）[8]，的實驗效果進行了比較。實驗中，通過隨機標記測試數據集中的已知溫度數據為缺失值，再分別使用三種算法對缺失值進行估計，從而評價各種算法的有效性。

3.1 對比實驗

考慮到本文所要解決的問題是如何準確估計缺失數據，因此本文以算法對缺失值估計的準確性作為衡量算法性能的標準，采用估計值與原始值的均方根誤差（Root Mean Square Error，RMSE）作為評價度量。RMSE越小，表示對缺失數據恢復地越好。

一方面，感知數據的缺失間隔時間是影響算法性能的主要因素。為了測試數據缺失時間間隔對算法性能的影響，本文測試了時間間隔為1～30 min的算法性能，圖X為實驗結果?？梢园l現，不同數據缺失間隔時間下，本文算法的誤差均小于NNI與LM算法，所以缺失時間間隔并沒有對本文算法的性能產生較大影響，在于本文算法考慮到WSNs的空間結構特征，算法的準確率也更為依賴數據的空間相關性。此外，當間隔時間超過15 min后，溫度的缺失值估計精度并不會進一步提高，說明本文算法在樣本容量達到 30 后，算法的結果已趨于穩定。

圖1 不同缺失時間間隔算法性能比較

4 結束語

數據缺失問題是傳感器網絡中的固有問題。本文通過在真實傳感器采集的數據集上利用溫度值進行估計的仿真實驗證明，該方法具有較高的準確度和穩定性。