基于半监督拉普拉斯映射的移动定位算法

,,

(南京航空航天大学 计算机科学与技术学院,南京 211106)

0 概述

微机电系统、数字电子技术和无线通信产业的逐渐成熟促进了无线传感器网络(Wireless Sensor Network,WSN)的长足发展。WSN是通过部署大量的传感器节点至目标区域,形成一个分布式传感器网络,自主地感知外部的世界。WSN广泛地应用于智能交通、环境监控、军事、医疗卫生等多个领域,其中定位技术是无线传感器网络中的研究难点和关键技术之一[1]。

典型的无线传感器定位方式主要分为基于测距和非测距的方式,其中基于测距的定位技术在障碍物少、干扰少,较理想的环境中具有较好的定位精度,应用较为广泛,主要分为RSSI[2]、TOA[3]、TDOA[4]和AOA[5]等。文献[6]提出了一种基于RSSI测距的二维对数分布式搜索算法。基于非测距的定位技术无需测量节点间的绝对距离或方位,对硬件依赖低,并且粗精度能满足实际需求,主要分为DV-Hop[7]、凸规划[8]、MDS-MAP[9]等。文献[10]选举共线度较低的节点作为锚节点,提出了一种分布式协作的DV-Hop算法。

以上这些传统的定位技术稳定性差、功耗高、需要外部设备的支持或定位精度易受外界环境的影响。近些年,随着机器学习的发展,学术界提出了众多基于机器学习的节点定位算法。该类算法首先训练出信号空间和物理空间的映射模型,然后基于该映射模型对未知节点进行定位[11-12]。基于机器学习的定位算法,定位稳定,且定位精度较高。

本文提出的基于拉普拉斯映射的正则化算法即是机器学习中降维和流形学习的一种。在考虑非信标节点的不足和网络拓扑结构不断更新的基础上,将定位问题放在半监督框架中进行研究。首先在半监督学习中提出流形正则化框架,基于局部光滑性假设对定位在标记样本上的损失函数进行正则化,防止在建模的过程中,特征值过多,建模效率低。然后在建模的过程中,分析节点的分布符合流形的特点,挖掘网络的局部空间特性。最后引入高斯核,构建Gram矩阵,更好地反映信号空间的非线性拓扑结构。

1 问题描述

考虑一个二维的节点定位问题,人手持移动设备在一个L×L大小的室内进行移动,室内有n个信标节点布置在预定的位置上,可以周期性地发送和接收信号。在某个时刻ti,移动设备接收到一组向量si=[si1,si2,…,sin]∈n。人手持移动设备按照预定的路线行走结束后,得到一组m×n的信号量矩阵S=T。这里m个n维的向量包括已知节点和未知节点接收的信号向量。

如图1所示,在一个16 m×16 m的室内,布置8个信标节点。假设人手持cc2530传感器,按照下面的轨迹进行移动。移动设备将经过A、B、C、D、E、F等点,相应的一个6×8的信号向量矩阵如表1所示。

图1 移动设备的运动轨迹示意图

时刻AP1AP2AP3AP4AP5AP6AP7AP8tA-45-36-75-88-92-127-163-192tB-162-129-63-69-73-173-42-123tC-128-89-158-58-51-44-143-48tD-54-24-74-73-79-119-152-183tE-158-80-103-46-39-70-67-42tF-61-26-89-42-51-87-159-143

依据无线传感器网络流形的局部拓扑结构,信号强度和物理坐标之间存在着潜在的相关联系,一般具有以下3个特性[13]:

1)如果信号空间中不同时刻的信号向量是相似的,则物理空间中2个移动节点的物理坐标是相近的。例如表1中tA和tD时刻2行信号向量是相似的,由图1可知实际物理位置也是相近的。

2)如果信号空间中2个信标节点接收的信号向量是相似的,则物理空间中2个信标节点部署的位置是相近的。例如在图1中AP4和AP5节点是相近的,其相应的信号向量也是相似的。

3)如果信号强度值接近于0,则该移动节点与相应的信标节点位置较近。例如图1中,节点在tD时刻离AP2节点较为接近,可以发现其信号强度值接近于0。

2 相关工作

2.1 流形结构上的正则化半监督学习

