陳業(yè)斌， 王仁偉，李 穎

(1.安徽工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 安徽 馬鞍山 243032；2.馬鞍山師范高等?？茖W(xué)校 教師教育系， 安徽 馬鞍山 243041)

?

無線傳感器網(wǎng)絡(luò)中基于采樣的時空數(shù)據(jù)恢復(fù)

陳業(yè)斌1， 王仁偉1，李 穎2

(1.安徽工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 安徽 馬鞍山 243032；2.馬鞍山師范高等?？茖W(xué)校 教師教育系， 安徽 馬鞍山 243041)

隨著智慧城市步伐的深入，對物理環(huán)境感知的要求越來越高；無線傳感器網(wǎng)絡(luò)被廣泛部署到真實環(huán)境中去收集各種各樣的環(huán)境數(shù)據(jù)，比如溫度、濕度、光照度和二氧化碳的含量等。當(dāng)無線傳感器網(wǎng)絡(luò)的規(guī)模很大時，巨大的數(shù)據(jù)傳輸量嚴(yán)重阻礙了無線傳感器網(wǎng)絡(luò)的長時間有效運(yùn)行。矩陣填充作為一個新的稀疏表示技術(shù)，可以通過低秩矩陣中少量隨機(jī)采樣進(jìn)行數(shù)據(jù)重構(gòu)。由于傳感數(shù)據(jù)的時空相關(guān)性，相鄰傳感器節(jié)點和時間節(jié)點的數(shù)據(jù)信息相對冗余，故采用分塊采樣的策略進(jìn)行稀疏采樣，在保證恢復(fù)精度的同時降低采樣率，以達(dá)到降低數(shù)據(jù)傳輸代價的目的。

無線傳感器網(wǎng)絡(luò)；稀疏采樣；矩陣填充；采樣策略

隨著信息技術(shù)的高速發(fā)展，無線傳感器網(wǎng)絡(luò)被廣泛部署在網(wǎng)絡(luò)空間中[1],用來收集各種各樣的傳感數(shù)據(jù)。ExScal[2]使用1 000個以上傳感器節(jié)點進(jìn)行網(wǎng)絡(luò)入侵檢測。CitySee系統(tǒng)[3]被用來連續(xù)收集環(huán)境數(shù)據(jù)，包括溫度、濕度、光照度和二氧化碳的含量等。無線傳感器網(wǎng)絡(luò)通常希望能長時間收集環(huán)境傳感數(shù)據(jù)。然而，傳感器節(jié)點的物理限制和大量數(shù)據(jù)的傳輸阻礙了傳感器網(wǎng)絡(luò)的長時間有效運(yùn)行。利用部署在真實環(huán)境中的傳感數(shù)據(jù)的時空相關(guān)性和稀疏表示技術(shù)，通過收集小部分?jǐn)?shù)據(jù)可以高精度恢復(fù)所有的監(jiān)測數(shù)據(jù)。

近年來，很多稀疏表示方法[5-7]已經(jīng)被用來降低無線傳感器網(wǎng)絡(luò)中的采樣代價。目前存在的方法可以分為基于壓縮感知的數(shù)據(jù)收集和基于低秩矩陣填充的數(shù)據(jù)重構(gòu)2種?；趬嚎s感知的數(shù)據(jù)收集技術(shù)利用數(shù)據(jù)向量的組合來降低數(shù)據(jù)的傳輸量。C.Luo等[5]提出一個大規(guī)模壓縮數(shù)據(jù)收集方案，可在每一條鏈路上降低傳輸代價和均衡能量代價。盡管基于壓縮傳感的數(shù)據(jù)收集技術(shù)能降低傳輸代價，但是它只能利用時間或者空間信息來降低采樣數(shù)量。同時，鏈路錯誤會嚴(yán)重影響傳感數(shù)據(jù)的恢復(fù)效果[9]。為了利用傳感數(shù)據(jù)的時空相關(guān)性，J.Cheng等[7]提出一個基于低秩矩陣填充的時空壓縮數(shù)據(jù)收集技術(shù),相對于基于壓縮傳感的收集技術(shù)能進(jìn)一步降低傳輸代價。在文獻(xiàn)[10-11]中，當(dāng)無線傳感器網(wǎng)絡(luò)中數(shù)據(jù)的丟失率變得很大時，低秩矩陣填充理論被提出來重構(gòu)傳感數(shù)據(jù)。眾所周知，目前存在的基于矩陣填充的數(shù)據(jù)收集技術(shù)都是假設(shè)傳感數(shù)據(jù)矩陣的秩是已知的，然而由于監(jiān)測數(shù)據(jù)通常是未知的，故傳感數(shù)據(jù)的秩很難計算。與此同時，真實的傳感數(shù)據(jù)實驗結(jié)果顯示：傳感數(shù)據(jù)矩陣的秩會隨時間動態(tài)變化。

