无线定位算法的学习笔记

1、无线传感器网络中定位算法的学习笔记Author: Jian ZouAdvisor: Prof .Jianxia Chen摘 要: 无线传感器网络(wireless sensor network,简称WSN)，是一种比较新的信息获取和处理技术，它能够在很多应用领域上实现复杂的监测和跟踪任务，对目标物体进行实时定位。与传统的基于终端定位方式不同的是，基于终端的定位是指移动终端根据基站和服务器所提供的信息进行定位，比如全球卫星定位技术（Global positioning satellite，简称GPS），而基于WSN的定位是根据定位网络所测得的数据来计算目标物体的位置信息，主要分为测距定位和测向定

2、位，其中在测距定位的基础上产生了很多种定位算法，比较经典的有RSSI，DVhop，TOA，TDOA，最近邻居算法等，基于测向的算法有AOA算法，以及包括在AOA算法基础上进行改进的基于神经网络的AOA定位算法等。在这些算法中，RSSI（Recept Signal Strength Indication，接收信号强度指示，简称RSSI）算法由于其低成本，低复杂性的优势被广泛应用到各个领域，但是由于信号强度很容易受影响（比如天气，障碍物等）导致定位精度会有所影响。因为RSSI算法的优势，所以在RSSI算法上寻求一种能提高定位精度的方法很有必要，现阶段我主要是通过大量阅读相关期刊文献，弄清

3、楚算法理论的基础上，能够产生自己的思想，找到一种低成本投入实现高精度定位的算法，并能在仿真平台上去验证自己的思想。关键词:WSN 定位 RSSI 精度 1.关于RSSI算法的介绍RSSI算法是指根据无线传感器接受到（目标物体）的信号指示强度，计算该信号在传播中的损耗，根据理论或者经验的信号传播模型将信号强度转换成距离。但是这种算法很容易受到天气，障碍物或人员流动的影响，导致测距不精确，从而定位精度不高。但是由于RSSI算法简单，成本低廉，很多无线通信模块提供RSSI值，所以RSSI算法依然应用在众多领域中。下面给出了RSSI算法的模型和理论公式；R(d0)R(d)d1d图1.基于RSSI的测距

4、模型上图中，R（d）表示目标物体在距离阅读器d处的信号强度，R（d0）表示参考物体在距离阅读器d0处的信号强度，根据信号损耗的理论模型，可以得到公式（1）： （1）其中n是一个信号衰减指数，一般根据具体的环境情况而设定，属于经验值，一般取（2,5）之间，根据公式（1），我们可以求出距离d，见公式（2）： （2）其中参考物体的坐标已知为（x0，y0），两个阅读器的坐标（x1,y1）,(x2,y2),假设目标物体的坐标（x，y），可以列出下面的式子：（3）（4）根据（3），（4）就可以求出目标标签的坐标值。下面将介绍2篇关于改进的RSSI算法的研究。2.阅读关于改进的RSSI定位算法的期刊文献后的

5、笔记2.1.Paper ITitle:无限网络定位技术研究（第21卷，第10期，2011年，计算机技术与发展）文章摘要：这篇文章主要针对RSSI定位算法的距离值容易受影响而导致定位精度低的问题，提出了在RSSI定位算法的基础上，通过高斯滤波的方法优先选取RSSI值的策略，并融入了加权质心算法，以保证定位定都的提高。改进的算法在相应的实验环境下得到了验证，改进后的算法的定位精度得到了改善。关键词：RSSI Gaussian Filters weighted centroid(1).文中改进的RSSI算法流程图2.改进的RSSI算法流程(2).高斯滤波寻找最优的RSSI值首先定义在某段时间内，信号

6、接收器接收到未知节点的n个RSSI值，由于这n个RSSI值是随机离散的变量，则这些值服从或近似服从高斯分布（正态分布），选取那些高概率，即分布密度比较大的区域（一般经验值位大于等于0.6的区域），测量结果关于x的密度函数f(x)如下公式所示： （5）其中，u是这n个RSSI值的几何平均值，是标准差，具体表达式如下： （6） （7）经过高斯滤波后，选取范围在0.15+u,3.09+u范围内的RSSI值，对这些RSSI值进行几何平均，就可以得到某未知节点在一段时间内的RSSI值。根据上面的RSSI的传播损耗模型，就可以估算出未知节点距离接收节点的距离。(3).采用三边测量法来确定未知节点的坐标理想

