肖　甫　沙朝恒　陳　蕾,2　孫力娟　王汝傳

1(南京郵電大學(xué)計(jì)算機(jī)學(xué)院　南京　210003)

2(江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué))　南京　210003)

3　　　(寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué))　南京　210003)

(xiaof@njupt.edu.cn)

?

基于范數(shù)正則化矩陣補(bǔ)全的無線傳感網(wǎng)定位算法

肖甫1,2,3沙朝恒1陳蕾1,2孫力娟1,2,3王汝傳1,2,3

1(南京郵電大學(xué)計(jì)算機(jī)學(xué)院南京210003)

2(江蘇省無線傳感網(wǎng)高技術(shù)研究重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué))南京210003)

3(寬帶無線通信與傳感網(wǎng)技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室(南京郵電大學(xué))南京210003)

(xiaof@njupt.edu.cn)

Localization Algorithm for Wireless Sensor Networks via Norm Regularized Matrix Completion

Xiao Fu1,2,3, Sha Chaoheng1, Chen Lei1,2, Sun Lijuan1,2,3, and Wang Ruchuan1,2,3

1(SchoolofComputerScienceandTechnology,NanjingUniversityofPostsandTelecommunications,Nanjing210003)2(JiangsuHighTechnologyResearchKeyLaboratoryforWirelessSensorNetworks(NanjingUniversityofPostsandTelecommunications),Nanjing210003)3(KeyLaboratoryofBroadbandWirelessCommunicationandSensorNetworkTechnology(NanjingUniversityofPostsandTelecommunications),MinistryofEducation,Nanjing210003)

AbstractLocalization is one of the important preconditions for wireless sensor networks (WSNs) applications.Traditional range-based localization algorithms need large amounts of pair-wise distance measurements between sensor nodes.However, noise and data missing are inevitable in distance ranging, which may degrade localization accuracy drastically. To address this challenge, a novel localization algorithm for WSNs based on L1-norm regularized matrix completion (L1NRMC) is proposed in this paper. By utilizing the natural low rank feature of the Euclidean distance matrix (EDM) between nodes, the recovery of partly sampled noisy distance matrix is formulated as an L1-norm regularized matrix completion problem, which is solved by alternating direction method of multipliers (ADMM) and operator splitting technology.Based on the reconstructed EDM, the classical MDS-MAP algorithm is applied to obtain the coordinates of all the unknown nodes.This algorithm can not only detect and remove outliers, but also smooth the common Gaussian noise implicitly. Simulation results demonstrate that compared with traditional node localization algorithms, our algorithm achieves high accuracy from only small fraction of distance measurements and resists various types of ranging noise, which makes our algorithm suitable for resource-limited WSNs.

Key wordswireless sensor networks (WSNs); localization; outlier; matrix completion; L1-norm regularization

摘要節(jié)點(diǎn)定位是實(shí)現(xiàn)無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)應(yīng)用的重要前提之一.針對(duì)傳統(tǒng)基于測(cè)距的定位方法需要大量節(jié)點(diǎn)距離信息以及多徑效應(yīng)、噪聲干擾等導(dǎo)致的節(jié)點(diǎn)測(cè)距誤差問題，提出了一類基于L1范數(shù)正則化矩陣補(bǔ)全(L1-norm regularized matrix completion, L1NRMC)的WSNs節(jié)點(diǎn)定位方法.該方法基于傳感網(wǎng)節(jié)點(diǎn)間距離矩陣低秩特性，將部分采樣信息下的距離恢復(fù)問題建模為稀疏野值噪聲(outlier)情形下的矩陣補(bǔ)全問題，然后采用交替方向乘子法(alternating direction method of multipliers, ADMM)結(jié)合算子分裂技術(shù)(operator splitting technology)對(duì)該問題進(jìn)行求解，所設(shè)計(jì)的非精確L1范數(shù)正則化矩陣補(bǔ)全(InExact-L1NRMC)算法不僅能顯式解析采樣矩陣中的稀疏野值噪聲，也可隱式平滑常見的高斯隨機(jī)噪聲.仿真結(jié)果表明:相比已有的同類定位方法，該算法只需進(jìn)行部分測(cè)距采樣即可實(shí)現(xiàn)精準(zhǔn)的節(jié)點(diǎn)定位，且對(duì)各類測(cè)距噪聲具有很好的抗干擾能力，適用于資源受限的WSNs.

關(guān)鍵詞無線傳感器網(wǎng)絡(luò);定位;野值噪聲;矩陣補(bǔ)全;L1范數(shù)正則化

近年來，無線傳感器網(wǎng)絡(luò)(wireless sensor networks, WSNs)技術(shù)得到快速發(fā)展，其正廣泛應(yīng)用于軍事偵查、智能交通、環(huán)境監(jiān)測(cè)等領(lǐng)域[1]，智能家居系統(tǒng)、自動(dòng)泊車距離警告、森林火險(xiǎn)監(jiān)控等均為WSNs的典型應(yīng)用.在WSNs中，節(jié)點(diǎn)自身位置信息的獲取對(duì)各種應(yīng)用至關(guān)重要.受限于節(jié)點(diǎn)能量、部署條件和經(jīng)濟(jì)因素等， 一般WSNs只有少數(shù)錨節(jié)點(diǎn)通過裝載GPS等獲取自身位置，其他未知節(jié)點(diǎn)的位置信息則由定位算法計(jì)算得到.目前已有許多解決WSNs自定位的方案[2]， 如凸規(guī)劃算法、DV-hop算法[3]、MSVR算法[4]等.整體上傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位可分為基于測(cè)距的定位算法和與測(cè)距無關(guān)的定位算法2大類，前者可實(shí)現(xiàn)較為精確的定位，但計(jì)算和通信開銷較大，且需要一定的硬件支持;后者定位精度較低，但計(jì)算開銷較小，適用于低功耗、低成本的應(yīng)用領(lǐng)域.

本文側(cè)重研究基于測(cè)距的WSNs節(jié)點(diǎn)定位算法，該類定位算法一般可描述為：已知WSNs中少量節(jié)點(diǎn)，即錨節(jié)點(diǎn)的位置信息，通過測(cè)距獲得部分或全部節(jié)點(diǎn)之間的距離數(shù)據(jù)，據(jù)此求解未知節(jié)點(diǎn)的位置信息.常見的測(cè)距定位算法包括：多點(diǎn)定位、半定規(guī)劃(semi-definite programming, SDP)算法[5-6]和MDS-MAP(multidimensional scaling and MAP)[7-8]算法等.一般情況下，這些算法均需獲知大部分距離數(shù)據(jù)且要求距離數(shù)據(jù)較為精確，否則將導(dǎo)致較大的定位誤差.然而，實(shí)際情況中受限于無線傳感器節(jié)點(diǎn)自身的能量，往往無法獲取足夠的距離數(shù)據(jù)[9];此外受噪聲因素的影響，采樣的距離數(shù)據(jù)也不可避免地存在誤差.已有研究工作[10-12]表明：在節(jié)點(diǎn)距離數(shù)據(jù)采樣中，除了常見的高斯噪聲，受節(jié)點(diǎn)硬件故障、非視距傳播、環(huán)境干擾及惡意攻擊等因素的影響，采樣的節(jié)點(diǎn)距離數(shù)據(jù)中往往還包括部分遠(yuǎn)超正常范圍的異常值噪聲干擾，本文將其稱為野值噪聲(outlier)，這類噪聲嚴(yán)重影響了傳感器節(jié)點(diǎn)的定位精度.

