基于虚拟静态锚节点的加权质心定位算法*

于海存，石为人，冉启可，王开通

(重庆大学自动化学院，重庆400030)

无线传感器网络是由部署在监测区域内大量的廉价微型传感器节点组成，通过无线通信方式形成的一个多跳自组织网络。而随着数据业务和多媒体业务的快速增加，人们对定位与导航的需求日益增大。在室内目标定位和跟踪等应用中，无线传感器网络正好弥补了GPS卫星定位在室内难于获得准确位置信息的弊端［1］，可以为监狱、仓库、矿井、大型场馆等提供安全防护、人员跟踪等实时位置信息。

根据是否需要测量距离，无线传感器网络定位算法可分为基于测距(Range-Based)的定位算法和非测距(Range-Free)的定位算法［2］。前者是利用测量得到的距离或角度信息来进行定位计算;后者一般是利用网络的节点的连通性和多跳路由交换信息等方法来间接估计两点间的距离［3］。目前比较典型的基于测距的定位算法有 RSSI、TOA、TDOA、AOA［4］;基于非测距的定位算法有质心算法、APIT算法、DV-Hop 算法以及 MAP 算法［5－6］。

加权质心定位算法继承了质心算法运算较为简单的特点，并利用RSSI测距作为依据合理的分配权重，经过加权之后可以得到较高的定位精度［7］。该算法的缺陷是:为了达到较高的定位精度，往往需要布置数量较多的锚节点［8］，造成硬件成本的增加，大大限制了该算法在实际中的应用。针对该算法的缺陷，本文结合余弦定理，构造虚拟静态锚节点参与定位。仅需布置较少的锚节点就可以取得较高的定位精度，提高了加权质心算法的实用性。

1 加权质心算法

本节首先简要介绍目前应用最广泛的无线电磁波信号测距模型。第二部分内容是对加权质心算法进行数学分析，从导数的角度阐述了权重系数和RSSI测距在加权质心算法中的影响作用。第三部分内容着重分析布置锚节点数量较少的情况下，定位误差较大的原因。

1.1 无线电磁波信号RSSI测距模型

在自由空间中，最常用的无线信号传播模型是对数—常态分布模型［9］，距发射端d米处的天线接收到的信号强度由式(1)给出:

式(1)中，d为接收端与发射端之间的距离;d0为参考距离，一般取1 m;Pr(d)是接收端的接收信号功率;Pr(d0)是参考距离d0点对应的接收信号功率;Xσ是一个均值为0的高斯随机变量;β为路径损耗指数。通过测量接收信号的功率强度，利用式(2)可计算出信号发射端和接收端之间的距离:

1.2 加权质心算法分析

质心算法只单纯考虑了网络的连通度，未考虑锚节点与未知节点的远近程度对未知节点定位的影响［10］，故定位精度较低。显然，当某锚节点与未知节点距离越近时，该锚节点的坐标对未知节点的定位结果影响越大;反之，则影响越小。据此，运用权重的概念，令该值与锚节点到未知节点的距离的n次方成反比，利用权重值进行加权之后的质心定位算法可表示为［11］:

其中，Pi(x，y)为未知节点估计位置的坐标;Bj(x，y)为锚节点j的坐标;wij为锚节点j对未知节点i的权重值;n为权重系数，取值一般在1～4之间;dij为锚节点j到未知节点i的距离值;N为锚节点个数。

加权质心定位算法的关键在于如何合理分配权重值。由式(4)可知，加权质心算法权重只与两因素有关:权重系数和未知节点到各个锚节点的距离值。接下来将就这两因素分别分析它们对定位算法的影响作用。

1.2.1 权重系数变化对加权质心算法的影响作用分析

研究表明，权重系数n取值不同，定位结果也会有所差异，且在不同的子区域对应的最优权重系数也不尽相同［12］。

由式(3)可变换为式(5)和式(6):

