一种基于核方法的无线传感器网络定位算法

林海

摘 要：无线传感器网络（WSN）作为一种新兴的分布式网络技术，被认为是21世纪改变世界的十大革新技术之一。定位是无线传感器网络的重要支撑技术之一，实现传感器节点自定位是提供监测目标位置信息的必要条件。而实现高效、可靠、准确的节点定位对目标跟踪具有重要意义。不幸的是，环境噪声使得节点的定位精度降低。基于此，该文提出一种基于核方法的无线传感器网络定位算法。实验表明，在WSN中通过采用卡尔曼滤波的核方法定位算法，一定程度上减少了随机噪声对节点定位精度的影响，有效的降低了系统定位误差，实现一定程度的抗干扰。

关键词：卡尔曼滤波 传感器网络 定位 核方法

中图分类号：TP301 文献标识码：A 文章编号：1674-098X（2014）09（b）-0051-04

无线传感器网络（Wireless Sensor Network，WSN）将逻辑上的信息世界与真实物理世界融合在一起，改变了人与自然的交互方式，是继Internet之后将对人类生活方式产生重大影响的新兴IT技术之一。WSN是集计算机、网络、通信、传感器、嵌入式系统、智能计算、微电子等多个领域于一体的交叉学科，可由大量的体积小、种类繁多、价格低廉的传感器节点（采集、传感、收发、处理于一体）以自组织的形式形成自治网络，实现对真实物理世界动态智能协同感知。

随着无线传感器网络的快速发展，传感器节点的位置信息在WSN的诸多实际应用中将成为不可或缺的一部分，如在火灾监控、环境监测、潮汐、生态学等研究领域，采用WSN对物理世界信息的收集和处理。如在火场战斗员的跟踪应用中，结合传感器节点感知目标运动速度和传感器节点自身位置，可火场战斗员的运动轨迹并预测目标的运动方向。

全球定位系统（Global Positioning System，GPS）以全天候、高精度、自动化、高效益的特点，应用于众多的户外定位领域，但实际应用中，不是所有传感器节点都能利用GPS来定位，原因如下：（1）GPS和传感器节点相比，质量较重、功耗较大且价格昂贵，而传感器节点则质量轻、低功耗且价格低廉；（2）GPS适合在开阔户外使用，而户内或有障碍物遮挡等环境却不适用；（3）在特殊条件下（如GPS系统被摧毁）将无法使用GPS。

综上所述，在特殊环境下WSN有其独有的优势，使得利用WSN进行定位成为一个热门的研究方向。从提出传感器网络这个概念至今，如何设计高效、高精度的定位算法一直是传感器网络研究中的热点问题之一。针对不同的硬件设施和应用环境，学术界提出了众多的节点定位算法，其主要包括基于测距的定位算法，例如Cricket室内定位系统、RADAR系统、基于AOA的APS（Ad hoc Position System）算法、DPE（Directed Position Estimation）定位算法、凸优化定位算法等，和基于非测距的定位算法，例如质心算法（Centroid Algorithm）、DV-Hop（Distance Vector Hop）算法、基于SVM（Support Vector Machine）定位算法等。

真实物理环境是存在随机干扰的，在传统的基于RSSI的WSN定位算法中（例如SVM、DV-Hop等），并未考虑环境随机噪声对RSSI信号强度的影响（例如在定位过程中障碍物的随机游动等），从而导致估算的位置信息在一定位置空间范围内发生抖动。为了减少和平滑这种位置信息的抖动现象，该文提出了一种基于核方法的无线传感器网络定位算法，通过采用卡尔曼滤波的核方法定位算法，一定程度上减少了随机噪声对节点定位精度的影响，有效的降低了系统定位误差，实现一定程度的抗干扰。

1 传感器网络建模

考虑由N个传感器节点组成的无线传感器网络部署在二维ROIC中，，各节点ID分别为1，2，…，N。令集合…表示传感器节点集合，节点的真实坐标为…表示节点坐标矩阵。不失一般性，令集合中的前个元素表示信标节点，其坐标在系统初始化阶段已给出，并令…表示信标节点的坐标矩阵。节点定位的目标是计算未知节点坐标的估计值…，使得尽可能地逼近未知节点的真实坐标。

2 核方法定位

2.1 核函数的定义

令c为输入空间，核函数k隐含地定义了非线性映射：