針對(duì)上述問題，本文提出了一種基于L1范數(shù)正則化矩陣補(bǔ)全(L1-norm regularized matrix com-pletion, L1NRMC)的WSNs定位算法.通過將無線傳感器節(jié)點(diǎn)之間的距離數(shù)據(jù)構(gòu)造成平方歐氏距離矩陣(Euclidean distance matrix, EDM)，矩陣中只包含采樣獲得的少量距離元素，且這些元素可能含有噪聲.由于節(jié)點(diǎn)間的平方距離矩陣具有低秩特性，采用擴(kuò)展的矩陣補(bǔ)全方法，綜合考慮野值噪聲和高斯噪聲，通過引入L1范數(shù)正則化因子對(duì)野值噪聲進(jìn)行平滑，將噪聲下的矩陣補(bǔ)全建模為凸優(yōu)化問題，在此基礎(chǔ)上通過交替方向乘子法(alternating direction method of multipliers, ADMM)[13]結(jié)合算子分裂技術(shù)(operator splitting technology)[14]進(jìn)行求解以補(bǔ)全和恢復(fù)距離矩陣，在此基礎(chǔ)上求解待定位節(jié)點(diǎn)的位置信息.

1相關(guān)工作

基于測(cè)距的WSNs節(jié)點(diǎn)定位算法一般包括2個(gè)步驟：1)利用某種測(cè)距方法測(cè)量節(jié)點(diǎn)之間的距離;2)利用測(cè)得的距離數(shù)據(jù)結(jié)合錨節(jié)點(diǎn)坐標(biāo)信息計(jì)算未知節(jié)點(diǎn)坐標(biāo).典型的測(cè)距方法主要包括：基于信號(hào)傳輸時(shí)間(time of arrival, TOA)的方法、基于信號(hào)傳輸時(shí)間差(time difference of arrival, TDOA)的方法以及基于信號(hào)接收信號(hào)強(qiáng)度(received signal strength indicator, RSSI)的方法.這3種測(cè)距方法各具優(yōu)勢(shì)，但均易受多路徑反射、非視距問題及環(huán)境干擾等因素影響，從而導(dǎo)致較大的測(cè)距誤差.

文獻(xiàn)[5-6]將WSNs節(jié)點(diǎn)定位問題看作歐幾里得矩陣補(bǔ)全問題和圖實(shí)現(xiàn)問題的一個(gè)變形，以測(cè)距獲得的距離數(shù)據(jù)為約束，通過引入松弛變量把非凸二次距離約束轉(zhuǎn)化為線性約束，將WSNs定位問題建模為半定規(guī)劃問題，從而獲得最優(yōu)的定位結(jié)果;文獻(xiàn)[15]利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的局部信息，提出了一種局部保持的典型相關(guān)分析模型來建立從信號(hào)空間到現(xiàn)實(shí)物理空間的映射，以獲得更高的定位精度;文獻(xiàn)[7-8]引入經(jīng)典的多維尺度(multidimensional scaling, MDS) 數(shù)據(jù)分析方法，將無線傳感器節(jié)點(diǎn)間的距離關(guān)系映射至低維空間，基于最短路徑求解節(jié)點(diǎn)間的近似距離，產(chǎn)生一個(gè)最符合節(jié)點(diǎn)間距離關(guān)系的相對(duì)坐標(biāo)地圖，并利用少量錨節(jié)點(diǎn)的位置信息將相對(duì)位置轉(zhuǎn)換為全局位置.然而，上述算法均需精確地獲取節(jié)點(diǎn)間的距離數(shù)據(jù)或基于最短路徑算法構(gòu)造節(jié)點(diǎn)距離矩陣，對(duì)采樣數(shù)量和采樣精度均有較高要求，且在網(wǎng)絡(luò)拓?fù)洳灰?guī)則時(shí)定位精度不高.但在實(shí)際的WSNs應(yīng)用中，可能只能獲取部分距離數(shù)據(jù)，并且這些數(shù)據(jù)往往存在誤差;此外從節(jié)能的角度，需盡可能減少節(jié)點(diǎn)間的測(cè)距信號(hào)傳輸.因此，對(duì)采樣的距離數(shù)據(jù)進(jìn)行修正和補(bǔ)全對(duì)于節(jié)點(diǎn)的精確定位具有重要意義.文獻(xiàn)[10]基于圖剛性理論，通過定義可檢驗(yàn)邊來進(jìn)行野值噪聲的檢測(cè)，實(shí)現(xiàn)節(jié)點(diǎn)間距離數(shù)據(jù)的修正，從而提高節(jié)點(diǎn)定位的精度;文獻(xiàn)[11]提出了一種野值魯棒的WSNs定位算法，在多點(diǎn)定位的基礎(chǔ)上引入魯棒的區(qū)域合并操作，有效消除野值噪聲以修正采樣距離數(shù)據(jù);文獻(xiàn)[12]則將節(jié)點(diǎn)定位視為一種圖嵌入問題，利用冗余剛性理論來檢測(cè)和去除距離數(shù)據(jù)中的野值噪聲，從而獲得更高的定位精度.但上述工作主要關(guān)注通過降低野值噪聲對(duì)距離數(shù)據(jù)進(jìn)行修正，從而實(shí)現(xiàn)精確的節(jié)點(diǎn)定位，其均沒有考慮節(jié)點(diǎn)距離矩陣的補(bǔ)全操作.事實(shí)上，節(jié)點(diǎn)的距離矩陣具有低秩特性，可采用矩陣補(bǔ)全算法[16]基于部分?jǐn)?shù)據(jù)采樣實(shí)現(xiàn)距離矩陣的較為精確恢復(fù).常見的矩陣補(bǔ)全算法包括奇異值閾值(singular value thresholding, SVT)算法[17]、OptSpace算法[18]、FPCA算法[19]等，當(dāng)矩陣采樣元素?zé)o噪或僅包含高斯噪聲時(shí)，這些算法均能較精確地恢復(fù)原矩陣[20]，但對(duì)于野值噪聲則效果不夠理想.文獻(xiàn)[9]綜合考慮了距離矩陣的修正和補(bǔ)全，采用秩最小化原理約束采樣距離矩陣，在此基礎(chǔ)上提出了一種新型的基于SVT的WSNs節(jié)點(diǎn)定位算法，但其只是將距離數(shù)據(jù)包含的噪聲簡(jiǎn)單地假設(shè)為單純的高斯隨機(jī)噪聲，忽略了因節(jié)點(diǎn)硬件故障、多徑傳輸?shù)葘?dǎo)致的野值噪聲的存在.事實(shí)上，少量的野值噪聲會(huì)嚴(yán)重影響節(jié)點(diǎn)定位的精確性[10].針對(duì)文獻(xiàn)[9]存在的問題，本文在距離矩陣補(bǔ)全的基礎(chǔ)上引入L1范數(shù)正則化因子以處理野值噪聲，研究并提出了一類基于L1NRMC的WSNs節(jié)點(diǎn)定位方法，從而進(jìn)一步提高定位準(zhǔn)確性.

