基于粒子群最小二乘支持向量机的无线传感网络定位算法的研究

摘要：针对传统野外无线传感网络节点定位存在环境复杂，节点分散，没有规律的分布等导致一些定位难题，本文提出了一种基于粒子群优化最小二乘支持向量回归机的三维无线传感器网络节点定位方法。实验表明，发现该方法在较少的样本条件下，亦能非常逼近目标值，具有精确的定位能力。

关键词：粒子群最小二乘支持向量机 无线传感器网络定位 训练样本集

中图分类号：TP273 文献标识码：A 文章编号：1007-9416（2015）11-0000-00

Abstract： in this paper， a 3D wireless sensor network node localization method based on particle swarm optimization is proposed， which is based on the particle swarm optimization algorithm.Experiments show that the method can be very close to the target value， and has the ability to locate the target.

Keywords： particle swarm least squares support vector machine； wireless sensor network localization； training sample set

1 引言

近年，关于野外旅行越来越多，但是复杂的地理环境容易发生失踪现象。获取复杂地形的地理位置一直是无线传感网络定位相关研究工作的难题。支持向量机是建立在一套较好的有限样本下机器学习的理论框架和通用方法之下，既有严格的理论基础，又能较好的解决小样本、非线性、高维数和局部极小点等实际问题，已在很多领域得到了成功的应用。基于此，本文在对 RSSI 定位和 SVC 研究的基础上，提出基于粒子群最小二乘支持向量机的无线传感网络定位算法，并结合最近邻聚类算法和分布式的结构，以达到精确的定位能力。

2 最近邻聚类算法

最近邻聚类算法的前提是存在一个样本的数据集，每一个样本都有自己的标签，表明自己的类型[1]。现在有一个新的未知的数据，需要判断它的类型。那么通过计算新未知数据与已有的数据集中每一个样本的距离，然后按照从近到远排序。取前K个最近距离的样本，来判断新数据的类型[2]。

假设已有混合样本集 ，按照最近邻原则进行聚类，算法如下：

① 选取距离阈值T，并且任取一个样本作为第一个聚类中心，如：。② 计算样本到的距离， 若，则 为中心的聚类中心，否则令为第二个聚合中心， 。

设，计算聚类中心到和的距离和，若 和，则建立第三个聚合中心。否则把 归于最近邻的聚合中心。依此类推，直到把所有样本都进行分类。

③ 按照某种聚类准则考察聚类结果，若不满意，则重新选取距离阈值、第一个聚合中心，返回②，直到满意，算法结束。

在样本分布一定时，该算法的结果在很大程度上取决于第一个聚合中心的选取和距离阈值的大小。该算法的优点是简单，如果有样本分布的先验知识用于指导阈值和起始点的选取，则可较快得到合理结果。对于高维的样本集来说，则只有经过多次试探，并对聚类结果进行验算，从而选择最优的聚类结果。

3 粒子群算法（PSO）

粒子群算法由Eberhart 博士和kennedy 博士在1995年提出， 来于对鸟群捕食的行为研究的算法，并推广于最优化问题的求解[3]。在使用PSO算法求解最优化问题时，每个问题的解被看作空间中一个没有质量，没有体积的粒子，每个粒子所在的位置被看作空间的一个解，根据个体与群体的飞行经验的来分析结果来随时调整飞行速度。假设在D维空间中，经历k次迭代，第i个粒子的速度和位置分为：，每个粒子都保存着自己的最好位置，个体极值和全局极值分别记为pbest，gbest。所以粒子i在进行k次迭代时的速度和位置更新可用下面的公式表示：

（3）

（4）

其中：w为惯性权重；c1，c2为学习因子，分别调节个体最好粒子和全局最好粒子方向飞行的最大步长，通常取2.0；r1，r2为[0，1]上的随机数。

3.1 惯性权重

在粒子群算法中的参数中，惯性权重是非常重要的参数，当w较大时有利于提高算法的全局搜索能力，但局部搜索能力较差；而当w较小时可以增强算法的局部搜索能力，但搜索新领域的能力较差。目前使用较多的是线性递减策略（LDW）：将w初始化为0.9，随着迭代次数的增加线性递减到0.3。如式所示：

（5）

其中， kmax为最大迭代次数，k为当前迭代次数。

3.2 适应度函数

适应度函数用来评价每个粒子的表现，适应度函数用来评价每个粒子的表现，是粒子选中的变量在故障诊断中表现的性能。考虑到过多的变量会增加定位精度

的复杂性和实时性，因此需要去除非必要变量以减少维数来提高定位精度的准确率。粒子的适应度函数可以选为

（6）

式中，其中分别是LS-SVM训练输出值和实际输出值。

4 最小二乘支持向量机（LS-SVM）

近年来，统计学习理论在数据分类，回归预测研究方向上取得了突破性的进展。统计学习理论是一种专门研究小样本情况下机器学习规律的理论[4]。Vapnik 在 1995 年提出一种新型统计学习方法―支持向量机，SVM 是建立在一套较好的有限样本下机器学习的理论框架和通用方法之下，既有严格的理论基础，又能较好的解决小样本、非线性、高维数和局部极小点等实际问题，已在很多领域得到了成功的应用，如指纹识别，物体分类等。最小二乘支持向量机是Suykens和 Vandewalb提出的SVM变形算法，其优化指标采用了平方项，只有等式约束，而没有C-SVM的不等式约束，从而推出不同的一系列的等式约束，而不是二次规划

