一种改进的质心定位及误差校正算法

杜士怀 宋 杰

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

一种改进的质心定位及误差校正算法

杜士怀 宋 杰

(安徽大学计算机科学与技术学院 安徽 合肥 230601)

在信标节点分布不均匀的情况下，为了使节点定位的误差尽可能小以及在误差校正过程更加有效和可靠，提出一种改进的质心定位算法。该算法首先确定未知节点通信范围内的信标节点，然后取部分这些信标节点作为顶点构成凸多边形，通过RSSI获取未知节点与凸多边形的各个顶点的距离，之后将质心定位的凸多边形内的所有信标节点都作为校正节点，由这些校正节点得到相对应的校正因子，通过添加权重因子综合所有的校正因子来替换未知节点的测距误差因子，对测距误差进行补偿，最后利用加权质心定位方法确定未知节点的最终位置。仿真实验表明：在信标节点分布不均匀的情况下，在100 m×100 m的监测区域内，该算法相比于其他定位算法具有更强的抗干扰能力，而且平均定位误差至少减少12%，是一种定位精度更高的算法。

节点定位 接收的信号强度指示 质心定位算法 凸多边形 校正因子 补偿

0 引 言

在研究无线传感器网络中，节点定位技术是一项重要的支撑技术。获取传感器节点的位置信息的精确与否对于无线传感器网络至关重要[1]。

在无线传感器网络(WSN)定位算法中，由节点的坐标位置信息是否已知可分为信标节点和未知节点；在获得位置信息时根据未知节点与信标节点之间的距离是否需要测量分为测距算法和非测距算法[2]。前者常使用的测距算法主要包括RSSI、AOA、TOA等定位算法，而后者常使用的非测距算法主要有质心法、凸规划法、DV-Hop等定位算法[3]。

尽管当前的定位算法很多，但都有定位精度不足、及抗干扰性差等问题，本文结合以上问题提出了一种基于RSSI测距的改进的质心定位算法。仿真实验表明：该算法在抗干扰性、定位的精度和定位误差等方面都有所优化，本算法是一种有效处理节点定位的算法。

1 定位算法模型介绍

1.1 RSSI测距原理

RSSI测距即测量发送节点和接收节点之间的距离，通常采用信号强度或接收功率来测量，而无线射频信号是这类测量的常用方法[4]；考虑到在实际环境中，无线信号是受到多路径、散射等的影响，故在这里使用Shadowing模型作为无线信号传播路径损耗模型。如下式：

(1)

其中，发射节点到接收节点的距离为d；参考距离为d0；η为衰减指数，通常取2～4；Pd为距发射节点d处的信号强度；P0为参考距离d0处的接收信号功率；Xσ是均值为零、方差为σ的高斯随机噪声；在应用中常常忽略Xσ的影响，并取参考距离=1 m，于是得到常用的基于RSSI的测距公式如下：

Pd=A-10ηlgd

(2)

其中A为距发射节点1 m处的接收信号功率[4]。

1.2 改进的质心定位算法

传统的质心定位算法是一种仅基于连通性、与距离无关的定位算法，该算法简单、实现难度低，算法的基本思想如下：未知节点首先确定在其网络通信范围内有哪些信标节点，然后把这些信标节点作为顶点构成多边形，最后根据这个多边形的质心来估计未知节点的位置[5-6]。

在传统的质心定位算法中把多边形的质心当作未知节点，这种做法的精确度与信标节点的密度以及信标节点的分布是否均匀都有着直接的关系，当信标节点的密度较低且分布不均匀时，常见的特别是在多边形为非对称不规则的凹多边形时，如图1所示。

图1 凹多边形下的质心定位图

显然此时多边形的质心与未知节点相差甚远，在这种情况下使用此算法获得的未知节点坐标的精度明显降低，所以基于此，本文提出了一种改进的基于RSSI的质心定位算法。算法的基本思想如下：如上所述，以信标节点作为顶点构成多边形，对此多边形作如下操作：如果是凹多边形，通过剔除顶点的方式转变为较为规则的凸多边形；如果是凸多边形则不变。然后以质心定位算法为基础，依次将RSSI引入，起辅助信息的作用，为每一个信标节点增加权值，反映不同信标节点对未知节点的影响。所以未知节点的预测坐标计算如式(3)：

(3)

故先构成凸多边形，然后在传统的质心定位算法中引入RSSI数据信息，从而提高预测坐标的精度。算法示意如图2及其应用过程如下：

图2 改进的质心定位原理图

(1) 信标节点周期性地向邻居节点广播身的ID和位置信息的信号；当未知节点O接收到这些信息后将其储存，当收到某个信标节点的信号数量超过预先设定的阈值后，该节点认为与此信标节点连通，并取该信标节点RSSI的均值。

(2) 由上一步得到信标节点的集合：B_set=(b1,b2,…,bk)；通过凸多边形的所有边中，任意一条边向两方无限延长成为一条直线时，其他各边及顶点都在此直线的同旁的原则，将此集合中的节点构成凸多边形(ABCDE)。

