无线传感器网络距离约束定位算法

张松涛 田钧 宋树祥

摘 要： 为克服稀疏信标结点和测距误差问题，提出了一个距离约束定位算法。该算法先借助多跳以外的信标结点进行传感器结点初始位置估算；然后利用直接邻居信息进行结点位置迭代更新。为了提高定位准确性，新算法引入了一些改进措施。在初始位置估算阶段，引入合理的可信度权值因素。在结点位置迭代更新阶段，只选择部分可靠邻居结点用于邻居结点距离检测，并有选择性地用上次迭代结果作为最新定位结果。仿真结果表明，与以前算法相比，新算法能降低定位误差。

关键词： 无线传感器网络； 定位； 距离约束； 迭代

中图分类号：TP393 文献标志码：A 文章编号：1006-8228（2015）09-08-04

Distance constraint localization algorithm in wireless sensor network

Zhang Songtao1， Tian Jun1， Song Shuxiang2

（1. Dept. of Electronic and Information Engineering， Foshan Polytechnic， Foshan， Guangdong 528137， China；

2. College of Electronic Engineering， Guangxi Normal University）

Abstract： In order to overcome the problem of sparse anchors and ranging error， a distance constrained localization algorithm is proposed. In this algorithm， the initial position of sensor nodes is estimated by using the anchors beyond the multi-hop， then the position of sensor nodes is updated by using the direct neighbor information. In order to improve the accuracy of localization， the new algorithm introduces some improvement measures. In the initial position estimation stage， the reasonable reliability weighting factor is introduced. In the node position iteration， only some selected reliable neighbor nodes are used to detect the distance to neighbor nodes， and the results of the last iteration are selectively used as the most recent results. Simulation results show that the new algorithm can reduce the localization error compared with the previous algorithms.

Key words： wireless sensor network； localization； distance constraint； iteration

0 引言

由大量传感器结点协同合作构成的无线传感器网络，在工农业控制、军事国防、生物医疗、环境监测、抢险救灾等诸多领域有着广泛的应用前景[1-2]。各结点感知数据、传回数据，并在中心结点进行分析处理，成为各种应用的一种基本途径。所以，没有位置信息的测量数据会造成中心结点或中央处理器不知道测量数据发生的精确地点或大致范围，使测量数据失去意义。而且，各结点的位置信息有助于网络数据融合[3]、路由[4]、覆盖[5]等算法的改善。

在一个传感器网络中，通常只有一小部分结点采用全球定位系统GPS技术或其他方式获得结点自身位置信息（这部分结点我们称为信标结点），其他绝大多数普通结点没有自己的位置信息。估算普通结点的位置正是传感器网络定位技术要解决的问题。

对于一个平面网络，某未知结点如果知道三个参考结点的位置和到相应参考结点的测量距离，就可以运行基本的三边测量定位算法，估算出自身位置坐標。但使用通常的距离测量方法，测量结果会产生不同程度的误差，对定位结果产生不利影响。因此，如何克服距离测量误差的影响成为传感器网络结点定位技术挑战性工作之一。定位技术的另一个难题是，由于多方面的原因，网络中信标结点的数量较少。一个普通结点只有很小的可能性，能有三个或以上邻居结点为信标结点，从而运行基本三边测量定位算法来估算出自身位置。

为了改善上述稀疏信标结点和测量误差问题，本文提出一种可靠邻居结点距离约束定位算法（Distance Constraint Refinement with Credible Neighbors，DCRCN）。该算法以经典定位算法Hop-terrain[6]为基础，采取有效策略控制结点位置迭代更新，以提高结点定位准确性和定位结点比例。

1 相关研究工作

文献[7]对最新传感器网络定位方法，包括基于连通性定位方法、基于距离测量定位方法、基于角度测量定位方法、基于信标结点定位方法、无信标结点定位方法、概率定位方法、结点移动时的定位方法等，从问题产生动机、问题描述、解决方法及定位性能等方面，进行了比较全面的分析。

Savvides[8]等人提出的原子多边形算法和Zhou[9]等人提出的三维欧氏距离定位算法都是利用直接邻居信标结点运行三边测量定位算法估算普通结点位置。获得位置估算的普通结点转变成为新的信标结点辅助其他普通结点进行位置估算。这些算法在网络结点连通度（网络中结点的平均邻居个数）和信标结点比例较高时能够实现较准确的结点定位。

