陳正宇,胡國兵,姜志鵬

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

基于矩陣補全的無線傳感器網絡收集數據重建方法*

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

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

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

感器網絡;數據收集;矩陣補全;數據重建

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

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

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

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

1.1 系統(tǒng)模型

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

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

(1)

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

(2)

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

PΩ(S)=PΩ(X)

(3)

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

Rij=Xij+Zij

(4)

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

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

(5)

式中:Z為行形式的結構化噪聲矩陣。

1.2 問題描述

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

(6)

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

2 算法設計

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

(7)

式中:‖·‖F為矩陣Frobenius范數,參數τ用來調整彈性網正則化項對原問題的擾動程度。易知該問題的Lagrangian函數為:

(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得到:

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

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

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

應用梯度下降法可得:

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

算法1 EnRMC

輸入:R,λ,τ和δ,最大迭代次數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為收集數據矩陣中丟失的數據元素個數,則pn=n/(N×T)為數據丟失率。未丟失數據的比例為ps=1-pn,也稱為數據采樣率。m表示存在錯誤收集數據的傳感器節(jié)點數。將存在錯誤收集數據的傳感器節(jié)點占所有傳感器節(jié)點的比例稱為傳感器節(jié)點故障率,記pm=m/N。為了評估算法性能,采用Intel室內項目[5]的真實數據進行算法驗證。采用溫度數據作為實驗數據,收集52個傳感器節(jié)點在連續(xù)300個時隙中采集的數據,即N=52,T=300,環(huán)境數據矩陣為XN×T。利用XN×T合成得到收集數據矩陣RN×T。具體過程為:

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

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

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

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

3.2 性能參數定義

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

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

(11)

(12)

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

圖1 不同數據丟失率下的缺失元素恢復誤差

3.3 仿真結果和分析

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

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

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

圖3 不同故障率下含錯數據行整體恢復誤差

4 結論

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

[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 室內項目. 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] 陳蕾,楊庚,陳正宇,等. 基于結構化噪聲矩陣補全的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-),男,江蘇淮安人,漢族,博士,副教授,金陵科技學院電子信息工程學院副院長,研究領域為無線傳感器網絡數據收集與管理,zych@jit.edu.cn。