周 莹

(重庆电子工程职业学院应用电子学院，重庆401331)

一种基于虚拟锚节点策略改进的Bounding Box定位算法*

周 莹*

(重庆电子工程职业学院应用电子学院，重庆401331)

针对Bounding Box算法定位误差大、覆盖率低的缺点，提出了一种采用虚拟锚节点策略的改进定位算法。首先未知节点利用其通信范围内的锚节点进行定位;其次，已定位的节点根据升级策略有选择性的升级为虚拟锚节点;最后，无法定位的节点利用虚拟锚节点实现定位。另外，在离散网络模型的基础上，通过建立双半径网络节点模型从而进一步约束了未知节点的位置。理论分析及仿真结果均表明，该算法在显著提高定位覆盖率的同时，有效地提高了定位精度。

无线传感器网络;定位;Bounding Box算法;离散网络;虚拟锚节点

无线传感器网络WSN(Wireless Sensor Network)的大多数应用领域中，位置信息对其监测功能的实现至关重要，没有位置信息的监测信息往往毫无意义［1］。定位的目标就是根据网络中部分位置已知的节点(锚节点)来估计其余节点(未知节点)的位置［2-3］。近年来所开发出来的各种无线传感器网络定位算法与机制［4-6］，采用的网络场景通常分为连续和离散两种模型。其中离散模型方法便于规范建模及统计分析，能够有效地降低算法复杂度［7］。

文献［4］的Bounding Box算法就是在离散网络模型中对锚节点通信距离内的未知节点进行定位，能够逼近节点的真实位置。但缺点是定位精度及算法覆盖率不高，对锚节点的密度及分布有很严格的要求。文献［7-9］针对上述问题分别做出了相应的改进:文献［7］提出了一种基于三跳通信环带的方法提高了算法的定位精度;文献［8］将多边测距定位方法引入到Bounding Box算法中解决了该算法未知节点定位过分依赖锚节点的问题;文献［9］利用锚节点与未知节点之间的关系通过约束待测节点的位置提高算法的覆盖率。上述算法仅对Bounding Box算法的某一缺点进行了改进，并没有对其定位精度和覆盖率进行整体改善。

针对这一问题，本文在文献［7］的基础上，提出了一种采用虚拟锚节点的Bounding Box改进算法，通过将已定位的节点根据升级策略有选择性的升级为虚拟锚节点提高了该算法的覆盖率;另一方面提出了双半径网络节点模型对未知进行约束优化从而提高了该算法的定位精度。

1 Bounding Box算法描述

Bounding-Box［4］算法由Simic SN等人提出。该算法的核心思想是:在二维区域内，未知节点的通信范围内会有一些锚节点，通过这些锚节点的位置和传感器节点的通信半径，就能获得未知节点所在的一个二维方形区域范围。具体过程如下述。

假设在一个正方形区域Q=［-q/2，q/2］×［-q/2，q/2］中随机分布了N个节点，其中有M个锚节点。首先锚节点广播其位置信息至整个网络，传播半径为R。考虑到干扰、偏移等不稳定因素，假定所有节点的位置都是一个矩形范围，即

如果将圆形通信范围近似为其内接正方形的约束盒(Bounding Box)［4］，将对该节点位置的2次约束简化为线性约束，并考虑更多锚节点约束，就能缩小覆盖区域的范围，进而降低节点位置区域的不确定性。为了便于进一步的研究，Bounding Box算法将以上模型进行离散化，如图1所示。

图1 Bounding Box算法定位原理(p=2)

在图1中，实心点S1、S2、S3为锚节点，空心点S为未知节点，假定n为偶数，Q分解成(n+1)2个正方形单元格，S=［-n/2，n/2］×［-n/2，n/2］。节点所处单元格的坐标为(i，j)，节点通信范围是正方形

2 算法改进

由上述对Bounding Box算法原理的分析可知，在进行方盒重叠计算时，若未知节点接收到的锚节点信息越多，则用来重叠的方形区域就越多，因而误差也就越小，同时，未知节点所接收到的锚节点信息数量的多少对算法的覆盖率也有直接影响。但是，由于无线传感器网络受到成本的限制，过多的增加锚节点将大大增加网络的开销，是不切实际的［10］。为了解决这一问题，本文将具体作出以下改进。

2.1 双半径网络节点模型

在Bounding Box算法设定的离散网络模型的基础上，考虑到算法能量消耗的问题，对锚节点引入两种通信半径，分别为p和p/2，图2给出了双半径网络节点模型的示意图。

图2 双半径网络节点模型示意图

如图2所示，S1、S2为锚节点，S为未知节点，其中锚节点的半径为p和p/2，则正方形的边长分别为2p+1和p+1，即锚节点的通信范围为:

由图2左图可知，当锚节点半径取p时，未知节点接收到的两个锚节点所重叠的区域为阴影区域A;而当锚节点半径取p/2时，未知节点接收到的两个锚节点所重叠的区域为白色区域B，显然，将区域B的质心作为未知节点S的估计坐标比将区域A的质心作为估计坐标所产生的误差小的多，从而大大提高了算法的定位精度。

由于这一模型在锚节点向网络广播自身位置信息时首先采用半径p，而在未知节点计算自身位置时采用p/2的通信半径对方形区域进行划分并完成定位。但是可以发现，当锚节点半径取为p/2时，未知节点S有可能出现在锚节点S1、S2的通信范围外，而无法定位，此时则采用通信半径p实现定位，因而并未影响算法的覆盖率。

2.2 虚拟锚节点策略

根据上述的分析可知，当采用双半径网络节点模型进行定位时，虽然能够较大程度的提高算法的定位精度，但未知节点需要依赖大量锚节点进行定位的问题仍未解决。为此，本文在上述基础上，提出了一种虚拟锚节点策略，以期提高算法的覆盖率。该策略的基本思想如下述。

首先根据双半径网络节点模型的思想，针对那些能够与锚节点建立连通的未知节点，Bounding Box算法的定位过程，完成自身位置的估计，并自动升级为虚拟锚节点;而后，对于未能和锚节点建立连通的未知节点，则利用升级后的锚节点进行定位。采用该策略，一方面能够在锚节点数量有限的条件下明显地提高算法的定位率;另一方面，由于在双半径网络节点模型的基础上实现的定位，能够保证未知节点较高的定位精度，因此，在升级为虚拟锚节点后并被其他未知节点用来定位时所产生的误差较小。另外，该策略中，只有那些没有邻锚节点的未知节点才虚拟锚节点进行定位，而不是所有节点都利用这一策略，因而可以有效的避免由于累积误差而导致误差增大的问题。

2.3 改进算法流程

根据上述分析本文改进算法的基本流程如图3所示。

图3 改进算法流程图

3 算法仿真与性能分析

为了验证本文改进算法的性能，本文使用MATLAB仿真工具对算法进行仿真实验。仿真所用网络区域为各向同性的边长为100 m的方形监测区域，其中令p=2。测试在不同的节点个数及锚节点个数下本文改进算法(记为VB-Box)与文献［7］提出的算法(记为TB-Box)和传统算法(记为BBox)在定位精度及覆盖率方面的性能。

设节点个数为N，锚节点个数为M，则相对定位误差为:

其中(xest，yest)为未知节点的估计坐标，(xtrue，ytrue)为未知节点的实际坐标，p为节点的通信半径。网络中所有未知节点的归一化的平均相对定位误差［11］为:

其中k为仿真次数，在未加说明的情况下k=500次，nc为可定位的节点个数。归一化的平均定位率通过下式计算:

3.1 算法定位精度分析

图4 定位精度比较

定位精度是衡量算法准确性的关键指标。为了分析比较3种算法的定位精度，仿真了在两种不同条件下定位精度的变化情况，图4分别为3种算法的定位精度随节点总数和锚节点个数变化的趋势图，其中，在图4(a)中，设锚节点比例为10%，可以看出，随着节点总数的增加，3种算法的定位精度均逐渐减小，文献［7］提出的算法定位精度小于传统算法，但本文改进算法明显由于传统算法和TB-Box算法，且分别提高了9.64%和4.6%。

在图4(b)中，设节点总数N=130，可以看出，在随锚节点个数增加时，3种算法的定位精度均逐渐减小并趋于稳定，说明了在锚节点增加到一定程度时，其对定位精度的影响逐渐减小。相比于BBox算法和TB-Box算法，本文改进算法定位精度在该条件下平均提高了13.41%和7.4%。

3.2 算法复杂度分析

在无线传感器网络中，由于本身特点的限制，要求算法在计算过程中尽可能小的消耗能量以确保网络节点的平均寿命。在本文中，用算法每次定位的平均时间等效算法的复杂度，来衡量比较3种算法的能量消耗情况。图5给出了3种算法在不同条件下定位时间的变化曲线。其中，图5(a)为锚节点比例为10%时3种算法定位时间随节点总数的变化曲线，可以看出，随着节点总数的增加，3种算法的定位时间均逐渐增多，传统算法的定位时间最少，而文献［7］所提出的算法每次定位用的时间较多，而本文改进算法则适中，相比于B-Box算法，本文算法每次定位时间平均增加了0.018 1 s，而相比于TBBox算法，本文算法则减少了0.013 3 s。