（1）

使低维输入空间c中的数据投影到高维特征空间中。核函数定义为特征空间中的内积，即：

（） （2）

核函数的进一步解释：

（1）由模式可分性定理可知，一个复杂的模式分类问题从低维空间映射到高维空间后，变得更容易线性可分，并且使用经过核函数转化后的线性分类器可以对线性数据进行分类，且分类效果更优。

（2）满足Mercer定理的核函数隐含地定义了从输入空间到高维特征空间的映射。如果直接在高维特征空间内计算内积会面临维数灾难问题。然而，核函数的引入解决了该维数灾难问题，并且不会增加计算的复杂度。

（3）核函数可以看成是线性空间中样本间的相似性的度量，它既可以定义在样本间的距离上，也可以定义在样本间的相似度上。

定义1.1（正定核函数（Positive Kernel））：（连续情况）如果对称函数，使得下式成立：

（3）

则称函数为正定核函数；（离散情况）或者对于任意的样本集和系数，对称函数

满足：

≥0 （4）

则称对称函数为正定核函数。

在数学上，正定核函数有严格的定义，其中最著名的是Mercer定理。

定理1.1（Mercer定理）：假设对称函数使得积分算子

（5）

是正定的，则：

（6）

对称函数称作算子对应的正定核函数。endprint

2.2 核函数和定位问题的联系[1]

在WSN中，节点间都是通过无线的方式进行通讯，无线信号容易受到环境的干扰，测量误差较大，表现为测量数据的高非线性和不确定性。在以往的研究中发现，测量数据的非线性能够通过核函数进行捕获。

传感器网络节点间的信号强度与距离之间的关系为：

（7）

其中，P为节点发射电压，k为比例因子，为节点间的真实距离，μ是信号衰减系数，通常。

基于距离的径向基核函数具有以下的形式：

（8）

其中，是定义在上的函数。容易验证，当方程（8）中的时，方程（7）和方程（8）等价。因此，传感器网络节点间的信号强度衰减模型和基于距离的径向基核函数之间必然存在联系，而且可以通过核函数来度量节点之间的关系。值得注意的是，当无线传感器网络工作在理想环境中时，信号强度矩阵是半正定的，因此，信号强度矩阵自身就可以被认为是核函数矩阵。

另外，Sheng等人证明了，在传感器节点定位问题中，声波强度衰减模型和高斯核函数相似。

节点信号强度空间和节点坐标空间如图1所示。如果将网络中的节点看成是独立的器件，它们可以和通信半径内存在视距关系的任意节点双向通信，那么下面的观测是成立的：

（1）如果两个节点的无线信号覆盖区域存在交集，那么它们可以直接通信。

（2）如果两个节点接收到的来自网络中的其余的节点的信号强度形成的信号强度向量之间的距离越小，那么它们之间的真实距离越近，即它们越相似。

（3）如果两个节点之间的实际距离越远，那么它们接收到的来自网络中的其余的节点的信号强度形成的信号强度向量之间的距离就应该越大，即它们之间的不相似性越大。

因此，在节点定位过程中，可以通过相似性或者不相似性在节点的信号强度空间和节点分布的坐标空间之间搭起一座桥梁，进而通过考察节点间的相似性关系或者不相似性关系来估计未知节点的坐标。例如，当选择相似性度量节点之间的关系时，先通过相似性度量函数和节点间信号强度建立一个映射，然后再通过考察节点间相似性关系和节点真实坐标之间的关系在相似性度量和节点的坐标空间之间建立一个映射。由于正定核函数可以看成是线性空间中样本间相似性的度量，所以可以通过核函数建立起信号空间和坐标空间之间的关系，即通过正定核函数将信号强度空间中的节点信号强度向量投影到核函数对应的RKHS空间中。由于核函数的引入，使得由于测量误差造成的信号强度空间中的非线性关系，投影到了中节点间的函数关系，考虑到核函数投影是非线性投影，因此，可能将原来信号强度空间中的非线性关系变成中函数间的线性关系。当选择不相似性关系信号强度空间和坐标空间时，根据条件正定核函数的定义，可以选择条件正定核函数来度量节点之间的不相似性。条件正定核函数同样可能将原来信号强度空间中的非线性关系变成函数间的线性关系。

