陳正宇,胡國兵,姜志鵬

(金陵科技學院電子信息工程學院,南京 211169)

基于矩陣補全的無線傳感器網(wǎng)絡收集數(shù)據(jù)重建方法*

陳正宇*,胡國兵,姜志鵬

(金陵科技學院電子信息工程學院,南京 211169)

許多自然科學研究都利用無線傳感器網(wǎng)絡收集環(huán)境數(shù)據(jù)。收集數(shù)據(jù)的完整性和準確性決定科研結(jié)果的可靠性。然而,數(shù)據(jù)收集過程中通常會出現(xiàn)數(shù)據(jù)丟失和數(shù)據(jù)錯誤等問題。為提升收集數(shù)據(jù)的可用性,需要從含有錯誤元素的不完整數(shù)據(jù)集中恢復丟失的數(shù)據(jù)。利用環(huán)境數(shù)據(jù)的低秩特性,提出一種基于彈性網(wǎng)正則化的結(jié)構(gòu)化噪聲矩陣補全算法(EnRMC),既能實現(xiàn)丟失數(shù)據(jù)的有效恢復,也能精確判斷收集到錯誤數(shù)據(jù)的傳感器節(jié)點。利用真實數(shù)據(jù)進行仿真,實驗結(jié)果表明算法性能優(yōu)于現(xiàn)有算法,能以較高的精度重建環(huán)境數(shù)據(jù)。

感器網(wǎng)絡;數(shù)據(jù)收集;矩陣補全;數(shù)據(jù)重建

在環(huán)境、農(nóng)作物生長和生物習性監(jiān)測等科學研究中,通常需要利用無線傳感器網(wǎng)絡收集的感知數(shù)據(jù)來開展科學研究[1-2]。相關(guān)研究和決策的準確性依賴于收集數(shù)據(jù)的完整性和正確性[3]。然而,由于無線傳感器網(wǎng)絡的固有特性,數(shù)據(jù)收集過程中會出現(xiàn)數(shù)據(jù)丟失和數(shù)據(jù)錯誤[4]。例如,在伯克利Intel項目[5]中,通過3個星期的觀察,發(fā)現(xiàn)接近40%的數(shù)據(jù)丟失和8%的數(shù)據(jù)錯誤[6]。因此,利用收集到的含有錯誤元素的不完整數(shù)據(jù)集重建環(huán)境數(shù)據(jù)具有重要的意義。

傳統(tǒng)的缺失數(shù)據(jù)恢復方法是利用收集數(shù)據(jù)之間的時空相關(guān)性實現(xiàn)缺失數(shù)據(jù)的恢復,如各類插值算法等。這些算法在數(shù)據(jù)丟失率較低的情況下效果較好,當數(shù)據(jù)丟失率升高時,恢復性能急劇下降[7]。近幾年,隨著矩陣補全理論的廣泛應用,文獻[8]首次提出利用矩陣補全技術(shù)進行數(shù)據(jù)收集,將數(shù)據(jù)恢復問題建模成缺失數(shù)據(jù)矩陣的補全問題,實現(xiàn)較小的恢復誤差。在文獻[8]基礎上,文獻[9]提出空時壓縮數(shù)據(jù)收集方法STCDG,利用數(shù)據(jù)的瞬時穩(wěn)定性,在求解矩陣補全的最優(yōu)解時提供穩(wěn)定性約束,實現(xiàn)更低的恢復誤差。文獻[10]分析了無線傳感器網(wǎng)絡收集數(shù)據(jù)丟失模式,利用收集數(shù)據(jù)的低秩特性、時間和空間相關(guān)性等特征,提出一種缺失數(shù)據(jù)恢復方法。文獻[11]提出聯(lián)合矩陣補全和稀疏限定的數(shù)據(jù)恢復方法DRMCSC,將傳感器網(wǎng)絡數(shù)據(jù)稀疏約束和矩陣補全結(jié)合在一個優(yōu)化問題中,并設計交替最小化算法,實現(xiàn)缺失數(shù)據(jù)的恢復。以上這些算法僅考慮丟失數(shù)據(jù)的恢復問題,對于無線傳感器網(wǎng)絡收集數(shù)據(jù)的錯誤問題,以及數(shù)據(jù)錯誤對缺失數(shù)據(jù)恢復精度的影響均沒有考慮。對于錯誤數(shù)據(jù)的檢測問題,已有研究通常利用數(shù)據(jù)相關(guān)性和統(tǒng)計特性來檢測錯誤數(shù)據(jù)。文獻[12-13]分別提出基于直方圖和基于收集數(shù)據(jù)統(tǒng)計特性的Outlier數(shù)據(jù)檢測方法。文獻[14]提出利用序列檢測方法來發(fā)現(xiàn)傳感器網(wǎng)絡中的錯誤數(shù)據(jù)。文獻[15]研究異常收集數(shù)據(jù)和鏈路中斷的存在對數(shù)據(jù)收集精確度的影響,并基于壓縮感知理論辨別和糾正異常收集數(shù)據(jù),從而推斷中斷鏈路。上述這些算法都沒有考慮數(shù)據(jù)丟失對于錯誤數(shù)據(jù)檢測的影響。

