一种改进的质心定位算法

刘皇保，王 涛，彭 刚

（1.桂林电子科技大学 电子工程与自动化学院，广西 桂林541004；2.空军空降兵学院 教育技术中心，广西 桂林541003）

无线传感器网络是大量的静止或移动的传感器以自组织和多跳的方式构成的无线网络，大量的传感器节点将探测数据，通过汇聚节点经其他网络发送给了用户[1]。

节点定位技术是无线传感器网络的关键技术之一。没有节点的位置信息，传感器监测信息将没有实际意义。无线传感器网络只有少数锚节点可以人工布置或者通过GPS定位系统获得自身的位置信息，大部分普通节点则必须通过锚节点信息来进行定位。

无线传感器网络定位技术主要分为基于距离的定位算法（如RSSI、TOA/TDOA和AOA）和距离无关的定位算法（如质心、DV-Hop、APIT、Amorphous和凸规划）。

质心算法可以快速、方便地定位节点的初始位置，而基于距离的定位算法RSSI[2]需要额外的器件来测量实际节点间的距离，会增加功耗，但与距离无关的定位算法相比较，其定位精度更高。将两者结合势必会取得较好的定位效果。通过分析现有的质心算法缺陷，结合RSSI，对质心算法进行改进，提出一种改进的质心定位算法。

1 质心定位算法

1.1 质心定位算法的基本思想

质心算法[4]是由南加州大学的Nirupama Bulusu等人提出的，在未知节点收到相邻锚节点的位置信息后，取这些相邻锚节点的质心作为该未知节点的估计位置。传统的质心算法 （Centroid Algorithm）是一种基于连通而无需距离信息的简单定位算法。传统的质心算法的基本原理如图1所示。

图1 质心定位算法

在质心定位算法中，信标节点周期性地向邻近节点广播信标分组，信标分组中包含信标节点的标识号和位置信息。当未知节点接收到来自不同信标节点的信标分组数量超过某一个门限或接收一定时间后，就确定自身位置为这些信标节点所组成的多边形的质心：

其中，（Xi1，Yi1）…（Xik，Yik）为未知节点能够接收到其分组的信标节点坐标。

通过对算法思想的分析，可知传统的质心定位算法定位误差较大。

1.2 现有改进的质心定位算法

胡咏梅等[4]人提出了一种改进的加权质心定位算法，对未知节点大致位置的算法作了新的修正，并对未知节点位置确定算法中的加权因子进行了优化。于慧霞[5]提出了一种新的校正RSSI测距值的加权定位算法。测距阶段将锚节点之间的距离和信号强度信息同时考虑在内，进行RSSI值校正，权值选择阶段采用了修正传统权重的计算方法，权值取距离倒数之和。苟胜难[6]提出了一种基于改进的RSSI无线传感器网络节点定位算法研究。算法首先通过无线信号强度计算出节点间RSSI值，然后把RSSI值转换成质心算法权值，最后采用质心定位算法对待测节点位置进行估计，获得节点的准确位置。

苹果想要卖上好价，关键在提高果品质量。现场采购商对王建云及其他参赛选手的苹果品质表示了认可，并向记者透露，果农是否选择大品牌的农资产品，对于采购商来说是一个重要的参考指标。因为使用像亲土1号这样的产品，更能有效保障果品的质量和安全，而只要是品质好的果子，既不愁卖，也不担心卖不上价。

2 本文对质心算法的改进

以往的算法应用于未知节点周边的锚节点的整个区域，本文将未知节点周边区域进行了细分，利用未知节点收到周边锚节点的信号强度（RSSI），取细分后的某区域的质心作为未知节点的估计位置。

具体步骤如下：

（1）利用周围锚节点收到的未知节点信号的强度确定最近的3个不共线的锚节点。

如图2所示，可知锚节点A、B、C为未知节点O周围最近的3个不共线的锚节点。

（2）确定3个锚节点构成的三角形的外接圆，通过三角形三边的垂直平分线将外接圆分成6个区域，如图3所示。