2范數(shù)正則化矩陣補(bǔ)全算法

2.1相關(guān)數(shù)學(xué)基礎(chǔ)

定義1. 矩陣奇異值分解(singular value decom-position, SVD)[21]. 設(shè)X是一個(gè)秩為r的n1×n2維矩陣，I是r×r維的單位矩陣，則存在2個(gè)正交矩陣：

U=(u1,u2,…,ur)∈n1×r，UTU=I，

V=(v1,v2,…,vr)∈n2×r，VTV=I，

以及對(duì)角陣Σ=diag({σi|1≤i≤r})且奇異值σ1≥σ2≥…≥σr>0，滿足：

X=UΣVT，

(1)

式(1)稱為矩陣X的奇異值分解.

定義2. 矩陣范數(shù)[21].設(shè)矩陣X∈n1×n2存在如式(1)所示的奇異值分解，則：

1) 矩陣X的L0范數(shù)定義為

2) 矩陣X的L1范數(shù)定義為

3) 矩陣X的Frobenius范數(shù)定義為

定義3. 矩陣收縮算子[22]. 設(shè)矩陣X∈n1×n2，若τ≥0，則τ對(duì)應(yīng)的矩陣收縮算子定義為

其中sgn(·)為符號(hào)函數(shù).

定義4. 矩陣奇異值閾值算子[17].設(shè)矩陣X∈n1×n2存在如式(1)所示的奇異值分解，若τ≥0，則τ對(duì)應(yīng)的奇異值閾值算子定義為Dτ(X)=USτ(Σ)VT.

定理1. 對(duì)任意的τ>0，Z∈n1×n2，矩陣收縮算子Sτ(Z)滿足：

(2)

證明. 略，詳見文獻(xiàn)[22].

定理2. 對(duì)任意的τ>0，Z∈n1×n2，矩陣奇異值閾值算子Dτ(Z)滿足：

(3)

證明. 略，詳見文獻(xiàn)[17].

定理3. 假設(shè)F1，F(xiàn)2是n1×n2上2個(gè)下半連續(xù)的凸函數(shù)，且F2在n1×n2中可微并具有β-Lipschitz連續(xù)梯度，則對(duì)于凸優(yōu)化問題：

(4)

若函數(shù)F1+F2是強(qiáng)制的且嚴(yán)格凸的，則該問題存在唯一解，且對(duì)任意初始值X0及0<δ<2β，采用如下方法生成的迭代序列Xk+1是收斂到該問題的唯一解：

(5)

證明. 略，詳見文獻(xiàn)[14].

2.2L1NRMC算法

近年來，壓縮感知理論[23]為信號(hào)采集技術(shù)帶來了革命性的突破.眾所周知，壓縮感知理論要求在已知信號(hào)具有稀疏性的條件下對(duì)信號(hào)進(jìn)行采集和重構(gòu)，而在很多實(shí)際問題中，需要重構(gòu)的目標(biāo)常常是以矩陣的形式組織的.因此，壓縮感知理論便自然地從向量空間被拓展至矩陣空間，從而利用矩陣奇異值向量的稀疏性，通過采樣矩陣的部分元素來恢復(fù)低秩矩陣.在機(jī)器學(xué)習(xí)領(lǐng)域，這類問題通常被刻畫為矩陣補(bǔ)全(matrix completion, MC)問題.迄今為止，矩陣補(bǔ)全理論已在圖像修復(fù)[24]、三維運(yùn)動(dòng)估計(jì)[25]、無線傳感網(wǎng)數(shù)據(jù)收集[26]、多標(biāo)記圖像分類[27]以及視頻去噪[28]等領(lǐng)域得到了重要應(yīng)用，也逐漸成為機(jī)器學(xué)習(xí)、模式識(shí)別以及計(jì)算機(jī)視覺領(lǐng)域中的主要研究熱點(diǎn)之一.

自動(dòng)化水平也是衡量鈑金工藝先進(jìn)性的重要標(biāo)志之一。我國(guó)的鈑金企業(yè)一般可以分為民營(yíng)企業(yè)、國(guó)有企業(yè)兩種類型，其中民營(yíng)企業(yè)的占比大、數(shù)量大，但是缺乏資金與技術(shù)，在管理方面也存在許多漏洞。這樣一來，導(dǎo)致市場(chǎng)上的大部分鈑金工藝產(chǎn)品的質(zhì)量得不到保障。除此之外，由于資金投入不足，這些企業(yè)的生產(chǎn)自動(dòng)化水平達(dá)不到預(yù)期的標(biāo)準(zhǔn)，所以人員的勞動(dòng)強(qiáng)度較高，勞動(dòng)力成本占比過大，也不利于行業(yè)的平穩(wěn)快速發(fā)展，帶來了嚴(yán)重的滯后性問題。

標(biāo)準(zhǔn)的矩陣補(bǔ)全問題通常描述為

(6)

且Ω?[n1]×[n2]([n1]={1,2,…,n1}，[n2]={1,2,…,n2})為采樣元素的下標(biāo)集合，PΩ(·)為正交投影算子，表示當(dāng)(i,j)∈Ω時(shí)，Mi j為采樣元素，即：

(7)

由于矩陣的秩是一個(gè)非凸函數(shù)，該問題是一個(gè)NP-hard問題，求解該問題所需時(shí)間隨著矩陣規(guī)模的增加成指數(shù)倍增長(zhǎng).受壓縮感知理論的啟發(fā)， Candès等人[16]引入矩陣的核范數(shù)來替代矩陣的秩函數(shù)， 并且Recht等人[29]還從理論上證明了矩陣秩函數(shù)可以被其凸包核范數(shù)所取代，因此式(6)可以松弛為

(8)

