基于动态损耗因子和权重的改进质心定位算法

任晓奎 李锋 程琳

摘 要：针对无线传感器网络（WSN）节点的定位精度受环境和误差权重因子的影响问题，提出一种对路径损耗因子和误差权重因子动态修正的质心定位算法。前期根据实测和路径损耗模型，加权修正得出动态损耗因子;后期通过划分矩形区域，构造权重因子矩阵。首先，使用动态损耗因子，代入传统加权质心定位算法估算出未知节点的位置;然后，查询误差权重因子矩阵，确定最优权重因子，重新计算出未知节点坐标。实验结果表明，改进的算法降低了平均误差和最小误差，定位精度比普通质心算法提高了58%，比动态修正质心算法提高了21%，比动态加权质心算法提高了11%，定位精度有所提高。

关键词：无线传感器网络;定位;动态损耗因子;误差权重因子;动态修正

中图分类号： TP391.9

文献标志码：A

文章编号：1001-9081（2019）03-0824-05

Abstract： Aiming at the problem that the positioning accuracy of wireless sensor network nodes is affected by the environment and the error weight factor， a centroid positioning algorithm was proposed to dynamically correct path loss factor and error weight factor. At earlier stage， a dynamic loss factor was obtained by weighting correction according to the actual measurement and path loss model; at later stage， the weight factor matrix was constructed by dividing rectangular region. Firstly， the location of the unknown node was estimated by introducing dynamic loss factor into the traditional weighted centroid localization algorithm. Then， the error weight factor matrix was queried to determine the optimal weight factor. Finally， the unknown node location was recalculated. The experimental results show that the improved algorithm reduces the average error and the minimum error， and the positioning accuracy is 58% higher than ordinary centroid algorithm， 21% higher than dynamic correction centroid algorithm， and 11% higher than dynamic weighted centroid algorithm.

Key words： Wireless Sensor Network （WSN）; positioning; dynamic loss factor;error weight factor;dynamic correction

0 引言

目前，定位技術早已成为国内外研究的热点问题。在室外定位，各种导航系统已经完全满足定位精度的需要。但在室内定位方面，定位精度仍不理想。为此，各种室内定位技术被不断提出和发展。无线传感器网络（Wireless Sensor Network， WSN）技术设置灵活，且WSN定位技术[1-3]可以通过有限的已知锚点，进行未知节点的区域估算，结合彼此间的信息交换和各种算法的运行，确定未知节点的位置。WSN节点定位技术在研究领域已取得很大成果[4]。目前，常用的算法主要是质心定位算法以及质心定位算法的各种改进。其主要过程一般包括对距离的确定和对位置的估算。文献[5]使用等边三角形定位;文献[6-7]通过接收信号强度（Received Signal Strength， RSS）判断收发距离来进行定位;文献[8]通过优选定位节点，解决了通信半径和定位精度相矛盾的问题;文献[9]和文献[10]都是根据信标节点对未知节点的不同影响力，确定加权因子，并优选信标节点。这些都是利用RSS转化成距离来进行定位，没有充分利用每个节点接收的强度。文献[11]针对以上缺点，将RSS进行卡尔曼滤波，并利用皮尔逊相关系数作为权重，使定位精度得到提高;文献[12]为了提高精度，通过高斯滤波然后进行定位等。还有一些文献研究安装天线的类型对室内定位的影响，如文献[13]采用定向天线，利用信号强度差定位;文献[14]改进文献[13]，同样利用定向天线，但扩大了定位面积。

而在对模型参数进行改进的过程中，文献[15]中提出了一种基于卡尔曼和线性插值滤波的改进三角质心定位算法，但也仅仅通过测量固定的1m处的接收功率A和路径损耗因子n的值进行定位;文献[16]提出了一种基于RSS路径损耗因子动态修正的算法，有较好的定位效果，但在算法后期定位过程中仍是利用普通的质心算法;文献[17]使用动态权重因子，但在测距阶段没有考虑到路径损耗因子的动态变化。

针对文献[16]和文献[17]的不足，本文提出了一种动态修正的质心定位算法。在接收到信号强度RSS后，先经高斯滤波，通过已知距离d测出实际RSS值与n的关系，进行一定的运算，求出动态n值;然后再与改进的加权质心算法结合，即在不同区域选用不同的权重因子a，结合两种方法的优点，从而使定位更加精确。

1 质心定位

1.1 路径损耗模型

在进行室内定位的研究中，通常使用以下室内路径损耗模型来进行测距。即：

为了表示方便，将r仍改为d计算。

1.2 高斯滤波

由于在室内传播时，信号不稳定，在同一位置的RSS值具有随机性，为了减小误差，必须对原始信号进行滤波处理。在对RSS进行滤波时，有许多优化方法，常用的有均值滤波、高斯滤波和卡尔曼滤波。在实际的应用中，当距离较近时，三者滤波效果相差不大，但超过一定界限，高斯滤波的效果较好。