图3中，由3条垂直平分线l1、l2、l3将未知节点O周围圆形区域划分为6个区域。6个区域内的未知点发送的信号在A、B、C 3个位置收到的信号强度大小关系各不同。

图2 未知节点周边锚节点

图3 分区示意图

（3）根据A、B、C 3个位置锚节点收到的信号强度关系确定未知节点所在区域，如图4所示。

图4 未知节点所在区域

从区域的△OPQ内的未知节点发射的信号，在A、B、C 3个位置收到的信号强度有如下关系：

未知节点在6个区域中发射的信号在A、B、C 3个位置锚节点收到的信号强度关系各不同。因此，根据信号强度关系，按照以下方法可以进行更为精确的定位：

①如果3个锚节点收到的信号强度都不同，则根据信号强度关系先确定未知节点所在三角形区域，然后取该区域的质心作为未知节点的估计位置。

②如果A、B、C 3个锚节点中某两个点收到的信号强度一样，则定位区域变成一条线。如图4所示，假设RSSIa=RSSIc，则未知节点在l3上，结合RSSIa>RSSIb，可确定未知节点的估计位置在上，此时，取的中点作为估计位置。

③如果A、B、C 3点收到的信号强度是一样的，则取外心O作为未知节点的估计位置。

3 实验及仿真结果

本文采用MATLAB 7.1作为仿真工具，对算法进行了仿真。仿真环境设置在1 000 m×1 000 m的正方形区域内，随机生成300个网络节点，锚节点占一定比例，锚节点的通信距离为200 m。对仿真结果数据取10次仿真的平均值。节点分布如图5所示。

图5 初始节点分布

接下来，根据区域内节点的分布关系，计算出所有节点的邻居关系，为后面的未知节点定位做好准备。节点邻居关系如图6所示。

图6 节点邻居关系

最后，采用改进的质心定位算法进行未知节点的定位，计算出各个未知节点的定位误差。画出定位误差图形如图7所示。

图7 每个未知节点的定位误差

通过设置不同的锚节点比例得到相应不同的定位误差，与原始的质心算法仿真结果对比，可以得出定位误差对比图，如图8所示。

在通信距离为200 m时以锚节点占全部节点的比例来作为图中的横坐标，以未知节点的平均定位误差作为纵坐标，作出原始质心算法和改进的质心算法的平均定位误差图。从图8可以看出，随着锚节点增加，未知节点的定位误差相应减小，同时，与原始质心算法相比，改进的质心算法平均定位误差减少了将近60%。

图8 平均定位误差

基于传统的质心算法和RSSI思想，本文提出了一种基于RSSI的改进的质心定位算法。该算法首先通过RSSI大小确定未知节点周边锚节点的远近，找出最近的3个锚节点，采用3个锚节点确定的三边的垂直平分线将未知节点的辐射范围划为6个区域；然后，根据RSSI确定未知节点所在的更小区域；最后，取该区域的质心作为未知节点的估计位置。仿真结果证明，此方法大大提高了定位精度。

[1]孙利民，李建中，陈渝，等.无线传感器网络[M].北京：清华大学出版社，2005.

[2]HEURTEFEUX K，VALOIS F.Is RSSI a good choice for localization[C].26th IEEE International Conference on Advanced Information Networking and Applications in Wireless Sensor Network，France，2012.

[3]BULUSU N，HEIDEMANN J，ESTRIN D.GPS-less lowcost outdoor localization for very small devices[J].Personal Communications，IEEE，2000，7（5）：28-34.

[4]胡咏梅，张欢.一种改进的无线传感器网络质心定位算法[J].计算机工程与科学，2012，34（2）：45-49.

[5]于慧霞.WSN中基于RSSI的加权质心定位算法的改进[J].电子测试，2012，1（1）：28-34.

[6]苟胜难.基于改进的RSSI无线传感器网络节点定位算法研究[J].计算机应用研究，2012，29（5）：1867-1869.