现实世界中对于机器学习问题,标记样本的数量是有限的,而未标记的样本数据是巨大的,样本之间存在着潜在的流形结构。假设所有的数据都在高维表示空间的一个低维嵌入子流形上,那么算法可以利用大量的未标记样本学习出数据的内在结构或规律,并在此基础上利用少量的标记样本进行分类或回归。流形学习是通过学习出隐含在数据中的流形结构和相应的低维坐标来实现对高维数据的非线性约简。此时未标记样本能用来提高学习性能,这使得流形上机器学习成为半监督学习的一种研究方法。文献[14]提出了使用一种新的流形正则化形式,结合有监督的数据和无监督数据,挖掘数据分布的几何形状。

在再生核希尔伯特空间HK中,假设存在一个Mercer核K:X×X→R,X→R函数必然存在一个相应的‖‖K。现在给出l个标记和u个未标记的数据(xi,yi),i=1,2,…,l,…,l+u。标准的框架如式(1)所示。

(1)

其中,函数V是平方损失函数,在正则化最小二乘法中函数V可表示为(yi-f(xi))2,在支持向量机中可表示为max[0,1-yif(xi)],γ是控制函数在再生核希尔伯特空间中的过拟合参数。

基于正则化的最小二乘法半监督学习中,最优的f可表示为:

(2)

将式(2)代入式(1)中,可化简为:

(3)

其中,K是一个(l+u)×(l+u)的Gram矩阵,Kij=K(xi,xj),Y是一个标记的向量,Y=[y1,y2,…,yl+u]T。

2.2 拉普拉斯映射算法

流形结构上的降维算法是近年来的热门研究领域之一,大量专家学者投入其中研究出众多的降维算法。降维算法主要分为线性降维算法和非线性降维算法。线性降维算法包括PCA、LDA、LPP等;非线性降维算法基于核,包括ISOMAP、LLE、LE等。拉普拉斯映射算法是典型的局部降维算法,在降维的过程中保证数据分布的局部结构,降维后数据的整体分布发生变化,但计算复杂度较低。文献[15]将拉普拉斯映射引入到无线传感器网络节点定位过程中。

本文提出的基于拉普拉斯映射的正则化定位算法主要分为2个阶段:训练阶段和定位阶段。在训练阶段中,通过拉普拉斯正则化的最小二乘法对信号空间和物理空间进行拟合,考虑空间中的局部结构特性,训练出信号空间和物理空间中的映射模型。在定位阶段,通过映射模型对未知节点进行位置估计。

假设现在有N个数据样本,其相邻的样本间构成了一个拉普拉斯图,嵌入映射就通过求解拉普拉斯映射的特征向量得到,算法过程如下:

1)构建邻域图

采用k-近邻算法,如果节点i是节点j的k个近邻之一,或者节点j是节点i的k个近邻之一,则认为节点i和j是相连的。遍历完所有节点,构造好邻域图。

2)确定邻域图的边权重

确定点和点之间的权值大小,可以选择热核函数来确定,如果节点i和节点j相连,那么它们的权重可设定为:

(4)

否则,Wij=0。

3)拉普拉斯特征映射

在d维空间中用各个样本的近邻重构该样本数据,使任意Xi的近邻在降维后仍然尽可能靠近Xi,即所有点与其近邻的距离和最小:

(5)

3 LP-LapRLS算法

在无线传感器网络定位机制中,基于流形结构的机器学习逐渐成为热点之一。节点的定位过程一般分为训练阶段和定位阶段,训练阶段主要对少量的已知节点和大量的未知节点进行拉普拉斯正则化分析,训练出物理坐标到信号空间的映射。定位阶段,通过映射对移动的目标进行实时的定位。

在原始的高维空间中,包含冗余信息以及噪音信息,在实际的传感器定位过程中造成了误差,降低了定位准确率。本文引入拉普拉斯特征映射,揭示了数据的局部特性,反映了决策函数的平滑性。LP-LapRLS算法主要最优化下列等式:

(6)

考虑流形的结构,对任意的f(xi)有:

(7)

其中,αj是全局的映射函数,K(xi,xj)是半正定核函数。

在复杂的传感器网络中,由于路径损失、障碍物、环境等外部因素的影响,导致采集的数据模型非线性且含有噪声。一般采用核函数的方法构建模型,使得原始空间中的非线性问题转变为线性问题进行研究[16]。相比线性核函数、多项式核函数和感知器核函数等,高斯核函数能够更好地拟合信号空间非线性的结构特性。因此在定位过程中,一般选择高斯核函数反映信号强度的拓扑结构,如式(8)所示:

(8)

因此形成了一个凸可微的目标函数:

(9)

通过对上式中的α求偏导,得到如下最优解:

(10)

通过不断地调节参数rA和rI,可以达到更好的定位效果。经过大量的实验验证,当参数γA取值在0.03～0.05范围之间,定位误差在26%左右;参数γI取值在0.89～1.03范围之间,定位误差在25%左右,定位精度达到85%。

在训练阶段,通过式(10)求得信号空间和物理空间的映射模型α。在定位阶段,移动节点接收到信号向量si。用模型α对其进行线性变化,求得相邻节点坐标集合Loc=α×si。通过欧式距离的计算,选出k个最相近的节点,通过质心算法求得未知节点的坐标。

LP-LapRLS算法描述如下:

步骤1采集l个信标节点和u个未知节点,通过k-近邻的方法构建邻域图,计算边的权重wij。

步骤2计算拉普拉斯矩阵L=D-W。

步骤3选择一个合适的核函数K(xi,yj),计算Gram矩阵。

步骤4选择一个合适的参数γA和γI。

步骤5通过式(10)计算映射矩阵α。

步骤6在定位阶段,通过映射矩阵α求得未知节点的相邻节点坐标的集合Loc,通过欧式距离的计算选出k个相邻的节点,利用质心算法求得未知节点的坐标。

4 仿真及结果分析

4.1 实验描述

为了验证算法的有效性,采用一组由香港科技大学提供的数据集对算法进行验证。实验由Cross-bow MICA2 传感器节点构成,其中包括8个AP节点,分别部署在该校大楼的不同位置。每个传感器节点接收到的信号强度为8维的向量。所有数据均由IBM笔记本电脑链接一个外部的无线USB网络适配器采集得到。

香港科技大学提供的数据集包括2组数据,一组数据为移动节点在不同时刻不同位置采集到的8个AP节点的信号强度值,另一组数据为移动节点对应的物理坐标值,一共均匀采集了2 999个样本数据,将其中一部分数据用作训练数据,学习定位模型,其余用作测试数据,计算定位精度。

图2是从2 999个样本中随机选取出1 500个样本的随机分布效果图。香港科技大学的数据集信标节点的位置是固定的,未知节点的位置是随机的。

图2 节点分布效果图

为了进行对比实验,同时运行了基于相同高斯核函数的LE-LPCCA算法[17]和半监督共定位算法Co-Localization[18],半监督共定位算法采用SVD分解和半监督流形学习对未知节点同时进行定位和修正。实验环境为Matlab2013a,为了验证算法的有效性,在数据集中各运行50次,取平均值作为评价的标准。

4.2 实验结果分析

图3是训练样本集比例分别取20%～80%时,LP-LapRLS算法和LE-LPCCA算法、Co-Localization算法定位精度的对比图。

图3 不同的训练集比例下的误差对比

由图3可以看出,LP-LapRLS算法相比于其他2种算法具有较大的优势,样本训练集达到60%时,已经具有较稳定的定位效果,定位精度在84%左右。随着样本训练集的增加,定位结果更加稳定。LE-LPCCA算法在训练样本集达到60%时,定位精度可达82%以上,定位精度较高。但是训练样本集较低时,相比Co-Localization算法和LP-LapRLS算法,定位精度较差,因为LE-LPCCA算法并没有充分地利用非信标节点对定位模型进行修正。Co-Localization采取了双重定位进行目标位置的确定,当已知的信标节点较少时,具有较大的优势,相比其他2种算法,提高了3～5个百分点。对于Co-Localization算法,当训练样本集数量较大,定位精度提升减缓。主要由于定位过程中奇异值分解和流学习的双重定位,不能充分地反映节点的拓扑结构,影响了定位的准确度。

4.3 参数对定位的影响

在LP-LapRLS算法中,参数γA和γI的选择对传感器节点的定位精确度有着重要的影响。文献[14]通过大量的仿真实验论证了当γA=0.031 25和γI=1时,拉普拉斯映射更加符合无线传感器网络的流形结构。

在图4和图5中,训练样本集比例均为60%,信标节点样本的数量l为500,非信标节点的样本数量u为1 000。在图4中,假设γI为1,设置不同的值,观察参数γA对定位误差的影响。同时,在图5中设置γA=0.031 25,观察参数γI对定位误差的影响。

图4 参数γA对定位的影响

图5 参数γI对定位的影响

