基于低秩矩阵恢复的移动WSN节点轨迹拟合研究*

冯 绪,许小丰,梁 璇,陆亚芳,万江文*

(1.北京航空航天大学仪器科学与光电工程学院,北京 100191;2.通信信息控制和安全技术重点实验室,浙江 嘉兴 314033)



基于低秩矩阵恢复的移动WSN节点轨迹拟合研究*

冯 绪1,许小丰2,梁 璇1,陆亚芳1,万江文1*

(1.北京航空航天大学仪器科学与光电工程学院,北京 100191;2.通信信息控制和安全技术重点实验室,浙江 嘉兴 314033)

对传感节点的位置和轨迹信息进行更新和管理,是传感节点可移动的无线传感器网络系统的主要特征。传感节点的位置和轨迹信息频繁传输会增加网络的能量消耗。为了降低信息的传输量,对信息进行采样,并通过拟合传感器节点的移动轨迹恢复原始轨迹信息;为了进一步提高拟合准确度,将压缩感知理论应用于轨迹拟合中,该算法对非凸最优化问题进行松弛,将矩阵的秩松弛到矩阵的Frobenius范数,并转化为非约束优化问题,然后采用最小二乘法对目标函数进行迭代以求得最优解。仿真实验结果表明,算法能够较好地拟合传感节点的移动轨迹,能显著减少传感节点位置和轨迹信息的发送量。

移动无线传感器网络;轨迹拟合;压缩感知;低秩矩阵恢复

近年来,传感节点可以移动的无线传感器网络WSN(Wireless Sensor Network)引起了人们越来越广泛的关注。很多情况下,移动无线传感器网络能够有效提高网络的可靠性和能量效率[1-3]。在复杂多变的应用环境中,移动无线传感器网络需要结合节点的实际移动情况对数据进行采集和分析,传感节点的位置和轨迹信息频繁传输会增加网络的能量消耗。有必要研究一种能减少传感节点位置和轨迹信息的发送量并且能够准确拟合节点移动轨迹的方法。

对于移动节点的轨迹跟踪,文献[4]采用动态联盟协同任务分配机制,实现了对WSN中多目标的追踪任务;文献[5]将网络分为多个网格,通过计算节点在每个网格出现的概率来预测移动节点的轨迹。文献[4-5]均利用了网络中固定的已知坐标的节点来实现对移动节点的跟踪,其方法不能适用于节点都移动的无线传感器网络。在拟合算法方面,文献[6]采用分段曲线拟合方法对测得的RSSI数据进行拟合,文献[7]采用二阶曲线拟合的方法拟合目标节点轨迹,这两种方法在轨迹发生转折或者数据出现大量丢失时,拟合结果会出现偏差。

低秩矩阵恢复是压缩感知[8-9]在二维矩阵数据的推广,能够根据矩阵的低秩结构将原始矩阵中的信号或数据恢复出来。文献[10]将压缩感知应用于移动网络的定位中,利用网络节点坐标矩阵的低秩特性实现了网络节点的准确定位;文献[11]将低秩矩阵恢复应用于室内定位系统的指纹收集中,有效地减少了指纹的存储量。将基于低秩矩阵恢复的算法应用于对传感器节点的移动轨迹拟合,首先对节点的位置信息进行采样,并建立求解位置信息矩阵的最优化问题模型;简化非凸最优化问题,通过改写矩阵的形式将问题转化为非约束优化问题;迭代最小二乘法求得位置信息矩阵的最优逼近。算法能够在显著减少移动节点位置与轨迹信息发送量的同时,精确地拟合节点轨迹。

1 系统模型

1.1 位置信息矩阵

假设系统中有W个节点,每个节点以相同的时间间隔移动N次,每次移动之后记录节点当前的位置坐标。令X为2W×N阶的节点位置信息矩阵,且X=[E1E2…EW]T,其中Ei为N×2的矩阵,其第1列和第2列数据分别对应第i个节点的x轴和y轴坐标,即

(1)