Pi，j(x，y)表示锚节点 Bj(x，y)对最终定位结果的贡献大小。为了分析权重系数变化对Pi，j(x，y)的影响，对权重系数n求导可得:

假设未知节点到锚节点Bk(x，y)距离最近，到锚节点 Bm(x，y)的距离最远，即 dik=min(di1，di2，di3，…，diN)，dim=max(di1，di2，di3，…，diN)，则可得到式(8)、式(9):

即 Pi，k(x，y)的导数恒大于零，Pi，m(x，y)的导数恒小于零。所代表的物理意义是:随着n增大，距离未知节点最近的锚节点Bk(x，y)对最终定位结果Pi(x，y)的影响越大，Pi，k(x，y)相对于 Pi(x，y)所占的比例越大，未知节点的估计位置越接近于锚节点k;距离未知节点最远的锚节点Bm(x，y)对最终定位结果Pi(x，y)的影响越小，Pi，m(x，y)相对于 Pi(x，y)所占的比例越小，未知节点的估计位置越远离锚节点m。当系数n减小时，亦可以推导出与上相反的结论。

1.2.2 RSSI测距变化对加权质心算法的影响作用分析

类似的，当要研究未知节点到某一锚节点距离变化对该锚节点权重值的影响时，就要把权重系数当作常量，距离值当变量。这里假定锚节点k到未知节点i的距离dik减小，推导Pi，k(x，y)的变化。由式(6)中1/dik求导可得:

即 dik减小，1/dik增大，而 P'i，k(1/dik)恒大于零，故可得到 Pi，k(x，y)增大，Pi，k(x，y)相对于 Pi(x，y)所占的比例越大，未知节点的估计位置越接近于锚节点k。

1.3 锚节点数量较少导致定位误差较大的原因分析

覆盖一个矩形的平面定位区域最少需要布置四个锚节点，接下来就以锚节点布置数量最少为应用背景分析在此情况下加权质心算法出现定位误差较大的原因，如图1所示。

图1 权重系数作用分析

情形1:未知节点位于O1时被定位在O'1，定位误差较小，原因是锚节点B2距离O1很近，分配的权重值远大于其他几个锚节点，故定位位置会非常接近锚节点B2。

情形2:未知节点位于O2时定位位置在O'2，误差较大，原因是缺少一个对定位结果起主导作用的锚节点。此时由于未知节点到锚节点B1、B2的距离与到锚节点B3、B4的距离差距不足以让锚节点B1、B2获得足够大的权重值。假设在未知节点O2附近增设一个能起主导作用的锚节点，该未知节点的定位误差就会减小，分析如情形1。

通过上面的分析，定位计算过程可以理解为多个锚节点之间的“博弈”过程，即在权重系数选取适当的前提下，多个锚节点之间根据RSSI测距合理分配权重的过程;适当增加锚节点数量，能有效的提高加权质心算法的定位精度。在下节基于VSAN的加权质心算法中，我们将结合该算法仿真结果进行更加具体的论述。

2 基于VSAN的加权质心算法

前文已经提到，锚节点布置数量较少时，必然会导致某些位置的未知节点定位误差较大，而限制加权质心定位算法在实际中应用的主要因素又恰好是定位所需的硬件成本较大，因此在满足所需定位精度的前提下如何减少锚节点的布置数量就变得非常具有意义。本文主要的研究思路是以虚拟锚节点替代部分真实锚节点参与节点，变相减少锚节点的布置数量。本节将详细阐述基于虚拟静态锚节点VSAN的加权质心算法的实现方法和算法流程。

2.1 增设VSAN的实现方法

加权质心算法的计算过程需要获取两部分信息，即各个锚节点的位置坐标和未知节点到各个锚节点的相应距离值［13］。因此，只要获得了某个锚节点的位置坐标以及未知节点到该锚节点的距离值，就等价于在物理空间布置了该锚节点并实现了该锚节点和未知节点之间的通信，而该锚节点并不一定是真实存在的。我们将具有这样功能的“节点”称之为虚拟静态锚节点VSAN(Virtual Static Anchor Node)。

