基于粒子群优化的多维标度节点定位算法*

刘 政

（桂林航天工业学院自动化系，广西桂林541004）

基于粒子群优化的多维标度节点定位算法*

刘 政*

（桂林航天工业学院自动化系，广西桂林541004）

针对无线传感网络节点定位易受外部环境影响的问题，提出一种基于粒子群寻优的多位标度定位算法。利用基于动态路径损耗指数的接受信号强度测距，建立距离矩阵，使用多维标度方法构建节点的相对坐标，通过四参数坐标转换模型得到绝对坐标，再用绝对坐标与实际坐标的差异度作为粒子群寻优的适应度函数，通过分群搜索，优化节点位置估计。仿真结果表明：改进算法对实际环境影响具有较好的鲁棒性，节点定位精度有了明显的提高，能够满足定位系统需求。

无线传感器网络；节点定位；多维标度；粒子群

无线传感器网络（Wireless Sensor Network，WSN）是由一些随机部署在检测区域内的无线传感器节点通过节点间的无线通信而形成的自组织网络系统［1］。在无线传感器网络研究、应用中，节点定位一直是个热门的应用方向。到目前为止，很多专家、学者提出了各种关于无线传感器网络的节点定位算法，这些算法在定位精度、平均定位误差、定位节点的连通率、节点能量损耗、信标节点分布密度等指标上进行不断的改进。

多维标度法（Multidimensional-Scaling，MDS）是一种把实体间的相关性转换为空间坐标的数据分析方法，利用网络分布中节点间的相关信息来确定节点的空间坐标。早期，由Shang等提出的MDS-MAP［2-4］多维标度定位算法，利用节点间的距离信息构造目标对象间的相异性距离矩阵，再求解中心内积矩阵的非零特征值及特征向量，最终求得相对坐标。后期，相继有人提出了基于MDS的改进算法，比如：距离重构MDS［5］、改进分布式MDS［6-7］、分布加权式MDS［8-9］、非线性滤波MDS［10］等。以上基于MDS的定位算法实际上是利用WSN网络中可通信节点间的关联信息来获取节点的空间坐标，即使网络中没有信标节点，也能计算定位节点的相对坐标，只需补充少量信标节点，就能将相对坐标转换为定位节点的绝对坐标。然而，MDS算法的基础是计算网络中定位节点间欧氏距离组成的距离矩阵，而节点间距信息的获取易受外部环境影响，会引入较大的测距误差，降低定位精度。

为了提高定位精度，本文引入改进RSSI测距来降低测距误差影响，并用分群PSO算法搜索MDS坐标变换的最小坐标差异度，寻找最优位置估计。仿真实验验证，改进算法优化了节点坐标估计，有效地提高了节点定位精度。

1 SPSO-MDS算法

1.1 MDS算法

设r维空间中的n个点表示为X1,X2,…,Xn，用矩阵表示为X=(X1,X2,…,Xn)′，称X为距离阵D的一个拟合构图，求得的n个点之间的距离阵称为D的拟合距离阵，和 D尽可能接近。如果，则称X为D的一个构图。

对应欧氏空间的n个点，其距离阵为D=(dij)n×n，它们所对应的空间的维数为r，第i个节点对应的点记为 Xi，则 Xi的坐标记作

设B=(bij)n×n，其中：

用矩阵表示为：

记λ1≥λ2≥…≥λr为B的正特征根，λ1,λ2,…, λr对应的单位特征向量为 e1,e2,…,er，Γ=(e1,e2,…,er)是单位特征向量为列组成的矩阵，则，X矩阵中每一行对应空间中的一个点，第i行即为 Xi。令Λ=diag(λ1,λ2,…,λr)，那么：

多维空间中的节点相对坐标为：

按照式（2）求出各个点对之间的内积，得到内积矩阵B的r个非零特征值及所对应的一组特征向量，再根据式（4）即可求出X矩阵的r个列向量或空间n个点的坐标。若使用二维坐标，只需保留两个最大的特征值及对应的特征向量，若使用三维坐标，需要保留三个最大的特征值及对应的特征向量，传感器网络各节点的相对坐标即可得到［11］。

通过以上多维标度法获得的节点坐标是相对坐标，需要变换到信标节点的绝对坐标系中。在二维空间有3个以上信标节点或者在三维空间有4个以上信标节点，就可以利用信标节点的绝对坐标位置，通过平移、旋转和映射等线性变换，将相对坐标转换到信标节点所在的绝对坐标系中去。考虑到二维空间的适用性，利用四参数坐标转换模型建立两个平面坐标系的转换关系，它包括两个平移参数、一个旋转参数和尺度参数，其转换模型为：