由上分析可知，当选择核函数来解决传感器网络中的节点定位问题时，核函数的选择至关重要，如何选择合适的核函数来设计核函数相关的定位算法是定位机制设计者必须面对的问题。

2.3 核方法定位

在定位算法中，给定n个训练数据样本，其中表示输入空间。表明数据点是否位于区域中，如果数据点位于C中，则，

否则。定位算法需寻求一个判别函数并最小化定位错误[2]。

核方法定位的核心是核函数，它描述了输入空间中两点和的相似度。一般情况下，核函数需是一个对称正定核。Mecer定理表明存在特征空间，使得核函数为特征空间中两个向量和的内积，即。核方法定位算法是在特征空间选择一个线性函数，对于w满足≤B并最小化训练错误：

（9）

φ是相应的损失函数，因此f可直接用核函数表达为：

（10）

有许多核函数满足正定性，例如高斯核函数：

多项式核函数：

3 卡尔曼滤波建模

下面简述Kalman滤波模型，定义观测方程：

（11）

系统方程

（12）

是t时刻状态向量，是从t-1时刻到t时刻的已知状态转移矩阵，是t时刻观测向量，是t时刻观测数据，为t时刻观测噪声，是均值为零协方差矩阵为的时间序列，是t时刻过程转移矩阵，描述了期望的位置变化，是t时刻输入噪声，是均值为零协方差矩阵为的时间序列。

Kalman滤波算法方程集为：

（13）

设在t-1时刻，对应于测试点（未知节点）相对于参考点（信标节点）的m维状态向量为的各个分量为时间序列。并设t时刻的预测值等于t-1时刻的最优估计值，即。定位系统中无控制量，假设由噪声驱动，所以状态转移矩阵和过程转移矩阵在任意时刻t都为m阶单位阵：

并假设在任意时刻t，过程（输入）噪声和观测噪声的各分量和分别服从均值为0、方差为和的正太分布，即。由于参考点系统独立，则的各分量相互独立、的各分量相互独立，相应的协方差矩阵为：

则方程集（13）可简化为：

（14）

过程噪声的协方差矩阵系数可以通过在实际环境中测量得到，而观测噪声的协方差矩阵系数可以适当指定，一般情况下要求，这样Kalman滤波算法在迭代过程中才能收敛。的初始值可以适当假设，但对角元素不能为0，例如，可设。

4 实验环境

选择空旷平坦区域作为仿真实验场所，在12.8 m×12.8 m=163.84 m2的实验区域范围内布置一个（测试）移动节点、七个（参考）信标节点、一个汇聚节点，且保证节点之间无障碍物遮挡，同时保证WSN网络中信号均匀无缝隙覆盖，节点布置方式如图2所示。为使测试节点收到的RSSI向量有良好的区分度，需将参考节点尽可能的放置在角落，且参考点必须保持在同一平面内。endprint

如图2所示，将实验区域进行均匀分割，被分割成的子区域作为一个类别，这里我们采用1.6 m的等距分割，将实验区域分成64个子区域并将其编号为0～63，并在欲定位的子区域内采集测试点指纹（RSSI向量），采集次数为。

5 仿真结果及分析

如图3所示为待定位区域采集样本点结果的分布情况，灰色点表示未采用Kalman滤波算法的定位结果，黑色点表示采用Kalman滤波算法的定位结果，通过对比可以得出未采用Kalman滤波算法的定位结果呈现定位数值波动大、数据不稳定，极大影响了定位精度。相反在进行了Kalman滤波之后，数据波动小，较稳定，集中分布在均值附近，提高了定位的稳定性。

如图4所示为待定位区域内增加了随机干扰后进行的样本点采集和定位结果的分布情况，黑色点表示采用Kalman滤波算法并采用高斯核函数的定位结果分布，灰色点表示未采用Kalman滤波并使用其他核函数的定位结果分布。通过对比可以得出采用Kalman滤波和高斯核函数之后，样本点分布收敛，定位结果波动范围小，稳定地分布在均值附近，提高了定位的精确性。

6 结语

综上所述，通过采用Kalman滤波算法，能够过滤掉定位系统本身和环境所带来的随机噪声，使得对应于特征输入空间的采集样本向量各维度波动范围非常小，提高了采集样本数据的稳定程度。在核方法定位算法中，通过选取高斯核函数，一定程度提高了定位的精确程度。通过二者的结合，该定位算法一定程度上提高了WSN非测距定位的稳定性和精确性。