本文利用無線傳感器網(wǎng)絡收集環(huán)境數(shù)據(jù)矩陣的低秩特性,將含有錯誤收集數(shù)據(jù)情況下缺失數(shù)據(jù)恢復問題建模為結(jié)構(gòu)化噪聲矩陣補全問題,并提出一種基于彈性網(wǎng)正則化的結(jié)構(gòu)化噪聲矩陣補全算法(Elastic-net Regularization based Matrix Completion with Structral Noise,EnRMC)。EnRMC算法能以較高的精度恢復缺失數(shù)據(jù),同時能辨識出含有錯誤數(shù)據(jù)的傳感器節(jié)點。

1 系統(tǒng)模型與問題描述

1.1 系統(tǒng)模型

假設監(jiān)測區(qū)域內(nèi)有N個傳感器節(jié)點{v1,v2,…,vN},用于感知不同類型的環(huán)境數(shù)據(jù)。采用周期性數(shù)據(jù)收集策略。每個收集時間間隔為τs,也稱為一個時隙。假設監(jiān)測總時間為T個時隙,則對于某一類環(huán)境數(shù)據(jù),總的數(shù)據(jù)量為N×T個。用X表示收集的環(huán)境數(shù)據(jù)矩陣,即

X=(X(i,j))N×T

(1)

式中:X(i,j),i=1,2,…N,j=1,2,…T,表示節(jié)點vi,在第j個時隙收集到的某一類環(huán)境數(shù)據(jù)。由于存在數(shù)據(jù)丟失,Sink節(jié)點得到的是一個有很多元素丟失的不完全矩陣,稱為采樣矩陣,用S表示。該矩陣的任意元素可以表示為:

(2)

我們定義Ω?[N]×[T]([N]={1,…,N},T={1,…,T})為采樣元素在采樣矩陣中的下標索引集合。PΩ(·)為正交投影算子,表示當(i,j)∈Ω時,Sij為采樣元素,即有:

PΩ(S)=PΩ(X)

(3)

除數(shù)據(jù)丟失外,某些傳感器節(jié)點收集的數(shù)據(jù)容易出現(xiàn)錯誤,也就是收集數(shù)據(jù)矩陣某些行的數(shù)據(jù)元素容易發(fā)生錯誤?？蓪㈠e誤數(shù)據(jù)表示為原始環(huán)境數(shù)據(jù)疊加上噪聲值。假設第i個傳感器,在第j個時隙收集的數(shù)據(jù)發(fā)生錯誤,設這個錯誤值為Rij,可以表示為:

Rij=Xij+Zij

(4)

式中:Xij為原始環(huán)境數(shù)據(jù),Zij為噪聲值。對于這類行元素的錯誤問題,可視為采樣矩陣受到行形式的結(jié)構(gòu)化噪聲污染。將Sink節(jié)點最終收集的數(shù)據(jù)矩陣稱為收集數(shù)據(jù)矩陣,記為R,則有:

