无线传感器网络质心算法定位参数研究与性能分析

邹东尧，李晨，韩腾飞

（郑州轻工业学院计算机与通信工程学院，郑州　450001）

无线传感器网络质心算法定位参数研究与性能分析

邹东尧，李晨，韩腾飞

（郑州轻工业学院计算机与通信工程学院，郑州450001）

0　引言

无线传感器网络 （Wireless Sensor Network，WSN）作为一种新型的网络技术近些年得到了很多研究者的关注，广泛应用在军事国防、目标跟踪、环境保护、医疗卫生、智能家居和精细农业等领域［1］。在无线传感器网络的定位应用中，是否能精确地获得节点的位置信息至关重要。如果无线传感器网络中所得到的感知数据，没有得到对应的位置信息，通常是没有实际意义的［2］。

WSN节点定位根据是否需要测量节点间距离和角度信息可将定位算法分为基于测距 （range-based）［3］和基于非测距（range-free）［4］。目前，基于测距的定位算法主要有TDOA、AOA、TOA、RSSI［5］等；典型的基于非测距的定位算法主要有质心算法、Amorphous算法［6］和DV-hop算法等。质心定位算法的设计相对简单而且对节点的计算能力要求较低，目前的研究及应用较为广泛。张爱清［7］等人提出一种基于最小包围的多边形定位算法，该算法以包围未知节点邻居锚节点的最小多边形质心作为未知节点的估计位置。刘峰［8］等人提出将接收到的RSSI值与网络划分区域相结合的方法，构成未知节点的估计区域从而进行节点定位。张军［9］等人提出了一种动态节点定位算法，由未知节点接收和保存三个点的分组信息循环组成三角形，同时依靠内点测试方法判断未知节点的位置，再通过质心算法进行定位。衣晓［10］等人提出了WCSA定位算法，根据对定位信息的影响对不同的锚节点赋予不同的权值，对不可定位节点和边缘节点引入次锚节点并进行二次定位。

现阶段，质心算法中对其本身参数的优化和改进研究相对较少。本文通过对影响质心定位算法定位精度的锚节点数目、通信半径R等参数进行实验仿真分析，然后对这些参数进行了优化。仿真实验结果表明，通过仿真分析和参数优化，可以达到提高算法定位精度的目的。

1　质心定位算法及算法应用模型

1.1质心定位算法介绍

20世纪中期，美国Bulusu教授［11］提出了质心定位算法。算法设计比较简单，仅根据网络的连通性就能得到未知节点的位置信息。质心定位算法的基本思想为：在一定的时间内，未知节点先寻找在自己通信范围内的信标节点，主要通过接收目标的成功率的方法，然后把所能接收到信息的锚节点组成的多边形的几何质心作为未知节点的估计坐标值。如图1所示：

图1　质心定位算法示意图

在质心定位算法过程中，首先所有信标节点向网络中广播包含自身的位置信息和信标号的信息分组。待节点广播信息分组结束之后，未知节点保存所能接收到的锚节点的信息分组，未知节点的坐标信息就是接收到的信标节点组所成多边形的几何中心，即是多边形的各个顶点位置坐标的平均值。设n个信标节点依次是P1（a1，b1），P2（a2，b2），…，Pn（an，bn），则未知节点的坐标可表示为：

质心定位算法的具体步骤：

（1）网络初始化，各个信标节点都会在一段时间内以广播的方式不停地在全网内发送自己的信息分组，信息分组包含自身的唯一ID标识信息和自身的坐标信息。

（2）当未知节点接收到广播的信息分组，保存对应信标节点ID标识和坐标信息。

（3）当未知节点接收到的锚节点发送的信息组数量超过某一门限值时 （假设为n），则未知节点的坐标（A，B）可由公式（1）计算得到。

在一般的定位过程中，未知节点可能会因为通信半径内邻居锚节点个数少于三个而无法定位。本文质心定位算法中将解决这一问题。未知节点完成定位后就自动升级为次级信标节点，当等到自己的邻居未知节点定位之后，没有邻居锚节点的未知节点就可以进行定位了。

1.2自由空间传播模型

本实验采用理想环境下的自由空间传播模型［12］进行实验，假设实验采用的是无方向性的天线，当接收天线增益GR和发射天线增益GT相同都为1时，距离d米处接收端天线所接收到的功率PR可表示为：