基于VSAN的加权质心算法的核心思想是在定位区域布置少量真实的锚节点作为前提，通过间接方法获得虚拟静态锚节点的上述两种信息。虚拟静态锚节点的位置必须位于连接任意两个真实锚节点的直线上。未知节点到虚拟静态锚节点的距离值的获得主要由余弦定理计算完成。以在定位边界中点增加四个虚拟静态锚节点为例，原理图如图2所示。

图2 虚拟静态锚节点构造原理图

图2中，L1×L2的矩形平面代表定位区域，黑色信号发射源{B1，B2，B3B4}代表真实布置的锚节点，位置坐标已知;白色信号发射源{B5，B6，B7，B8}代表在该位置增设相应的虚拟静态锚节点;灰色标志物表示未知节点;{d1，d2，d3，d4}分别代表未知节点分别到四个真实锚节点的距离值，是根据式(2)求得，在图中用黑色实线表示;{d5，d6，d7，d8}则代表未知节点到四个虚拟静态锚节点的距离值，是利用{d1，d2，d3，d4}及真实锚节点的坐标值由余弦定理计算得出，在上图中用虚线表示;{α，β，θ}为上图中边集合{d1，d2，L1}组成的三角形的内角集合;Lx为图中矩形框左边界虚拟静态锚节点到矩形框上边界的距离值。根据上图2以及余弦定理，可得:

联立式(11)、式(12)可解得:

这里以虚拟静态锚节点布置在定位区域边界中点处为例，即Lx=L1/2

同样方法，可获得其他几个虚拟静态锚节点的坐标和到未知节点的相应距离值。

必须提及的是，虚拟静态锚节点到未知节点的距离计算结果与两者之间的实际距离同样是有误差的，但不代表该信息不是有用信息(实际布置的参考锚节点测距信息也同样包含误差，从测距结果是否包含误差这一点来说，实际布置的锚节点和虚拟锚节点是等效的)。事实上，每增加一个虚拟锚节点，便会增加一条信息，即该虚拟锚节点到未知节点的距离值。即便这个距离值是不准确的(测距值也不可能准确)，它对确定一个未知节点的位置也是有益的，因为它可以将未知节点位置确定在以虚拟锚节点为中心的一个大致范围内，当虚拟锚节点较多时，这些区域的重叠部分就是未知节点位置可能性较大的区域，这也是APIT定位算法的思想。进一步讲，从上节的数学分析可知，在加权质心算法中对定位精度影响最大的是距离未知节点最近的锚节点，且该锚节点距离未知节点越近，加权质心定位算法越容易得到较精确的定位结果。而在本文中构造了若干个虚拟静态锚节点，相当于增加了定位区域内的参考锚节点，使未知节点很容易找到一个距离自己“相对较近”的最近锚节点，而该锚节点拥有较大的加权权重，可以将未知节点的定位位置大致确定在该锚节点自身附近，即便考虑到误差的因素，该锚节点的信息仍能使未知节点的定位更加准确。

2.2 算法流程

增加了获取虚拟静态锚节点信息的环节，改进后的算法流程具体步骤如下:

步骤1:锚节点周期性地向定位区域发送有关自身的信息，包括:节点ID、自身位置坐标。

步骤2:未知节点接受锚节点发送的数据包，并对数据包进行解析和处理:建立锚节点集合{B1，B2，B3B4};由式(2)将 RSSI转化为距离，建立未知节点到相应锚节点的距离值集合{d1，d2，d3，d4}。

步骤3:由式(13)和锚节点集合{B1，B2，B3B4}得到合适的虚拟静态锚节点集合{B5，B6，…，BN};由式(13)得到未知节点到虚拟静态锚节点的相应距离值集合{d5，d6，…，dN}。

步骤4:由上面两步建立扩展后的锚节点集合{B1，B2，B3，B4，B5，B6，…，BN}和未知节点到相应锚节点的距离值集合{d1，d2，d3，d4，d5，d6，…，dN}。利用上述两个扩展后的集合信息，由式(3)和式(4)计算出未知节点位置坐标。