高斯滤波过程如图1所示。

2）选取概率较高值的集合：

通常为了去除相对误差较大的数据，会加入约束条件，在概率论中当概率大于0.5而小于1时为大概率事件，可以保留，本文取0.6，即将大于0.6的RSS提取出来，放入集合RGAUSS[i]：

1.3 质心定位

在数学计算中，只要知道三个已知端点的位置，以及各端点到未知节点的距离长度，如图2，就可以利用式（8）计算出未知节点的大概位置。

但因各种环境因素的影响，路径损耗模型并不一定完全匹配，因此所求出的未知节点与实际位置有一定的误差，如图3所示，未知节点并不处于A、B、C三圆交点。为此，各种加权质心算法的提出就是为了减小估算位置与实际位置的误差，以下为一般质心算法式（9）：

但普通的质心定位中，并没有考虑距离远近对定位结果的影响，因此在普通的质心定位算法的基础上进行改进，提出各种加权质心定位算法。其中以距离和倒数的加权质心算法较为常见，如式（10）：

2 算法改进

本文实际是对文献[16]和文献[17]的改进。文献[16]使用动态损耗因子后，使用普通的质心算法进行定位，因此使用普通的算法这一步还可以进行改进;文献[17]在初次定位计算初次未知节点M时，使用一般的静态损耗模型后，再进行动态权重计算，因此在使用损耗模型这一步可以进行改进。本文的改进实际上是在前半部分使用动态损耗因子来确定路径损耗模型，而后在定位阶段使用动态权重方法。

2.1 动态损耗因子n的选择

方法步骤：

1）在相同距离单个参考点1m不同角度测出信号值N组，经高斯滤波式（6）后，代入式（7），取其均值为A。

2）同样方法在距离为2m、3m等一直到10m（实际可根据现场选择）的距离值测出信号强度RSS，根据不同的距离下的RSS值代入距离损耗式（3），其中A为1m处的信号强度，求出不同的固定n值，并将其列入表1中，表1中RSS/dBm表示接收的信号强度，nd为距离为d时的路径损耗因子。

3）令在未知点所测的RSS信号强度为R0，对照表1中RSS值Ri，代入式（11）中，求出动态的n值，从而求出距离d。

2.2 动态权重a的选择

由于不同区域拥有不同的相对最优权重，因此可以利用此种算法对定位精度进行改进。

其具体步骤如下：

1）在一个矩形区域顶点设置4个参考点A、B、C、D。

2）将矩形区域对半均分为4个区域如图4所示，并分别标号1、2、3、4，由于误差分布呈对称关系[17]，为节省时间，可只测量区域标号1，如图4，其他区域可进行对称运算。

3）将区域1均分为若干相同矩形区域，如图4所示，长宽随实际场地再具体确定定值（长宽值越小，所分网格越密，定位时精度越高，但相应复杂度增大），如图5、图6;测量出每个网格顶点距离A、B、C、D最近3个距离值d1、d2、d3，代入式（10），遍历每个点上误差的权重因子（-15～15，步长为0.1），选取最优的权重值，将权重值放入矩阵，构成权重因子矩阵A，如式（12）所示：

2.3 定位

1）通过测量未知节点M从4个参考点接收的RSS值，将所得到的RSS值与表1中进行比较，通过式（11）求出动态损耗因子，然后代入路径损耗公式（3），计算出4个距离d1、d2、d3和d4，如图5所示，选取最短的3个距离重新定义为d1、d2、d3。

2）将权重因子a先设置为1，再次代入式（10）进行粗定位，计算出未知节点M′的位置。

3）根据M′计算出实际M点位置。

①当M′点位于矩形区域内部时：

②当正好位于顶点时，直接取此点坐标。

③当位于分界处时，取分界线所在两个顶点的权重，反求新的两个未知点，再求均值。

考虑到在此步仍可用三角质心定位，但若划分区域很小，就可以不用，以节省時间，因此本文最后采用均值计算。

2.4 程序流程

改进算法的主要流程如下。

1）取出在1m处测的RSS值N组，高斯滤波后取其均值，得出A值。

2）将A代入路径模型，求出在已知固定距离和RSS值下的路径损耗因子n。

3）将在未知节点M所测的RSS值代入式（11），得出动态的n值。

4）将RSS值和动态n值代入式（3），得出4个距离，取其最小的3个，记为d1、d2、d3。

5）将权重因子a设为1，代入式（10），进行粗定位，求出此时M′点坐标。

6）在权重矩阵中取出M′点所在网格中的4个顶点的权重a，分别代入式（10），得出4个未知节点坐标。

7）将所求4个未知节点坐标取均值，最终得出未知节点M的坐标。