為解決監(jiān)測數(shù)據(jù)矩陣秩的不確定導(dǎo)致采樣數(shù)量不確定的問題，本研究采用了采樣終止條件[8]。由于傳感數(shù)據(jù)具有時空相關(guān)性，相鄰傳感器節(jié)點和時間節(jié)點的數(shù)據(jù)信息相對冗余，為降低采樣率采用分塊采樣的策略，從而減少了數(shù)據(jù)的傳輸代價。

1 問題描述

1.1 低秩矩陣填充

矩陣填充是一個通過已知的部分矩陣元素來恢復(fù)整個低秩矩陣的新技術(shù)。假設(shè)存在矩陣M∈Rn1×n2,其中，M矩陣的(i,j)位置的元素用Mij來表示，則(i,j)的全集用Ω表示。故矩陣填充的問題就是用根據(jù)部分已知元素來恢復(fù)未知元素得到新的矩陣X，并且使得X的秩最小。矩陣填充問題的數(shù)學(xué)模型如下：

min rank(X)

s.t.PΩ(X)=PΩ(M)

(1)

采樣操作PΩ：Rn1×n2→Rn1×n2的定義如下：

(2)

由于這是一個NP-hard問題，可以用以下凸優(yōu)化模型來代替：

s.t.PΩ(X)=PΩ(M)

(3)

m≥C*n6/5*r*logn

(4)

其中n=max{n1,n2}。

1.2 問題介紹

近年來，隨著社會經(jīng)濟(jì)生活的快速發(fā)展，環(huán)境保護(hù)問題越來越受到人們的關(guān)注。世界各國都在致力于控制和減少環(huán)境污染，研究環(huán)境可持續(xù)發(fā)展的綠色方案。我國也提出了低碳經(jīng)濟(jì)的戰(zhàn)略目標(biāo)，并對環(huán)境監(jiān)控提出了更高的要求。

基于無線傳感器網(wǎng)絡(luò)的環(huán)境監(jiān)測可將大量微型傳感器節(jié)點隨機(jī)部署到感興趣的區(qū)域中，對特定區(qū)域的環(huán)境信息進(jìn)行間斷或者連續(xù)地采樣，自動積累環(huán)境的長期監(jiān)測數(shù)據(jù)。在對環(huán)境進(jìn)行監(jiān)控時，需要實時對無線傳感器網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行采樣、傳輸、處理等流程。由于傳感器網(wǎng)絡(luò)中數(shù)據(jù)量龐大，遍歷采樣需要巨大的代價，故可以通過矩陣填充技術(shù)來減少采樣數(shù)量以降低環(huán)境監(jiān)控的成本。為了進(jìn)一步降低采樣數(shù)量，可以充分利用傳感器網(wǎng)絡(luò)歷史數(shù)據(jù)進(jìn)行矩陣恢復(fù)。

在一個傳感器網(wǎng)絡(luò)中，存在M個節(jié)點，每一個節(jié)點每隔一段時間會采集一次環(huán)境數(shù)據(jù)，則在N個時間段就生成數(shù)據(jù)矩陣XM×N，歷史數(shù)據(jù)也存儲在數(shù)據(jù)庫中。故假設(shè)從歷史數(shù)據(jù)中截取矩陣X1，在XM×N中稀疏采樣，并根據(jù)X1得到XM×N的恢復(fù)矩陣。

1.3 問題建模

令XM×N為X2，則X=[X1;X2],其中X1的維度是M×N1，X2的維度是M×N2，并且X1已知，X2未知。本文使用二值采樣矩陣D。已知或者已采樣的元素為1，其余的為0，D的定義如下：