3 仿真及实验

3.1 VSAN算法仿真

3.1.1 仿真环境设置

为了验证本文算法的有效性，首先在MATLAB环境中进行仿真实验。为了更贴近实际环境，在测试中我们设置仿真区域为20 m×20 m大小的平面区域，并将四个锚节点放置在该区域的四个顶点处;在定位区域内划分1 m×1 m的网格，并将待定位的未知节点布置在网格连接点处，由此得到21×21总计441个未知节点使其能够密集覆盖整个待定位区域。假设未知节点的通信半径R=30 m，故在该仿真区域内不存在未知节点接收不到锚节点信息的现象。对于式(1)和式(2)表示的RSSI测距模型，为了尽可能的模拟真实环境，模型参数取如下数值:Pr=0 dBm，d0=1 m，β=2，Xσ=(0，4)，权重系数n在1～4之间取值。

3.1.2 仿真方案及结果

根据“增设”虚拟静态锚节点数量和布置位置的异同，设计4种不同的方案对比验证算法的有效性，分别是:“增设”0个虚拟静态锚节点、“增设”4个虚拟静态锚节点{B5，B6，B7，B8}、“增设”12 个虚拟静态锚节点{B5，B6，…，B15，B16}、“增设”17 个虚拟静态锚节点{B5，B6，…，B20，B21}。每一种方案相对应的算法分别简称为:0-VSAN算法、4-VSAN算法、12-VSAN算法、17-VSAN算法。虚拟静态锚节点的具体布置如图3所示。

图3 虚拟静态锚节点的布点方案

在上述布置方案中，人为的将定位区域划分为中心地带和边缘地带，如图3所示线条围成的区域划为中心地带{4≤x≤16，4≤y≤16}，其余区域为边缘地带。分别对上述4种方案做了多次重复仿真实验，每种方案对应若干个不同的权重系数值做仿真实验，每组计算441个(边缘区域272个，中心区域169个)未知节点定位误差信息，取十组平均值作为最后结果。在验证VSAN算法是否能有效提高定位精度的同时，观察权重系数n值的变化对加权质心算法定位结果造成的影响，包括对区域整体定位误差的影响、中心地带定位误差的影响、边缘地带定位误差的影响。仿真结果如图4、图5所示。

图4 不同n值下的整体定位误差曲线

图5 VSAN算法

根据仿真数据建立实验数据如表1所示。进一步研究基于VSAN的加权质心算法在同一权重系数下，定位区域中心地带和边缘地带的定位特性，4种VSAN算法在不同区域得到的仿真图如图5所示。

表1 VSAN算法仿真数据

根据仿真数据建立实验数据如表2所示。

表2 VSAN算法在不同区域的仿真数据

3.1.3 仿真结果分析

由表2可知，0-VSAN算法在n=1.8时定位效果最好，误差为2.01 m;4-VSAN算法在n=2.3时定位效果最好，误差为1.68 m;12-VSAN算法在n=2.6时定位效果最好，误差为1.60 m;17-VSAN算法在n=3.2时定位效果最好，误差为1.55 m。3种“增设”了虚拟静态锚节点的算法定位误差相比0-VSAN 算法分别降低了 0.33 m、0.41 m、0.46 m，精度分别提高了 16.4%、20.4%、23.4%。说明本文提出的算法能够在不增加锚节点数量的前提下，达到实现提高定位精度的目标。

上述4种算法在中心地带能够取得的最小的定位误差分别为 1.47 m、1.53 m、1.48 m、1.43 m，定位误差差别很小。“增设”虚拟静态锚节点对中心地带定位效果影响甚微。

