改进的无线传感器网络质心定位算法

胡必玲,仝 钰, 郭玉堂

(合肥师范学院 计算机学院，安徽 合肥 236032)

作为一种智能信息采集系统，传感器网络应用在许多领域，而提供事件发生的位置对于大部分应用来说都是系统必须满足的一项服务.传感器网络中事件发生的位置通常确定为检测到事件的传感器节点的位置.因此对传感器节点进行定位成为传感网应用中的基本问题[1].

无线传感器网络中的定位技术一般分为基于测距的定位和无需测距的定位两种.基于测距的定位通常需要对节点之间的角度数据或者距离信息进行测量，如接收信号强度(RSSI)[2]、信号传播时间(TOA、TDOA、RTOF)[3]等.此种定位算法一般能获得比较高的定位准确度，但定位过程中节点能量消耗较大，同时对网络的硬件设备要求较高，会增加网络计算量和通信成本.无需测距的定位一般基于节点间跳数信息、网络连通情况等实现节点自身定位，主要有质心定位算法[4]、DV-HOP 定位算法[5]、MDS_MAP[6]等.相比基于测距的定位，该类算法定位精度较低，但是由于不需要对未知节点与锚节点间的距离或者角度进行精确计算，降低了定位过程中节点能量的消耗和网络的硬件设备要求，减少了网络的计算量和通信成本，因而在实际应用中比较广泛.

本文针对传统质心定位算法中由于锚节点密度分布不均而引起的定位误差，提出了一种结合三角形内点测试和未知节点优化的质心定位算法.将所提出的算法与质心定位算法[7]、基于RSSI的加权质心定位算法[13]、增强的质心定位算法[14]进行对比，从而证明所提出算法的优势.

1 质心定位算法

在质心定位算法中网络的锚节点会向通信范围内的邻居节点周期性广播信标信号，其中包含自身位置信息和ID.未知节点根据一段时间内侦听到的来自锚节点的信标信号数量判断是否与此锚节点连通，并将所有和其连通的锚节点构成的多边形几何质心确定为自身位置.

假设与未知节点U相连通的锚节点有M1,M2,…,Mk,其坐标为(Xm1,Ym1), (Xm2,Ym2),…, (Xmk,Ymk)，未知节点的实际位置为(X,Y),其对自身的估计位置(Xest,Yest)，R为通信半径，则

Xest=(Xm1+Xm2+…+Xmk)/k，
Yest=(Ym1+Ym2+…+Ymk)/k.

(1)

定位误差率为E,其计算公式如下：

(2)

质心定位算法的特点是简单、计算量小，其计算过程完全依据网络的连通性，在锚节点分布均匀的情况下，会获得比较满意的仿真定位精度.但通常情况下锚节点分布较为随机，质心定位算法的定位结果会呈现较大误差.

2 相关改进工作

针对质心定位准确度低的问题，目前已有相关改进工作.文献[7]考虑到锚节点距离对节点定位的影响而引入接收信号强度对质心的位置进行加权计算；文献[8]利用质心定位算法获得未知节点估计位置后，又将未知节点通信范围内的所有其它未知节点的估计位置纳入考虑,得到首次估计位置和自身位置求和取平均值，作为自身最终的估计位置；文献[9]以初始连通信标节点与未知节点的地理位置关系确定算法的迭代收敛条件, 然后通过N个连通信标节点的坐标及其与未知节点间的接收信号强度计算当前连通信标节点所围成的区域质心的坐标及其与未知节点间的距离,并用计算得到的质心节点替代与未知节点距离最远的连通信标节点,缩小未知节点的所在区域,同时进行多次迭代以此提高节点定位精度;文献[10]应用人工鱼群算法对质心定位进行优化，将参考节点的位置和信号接收强度计算出的距离和作为适应度函数,虽然提升了定位准确性,但是增加了计算量；文献[11]基于RSSI测距技术计算传感器各节点之间的距离，然后构建以未知节点坐标为参数的数学模型，模型的建立以距离未知节点最近的3个锚节点和已定位节点为基础，求解时在PSO算法的基础上利用混沌优化思想避免搜索过程陷入局部极小，结合鸡群算法进一步优化.

3 优化的质心定位算法

3.1 算法基本思想