(5)

定義采樣矩陣S來記錄原始測量數(shù)據(jù)。矩陣S是一個不完整的監(jiān)控數(shù)據(jù)矩陣，可以表示為

SM×(N1+N2)=X*D

(6)

其中*代表兩個矩陣的點積，即Sij=Xij×Dij。根據(jù)前面介紹的矩陣填充技術(shù)，當(dāng)采樣數(shù)量足夠時，X可以通過如下公式從S中恢復(fù)得到：

s.t.S=X*D

(7)

定義從式(7)中恢復(fù)得到矩陣為X～。

1.4 挑戰(zhàn)

盡管前面介紹矩陣填充是從子數(shù)據(jù)集中高精度恢復(fù)數(shù)據(jù)，但是前提條件是需要知道數(shù)據(jù)矩陣的秩。然而，傳感器網(wǎng)絡(luò)中數(shù)據(jù)的秩未知，因此遇到的挑戰(zhàn)如下：為降低采樣代價，則冗余的采樣數(shù)量則應(yīng)該最小。然而，根據(jù)矩陣填充理論，由于不知道數(shù)據(jù)矩陣的秩，很難知道采樣數(shù)量是否足以達(dá)到準(zhǔn)確恢復(fù)的目的。

本文發(fā)現(xiàn)誤差的奇異點都集中在某些區(qū)域，為提高恢復(fù)精度，需要設(shè)計一個更有效的采樣策略來發(fā)現(xiàn)誤差奇異值區(qū)域，而不是采用簡單隨機(jī)采樣策略。然而，由于不知道數(shù)據(jù)矩陣結(jié)構(gòu)，故設(shè)計采樣策略是一個難點。

2 解決方案

2.1 采樣策略

由于測量矩陣的秩未知，很難知道多少采樣數(shù)量是足夠的，故本文提出分塊自適應(yīng)連續(xù)采樣策略。相對于后期的采樣數(shù)量，本文在初始采樣時設(shè)置一個較小的值，然后根據(jù)需要恢復(fù)的數(shù)據(jù)矩陣確定是否需要進(jìn)行更多的樣本采樣。那么采樣的終止條件是什么呢？

對于一個低秩矩陣X，給出t和t+1兩個連續(xù)采樣步驟，其中第t步采樣m個樣本，t+1額外采樣C個樣本。這兩個采樣步驟得到的恢復(fù)矩陣分別為X～(t)和X～(t+1)，如果X～(t)=X～(t+1)，則X～(t)精確等于矩陣X。

定義1 給出連個矩陣AN×N和BN×N，定義A?B，只要滿足如下條件：

≤ε

(8)

其中ε是一個非常小的常數(shù)。

定義2 采樣終止條件

定義經(jīng)過連續(xù)t和t+1兩個采樣步驟矩陣填充操作恢復(fù)出的數(shù)據(jù)分別為X～(t)和X～(t+1)。如果這兩個數(shù)據(jù)矩陣滿足X～(t)=X～(t+1)，那么認(rèn)為傳感器網(wǎng)絡(luò)數(shù)據(jù)在第t步已經(jīng)準(zhǔn)確地恢復(fù)出來，在第t+1步終止采樣操作。本文會給出理論證明。

在一個在線的監(jiān)測系統(tǒng)中，很難知道相關(guān)矩陣的特征和秩。在簡單的隨機(jī)采樣中，隨著采樣率地提高，恢復(fù)的精度和效果越來越高，最終達(dá)到一個穩(wěn)定的狀態(tài)。然而簡單隨機(jī)采樣帶有冗余采樣。為在提高恢復(fù)準(zhǔn)確率的同時降低整個采樣數(shù)，需要進(jìn)行智能化采樣?？紤]到t和t+1是兩個連續(xù)采樣步驟，令S(t)和S(t+1)分別代表這兩步驟的采樣矩陣，很明顯S(t)∈S(t+1)，恢復(fù)出的數(shù)據(jù)分別為X～(t)和X～(t+1)。當(dāng)采樣率很低時，整個數(shù)據(jù)矩陣恢復(fù)不理想的數(shù)據(jù)都集中在某些區(qū)域中。針對這一問題，本文采用分塊的思想，把整個數(shù)據(jù)均勻分割成若干小塊。由于X=[X1;X2]，X1已知，對X進(jìn)行分塊，如圖1所示。