上述4种算法在边缘地带能够取得的最小的定位误差分别为 2.35 m、1.75 m、1.51 m 和 1.61 m。4-VSAN算法、12-VSAN算法、17-VSAN算法相比0-VSAN算法在边缘地带的定位误差分别减少了0.60 m、0.84 m 和0.74 m。由此可见，基于虚拟静态锚节点的改进定位算法实际上提高的是边缘地带的定位精度。

如表1所示，虚拟静态锚节点越多，定位精度越高，但每次的增幅却在逐渐减小。如图4所示，4-VSAN算法的定位误差相较于0-VSAN降低了0.33 m，12-VSAN算法相较于4-VSAN的定位误差只降低了0.08 m，17-VSAN算法相较于12-VSAN定位误差只降低了0.05 m。可以预计，“增设”更多的虚拟静态锚节点对定位精度的提高作用会越来越小，故对这种情况不再继续研究。

3.1.4 权重系数特性分析

观察图5及表2可以总结出，随着“增设”虚拟静态锚节点数量的增多，VSAN定位算法权重系数的特性有一定的变化规律:①虚拟静态锚节点越多，对应算法的最优权重系数n越大。0-VSAN对应最优n值为1.8，4-VSAN 最优 n 值为 2.3，12-VSAN 最优 n 值为2.6，17-VSAN对应的最优n值为3.2，这种对应的变化趋势绝对偶然。我们可以利用本文证明的式(6)～式(9)推导出的结论加以解释:“增设”了虚拟静态锚节点后，总的锚节点数量N变大，在权重系数n值不变的情况下，式(6)中分母变大、分子不变，结果是Pi，j(x，y)变小。由前文可知，对于距离未知节点最近的锚节点Bk(x，y)对最终定位结果Pi(x，y)的影响最大，所以Pi，k(x，y)的减小使得在原有最优权重系数n不变的情况下得不到最优的定位效果。根据式(8)和式(9)，可行的调整方法就是增大权重系数n的值，使得 Pi，k(x，y)变大，Pi，m(x，y)变小，从而再次改善定位效果。逐渐增大n值，当定位误差最小时便可确定此时对应的n值为最优权重系数，继续增大n值，定位误差反而会增大。②由表2可得到上述4种方案一个共同点:边缘地带对应的最优权重系数n总是大于中心地带对应的最优权重系数n。这种现象仍然可以由式(6)～式(9)来解释:边缘地带为了取得较好的定位效果，就要相对性的增大n值，确保距离未知节点最近的锚节点能获得足够大的权重;而在中心地带，各个锚节点到未知节点之间的距离差距不大，如果n值较大，就会使本来较小的距离差距过度放大，导致定位位置过于趋进锚节点Bk(x，y)，中心地带的未知节点就可能因此被定位在边缘区域。

因此，对基于VSAN的加权质心算法进行下一步改进的思路是在定位区域中心地带和边缘地带分别对应各自的最优权重系数进行定位计算。

3.2 VSAN算法实验

3.2.1 实验环境设置

为验证基于VSAN的定位算法在实际环境中的有效性，以12-VSAN算法为例(边缘地带定位误差最小)，采用6个通信模块为cc2510的传感器节点组成小型无线传感器网络，用于进行室内定位实验。定位区域限定在重庆大学主教学楼裙楼一块大小为10 m×10 m的平面区域。4个传感器节点作为已知坐标的锚节点，布置在定位区域的各个顶点处;1个节点作为待定位的未知节点，布置在定位区域内某一点进行定位;另外采用一个节点作为Sink节点与控制后台连接，负责向锚节点和未知节点发送控制参数，并将未知节点定位信息通过串口线送到控制后台进行处理。实验步骤参见上节算法流程。锚节点的坐标分别预设为 B1(0.0，0.0)、B2(0.0，10.0)、B3(10.0，10.0)、B4(10.0，0.0)。定位过程中每一组定位数据用0-VSAN和12-VSAN两种算法分别计算定位坐标。0-VSAN算法权重系数取值为1.8，12-VSAN算法权重系数取值为2.6，具体布置如图6所示。

图6 现场实验布置

3.2.2 实验结果及分析