自由空间的传输损耗为：

当GT=GR=1时，自由空间的传输损耗可表示为：

公式（4）中，f为工作频率（单位为Hz）；d为收发天线间的距离（单位为m）；c为光波的传输速度（单位为m/s）。计算过程中，通常取频率f的单位为MHz，距离d的单位为km，此时公式（4）可改写为：

这里信号的传输损耗，实际上指电磁波在远距离的传输过程中，电磁波的能量会自然扩散，能量因扩散而产生的损耗跟电磁波的频率f和传播距离d密切相关。实际上接收天线所捕获的信号能量只是发射机天线发射的一小部分，大部分能量都扩散掉了。

2　质心定位算法参数

2.1节点通信半径

在定位过程中，如果节点通信半径变大而数量不变，则节点的能耗自然将会变大。图2中N为未知节点，m1，m2，m3为信标节点，Ra为变化之前的半径、Rb为变化后的半径。A1点为当半径为Ra时，由节点m1，m2得到的N的估计位置；A2点为当半径变化为Rb时，由节点m1，m2，m3得到N的估计位置。

图2　通信半径变大，定位误差变小

从图2可以看到未知节点的定位误差易受网络中锚节点的分布情况和节点通信半径大小的影响。当通信半径从Ra变化为Rb时，在图2中，未知节点N的估计位置由A1变为A2，定位误差有所减小；相反在图3中，未知节点N的估计位置由A1变为A2，未知节点的定位误差却有所增大。因此，通信半径对定位误差的影响要根据所在网络信标节点的分布情况去判断，之间没有相对应的函数关系。

图3　通信半径变大，定位误差变大

2.2锚节点数量

质心定位算法是把未知节点所有能接受到信息分组的信标节点组成的多边形的质心作为未知节点的位置，因此，锚节点数量的增多可以提高未知节点的定位精度，但同时也会增加节点间的通信开销，这也使得节点间的资源的消耗有所增加。另外，定位时随机生成未知节点和锚节点的分布位置，当锚节点彼此之间的距离很近时，特别是在或者近似在一条直线上，对定位精度影响很大。

3　参数仿真研究及结果分析

通过本文第2节的分析可知，网络中节点的分布情况、锚节点个数和通信半径等参数都会对算法的定位精度产生影响。如图4所示，图4中o号表示未知节点，*号表示信标节点。实验中锚节点和未知节点随机分布在100m×100m的网格区域内，依次改变上述参数信息，从实验结果中研究分析得出最佳参数。

当锚节点的个数和节点的通信半径不同时，节点的定位误差没有呈现出一定的规律性。实验中节点总数为100个，随机分布在100m×100m的正方形网格区域内，节点通信半径的依次取值为15m、25m、45m，锚节点个数在［2，28］之间变化。实验结果如下图所示：

图4　节点分布图

图5　节点总数为100个

从图5可以看出：在锚节点的数量在［2，14］之间变化时，节点定位误差减小的趋势较为明显；当个数在［14，28］之间变化时，节点定位误差的趋势趋近平缓。当通信半径不变时，锚节点个数为14个，节点定位误差为最优。当R=45m时，节点的定位误差是三个里面最大的。当R=15m和R=25m时，锚节点数量在［2，10］之间变化时，节点定位误差的趋势基本相同；当锚节点数量大于10个时，节点定位误差变动的趋势不明显。

为了研究通信半径对节点定位误差的影响，在100m×100m的无线传感器网格内，总节点数量设为100个，锚节点个数分别为6个、8个、10个、12个、14个，当通信半径从12m到50m的变化时，定位误差情况如图6所示。

从图6中可以看出：通信半径不变，随着锚节点数量的增加，节点的定位误差会相对降低；锚节点个数不同时，通信半径从12m到28m变化时，节点定位误差变化的趋势比较平缓，有的几乎没有变化，通信半径在28m处达到平均误差最优；通信半径大于28m时，通信半径越大造成定位误差越大，仿真实验结果表明：当总节点数为100时，R=28m为最优通信半径。

图6　定位误差图

为了得到最优仿真结果，我们进行了500次实验，并对每个点的取值进行平均。从图5和图6中可以看出：在100m×100m的无线传感器网格内，总节点数量为100个，当锚节点个数为14个，节点通信半径为28m时，节点的定位误差为最优值。

