基于RSSI的三维空间定位算法研究

王山　冯锋　王洪伟

摘要：在无线传感网络（WSN）的三维定位的过程中，由于实际环境的复杂性，会在定位过程中产生不稳定的接收信号强度（RSSI），同时还会导致无线传感网络中的未知节点产生不可靠定位数据，这些都会影响定位的精度。据此，本文提出了一种位置过滤算法，该算法首先利用高斯过滤模型对RSSI值进行过滤得到稳定的RSSI值，然后使用四面体质心算法计算得到未知节点的估计位置，最后结合DBSCAN算法对得到的估计位置进行过滤，从而剔除计算过程中获得的不可靠数据。本算法通过与传统的定位算法进行仿真对比，结果表明，本算法有效地提高了定位精度，对特定条件下的三维空间定位工程具有较强的借鉴意义。

关键词：WSN；三维定位；RSSI；估计位置过滤；DBSCAN

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2016）19-0221-04

Study of Three-dimensional Location Space Algorithm Based on RSSI

WANG Shan1， FENG Feng1， WANG Shong-wei2

（1.College of Mathematics and Computer Science， Ningxia University， Yinchuan 750000， China； 2.Engineering University of CAPF， Xian 710086， China）

Abstract： In the process of wireless sensor networks （WSN） positioned in three dimensional localization， due to the complexity of the physical environment， it will produce an unstable Received Signal Strength Indication （RSSI） during positioning， but also lead to unknown wireless sensor networks node generates unreliable positioning data， which will affect the positioning accuracy. Hereby， this paper proposes a position filtering algorithm， the proposed algorithm first using gauss filter model to filter the RSSI value and get the stability of the RSSI values， and then use the tetrahedron centroid algorithm to calculate the estimates of the unknown node position， finally combining with DBSCAN algorithm to filter the estimated location， thus to reject the unreliable data obtained from the calculation. Compared with the traditional positioning algorithm， the results show that the algorithm can effectively improve the positioning accuracy， and it can be used for reference in the three-dimensional space localization project under certain conditions.

Key words： WSN； three dimensional localization；RSSI； filter the estimated location；DBSCAN

1 引言

随着物联网技术的迅猛发展，无线传感网络（WSN）迅速成为21世纪最具影响力的技术之一[1]，由于无线传感网络综合了传感技术、网络传输技术、无线通讯技术、无线定位技术、数据融合技术、嵌入式技术等多种技术，使得WSN成为当今研究的热点。而无线传感节点的定位是支撑无线传感网络的核心技术[2]，在目标定位、目标跟踪、地理信息获取等方面发挥着巨大作用，因此对无线传感网络定位算法的研究具有重要的意义。

目前，无线传感网络定位在二维平面中的应用已非常成熟，但随着社会的发展，三维定位需求日益成明显，三维定位使得传感器节点呈现出立体分布，而非平面分布的特点，因此在平面上的定位算法已不能满足空间场景的定位需求。为了解决上述问题，人们提出了基于三维的节无线传感网络定位算法。无线传感器网络中的定位方法较多，可以根据数据采集和数据处理方式的不同来进行分类。在数据采集方式上。算法根据需要对采集的数据有所侧重，比如角度、时间、周围节点信息等，其目的是采集与定位相关的数据。在数据处理方面，不管数据时被自身节点处理还是上传到其他设备上处理，其结果是将数据转换为定位坐标，从而完成定位。 其中依据距离测量与否算法可划分为两大类：基于测距的定位和与距离无关的定位。目前，在测距的定位算法中基于接收信号强度（RSSI）的定位是研究的热点。相对于与距离无关的定位方法，基于RSSI的定位方法增添了额外的通信链路质量信息，并且获取简单，对于定位精度的提高具有一定的作用。

RSSI通过比较发射结点发送信号强度和接收结点接收信号的强度，再考虑信号在传播过程中的损失，使用理论或者经验的信号传播模型将传播损耗转化为发送节点和接收节点的距离[3]。在实际应用环境中，由于复杂的环境中的多径干扰，非视线关系等因素，该方法的定位精度不高。但由于这种基于RSSI的测距技术，具有方法简单、成本低、效率高、设备少、距离远等优点，因此，许多定位算法都结合了RSSI技术[4]。