Savarese等人提出一种由初始化和迭代更新两阶段组成、典型鲁棒性定位算法Hop-terrain[6]。在初始化阶段算法利用距离向量消息交换得到各结点之间的最短路径跳数，信标结点利用自身位置及各信标结点之间的最短路径跳数估算网络平均单跳距离。各普通结点利用网络平均单跳距离估算到信标结点的距离；然后进行三边测量定位计算，估算自身初始位置。迭代更新阶段普通结点利用邻居结点的估算位置及测距信息，运行三边测量定位算法，结合到邻居结点和到信标结点距离约束检测，进行位置迭代更新。

本文提出类似于Hop-terrain的DCRCN定位算法，对初始位置估算和迭代策略进行改进，较大地提高了结点定位准确性和定位结点比例。

2 DCRCN定位算法改进思路

DCRCN算法采用与Hop-terrain算法相似的两个步骤：首先利用信标结点估算普通结点初始位置，然后利用邻居结点迭代更新普通结点位置。迭代更新阶段需要用邻居结点的位置信息和到邻居结点的测量距离。距离测量准确性与测距硬件和传感器网络环境密切相关。而位置迭代更新需要反复进行，每一次邻居结点位置估计的准确性会对迭代性能形成直接影响。另外，测量误差虽然与硬件密切相关，但有利的迭代策略可以改善它对结点定位准确性的影响。

根据上述思路，DCRCN定位算法相对于Hop-terrain算法在结点初始位置估算阶段和结点坐标迭代更新阶段分别作了相应改进。在结点初始坐标估算阶段某结点运行三边测量定位算法时，对直接邻居信标结点采用测量距离而非跳数估算距离；对不同信标结点按到待求结点跳数大小赋以不同权值。在坐标迭代更新阶段，为了降低结点定位误差，要设法保留较好的中间结果。首先，如果某普通结点在某次迭代中无法成功运行三边测量定位计算、或成功运行三边测量定位计算但没有通过距离约束检测，我们将有选择性地用上次估算位置作为最新估算位置；然后，只选择部分可靠邻居结点进行到邻居结点距离检测，而不采用原Hop-terrain算法中所有邻居结点都参与到邻居结点距离约束检测的方法。

3 DCRCN定位算法

DCRCN算法首先利用信标结点信息進行结点初始坐标估算。这样，对于一个连通网络，所有普通结点都可以得到一个初始估算位置。然后，普通结点利用直接邻居结点信息进行基于距离约束的结点位置迭代更新，用以降低结点定位误差。下面将论述DCRCN算法两个主要步骤。

3.1 估计普通结点初始位置

在一般传感器网络应用中，信标结点的比例很低，绝大多数普通结点因为没有足够的邻居信标结点，所以不能直接运行三边测量定位算法估算自身位置。

为了解决上述稀疏信标结点问题，用距离向量交换思想估算普通结点到信标结点的距离。普通结点先获得以跳数为单位到信标结点的距离。信标结点利用到其他各信标结点的距离及跳数计算网络每跳的平均距离，并用有控制的泛洪法把该平均距离作为一个修正值在网络中传播。普通结点获得修正值即平均单跳距离，之后可计算到信标结点以米为单位的距离。

如果某信标结点为某普通结点的邻居结点，则不用基于跳数的估计距离，而直接用两点间的测量距离。某普通结点获得足够多信标结点的位置坐标和估算距离后，就可以运行带权值的三边测量定位算法估算自身初始坐标。由普通结点到若干信标结点的距离形成二次方程组，进一步整理成形如AX=b的线性方程组，再引入基于结点定位准确性的可信度权值参数，把线性方程组AX=b改成：

VAX=Vb ⑴

式⑴中，V为与可信度参数相关的权值向量，各元素按

⑵

取值。式⑵中，kij为普通结点i到信标结点j的最短路径跳数，wj为信标结点j的可信度权值。后面我们将看到，所有信标结点的权值均为1。最后采用标准的最小均方差估计方法可以得到方程组的解，即普通结点的初始坐标估计[10]。