3 实验分析

3.1 实验过程

在空旷的室内场地，选取10m×10m矩形区域进行实验。在矩形的4个顶点位置设置参考点，设置4个相同型号的路由器斐讯FWR-706，其中A（0，10）、B（10，10）、C（0，0）、D（10，0）。本文RSS测试软件选用Homedate 1.74，软件接收信号强度如图7所示。算法运行于Matlab 2014a版本。

按上述步骤所测不同距离RSS值与n的对应关系填入表1，数据如表1所示。为了表示直观方便，绘制图8、图9，直观地表现RSS和nd与接收距离之间的关系。从表2和图8中可以发现，随着距离的增加，信号强度RSS和路径损耗因子随距离的增加呈现不同的变化。

在所分割的4个区域中，仅当测试误差最小时，填入装载最小权重a的矩阵A，如式（14）：

剩下3个区域，2区为1区的左右翻转，3区为1区的上下翻转，4区为3区的左右翻转。

通过测量未知节点M的RSS值，将其代入式（3），求出M点距离4个参考点的距离值，选取其中最小的3个，分别作为d1、d2、d3。其实际计算如式（15）：

3.2 实验分析

由于实验环境的不同，实验数据不可能与文献[16]和文献[17]完全相同，為了进行准确率的对比，随机进行实验。

本文采用实际位置与估算位置之间的相对距离进行误差分析，如式（16）：

在实际环境中，随机挑选15个位置对几种方法依次进行定位分析，最终得到实验结果数据如表2所示。

但从表中无法直观地看出各算法的优劣，依据表中数据画出误差折线图9。

从图9中可以看出，普通的质心定位效果较差，动态损耗因子质心定位和动态加权质心定位效果相差不大，而改进算法尽管有些点比动态损耗因子质心定位和动态加权质心定位效果差，但从总体上看，还是有很大优势。

为了不失一般性，因此随机抽取这15个位置进行定位，取100组数据求其误差均值，绘制折线图如图10，从图中可以看出，改进算法的误差小于以上三种定位算法。

从表3中可以看出，在随机挑选100组未知节点进行计算时，动态损耗因子质心算法和动态加权质心算法的最小误差值相似，但都比普通的质心算法精确，而最大误差值后三者相似，但还是优于普通质心算法，而在结合两种算法的基础上进行的改进算法在精度上是最好的，比质心算法提高了0.44，提高58%，比动态修正质心算法提高了0.09，提高21%，比动态加权质心算法提高了0.04，提高11%，改进算法平均误差值最小。

本文从算法运行时间对算法进行分析，从表7中看出，相比于普通质心定位算法，动态损耗因子质心算法在定位前期不断的调整损耗因子，动态加权质心算法构造权重因子矩阵，从而导致两种算法的运行时间都比普通的质心定位长。而改进算法是动态损耗因子和动态权重因子的结合，因此在前期的运行时间和动态损耗因子算法相近，而在后期的定位阶段，由于则需要查询权重矩阵，所以在提升精度的同时，对运行时间有所增加。因此下一步的工作要进行算法时间的减少方向研究。

4 结语

本文在传统质心定位的基础上，综合考虑了文献[16]损耗因子的动态变化和文献[17]权重因子的不同对定位精度的影响，将路径损耗模型的动态损耗因子和加权质心定位算法的动态权重因子相结合，提出一种改进的质心定位算法，提升了定位的精度。新的算法将实际测量的RSS代入动态损耗因子计算公式，从而使不同的距离对应相应的路径损耗因子，减小质心定位算法因距离造成的误差;将定位区域划分网格，引入动态权重因子，减小因不同区域权重因子而造成的误差。改进的定位算法考虑了文献[16]和文献[17]的优点，经过实验验证，在定位精度上得到了提高。但由于算法的复杂，导致相应的运算时间延长，之后的工作将对算法进行精简改进，提高算法的运算速度;且本文主要是在没有遮挡物的情况下进行的实验，下一步将研究在室内条件下，有遮挡物时的定位问题。

参考文献 （References）

[1] YICK J， MUKHERJEE B， GHOSAL D. Wireless sensor network survey[J]. Computer Networks， 2008， 52（12）： 2292-2330.

[2] MAO G， FIDAN B， ANDERSON B D O. Wireless sensor network localization techniques [J]. Computer Networks， 2007， 51（10）： 2529-2553.

[3] RUDAFSHANI M， DATTA S. Localization in wireless sensor networks [C]// Proceedings of the 2007 6th International Symposium on Information Processing in Sensor Networks. New York： ACM， 2007： 51-60.

[4] 邓中亮，余彦培，徐连明，等.室内外无线定位与导航[M].北京：北京邮电大学出版社，2013：43-54.（DENG Z L， YU Y P， XU L M， et al. Indoor and Outdoor Wireless Positioning and Navigation [M]. Beijing： Beijing University of Posts and Telecommunications Press， 2013： 43-54.）