圖1 X的采樣結(jié)構(gòu)分布

(9)

計算第K個分塊的每一個元素的INFO值，并統(tǒng)計均值EK和方差SK。評估第K個分塊的恢復(fù)情況，用INFOK來表示：

INFOK=a*EK+b*SK

(10)

如果分塊K的INFOK很大，這意味著這個分塊的恢復(fù)效果不是很理想，需要在下一步增加采樣量。因此，本文的采樣策略就是在恢復(fù)不理想的分塊中增加采樣量，INFOK值越大，需要采樣的數(shù)量就越多。

2.2 理論分析

本文定義LM是矩陣X精確恢復(fù)的最低采樣閾值。由于X=[X1;X2]，則LM1是X1的最低采樣閾值，LM2是X2的最低采樣閾值，故有LM=LM1+LM2。m是第t步的采樣數(shù)，m+C是第t+1步的采樣數(shù)。要證明X～(t)=X～(t+1)成立的條件是m+C>m>LM。由于X=[X1;X2]，則有m=m1+m2，m1是在X1中的采樣數(shù)，m2是在X2中的采樣數(shù)。則有：

m1+m2+C>m1+m2>LM1+LM2

(11)

對不等式三邊同時減去LM1得：

m1-LM1+m2+C>m1-LM1+m2>+LM2

(12)

令m1-LM1=δ>0，那么有

m2+C+δ>m2+δ>LM2

(13)

為證明X～(t)=X～(t+1)成立的條件是上面的表達(dá)式，本文的證明分為3個部分：

1) 當(dāng)m2+C+δ>m2+δ>LM2時，很明顯有X～(t)=X～(t+1)=X。 2) 當(dāng)m2+C+δ>LM2>m2+δ時，X2～(t+1)=X2，X2～(t)≠X2，因此X～(t)≠X～(t+1)。

因此，綜合上面3種情況，本文得出X～(t)=X～(t+1) 成立的條件是m+C>m>LM。

2.3 算法實現(xiàn)

算法實現(xiàn)流程見表1。

3 實驗過程及結(jié)果

3.1 傳感器網(wǎng)絡(luò)數(shù)據(jù)

本研究的數(shù)據(jù)來源于無錫清華信息科學(xué)與技術(shù)國家實驗室GreenOrbs(綠野千傳)系統(tǒng)。關(guān)于GreenOrbs的詳細(xì)信息請參考文獻(xiàn)[14]。GreenOrbs系統(tǒng)[15]在森林部署330個傳感節(jié)點，以監(jiān)控森林的濕度、光照、二氧化碳等環(huán)境參數(shù)。實景分布圖和網(wǎng)絡(luò)拓?fù)鋱D如圖2所示。

表1 算法實現(xiàn)流程

圖2 GreenOrbs的實景分布圖的拓?fù)鋱D

3.1.1 硬件

GreenOrbs的傳感器節(jié)點是TelosB，其中該節(jié)點的處理器和收發(fā)器分別是MSP430和CC420，程序閃存為48 KB，測量串口閃存為1 024 KB，RAM是10 KB。

3.1.2 軟件和協(xié)議

GreenOrbs傳感器節(jié)點的操作系統(tǒng)是TinyOS2.1。主要的數(shù)據(jù)流是鏈路節(jié)點中多跳數(shù)據(jù)收集。同時，F(xiàn)TSP協(xié)議[16]的功能使得全網(wǎng)同步。

3.2 傳感器網(wǎng)絡(luò)數(shù)據(jù)預(yù)處理

本文的實驗數(shù)據(jù)是一個真實的傳感器網(wǎng)絡(luò)數(shù)據(jù)，傳感器網(wǎng)絡(luò)有部分節(jié)點未采集到數(shù)據(jù)，故傳感器網(wǎng)絡(luò)歷史數(shù)據(jù)存在部分零值的元素使得矩陣的秩很高，需要對歷史數(shù)據(jù)進(jìn)行預(yù)處理操作，本文使用奇異值收縮的方法進(jìn)行預(yù)處理，具體操作如下：

