基于接收信号强度指示的质心迭代定位算法

节点定位技术是无线传感器网络应用的关键。针对传统质心定位算法定位精度低的问题，提出了一种基于接收信号强度指示的三维质心迭代定位算法。算法根据测距技术简化未知节点的定位参考节点，通过节点间的空间几何关系得到距离偏移系数，利用系数的最优解对质心坐标进行修正，并多次迭代更新系数以更新定位结果，直到达到迭代准则为止。仿真实验结果表明，相比于传统的质心定位算法，本文算法可提高定位精度20%~28%，能有效减少无线传感器网络三维定位的定位误差。

Abstract

Node location technology is the key of wireless sensor networks. Aiming at the low accuracy of the traditional centroid localization algorithms， a three-dimensional iterative centroid localization algorithm based on received signal strength indication is proposed. Based on the location technology， the algorithm simplifies the location reference nodes of unknown nodes， obtains the distance offset coefficient through the spatial geometric relationship between the nodes， uses the optimal solution of the coefficient to modify the centroid coordinate， and updates the coefficient repeatedly to update the location result until the iteration criterion is reached. The simulation results show that compared with the traditional centroid positioning algorithm， the proposed algorithm can improve the positioning accuracy by 20%-28%， and effectively reduce the positioning error of three-dimensional positioning in wireless sensor networks.

1　引言

无线传感器网络（WSN）由在特定区域部署、对环境与物体等进行监控的无线传感器节点组成^［1］。在无线传感器网络中，位置信息对传感器网络的监测活动至关重要，节点定位技术作为无线传感器网络的关键技术之一，在**、工业、民用等领域具有巨大的应用价值^［2］。在目标检测与跟踪和基于位置信息的路由等应用中，没有位置信息的监测是毫无意义的，只有确定了节点的位置，采集到的数据才有参考价值^［3］。

节点定位算法可分为两类：基于测距的定位和与距离无关的定位。接收信号强度指示（RSSI）是目前研究较多的测距定位方法，相比于距离无关的定位方法，基于RSSI的定位技术方法简单，能够提高定位的精度^［4］。质心定位算法（CLA）^［5］作为一种与距离无关的分布式定位算法，其定位结果会偏向锚节点分布较多的区域，国内外学者针对经典质心定位算法进行了多次改进优化。文献［6］结合RSSI测距技术对加权质心定位算法的权值系数进行优化，修正了质心算法的定位结果，所提出的权值系数依赖于锚节点的分布。文献［7］在测距模型参数优化的基础上提出了六点质心定位算法，缩小了定位区域，该算法视节点均拥有圆形无线信号传播模型。文献［8］提出基于模糊C均值聚类的参考点加权质心算法来对RSSI的测距误差进行优化，但未对定位阶段的未知节点估计坐标修正。文献［9］引入虚拟锚节点增加锚节点密度，利用交叉阈值对边缘未知节点进行补偿修正，提高了定位精度，该算法是基于二维平面进行的。在实际应用中，节点在空间中呈立体分布，掌握节点的三维坐标至关重要，为进一步提高定位精度，本文对给定锚节点与质心之间的距离进行校正，提出了基于RSSI的质心迭代定位算法（CILA）。该算法将质心定位算法得到的位置坐标作为初始位置估计，利用距离偏移系数的最优解对质心定位结果进行更新优化，并多次迭代提高定位精度，仿真结果表明，算法能有效提高定位精度。

2　三维CILA算法

本文提出的CILA算法分为三个阶段过程：1）根据无线信号传播模型公式计算未知节点与各锚节点之间的距离，根据CLA算法得到质心，即未知节点的初步估计位置；2）计算各锚节点对应的距离偏移系数，并选取距离偏移系数的最优解；3）利用最佳距离偏移系数更新未知节点与锚节点之间的距离，实现质心位置的不断迭代从而得到未知节点的定位坐标。对算法涉及到的主要概念进行说明：

