基于低秩矩陣恢復(fù)的移動WSN節(jié)點(diǎn)軌跡擬合研究*

馮 緒,許小豐,梁 璇,陸亞芳,萬江文*

(1.北京航空航天大學(xué)儀器科學(xué)與光電工程學(xué)院,北京 100191;2.通信信息控制和安全技術(shù)重點(diǎn)實(shí)驗(yàn)室,浙江 嘉興 314033)

?

基于低秩矩陣恢復(fù)的移動WSN節(jié)點(diǎn)軌跡擬合研究*

馮 緒1,許小豐2,梁 璇1,陸亞芳1,萬江文1*

(1.北京航空航天大學(xué)儀器科學(xué)與光電工程學(xué)院,北京 100191;2.通信信息控制和安全技術(shù)重點(diǎn)實(shí)驗(yàn)室,浙江 嘉興 314033)

對傳感節(jié)點(diǎn)的位置和軌跡信息進(jìn)行更新和管理,是傳感節(jié)點(diǎn)可移動的無線傳感器網(wǎng)絡(luò)系統(tǒng)的主要特征。傳感節(jié)點(diǎn)的位置和軌跡信息頻繁傳輸會增加網(wǎng)絡(luò)的能量消耗。為了降低信息的傳輸量,對信息進(jìn)行采樣,并通過擬合傳感器節(jié)點(diǎn)的移動軌跡恢復(fù)原始軌跡信息;為了進(jìn)一步提高擬合準(zhǔn)確度,將壓縮感知理論應(yīng)用于軌跡擬合中,該算法對非凸最優(yōu)化問題進(jìn)行松弛,將矩陣的秩松弛到矩陣的Frobenius范數(shù),并轉(zhuǎn)化為非約束優(yōu)化問題,然后采用最小二乘法對目標(biāo)函數(shù)進(jìn)行迭代以求得最優(yōu)解。仿真實(shí)驗(yàn)結(jié)果表明,算法能夠較好地?cái)M合傳感節(jié)點(diǎn)的移動軌跡,能顯著減少傳感節(jié)點(diǎn)位置和軌跡信息的發(fā)送量。

移動無線傳感器網(wǎng)絡(luò);軌跡擬合;壓縮感知;低秩矩陣恢復(fù)

近年來,傳感節(jié)點(diǎn)可以移動的無線傳感器網(wǎng)絡(luò)WSN(Wireless Sensor Network)引起了人們越來越廣泛的關(guān)注。很多情況下,移動無線傳感器網(wǎng)絡(luò)能夠有效提高網(wǎng)絡(luò)的可靠性和能量效率[1-3]。在復(fù)雜多變的應(yīng)用環(huán)境中,移動無線傳感器網(wǎng)絡(luò)需要結(jié)合節(jié)點(diǎn)的實(shí)際移動情況對數(shù)據(jù)進(jìn)行采集和分析,傳感節(jié)點(diǎn)的位置和軌跡信息頻繁傳輸會增加網(wǎng)絡(luò)的能量消耗。有必要研究一種能減少傳感節(jié)點(diǎn)位置和軌跡信息的發(fā)送量并且能夠準(zhǔn)確擬合節(jié)點(diǎn)移動軌跡的方法。

對于移動節(jié)點(diǎn)的軌跡跟蹤,文獻(xiàn)[4]采用動態(tài)聯(lián)盟協(xié)同任務(wù)分配機(jī)制,實(shí)現(xiàn)了對WSN中多目標(biāo)的追蹤任務(wù);文獻(xiàn)[5]將網(wǎng)絡(luò)分為多個(gè)網(wǎng)格,通過計(jì)算節(jié)點(diǎn)在每個(gè)網(wǎng)格出現(xiàn)的概率來預(yù)測移動節(jié)點(diǎn)的軌跡。文獻(xiàn)[4-5]均利用了網(wǎng)絡(luò)中固定的已知坐標(biāo)的節(jié)點(diǎn)來實(shí)現(xiàn)對移動節(jié)點(diǎn)的跟蹤,其方法不能適用于節(jié)點(diǎn)都移動的無線傳感器網(wǎng)絡(luò)。在擬合算法方面,文獻(xiàn)[6]采用分段曲線擬合方法對測得的RSSI數(shù)據(jù)進(jìn)行擬合,文獻(xiàn)[7]采用二階曲線擬合的方法擬合目標(biāo)節(jié)點(diǎn)軌跡,這兩種方法在軌跡發(fā)生轉(zhuǎn)折或者數(shù)據(jù)出現(xiàn)大量丟失時(shí),擬合結(jié)果會出現(xiàn)偏差。