2 相关研究

基于RSSI理论的研究已经比较成熟，根据无线电传播理论，无线电信号在传播过程中会有能量损耗，这种损耗与无线电传播路径相关，测距模型正是基于这种相关性从而得出待测节点到参考点之间的距离，在实际环境中，由于多径衰落、反射以及扰射、不规则传播等因素，使得模型比较复杂，同时使得定位误差较大。目前普遍使用的统计模型[5]如下：

式1中d为距信号源的距离，单位一般为km；d0为参考距离，P（d）为在距离d处的信号强度值，np为路径衰减因子，一般取值为2～4，环境不同取值不同。室内环境通常取1.4～1.8，P0是在参考距离d0处的信号强度（dBm）。由于式1参考模型的理论环境与复杂的实际环境有较大的差别，使得无线电传播路径损耗在一定的程度上与理论值相比并不吻合，这就使得实际测量存值存在误差。通常基于RSSI技术的定位机制使用各种算法来减少测距误差对定位的影响，其中包括多次测量、循环定位求精等算法。

由于无线传感网分布的地理位置及环境复杂多变，无线信号会受到环境的各种因素影响，导致接收节点接收到的信号，并不是全部对定位有帮助，有时会增大误差，所以对接收的信号进行预处理就显得很有必要了。通过RSSI距离模型可知，当未知节点距离锚节点越近，接收到的RSSI值波动越小（最大值和最小值之差越小），说明由RSSI值计算得到的距离越接近实际距离。当未知节点距离锚节点越远，由于实际环境的多径效应使得测得的RSSI值波动变大，导致误差也大。为了消除较大波动值对定位的影响，我们首先将周围锚节点的RSSI值聚集起来形成一个数据集，并且从大到小排好序。数据集形式如下：

我们从数据集中选取RSSI值较大的锚节点，进行多次RSSI值采集，记录，结合高斯滤波模型，舍去波动较大的RSSI值，最后对于收集到的N个该锚节点RSSI值取算数平均数作为该锚节点的最终RSSI值。表达式如下：

在进行定位时，如果待测节点与锚节点的距离已知，则至少需要4个不位于同一个平面内的参考节点才能唯一确定待测节点的坐标值，否则无法进行定位[6]。我们假设这4个锚节点的坐标为Pi=（xi，yi，zi），i=1，2，3，4；待测节点到4个锚节点的距离为di，i=1，2，3，4，根据三维空间两点间距离公式有：

方程组中四个方程三个未知量，那么就可以确定未知节点N（x，y，z）的坐标：

根据以上理论基础，许多学者对三维定位方法做了深入的研究。例如，文献[7]提出了坐标四面体质心定位算法，该算法比传统算法定位精度要高。文献[8]提出了一种利用四面体质心算法替换三维APIT算法的网格扫描法。文献[9]提出了一种基于多次测量提高定位精度的思想等。但是目前的这些研究对于由客观或主观因素会产生不可靠数据的情况，都未涉及，因此，本文提出一种基于估计位置进行过滤的改进定位算法。

3 基于估计位置过滤的改进定位算法

3.1 估计位置过滤

在三维空间定位过程中通常需要布置较多的锚节点，所以对于某个待定节点周围存在多个1跳参考点，由相关研究的理论可知对于任意四个锚节点都能计算得到一个估计位置，所以在计算的结果中会有多个估计位置，譬如，当周围环境中有10个锚节点时，取其中4个作为参考节点，那么就会有C104=210种取法。对于位置的估计，由于存在一些主观因素和客观因素，如选取节点不合理、数据传输错误等。存在某些明显已知的错误，使得这些估计位置对定位精度影响较大，所以对这些位置需要屏蔽过滤，以提高定位精度。对于多组估计位置，如果很多估计位置比较集中，而少数估计位置距离群体比较远，则可以认为这几个少数位置是不可靠的，因此可以剔除掉，其他的位置则认为是可靠位置点。如图1所示，假如对一个位置估计得到如下六个估计位置（A，B，C，D，E，F），由图中可以看出A，B，C，D，E五个位置较为集中，而F这个位置距离群体较远，如果将这六个点求平均值作为未知节点的最终估计位置的话，会造成误差较大，因此将F剔除，仅对A，B，C，D，E五个点进行算术平均运算，结果作为未知节点的估计位置。