经上述基于距离向量交换得到普通结点到参考信标结点的距离估计、用基本三边测量定位方法估算普通结点初始坐标后，就可着手开始普通结点位置迭代更新了。

3.2 迭代更新普通结点位置

结点坐标迭代更新，以普通结点初始位置为基础，采用有效迭代策略，反复更新结点坐标，提高结点定位准确性。

一次迭代基本过程如下：各普通结点用单跳路由方式获得邻居结点最新的估算坐标及相互之间的距离信息。如果用于定位的参考邻居结点数量足够，某普通结点运行带权值的三边测量定位算法，以获得新位置估算。对于获得新位置估算的结点，利用邻居结点和信标结点进行两项距离约束检测，有选择性地用上次迭代结果作为最新坐标，以降低定位误差。

到信标结点距离约束检测与普通结点到信标结点的两项距离大小比较：距离1，按普通结点的估计坐标计算到信标结点的距离；距离2，是该普通结点到该信标结点的最短路径跳数与结点通信半径的乘积。如果某普通结点到所有可连通信标结点均满足距离1小于或等于距离2，则表明到信标结点距离检测成功。

接下来，到邻居结点距离约束检测比较某普通结点到各邻居结点测量距离与按估算位置计算距离的平均差值，以判断结点定位的优劣。如果邻居结点位置估算准确度不高，上述平均差值并不能很好地表示结点定位准确性。所以，我们只选取部分可靠邻居结点用于到邻居结点距离约束检测。如果可用的邻居结点数量足够，当上述平均差值小于某一阈值（比如传感器结点通信半径R）时，我们认为到邻居结点距离约束检测成功。

如果某结点利用邻居结点成功完成三边测量定位计算并两项距离约束检测均成功，则接受本次位置更新。对于两项距离约束检测失败的情况，如果该结点之前已成功定位，就用上次迭代结果更新该结点坐标；否则，用初始位置估算的结果更新该结点位置。

为了控制误差传播，参照结点初始坐标估算阶段的方法，在三边测量定位算法中，对各参考邻居结点引入基于定位准确性的可信度权值向量W，表征各邻居参考结点定位准确性高低，各元素取值在0到1之间。结点坐标迭代更新开始时，信标结点的可信度权值直接设置为1；普通结点的权值则设定为接近于0的某个值，如0.1。当某普通结点两项距离约束检测均成功时，用其邻居结点可信度权值的均值来更新该结点定位可信度权值，以此来更新上述权值向量W。

由于受到邻居结点和信标结点的距离约束，随着结点位置不断更新，结点估算位置不断逼近真实位置。如果少数结点一直无法成功定位，给定一个迭代停止条件使算法有效终止。

4 算法性能评估

为了验证算法有效性，本文搭建实验平台进行了广泛的实验仿真。我们把DCRCN算法定位性能的相关数据与Hop-terrain算法[6]进行了对比分析。

4.1 仿真环境设备

我们设计的实验场景为一个正方形区域，边长100m，400个传感器结点随机分布其中，一部分结点为信标结点。测量误差按正态分布考虑，标准差取实际距离的5%。改變结点无线通信半径和信标结点比例进行大量实验。按结点无线通信半径对定位误差归一化。

4.2 实验结果分析

图1是经初始位置估算后的定位误差随连通度变化情况。普通结点定位准确性随着网络连通度和信标结点比例的增加而提高。当信标结点比例为5%和10%时，在不同网络连通度情况下DCRCN算法结点定位误差比Hop-terrain算法小6-10%和2-6%。结点定位误差的改善主要来自两个方面。首先，对直接邻居信标结点不用跳数估计距离而采用测量距离，提高了距离测量准确性；其次，在三边测量定位计算中增加可信度权值因素，提高了运算的准确性。

图1 初始位置估算后定位误差随连通度变化情况

图2是经位置迭代更新后定位误差随连通度变化情况。经比较我们发现，在连通度为10以上时，DCRCN算法结点定位误差比Hop-terrain算法均有不同程度的下降。但连通度在10以下时，DCRCN算法定位误差比Hop-terrain算法略高。这主要是因为图2描述的是网络中成功定位结点的定位误差，但在连通度比较低时，DCRCN算法的定位结点比例比Hop-terrain算法高很多（图3的主要结论）。

