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

梁建国，傅游

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

梁建国，傅游

在深入分析研究质心定位算法原理的基础上，通过提高邻居锚节点的比例以及加权质心定位算法对其定位性能进行改进，仿真结果表明，改进后的质心定位算法，比改进前的质心定位算法的定位率提高了约 20%，定位误差增大了约 5m。

无线传感器网络；质心定位算法；定位率

0 引言

节点定位是无线传感器网络关键技术之一[1]，对无线传感器网络的应用如目标跟踪、生态环境监测等方面起着重要的作用[2]。无线传感器网络定位方法分类较多，目前最普遍的是根据定位过程中是否需要测距[3]，将其定位方法分为基于测距[4]和无需测距定位方法两种[5]。无需测距的定位方法与基于测距的定位方法相比，虽然定位精度偏低，但对节点的硬件需求不高，能适应多数无线传感器网络的定位需求，一直是大家关注的热点。无需测距的定位算法主要有质心定位算法[6]、凸规划定位算法[7]、DV-Hop（Distance Vector-Hop）定位算法[8]和 APIT（ApproximatePoint-In-Triangulation Test）算法[9]等。

1 质心定位算法介绍

质心定位算法的具体过程为：在质心定位算法中，锚节点每隔时间 t就向邻近节点广播信标分组，信标分组中包含了锚节点的标识号和位置信息，当未知节点接收到来自不同锚节点的信标分组数量超过某一个设定值或接收一定时间后，就把这些锚节点所组成的多边形的质心确定为自身位置为[10]。如图1 所示：

图1 质心定位算法示意图

如果未知定位节点的坐标为(X,Y)，n 个锚节点的坐标分别为 A1(x1, y1)，A2(x2, y2)，…， An(xn, yn)，则其坐标的平均值就是未知节点的近似坐标，见公式（1）：

通过分析可知，质心定位算法完全基于网络连通性，算法结构简单，易于操作，但该算法定位精度较低。另外，该算法还存在两方面的问题，一是在锚节点数量较低的情况下，质心定位算法的定位率偏低；二是质心定位算法只是对未知节点周围的锚节点进行简单的平均值，对不同位置的锚节点对定位精度的作用不同体现的不明显。为此一方面通过提高未知节点的锚节点数量来提高质心定位算法的定位率，另一方面通过引入加权的思想来体现不同锚节点在定位中的作用不同，从而达到提高定位精度的目的。

2 改进的质心定位算法的提出

2.1 提高邻居锚节点数量

在质心定位算法中，若周围没有锚节点，未知节点将无法实现定位。在质心定位算法中，未知节点只把节点通信范围内的锚节点作为邻居节点，然后通过邻居锚节点所围成多变形的质心定位为自己的坐标。但在实验过程中发现，有些节点虽然不在未知节点的通信范围之内，但是它还是可以作为邻居锚节点的如图2所示：

图2 锚节点选择示意图

对于未知节点A来说，锚节点B在节点通信半径r内，因此被视作节点A的邻居锚节点，但是锚节点C由于不在通信范围内，故不能视作节点A的邻居锚节点，但实际上，锚节点C与锚节点B之间的距离相差很小，在一定程度上可以升级为未知节点 A的邻居锚节点。为此，将原来算法中只用1跳范围内的锚节点进行定位改为了使用2跳范围内的锚节点进行定位，通过提高未知节点的邻居锚节点的比例达到了提高未知节点定位率的目的。

2.2 加权质心定位算法

扩大通信范围在很大程度上可以提高节点的定位率，但是其定位误差也会随之增大，为此，将通过加权质心定位算法减小定位误差，改进步骤如下：

步骤1：在用上述所描述的方法找到未知节点的邻居锚节点的基础上，对邻居锚节点进一步选择，判断1跳范围内是否存在锚节点，如果存在则选择1跳范围内的邻居锚节点进行定位，否则选择大于1跳小于2跳范围内的邻居锚节点。

步骤2：用传统质心定位算法对未知节点进行定位。步骤3：在以上两步的基础上，进行节点的定位计算，如图3所示：

图3 改进质心定位算法示意图

U，U′分别为未知节点和传统质心定位算法估算出的U 点的位置，A，B，C，D，E，F 为未知节点 U 的邻居锚节点。首先分别计算每个邻居锚节点到U′的距离；其次根据计算的距离为每个邻居锚节点赋予不同的权重，使距离U′点远的邻居锚节点获得较小的权重，较近的邻居锚节点获得较大的权重；最后重新计算未知节点的 U的坐标，多次迭代，使未知节点U的坐标更加准确。

2.3 改进的质心定位算法提出

设网络中未知节点的标识为 i，坐标信息为 U=(x, y)，传统质心定位算法估算的坐标信息 U′=(xi, yi)，网络中邻居锚节点有 n 个，其坐标为 Zj=（xj, yj）, j=1，2，3，…n，记 n 个邻居锚节点组成的集合为 M={Z1，Z2，…，Zn}。则改进质心定位算法的伪代码如下：

begin

if In the collection M,there are anchor nodes within 1 hop,

Select the anchor nodes within 1 hop from M, they

are grouped into the collection T, the number is m.

if (m＜2)

Estimate the value by centroid localization algo

rithm.

else

Estimate the value by centroid localization algo

rithm U′=(xi, yi).

for k=1:m

Calculate the distance between U′ and Tk,

they will be grouped into the collection E,

Calculate the weight coefficientis a small (negligible)

value, they will be grouped into the collection F.

end for

Use the elements in the collection T and F, using the weight centroid localization algorithm calculate the coordinates of the unknown node, the formula is

end if

else

Select the anchor nodes within 2 times the communication radius, the number is m, the collection is T from M.