其中对于只有两个估计位置的点不采取位置过滤，取这两个估计位置连线的中点作为节点的最终估计位置。

对于估计位置较多的，本文采用DBSCAN（Density-Based Spatial Clustering of Applications with Noise）算法，DBSCAN[10]算法是一种基于密度的聚类算法[11，12]，它将簇定义为密度相连的点的最大集合，能够把具有足够高密度的区域划分为簇，并可在噪声的空间数据库中发现任意形状的聚类，所以该算法可以有效识别噪声，即不可靠位置。

DBSCAN具体算法描述如下：

（1）检测数据库中尚未检查过的对象p，如果p为被处理（归为某个簇或者标记为噪声），则检查其邻域，若包含的对象数不小于，建立新簇C，将中所有点加入C；

（2）对C中所有尚未被处理的对象q，检查其邻域，若中至少包含个对象，则将中未归入任何一个簇的对象加入C；

（3）重复步骤2），继续检查C中未处理的对象，知道没有新的对象加入当前簇C；

（4）重复步骤1）～3），直到所有对象都归入了某个簇或标记为噪声。

输入数据：数据对象集合D，半径Eps，密度阈值MinPts

输出数据：聚类C

从算法中我们可以看出DBSCAN算法通过检查数据库中每个点的Eps-邻域来寻找聚类。如果一个点P的Eps-邻域包含多于MinPts个点，则创建一个以P作为核心对象的新簇。然后，DBSCAN反复地寻找从这些核心对象直接密度可达的对象并加入该簇，直到没有新的点可以被添加，该过程结束。

由于该算法可以有效地去除噪声即不可靠数据，因此DBSCAN算法能够很好的应用到空间位置过滤中去除空间不可靠数据。

3.2 改进后的定位算法

1）锚节点周期性发送自身信息：节点ID、自身位置信息。

2）待测节点接收其通讯范围内的所有节点的信息，并记录他们的RSSI值，建立从大到小的RSSI数据集，选取通讯RSSI值较大的锚节点进行多次通讯测值，并运用高斯滤波，舍去波动较大的RSSI值，得到N组 RSSI值取其算术平均值：

作为该锚节点的最终RSSI值。

3）如果未知节点接收到的锚节点的个数N<=3，则执行5）。否则随机选择一组锚节点组成四面体，并根据三维APIT算法判断未知节点是否在四面体中。如果不在则舍弃，如果在则记录这组锚节点并重复该过程，直到选取次数大于一个阀值M。

4）由3）得到四面体后，运用四边测量算法来对集合中的所有组合计算坐标位置。对计算得到N组坐标值过滤，对于只有两个估计位置的点不采取位置过滤，取这两个估计位置连线的中点作为节点的最后估计位置。对于估计位置较多的点，采用DBSCAN算法，选取集合最大的所有数据进行计算平均值作为最终坐标估计值。

5）若未知节点接收到的锚节点个数N<=3或者四面体集合为空，则对所有锚节点采用RSSI均值加权质心算法来进行未知节点估计。对于接收到P个锚节点信号，相应的RSSI的值为R1，R2，...，Rp，则第i个锚节点的加权系数为那么RSSI均值加权算法估计坐标为：

3.3定位误差

定位误差公式：

4 仿真试验

为了比较本文改进的定位算法和传统定位算法的性能，利用MATLAB建立了一100m×100m×100m的仿真环境，锚节点均匀地分布在这个范围内，在数据中添加方差为20、均值为3的随机噪声，用来模拟现实环境的影响。500个定位结果是在相同的环境下运行50次试验的平均值，部分区域仿真结果对比如图3、图4所示：

由图3和图4的仿真结果对比可以看出，由于在实际应用的环境中会出现节点异常或者环境异常带来的不可靠数据，会对系统定位精度产生影响，我们通过对采集的RSSI值过滤和估计位置进行过滤，定位结果要比未进行位置过滤和RSSI值高斯过滤的误差要小，提高了定位精度。