4　结语

本文首先介绍了质心定位算法的详细步骤及理想环境下的算法模型，其次分析了影响质心定位算法中定位精度的节点通信半径、锚节点个数等参数。经过仿真实验及分析表明：节点总数为100，随机分布在100m×100m的网格区域内，当锚节点个数为14个且通信半径为28m时，可使算法的定位精度达到最高值。

［1］史跃飞，冯秀芳，高昊.一种基于动态锚节点的改进加权定位算法［J］.计算机应用与软件，2013，30（10）：151-154.

［2］王焱，单欣欣，姜伟.无线传感网络中移动节点定位技术研究［J］.传感技术学报，2011，24（9）：1326-1330.

［3］梅举，陈涤辛玲.基于蒙特卡洛方法的移动传感网节点定位优化算法［J］.传感技术学报，2013，26（5）：689-694.

［4］HE Qin-bin，CHEN Fang-yue，CAI Shui-ming，et al.An efficient range-free localization algorithm for wireless sensor networks［J］. Science China Technological Sciences，2011，54（5）：1053-1060.

［5］邹东尧，郑道理，李晨.RSSI曲线拟合的误差分析与分段方法［J］.郑州轻工业学院学报（自然科学版），2014，29（2）：62-66.

［6］于海存，石为人，冉启可.基于虚拟静态锚节点的加权质心定位算法［J］.传感技术学报，2013，26（9）：1276-1283.

［7］张爱清，叶新荣，胡海峰.无线传感器网络质心定位新算法及性能分析［J］.计算机应用，2012，32（9）：2429-2431，2435.

［8］刘峰，章登义.基于RSSI的无线传感器网络质心定位算法［J］．计算机科学，2012，39（6）：96-98.

［9］张军，刘潜平.动态节点质心定位改进算法［J］.计算机工程与设计，2011，32（2）：446-449，538.

［10］衣晓，王梓有，薛兴亮.一种基于次锚节点的无线传感器网络质心定位算法［J］.计算机应用与软件，2013，30（6）：116-120.

［11］Bulusu N，Heidemann J，Estrin D．GPS-less low-cost outdoor localization for very small devices［J］．IEEE Personal Communication，2000，7（5）：28-34．

［12］程秀芝，朱达荣，张申等.基于RSSI差分校正的最小二乘-拟牛顿定位算法［J］.传感技术学报，2014，27（1）：123-127.

Wireless Sensor Network；Centroid Localization Algorithm；Positioning Error；Communication Range

Positioning Parameter Research and Performance Analysis for Wireless Sensor Network Based on Centroid Algorithm

ZOU Dong-yao，LI Chen，HAN Teng-fei
（College of Computer and Communication Engineering，Zhengzhou University of Light Industry，Zhengzhou 450001）

1007-1423（2015）20-0028-05

10.3969/j.issn.1007-1423.2015.20.007

邹东尧（1973-），男，河南许昌人，博士，副教授，研究方向为物联网定位、分布式网络

李晨（1991-），女，河南南阳人，硕士研究生，研究方向为物联网定位

韩腾飞（1987-），男，河南洛阳人，硕士研究生，研究方向为物联网定位

2015-05-05

2015-07-08

质心定位算法是WSN中一种典型的定位算法。首先对质心定位算法和自由空间传播模型进行分析，然后在网格中随机部署未知节点和锚节点，通过改变锚节点个数、节点通信半径等参数，研究其对节点定位误差的影响。实验结果表明，总节点数量一定时，锚节点数量和通信半径对定位精度存在较优值。

无线传感器网络；质心定位算法；定位误差；通信半径

河南省科技厅科技攻关项目（No.112102210321）、河南省产学研合作项目（No.122107000022）

Centroid localization algorithm is a typical algorithm in wireless sensor networks.Analyzes centroid localization algorithm and free space propagation model.Then distributes the unknown nodes and anchor nodes randomly in the grid，by changing the number of anchor nodes and communication range，analyzes the effects of the parameters like the number of anchor nodes and communication range on the positioning error.The test results indicate that when the total number of nodes is fixed，anchor nodes and communication range would optimize the positioning accuracy.