(3) 然后将RSSI值转换为距离值，即距离集合：D_set=(d1,d2,…,dk)，以及凸多边形(ABCDE)的顶点坐标值代入式(3)中进行计算，从而得到未知节点O的预测值。

1.3 坐标误差校正算法

在以下的仿真实验中可见，以上改进的基于RSSI测距的质心定位算法比传统的质心定位算法精度更高，而且它的算法复杂度更低，但如果在要求精度更高的应用环境下，以上算法还不能满足；为了使坐标定位更精确，最后再提出一种对坐标进行误差校正的算法；在现有校正算法如三角形质心定位的误差校正的算法中，通常引入一个校正节点，此校正节点一般取离未知节点最近的信标节点，由于未知节点与校正节点距离很近，可以近似认为两者的误差因子影响一致，因而利用校正节点的校正因子代替未知节点的误差因子[7-9]。

以上算法得到的校正因子在一定程度上能够校正1.2节中得到的预测坐标，但是在环境干扰过大以及其他不确定的因素下，误差因子由某一个节点确定难免会带来更大的误差，故本文提出利用1.2节中的凸多边形内的所有的信标节点作为校正节点，然后对预测坐标进行校正计算，此校正算法更为可靠及有效地避免上类问题的出现。本文提出的改进的误差校正算法如下：

(4)

可得相应的测距误差因子(αf1、αf2、αf3、…)。

(5)

通过上式可得对应信标节点A的校正因子βA，按照以上两步可得校正因子βB、βC、βD、βE。因而利用校正节点的校正因子代替未知节点的误差因子。而将校正因子βA、βB、βC、βD、βE代入加权质心定位算法即可得到测距误差校正公式：

(6)

2 基于RSSI测距的误差校正改进的定位算法

正如1.2节中所述，在传统的基于RSSI的质心定位算法中，当由未知节点通信范围内的信标节点构成的多边形是凸多边形时，会提高定位的精度，故提出将多边形转为凸多边形；而常用的误差校正方法存在环境干扰的偶然性过大及相关的不确定因素存在，故本文提出了一种更可靠以及更有效的误差校正算法以避免上类问题的出现。算法过程及流程如图3所示。

图3 基于RSSI测距的改进的质心算法流程图

首先通过已确定的未知节点接收信标节点的信号数量的阈值判断节点之间的连通性，然后使用与未知节点连通的信标节点构造多边形，接着使多边形向凸多边形转变。凸多边形的所有边中，任意一条边向两方无限延长成为一条直线时，其他各边及顶点都在此直线的同旁，然后利用RSSI计算未知节点与信标节点的距离，将以上信息代入式(3)中得到未知节点的预测坐标值，在对定位精度要求不高的应用环境中，此种方法已满足；在定位精度更高的环境下，则可以将校正因子代入式(3)，即利用凸多边形内的信标节点作为校正节点，由这些校正节点得到相对应的校正因子，通过添加权重因子综合所有的校正因子来替换未知节点的测距误差因子，对测距误差进行补偿，最后利用加权质心方法确定定位(式(6))，从而得到未知节点的最终坐标。

3 仿真实验与分析

3.1 仿真环境

传感器节点随机分布在100 m×100 m的监测区域内，200个未知节点随机分布在平面内，通信半径设为20 m,通过Matlab对实验环境进行模拟并对数据进行分析。本仿真实验分两部分，首先验证改进的质心定位算法能否有效地提高定位精度，然后验证误差校正算法在有环境干扰的情况下定位的精度是否更加稳定和可靠。

3.2 实验结果与分析

首先实验验证改进的质心定位算法能否提高定位的精度。将改进的算法与传统的质心定位算法做对比，实验在无环境干扰的情况下进行，在同一网络环境下重复实验50次，每次实验都将所有节点重置，对50次实验结果求均值，分别在信标节点分布情况不同的条件下进行实验。实验结果如下所示：在图4中可见，在信标节点分布均匀的情况下，改进的质心定位算法并没有有效地降低定位误差，而如图5在信标节点分布不均匀的情况下，随着信标节点的数量从20增加到80，传统的质心定位算法的定位误差从39.24%下降到26.28%，改进的算法的定位误差从27.89%下降到17.73%；改进算法有明显降低误差的效果，而且从两个图中可以看到，改进算法的误差曲线波动更小，更稳定，受信标节点分布情况的影响更小。

图4 在信标节点分布均匀的情况下

图5 在信标节点分布不均匀的情况下