问题[5]]6][7][8]。其问题表示为：

（7）

式中，为正则化参数。

可得到线性方程组：

（8）

核函数本文采用径向基核函数

（9）

式中 σ为径向基核参数。在没有关于问题的先验知识时，由这种核函数训练而成的模型具有比基于其他核函数的模型更好的总体性能。

和可通过最小二乘法解得，应用LS-SVM对非线性函数回归的结果为[6][7]：

（10）

最小二乘支持向量机的最大优点就是能显著提高标准支持向量机的训练速度，简化了计算复杂度[6]。

5具体实现步骤

（1）根据实际地形进行节点的布置，原则上每个节点距离不应超过节点最大传输距离的50%。

（2）计算聚类中心。首先，根据实际需要每个聚类中心至少四个已知节点，运用最近邻聚类算法，把距离未知节点最近的点作为聚类中心，然后设置聚类节点的阀值，一般只进行两类的聚类，即离未知节点较近的聚为一类，较远的聚为一类。

（3）利用分布式结构，进行数据的采集。以聚类中心为中心点，进行网格划分，称为第一层划分，记录聚类中心的坐标和到每个参考节点的距离。再利用划分的小网格，计算每个小网格的聚类中心的坐标和到每个参考节点的距离，称第二层划分，以此类推，直到到达精度为止。

（4）构建粒子群优化最小二乘支持向量机的构建

步骤1 训练样本集为，测试样本集为。对LSSVM中的惩罚因子和核函数宽度初始化；同时对粒子群算法中粒子的速度向量v也初始化为（0，1）之间的随机数。 定义PSO算法的截止迭代的次数=100，初始种群规模为50，权重因子，粒子群算法中的权重函数w根据式（5）从0.9线性地减少到0.3

步骤2 初始化后，将训练样本集带入网络中，根据式（6）评价每个粒子的适应度函数，分别是LS-SVM训练输出值和实际输出值。在PSO算法的迭代中，如果当前粒子的适应度优于上一代粒子的适应度，则令当前粒子值等于pbest值，如果在整个群体中，其余某个粒子的适应度好于当前粒子的最优值，则令该粒子值等于gbest值。

步骤3 将更新后的pbest值和gbest值代入式（3）和式（4），得到新一代粒子的速度和位置向量。

步骤4 在本轮算法学习结束后，如果当前迭代次数达到了预先设定的最大次数或最小目标误差，则得出最优的惩罚因子和核函数 。

步骤5 形成训练样本集：把每层节点距离向量到样本自身的坐标形成训练样本集。训练定位模型，选用径向基（RBF）核函数[9]，利用步骤4得出的正则化参数和核参数训练样本集的数据经预处理后得到，利用 LSSVR 对其训练，获得定位模型 X-LSSVR、Y-LSSVR 和 Z-LSSVR。

（5）进行定位：利用 RSSI 测距，得到离未知节点最近的聚类中心节点，然后对数据进行归一化处理，利用上面构建粒子群优化最小二乘支持向量机回归模型，得出最终归属的那个区域，并把这个区域的聚类中心作为未知节点的坐标。

6 实验测试结果

为验证本文提出算法的正确性，，分别进行 50 个节点和 100个已知节点的 分布，并随机产生10个未知节点，分别对其定位误差进行统计并求其平均定位误差。然后以不同的节点平均测距误差率的值为横坐标，以对应的定位误差率为纵坐标绘图，然后在 Windows7 环境下的 Matlab 7.0 软件中，对最小二乘二维定位算法进行误差分析。

分析方法是：设定定位精度公式为

（11）

为预测坐标，为真实坐标，已知50 个节点和 100个节点的正确率为表1。

仿真对比实验，算法的定位精度基本满足实际需要，同时节点布置越多，定位越准确。

7结语

本文提出基于粒子群优化最小二乘支持向量回归机的三维无线传感器网络节点定位方法算法，利用粒子群能够快速寻优的特点，克服了认为选取的盲目性和随意性，具有较高的精度，实现了正则化参数和支持向量机核参数达到最优选择。同时，对于野外复杂环境，利用分布式的方式逐步判断，达到高效的速度，找到最优位置。通过实验结果可以看到，实验表明发现该方法在较少的样本条件下，亦能非常逼近目标值，具有精确的定位能力。

参考文献

[1]李杰星，章云，符曦.一种改进的最近邻聚类学习算法[J]；控制理论与应用，2000年05期.

[2]沈清，杨霖.模式识别导论.长沙：国防科技大学出版社，1991.

[3]杨冬云，李数函.粒子群算法在支持向量机参数选择优化中的应用研究[C]中国控制与决策学术年会论文集，2007：447-452.

[4]邓乃扬，田英杰.支持向量机理论、算法与拓展[M].北京：科学出版社，2009.

[5]李应红，尉询楷.支持向量机的工程应用[M].北京：兵器工业出版社，2004.

[6]王晓丹，王积勤.支持向量机训练和实现算法综述[J].计算机工程与应用，2004（13）： 75-79.

[7]肖勇.基于最小二乘和支持向量机的 WSN节点定位方法研究[D].赣州：江西理工大学，2011 .

[8] 周松斌，刘桂雄，张晓平，等.基于LS-SVR的无线传感器网络节点定位算法[J].制造业自动化，2008 ，30（9）：12-16 .

[9] 支持向量机核函数的构造方法研究与分析[J].高师理科学刊，2010，30（20）：23-26.