1）锚节点指已知自身坐标信息的节点，可通过技术手段等方式预先获取位置信息，为其他节点提供参考坐标。

2）未知节点指在无线传感器网络中坐标信息未知的节点。

2.1　RSSI测距模型

RSSI是一种接收信号强度指示测距的方法^［10］，能够获取信号的传播损耗并将其转化为距离。信号传输损耗符合对数正态阴影模型，可用修正的路径损耗模型描述^［11］，

P_{P L} (d) = P_{P L} (d_{0}) - 10 n l g (\frac{d}{d_{0}}) + X_{σ}

，（1）

式中： $P_{P L} (d)$ 为信号传播距离 $d$ 后的损耗，单位为dBm； $n$ 为传播因子（常取2~5）； $d$ 为发送节点与接收节点间的距离； $X_{σ}$ 为遮蔽因子，是一个均值为0、方差为 $σ$ 的高斯随机噪声变量，单位为dBm。

为了便于计算，在运用时参考距离 $d_{0}$ 取值为1 m。因此， $R S S I$ 公式可简化为

R_{R S S I} = - (A + 10 n l g d)

，（2）

式中：A为距离发射中心1 m处传感器节点所接收信号强度值； $R_{R S S I}$ 单位为dBm。依据（2）式，可求得 $d$ 的计算公式为

d = 10 - \frac{A + R_{R S S I}}{10 n}

。（3）

2.2　质心定位算法

质心定位算法是一种基于连通性与距离无关的定位算法^［12］，未知节点接收锚节点的位置广播信息，将自己的坐标定义为锚节点的质心。设待定位节点坐标为 $O (X, Y, Z)$ ，已知 $M$ 个锚节点信息，锚节点坐标分别 $S_{1} (x_{1}, y_{1}, z_{1})$ ， $S_{2} (x_{2}, y_{2}, z_{2})$ ，…， $S_{M} (x_{M}, y_{M}, z_{M})$ ，则节点O的物理位置估计坐标为

(X, Y, Z) = (\frac{x_{1} + x_{2} + \dots + x_{M}}{M}, \frac{y_{1} + y_{2} + \dots + y_{M}}{M}, \frac{z_{1} + z_{2} + \dots + z_{M}}{M})

。（4）

仅基于质心的定位算法虽然计算简单，但单纯依赖于锚节点的分布会导致计算结果偏于锚节点分布较多的区域。

利用RSSI的对数衰减特性对质心算法进行初步改进。估算未知节点的位置之前，先对锚节点进行选择，在锚节点均匀分布的室内定位环境下，未知节点可与多个锚节点进行点对点通信，将未知节点能接收到的 $R_{R S S I}$ 值降序排列，记为 $\{R_{R S S I}\} = \{R_{R S S I 1}, R_{R S S I 2}, \dots, R_{R S S I M}\}$ 。空间中4点即可确定一个点的坐标^［13］，选取接收到的 $R_{R S S I}$ 值最大的4个锚节点作为待定位节点的参考节点，如图1（a）所示，锚节点为球心，节点通信距离为半径，球体即为锚节点的通信范围，则球体交集区域内的每一个点都有可能是未知节点，如图1（b）所示。

图 1. 定位模型示意图。（a）定位锚节点;（b）未知节点所在区域

Fig. 1. Schematic of positioning model. （a）Anchor nodes;（b）unknown nodes area

下载图片查看所有图片

因此，仅计算质心坐标会造成定位结果的不准确。为了进一步减小定位误差，本文引入距离偏移系数对所得质心坐标进行校正。

2.3　质心迭代定位算法

设未知节点O通信范围内第 $N$ 个锚节点的坐标为 $(x_{N}, y_{N}, z_{N})$ ，则该锚节点与未知节点之间的欧氏距离为

\begin{array}{l} d = \sqrt[]{(x_{N} {- X)}^{2} + (y_{N} {- Y)}^{2} + (z_{N} {- Z)}^{2}}, \\ 1 \leq N \leq 4 \end{array}

。（5）