接着在同样的环境下，增加环境干扰，对比基于RSSI的误差校正的三角形质心定位算法和本文提出的基于RSSI误差校正质心定位算法。对比两种算法之间的误差分布对比图如图6所示：在此实验中固定信标节点为40个，此处使用的环境干扰为高斯白噪声，在MATLAB中产生此噪声非常方便，对某一局部进行干扰，此干扰的影响是RSSI的测距的误差逐渐变大，对定位造成影响；故在实验中不断加大环境干扰，分析在此情况下两种算法的稳定性和可靠性。实验结果如下所示：随着噪声干扰的逐渐增大，两种定位算法的误差都逐渐增大，但显然基于RSSI的误差校正的三角形质心定位算法的误差增大的幅度比本文提出的算法更快，而且误差也更大。

图6 两种误差校正定位方法的对比

由以上两个实验验证了以上的理论，改进的基于RSSI的质心定位算法相对于传统的质心定位算法的定位精度更高，而基于此算法的误差校正算法的精度和稳定性、可靠性都有所提高。总之，改进的算法可以有效地提高测距的精度和增强定位的稳定性和可靠性，从而更加适用于无线传感器网络节点的定位。

4 结 语

本文在研究定位算法的基础上，提出一种改进的基于RSSI测距的质心定位算法和其误差校正的定位算法。即通过未知节点通信范围内的信标节点构造凸多边形，通过RSSI测距利用加权质心算法对未知节点定位。在此算法的基础上，利用凸多边形内的信标节点得到校正因子，对RSSI的距离信息进行校正，得到最终的坐标值。该算法不仅在提高定位的精度方面有很好的效果，而且在抗干扰、稳定性和可靠性上都有很好的表现。基于仿真实验表明：本文提出的改进算法不但能提高节点的测距精度，满足节点的定位，同时还有良好的抗干扰能力和可靠性。

[1] 郑军, 张宝贤. 无线传感器网络技术[M]. 北京：机械工业出版社, 2012.

[2] Erramilli V, Malta I, Bestavros A. On the interaction between data aggregation and topology control in wireless sensor networks[C]//Proceedings of the 1st Annual IEEE Communications Society Conference on Sensor and Ad Hoc Communications and Networks, 2004:557-565.

[3] 张婵爱, 马艳艳, 白凤娥, 等. 基于RSSI的加权质心定位算法的实现[J]. 太原理工大学学报, 2009, 40(2):146-147,199.

[4] 马祖长, 孙怡宁. 无线传感器网络节点的定位算法[J]. 计算机工程, 2004, 30(7):13-14,48.

[5] 詹杰, 吴伶锡, 唐志军. 无线传感器网络RSSI测距方法与精度分析[J]. 电讯技术, 2010, 50(4):83-87.

[6] 杨宁, 钟绍山, 徐耀良, 等. 一种改进高斯-卡尔曼滤波的RSSI处理算法[J]. 自动化仪表, 2013, 34(7):6-8,11.

[7] 刘政. 基于接收信号强度指示的误差校正定位算法[J]. 传感技术学报, 2014, 27(7):970-975.

[8] 朱博, 陈曙. 一种无线传感器网络质心定位改进算法[J]. 传感技术学报, 2010, 23(6):868-872.

[9] 李娟, 王珂, 李莉, 等. 基于锚圆交点加权质心的无线传感器网络定位算法[J]. 吉林大学学报(工学版), 2009, 39(6):1649-1653.

[10] 张春园, 刘兴长, 张伟伟, 等. 基于6LowPAN的RSSI测距方法优化[J]. 自动化与仪器仪表, 2014(11):151-154.

[11] 王振朝, 张琦, 张峰. 基于RSSI测距的改进加权质心定位算法[J]. 电测与仪表, 2014, 51(21):63-66.

[12] 文春武, 宋杰, 姚家振. 基于RSSI校正的无线传感器网络定位算法[J]. 传感器与微系统, 2014, 33(12):134-136,145.

AN IMPROVED CENTROID LOCALIZATION AND ERROR CORRECTION ALGORITHM

Du Shihuai Song Jie

(ScoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

In order to make the error of node location as small as possible and more effective and reliable in the error correction process, an improved centroid location algorithm is proposed in the case of nonuniform beacon distribution. The algorithm firstly determines the beacon nodes in the communication range of unknown nodes, and then takes some of these beacon nodes as vertices to form convex polygons. The distance between the unknown node and each vertex of the convex polygon is obtained through the RSSI. Then all the beacon nodes in the convex polygon of the center of mass are taken as correction nodes, and the corresponding correction factors are obtained by these correction nodes. By adding the weighting factor, all the correction factors are combined to replace the ranging error factor of the unknown node, and the error of the ranging is compensated. Finally, the final position of the unknown node is determined by the weighted centroid localization method. Simulation results show that the algorithm has stronger anti-jamming capability than other localization algorithms in the 100 m×100 m monitoring area, and the average positioning error is reduced by at least 12% when the beacon nodes are distributed unevenly, the algorithm is a more accurate location algorithm.

Node localization RSSI Centroid localization algorithm Convex polygon Correction factor Compensation

2016-01-29。杜士怀，硕士生，主研领域：无线传感器网络。宋杰,副教授。

TP393

A

10.3969/j.issn.1000-386x.2017.05.020