图2 坐标迭代更新后定位误差随连通度变化情况

图3是定位结点比例随连通度变化的情况。随着网络连通度的增加，定位结点比例不断增加。同时，DCRCN算法的定位结点比例比Hop-terrain算法有明显提高，尤其在网络连通度比较低时，DCRCN算法定位结点比例比Hop-terrain算法高10-20%左右。

图3 位置迭代更新后定位结点比例随连通度变化情况

图4是结点定位累积误差分布图。当信标结点比例为5%时，DCRCN算法定位误差小于50%的结点占所有普通结点比例为61.96%（Hop-terrain算法为53.91%），比Hop-terrain算法高8个百分点。总体上，当信标结点比例分别为5%和10%时，DCRCN算法定位误差小于10%-100%的结点占所有普通结点比例比Hop-terrain算法相应要高2-5百分点。所以，在相同实验条件下，DCRCN算法具有较小定位误差的结点比例比Hop-terrain算法高。DCRCN算法定位准确性的提高，除了前面提到的在结点初始位置估算阶段的改善外，同样有结点位置迭代更新阶段的改善，这包括：在坐标迭代更新时有选择性地用上次迭代位置作为本次迭代位置；只选择部分可靠邻居结点到邻居结点距离检测。通过以上措施，降低了定位误差。

图4 累积误差分布（连通度7.5）

我们改变网络拓扑，在格形网络（将平面网络分割成等大小均匀分布的格子，各结点在每个格子内随机分布）中也做了大量实验，得出了与上述随机布撒的均匀分布网络比较类似的结果：DCRCN算法定位结点比例和结点定位准确性比Hop-terrain算法都有不错的提高。

5 结束语

本文提出一种可靠邻居结点距离约束定位算法。在估计结点初始位置阶段，对直接邻居信标结点采用测量距离取代跳数估算距离，同时在三边测量定位计算时增加合理的可信度权值因素。在结点位置迭代更新阶段，只选择部分可靠邻居结点进行到邻居结点距离约束检测，并根据可靠邻居距离约束关系有选择性地用上次迭代位置作为最新估算位置。以上几个方面的改善，有效地提高了定位结点比例，降低了结点定位误差。

参考文献：

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

[2] AKYILDIZ I F， SU W， SANKARASUBRAMANIAM Y， et al.

Wireless sensor networks： a survey[J]. Computer Networks，2002.38（4）：393-422

[3] Wang Cheng，TANG Shao-Jie and LI Xiang-Yang. SelectCast：

scalable data aggregation scheme in wireless sensor networks[C] // Proceedings of IEEE INFOCOM， Shanghai， China，2011.4：10-15

[4] YU Xiao-Kang， YIN Xiao-Tian， HAN Wei， et al. Scalable routing

in 3D high genus sensor networks using graph embedding[C] // Proceedings of IEEE INFOCOM， Orlando， FL， USA，2012.3：25-30

[5] LIU Chang-Lei and CAO Guo-Hong. Distributed critical location

coverage in wireless sensor networks with lifetime constraint[C] // Proceedings of IEEE INFOCOM， Orlando， FL， USA，2012.3：25-30

[6] SAVARESE C， RABAEY J， and LANGENDOEN K. Robust

positioning algorithms for distributed ad-hoc wireless sensor networks[C] // Proceedings of the USENIX Technical Annual Conference， Monterey， CA， USA，2002.6：10-15

[7] WANG Jing， GHOSH R K， and DAS S K. A survey on sensor

localization[J]. Journal of Control Theory and Applications，2010.8（1）：2-11

[8] SAVVIDES A， HAN C C， and STRIVASTAVA M B. Dynamic

fine-grained localization in ad-hoc networks of sensors[C] // Proceedings of ACM MobiCom， Rome， Italy，2001.7：16-21

[9] ZHOU Zhong， CUI Jun-Hong， and ZHOU Sheng-Li. Localization

for large-scale underwater sensor networks[C] // Proceedings of IFIP Networking， Atlanta， GA， USA，2007.5：14-18

[10] GOLUB G. Matrix computations[M]. 3rd edition， The Johns

Hopkins University Press，1996.