無線傳感器網絡中基于采樣的時空數據恢復

陳業斌， 王仁偉，李 穎

(1.安徽工業大學 計算機科學與技術學院, 安徽 馬鞍山 243032；2.馬鞍山師范高等專科學校 教師教育系， 安徽 馬鞍山 243041)

?

無線傳感器網絡中基于采樣的時空數據恢復

陳業斌1， 王仁偉1，李 穎2

(1.安徽工業大學 計算機科學與技術學院, 安徽 馬鞍山 243032；2.馬鞍山師范高等專科學校 教師教育系， 安徽 馬鞍山 243041)

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

無線傳感器網絡；稀疏采樣；矩陣填充；采樣策略

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

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

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

1 問題描述

1.1 低秩矩陣填充

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

min rank(X)

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

(1)

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

(2)

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

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

(3)

m≥C*n6/5*r*logn

(4)

其中n=max{n1,n2}。

1.2 問題介紹

近年來，隨著社會經濟生活的快速發展，環境保護問題越來越受到人們的關注。世界各國都在致力于控制和減少環境污染，研究環境可持續發展的綠色方案。我國也提出了低碳經濟的戰略目標，并對環境監控提出了更高的要求。

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

在一個傳感器網絡中，存在M個節點，每一個節點每隔一段時間會采集一次環境數據，則在N個時間段就生成數據矩陣XM×N，歷史數據也存儲在數據庫中。故假設從歷史數據中截取矩陣X1，在XM×N中稀疏采樣，并根據X1得到XM×N的恢復矩陣。

1.3 問題建模

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

(5)

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

SM×(N1+N2)=X*D

(6)

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

s.t.S=X*D

(7)

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

1.4 挑戰

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

本文發現誤差的奇異點都集中在某些區域，為提高恢復精度，需要設計一個更有效的采樣策略來發現誤差奇異值區域，而不是采用簡單隨機采樣策略。然而，由于不知道數據矩陣結構，故設計采樣策略是一個難點。

2 解決方案

2.1 采樣策略

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

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

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

≤ε

(8)

其中ε是一個非常小的常數。

定義2 采樣終止條件

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

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

圖1 X的采樣結構分布

(9)

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

INFOK=a*EK+b*SK

(10)

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

2.2 理論分析

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

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)成立的條件是上面的表達式，本文的證明分為3個部分：

1) 當m2+C+δ>m2+δ>LM2時，很明顯有X～(t)=X～(t+1)=X。 2) 當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 算法實現

算法實現流程見表1。

3 實驗過程及結果

3.1 傳感器網絡數據

本研究的數據來源于無錫清華信息科學與技術國家實驗室GreenOrbs(綠野千傳)系統。關于GreenOrbs的詳細信息請參考文獻[14]。GreenOrbs系統[15]在森林部署330個傳感節點，以監控森林的濕度、光照、二氧化碳等環境參數。實景分布圖和網絡拓撲圖如圖2所示。

表1 算法實現流程

圖2 GreenOrbs的實景分布圖的拓撲圖

3.1.1 硬件

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

3.1.2 軟件和協議

GreenOrbs傳感器節點的操作系統是TinyOS2.1。主要的數據流是鏈路節點中多跳數據收集。同時，FTSP協議[16]的功能使得全網同步。

3.2 傳感器網絡數據預處理

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

對X∈Rn1×n2進行奇異值分解如下：

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

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

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

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

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

3.3X1對X2恢復的影響

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

圖3 X1對X2恢復的影響

3.4ε對X2恢復的影響

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

圖4 對X2恢復精度的影響

圖5 對X2恢復采樣率的影響

從圖4、5中不難發現：ε越小X2的恢復精度越高，同時對X2的采樣率也相應提高。為了調節采樣率和準確率之間的平衡，實驗觀測當ε=0.03時，相對誤差只有2.26%，并且采樣率只有32.7%，故設置ε=0.03。

3.5 分塊大小對實驗的影響

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

圖6 分塊大小對X2恢復誤差的影響

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

4 結束語

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

[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系統[EB/OL].[2016-11-12].http://www.greenorbs.org/

(責任編輯 楊黎麗)

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

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

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

陳業斌， 王仁偉，李穎.無線傳感器網絡中基于采樣的時空數據恢復[J].重慶理工大學學報(自然科學)，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