PΩ(R)=PΩ(X+Z)

(5)

式中:Z為行形式的結(jié)構(gòu)化噪聲矩陣。

1.2 問題描述

數(shù)據(jù)重建就是利用Sink節(jié)點收集到的數(shù)據(jù)矩陣R來重建環(huán)境數(shù)據(jù)矩陣X?；谖墨I[9-10]分析的環(huán)境數(shù)據(jù)矩陣的低秩特性,將數(shù)據(jù)重建問題建模為矩陣補全問題[16]。為了有效地平滑結(jié)構(gòu)化噪聲,將其帶來的不利影響盡可能降到最低,引入矩陣L2,1范數(shù)正則化參數(shù)到標準矩陣補全問題。對目標函數(shù)施加正則化約束,從而將含有錯誤數(shù)據(jù)條件下的無線傳感器網(wǎng)絡缺失數(shù)據(jù)恢復問題建模為基于L2,1范數(shù)正則化的結(jié)構(gòu)化噪聲矩陣補全問題:

(6)

式中:R∈n1×n2為收集數(shù)據(jù),X為優(yōu)化矩陣,Z為噪聲矩陣,‖X‖*為X的核范數(shù),‖Z‖2,1為矩陣Z的L2,1范數(shù),用來平滑結(jié)構(gòu)化噪聲;λ是一個用來平衡結(jié)構(gòu)化噪聲和矩陣低秩程度的可調(diào)參數(shù)。

2 算法設計

為了增加結(jié)構(gòu)化噪聲矩陣補全問題式(6)求解的穩(wěn)定性,引入彈性網(wǎng)正則化技術(shù)[17]到矩陣補全問題中,提出一種基于彈性網(wǎng)正則化的結(jié)構(gòu)化噪聲矩陣補全算法(EnRMC)。EnRMC算法采用Frobenius范數(shù)正則化控制解的穩(wěn)定性,首先將問題(6)松弛為如下近似問題(7):

(7)

式中:‖·‖F(xiàn)為矩陣Frobenius范數(shù),參數(shù)τ用來調(diào)整彈性網(wǎng)正則化項對原問題的擾動程度。易知該問題的Lagrangian函數(shù)為:

(8)

進一步,由于該問題為凸集合上的凸優(yōu)化問題且滿足Slater條件,因此強對偶性成立,其全局最優(yōu)解(X*,Y*,Z*)滿足:

(9)

可采用如下交替迭代方法求解(X*,Y*,Z*):

(10)

下面依次給出計算Xk+1,Zk+1和Yk+1的具體步驟:

在求解子問題1之前先給出如下定義和定理:假設矩陣X∈n1×n2的奇異值分解(SVD)為X=UΣVT,Σ=diag({σi|1≤i≤min(n1,n2)}),若矩陣X的秩為r,即Σ=diag({σi|1≤i≤r且σ1≥σ2≥…≥σr>0}),如果τ≥0,則τ對應的奇異值閾值算子定義為:Dτ(X)=USτ(Σ)VT,其中Sτ(Σ)=diag({max(0,σi-τ)|i=1,2,…,r})[18]。

定理1[18]對任意τ,μ>0,Z∈n1×n2,有

證明略,詳見文獻[18].

將式(8)代入子問題1得到:

根據(jù)定理1可得:Xk+1=Dτ(PΩ(Yk))。

顯然,子問題2可以一般化為如下優(yōu)化問題:

求解優(yōu)化上述問題時,由于矩陣D依賴于目標變量Z,因此D也是未知變量,從而導致函數(shù)tr(ZTDZ)仍然不可微。因此,提出一種交替更新算法來求解該問題,即:在每一次迭代中,首先固定變量D求目標變量Z,然后再根據(jù)求得的Z更新D,直到算法收斂時迭代結(jié)束。

應用梯度下降法可得:

Yk+1=Yk+δPΩ(R-Xk+1-Zk+1)。

算法1 EnRMC