锚节点 $S_{1} 、 S_{2} 、 S_{3} 、 S_{4}$ 所张成的三维空间的质心 $O_{1}$ 坐标为 $(X_{O_{1}}, Y_{O_{1}}, Z_{O_{1}})$ ，其计算公式为

\{\begin{array}{l} X_{O_{1}} = \frac{1}{4} \sum_{N = 1}^{4} x_{N} \\ Y_{O_{1}} = \frac{1}{4} \sum_{N = 1}^{4} y_{N} \\ Z_{O_{1}} = \frac{1}{4} \sum_{N = 1}^{4} z_{N} \end{array}

。（6）

质心 $O_{1}$ 与锚节点 $S_{1}$ 的距离为

d_{11} = \sqrt[]{{(\frac{1}{4} \sum_{N = 1}^{4} x_{N} - x_{1})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} y_{N} - y_{1})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} z_{N} - z_{1})}^{2}}

。（7）

同理可得，质心 $O_{1}$ 与锚节点 $S_{2}$ 、 $S_{3}$ 、 $S_{4}$ 的距离分别为

d_{12} = \sqrt[]{{(\frac{1}{4} \sum_{N = 1}^{4} x_{N} - x_{2})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} y_{N} - y_{2})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} z_{N} - z_{2})}^{2}}

，（8）

d_{13} = \sqrt[]{{(\frac{1}{4} \sum_{N = 1}^{4} x_{N} - x_{3})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} y_{N} - y_{3})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} z_{N} - z_{3})}^{2}}

，（9）

d_{14} = \sqrt[]{{(\frac{1}{4} \sum_{N = 1}^{4} x_{N} - x_{4})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} y_{N} - y_{4})}^{2} + {(\frac{1}{4} \sum_{N = 1}^{4} z_{N} - z_{4})}^{2}}

。（10）

定义由对数衰减模型求得的盲-锚的距离值 $d_{I i}$ 与由质心定位求得的盲-锚距离值 $d_{O_{I}}$ 的比值为距离偏移系数，

C_{d e v} = \frac{d_{I i}}{d_{O_{I}}}, i = 1,2, 3,4

，（11）

式中： $I$ 为质心的更新次数。每次质心迭代都能得到4个偏移系数，因此选取合适的系数对于定位结果的精确性具有重要意义。根据所得偏移系数设定样本置信区间，选取最优偏差系数进行再次迭代计算，定义选取到的偏移系数为t-系数。偏差系数的均值为

E = \frac{C_{d e v 1} + C_{d e v 2} + C_{d e v 3} + C_{d e v 4}}{4}

。（12）

偏移系数的标准差为

S_{s t} = \sqrt[]{\frac{1}{N} \sum_{1}^{N} (C_{d e v i} {- E)}^{2}}

。（13）

抽样分布 $σ$ 为

σ = \frac{S_{s t}}{\sqrt[]{N}}

，（14）

式中： $N = 4$ 。由于系数的样本量较少，可用t分布^［14］的统计特性对所得系数进行评估，计算最优距离偏移系数的置信区间：

C_{d e v i} \in E \pm t \times σ

。（15）

将落在置信区间内的系数作为二次迭代的距离偏移系数，并对其平均数、中位数以及本文选取数据进行研究分析，比较不同系数的定位结果，定位误差表示为 $E_{e r r o r}$ ，计算公式为

E_{e r r o r} = \sqrt[]{{(X - x)}^{2} + {(Y - y)}^{2} + {(Z - z)}^{2}}

。（16）

其一次定位结果如图2所示。

图 2. 不同偏移系数定位误差对比图

Fig. 2. Comparison of positioning errors with different offset coefficients

下载图片查看所有图片

从图中可以看出，偏移系数取平均值其定位误差比t-系数的定位误差高0.29 m，定位结果易受到部分极值的影响，并影响质心二次迭代的准确性；取中位数能减少极值对数据的影响，但忽略了数据的整体性；t分布的统计特性使用正态分布对小样本进行统计分析，其定位结果较平均系数、中位系数的定位结果分别提高了17%、10%。根据所得距离偏移系数的最优解，更新质心与对应锚节点之间的距离：