低秩矩陣恢復(fù)是壓縮感知[8-9]在二維矩陣數(shù)據(jù)的推廣,能夠根據(jù)矩陣的低秩結(jié)構(gòu)將原始矩陣中的信號或數(shù)據(jù)恢復(fù)出來。文獻(xiàn)[10]將壓縮感知應(yīng)用于移動網(wǎng)絡(luò)的定位中,利用網(wǎng)絡(luò)節(jié)點(diǎn)坐標(biāo)矩陣的低秩特性實(shí)現(xiàn)了網(wǎng)絡(luò)節(jié)點(diǎn)的準(zhǔn)確定位;文獻(xiàn)[11]將低秩矩陣恢復(fù)應(yīng)用于室內(nèi)定位系統(tǒng)的指紋收集中,有效地減少了指紋的存儲量。將基于低秩矩陣恢復(fù)的算法應(yīng)用于對傳感器節(jié)點(diǎn)的移動軌跡擬合,首先對節(jié)點(diǎn)的位置信息進(jìn)行采樣,并建立求解位置信息矩陣的最優(yōu)化問題模型;簡化非凸最優(yōu)化問題,通過改寫矩陣的形式將問題轉(zhuǎn)化為非約束優(yōu)化問題;迭代最小二乘法求得位置信息矩陣的最優(yōu)逼近。算法能夠在顯著減少移動節(jié)點(diǎn)位置與軌跡信息發(fā)送量的同時(shí),精確地?cái)M合節(jié)點(diǎn)軌跡。

1 系統(tǒng)模型

1.1 位置信息矩陣

假設(shè)系統(tǒng)中有W個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)以相同的時(shí)間間隔移動N次,每次移動之后記錄節(jié)點(diǎn)當(dāng)前的位置坐標(biāo)。令X為2W×N階的節(jié)點(diǎn)位置信息矩陣,且X=[E1E2…EW]T,其中Ei為N×2的矩陣,其第1列和第2列數(shù)據(jù)分別對應(yīng)第i個(gè)節(jié)點(diǎn)的x軸和y軸坐標(biāo),即

(1)

不難看出,當(dāng)節(jié)點(diǎn)各自以恒定的速度移動時(shí),矩陣X的秩為2,具有低秩性。而在實(shí)際場景中,節(jié)點(diǎn)并不一定會以恒定的速度移動,但通常可以認(rèn)為節(jié)點(diǎn)在運(yùn)動的過程中軌跡變化具有一定的規(guī)律性于是可以推斷矩陣X同樣具有低秩性。

1.2 節(jié)點(diǎn)移動模型

針對兩種不同的移動模型進(jìn)行研究。

(1)移動節(jié)點(diǎn)有目的地進(jìn)行移動,且在運(yùn)動的過程中速度和方向呈規(guī)律性變化。設(shè)定在初始化階段,節(jié)點(diǎn)隨機(jī)選取自身的運(yùn)動方向和初始速度,以該方向和速度作為節(jié)點(diǎn)移動的基準(zhǔn);在移動過程中,其速度和方向變化規(guī)律如下:

(2)

其中,Vi和θi分別表示節(jié)點(diǎn)第i次移動時(shí)的速度和角度,Vinit為初始化階段節(jié)點(diǎn)隨機(jī)分配的速度。

(2)節(jié)點(diǎn)的移動具有隨機(jī)性。大多數(shù)移動模型基于簡單隨機(jī)的直線運(yùn)動,而為了描述現(xiàn)實(shí)中的曲線運(yùn)動模式,在隨機(jī)路徑點(diǎn)模型(Random Waypoint Model)的基礎(chǔ)上進(jìn)行改進(jìn)。在移動過程中,每個(gè)節(jié)點(diǎn)隨機(jī)地選擇目的坐標(biāo),并在一定范圍內(nèi)隨機(jī)選取起始角度和移動時(shí)間沿弧線向目的坐標(biāo)移動;當(dāng)節(jié)點(diǎn)到達(dá)目的地后,在目的地選取隨機(jī)的一段時(shí)間暫停,之后再繼續(xù)移動。

1.3 位置信息采樣