质心定位算法中如果未知节点通信范围内存在的锚节点个数较少或分布不均，则未知节点不位于由锚节点构成的几何图形范围之内会导致定位效果偏差较大.为提升锚节点随机分布情况下的定位精度，提出了一种结合三角形内点测试(PIT)和通信范围内已定位未知节点的优化质心定位算法，如图1和图2所示.

图1 优化的质心定位算法定位图例(1)

图2 优化的质心定位算法定位图例(2)

优化质心定位算法的核心思想是:未知节点首先获取自己通信范围内的锚节点数量，若不低于3个，则任选3个锚节点构成三角形，并进一步判定自己是否位于此三角形内；如果未知节点处于n个由其通信范围内的锚节点组成的三角形范围之内，则用每个三角形锚节点的信号强度进行加权得出每个三角形质心，取所有质心的平均值作为自己的位置;如果未知节点获取到的通信范围内锚节点的个数小于3个或不处于任一锚节点所组成三角形范围内，则增加其通信范围内已经定位的未知节点作为新的锚节点，继续判定其位于哪几个三角形范围内，取三角形质心的平均值为其位置.如果未知节点不处于任一由其通信范围内的锚节点和已定位的未知节点组成的三角形范围之内，则取其通信范围内的所有锚节点和已经定位的未知节点坐标的平均值作为其位置；如果引入已定位未知节点(新的锚节点)后，周围的锚节点个数仍小于3个，则该未知节点不能被定位.

图1中U1为待定位的未知节点,M1、M2、M3和M4为在U1通信范围内的锚节点,依据质心定位算法U1对自身的估计位置为M1、M2、M3和M4的几何质心，即E1点.在优化的质心定位算法中，U1首先确定自己处于由三角形M1M3M4和三角形M2M3M4范围之内，然后取两个三角形的加权质心平均值E点作为其估计位置.从图中可以看出采用优化的质心定位算法得到的位置E比原质心算法更接近真实位置.

图2为未知节点不处于其通信范围内的锚节点所组成的任一三角形范围之中.同样，U1为待定位的未知节点,M1、M2和M3为在U1通信范围内的锚节点,依据质心定位算法定位U1的估计位置为M1、M2和M3的几何质心，即E1.利用优化的质心定位算法，U1判定自己并不属于其通信范围内的3个锚节点组成的三角形范围之内，于是和其通信范围内的另外两个未知节点交换信息，得到估计位置E2和E3，可以判断出自己处于三角形M1M3E2、M1E2E3、M2M3E2、M2E2E3范围之内，取4个三角形的质心平均值点E作为自己的估计位置.从图2中可以看出采用优化的质心定位算法得到的位置E更接近真实位置.

3.2 算法流程

步骤1：每个未知节点搜索自己通信范围内的锚节点，判断节点数量是否大于3，如果大于3转步骤2，否则转步骤4；

步骤2：任意组合3个锚节点形成若干个三角形，判断未知节点是否至少处于一个三角形中，并统计个数，如果是，转步骤3，否则转步骤4；

步骤3：根据接收信号强度对各个三角形的加权质心进行计算，并求平均值，作为未知节点坐标；

步骤4：未知节点搜索其通信范围内已被定位出的其它未知节点，将这些节点设置为新锚节点使用.继续判断锚节点个数是否超过3个，如果超过3个，转步骤5，否则转步骤7；

步骤5：任意选取3个锚节点(包括其通信范围内的锚节点和已经被定位的其它未知节点)组成三角形，判断未知节点是否至少位于一个三角形中，如果是，转步骤3，否则转步骤6；

步骤6：未知节点取其通信范围内的所有锚节点和已经定位的未知节点坐标的平均值作为其位置；

步骤7：未知节点通信范围内锚节点和新增锚节点(已经定位的未知节点)个数小于3，节点不能被定位；

步骤8：将整个网络范围内所有未知节点的定位误差求和取平均值作为网络的总体定位误差.

为了对优化的质心定位算法有个清晰的描述，图3给出了算法的流程图.

图3 算法流程图

4 仿真实验及结果分析