[5] 朱剑，赵海，孙佩刚，等.基于RSS均值的等边三角形定位算法[J].东北大学学报（自然科学版），2007，28（8）：1094-1097.（ZHU J， ZHAO H， SUN P G， et al. Equilateral triangle localization algorithm based on average RSSI [J]. Journal of Northeastern University （Natural Science）， 2007， 28（8）：1094-1097.）

[6] 赵昭，陈小惠.无线传感器网络中基于RSSI的改进定位算法[J].传感技术学报，2009，22（3）：391-394. （ZHAO Z， CHEN X H. An improved localization algorithm based on RSSI in WSN [J]. Chinese Journal of Sensors and Actuators， 2009， 22（3）： 391-394.）

[7] 杜佳星，陈亚伟，张静.基于聚类分析优化的距离修正室内定位算法[J].计算机工程与科学，2018，40（2）： 246-254. （DU J X， CHEN Y W， ZHANG J. Distance rectification indoor localization based on cluster analysis optimization [J]. Computer Engineering and Science， 2018， 40（2）： 246-254.）

[8] 谷广，游峰.基于接收信号强度指示的改进质心定位算法[J].传感器与微系统，2018，37（2）：147-153. （GU G， YOU F. Improved centroid localization algorithm based on RSSI [J]. Transducer and Microsystem Technologies， 2018， 37（2）： 147-153.）

[9] 陈维克，李文锋，首珩，等.基于RSSI的无线传感器网络加权质心定位算法[J].武汉理工大学学报（交通科学与工程版），2006，30（2）： 265-268.（CHEN W K， LI W F， SHOU H， et al. Weighted centroid localization algorithm based on RSSI for wireless sensor networks [J]. Journal of Wuhan University of Technology （Transportation Science and Engineering Edition）， 2006， 30（2）： 265-268.）

[10] 杨博雄，倪玉华，刘琨，等.基于加权三角质心RSSI算法的ZigBee室内无线定位技术研究[J].传感器世界，2012（11）：31-35. （YANG B X， NI Y H， LIU K， et al. Study on ZigBee wireless location technology based on weighting triple centroid RSSI algorithm [J]. Sensor World， 2012（11）： 31-35.）

[11] 姚碧超.室内WiFi定位技术研究[D].成都：电子科技大学，2017：41-43.（YAO B C. Research on indoor location technology based on WiFi [D]. Chengdu： University of Electronic Science and Technology of China， 2017： 41-43.）

[12] 朱玲玲，程学云，魏晓宁.基于高斯修正测距模型的节点改进加权质心定位算法设计[J].计算机测量与控制，2012，20（11）： 3089-3091.（ZHU L L， CHENG X Y， WEI X N. Design for improved weighted centroid localization algorism based on Gaussian correction ranging model for sensor node [J]. Computer Measurement and Control， 2012， 20（11）： 3089- 3091.）

[13] 李新春，蘭根.基于定向天线信号强差的定位方法[J].计算机应用与软件，2016，33（8）：167-171.（LI X C， LAN G. Localisation based on RSSI difference of directional antennas [J]. Computer Applications and Software， 2016， 33（8）： 167-171.）

[14] 任晓奎，张永旺.一种基于正交定向天线的节点定位算法[J].测控技术，2017，36（8）： 107-110.（REN X K， ZHANG Y W. A node localization algorithm based on orthogonal directional antenna [J]. Measurement and Control Technology，2017， 36（8）： 107-110.）

[15] 赵大龙，白凤山，董思宇，等.一种基于卡尔曼和线性插值滤波的改进三角质心定位算法[J].传感技术学报，2015，28（7）：1086-1090. （ZHAO D L， BAI F S， DONG S Y， et al. An improved triangle centroid location algorithm based on Kalman filtering and linear interpolation [J]. Chinese Journal of Sensors and Actuators， 2015， 28（7）： 1086-1090.）

[16] 张宏刚，黄华.基于RSSI路径损耗因子动态修正的三边质心定位算法[J].传感技术学报，2016，29（11）：1731-1736. （ZHANG H G， HUANG H. Dynamic correction algorithm for trilateral centroid localization based on RSSI path loss factor [J]. Chinese Journal of Sensors and Actuastors， 2016， 29（11）： 1731-1736.）

[17] 王飞，童敏明，白琪，等.基于RSSI的ZigBee动态加权质心四点定位算法[J].计算机应用研究，2018，35（9）：2663-2665. （WANG F，TONG M M， BAI Q， et al. ZigBee dynamic weighted centroid four points location algorithm based on RSSI[J].Application Research of Computers，2018， 35（9）： 2663-2665.）