對X∈Rn1×n2進(jìn)行奇異值分解如下：

X=U×∑×V*, ∑=diag({σi})

對于每個τ≥0，有軟閾值操作Dτ:

Dτ(X):=U×Dτ(∑)×V*

Dτ(∑)=diag({σi-τ}+)

其中τ+表示τ的非負(fù)部分，即τ+=max(0,τ)。這個軟閾值操作僅僅應(yīng)用在矩陣X1的奇異值上，使它們趨于0，這樣可以降低X1的秩。

3.3X1對X2恢復(fù)的影響

在矩陣填充的理論中，隨著采樣率的提高恢復(fù)精度也會越來越高，然而在恢復(fù)效果很好時，相應(yīng)的采樣率又很大。為了在保證恢復(fù)精度的同時降低采樣率，采樣傳感器網(wǎng)絡(luò)歷史數(shù)據(jù)X1來降低X2采樣率。在X2相同采樣率下，對比X1對X2的恢復(fù)影響，如圖3所示。

圖3 X1對X2恢復(fù)的影響

3.4ε對X2恢復(fù)的影響

根據(jù)采樣終止條件，當(dāng)采樣終止條件觸發(fā)時，X～(t)和X～(t+1)之間的差距小于閾值ε。為了驗證ε對X2恢復(fù)精度和采樣率的影響，使用不同的ε運(yùn)行本文的算法。實驗結(jié)果如圖4、5所示。

圖4 對X2恢復(fù)精度的影響

圖5 對X2恢復(fù)采樣率的影響

從圖4、5中不難發(fā)現(xiàn)：ε越小X2的恢復(fù)精度越高，同時對X2的采樣率也相應(yīng)提高。為了調(diào)節(jié)采樣率和準(zhǔn)確率之間的平衡，實驗觀測當(dāng)ε=0.03時，相對誤差只有2.26%，并且采樣率只有32.7%，故設(shè)置ε=0.03。

3.5 分塊大小對實驗的影響

為分析分塊的粗細(xì)粒度對X2恢復(fù)的影響，本文采用大小分別為4×4,8×8,16×16,32×32,64×64的分塊去運(yùn)行采樣算法，得到的結(jié)果如圖6、7所示。從圖6、7可以發(fā)現(xiàn)：分塊的大小對最終的采樣率和恢復(fù)精度影響都不大，故本文最終采用分塊的大小為8×8。

圖6 分塊大小對X2恢復(fù)誤差的影響

圖7 分塊大小對X2恢復(fù)采樣率的影響

4 結(jié)束語

為了降低傳感器網(wǎng)絡(luò)中數(shù)據(jù)的監(jiān)測成本，本文利用歷史數(shù)據(jù)極大地降低了采樣率和提高了恢復(fù)準(zhǔn)確率；使用了采樣終止條件解決了矩陣秩的未知的難題。此外，本文采用了分塊的技術(shù)解決了冗余信息集中的問題。冗余信息集中在一起，無須全部采樣，只需采樣部分即可準(zhǔn)確恢復(fù)周圍全部數(shù)據(jù)，這樣進(jìn)一步降低了采樣率，提高了系統(tǒng)對數(shù)據(jù)采樣的效率。

[1] YICK J,MUKHERJEE B,GHOSAL D.Wireless sensor network survey[J].Computer Networks,2008,52(12):2292-2330.

[2] ARORA A,RAMNATH R,ERTIN E,et al.Exscal:Elements of an extreme scale wireless sensor network[C]//11th IEEE International Conference on Embedded and Real-Time Computing Systems and Applications (RTCSA’05).USA:IEEE,2005:102-108.

[3] LIU Y,MAO X,HE Y,et al.CitySee:Not only a wireless sensor network[J].IEEE Network,2013,27(5):42-47.

[4] ANASTASI G,CONTI M,DI FRANCESCO M,et al.Energy conservation in wireless sensor networks:A survey[J].Ad hoc networks,2009,7(3):537-568.

[5] LUO C,WU F,SUN J,et al.Compressive data gathering for large-scale wireless sensor networks[C]//Proceedings of the 15th annual international conference on Mobile computing and networking.2009:145-156.