式中：(y1,y2)为转换后的绝对坐标，(x1,x2)为相对坐标，Δx1、Δx2为平移参数，m为尺度参数，α为旋转参数。

1.2 SPSO寻优算法

粒子群算法（Particle Swarm Optimization，PSO）通过迭代计算当前搜索到的局部最优值来寻找全局最优值，并建立适应度函数来评价解空间的性能。为了加快寻优速度，对PSO算法进行改进，得到SPSO算法。

SPSO算法描述：设由N个粒子组成的粒子群以一定的速度在二维空间中搜索最优解，粒子i在二维空间的位置表示为Zid=（zi1,zi2），飞行的速度表示为Vid=（vi1,vi2），经过迭代计算，每个粒子搜索个体最优位置Pdbest=（pd1,pd2）和全局最优位置Pgbest=（pg1,pg2）。每个粒子在找到个体和全局两个最优值后，根据式（6）来更新速度与位置：

式中：w为惯性权重，k是迭代次数，c1和c2是加速因子，r1和r2是［0，1］之间的随机数。

建立以winner粒子为核心的多个子群［12］。在每次迭代完后，winner粒子的适应度函数filter(zj,vj)需满足式（7）要求，以winner粒子为中心进行分群搜索，比较winner粒子Pdbest与分群Psgbest的适应度函数，得到子群最优；再比较Pdbest与种群Pgbest的适应度函数，找到种群最优。

分群搜索过程描述如下：

将种群分割成成若干个子群，将种群大搜索分解为子群同步小搜索，既缩小了搜索范围，又提高了收敛速度。

1.3 改进RSSI测距

基于RSSI测距的前提是路径损耗指数为常数，但是如果区域环境发生变化，那么不同区域的路径损耗指数存在差异，所以未经修正的RSSI测距会引入较大的误差，为了减少这种误差，考虑找到能够描述区域路径损耗指数的算式［13］。

对数-常态分布模型：

式中，RSSI（d）：接收信号强度；Pt：发射信号功率；PL(d)：路径损耗；d0：近地参考距离；PL(d0)：传输d0距离的路径损耗；n：路径损耗指数；Xσ：平均值为0的高斯分布随机变数。

通过计算区域邻居信标节点（B1、B2、B3）间的RSSI值，得到当前区域内的路径损耗指数：

合并式（9）、式（10），得到路径损耗指数算式：

将式（11）代入式（8），得到基于动态路径损耗指数的RSSI测距算式

1.4 SPSO-MDS算法描述

由MDS算法中的式（5）坐标转换模型得到绝对坐标：

设定diver(x,y)函数来衡量实际坐标(z1,z2)和转换后绝对坐标(y1,y2)的差异度［14］：

将差异度函数diver(x,y)作为SPSO寻优过程中的适应度函数filter(z,v)：

通过分群搜索，寻找全局最优位置Pgbest：

SPSO-MDS算法描述如下：

步骤1改进RSSI测距，获取节点间的距离，构成距离阵D；

步骤2由式（1）～式（5）得到节点MDS相对坐标和绝对坐标，作为SPSO粒子初始位置；

步骤3由式（6）更新粒子位置和速度，用式（7）搜索winner粒子；

步骤4由式（14）得到的差异度函数替代SPSO寻优的适应度函数，找到群最优。

2 实验仿真与分析

本文基于MATLAB平台进行仿真实验，仿真参数设置：信标节点20个，未知节点60个，随机分布在100 m×100 m的正方形区域，节点通信半径30 m。

评价指标：平均定位误差（Average Position Error，APE）。

式中：xest为估计位置，xreal为实际位置，N为待定位节点个数，R为节点通信半径。

比较SPSO-MDS算法与MDS-MAP、MDS-MAP（P）算法之间的性能差异，分别以测距误差、信标节点数、网络连通度对APE的影响程度来验证改进效果。

2.1 测距误差对APE的影响

从图1可以看出，在同等测距误差影响下，SPSOMDS算法的平均定位误差小于MDS-MAP和MDSMAP（P）算法。随着测距误差的增大，三种算法的平均定位误差都有逐渐增大的趋势，但改进算法的定位误差增长率最小，相比较另外两种算法，改进算法对测距误差的影响具有最好的鲁棒性，这是因为利用RSSI改进测距算式（12）获取动态路径损耗指数，减少了外部环境影响，降低了测距误差。

图1 定位误差受测距误差的影响

2.2 信标节点数对APE的影响

从图2可以看出，当网络中信标节点数量相同时，SPSO-MDS算法的平均定位误差小于MDS-MAP和MDS-MAP（P）算法。随着信标节点数逐渐增加，三种算法的平均定位误差都有下降的趋势。当信标节点数处于5%～30%之间时，平均定位误差下降迅速；当信标节点数超过30%，平均定位误差的下降趋势变缓且趋于稳定。整体来看，改进算法的效果明显优于另外两种算法。