輸入:R,λ,τ和δ,最大迭代次數(shù)max_K,max_T。

1 INITIALIZEX0=0,Z0=0;

2Y0=PΩ(R-X0-Z0);

3 FORk=0 to max_K

4 (U,Σ,V)=svd(Yk);

5Xk+1=USτ(Σ)VT;

6 INITIALIZED0=I;

7 FORt=1 to max_T

10t=t+1;

11 END FOR

12Yk+1=Yk+δPΩ(R-Xk+1-Zk+1);

13k=k+1;

14 END FOR

3 仿真實驗

3.1 實驗條件

為了便于闡述,給出一些基本定義。設n為收集數(shù)據(jù)矩陣中丟失的數(shù)據(jù)元素個數(shù),則pn=n/(N×T)為數(shù)據(jù)丟失率。未丟失數(shù)據(jù)的比例為ps=1-pn,也稱為數(shù)據(jù)采樣率。m表示存在錯誤收集數(shù)據(jù)的傳感器節(jié)點數(shù)。將存在錯誤收集數(shù)據(jù)的傳感器節(jié)點占所有傳感器節(jié)點的比例稱為傳感器節(jié)點故障率,記pm=m/N。為了評估算法性能,采用Intel室內(nèi)項目[5]的真實數(shù)據(jù)進行算法驗證。采用溫度數(shù)據(jù)作為實驗數(shù)據(jù),收集52個傳感器節(jié)點在連續(xù)300個時隙中采集的數(shù)據(jù),即N=52,T=300,環(huán)境數(shù)據(jù)矩陣為XN×T。利用XN×T合成得到收集數(shù)據(jù)矩陣RN×T。具體過程為:

步驟1 根據(jù)數(shù)據(jù)采樣率ps,隨機產(chǎn)生采樣元素的下標索引集合Ω。依據(jù)Ω從環(huán)境數(shù)據(jù)矩陣XN×T中采樣元素,得到合成數(shù)據(jù)矩陣RN×T,滿足:

步驟2 基于傳感器節(jié)點故障率pm,確定存在錯誤收集數(shù)據(jù)的傳感器節(jié)點數(shù)m=|pm×N|,從RN×T中隨機選取m行,并將這m行中50%的非零元素疊加隨機噪聲Zij。假設錯誤數(shù)據(jù)的下標索引集合為。得到最終的合成數(shù)據(jù)矩陣RN×T,滿足:

式中:Zij是均值為0,方差為δ2的正態(tài)分布隨機變量,即Zij～N(0,δ2)。

通過上述兩個步驟可以得到用于實驗的收集數(shù)據(jù)矩陣RN×T。執(zhí)行算法后,將恢復的數(shù)據(jù)矩陣和環(huán)境數(shù)據(jù)矩陣XN×T進行對比,來衡量算法性能。對于λ,τ和δ等可調(diào)參數(shù)自適應設置的理論研究還沒有展開,本文依據(jù)所處理問題的先驗知識對可調(diào)參數(shù)進行交叉驗證。

3.2 性能參數(shù)定義

為了衡量算法性能,給出一些性能參數(shù)的定義。

(1)缺失元素恢復誤差εM,表示恢復缺失環(huán)境數(shù)據(jù)的精確程度。其可以表示為:

(11)

(12)

式中:E表示收集數(shù)據(jù)矩陣中含有錯誤數(shù)據(jù)的行的集合。

圖1 不同數(shù)據(jù)丟失率下的缺失元素恢復誤差

3.3 仿真結(jié)果和分析