d_{O_{I}} = \frac{d_{I i}}{C_{d e v i}}, I = 1,2, 3, \dots, N

。（17）

根据（5）式、（17）式重新计算新的质心坐标，实现质心定位结果的校正。

为了找到合适的迭代终止次数，在图3中进行10次迭代计算来提高不同通信半径（节点通信半径R=15 m和R=30 m）和不同锚节点间隔（锚节点间隔为20 m和30 m）时的定位精度。由图3可知，即使在节点通信半径R=15 m且锚节点间隔为30 m的较差定位条件下，3次迭代后也可以将定位误差降低47%。算法的定位精度随着质心迭代次数的增加而提高，随着距离偏移系数趋于稳定，算法迭代对未知节点的定位精度的改善作用减小，在5次迭代之后达到收敛，因此本文设定算法迭代次数为5次。

图 3. 迭代次数分析

Fig. 3. Analysis of number of iterations

下载图片查看所有图片

3　仿真分析

用MATLAB对所述定位算法进行仿真分析。假设仿真区域为100 m×100 m×100 m的三维空间，125个锚节点均匀分布，10个未知节点随机分布，仿真场景如图4所示。在相同环境下对本文算法和质心算法的定位精度进行对比。

图 4. 仿真环境模拟

Fig. 4. Simulation environment simulation

下载图片查看所有图片

考虑实际定位应用中节点的硬件条件，分别选取节点通信距离较小的情况，即R=15 m，和节点通信半径较大的情况，即R=30 m，仿真对比传统质心定位误差和对质心进行迭代优化后的定位误差。

由图5可知，通信半径为15 m时CILA方法比CLA方法的定位误差减少了20%，通信半径为30 m时CILA方法比CLA方法的定位误差减少了28%。这是因为质心定位算法的定位性能易受锚节点数量的影响，在通信半径较小时，未知节点连通的锚节点数量较少，定位误差处于较高水平，节点通信半径的增大使得与未知节点连通的锚节点数量增加，定位精度得到提高。

图 5. 不同通信半径定位对比

Fig. 5. Comparison of different communication radius

下载图片查看所有图片

通信半径为15 m时CILA方法的平均定位误差仅仅比通信半径为30 m时CLA方法的平均定位误差高0.03 m。这是因为本文算法采用质心迭代计算的方法估计未知节点的位置信息，多次迭代计算可以提高未知节点的定位精度，因此，在连通锚节点数量较少的情况下定位效果依然很好。

4　结论

本文对质心定位算法进行了优化和改进，提出一种基于RSSI的三维质心迭代定位算法。该算法融合RSSI测距技术进行对定位锚节点的筛选，排除了未知节点接收锚节点信号过多的情况，分别计算锚节点-未知节点和初始质心-未知节点之间的距离得到距离偏移系数，并选取合适的系数更新质心位置，通过多次迭代不断减小定位误差。仿真结果表明，该算法能有效地提高定位精度，与质心定位算法相比，定位效果更好。

参考文献

[1] 杨超超，陈建辉，刘德亮，等. 基于到达时间和到达角度的室内联合定位算法［J］. 激光与光电子学进展， 2019， 56（22）： 222802.

Yang C C， Chen J H， Liu D L， et al. Indoor joint localization algorithm based on time and angle of arrival［J］. Laser & Optoelectronics Progress， 2019， 56（22）： 222802.

[2] 刘伟荣，何云. 物联网与无线传感器网络［M］. 北京：电子工业出版社， 2013： 140.

Liu W R， He Y. Internet of things and wireless sensor networks ［M］. Beijing： Publishing House of Electronics industry， 2013： 140.

[3] 陈道钱，吴晓平，华宇婷. 一种测距辅助的室内可见光指纹定位方法［J］. 激光与光电子学进展， 2019， 56（6）： 060603.