目前標(biāo)準(zhǔn)矩陣補(bǔ)全問題已有多種成熟的求解算法，如Cai等人[17]提出的SVT算法、Keshavan等人[18]提出的OptSpace算法、Ma等人[19]提出的不動(dòng)點(diǎn)連續(xù)算法(fixed point continuation with approximate SVD, FPCA)及Toh等人[30]提出的加速近鄰梯度算法(accelerated proximal gradient, APG)等.當(dāng)矩陣采樣元素?zé)o噪或僅包含高斯噪聲時(shí)，這些算法均能精確地恢復(fù)目標(biāo)矩陣.但當(dāng)采樣矩陣包含稀疏的野值噪聲時(shí)，這些算法的性能將急劇下降.此處的野值噪聲即異常值，通常指代那些遠(yuǎn)超正常范圍的數(shù)據(jù)，這些數(shù)據(jù)往往意味著較大的誤差.

為有效平滑此類野值噪聲對(duì)矩陣補(bǔ)全性能的影響，本文將正則化技術(shù)引入到矩陣補(bǔ)全問題中.如何選取正則化因子通常由問題的具體要求決定.例如，為了得到壓縮感知問題的稀疏向量解，壓縮感知理論采用了向量L0范數(shù)來刻畫其稀疏性，在目標(biāo)函數(shù)中引入向量L0范數(shù)正則化因子.受此啟發(fā)，我們將稀疏野值噪聲情形下的矩陣補(bǔ)全問題建模為

(9)

由于矩陣的秩和L0范數(shù)均為非凸函數(shù)，式(9)是一個(gè)NP-hard問題.借鑒文獻(xiàn)[31]的思想，我們將矩陣的秩函數(shù)松弛為矩陣核范數(shù)，將矩陣的L0范數(shù)松弛為L(zhǎng)1范數(shù)，因此上述問題可松弛為如下凸優(yōu)化問題：

(10)

進(jìn)一步，由于實(shí)際應(yīng)用中采樣矩陣包含稀疏野值噪聲的同時(shí)往往伴隨著不同程度的高斯噪聲，因此我們?cè)谠O(shè)計(jì)式(10)的求解算法時(shí)不僅希望該算法能平滑野值噪聲也能一定程度上平滑高斯噪聲，為此我們引入優(yōu)化領(lǐng)域流行的交替方向乘子法(ADMM)來求解該問題. 交替方向乘子法的實(shí)質(zhì)是通過引入增廣拉格朗日函數(shù)將約束優(yōu)化問題轉(zhuǎn)換為無約束優(yōu)化問題，不妨設(shè)式(10)對(duì)應(yīng)的增廣拉格朗日函數(shù)為

(11)

則可以通過求解如下無約束優(yōu)化問題來求得式(10)的最優(yōu)解(X*,Y*,Z*)，即：

(12)

(13)

由交替方向乘子法易知，式(13)應(yīng)按如下方式迭代求解：

(14)

將式(11)代入子問題1后可得：

(15)

即：

(16)

進(jìn)一步考察式(16),令:

(17)

即：

(18)

進(jìn)一步，由定理2可得：

(19)

將式(11)代入子問題2后可得：

(20)

(21)

進(jìn)一步由定理1可得：

(22)

因此，我們將式(10)的上述求解過程歸納為精確的L1范數(shù)正則化矩陣補(bǔ)全算法(exact L1-norm regularized matrix completion, Exact-L1NRMC)，算法1描述了Exact-L1NRMC算法的詳細(xì)求解步驟.

算法1. Exact-L1NRMC算法.

輸入：采樣矩陣PΩ(M)、參數(shù)λ；

輸出：目標(biāo)矩陣Xopt、稀疏噪聲矩陣Zopt.

① 初始化X0=0,Z0=0,Y0=0,k=0及kX，kZ；

② while 不收斂 do

④fori=0 tokX

⑤

Zk-M)-δXPΩ(Yk));

⑥end for

⑧ forj=0 tokZ

⑨

⑩end for

Zk+1=ZkZk+1;

事實(shí)上，我們并不需要求解出子問題的精確解，只需更新X與Z各一次得到子問題的一個(gè)近似解，就足以使算法最終收斂到原問題的最優(yōu)解.據(jù)此，我們就可以得到一個(gè)更為簡(jiǎn)潔且收斂速度更快的算法，我們稱之為非精確L1NRMC算法，算法2描述了非精確L1NRMC的求解步驟.

算法2. InExact-L1NRMC算法.

輸入：采樣矩陣PΩ(M)和參數(shù)λ；

輸出：目標(biāo)矩陣Xopt、稀疏噪聲矩陣Zopt.

① 初始化X0=0,Z0=0,Y0=0,k=0；

② while 不收斂 do

③ Xk+1=DδX(Xk-δXρPΩ(Xk+Zk-M)-

δXPΩ(Yk));

④ Zk+1=SδZλ(Zk-δZρPΩ(Xk+1+Zk-M)-

δZPΩ(Yk));

⑤ Yk+1=Yk+ρPΩ(Xk+1+Zk+1-M);

⑥k=k+1;

⑦ end while

由算法2可以看出，InExact-L1NRMC算法在迭代過程中一方面可使變量Z和Y保持良好的稀疏性以節(jié)省存儲(chǔ)空間，同時(shí)還能使變量X保持好的低秩性，而且算法的每一次迭代執(zhí)行過程中只涉及一個(gè)SVD分解，這些特性確保了InExact-L1NRMC算法具有較高的時(shí)間和空間效率.

3基于矩陣補(bǔ)全的節(jié)點(diǎn)定位算法

節(jié)點(diǎn)定位技術(shù)是WSNs的重要支撐技術(shù)之一.準(zhǔn)確地獲取傳感器節(jié)點(diǎn)的位置信息，可確保數(shù)據(jù)的有效性、提高路由效率、實(shí)現(xiàn)網(wǎng)絡(luò)拓?fù)渥赃m應(yīng)配置等.在典型的WSNs應(yīng)用中，大量的WSNs節(jié)點(diǎn)被隨機(jī)部署在一個(gè)固定區(qū)域.通常情況下，如果能有效獲取節(jié)點(diǎn)間完整的距離信息，那么將很容易根據(jù)錨節(jié)點(diǎn)的坐標(biāo)計(jì)算得到未知節(jié)點(diǎn)的具體坐標(biāo).但由引言可知，我們能收集到的只是區(qū)域節(jié)點(diǎn)間的部分距離信息，而且這些距離信息往往還包含稀疏野值噪聲和高斯隨機(jī)噪聲.

現(xiàn)有的矩陣補(bǔ)全算法在采樣信息僅僅包含高斯隨機(jī)噪聲情形下效果良好，但無法有效處理稀疏野值噪聲.本文提出的稀疏野值噪聲情形下非精確L1范數(shù)正則化矩陣補(bǔ)全 (InExact-L1NRMC) 算法(即算法2)不僅能顯式處理稀疏野值噪聲，還能通過拉格朗日參數(shù)ρ的調(diào)節(jié)隱式平滑采樣矩陣中的高斯隨機(jī)噪聲.因此，我們首先將基于部分采樣信息的無線傳感網(wǎng)節(jié)點(diǎn)間距離矩陣補(bǔ)全問題建模為如下的稀疏野值噪聲情形下矩陣補(bǔ)全問題：