在對移動節(jié)點(diǎn)位置信息的采集過程中,節(jié)點(diǎn)每次移動之后都將位置信息上傳至數(shù)據(jù)處理中心,由于無線傳感器網(wǎng)絡(luò)能量受限的特性,大量發(fā)送節(jié)點(diǎn)位置信息會造成網(wǎng)絡(luò)能量消耗過快,縮短網(wǎng)絡(luò)壽命。

為了減少能量消耗,對節(jié)點(diǎn)的位置信息進(jìn)行如下采樣處理:

(1)對系統(tǒng)設(shè)置0到1之間的閾值,即數(shù)據(jù)采集率;

(2)節(jié)點(diǎn)每一次移動之后產(chǎn)生一個(gè)0到1之間的隨機(jī)數(shù);

(3)節(jié)點(diǎn)對隨機(jī)數(shù)和數(shù)據(jù)采集率進(jìn)行比較,當(dāng)隨機(jī)數(shù)大于系統(tǒng)設(shè)定的閾值時(shí)將位置信息上傳,否則不發(fā)送數(shù)據(jù)。

通過設(shè)置數(shù)據(jù)采集率,可以控制位置信息數(shù)據(jù)的發(fā)送量。經(jīng)過采樣之后,數(shù)據(jù)中心得到一個(gè)信息不完整的位置信息矩陣,需要對矩陣中缺失的信息進(jìn)行恢復(fù)。

2 節(jié)點(diǎn)軌跡擬合

2.1 模型建立

針對式(1)所示的位置信息矩陣,通過位置信息采樣,得到采樣矩陣A:

(3)

令M為經(jīng)過采樣后實(shí)際測量到的節(jié)點(diǎn)位置信息矩陣,則有

M=A.*X

(4)

其中,‘.*’表示兩個(gè)矩陣的點(diǎn)乘。在系統(tǒng)中,矩陣M和A可以通過實(shí)際測量得到,矩陣M僅包含了部分的節(jié)點(diǎn)位置信息,要解決的問題是如何通過M和A求出完整的位置信息矩陣X。

2.2 奇異值分解

假設(shè)矩陣X的秩為r,即rank(X)=r,其奇異值分解SVD(Singular Value Decomposition)為

(5)

其中,U∈R2W×2W和V∈RN×N均為正交矩陣,有UTU=UUT=I,VTV=VVT=I。Σr為r×r對角陣,其對角線元素為矩陣X的r個(gè)奇異值(σ1,σ2,…,σr),而且滿足σ1≥σ2≥…≥σr>0。

記U=(u1,u2,…,u2W),V=(v1,v2,…,vN),其中ui和vi分別為奇異值σi的左奇異向量和右奇異向量,則式(5)可以表示為

(6)

(7)

(8)

針對1.2節(jié)中的兩種移動模型,通過仿真實(shí)驗(yàn)驗(yàn)證它們形成的位置信息矩陣具有低秩性。布置40個(gè)節(jié)點(diǎn),每個(gè)節(jié)點(diǎn)移動60次,記錄下每次移動的位置坐標(biāo),得到80×60的位置信息矩陣。由于位置信息是以矩陣形式呈現(xiàn)的,可以通過主成分分析來分析矩陣性質(zhì),其中,奇異值分解是常用的工具。

圖1 位置信息矩陣奇異值分布

2.3 位置信息矩陣補(bǔ)全

在式(4)中,采樣矩陣A和測量矩陣M為先驗(yàn)信息,位置信息矩陣X為約束條件,對式(8)的求解等同于求解以下優(yōu)化問題:

(9)

(10)

其中L=UD1/2,R=VD1/2,矩陣U和V均為酉陣。則式(9)轉(zhuǎn)化為:

(11)

在式(11)中,求解矩陣的秩的最小化問題是非凸最優(yōu)化問題,是NP難的,因此需要對此優(yōu)化問題的目標(biāo)函數(shù)進(jìn)行松弛。根據(jù)文獻(xiàn)[15],當(dāng)式(11)中的約束條件滿足一定條件時(shí),通過求解核范數(shù)最小化問題能夠精確地恢復(fù)原始低秩矩陣,即可以通過求解L和R矩陣的Frobenius范數(shù)的和的最小化問題求解式(11):

(12)

(13)

其中λ是折中因子。

采用最小二乘法求解式(13),令f(L,R)為式(13)中的目標(biāo)函數(shù),即

(14)