图2 定位误差受信标节点数的影响

2.3 网络连通度对APE的影响

获取网络连通度对定位误差的影响，可以通过保持信标节点数不变，调整节点通信半径来比较效果。从图3可以看出，当网络连通度处于［5-25］区间，随着连通度的增加，三种算法的平均定位误差降低都比较明显，其中改进算法最显著；当连通度超过25以后，三种算法的平均定位误差下降变缓，连通度的影响逐渐弱化，反而由于可通信范围内节点数的增加，导致节点通信开销的增加。

图3 定位误差受网络连通度的影响

3 结束语

通过获取动态路径损耗指数，减少外部环境影响，降低测距误差，将改进测距应用于基于多维标度法的节点定位，提高距离矩阵精度，并进行分群粒子群搜索，对坐标差异度寻优。实验结果表明，与其它多维标度定位算法相比，同等影响因素下SPSO-MDS算法具有更高的定位精度，对实际环境的影响具有较好的鲁棒性，可以适用于无线传感器网络定位应用。

［1］孙利民，李建中，陈渝，等.无线传感器网络［M］.北京：清华大学出版社，2005.

［2］Shang Y，Ruml W，Zhang Y.Localization from Mere Connectivity in Sensor Network［C］//Proceeding of the 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing.2003：201-212.

［3］Shang Y，Ruml W.Improved MDS-Based Localization［C］//Proc of IEEE INFOCOM.Hong Kong：IEEE Press，2004：2640-2651.

［4］Shang Y，Ruml W，Zhang Y.Localization from Connectivity in Sensor Networks［J］.IEEE Trans on Parallel and Distributed System，2004，15（11）：961-973.

［5］黄亮，王福豹，段渭军，等.基于距离重构的无线传感器网络多维定标定位算法［J］.传感技术学报，2013，26（9）：1284-1287.

［6］刘健苗，许新忠，黄书广，等.改进的分布式无线传感器网络多维标度定位算法［J］.传感技术学报，2014，27（5）：692-697.

［7］Gopakumar Aloor，Lillykutty Jacob.Distributed Wireless Sensor Network Localization Using Stochastic Proximity Embedding［J］.Computer Communications，2010，33（6）：745-755.

［8］Chan F，So H C.Efficient Weighted Multidimensional Scaling for Wireless Sensor Network Localization［J］.IEEE Trans on Signal Processing，2009，57（11）：4548-4553.

［9］王新生，胡玉兰，刘永帅.一种改进的传感器节点多维标度定位算法［J］.小型微型计算机系统，2013，34（4）：727-731.

［10］陈岁生，卢建刚，楼晓春.基于MDS-MAP和非线性滤波的WSN定位算法［J］.浙江大学学报：工学版，2012，5（5）：866-872.

［11］秦爽.参数化多维标度定位方法研究［D］.成都：电子科技大学，2012.

［12］张亚明，史浩山，程伟，等.一种无线传感器网络中的进化定位机制［J］.西北工业大学学报，2013，31（4）：633-638.

［13］刘政.基于权重动态离散模型的WSNs定位算法［J］.传感技术学报，2015，28（3）：437-442.

［14］石欣，印爱民，陈曦.基于RSSI的多维标度室内定位算法［J］.仪器仪表学报，2014，35（2）：261-268.

刘 政（1981-），男，讲师，主要研究方向为无线传感器网络，智能仪器，davidbetty@163.com。

Node Localization Algorithm Based on Particle Swarm Optimization and Multidimensional Scaling*

LIU Zheng*
（Department of Automation，Guilin University of Aerospace Technology，Guilin Guangxi 541004，China）

Aiming to reduce the interference with the external environment in position algorithms for wireless sensor networks，an improved multidimensional scaling algorithm based on particle swarm optimization is proposed.RSSI based on dynamic path loss exponent is used to range，establish a distance matrix，build a relative coordinate with multidimensional scaling，and acquire absolute coordinate through four parameters coordinate transformation model.Then the difference of relative coordinate between absolute coordinate is utilized as the fitness function of particle swarm optimization and optimizes the node position estimation through sub-swarm search.The simulation reveals that the improved algorithm has good robustness to actual environmental impact，improves the node localization accuracy，and satisfies the needs of positioning system.

wireless sensor networks；node localization；multidimensional scaling；particle swarm optimization

TP393

A

1004-1699（2015）08-1228-05

��7230

10.3969/j.issn.1004-1699.2015.08.021

项目来源：国家自然科学基金项目（61202007）；桂林航天工业学院基金项目（YJ1302）

2014-11-13 修改日期：2015-05-27