(23)

其中，PΩ(M)為含噪平方歐氏距離采樣矩陣，N為稀疏野值噪聲矩陣，D為待補(bǔ)全的平方歐氏距離目標(biāo)矩陣.

事實(shí)上，矩陣補(bǔ)全理論適用的前提為目標(biāo)矩陣為低秩或近似低秩.矩陣的秩為矩陣所包含的極大線性無關(guān)列向量或行向量的數(shù)目，低秩矩陣對(duì)應(yīng)的秩遠(yuǎn)小于矩陣維度，即具有較高的冗余性，因此可以通過部分元素恢復(fù)出整個(gè)矩陣.為驗(yàn)證無線傳感網(wǎng)節(jié)點(diǎn)間平方歐氏距離矩陣D的低秩性，我們采用如下引理和定理：

1) rank(A·B)≤min{rank(A),rank(B)};

2) rank(A+B)≤rank(A)+rank(B).

定理4. 假設(shè)xi∈d,i=1,2,…,n為d維空間中n個(gè)節(jié)點(diǎn)，如果記任意節(jié)點(diǎn)xi與xj之間的平方歐氏距離為Di j，則所得平方歐氏距離矩陣D的秩不超過d+2.

證明. 節(jié)點(diǎn)xi與xj之間的平方歐氏距離Di j可表示為

(24)

不妨令X=(x1,x2,…,xn)，B=XTX，1=(1,1,…,1)T表示單位n維列向量，則由式(24)可知：

(25)

其中diag(·)表示取矩陣主對(duì)角線元素的對(duì)應(yīng)列向量.

由于rank(diag(B))=rank(1T)=rank(1)=1且rank(X)≤d，根據(jù)引理1可知：

rank(D)≤rank(diag(B)·1T)+rank(1·

[diag(B)]T)+rank(-2B)≤1+1+d=d+2，

即平方歐氏距離矩陣D的秩不超過d+2.

證畢.

由于傳感網(wǎng)節(jié)點(diǎn)坐標(biāo)一般為2維或者3維向量，根據(jù)定理4易知平方歐氏距離矩陣的秩一般不超過5.由秩的定義可知，評(píng)價(jià)矩陣低秩性好壞的依據(jù)是矩陣秩和矩陣維度的比值，該比值越小其低秩性越好.由于平方歐氏距離矩陣的秩不超過d+2，因此節(jié)點(diǎn)數(shù)量越多，則平方歐氏矩陣的維度越大，低秩性將越好，其冗余性也就越高，從而其補(bǔ)全性能也越好.此外，通過采用算法2，我們不僅可以精確補(bǔ)全節(jié)點(diǎn)間距離信息，而且可以顯式解析出稀疏野值噪聲矩陣，進(jìn)而根據(jù)該矩陣精確定位出產(chǎn)生異常測(cè)距信息的節(jié)點(diǎn)對(duì)，從而為WSNs的節(jié)點(diǎn)故障診斷提供依據(jù).

WSNs節(jié)點(diǎn)定位的最終目的是為了獲得傳感節(jié)點(diǎn)的具體坐標(biāo)，經(jīng)典的多維標(biāo)度算法能有效利用完全距離矩陣信息準(zhǔn)確估算整個(gè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)之間的相對(duì)位置.在獲得了節(jié)點(diǎn)之間的相對(duì)位置信息后，本文進(jìn)一步采用多維標(biāo)度映射算法(MDS-MAP)根據(jù)錨節(jié)點(diǎn)的真實(shí)坐標(biāo)及其對(duì)應(yīng)相對(duì)坐標(biāo)之間的關(guān)系，計(jì)算出將相對(duì)位置轉(zhuǎn)換為絕對(duì)位置的坐標(biāo)變換矩陣，從而將所有節(jié)點(diǎn)的相對(duì)坐標(biāo)轉(zhuǎn)換為絕對(duì)坐標(biāo).算法3給出了基于L1范數(shù)正則化矩陣補(bǔ)全的無線傳感網(wǎng)節(jié)點(diǎn)定位算法的詳細(xì)步驟.

算法3. 基于范數(shù)正則化矩陣補(bǔ)全的定位算法.

輸入：部分含噪的距離信息PΩ(M)、坐標(biāo)維度d及錨節(jié)點(diǎn)坐標(biāo)T1,T2,T3；

輸出：所有未知位置信息的節(jié)點(diǎn)坐標(biāo){Ti|i=4,5,…,n}.

① 基于算法2計(jì)算平方距離矩陣D：

s.t.PΩ(M)=PΩ(D+N);

② 計(jì)算雙中心化相似矩陣G：

③ 對(duì)矩陣G進(jìn)行SVD分解：

[U,Σ,V]=svd(G);

④ 計(jì)算相對(duì)坐標(biāo)矩陣：

其中Ri∈d×1,Ud=U(∶,1∶d)；

⑤ 計(jì)算坐標(biāo)變換矩陣：

Q=(T2-T1,T3-T1)·(R2-R1,R3-R1)-1;

⑥ 計(jì)算并輸出所有節(jié)點(diǎn)坐標(biāo)：

{Ti=Q·(Ri-R1)+T1,i=4,5,…,n}.

由算法3可知， 基于L1范數(shù)正則化矩陣補(bǔ)全的傳感網(wǎng)節(jié)點(diǎn)定位算法主要由2部分組成，即“基于部分采樣信息的距離矩陣補(bǔ)全”(依賴于算法2)和“基于完全距離矩陣的節(jié)點(diǎn)坐標(biāo)計(jì)算”，因此其計(jì)算量主要體現(xiàn)在2次奇異值的分解上，對(duì)應(yīng)時(shí)間復(fù)雜度為O(n3).為進(jìn)一步提高算法的實(shí)時(shí)性，我們可以使用PROPACK[32]軟件包進(jìn)行部分奇異值分解，從而有效降低奇異值分解的時(shí)間復(fù)雜度.

4仿真實(shí)驗(yàn)