由图4可知,当参数γA取值在0.03～0.05范围之间,定位误差在26%左右,定位精度达到最高。随着参数的不断增大,估计位置逐渐偏离出真实物理位置。由图5可知,当参数γI取值在0.89～1.03范围之间,定位误差在25%左右,定位精度达到85%。参数取值接近于0,对定位精度影响较大,因为映射模型的修正几乎可以忽略不计,等同于用少量的信标节点通过质心算法求未知节点的坐标。

5 结束语

本文提出的算法综合考虑了非信标节点信息和无线传感器网络结构的局部信息,将节点定位问题转化为半监督回归问题,建立了信号空间和物理空间之间的映射模型。通过对香港科技大学数据集进行仿真实验表明,LP-LapRLS算法相比于同类算法精确度和稳定性更加优异。

本文在建立预测模型的过程中,并没有考虑外部环境的影响,例如温度、湿度或者节点的非正常死亡等,不能动态地自适应现场的环境。下一步的工作是建立一个动态自适应的预测模型。

[1] 王福豹,史 龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005,16(5):857-868.

[2] DANG Xiaochao,HEI Yili,HAO Zhanjun.An Improved Indoor Localization Based on RSSI and Feedback Correction of Anchor Node for WSN[C]//Proceedings of International Conference on Computer,Information and Telecommunication Systems.Washington D.C.,USA:IEEE Press,2016:1-5.

[3] TAHERI M,MOTAMEDI S A.Transceiver Optimization for ToA-based Localization of Mobile WSN[J].Journal of Circuits System & Computers,2016,25(9).

[4] RAN Qiu,FENG Renjian,YU Ning,et al.A Weighted Least Squares Source Localization Algorithm Using TDOA Measurements in Wireless Sensor Networks[C]//Proceedings of the 6th International Conference on Electronics Information and Emergency Communication.Washington D.C.,USA:IEEE Press,2016:10-13.

[5] MOHAPATRA S,BEHERA S,TRIPATHY C R.A Comparative View of AoA Estimation in WSN Positioning[M].Berlin,Germany:Springer,2015.

[6] 朱 莉,顾能华,姚英彪,等.基于RSSI的WSN二维对数搜索定位算法[J].计算机工程,2014,40(4):87-90.

[7] GUI Linqing,VAL T,WEI A,et al.Improvement of Range-free Localization Technology by a Novel DV-hop Protocol in Wireless Sensor Networks[J].Ad Hoc Networks,2014,24(2):55-73.

[8] 陈 迅,唐红雨,涂时亮,等.无线传感器网络主动分布式节点定位算法[J].计算机工程与设计,2008,29(7):1664-1667.

[9] ZHOU C,XU T,DONG H.Distributed Locating Algorithm MDS-MAP (LF) Based on Low-frequency Signal[J].Computer Science & Information Systems,2015(12):55.

[10] 王景珲.一种基于DV-Hop的无线传感器网络节点定位算法[J].计算机工程,2015,41(1):82-86.

[11] 顾晶晶.基于局部拓扑结构的无线传感器网络定位研究和应用[D].南京:南京航空航天大学,2011.

[12] 张兴福.基于流形学习的局部降维算法研究[D].哈尔滨:哈尔滨工程大学,2012.

[13] PAN J J,PAN S J,YIN Jie,et al.Tracking Mobile Users in Wireless Networks via Semi-supervised Colocali-zation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(3):587-600.

[14] BELKIN M,NIYOGI P,SINDHWANI V.Manifold Regularization:A Geometric Framework for Learning from Labeled and Unlabeled Examples[J].Journal of Machine Learning Research,2004,7(1):2399-2434.

[15] PAN J J,YANG Qiang,CHANG Hong,et al.A Manifold Regularization Approach to Calibration Reduction for Sensor-network Based Tracking[C]//Proceedings of National Conference on Artificial Intelligence.New York,USA:ACM Press,2006:988-993.

[16] 孙艳娜.基于2DPCA的人脸识别方法[D].西安:西安电子科技大学,2013.

[17] GU Jingjing,CHEN Songcai.Manifold-based Canonical Correlation Analysis for Wireless Sensor Network Localization[J].Wireless Communications & Mobile Computing,2012,12(15):1389-1404.

[18] PAN J J,PAN S J,YIN Jialin,et al.Tracking Mobile Users in Wireless Networks via Semi-supervised Colocalization[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2012,34(3):587-600.