李微微，馬衛(wèi)

（南京旅游職業(yè)學(xué)院，江蘇南京，211000）

0 引言

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）是一種全新的信息獲取和處理技術(shù)，其在軍事、環(huán)境監(jiān)測(cè)、災(zāi)難救援、工業(yè)控制、智能家居等諸多領(lǐng)域得到廣泛應(yīng)用，是信息領(lǐng)域的研究重點(diǎn)。無(wú)線傳感器節(jié)點(diǎn)通常直接暴露在外部環(huán)境中，天氣狀況、傳感器器件自身穩(wěn)定性、人為因素等等原因都會(huì)導(dǎo)致通信鏈路的頻繁斷接，從而導(dǎo)致采集到的感知數(shù)據(jù)在傳輸中存在數(shù)據(jù)丟失或者數(shù)據(jù)異常的現(xiàn)象。

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

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

本文針對(duì)WSNs數(shù)據(jù)缺失問(wèn)題，提出一種基于空間結(jié)構(gòu)約束的矩陣補(bǔ)全方法。該方法在進(jìn)行數(shù)據(jù)恢復(fù)的同時(shí)，不僅考慮到了WSNs時(shí)間上的關(guān)聯(lián)，而且添加了空間上的結(jié)構(gòu)約束。實(shí)驗(yàn)證明本文方法能顯著提高數(shù)據(jù)恢復(fù)的準(zhǔn)確度。

1 方法

1.1 矩陣補(bǔ)全

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

1.2 基于結(jié)構(gòu)約束的矩陣補(bǔ)全

低秩結(jié)構(gòu)意味著M的行與列之間存在線性相關(guān)，但這種相關(guān)性通常不是結(jié)構(gòu)化的。因此當(dāng)矩陣M存在某種結(jié)構(gòu)關(guān)系時(shí)，我們可以通過(guò)增加正則化項(xiàng)的方式來(lái)約束矩陣補(bǔ)全的解空間，使其更加接近真實(shí)值。在本文面對(duì)的傳感器網(wǎng)絡(luò)數(shù)據(jù)中，其天然的帶有空間上的結(jié)構(gòu)約束，而在數(shù)學(xué)上，我們可以將這種結(jié)構(gòu)信息表示為圖結(jié)構(gòu)。

上式中包含了不可微分項(xiàng)，因此需要借助交替方向乘子法（Alternating Direction Method of Multipliers，ADMM）進(jìn)行求解，ADMM將原問(wèn)題的目標(biāo)函數(shù)進(jìn)行等價(jià)分解為若干個(gè)較易找到局部解的子問(wèn)題，從而得到原問(wèn)題的全局解，是解決可分離凸規(guī)劃問(wèn)題的一種簡(jiǎn)單有效的方法。

其中式（5）的可分離函數(shù)為：

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

2.1 數(shù)據(jù)介紹

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

2.2 結(jié)構(gòu)矩陣構(gòu)建

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 對(duì)比實(shí)驗(yàn)

考慮到本文所要解決的問(wèn)題是如何準(zhǔn)確估計(jì)缺失數(shù)據(jù)，因此本文以算法對(duì)缺失值估計(jì)的準(zhǔn)確性作為衡量算法性能的標(biāo)準(zhǔn)，采用估計(jì)值與原始值的均方根誤差（Root Mean Square Error，RMSE）作為評(píng)價(jià)度量。RMSE越小，表示對(duì)缺失數(shù)據(jù)恢復(fù)地越好。

一方面，感知數(shù)據(jù)的缺失間隔時(shí)間是影響算法性能的主要因素。為了測(cè)試數(shù)據(jù)缺失時(shí)間間隔對(duì)算法性能的影響，本文測(cè)試了時(shí)間間隔為1～30 min的算法性能，圖X為實(shí)驗(yàn)結(jié)果。可以發(fā)現(xiàn)，不同數(shù)據(jù)缺失間隔時(shí)間下，本文算法的誤差均小于NNI與LM算法，所以缺失時(shí)間間隔并沒(méi)有對(duì)本文算法的性能產(chǎn)生較大影響，在于本文算法考慮到WSNs的空間結(jié)構(gòu)特征，算法的準(zhǔn)確率也更為依賴數(shù)據(jù)的空間相關(guān)性。此外，當(dāng)間隔時(shí)間超過(guò)15 min后，溫度的缺失值估計(jì)精度并不會(huì)進(jìn)一步提高，說(shuō)明本文算法在樣本容量達(dá)到 30 后，算法的結(jié)果已趨于穩(wěn)定。

圖1 不同缺失時(shí)間間隔算法性能比較

4 結(jié)束語(yǔ)

數(shù)據(jù)缺失問(wèn)題是傳感器網(wǎng)絡(luò)中的固有問(wèn)題。本文通過(guò)在真實(shí)傳感器采集的數(shù)據(jù)集上利用溫度值進(jìn)行估計(jì)的仿真實(shí)驗(yàn)證明，該方法具有較高的準(zhǔn)確度和穩(wěn)定性。