為驗(yàn)證算法性能，我們基于Matlab進(jìn)行了仿真實(shí)驗(yàn)：在100 m×100 m的區(qū)域內(nèi)隨機(jī)部署100個(gè)無線傳感器節(jié)點(diǎn)，其中4個(gè)節(jié)點(diǎn)為錨節(jié)點(diǎn)，其他節(jié)點(diǎn)為未知節(jié)點(diǎn).令X∈2×n為節(jié)點(diǎn)的坐標(biāo)矩陣，D∈n×n為節(jié)點(diǎn)間的平方距離矩陣(n為網(wǎng)絡(luò)中節(jié)點(diǎn)個(gè)數(shù)，本實(shí)驗(yàn)中n=100).首先對(duì)矩陣D添加噪聲干擾，得到含噪距離矩陣Dnoise;然后從Dnoise中隨機(jī)采樣部分元素作為已知的采樣距離數(shù)據(jù)，使用本文提出的算法2對(duì)采樣矩陣進(jìn)行恢復(fù);最后，利用算法3求解所有待定位節(jié)點(diǎn)的具體坐標(biāo).我們選取如下2個(gè)指標(biāo)來衡量算法性能：

1) 距離矩陣補(bǔ)全誤差

(26)

其中,D′為補(bǔ)全后的距離矩陣.ec衡量了補(bǔ)全后的距離矩陣與原始真實(shí)距離矩陣的相對(duì)誤差，其值越小，表明距離矩陣補(bǔ)全效果越好.

2) 傳感器節(jié)點(diǎn)定位誤差

(27)

其中,X′表示算法3計(jì)算得到的坐標(biāo)矩陣.el衡量了定位算法計(jì)算得到的節(jié)點(diǎn)坐標(biāo)與其真實(shí)坐標(biāo)間的絕對(duì)誤差，其值越小，表明定位效果越好.

為考察算法在不同噪聲污染情形下的性能，我們?cè)O(shè)計(jì)了4組不同的實(shí)驗(yàn).實(shí)驗(yàn)1～4分別考察在無噪聲條件、野值噪聲、高斯噪聲及高斯野值混合噪聲條件下的算法效果.4組實(shí)驗(yàn)均以文獻(xiàn)[18]所研究的基于OptSpace算法的矩陣補(bǔ)全及文獻(xiàn)[8]研究的基于SVT算法補(bǔ)全的WSNs節(jié)點(diǎn)定位算法進(jìn)行對(duì)比.

實(shí)驗(yàn)1. 無噪聲實(shí)驗(yàn)

本實(shí)驗(yàn)假設(shè)所有距離數(shù)據(jù)均為準(zhǔn)確值，不包含任何噪聲.圖1顯示了對(duì)距離矩陣進(jìn)行不同比例采樣情況下的距離矩陣補(bǔ)全誤差及傳感器節(jié)點(diǎn)定位誤差的變化情況.橫軸代表距離矩陣采樣比例，圖1(a)中縱軸代表距離矩陣補(bǔ)全誤差，圖1(b)中縱軸則代表傳感器節(jié)點(diǎn)定位誤差.

Fig. 1　Relationship between error and sampling rate without noise.圖1　無噪聲條件下誤差與采樣比例的關(guān)系

由圖1(a)可以看出，無噪聲條件下本文算法2的矩陣補(bǔ)全精度優(yōu)于SVT算法和OptSpace算法，只需采樣20%的距離數(shù)據(jù)即可得到低于0.05的補(bǔ)全誤差.對(duì)比圖1(a)與圖1(b)可知，傳感器節(jié)點(diǎn)定位誤差與距離矩陣補(bǔ)全誤差是一致的， 算法2對(duì)應(yīng)的節(jié)點(diǎn)定位誤差同樣小于SVT算法和OptSpace算法，具體在20%的采樣率條件下， 算法2對(duì)應(yīng)的節(jié)點(diǎn)定位誤差約為0.15 m.

實(shí)驗(yàn)2. 野值噪聲實(shí)驗(yàn)

本實(shí)驗(yàn)假設(shè)采樣數(shù)據(jù)僅包含野值噪聲,實(shí)驗(yàn)中野值噪聲大小由5 000～10 000 m之間隨機(jī)產(chǎn)生.對(duì)于算法2，野值噪聲比例(sparse ratio)分別設(shè)定為1%，5%，10%這3種；SVT算法和OptSpace算法則設(shè)定為5%.圖2顯示了在對(duì)距離矩陣進(jìn)行不同比例采樣情況下誤差的變化情況.

Fig. 2　Relationship between error and sampling rate under the condition of sparse outlier.圖2　野值噪聲條件下誤差與采樣比例的關(guān)系

由圖2(a)可以看到，SVT算法和OptSpace算法在野值噪聲條件下效果較差，即使當(dāng)距離數(shù)據(jù)采樣比例接近于1時(shí)補(bǔ)全誤差仍在0.15以上，這說明SVT算法和OptSpace算法無法處理野值噪聲;對(duì)于本文提出的算法2，在不同比例的野值噪聲條件下，當(dāng)距離數(shù)據(jù)采樣比例超過30%時(shí)，距離矩陣補(bǔ)全誤差均接近于0.對(duì)比圖2(a)與圖2(b)，傳感器節(jié)點(diǎn)定位誤差與距離矩陣補(bǔ)全誤差是一致的.SVT算法和OptSpace算法對(duì)應(yīng)的定位誤差較大，一般都在1 m以上;而對(duì)于本文算法2，隨著采樣比例的增加，定位誤差迅速降低，當(dāng)距離數(shù)據(jù)采樣比例達(dá)到30%時(shí)即可實(shí)現(xiàn)接近于0的定位誤差.具體到30%的采樣率，在1%，5%，10%這3種野值噪聲條件下，本文算法2對(duì)應(yīng)的定位誤差在0～0.2 m之間，野值噪聲越稀疏，則定位誤差越小.