[6] WU X,XIONG Y,YANG P,et al.Sparsest random scheduling for compressive data gathering in wireless sensor networks[J].IEEE Transactions on Wireless Communications,2014,13(10):5867-5877.

[7] CHENG J,YE Q,JIANG H,et al.STCDG:an efficient data gathering algorithm based on matrix completion for wireless sensor networks[J].IEEE Transactions on Wireless Communications,2013,12(2):850-861.

[8] XIE K,WANG L,WANG X,et al.Sequential and adaptive sampling for matrix completion in network monitoring systems[C]//2015 IEEE Conference on Computer Communications(INFOCOM).USA:IEEE,2015:2443-2451.

[9] WU X,YANG P,JUNG T,et al.Compressive sensing meets unreliable link:sparsest random scheduling for compressive data gathering in lossy WSNs[C]//Proceedings of the 15th ACM international symposium on Mobile ad hoc networking and computing.2014:13-22.

[10]KONG L,XIA M,LIU X Y,et al.Data loss and reconstruction in wireless sensor networks[J].IEEE Transactions on Parallel and Distributed Systems,2014,25(11):2818-2828.

[11]XIE K,NING X,WANG X,et al.Recover Corrupted Data in Sensor Networks:a Matrix Completion Solution[J].IEEE Transactions on Mobile Computing,2017 (99):1434-1448.

[12]WU Xiaopei,LIU Mingyan,WU Yue.In-situ soil moisture sensing:Optimal sensor placement and field estimation[J].TOSN,2012,8(4):33.

[13]WANG J,TANG S,YIN B,et al.Data gathering in wireless sensor networks through intelligent compressive sensing[C]//INFOCOM,2012 Proceedings IEEE.2012:603-611.

[14]LIU Y,HE Y,LI M,et al.Does wireless sensor network scale A measurement study on GreenOrbs[J].IEEE Transactions on Parallel and Distributed Systems,2013,24(10):1983-1993.

[15]GreenOrbs系統(tǒng)[EB/OL].[2016-11-12].http://www.greenorbs.org/

(責(zé)任編輯 楊黎麗)

Sampling-Aware Based Accurate Spatial-Temporal Data Completion for Wireless Sensor Networks

CHEN Ye-bin1, WANG Ren-wei1, LI Ying2

(1.College of Computer Science and Technology, Anhui University of Technology, Ma’anshan 243032, China; 2.School of Science and Engineering, Ma’anshan Teacher’s College, Ma’anshan 243041, China)

With the deepening of smart city, the requirements of physical environment sensoring are becoming higher and higher. Wireless sensor networks (WSNs) have been built for continuously collecting environmental data including temperature, humidity, illumination and carbon dioxide etc. Unfortunately, extremely large amount of data transmission hinder the large-scale WSNs long time running. As a newly emerging technique, matrix completion, concerns the recovery of a low-rank matrix from incomplete samples of its entries. Because of the spatial-temporal correlation in sensor data, data from adjacent node in adjacent time slots are redundant, so we use the block sampling strategy for sparse sampling to reduce the data transmission cost.

wireless sensor networks; sparse sampling; matrix completion; sampling strategies

2017-01-16

安徽省教育廳科學(xué)研究重大項目 (KJ2015ZD39)

陳業(yè)斌(1971—)，男，安徽全椒人，教授，主要從事計算機(jī)網(wǎng)絡(luò)及數(shù)據(jù)庫研究；王仁偉(1991—)，男，安徽天長人，碩士研究生，主要從事無線傳感器網(wǎng)絡(luò)及室內(nèi)定位研究，E-mail: wangrenweiahut@163.com。

陳業(yè)斌， 王仁偉，李穎.無線傳感器網(wǎng)絡(luò)中基于采樣的時空數(shù)據(jù)恢復(fù)[J].重慶理工大學(xué)學(xué)報(自然科學(xué))，2017(6):127-133.

format：CHEN Ye-bin, WANG Ren-wei, LI Ying.Sampling-Aware Based Accurate Spatial-Temporal Data Completion for Wireless Sensor Networks[J].Journal of Chongqing University of Technology(Natural Science)，2017(6):127-133.

10.3969/j.issn.1674-8425(z).2017.06.019

TN929

A

1674-8425(2017)06-0127-07