如图5所示，在锚节点小于10个的时候本文算法定位精度明显优于传统算法，这是因为锚节点较少时环境误差对定位精度影响较大，造成了传统算法的定位不精确，而本文所提出的改进算法具有明显的优点。但随着锚节点个数的增加两种算法的精度都在不断提高，这是因为随着锚节点的增加，由于最后取几何均值使得环境误差数据对总的定位结果影响较少，所以定位精度就得到了提高。

图6给出的是定位误差随通讯距离变化的趋势。由图中可知随着通讯距离的增加，传统算法和本文算法的定位误差都减小。因为增加节点的通讯距离后，会使距离估计更加接近节点间的欧氏距离。

由以上结果分析可知，在定位过程中节点的噪声数据会影响定位的精度，本文在质心定位算法的基础上先通过对RSSI值进行高斯过滤从而优化了采集的RSSI值，保证了入口数据的准确性和稳定性。然后对计算结果进行基于DBSCAN算法的估计位置过滤，通过仿真结果可以看出该算法有效的减少了不可靠数据对定位的影响，提高了定位精度。

4 总结

本文在研究了传统的三维定位算法的基础上，提出了一种估计位置过滤算法。该算法通过高斯过滤模型对采集的RSSI的值进行过滤得到稳定的RSSI值，然后对待定位的节点进行估计位置过滤，去除了在定位过程中由于主观或者客观因素带来的不可靠位置，减少了其对定位精度的影响。文章通过仿真对比了本文算法和传统算法在定位精度上的优劣，由对比结果可知本文算法在定位精度上有了明显的提高，能够有效的减少实际应用中随机噪声对定位的影响，该算法在三维定位中有着较大的应用潜力。

参考文献：

[1] SUOMELA J. Computational complexity of relay placement in sensor networks[J]. Lecture Notes in Computer Science， 2006， 3831：521-529.

[2] KIM S， KO J G，YOON J， et al. Multiple-objective metric for placing multiple base stations in wireless sensor networks[A]. Proc of the 2rd International Symposium on Wireless Pervasive Computing[C].Pis-cataway，USA，2007：627-631.

[3] Zhang Jie， Wu Ling-xi，Tang Zhi-jun. Ranging Method and Accuracy Analysis Based on RSSI of Wireless SensorNetwork[J].Telcommunication Engineering，2010，50（4）：83-87

[4] WU Jie，FENG Feng，DING Zhi-yi Research on coal mine underground localization algorithm based on integration of RFID and WSN[J].Computer Engineering And Design.2014（7）：2278-2282.

[5] SHEN X， WANG Z， JIANG P， et al. Connectivity and RSSI based localization scheme for wireless sensor networks[J]. Lecture Notes in Computer Science， 2005， 3645（2）：578-587.

[6] Laitinen E， Lohan E S， Talvitie J， et al. Access point significance measures in WLAN-basedlocation[C]//Positioning Navigation and Communication （WPNC）， 2012 9th Workshop on. IEEE，2012：24-29.

[7] Chen Hong-yang， Huang Pei， Martins M. Novel Centroid Localization Algorithm for Three Dimensional Wireless Sensor Networks[C]//WiCOM'08 4th International Conference on Wireless C'ommunications，Networking and Mobile Computing. 2008：1-4

[8] Liu Zhuang，Fang Zhi-yi，Ren Nai-ji. A New Range-Free Localization Algorithm Based on Annulus Intersection and Grid Scan in Wireless Sensor Networks [J].Journal of Information and Computational Science，2012，9（4）：831-841

[9] VIANI F， LIZZI L， ROCCA P， et al. Object tracking through RSSI measurements in wireless sensor networks[J]. Electronics Letters， 2008， 44（10）： 653-654.

[10] ESTER M， KRIEGEL H， SANDER J， et al. A den-sity-based algorithm for discovering clusters in largespatial databases with noise[C]// Proc of the 19962nd Int' l Conf on Knowledge Discovery and DataMining.Portland： AAAI Press， 1996：226-231.

[11] QIAN Wei-ning， GONG Xue-qing， Ao Ying-zhou.Clustering in very large databases based on distanceand density[J]. Journal of Computer Science and Technology， 2003， 18（1）： 67-76.

[12] ZHOU Shui-Geng，ZHOU Ao-Ying，CAO Jing.A fast densite-based clustering algorithm[J].Journal Of Computer Research And Development.2000，37（11）：1287-1292.