同時(shí)，在實(shí)驗(yàn)過程中發(fā)現(xiàn)，當(dāng)采樣的距離數(shù)據(jù)到達(dá)一定比例時(shí)，本文算法2能夠較準(zhǔn)確地預(yù)測(cè)野值噪聲元素所在位置，這有助于了解無線傳感器節(jié)點(diǎn)所處的環(huán)境及其自身狀態(tài)，進(jìn)而為WSNs節(jié)點(diǎn)故障診斷、調(diào)度策略及拓?fù)湔{(diào)整等提供依據(jù).

定義野值噪聲識(shí)別率pr為

(28)

其中,mall表示算法2識(shí)別的野值噪聲元素個(gè)數(shù)，mtrue表示所識(shí)別的野值噪聲元素中的確為野值噪聲元素的個(gè)數(shù)，m表示采樣元素中包含野值噪聲的元素個(gè)數(shù).

如圖3所示，隨著距離數(shù)據(jù)采樣比例的增大，野值噪聲識(shí)別率逐步提高;當(dāng)采樣比例為40%時(shí)，稀疏噪聲元素識(shí)別率接近于1，此時(shí)絕大部分野值噪聲位置都可準(zhǔn)確預(yù)測(cè).

Fig. 3　Relationship between recognition accuracy and sampling ratio under the condition of sparse outlier.圖3　野值噪聲識(shí)別率與采樣比例的關(guān)系

實(shí)驗(yàn)3. 高斯噪聲實(shí)驗(yàn)

本實(shí)驗(yàn)假設(shè)距離數(shù)據(jù)僅包含高斯噪聲.實(shí)驗(yàn)中高斯噪聲均值為0，標(biāo)準(zhǔn)差為100.圖4顯示了對(duì)距離矩陣進(jìn)行不同比例采樣情況下誤差的變化情況.

Fig. 4　Relationship between error and sampling rate under the condition of Gaussian noise.圖4　高斯噪聲條件下誤差與采樣比例的關(guān)系

由圖4可以看出，本文提出的算法2和傳統(tǒng)SVT算法、OptSpace算法均能有效地處理高斯噪聲；算法2的矩陣補(bǔ)全精度優(yōu)于SVT算法，但與OptSpace算法相當(dāng);算法2對(duì)應(yīng)傳感器節(jié)點(diǎn)定位誤差略低于SVT算法，但與OptSpace算法相當(dāng).當(dāng)采樣比例達(dá)到30%時(shí)3種算法的定位誤差均接近0.

實(shí)驗(yàn)4. 混合噪聲實(shí)驗(yàn)

本實(shí)驗(yàn)中我們同時(shí)考慮野值噪聲與高斯噪聲的影響.實(shí)驗(yàn)中野值噪聲大小由5 000～10 000之間隨機(jī)產(chǎn)生，高斯噪聲均值設(shè)置為0，標(biāo)準(zhǔn)差設(shè)置為100;和實(shí)驗(yàn)2類似，對(duì)于算法2，噪聲比例分別設(shè)定為1%，5%和10%，SVT算法和OptSpace算法則設(shè)定為5%.實(shí)驗(yàn)結(jié)果如圖5所示.

如圖5所示，SVT算法和OptSpace算法在混合噪聲條件下誤差較大，無法實(shí)現(xiàn)節(jié)點(diǎn)的精確定位;與單一噪聲條件相比，算法2在混合噪聲條件下的距離矩陣補(bǔ)全誤差以及節(jié)點(diǎn)定位誤差在整體上均有一定幅度的增加，但當(dāng)距離數(shù)據(jù)采樣比例高于30%時(shí)，補(bǔ)全誤差和定位誤差均大幅減小并趨于穩(wěn)定，此時(shí)算法仍能實(shí)現(xiàn)較高的定位精度.具體到30%的采樣率，在1%，5%，10%這3種野值噪聲條件下，算法2對(duì)應(yīng)的定位誤差在0～0.35 m之間，野值噪聲越稀疏，對(duì)應(yīng)定位誤差越小，當(dāng)野值噪聲比例為1%時(shí)，定位誤差低于0.12 m.

Fig. 5　Relationship between error and sampling rate under the condition of mixed noise.圖5　混合噪聲條件下誤差與采樣比例的關(guān)系

圖6顯示了100個(gè)傳感器節(jié)點(diǎn)的最終定位結(jié)果.實(shí)心正方形代表錨節(jié)點(diǎn)，它們和未知節(jié)點(diǎn)一樣隨機(jī)部署在100 m×100 m的區(qū)域內(nèi);實(shí)心點(diǎn)對(duì)應(yīng)未知節(jié)點(diǎn)的實(shí)際位置；空心圓則代表采用本文算法3計(jì)算得到的節(jié)點(diǎn)位置.圖6(a)中距離數(shù)據(jù)采樣率設(shè)定為30%，野值噪聲比例設(shè)定為10%，無高斯噪聲;圖6(b)中距離數(shù)據(jù)采樣率設(shè)定為30%，野值噪聲比例設(shè)定為1%，高斯噪聲均值為0，標(biāo)準(zhǔn)差為100.從圖6可見，空心圓和實(shí)心點(diǎn)實(shí)現(xiàn)了較好的對(duì)應(yīng)及吻合，驗(yàn)證了在含噪的部分采樣距離條件下，本文算法2可較準(zhǔn)確地實(shí)現(xiàn)傳感器節(jié)點(diǎn)定位.

Fig. 6　Localization results under the condition of different sampling rates and different noise ratios.圖6　不同采樣率和噪聲比例下的節(jié)點(diǎn)定位結(jié)果圖

5結(jié)論

本文基于WSNs節(jié)點(diǎn)距離矩陣低秩特性，提出了一種基于矩陣補(bǔ)全的節(jié)點(diǎn)定位算法.傳統(tǒng)矩陣補(bǔ)全算法只適用于無噪聲或高斯隨機(jī)噪聲，而WSNs中節(jié)點(diǎn)間的無線通信受多徑效應(yīng)、非視距傳播、硬件故障、惡意攻擊等因素導(dǎo)致測(cè)距往往還包含野值噪聲，其嚴(yán)重影響節(jié)點(diǎn)定位精度.因此本文基于節(jié)點(diǎn)間距離矩陣低秩特性，將部分采樣信息下的距離恢復(fù)問題建模為稀疏野值噪聲情形下的矩陣補(bǔ)全問題，在此基礎(chǔ)上采用交替方向乘子法結(jié)合算子分裂技術(shù)進(jìn)行求解.仿真結(jié)果表明，本文算法只需進(jìn)行少量節(jié)點(diǎn)測(cè)距即可實(shí)現(xiàn)精準(zhǔn)的定位，且在無噪聲條件下、高斯噪聲條件下、野值噪聲條件下和高斯野值混合噪聲條件下均能獲得較高的定位精度.此外，算法還可較為準(zhǔn)確地預(yù)測(cè)野值噪聲所在位置，從而為WSNs節(jié)點(diǎn)故障診斷提供依據(jù).

參考文獻(xiàn)

[1]Akyildiz I F, Su Weilian, Sankarasubramaniam Y, et al. A survey on sensor networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114

[2]Han Guangjie, Xu Huihui, Duong T Q, et al. Localization algorithms of wireless sensor networks: A survey[J]. Telecommunication Systems, 2013, 52(4): 2419-2436

[3]Wang Yun, Wang Xiaodong, Wang Demin, et al. Range-free localization using expected hop progress in wireless sensor networks[J]. IEEE Trans on Parallel and Distributed Systems, 2009, 20(10): 1540-1552

[4]Lee J, Choi B, Kim E. Novel range-free localization based on multidimensional support vector regression trained in the primal space[J]. IEEE Trans on Neural Networks and Learning Systems, 2013, 24(7): 1099-1113

[5]So M, Ye Yinyu. Theory of semi-definite programming for sensor network localization[J]. Mathematical Programming, 2007, 109(23): 367-384

[6]Shamsi D, Taheri N, Zhu Zhisu, et al. Conditions for Correct Sensor Network Localization Using SDP Relaxation[M]. Berlin: Springer, 2013

[7]Shang Yi, Zhang Ying, Ruml W, et al. Localization from mere connectivity[C]Proc of the ACM Int Symp on Mobile Ad Hoc Networking and Computing (MobiHoc). New York: ACM, 2003: 201-212

[8]Sun Xiaoling, Chen Tao, Li Weiqing, et al. Performance research of improved MDS-MAP algorithm in wireless sensor networks localization[C]Proc of the IEEE Int Conf on Computer Science and Electronics Engineering. Piscataway, NJ: IEEE, 2012: 587-590

[9]Feng Chen, Valaee S, Au W S A, et al. Localization of wireless sensors via nuclear norm for rank minimization[C]Proc of the 53rd IEEE Global Telecommunications (GLOBECOM’10). Piscataway, NJ: IEEE, 2010: 1-5

[10]Yang Zhen, Wu Chenshu, Liu Yunhao, et al. Detecting outlier measurements based on graph rigidity for wireless sensor network localization[J]. IEEE Trans on Vehicular Technology, 2013, 62(1): 374-383

[11]Xiao Qingjun, Bu Kai, Wang Zhijun, et al. Robust localization against outliers in wireless sensor networks[J]. ACM Trans on Sensor Networks, 2013, 9(2): 24:1-26

[12]Yang Zhen, Jian Lirong, Wu Chenshu, et al. Beyond triangle inequality: Sifting noisy and outlier distance measurements for localization[J]. ACM Trans on Sensor Networks, 2013, 9(2): 1-20

[13]Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[J]. Foundations and Trends in Machine Learning, 2011, 3(1): 1-122

[14]Combettes P L, Wajs V R. Signal recovery by proximal forward-backward splitting[J]. Multiscale Modeling and Simulation, 2005, 4(4): 1168-1200

[15]Gu Jingjing, Chen Songcan, Zhuang Yi. Localization in wireless sensor network using locality preserving canonical correlation analysis[J]. Journal of Software, 2010, 21(11): 2883-2891 (in Chinese)(顧晶晶, 陳松燦, 莊毅. 用局部保持典型相關(guān)分析定位無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)[J]. 軟件學(xué)報(bào), 2010, 21(11): 2883-2891)