不难看出,当节点各自以恒定的速度移动时,矩阵X的秩为2,具有低秩性。而在实际场景中,节点并不一定会以恒定的速度移动,但通常可以认为节点在运动的过程中轨迹变化具有一定的规律性于是可以推断矩阵X同样具有低秩性。

1.2 节点移动模型

针对两种不同的移动模型进行研究。

(1)移动节点有目的地进行移动,且在运动的过程中速度和方向呈规律性变化。设定在初始化阶段,节点随机选取自身的运动方向和初始速度,以该方向和速度作为节点移动的基准;在移动过程中,其速度和方向变化规律如下:

(2)

其中,Vi和θi分别表示节点第i次移动时的速度和角度,Vinit为初始化阶段节点随机分配的速度。

(2)节点的移动具有随机性。大多数移动模型基于简单随机的直线运动,而为了描述现实中的曲线运动模式,在随机路径点模型(Random Waypoint Model)的基础上进行改进。在移动过程中,每个节点随机地选择目的坐标,并在一定范围内随机选取起始角度和移动时间沿弧线向目的坐标移动;当节点到达目的地后,在目的地选取随机的一段时间暂停,之后再继续移动。

1.3 位置信息采样

在对移动节点位置信息的采集过程中,节点每次移动之后都将位置信息上传至数据处理中心,由于无线传感器网络能量受限的特性,大量发送节点位置信息会造成网络能量消耗过快,缩短网络寿命。

为了减少能量消耗,对节点的位置信息进行如下采样处理:

(1)对系统设置0到1之间的阈值,即数据采集率;

(2)节点每一次移动之后产生一个0到1之间的随机数;

(3)节点对随机数和数据采集率进行比较,当随机数大于系统设定的阈值时将位置信息上传,否则不发送数据。

通过设置数据采集率,可以控制位置信息数据的发送量。经过采样之后,数据中心得到一个信息不完整的位置信息矩阵,需要对矩阵中缺失的信息进行恢复。

2 节点轨迹拟合

2.1 模型建立

针对式(1)所示的位置信息矩阵,通过位置信息采样,得到采样矩阵A:

(3)

令M为经过采样后实际测量到的节点位置信息矩阵,则有

M=A.*X

(4)

其中,‘.*’表示两个矩阵的点乘。在系统中,矩阵M和A可以通过实际测量得到,矩阵M仅包含了部分的节点位置信息,要解决的问题是如何通过M和A求出完整的位置信息矩阵X。

2.2 奇异值分解

假设矩阵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个奇异值(σ1,σ2,…,σr),而且满足σ1≥σ2≥…≥σr>0。

记U=(u1,u2,…,u2W),V=(v1,v2,…,vN),其中ui和vi分别为奇异值σi的左奇异向量和右奇异向量,则式(5)可以表示为

(6)

(7)

(8)

针对1.2节中的两种移动模型,通过仿真实验验证它们形成的位置信息矩阵具有低秩性。布置40个节点,每个节点移动60次,记录下每次移动的位置坐标,得到80×60的位置信息矩阵。由于位置信息是以矩阵形式呈现的,可以通过主成分分析来分析矩阵性质,其中,奇异值分解是常用的工具。

图1 位置信息矩阵奇异值分布

2.3 位置信息矩阵补全

在式(4)中,采样矩阵A和测量矩阵M为先验信息,位置信息矩阵X为约束条件,对式(8)的求解等同于求解以下优化问题:

(9)

(10)

其中L=UD1/2,R=VD1/2,矩阵U和V均为酉阵。则式(9)转化为:

(11)

在式(11)中,求解矩阵的秩的最小化问题是非凸最优化问题,是NP难的,因此需要对此优化问题的目标函数进行松弛。根据文献[15],当式(11)中的约束条件满足一定条件时,通过求解核范数最小化问题能够精确地恢复原始低秩矩阵,即可以通过求解L和R矩阵的Frobenius范数的和的最小化问题求解式(11):

(12)

(13)

其中λ是折中因子。

采用最小二乘法求解式(13),令f(L,R)为式(13)中的目标函数,即

(14)

