基于改进型加权质心算法的井下人员定位

杨 鹃，韩雪松

(承德石油高等专科学校计算机与信息工程系，河北 承德 067000)

基于改进型加权质心算法的井下人员定位

杨 鹃，韩雪松

(承德石油高等专科学校计算机与信息工程系，河北 承德 067000)

节点定位技术可用于井下人员位置的确定，在日常作业监控和人员调度中起到非常重要的作用。采用无线传感网络的通信技术，基于传统加权型质心算法，添加了区域判定的改进型定位算法，设计了井下人员定位系统。为验证算法的有效性，用matlab软件模拟仿真了算法的执行，结果表明能够提高系统的定位精度，可用于复杂工作环境的井下监控系统中。

无线传感网络;节点定位;定位算法;

无线网络节点定位技术设计主要包括两方面的内容:锚节点的布置和定位算法的选择。无线传感器网络节点自身都有接收信号强弱指示功能(RSSI)，节点间可定时发送/接收信号帧，节点的位置由唯一标识的地址表示［1-2］。无线网络定位系统可用现有的设备发送和接收RSSI信号，无须添加额外的设备，实现起来较为容易。然而煤矿井下巷道中，矿井环境非常复杂，电磁波信号衰减严重，路径损耗无法实现准确计算，不适用于采用单一的RSSI测距技术。本文在加权型质心定位算法的基础上，改进了算法的后期计算工作，有效的提高了定位的精度，是井下节点定位中比较可行的方法。

1 定位方案

定位方案分为固定锚节点和移动锚节点两种形式，采用位置已知的锚节点进行定位，通常锚节点的数量与定位的精度是成正比的，定位精度要求越高，需要的锚节点的数量就要求越多，本文设计的定位系统主要针对于井下人员的定位，井下工作环境非常复杂，通信干扰较多，且信号传输的过程中多径衰落现象严重，不利于信号的远距离传输。主要是由于以下原因造成的:

1)井下内部安放了多种机电设备、运输导轨，煤和矸石随处可见，空间内部相比于室外狭窄许多。

2)墙壁、空气中的粉尘颗粒以及空气中的水分都会吸收电磁波，其中湿度对电磁波损耗的影响最大，电磁损耗会随着湿度和电磁波频率的增加而严重增加［3］。巷道墙壁不平、粗糙会造成电磁波的路径损耗，出现多径衰落现象，电磁波传输损耗大。

3)巷道路径复杂多变，弯道和岔路会造成信号的反射、衍射，造成接收信号的误差。

4)机电设备的使用使得巷道内部噪声较大，且电磁波信号在巷道壁的反射和折射也会造成接收信号里包含了许多的干扰信号，电磁干扰过大。

井下复杂的工作环境显然不适宜采用移动的锚节点进行节点定位，故本文采用固定锚节点的方式进行节点定位。由于井下环境的复杂多变，考虑到耗电的问题，运算复杂的定位方法不易采用。传统的加权型质心算法，其运算简单，系统耗电量低，适用于井下的定位工作。

2 定位算法

2.1 加权型质心定位算法

无线网络系统中锚节点定期向外发送信号帧，未知节点接收到该信号帧后，两者之间可实现网络通信。传统的质心定位算法［4-5］是一种免测距的算法，将与未知节点实现网络通信的锚节点的位置组成多边形，取该多边形的质心作为算法的位置估计，该算法的执行取决于网络的连通性和节点间的距离大小。与未知节点通信的锚节点的数量越多，定位的精度越准确。节点间不需协调，网络拓展易于实现。为提高定位精度，往往要增加系统锚节点的个数，减少锚节点间的距离，这会造成系统成本的大幅度的增加。并且质心定位算法适用于网络节点分布均匀的环境下，这样计算的定位误差较小，否则定位误差会大大增加。为了解决这一问题，加权型的质心定位算法应运而生，该算法将节点间的距离的倒数作为计算的权值添加到计算公式中，将节点间距离的影响体现到具体的计算中，提高了算法的定位精度。锚节点距离未知节点的距离越近，其对未知节点的坐标的影响越大，因而将节点间的距离值的倒数作为质心定位算法的偏移权值。加权的质心定位算法的计算公式如(1)。

式中，xi和yi作为锚节点的di坐标，为锚节点和未知节点的距离值，x、y作为质心定位的估计坐标点。

2.2 RSSI测距技术

质心型定位算法中的距离值需要采用RSSI测距技术来确定。RSSI测距技术的核心思想是锚节点向外发射已知信号强度的信号，未知节点接收该信号，根据接收到的信号强度和系统环境的路径损耗来计算未知节点的距离。各未知节点接收锚节点信号时的信号强度如公式(2)。