首先隨機(jī)生成L矩陣,通過最小二乘法求得R矩陣,將求得的R矩陣代入式(13)中,采用相同的方法求得L矩陣。重復(fù)上述步驟,交替迭代兩個(gè)矩陣,則L和R矩陣的迭代更新公式為

(15)

3 算法仿真及誤差分析

3.1 算法仿真

采用MATLAB對節(jié)點(diǎn)軌跡擬合算法進(jìn)行仿真,并與二階曲線擬合算法做比較。算法仿真參數(shù)如表1所示。

表1 仿真參數(shù)

在仿真中,僅僅采集30%的移動節(jié)點(diǎn)的位置信息,然后分別對兩種移動模型用SRSVD算法和二階曲線擬合算法對節(jié)點(diǎn)的軌跡進(jìn)行擬合。

圖2為網(wǎng)絡(luò)中第1個(gè)節(jié)點(diǎn)的實(shí)際運(yùn)動軌跡和兩個(gè)算法的擬合結(jié)果,上圖為規(guī)律性移動模型的仿真結(jié)果,下圖為隨機(jī)性移動模型的仿真結(jié)果。由圖可知,在減少了70%的數(shù)據(jù)發(fā)送量的情況下,SRSVD算法仍能夠很好地對丟失的位置信息進(jìn)行還原,還原結(jié)果與真實(shí)值較為接近;二階曲線擬合法在變化較為平緩的階段能夠?qū)?jié)點(diǎn)移動軌跡很好地?cái)M合,而在節(jié)點(diǎn)運(yùn)動軌跡的轉(zhuǎn)折處或者當(dāng)數(shù)據(jù)出現(xiàn)嚴(yán)重丟失時(shí)則出現(xiàn)了失真。

圖2 軌跡擬合仿真結(jié)果

3.2 誤差分析

(16)

其中,n為矩陣(1-A)中的非零元素個(gè)數(shù),A為采樣矩陣。

針對不同的數(shù)據(jù)采集率,分別使用SRSVD算法和二階曲線擬合法對位置信息矩陣進(jìn)行恢復(fù),計(jì)算兩個(gè)算法在不同數(shù)據(jù)采集率下的擬合誤差,結(jié)果如圖3所示,其中上圖為規(guī)律性移動模型的仿真結(jié)果,下圖為隨機(jī)性移動模型的仿真結(jié)果。

從圖3可以看出,相比于二階曲線擬合法,SRSVD算法能夠更好地還原位置信息矩陣的細(xì)節(jié),在不同的數(shù)據(jù)采集率下,SRSVD算法的擬合誤差都較小,有更高的準(zhǔn)確度。

圖3 擬合誤差

4 結(jié)論

基于低秩矩陣恢復(fù)的軌跡擬合算法利用了位置信息矩陣的低秩性,通過少量的數(shù)據(jù)將缺失的節(jié)點(diǎn)位置信息恢復(fù)出來,達(dá)到減少信息發(fā)送量、減少網(wǎng)絡(luò)能耗的目的。節(jié)點(diǎn)位置信息以矩陣的形式組織,以采樣的方式采集位置信息以減少網(wǎng)絡(luò)中的通信量;采用SRSVD方法松弛非凸優(yōu)化問題,可將問題簡化為兩個(gè)矩陣的Frobenius范數(shù)之和的最小化問題,并轉(zhuǎn)化為非約束優(yōu)化問題;采用最小二乘法交替迭代目標(biāo)函數(shù),求得位置信息矩陣的最優(yōu)逼近,恢復(fù)出缺失的位置信息。仿真實(shí)驗(yàn)結(jié)果表明,在減少了70%的數(shù)據(jù)發(fā)送量的情況下仍能有效地恢復(fù)移動節(jié)點(diǎn)的軌跡。

[1] Yun Y S,Xia Y. Maximizing the Lifetime of Wireless Sensor Networks with Mobile Sink in Delay-Tolerant Applications[J]. IEEE Transactions on Mobile Computing,2010,9(9):1308-1318.

[2]劉文軍,樊建席,李春勝,等. 基于ZigBee無線傳感器網(wǎng)絡(luò)的智能交通系統(tǒng)設(shè)計(jì)[J]. 傳感技術(shù)學(xué)報(bào),2013(12): - .

[3]蔣凌云,孫力娟,王汝傳,等. 移動無線傳感網(wǎng)能量時(shí)延約束的自適應(yīng)路由及性能評估[J]. 電子學(xué)報(bào),2013,40(12):2495-2500.

