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

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

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

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

(xiaof@njupt.edu.cn)

?

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

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

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

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

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

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

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

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

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

1相關(guān)工作

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

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

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

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

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

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

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

以及對角陣Σ=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，則τ對應(yīng)的矩陣收縮算子定義為

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

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

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

(2)

證明. 略，詳見文獻[22].

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

(3)

證明. 略，詳見文獻[17].

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

(4)

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

(5)

證明. 略，詳見文獻[14].

2.2L1NRMC算法

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

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

標準的矩陣補全問題通常描述為

(6)

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

(7)

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

(8)

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

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

(9)

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

(10)

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

(11)

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

(12)

(13)

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

(14)

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

(15)

即：

(16)

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

(17)

即：

(18)

進一步，由定理2可得：

(19)

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

(20)

(21)

進一步由定理1可得：

(22)

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

算法1. Exact-L1NRMC算法.

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

輸出：目標矩陣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;

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

算法2. InExact-L1NRMC算法.

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

輸出：目標矩陣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é)省存儲空間，同時還能使變量X保持好的低秩性，而且算法的每一次迭代執(zhí)行過程中只涉及一個SVD分解，這些特性確保了InExact-L1NRMC算法具有較高的時間和空間效率.

3基于矩陣補全的節(jié)點定位算法

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

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

(23)

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

事實上，矩陣補全理論適用的前提為目標矩陣為低秩或近似低秩.矩陣的秩為矩陣所包含的極大線性無關(guān)列向量或行向量的數(shù)目，低秩矩陣對應(yīng)的秩遠小于矩陣維度，即具有較高的冗余性，因此可以通過部分元素恢復(fù)出整個矩陣.為驗證無線傳感網(wǎng)節(jié)點間平方歐氏距離矩陣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個節(jié)點，如果記任意節(jié)點xi與xj之間的平方歐氏距離為Di j，則所得平方歐氏距離矩陣D的秩不超過d+2.

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

(24)

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

(25)

其中diag(·)表示取矩陣主對角線元素的對應(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é)點坐標一般為2維或者3維向量，根據(jù)定理4易知平方歐氏距離矩陣的秩一般不超過5.由秩的定義可知，評價矩陣低秩性好壞的依據(jù)是矩陣秩和矩陣維度的比值，該比值越小其低秩性越好.由于平方歐氏距離矩陣的秩不超過d+2，因此節(jié)點數(shù)量越多，則平方歐氏矩陣的維度越大，低秩性將越好，其冗余性也就越高，從而其補全性能也越好.此外，通過采用算法2，我們不僅可以精確補全節(jié)點間距離信息，而且可以顯式解析出稀疏野值噪聲矩陣，進而根據(jù)該矩陣精確定位出產(chǎn)生異常測距信息的節(jié)點對，從而為WSNs的節(jié)點故障診斷提供依據(jù).

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

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

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

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

① 基于算法2計算平方距離矩陣D：

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

② 計算雙中心化相似矩陣G：

③ 對矩陣G進行SVD分解：

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

④ 計算相對坐標矩陣：

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

⑤ 計算坐標變換矩陣：

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

⑥ 計算并輸出所有節(jié)點坐標：

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

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

4仿真實驗

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

1) 距離矩陣補全誤差

(26)

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

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

(27)

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

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

實驗1. 無噪聲實驗

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

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

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

實驗2. 野值噪聲實驗

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

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

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

定義野值噪聲識別率pr為

(28)

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

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

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

實驗3. 高斯噪聲實驗

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

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

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

實驗4. 混合噪聲實驗

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

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

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

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

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

5結(jié)論

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

參考文獻

[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é)點[J]. 軟件學(xué)報, 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).

中圖法分類號TP391

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

收稿日期：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.