图5(b)给出了在节点总数为130时3种算法定位时间随锚节点个数的变化曲线，可以看出，随着锚节点数的增多，3种算法的定位时间基本保持不变，其中本文算法较传统算法定位时间平均增加了0.017 1 s，而较TB-Box算法则降低了0.022 6 s。

图5 定位消耗时间比较

通过上述仿真分析可知，本文改进算法在节点个数较少且锚节点数较为稀疏时覆盖率明显优于传统算法和文献［7］提出的算法，且算法的能量消耗适中，同时能够保证良好的定位精度，图6给出了在节点个数N=80，锚节点个数为7，p=2时本文改进算法与TB-Box算法的每次定位误差分布图。

图6 两种算法对网络所有节点的定位误差

由图6可知，本文改进算法平均定位误差为38.893%，而文献［7］提出的算法定位误差平均为53.036%，且本文算法在72个未知节点中可定位的节点有71个，而TB-Box算法仅有55个节点能够实现定位。

4 结束语

无线传感网络节点定位算法的覆盖率和定位精度是衡量定位算法有效性与实用性的重要指标。本文针对Bounding Box算法覆盖率及定位精度较低的问题，在详细分析离散网络模型的基础上，通过建立双半径网络节点模型并将虚拟锚节点的思想引入到算法的定位过程中，在大大提高算法覆盖率的同时减小了定位误差。理论分析和仿真结果表明，在锚节点个数较少且网络平均连通度较低时，相比于传统算法及文献［7］提出的改进算法，本文改进算法在略微增加算法复杂度的同时仍能保持较高的定位率;另外在确保网络连通度的基础上，本文算法有效的提高了定位精度，大大提升了算法的实用性。

［1］ 吴晓平，谈士力.基于半定规则的无线传感器网络定位算法性能分析［J］.传感技术学报，2012，25(12):1731-1736.

［2］ 海丹，郑志强，张辉.无线传感器网络环境下基于锚节点定位的节点定位误差分析［J］.计算机应用研究，2011，28(4):1486-1489.

［3］ Stupp G，Sidi M.The Expected Uncertainty of Range Free Localization Protocols in Sensor Networks［C］//Algorithmic Aspects of Wireless Sensor Networks:First International Workshop，Algosensors.2004.85-97.

［4］ Simic S N，Sastry S.Distributed Localization in Wireless Ad Hoc Networks［R］.Technical Report UCB/ERL M02/26，UC Berkeley，2002.

［5］ Whitehouse C D.The Design of Calamari:an Ad-Hoc Localization System for Sensor Networks［D］.University of California at Berkeley，2002:1-73.

［6］ Leskovec J，Chakrabarti D，Faloutsos C.Information Survival Threshold in Sensor and p2p Networks［C］//Proceedings of 26th IEEE International Conference on Computer Communications.Anchorage，Alaska，USA，2007.1316-1324.

［7］ 向满天，史浩山，李立宏，等.高精度与高覆盖率的传感器网络定位算法［J］.通信学报，2008，29(11):19-23.

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

［9］ 向满天，史浩山，李立宏，等.基于单元格的无线传感器网络节点定位算法［J］.西北工业大学学报，2008，26(5):607-611.

［10］Edgar H C.Wireless Sensor Networks:Architectures and Protocols［M］.Boca Raton，Florida:CRC Press LLC，2004.

［11］程伟，史浩山，王庆文.基于差分修正的传感器网络加权质心定位算法［J］.系统仿真学报，2012，24(2):389-393.

周 莹(1983- )，女，汉族，重庆人，重庆电子工程职业学院电子系，讲师，主要研究方向为电路系统设计与分析、传感器技术，zhouying1983cq@163.com。

An Improved Bounding Box Localization Algorithm Based on the Virtual Anchor Nodes*

ZHOU Ying*
(Department of Electronics，Chongqing College of Electronic Engineering，Chongqing 401331，China)

To overcome the disadvantages of localization accuracy and low coverage rate in current Bounding Box algorithm，an improved algorithm using the virtual anchor nodes was proposed.Firstly，the anchor nodes within the communication range of unknown nodes were used to calculate the coordinates of the unknown nodes.Secondly，the located unknown nodes were upgraded as the virtual anchor nodes according to the promotion strategy selectively. Finally，the nodes which were unable to locate themselves used the virtual anchor nodes to get their location.On the other hands，the network node model of double radius based on the discrete network model was introduced to restrict the location of the unknown nodes.The result of simulation and analysis shows that the proposed algorithm can improve the localization coverage rate as well as the estimation accuracy significantly.

wireless sensor network;localization;Bounding Box algorithm;discrete network;virtual anchor nodes

10.3969/j.issn.1005－9490.2014.02.035

TP393

A

1005－9490(2014)02－0332－05

项目来源:国家自然科学基金项目(61202490)

2013-05-27修改日期:2013-06-15

EEACC:6150P