[4]文莎,蔡自興,劉麗玨,等. 無線傳感器網(wǎng)絡(luò)多目標(biāo)跟蹤中協(xié)同任務(wù)分配[J]. 中南大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,43(8):3032.

[5]Chen Y L,Lin Y C,Sun T C. A Prediction Scheme for Object Tracking in Grid Wireless Sensor Networks[C]//Innovative Mobile and Internet Services in Ubiquitous Computing(IMIS),2013 Seventh International Conference on. IEEE,2013:360-364.

[6]朱明強(qiáng),侯建軍,劉穎,等. 一種基于卡爾曼數(shù)據(jù)平滑的分段曲線擬合室內(nèi)定位算法[J]. 北京交通大學(xué)學(xué)報(bào)(自然科學(xué)版),2012,36(5):95-99.

[7]石為人,楊斌,許磊,等. 一種事件驅(qū)動型無線傳感器網(wǎng)絡(luò)目標(biāo)追蹤算法的研究[J]. 傳感技術(shù)學(xué)報(bào),2010,23(1):144-148.

[8]Candès E J,Romberg J,Tao T. Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J]. IEEE Transactions on Information Theory,2006,52(2):489-509.

[9]Donoho D L. Compressed Sensing[J]. IEEE Transactions on Information Theory,2006,52(4):1289-1306.

[10]Rallapalli S,Qiu L,Zhang Y,et al. Exploiting Temporal Stability and Low-Rank Structure for Localization in Mobile Networks[C]//Proceedings of the Sixteenth Annual International Conference on Mobile Computing and Networking. ACM,2010:161-172.

[11]Zhang Y,Zhu Y,Lu M,et al. Using Compressive Sensing to Reduce Fingerprint Collection for Indoor Localization[C]//Wireless Communications and Networking Conference(WCNC),2013 IEEE. IEEE,2013:4540-4545.

[12]Zhang Y,Roughan M,Willinger W,et al. Spatio-Temporal Compressive Sensing and Internet Traffic Matrices[C]//ACM SIGCOMM Computer Communication Review. ACM,2009,39(4):267-278.

[13]史加榮,鄭秀云,魏宗田,等. 低秩矩陣恢復(fù)算法綜述[J]. 計(jì)算機(jī)應(yīng)用研究,2013,30(6):1601-1605.

[14]彭義剛,索津莉,戴瓊海,等. 從壓縮傳感到低秩矩陣恢復(fù):理論與應(yīng)用[J]. 自動化學(xué)報(bào),2013,39(7):981-994.

[15]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.

馮緒(1989-),男,北京航空航天大學(xué)在讀碩士研究生,研究方向?yàn)闊o線傳感器網(wǎng)絡(luò)技術(shù),fredfx@163.com;

萬江文(1963-),男,北京航空航天大學(xué)教授,博士生導(dǎo)師,主要研究方向?yàn)閭鞲邢到y(tǒng)與儀器、傳感網(wǎng)絡(luò)與信息融合、定位與跟蹤技術(shù),jwwan@buaa.edu.cn。

ResearchonPathFittingofMobileNodesinMobileWSNBasedonLow-RankMatrixRecovery*

FENGXu1,XUXiaofeng2,LIANGXuan1,LUYafang1,WANJiangwen1*

(1.School of Instrumentation Science and Opto-Electronics Engineering,Beihang University,Beijing 100191,China; 2.Science and Technology on Communication Information Security Control Laboratory,Jiaxing Zhejiang 314033,China)

Updating and managing the position and path information of mobile sensor nodes,which is one of the main features of mobile wireless sensor network(MWSN)system. Frequently transferring the path information will increase the energy consumption of MWSN. In order to reduce the transmission of information,we apply the algorithm based on low-rank matrix recovery on path fitting to recover path information after sampling process. The algorithm relaxes the rank of matrix by replacing it with the Frobenius norm to simplify the non-convex optimization problem,turns the problem into a non-constrained problem,and uses an alternating least squares procedure to find the solution. Experiment results show that the algorithm achieves good accuracy on path fitting and reduces the transmission of path information in the meanwhile.

mobile wireless sensor network;path fitting;compressive sensing;low-rank matrix recovery

項(xiàng)目來源:國家自然科學(xué)基金項(xiàng)目(61371135)

2014-06-19修改日期:2014-09-03

10.3969/j.issn.1004-1699.2014.10.018

TP393

:A

:1004-1699(2014)10-1401-05