参考文献

[1] 王成群.基于学习算法的无线传感器网络定位问题研究[D].浙江大学，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint

如图2所示，将实验区域进行均匀分割，被分割成的子区域作为一个类别，这里我们采用1.6 m的等距分割，将实验区域分成64个子区域并将其编号为0～63，并在欲定位的子区域内采集测试点指纹（RSSI向量），采集次数为。

5 仿真结果及分析

如图3所示为待定位区域采集样本点结果的分布情况，灰色点表示未采用Kalman滤波算法的定位结果，黑色点表示采用Kalman滤波算法的定位结果，通过对比可以得出未采用Kalman滤波算法的定位结果呈现定位数值波动大、数据不稳定，极大影响了定位精度。相反在进行了Kalman滤波之后，数据波动小，较稳定，集中分布在均值附近，提高了定位的稳定性。

如图4所示为待定位区域内增加了随机干扰后进行的样本点采集和定位结果的分布情况，黑色点表示采用Kalman滤波算法并采用高斯核函数的定位结果分布，灰色点表示未采用Kalman滤波并使用其他核函数的定位结果分布。通过对比可以得出采用Kalman滤波和高斯核函数之后，样本点分布收敛，定位结果波动范围小，稳定地分布在均值附近，提高了定位的精确性。

6 结语

综上所述，通过采用Kalman滤波算法，能够过滤掉定位系统本身和环境所带来的随机噪声，使得对应于特征输入空间的采集样本向量各维度波动范围非常小，提高了采集样本数据的稳定程度。在核方法定位算法中，通过选取高斯核函数，一定程度提高了定位的精确程度。通过二者的结合，该定位算法一定程度上提高了WSN非测距定位的稳定性和精确性。

参考文献

[1] 王成群.基于学习算法的无线传感器网络定位问题研究[D].浙江大学，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint

如图2所示，将实验区域进行均匀分割，被分割成的子区域作为一个类别，这里我们采用1.6 m的等距分割，将实验区域分成64个子区域并将其编号为0～63，并在欲定位的子区域内采集测试点指纹（RSSI向量），采集次数为。

5 仿真结果及分析

如图3所示为待定位区域采集样本点结果的分布情况，灰色点表示未采用Kalman滤波算法的定位结果，黑色点表示采用Kalman滤波算法的定位结果，通过对比可以得出未采用Kalman滤波算法的定位结果呈现定位数值波动大、数据不稳定，极大影响了定位精度。相反在进行了Kalman滤波之后，数据波动小，较稳定，集中分布在均值附近，提高了定位的稳定性。

如图4所示为待定位区域内增加了随机干扰后进行的样本点采集和定位结果的分布情况，黑色点表示采用Kalman滤波算法并采用高斯核函数的定位结果分布，灰色点表示未采用Kalman滤波并使用其他核函数的定位结果分布。通过对比可以得出采用Kalman滤波和高斯核函数之后，样本点分布收敛，定位结果波动范围小，稳定地分布在均值附近，提高了定位的精确性。

6 结语

综上所述，通过采用Kalman滤波算法，能够过滤掉定位系统本身和环境所带来的随机噪声，使得对应于特征输入空间的采集样本向量各维度波动范围非常小，提高了采集样本数据的稳定程度。在核方法定位算法中，通过选取高斯核函数，一定程度提高了定位的精确程度。通过二者的结合，该定位算法一定程度上提高了WSN非测距定位的稳定性和精确性。

参考文献

[1] 王成群.基于学习算法的无线传感器网络定位问题研究[D].浙江大学，2009.

[2] XuanLong Nguyent，Michael I.Jordant，Bruno Sinopolit.A Kernel-based learning approach to ad hoc sensor network localization，2004.

[3] Tarun Dubey， Om Prakash Sahu. Broadcasting with Controlled Redundancy and Improved Localization in Wireless Sensor Networks. Journal of Electronic Science and Technology，2013.

[4] Huanqing Cui，Chuanai Zhou，Xiaojing Meng，Rong Hua.Mobile Anchor Assisted Localization in Wireless Sensor Networks with Reg ular Polygon Path. Proceedings of 2013 IEEE 4th International Conference on Software Engineering and Service Science，2013.endprint