將本文提出的EnRMC算法與DRMCSC[11]和STCDG[9]進行對比分析。對比數(shù)據(jù)是15次隨機實驗結(jié)果的平均值。圖1給出在不同數(shù)據(jù)丟失率的情況下,算法恢復性能對比。設置傳感器節(jié)點故障率15%,數(shù)據(jù)丟失率pn在10%到95%之間。為了便于觀察算法性能,將恢復誤差通過兩張圖片顯示。圖1(a)設置數(shù)據(jù)丟失率從10%到80%,以10%遞增。圖2(b)設置數(shù)據(jù)丟失率從80%到95%,以5%遞增。如圖1所示,所有算法對缺失元素的恢復誤差隨著數(shù)據(jù)丟失率的增加而增加,但EnRMC算法對缺失元素恢復誤差明顯低于其他算法。在數(shù)據(jù)丟失率比較低的情況下,幾種算法恢復誤差都較小;當數(shù)據(jù)丟失率超過85%時,恢復誤差急劇增加。在數(shù)據(jù)丟失率比較高的時候,EnRMC相比于其他算法有著更明顯的優(yōu)勢。

圖2給出不同傳感器節(jié)點故障率的情況下,算法性能對比。圖2中,設置數(shù)據(jù)丟失率pn=50%,傳感器節(jié)點故障率從5%到50%,每次遞增5%。隨著含有錯誤數(shù)據(jù)傳感器節(jié)點數(shù)量的增加,所有算法對缺失元素的恢復誤差也隨之增加,但EnRMC始終優(yōu)于其他算法,并且當傳感器節(jié)點故障率增加時,EnRMC的優(yōu)越性更加明顯。

圖2 不同故障率下缺失元素恢復誤差

圖3 不同故障率下含錯數(shù)據(jù)行整體恢復誤差

4 結(jié)論

針對無線傳感器網(wǎng)絡數(shù)據(jù)收集過程中出現(xiàn)的數(shù)據(jù)丟失和數(shù)據(jù)錯誤等問題,提出一種存在數(shù)據(jù)錯誤和缺失的無線傳感器網(wǎng)絡收集數(shù)據(jù)重建方法。該方法利用環(huán)境數(shù)據(jù)矩陣低秩特性,將無線傳感器網(wǎng)絡收集數(shù)據(jù)重建問題建模為結(jié)構(gòu)化噪聲矩陣補全問題,并設計一種基于彈性網(wǎng)正則化的結(jié)構(gòu)化噪聲矩陣補全算法,實現(xiàn)缺失數(shù)據(jù)的恢復和含錯誤數(shù)據(jù)傳感器節(jié)點的識別。實驗結(jié)果表明,該方法可以顯著提高環(huán)境數(shù)據(jù)的重建精度。本文后續(xù)工作將包括利用收集數(shù)據(jù)矩陣的時間和空間相關(guān)性進一步提升數(shù)據(jù)恢復精度。

[1] Gao Hong,Fang Xiaolin,Li Jianzhong,et al. Data Collection in Multi-Application Sharing Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2015,26(2):403-412.

[2] Habib C,Makhoul A,Darazi R,et al. Self-Adaptive Data Collection and Fusion for Health Monitoring Based on Body Sensor Networks[J]. IEEE Transactions on Industrial Informatics,2016,12(6):2342-2352.

[3] Xiang L,Luo J,Rosenberg C. Compressed Data Aggregation:Energy-Efficient and High-Fidelity Data Collection[J]. IEEE/ACM Transaction on Networking,2013,21(6):1722-1735.

[4] Kamal A R M,Bleakley C,Dobson S. Packet-Level Attestation(PLA):a Framework for in-Network Sensor Data Reliability[J]. ACM Transaction on Sensor Networks,2013,9(2):1-19.

[5] Intel 室內(nèi)項目. http://www.select.cs.cmu.edu/data/labapp3/index.html.

[6] Koushanfar F,Potkonjak M. Markov Chain-Based Models for Missing and Faulty Data in MICA2 Sensor Motes[C]//The 4th IEEE Conference on Sensors,Irvine,California,USA,2005:1430-1434.

[7] Kong Linghe,Xia Mingyuan,Liu Xiaoyang,et al. Data Loss and Reconstruction in Wireless Sensor Networks[J]. IEEE Transactions on Parallel and Distributed Systems,2014,25(11):2818-2828.