首先随机生成L矩阵,通过最小二乘法求得R矩阵,将求得的R矩阵代入式(13)中,采用相同的方法求得L矩阵。重复上述步骤,交替迭代两个矩阵,则L和R矩阵的迭代更新公式为

(15)

3 算法仿真及误差分析

3.1 算法仿真

采用MATLAB对节点轨迹拟合算法进行仿真,并与二阶曲线拟合算法做比较。算法仿真参数如表1所示。

表1 仿真参数

在仿真中,仅仅采集30%的移动节点的位置信息,然后分别对两种移动模型用SRSVD算法和二阶曲线拟合算法对节点的轨迹进行拟合。

图2为网络中第1个节点的实际运动轨迹和两个算法的拟合结果,上图为规律性移动模型的仿真结果,下图为随机性移动模型的仿真结果。由图可知,在减少了70%的数据发送量的情况下,SRSVD算法仍能够很好地对丢失的位置信息进行还原,还原结果与真实值较为接近;二阶曲线拟合法在变化较为平缓的阶段能够对节点移动轨迹很好地拟合,而在节点运动轨迹的转折处或者当数据出现严重丢失时则出现了失真。

图2 轨迹拟合仿真结果

3.2 误差分析

(16)

其中,n为矩阵(1-A)中的非零元素个数,A为采样矩阵。

针对不同的数据采集率,分别使用SRSVD算法和二阶曲线拟合法对位置信息矩阵进行恢复,计算两个算法在不同数据采集率下的拟合误差,结果如图3所示,其中上图为规律性移动模型的仿真结果,下图为随机性移动模型的仿真结果。

从图3可以看出,相比于二阶曲线拟合法,SRSVD算法能够更好地还原位置信息矩阵的细节,在不同的数据采集率下,SRSVD算法的拟合误差都较小,有更高的准确度。

图3 拟合误差

4 结论

基于低秩矩阵恢复的轨迹拟合算法利用了位置信息矩阵的低秩性,通过少量的数据将缺失的节点位置信息恢复出来,达到减少信息发送量、减少网络能耗的目的。节点位置信息以矩阵的形式组织,以采样的方式采集位置信息以减少网络中的通信量;采用SRSVD方法松弛非凸优化问题,可将问题简化为两个矩阵的Frobenius范数之和的最小化问题,并转化为非约束优化问题;采用最小二乘法交替迭代目标函数,求得位置信息矩阵的最优逼近,恢复出缺失的位置信息。仿真实验结果表明,在减少了70%的数据发送量的情况下仍能有效地恢复移动节点的轨迹。

[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无线传感器网络的智能交通系统设计[J]. 传感技术学报,2013(12): - .

[3]蒋凌云,孙力娟,王汝传,等. 移动无线传感网能量时延约束的自适应路由及性能评估[J]. 电子学报,2013,40(12):2495-2500.

[4]文莎,蔡自兴,刘丽珏,等. 无线传感器网络多目标跟踪中协同任务分配[J]. 中南大学学报(自然科学版),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]朱明强,侯建军,刘颖,等. 一种基于卡尔曼数据平滑的分段曲线拟合室内定位算法[J]. 北京交通大学学报(自然科学版),2012,36(5):95-99.

[7]石为人,杨斌,许磊,等. 一种事件驱动型无线传感器网络目标追踪算法的研究[J]. 传感技术学报,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]史加荣,郑秀云,魏宗田,等. 低秩矩阵恢复算法综述[J]. 计算机应用研究,2013,30(6):1601-1605.

[14]彭义刚,索津莉,戴琼海,等. 从压缩传感到低秩矩阵恢复:理论与应用[J]. 自动化学报,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-),男,北京航空航天大学在读硕士研究生,研究方向为无线传感器网络技术,fredfx@163.com;

万江文(1963-),男,北京航空航天大学教授,博士生导师,主要研究方向为传感系统与仪器、传感网络与信息融合、定位与跟踪技术,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

项目来源:国家自然科学基金项目(61371135)

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

10.3969/j.issn.1004-1699.2014.10.018

TP393

:A

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