其中路径损耗是与无线网络的工作环境相关的，现有的路径损耗的方法有经验法和曲线拟合法。经验法需要对未知环境的估计足够准确，事实上往往偏差很大。曲线拟合法往往要对实际环境进行测试，再经过计算获得实际的路径损耗，计算量很大。

考虑到井下环境的复杂性，本系统的RSSI与距离的公式计算采用遮蔽型，如公式(3)。

式中:λ—路径损耗系数，一般取2～5;ξ—随机数，符合高斯分布，平均值为0，其标准差一般取4～10;d0—参考距离;d—估计距离;Pr(d0)—参考距离的接收信号强度;Pr(d)—估计距离的接收信号强度;

2.3 定位算法的设计

在加权质心算法的基础上，很多文献根据应用的需求提出了不同的改进方法。文献［6］提出了一种基于RSSI修正的算法，该算法在首先利用RSSI算法取得未知节点的估计坐标后，重新计算估计坐标到锚节点的距离值，根据再将测距技术获得的未知节点与锚节点之间的距离值相比较，校正节点位置。对通信半径内的所有锚节点的估计坐标进行修正，再将修正后的坐标采用质心算法进行计算。文献［1］提出了选用锚节点定位最近的四个锚节点进行质心定位算法的定位，该方法锚节点密度越大，定位精度越高。文献［7］提出了多质心定位算法，该算法首先将网络当中的信标信号得到的广播信息值排序R-set={RSSI1，RSSI2，…RSSIn}转化成距离排序信号集合D-set，求出距离值与最小的距离值的差值集合△d-set，求取△d-set集合的平均值，将锚节点大于平均值的节点集合距离集合中取距离值相差最小的三个节点，用传统的质心心算法计算出该锚节点的三角形坐标。将新产生的锚节点与距离值小于平均值的锚节点组合成多边形，再用加权质心算法计算出新的未知节点的坐标。该算法的使用要求锚节点的数量较多，增加了系统的成本。

根据现有文献的技术，本文考虑到井下环境的复杂程度，将加权型质心算法的进行采用区域改进型的后期处理，求取定位最小误差，找到最优的定位点。区域改进型的加权质心定位算法具体的过程如下所示。

1)锚节点定期地向周围发送信号，包括信号强度和ID编号。

2)未知节点接收周围锚节点发送的信号，确定周围与之具有网络连通的锚节点以及其发送到未知节点的RSSI信号值，建立未知节点与锚节点的RSSI值的组合R-set:(R1，R1，…，Rm)，以及按照RSSI组合的顺序建立的与未知节点连通的锚节点的序号集合M-set:(m1，m2，…，mm)以及锚节点的位置集合 X-set:(x1，x2，…，xm)，Y-set:(y1，y2，…，ym)。将 R-set、X-set和 Y-set代入加权型质心算法的计算公式，求取未知节点的估计点坐标O(x，y)。

3)建立未知节点的估计区域，以O点为中心，0.5ξR为坐标的边界，如图1所示。本系统默认的模拟仿真运算中，将0.5ξR设定为1。

4)本定位算法的设计中定位误差计算如公式(4)。

式中di代表未知节点与锚节点间的实际距离，d'i代表估计坐标与锚节点间的距离值;仿真计算时，d'i由节点间的距离值表示，di根据RSSI信号发送和接收的公式，计算求得。分别求取O点以及估计区域顶点与锚节点序号集合的锚节点的定位误差，分别由ΔO、Δ1、Δ2、Δ3、Δ4表示。如果ΔO＜=min(Δ1，Δ2，Δ3，Δ4)，则认为该估计坐标为最小误差的定位点，O点坐标为最终的估计坐标值，结束此次判定。如果 ΔO ＞min(Δ1，Δ2，Δ3，Δ4)，则判定 O 点为非最佳定位点，选择 Δ1，Δ2，Δ3，Δ4 的最小点作为新的估计坐标点O，按照图1重新进行估计区域的确定，重复执行上述的过程。根据系统误差的情况，可设定重复执行的循环阈值，超过阈值大小，则退出循环执行的操作，将当前的估计坐标点作为定位坐标的结果，本文设定循环阈值为5。

3 仿真设计

3.1 仿真环境的设置