Chen D Q， Wu X P， Hua Y T. Indoor visible light fingerprint localization scheme with range-assistance［J］. Laser & Optoelectronics Progress， 2019， 56（6）： 060603.

[4] 张治斌，徐小玲，阎连龙. 基于Zigbee井下无线传感器网络的定位方法［J］. 煤炭学报， 2009， 34（1）： 125-128.

Zhang Z B， Xu X L， Yan L L. Underground localization algorithm of wireless sensor network based on Zigbee［J］. Journal of China Coal Society， 2009， 34（1）： 125-128.

[5] 宋海声，周浩，朱长驹，等. 二次栅格扫描与三角形质心迭代的定位算法［J］. 计算机工程与科学， 2019， 41（2）： 268-274.

Song H S， Zhou H， Zhu C J， et al. A positioning algorithm with twice grid scanning and triangle centroid iteration［J］. Computer Engineering & Science， 2019， 41（2）： 268-274.

[6] 尹亚波，徐晴. 基于RSSI测距的无线传感器网络质心定位算法优化［J］. 计算机与数字工程， 2018， 46（12）： 2425-2429， 2462.

Yin Y B， Xu Q. Centroid localization algorithm for wireless sensor networks based on RSSI distance measurement［J］. Computer & Digital Engineering， 2018， 46（12）： 2425-2429， 2462.

[7] 胡斌斌，倪晓军. 基于RSSI测距室内定位改进质心算法［J］. 计算机技术与发展， 2017， 27（9）： 133-136， 140.

Hu B B， Ni X J. An improved indoor localization algorithm of centroid with RSSI［J］. Computer Technology and Development， 2017， 27（9）： 133-136， 140.

[8] 李海啸，于东，胡毅，等. 改进的无线传感器网络三边质心定位算法［J］. 小型微型计算机系统， 2020， 41（6）： 1216-1223.

Li H X， Yu D， Hu Y， et al. Improved trilateration centroid localization algorithm for wireless sensor network［J］. Journal of Chinese Computer Systems， 2020， 41（6）： 1216-1223.

[9] Kwang-Yul K， Yoan S. A distance boundary with virtual nodes for the weighted centroid localization algorithm［J］. Sensors， 2018， 18（4）：1054-1064.

[10] 叶子蔚，叶会英，聂翔宇，等. 基于接收信号强度检测的高精度可见光定位方法［J］. 中国激光， 2018， 45（3）： 0306002.

Ye Z W， Ye H Y， Nie X Y， et al. High-accuracy visible light positioning method based on received signal strength indicator［J］. Chinese Journal of Lasers， 2018， 45（3）： 0306002.

[11] Kaur A， Kumar P， Gupta G P. A weighted centroid localization algorithm for randomly deployed wireless sensor networks［J］. Journal of King Saud University-Computer and Information Sciences， 2019， 31（1）：82-91.

[12] Li J， Li Z， Song W T. A new three-dimensional localization method for WSN［C］// Cloud Computing and Intelligent Systems （CCIS）， 2012 IEEE 2nd International Conference on. IEEE， 2012.

[13] Chen J， Wang S， Ouyang M， et al. Iterative positioning algorithm for indoor node based on distance correction in WSNs［J］. Sensors， 2019， 19（22）：4871-4887.

[14] 周敏，汪文俊. t分布的代表点及其在统计模拟中的应用［J］. 应用数学学报， 2016， 39（4）： 620-640.

Zhou M， Wang W J. Representative points of student's tn distribution and their applications in statistical simulation［J］. Acta Mathematicae Applicatae Sinica， 2016， 39（4）： 620-640.

赵晓倩, 王伟. 基于接收信号强度指示的质心迭代定位算法[J]. 激光与光电子学进展, 2021, 58(3): 0328005. Zhao Xiaoqian, Wang Wei. Iterative Centroid Localization Algorithm Based on Received Signal Strength Indication[J]. Laser & Optoelectronics Progress, 2021, 58(3): 0328005.