7、的三边测量法的模型：已知三个接收器节点A(x1,y1)，B(x2,y2)，C(x3,y3)，通过接收器接受到未知节点(x,y)的RSSI值Ra，Rb，Rc，根据上面的RSSI测距模型和公式可以将Ra，Rb，Rc信号强度值分别转换成距离R1，R2，R3，并且能够构成以A，B，C为圆心，R1，R2，R3为半径且相交于未知节点的三个圆，根据几何特性，可以求出未知节点（x，y）的坐标值： (8）图3.理想的三边测量法模型一般的三边测量法模型：上图中的理想模型在实际应用中往往是不存在的，一般的模型如下图所示：图4.一般的三圆相交情况对于M点（Xm，Ym），可以根据下面公式算出M点坐标： （9）同理，N（

8、Xn，Yn），E（Xe，Ye）的坐标也可以确定，听过三角形质心算法就可以确定未知节点D的坐标,即D（x，y）=D（10）但是，为了提高精度，文章提出了一种加权质心定位算法。(4).加权质心算法对于四个接收器节点A，B，C,F,它们的坐标位置已知，现在利用这4个已知节点来求未知节点D的坐标位置，每次从A，B，C，F四个节点中选择3个，通过上面的三角质心算法可以确定未知节点的4个坐标信息D1（x1,y1），D2（x2,y2）,D3（x3,y3）,D4（x4,y4）通过求平均值来求得未知节点D的坐标，其中引入了加权因子，该加权因子是每次选取的三个节点的半径之和的倒数，如下式所示： （11）最终得到的

9、未知节点的坐标信息为D（x，y）为，如下式所示： （12）(5).文章作者在Window平台上，用C+语言实现了该算法。实验环境包括笔记本电脑一台，装有wpa_supplicant用于接收信号强度，AP三个，USB接口TPLINK无线网卡一块。wpa_supplicant获得周围的无线信号强度后，根据筛选出的RSSI值定位。根据作者的实验数据可以看出，基于过滤的RSSI值结合加权质心算法来定位确实提高了定位精度。2.2 Paper IITitle：无线传感器网络中基于聚类平均的定位算法计算机应用与研究，2010年4月文章摘要：这篇文章主要是针对RSSI定位算法中RSSI由于在传播过程中的损耗，

10、导致定位精度不高的问题，提出了在信号强度值在传播模式中的相似度原则进行聚类平均，通过仿真表明，改进后的算法定位精度提高，算法抗干扰能力强，特别适合锚点数量较少的环境。关键词：RSSI clustering anti-interference(1)当运动节点离开信源时，接收的信号强度会减少，如下图曲线所示，虚线是这段信号强度的均值；图5.RSSI的实测值和平均值RSSI的信号距离模型: 上面的式子中n是一个传播损耗指数，根据具体的环境而变化，如果简单的用这段RSSI的平均值作为测距的信号值，那么测得的距离将会存在很大的误差，因为距离信源越远，传播过程中，信号损耗越大，n值也会大。文章提出了一种可

11、行的思路：对处在相似因素影响环境下的多个节点组成的接受到的RSSI值进行聚类，对于形成的k个聚类群，对每个聚类群的n值进行统计分析，然后求出每个聚类群中的RSSI均值，最后再对这k个聚类群的平均值再求几何平均，得到一个比较优的RSSI值，作为最后测距的RSSI值，其中的n是从这k个n中求平均值得到。图6.聚类质心算法流程文章中对聚类的相似度测量采用的是夹角余弦测量法：（13）上面的式子中，表示节点A接受到节点B的RSSI值，RA i和RB i分别是节点A、B 从相同的N 个节点中第i个节点接收到的RSSI值;文章通过仿真结果表明，聚类平均法定位具有很好的定位效果，通过与RSSI质心法，RSSI

12、校验法等基于RSSI测距算法进行对比，该算法有明显的优势。仿真结果如下图:图7 各种算法定位误差分析文章中作者提出了后续的研究重点：该聚类平均算法是一种旨在消除复杂环境下衰落对RSSI值的随机性影响的基础性算法,聚类平均算法如何与更优的后续处理策略相组合有望产生更好的性能。 3.总结 通过上面2篇文章的学习，我觉得这2篇文章各有互补，paper I中采用的是高斯滤波的策略对RSSI值进行筛选，然后再对优选的RSSI通过测距模型，转换成距离，再通过三边测量法，加权质心算法来对未知节点定位，我认为在对RSSI进行优选阶段，其中涉及到的经验值太多，比如选取高概率p=0.6，0.15+u,3.09+u

13、的范围，这些值的选定都具有随机性。可以通过paper II中提到的聚类思想，对于随机离散的RSSI值，我们可以通过聚类思想把这些离散的变量聚成k个集合，对于这k个聚类群，我们可以得到这个群体内的RSSI损耗指数，通过损耗模型，我们可以求出每个RSSI对于的距离，最后通过对这个群体的距离进行几何平均，我们可以得到k个这样的距离值，最后再求平均值，就可以得到一个优化的RSSI值，然后利用加权质心算法就可以得到目标物体的坐标信息。 图8.聚类流程图假设对这些RSSI值集合已经完成聚类，聚类数目k（人为设定），即n个RSSI值已经被聚成k个聚类群体中，每个聚类群体代表了具有最大相似度的RSSI值，我们

14、可以计算出在这个聚类群体中的信号传播指数为（其中有k个n值）n=n1,n2nk，对每个聚类中的RSSI值进行求平均值： （14）代表某类中有m个RSSI值，然后利用信号距离模型：求出这个聚类群体中的距离di，最后对这k个距离值进行几何平均，可以得到一个比较好的距离值。Reference1 侯亚娜, 胡维平.无线传感器网络中基于聚类平均的定位算法J.计算机应用与研究,2010年4月.2 李丽,周彦伟,吴振强.无线网络定位技术研究J.计算机技术与发展，2011年10月3 方震,赵湛,郭鹏,等. 基于RSSI测距分析J. 传感技术学报,2007, 20 (11) ，252622530.4 王焱,单欣欣,姜伟.无线传感网络中移动节点定位技术研究J传感技术学报.2011年9月.5 朱晓娟,孟祥瑞. 基于加权质心的无线传感器网络移动节点定位算法J计算机工程与科学，2011年11月.6 安雷,张国