基于混沌粒子群的WSN定位算法研究与matlab仿真

程 庆，张水锋，陈 帅

（1.淮南师范学院 计算机学院；2.淮南师范学院 电子工程学院，安徽 淮南 232001）

无线传感器网络简称WSN，它是一个分布式传感网络，也是一个很多学科高度交叉的研究领域，更是目前最热的研究领域之一，它的主要特点是动态性、可靠性、自组织和大规模等.现代无线传感器网络的发展离不开片上系统和传感器技术的发展进步.人们信息获取能力的提高离不开无线传感器网络的发展，通过无线传感器网络人们可以获得最直接、最真实、最有效的信息.因此，无线传感器网络具有广阔的应用前景，在城市管理、军事国防、生物医疗、工业控制、抢险救灾、环境监测以及危险区域远程控制等领域都得到广泛的应用.无线传感器网络由大量节点组成，它的三个要素是传感器、感知对象和观察者，它是一种由大量小型传感器所组成的网络.这些小型传感器一般称作传感器节点，这些节点通过一个或者几个基站来收集数据[1].

1 无线传感器网络定位原理及基本概念

检测、定位和通告是无线传感器网络进行目标跟踪的三个阶段.确定位置称为定位，它是无线传感器网络的重要支撑技术.自组织的网络通过一些方式方法来确定节点的位置信息就是无线传感器网络定位.确定目标在系统中的位置与确定自己在系统中的位置是定位的两个实际意义，也就是通常所说的节点自身定位与目标定位.确定节点的坐标位置的过程称为节点自身定位，确定网络覆盖范围内目标的坐标位置的过程称为目标定位[2].

在传感器网络定位中，可以把节点分为未知节点和信标节点，这种划分的依据是节点自身的位置是否已经知道.通过携带GPS定位设备等手段可以确定节点自身的位置，这种节点我们称为信标节点beacon node or anchor node，它是未知节点的参考节点，在无线传感器网络中占的比例很小.没有携带定位设备的节点我们称为未知节点unknown node，也就是除了信标节点剩下的都是未知节点,通信半径内的其他节点是邻居节点neighbor node.介绍了未知节点、信标节点和邻居节点的概念，我们来看下跳数及距离的概念.两个节点之间间隔的跳段总数称为跳数Hop Count.两个节点之间间隔的各跳段距离之和称为跳段距离.协助传感器节点定位的已知自身位置的固定设备称为基础设施.

2 无线传感器网络定位方法及分类

无线传感器网络常用的定位方法主要有：

2.1 三边测量法

已知 A、B、C 三点的坐标为(xa,ya)、(xb,yb)、(xc,yc),未知节点D到它们的距离为da,db,dc,设D点坐标为（x，y）.可列出如下公式：

由公式1可以解出D节点的坐标为：

2.2 三角测量法

已知 A、B、C 三点的坐标为(xa,ya)、(xb,yb)、(xc,yc),未知节点D相对于它们的角度为∠ADB,∠ADC,∠BDC,设D点坐标为（x，y）.对于节点 A，C 和角∠ADC，如果弧段 AC 在△ABC内，那么能够唯一确定一个圆，设圆心为O1(xo1,yo1)，半径为r1，那么 a=∠AO1C=(2π-2∠ADC),并可列出如下公式：

由公式2可以确定圆心O1点的坐标和半径r1.同理对A,B,∠ADB和B,C,∠BDC分别确定相应的圆心O2点的坐标、半径r2、圆心O3点的坐标和半径r3.最后利用三边测量法，由点O1、O2、O3的坐标确定D点的坐标.

2.3 极大似然估计法

已知1,2,3,……,n等n个节点的坐标分别为(x1,y1),(x2,y2),(x3,y3), ……,(xn,yn),节点 D 到它们的距离分别为 d1，d2，d3，……，dn,设 D 点坐标为（x，y）.可列出如下公式：

从第一个方程开始分别减去最后一个方程，得：

上式的线性方程表示方式为：AX=b,其中