if (m＜2)

Estimate the value by centroid localization algorithm.

else

Estimate the value by centroid localization algorithm U′=(xi, yi).

for k=1:m

Calculate the distance between U′ and Tk, they will be grouped into the collection E, the formula is

Calculate the weight coefficientvalue, they will be grouped into the collection F.

end for

Use the elements in the collection T and F, using the weight centroid localization algorithm calculate the coordinates of the unknown node, the formula is

end if

end if

end

3 仿真实验及分析

为了能够更客观、准确的模拟出改进前后质心定位算法的真实性能，在仿真时，所有节点包括锚节点和未知节点均在网络区域中随机生成。

仿真参数的设置如表1所示：

表1 仿真参数设置

节点总数 100仿真次数总计 100 次生存周期 TTL 15

由表可知，所有数据的产生都是对网络运行仿真 100次求得结果的平均值。生存周期 TTL 值为 15，即限制锚节点数据包仅传播 15 跳，定位性能仿真过程中，使用平均定位误差和定位率作为定位算法的定位性能的衡量指标。

如图4所示：

图4 无线传感器网络拓扑结构图

无线传感器网络的拓扑结构图，网络区域范围是 100m ×100m，网络中所有节点随机分布，圆圈节点为未知节点，星型节点为锚节点。

(1)锚节点个数对定位性能的影响

如图5所示：

图5 不同锚节点数下定位性能对比

锚节点个数从 3变化到 30时，改进前、后的质心定位算法的定位性能变化图，这里选择节点通信半径为 25m。可以看出，当节点总数与节点通信半径不变时，改进前后的定位算法的平均定位误差都随着锚节点数量的增加而减小，在锚节点数量从 3变化到 10时，改进前比改进后的平均定位误差低，但是它的定位率比改进后质心定位算法低，当锚节点的数量增加到 15以上时，两种定位算法的平均定位误差变化较小。

(2)节点通信半径对定位性能的影响如图6 所示：

图6 不同节点通信半径下定位性能比较

图6(a)、(b)和(c)给出了节点通信半径从 20 变化到 40，锚节点个数分别为 5、10 和 20 时，改进前、后质心定位算法的定位性能比较。从中可以看出，改进后比改进前的质心定位算法定位率提高了20%左右，定位误差减低了5m左右。

4 结论

本文在分析质心定位算法的基础上，从两方面对原质心定位算法进行改进，仿真结果表明，改进的质心定位算法在无需额外增加硬件设施开销的条件下，比改进前的质心定位算法的定位率提高20%左右，但是定位精度减低了5m左右。相比改进前的质心定位算法，本文提出的算法虽定位精度有所减低，但是其定位率却增加了很多，在实际应用中还是非常有价值的。

[1]蔡玲,周力.定位算法在传感器网络中的改进策略[J].通信技术,2011,44(04):93-96.

[2]Huang Tao, The Internet of Things Research & Dev elopment. Beijing: 2009.www.chinaunicom.com/upload /1277100691962.pdf.

[3]Chen Min Xiou, Wang Yin Din. An Efficient Locati on Tracking Structure for Wireless Sensor Networks [J]. Computer Communications,2009, 32: 1495- 1504.

[4]杨凤,史浩山,朱灵波,等.一种基于测距的无线传感器网络智能定位算法[J].传感技术学报,2008,21(01): 135-14 0.

[5]王福豹,史龙,任丰原.无线传感器网络中的自身定位系统和算法[J].软件学报,2005, 16(05):857-868.

[6]QinBin He, FangYue Chen, ShuiMingCai,JunJunHao, ZengRong Liu. An efficient range-free localization al gorithm for wireless sensor networks[J].SCIENCE CH INA Technological Sciences 2011,54(5): 1053-1060.

[7]NirupamaBulusu, John Heidemann. GPS-less Low-cos t Outdoor Localization for Very Small Devices. [J]IE EE Personal Communications: 2000,7(5):28-34.

[8]李成岳.基于 DV-Hop 的无线传感器网络节点定位算法研究[D]. 长春:吉林大学,2011.

[9]HET, HUANG C, BLUMBM,etal. Range-Free Local ization Schemes in Large Scale Sensor Network s[C]//Proceedings of the 9th Annual International Conference on Mobile Computing and Networki ng.California, USA:ACM Press, 2003: 81-95.

[10]李文辰,张雷.无线传感器网络加权质心定位算法研究[J].计算机仿真,2013,30(2),191-194.

Improvement Research on Centroid Localization Algorithm in Wireless Sensor Network

Liang Jianguo1, Fu You2
（1.Department of Computer Science, Qingdao Harbor Vocational & Technical College，Qingdao, Shandong266404,China; 2.College of Information Science andEngineering , SUST, Qingdao, Shandong266510, China）

Based on profound analysis and research about the principle of centroid localization algorithm, The positioning performance is improved by improving neighbor anchor node proportion and using weighted centroid localization algorithm. The simulation results show that the improved Algorithm increased its Position ingrate by about 20 percent and positioning error by about 5m.

Wireless Sensor Network; Centroid Localization Algorithm;Positioning Rate

TP393

A

1007-757X(2014)02-0009-03

2014.02.25)

山东省高等学校科技计划项目（J11LG22）;青岛经济技术开发区重点科技发展计划项目（2012-2-48）;青岛港湾职业技术学院科研项目（QDGW2013802）；

梁建国(1981-)，男，青岛港湾职业技术学院计算机科学系，讲师，硕士研究生，研究方向：计算机网络，青岛，266404.傅 游(1968-)，女，山东茌平人，教授，博士，研究方向：并行编译技术、分布/并行处理与高性能计，青岛，266510.