为了验证算法的有效性，采用MATLAB软件对算法进行仿真。假设将网络设置于100 m×10 m的区域内，该区域的左下角坐标(0，0)，区域内采用无线载波信号频率为2.4 GHz，节点的通信半径理论上设定为18 m，实际中由于路径损耗的原因，大约12米左右。为了验证算法的有效性，实际作业中的电磁干扰、电磁波反射和折射、湿度的干扰以及气候的影响由均值为0，标准差为5的高斯分布的随机噪声表示。锚节点的布局如图2所示。

3.2 定位精度的比较

1)不同定位算法的定位精度的比较。该精度的比较的仿真环境采用图2的布局方式，相同横坐标的锚节点间的距离相差为10，不同横坐标的锚节点间横坐标相差为5。随机选定未知节点的坐标，固定横坐标的大小，调整纵坐标的值比较不同的定位算法在不同的坐标下，定位误差的变换情况。比较的结果如图3所示。区域改进型的定位算法相比于加权型定位算法在定位误差的准确度方面有了较大的提高，并且从曲线变换情况看，加权型质心算法的定位误差与未知节点的未知有很大的关系，两侧误差值较大，已经达到了18%左右，而在中心位置的误差却较低，大约在3% ～8%左右。区域改进型的算法，从曲线的变换情况可以看出，定位误差最大大约有9%，最小可达到3%左右，定位精度的提高是比较明显的。两种质心算法的定位误差有一部分曲线是重合的，这说明在此坐标点上首次估计的未知坐标点就是最小误差点，所以定位误差大小是一致的。

2)定位距离对定位算法的影响。采用区域改进型的质心定位算法，调整锚节点间的定位距离，观察定位误差的变化情况。以锚节点间的横坐标的大小表示锚节点的距离，比较的结果如如图4所示。节点距离的调整对于定位误差的影响并没有明显的体现出来。本系统设定的实际通信半径大小为12，在任意的一个未知节点的定位过程中，与之通信的锚节点的个数至少为3个，这就保证了算法的准确程度，所以距离为5和距离为10的定位结果并没有较大的出入。如果将锚节点间的距离设定为15，则定位误差会大大增加，这是由于与之通信的锚节点的个数有时会少于3个。故在本算法的定位设计中，在保证与未知节点通信的锚节点个数不低于3个的情况下，选择最大的距离值布局锚节点的位置，提高系统的性价比。

4 总结

本文在加权型质心算法的基础上，改进了算法的处理过程，添加了区域估计，比较最小误差，寻求最佳的定位估计点。由定位的仿真结果图可以看出定位误差大大的减少了，适用于环境复杂的井下作业。

［1］于慧霞.WSN中基于RSSI的加权质心定位算法的改进［J］.电子测试，2012(1):28-32.

［2］郭秀才，滕以金，窦美玲.井下人员定位跟踪检测系统［J］.兵工自动化，2009，28(4):58-63.

［3］蔡翠翠.矿井无线通信的抗多径关键技术研究［D］.合肥:安徽理工大学，2012.

［4］陈茂聪，田华.移动无线传感器网络定位算法研究［J］.通信技术，2011，44(6):70-75.

［5］R.Behnke，D.＂fimmermann，“AWCL:Adaptive Weighted Centroid Localization as anefficient improvement of coarse grained localization，”5th Workshop on PositioningNavigation and Commumcation，PP.243-250，March 2008.

［6］王伟，陈岱，周勇.基于测距修正和位置修正的RSSI定位算法［J］.计算机工程与设计，2011，32(2):409-415.

［7］刘京.WSN中质心定位算法和基于移动锚节点的定位算法研究［D］.郑州:郑州大学，2008.

Underground Personnel Positioning Based on Improved Weighted Centroid Algorithm

YANG Juan，HAN Xue-song

(Department of Computer and Information Engineering，Chengde Petroleum College，Chengde 067000，Hebei，China)

Node location technology can be used to determine the mine personnel position，which plays a very important role in job monitoring and scheduling.This article adopts the communication technology of wireless sensor network.Based on the traditional weighted centroid algorithm，the improved localization algorithm is added to determine area.Mine personnel positioning system is designed in this article.To verify the validity of the algorithm，the paper uses matlab software to simulate the process，the compared result shows that the algorithm can improve the positioning accuracy of the system，and we can use it in the complex working environment of mine monitoring system.

wireless sensor network;node localization;positioning algorithm

TP216

A

1008-9446(2014)04-0057-04

2013-12-25

杨鹃(1979-)，女，黑龙江双鸭山人，承德石油高等专科学校计算机与信息工程系讲师，控制理论与控制工程硕士，研究方向为信息融合与无线网络。