[8] Cheng Jie,Jiang Hongbo,Ma Xiaoqiang,et al. Efficient Data Collection with Sampling in WSNs:Making Use of Matrix Completion Techniques[C]//2010 IEEE Global Communications Conference,Miami,Florida,USA,2010:1-5.

[9] Cheng Jie,Ye Qiang,Jiang Hongbo,et al. STCDG:An Efficient Data Gathering Algorithm Based on Matrix Completion for Wireless Sensor Networks[J]. IEEE Transaction on Wireless Communication,2013,12(2):850-861.

[10] Kong Linghe,Xia Mingyuan,Liu Xiaoyang,et al. Data Loss and Reconstruction in Sensor Networks[C]//IEEE INFOCOM 2013,Turin,Italy,2013:1654-1662.

[11] He Jingfei,Sun Guiling,Zhang Ying,et al. Data Recovery in Wireless Sensor Networks with Joint Matrix Completion and Sparsity Constraints[J]. IEEE Communications Letters,2015,19(12):2230-2233.

[12] Sheng Bo,Li Qun,Mao Weizhen,et al. Outlier Detection in Sensor Networks[C]//The 8th ACM International Symposium on Mobile Ad Hoc Networking and Computing(MobiHoc)Montreal,Quebec,Canada,2007:219-228.

[13] Ding Min,Cheng Xiuzhen. Robust Event Boundary Detection in Sensor Networks—A Mixture Model Based Approach[C]//IEEE INFOCOM 2013,Rio de Janeiro,Brazil,2013:2991-2995.

[14] Guo Shuo,Zhong Ziguo,Chen Jiming,et al. Detecting Faulty Nodes with Data Errors for Wireless Sensor Networks[J]. ACM Transactions on Sensor Networks,2014,10(3):1-27.

[15] Tang Yu,Zhang Bowu,Jing Tao,et al. Robust Compressive Data Gathering in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communications,2013,12(6):2754-2761.

[16] 陳蕾,楊庚,陳正宇,等. 基于結(jié)構(gòu)化噪聲矩陣補全的Web服務QoS預測[J]. 通信學報,2015,36(6):49-59.

[17] Li Hong,Chen Na,Li Luoqing. Error Analysis for Matrix Elastic-Net Regularization Algorithms[J]. IEEE Transactions on Neural Networks and Learning Systems,2012,23(5):737-748.

[18] Cai J F,Candes E J,Shen Z. A Singular Value Thresholding Algorithm for Matrix Completion[J]. SIAM Journal of Optimization,2010,20(4):1956-1982.

DataReconstructioninWirelessSensorNetworksBasedonMatrixCompletion*

CHENZhengyu*,HUGuobing,JIANGZhipeng

(School of Electronic and Information Engineering,Jinling Institute of Technology,Nanjing 211169,China)

Many natural science researches use Wireless Sensor Networks(WSNs)to collect environmental data,and use it for scientific research. The integrity and accuracy of the collected data determine the reliability of the results. However,data loss and error usually occur during the process of data collection. Therefore,it is necessary to design an effective method to recover the missing data from the incomplete and erroneous sensory data. Based on the low-rank feature of environmental data,we design an Elastic-net Regularization based on Matrix Completion with Structural Noise(EnRMC)algorithm for reconstructing data. The proposed approach can not only effectively recover the missing data,but also exactly detect the sensor nodes with erroneous data. The simulation results show that the proposed algorithm is superior to the existing algorithms,and can reconstruct the environmental data with high precision.

wireless sensor networks;data collection;matrix completion;data reconstruction

10.3969/j.issn.1005-9490.2017.06.027

項目來源:江蘇省基礎研究計劃(自然科學基金)項目(BK20130096,BK20161516,BK20161104);金陵科技學院高層次人才工作啟動項目(jit-b-201527)

2017-07-09修改日期2017-07-20

TP311

A

1005-9490(2017)06-1466-06

陳正宇(1978-),男,江蘇淮安人,漢族,博士,副教授,金陵科技學院電子信息工程學院副院長,研究領域為無線傳感器網(wǎng)絡數(shù)據(jù)收集與管理,zych@jit.edu.cn。