实验数据经统计后整理成表4和表5所示。

实验得到的12-VSAN算法的平均定位误差是1.65 m，略大于仿真得到的平均定位误差1.60 m;0-VSAN算法计算所得平均定位误差为2.16 m，略大于仿真得到的定位误差2.01 m。对此的解释是:定位区域越大，定位误差也就越大。考虑到仿真环节定位区域较大，实验环节定位区域较小，所以仿真结果和实验结果接近也是合理的。12-VSAN算法的平均定位误差相较于0-VSAN算法减小了0.51 m。再一次说明了基于VSAN的加权质心定位算法的有效性。

涉及的相关定位算法比较如表6所示。

表4 0-VSAN算法实验数据

表5 12-VSAN算法实验数据

表6 算法比较

4 总结

本文结合余弦定理，利用原有的锚节点定位信息构造出虚拟静态锚节点VSAN参与定位。该算法继承了加权质心算法实现简单、复杂程度低的特点，在不增加锚节点布置数量的前提下提高了加权质心算法的定位精度，在一定程度上解决了以往由于硬件成本过高而使得加权质心定位算法难以在实际中应用的难题。此外，对加权质心算法进行数学推导和分析，从导数的角度阐述了权重系数和RSSI测距对加权质心算法的影响作用。仿真和实验结果表明，基于VSAN的加权质心算法所需布置锚节点较少、定位精度较高，完全能够应用在工程实践中。下一步的改进思路是在定位区域中心地带和边缘地带分别对应各自的最优权重系数进行定位计算。

参考文献:

［1］吴晓平，谈士力，胡军国.基于残差修正法的无线传感器网络定位技术［J］.传感技术学报，2012，25(7):1014－1018.

［2］邓彬伟，黄光明.无线传感器网络移动节点辅助定位算法［J］.仪器仪表学报，2011，32(3):563－570.

［3］Rudafshni M，Datta S.Localization in Wireless Sensor Networks［C］//Information Processing in Sensor Networks(IPSN)，2007:51－60.

［4］Bahl P，Padmanabhan V N.RADAR:An in Building RF-Based User Location and Tracking System［C］//Proceedings of the IEEE Infocom 2000.Tel Aviv:IEEE Computer and Communications Societies，2000.775－784.

［5］Yi Shang，Ruml W，Ying Zhang.Localization from Mere Connectivity［C］//Mob Hoc’03，Annapolis，Maryland，USA，2003:201－210..

［6］李牧东，熊伟，梁青.基于人工蜂群改进算法的无线传感器网络定位算法［J］.传感技术学报，2013，26(2):241－245.

［7］王焱，单欣欣，姜伟.无线传感网络中移动节点定位技术研究［J］.传感技术学报，2011，24(9):1326－1330.

［8］许磊，石为人.一种无线传感器网络分步求精节点定位算法［J］.仪器仪表学报，2008，29(2):314－319.

［9］Alippi C，Vanini G.Wireless Sensor Networks and Radio Localization:A Metrological Analysis of the MICA2 Received Signal Strength Indicator［C］//Proceedings of the 29th Annual IEEE International Conference on Local Computer Networks(LCN’04)，Italy，2004:16－18.

［10］Yi Shang，Ruml W，Ying Zhang.Localization from Mere Connectivity［C］//Mob Hoc’03，Annapolis，Maryland，USA，2003:201－210..

［11］陈维克，李文锋，首珩.基于RSSI的无线传感器网络加权质心定位算法［J］.武汉理工大学学报，2006，20(12):2695－2700.

［12］詹杰，刘宏立，刘述钢，等.基于RSSI的动态权重定位算法研究［J］.电子学报，2011，39(1):82－88.

［13］Lim C B，Kang S H，Cho H H.An Enhanced Indoor Localization Algorithm Based on IEEE 802.11 WLAN Using RSSI and Multiple Parameters［C］//2010 Fifth International Conference on Systems and Networks Communications.2010:238－242.