为了测试本文算法在定位方面的性能，利用matlabR2014b将其与质心定位算法、RSSI加权质心定位算法、增强的质心定位算法进行仿真对比，讨论在相同的环境下，锚节点个数、通信半径、节点总数对不同定位算法性能的影响，使用定位误差率衡量各个算法的性能.

4.1 信号传播模型

最常用和简单的无线电信号传输模型是Regular Model.在 d0m 处的功率是 PL(d0)dBm,则在 dm 的功耗是：

(3)

其中，η定义为射频信道衰减指数，在自由空间一般取值为2，郊区或者城市中一般取值为3到6之间.然而由于传播介质和器件特性的因素，节点的信号强度在不同方向存在不可忽略的不规则性，(1)式所定义的模型较为理想，与实际测量的信号之间存在偏差.文献[12]介绍了无线电信号不规则(Radio Irregularity Model，RIM)模型，RIM模型是在简单的二进制不规则模型DOI的基础上提出的.在RIM模型中，作者引入了系数Ki表示不同方向的路径损耗，即Ki是第i个方向的系数，同时为了描述无线模型的不规则度，引入DOI参数.DOI定义为无线电传播方向上每单位度数变化的最大路径损失百分比变化，Ki的计算公式为：

(4)

RIM模型可用(5)式表示,式中Xσ表示信号衰减的固定部分.

(5)

本文的仿真实验使用这个更加精细的模型来评估定位算法的性能.

4.2 仿真环境参数

仿真环境参数如表1所列.

表1 仿真环境参数表

4.3 仿真结果

在仿真实验中，将传感器节点随机分布在1 000 m×1 000 m的区域,当传感器节点的总个数为300、锚节点比例为0.2、通信半径为200 m时，传感器网络中节点的分布如图4所示.其中锚节点用星号表示，未知节点表示为圆圈.节点邻居关系如图5所示.

图4 传感器节点分布图

图5 节点邻居关系

在部署区域内部随机散布300个传感器节点，通信半径为200，当锚节点的比例从0.1变化到0.3时，比较锚节点个数对定位误差率的影响.不同情况下的定位误差率结果如图6-图8所示.从图6可以看出，随着锚节点比例增加，传统质心定位算法，基于RSSI的加权定位算法和文献[8]所提出的增强质心定位算法以及本文算法的定位误差率都呈现下降趋势.其中传统质心定位算法的误差率在0.3 916～0.2 358之间，而本文算法定位误差率最低.增强质心定位算法在锚节点密度为0.15时定位误差开始大于传统质心定位算法，出现定位恶化情况.

图6 通信半径为200,节点总数为300的定位误差率

图7 通信半径为200,锚节点比例为0.2的定位误差率

图8 锚节点比例为0.2，节点总数为300的定位误差率

节点通信半径为200，锚节点的比例固定为0.2，比较节点总数从200变化到400时对定位误差率的影响如图7所示.从图7可以看出，随着节点总数增加，以上几种算法其定位误差率都在减少，当节点总数增加到250时，定位误差率趋于稳定，其中传统质心定位算法的误差率在0.3 373～0.2 673范围之间，本文算法定位误差率最低.

节点总数为300，锚节点比例为0.2，比较节点通信半径由100变化到300的过程中几种定位算法的误差率如图8所示.从图8可以看出，随着节点通信半径的增加，以上几种定位算法的误差率都在降低，但增强质心定位算法在通信半径为200左右时，定位误差开始大于传统质心定位算法，出现定位恶化情况.在通信半径为300时，传统质心定位算法的定位误差率为0.1 848，而文献[8]的定位误差率为0.2 661，本文算法误差率可降低到0.1 374，定位准确度明显提升.

5 结语

本文提出的优化质心定位算法结合三角形内点测试和通信范围内已定位的未知节点的坐标，实现对未知节点的定位，算法充分考虑了锚节点位置对未知节点定位的影响，与传统质心定位算法的不同之处在于：其首先对未知节点所处的区域进行判定，计算其所在的多个由锚节点所组成的三角形的质心平均值，将其作为未知节点的估计位置；在锚节点个数缺乏和判定出未知节点不处于任一锚节点所组成的三角形区域之后，将已定位的未知节点加入锚节点中，实现对未知节点进行定位.基于仿真实验结果可以看出本文所提出的算法在定位精度方面具有更好的精准率.