[16]Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9(6): 717-772

[17]Cai J F, Candès E J, Shen Zuowei. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20(4): 1956-1982

[18]Keshavan R H, Montanari A, Oh S. Matrix completion from noisy entries[J]. Journal of Machine Learning Research, 2010, 11(3): 2057-2078

[19]Ma Shiqian, Goldfarb D, Chen Lifeng. Fixed point and Bregman iterative methods for matrix rank minimization[J]. Mathematical Programming, 2011, 128(12): 321-353

[20]Keshavan R H, Montanari A, Oh S. Low-rank matrix completion with noisy observations: A quantitative comparison[C]Proc of the 47th IEEE Annual Allerton Conf on Communication, Control, and Computing. Piscataway, NJ: IEEE, 2009: 1216-1222

[21]Boyd S P, Vandenberghe L. Convex Optimization[M]. Cambridge, UK: Cambridge University Press, 2004

[22]Bruckstein A M, Donoho D L, Elad M. From sparse solutions of systems of equations to sparse modeling of signals and images[J]. SIAM Review, 2009, 51(1): 34-81

[23]Donoho D L. Compressed sensing[J]. IEEE Trans on Information Theory, 2006, 52(4): 1289-1306

[24]Wang Shusen, Zhang Zhihua. Colorization by matrix completion[C]Proc of the 26th AAAI Conf on Artificial Intelligence. Menlo Park, CA: AAAI, 2012: 1-7

[25]Li Kun, Dai Qionghai, Xu Wenli, et al. Three-dimensional motion estimation via matrix completion[J]. IEEE Trans on Systems, Man, and Cybernetics, Part B: Cybernetics, 2012, 42(2): 539-552

[26]Cheng Jie, Ye Qiang, Jiang Hongbo, et al. STCDG: An efficient data gathering algorithm based on matrix completion for wireless sensor networks[J]. IEEE Trans on Wireless Communications, 2013, 12(2): 850-861

[27]Cabral R S, Torre F D L, Costeira J P, et al. Matrix completion for multi-label image classification[C]Proc of the 25th Annual Conf on Neural Information Processing Systems (NIPS). Cambridge, MA: MIT Press, 2011: 190-198

[28]Ji Hui, Liu Chaoqiang, Shen Zuowei, et al. Robust video denoising using low rank matrix completion[C]Proc of the 23rd IEEE Conf on Computer Vision and Pattern Recognition (CVPR). Piscataway, NJ: IEEE, 2010: 1797-1798

[29]Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM Review, 2010, 52(3): 471-501

[30]Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J]. Pacific Journal of Optimization, 2010, 6(1): 615-640

[31]Lin Zhouchen, Chen Minming, Ma Yi, et al. The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices[EBOL]. (2010-09-26) [2014-09-27]. http:arxiv.orgpdf1009.5055

[32]Larsen R M. PROPACK—Software for large and sparse SVD calculations[CPOL]. (2010-09-26) [2014-09-27]. http:sun.stanford.edu～rmunkPROPACK

Xiao Fu, born in 1980. PhD. Professor and PhD supervisor of Nanjing University of Posts and Telecommunications. His main research interests include wireless sensor networks (WSNs).

Sha Chaoheng, born in 1990. Master candidate of Nanjing University of Posts and Telecommunications. His main research interests include wireless sensor networks (WSNs).

Chen Lei, born in 1975. PhD. Associate professor of Nanjing University of Posts and Telecommunications. His main research interests include machine learning.

Sun Lijuan, born in 1963. PhD. Professor and PhD supervisor of Nanjing University of Posts and Telecommunications. Her main research interests include wireless sensor networks (WSNs).

Wang Ruchuan, born in 1943. Professor and PhD supervisor of Nanjing University of Posts and Telecommunications. His main research interests include wireless sensor networks (WSNs).

中圖法分類號(hào)TP391

基金項(xiàng)目：國(guó)家自然科學(xué)基金項(xiàng)目(61373137,61373017,61171053,61373139);江蘇省高校自然科學(xué)研究計(jì)劃重大項(xiàng)目(14KJA520002);江蘇省“六大人才高峰”基金項(xiàng)目(2013-DZXX-014);江蘇省“青藍(lán)工程”項(xiàng)目;江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程項(xiàng)目-信息與通信工程

收稿日期：2014-10-08；修回日期：2015-02-28

This work was supported by the National Natural Science Foundation of China (61373137,61373017,61171053,61373139), the Major Program of Jiangsu Higher Education Institutions (14KJA520002), the Six Industries Talent Peaks Plan of Jiangsu (2013-DZXX-014), the Jiangsu Qinglan Project, and a Project Funded by Priority Academic Program Development of Jiangsu Higher Education Institutions.