使用标准的最小均方差估计方法可以得到X=(ATA)-1ATb即为节点D的坐标为[1].

无线传感器网络定位算法的分类方法有三种.第一种是基于测距Range-based和基于非测距range-free，第二种是递增式和并发式，第三种是信标节点和无信标节点.第一种算法的划分主要是根据是否测量距离，第二种算法的划分是根据节点的测量发生，第三种算法的划分是根据是否需要新标节点.

由于不需要额外配备测距设备，定位是通过计算跳数实现的，所以非测距定位更适合大规模的网络部署.非测距定位的优点是不需要额外的硬件设备，实现也相对容易；其缺点是比较依赖网络连通度和节点部署密度，对于较大规模的网络如果节点密度稀疏或分布不均，那么定位精度就会很低.非测距的定位算法，本文主要介绍三种，分别是质心算法、DV-hop算法和APIT算法.

基于测距的定位算法主要有TOA，TDOA，AOA和RSSI算法等，通过这些算法可以得到距离信息或者角度信息.依据这些信息，再结合前面提到的质心算法、三角测量法或者最大似然估计法来估计未知节点的位置.基于测距的定位算法的优点是具有较高的定位精度，缺点是节点需要携带额外的测距设备，因此对于规模小且定位精度要求高的网络比较适合这种算法.

3 混沌粒子群WSN定位算法原理

粒子群算法简称PSO算法，它是一种模拟鸟群随机搜寻食物的方式，依据个体经验和群体经验进行的群体智能算法.粒子群算法的优点是实现简单，收敛速度快.所以在模拟识别、多目标优化、神经网络以及控制决策等方向得到广泛的应用.PSO算法的原理是把网络节点作为一组随机粒子，再通过迭代方法求出最优解.在每一次迭代中，粒子通过个体最优解和全局最优解更新其速度和位置[3].

设Ha=(ha1,ha2,……,haD)是第 a个粒子(a=1,2,……,s)的 D维位置，Va=(va1,va2,……,vab,……,vaD)是粒子a的飞行速度，Pa=(pa1,pa2,……,pab,……,paD)是粒子a的个体最优解，Pg=(pg1,pg2,……,pgb,……,pgD)是整个种群的全局最优解.在每次迭代中粒子的速度和位置用下面两个式子来更新.

传统PSO算法的缺点是易陷入局部极值点易早熟收敛，把混沌思想引入粒子群算法可以解决这个问题，基于混沌的粒子群算法又称为CPSO算法.混沌理论是科学家在1975年提出来的，它在电路系统、保密通信及工程研究领域都得到了广泛的应用.混沌系统是一种复杂的非线性系统，它具有遍历性、混合性及随机性的特点.在物理学研究中经常提到遍历性的概念，在动力学系统中轨道具有回归性就认为它具有遍历性；若两个子集A、B，他们出现的概率成绩等于他们交集出现的概率，认为系统的混合的；随机性比较复杂，一是系统时域的随机混乱现象，二是系统长期不可预测性，三是系统频域的宽带白噪声，四是自相关性随着距离迅速衰减.混沌粒子群定位算法的原理如下.设在二维环境下未知节点i的估计坐标为 (xi,yi)与其邻居瞄节点j通过RSSI测距技术得到的距离为di,j，适应度函数表示式为f(xi,yi)，其中Bi为节点i邻居瞄节点数目，(xi,j,yi,j)为节点i邻居瞄节点j的坐标.算法的核心思想是求解使适应度函数f值最小的解，并以此作为未知节点的最优估计位置.

4 混沌粒子群定位算法的matlab仿真

对于混沌粒子群算法（CPSO）的定位算法，本文进行了仿真，结果如下.

5 小结

本文介绍了无线传感器网络定位的意义及混沌理论的原理，定位原理及基本概念，定位方法及分类，重点介绍了混沌粒子群算法的原理.由仿真结果可知混沌粒子群算法定位精度较高.传统三边测距法在锚节点较少时存在较大的平均定位误差，而本文研究的CPSO定位算法有效降低了定位误差.