0引言
近年来，随着微机电系统、无线电通信以及嵌入式计算等技术的不断进步，无线传感器网络（Wireless Sensor Network， WSN）逐渐被广泛应用于环境监测、健康医疗、抢险救灾和战场监视等领域[1-2]。对于很多应用，没有位置信息的数据是不具备任何意义的，比如野生动物习性监测、森林火灾救援以及基于地理位置信息的路由协议等[3]。最传统的定位方法就是采用GPS（Global Positioning System）进行定位，然而这种定位方式并不适用于无线传感器网络，主要原因有以下两点：1）无线传感器网络一般都有成百上千个节点，为每个节点配备GPS接收器会大幅度增加网络成本；2）GPS接收器能耗非常高，而对于无线传感器网络来说，每个节点存储的能量非常有限（一般都是通过电池供电，给节点更换电池是很不现实的，尤其是在环境很恶劣的场景下），这种定位方式会大幅度降低网络的生命周期。因此，目前一般的处理办法都是给少部分传感器节点配备GPS接收器来确定自身的位置信息（这种能够直接确定自身位置信息的节点称为信标节点），然后再利用信标节点的位置信息通过一定的定位算法来确定其他节点的位置（这种无法直接确定自身位置信息的节点称为未知节点）[4]。
为了解决无线传感器网络中的节点定位问题，国内外的研究者已经提出了一些相关定位算法。这些算法主要可以分为两类：基于测距（Rangebased）的定位算法[5-7]和无需测距（Rangefree）的定位算法[8-10]。文献[11]提出了采用几何质心原理来进行定位：信标节点每隔一段时间向邻居节点广播一个信号（信号中包含有位置信息），当未知节点在一段时间内接收到来自某个信标节点的信号数量超过某一个阈值后，该节点认为与此信标节点连通，最后将与之连通的所有信标节点构成的多边形的几何质心作为自身的估计位置。
质心定位（Centroid Localization， CL）算法是一种完全基于网络连通性的定位算法，其计算和实现起来都比较简单，但是定位精度有限。目前，一些学者已经提出了一些改进算法。文献中计算权重的方法对未知节点的位置进行估计。
对于质心定位算法，如果未知节点的实际位置与其通信范围内信标节点构成的多边形的几何质心位置很接近，那么定位效果会比较好。然而在实际场景下，未知节点的实际位置并不一定很接近信标节点构成的多边形的质心位置。当未知节点的实际位置与信标节点构成的多边形的质心位置相距很远时，将会产生很大的误差。如图1所示，未知节点O1的实际位置与信标节点A、B、C、D构成的多边形的几何质心位置距离很近，这种情况下用多边形的几何质心作为未知节点的估计位置产生的误差会比较小，而未知节点O2的实际位置与信标节点E、F、G、H构成的多边形的几何质心位置距离很远，此时若以几何质心作为最终的估计位置，则会导致较大的定位误差。
另外，质心定位算法很容易受到信标节点密度和信标节点选择的影响[15]。现有的改进算法大部分都是采用基于加权的思想来进行改进，虽然在一定程度上提高了定位精度，但是并没有很好地解决质心算法存在的问题。在图1中，如果未知节点O2定位时不选择信标节点E、F、G、H来进行位置估计，而是选择E、G、H来进行位置估计并以信标节点E、G、H构成的多边形的几何质心作为估计位置，误差则会大幅度降低。
针对这些问题，本文提出了一种基于最优信标节点的质心定位（Optimal Beacon Nodesbased Centroid Localization， OBCL）算法，在OBCL中主要提出了以下几点改进：
1）节点在定位时选择最优信标节点进行位置估计；
2）引入节点角色转变机制，当未知节点完成定位后，可以临时充当信标节点的角色来辅助定位；
3）定位过程中需要进行重定位，保证所有节点能够成功定位。
假设该传感器网络具有以下性质：
1）网络中待定位的N个传感器节点在部署好之后不再移动；
2）4个移动信标节点具备位置信息获取和方向感知能力；
3）4个移动信标节点的无线发射功率可调，最大发射功率可覆盖全网，并且这4个信标节点拥有足够的能量；
4）待定位的N个传感器节点通信半径相同，都为R0；
5）网络中所有的节点，包括信标节点和待定位的节点都严格时间同步。
1.2信道传播模型
本文的信道传播模型采用Lognormal Shadowing路径损耗模型，其一般表示形式为：
2算法描述
2.1相关定义
2.2信标节点的路径规划
为了减小信标节点的位置对定位造成的影响和解决信标节点不足时误差较大的问题，本文引入移动信标节点，并让信标节点按照一定的轨迹移动，各个信标节点的移动路径如图3所示。
图4中，该时刻节点P和Q完成了定位，成为准信标节点。此时未知节点G选择B1、B3和P构成的多边形的几何质心作为估计位置误差最小。而在所有节点完成初次定位之后，节点E、F也会转变成准信标节点，显然E、F、P的几何质心比B1、B3和P构成的多边形的几何质心更加接近于节点G的真实位置。因此，为了解决上面两个问题，本文引入重定位机
制，重定位过程描述如下：
1）对网络中任一节点vi重新生成最优信标节点集合OBNi。
2）若重新计算得到的OBNi的SDD小于前一次定位时的最优信标节点集合的SDD，则用重新得到的最优信标节点集合按照式（7）来对节点重新进行位置估算，并以此次估算的位置作为节点的最终估计位置；否则仍以前一次定位时的结果作为节点的最终估计位置。
3）4个信标节点分别以最大功率向全网广播一条消息，当节点vi接收到4个信标节点广播的消息之后，如果vi完成定位，则不作任何处理；如果vi还未完成定位，则根据式（1）和式（7）来估算位置。
4）重复1）、2）、3）过程，直至网络所有节点完成定位过程。
4.1定位精度的比较
OBCL核心思想是利用最优信标节点以及重定位机制来提高质心定位算法精度，并引入移动信标节点和节点角色转变机制，从而使得整个网络只需要4个信标节点就能达到比较好的定位效果。图5显示了CL、WCL、RRWCL和OBCL算法的定位精度。
从图5可以明显看出，不断增加网络中信标节点的比例，CL、WCL、RRWCL这3种质心定位算法的定位误差逐渐减小，而本文算法在只有4个信标节点的情况下，平均定位误差要小于其他3种算法在40%信标节点比例时的定位误差。由此可见，OBCL算法更适用于定位精度要求高的场合，并且只需要4个信标节点，能够大大减少网络成本。
4.2通信半径对定位精度的影响
本组实验主要研究通信半径对整个网络定位精度的影响。图6显示了CL、WCL、RRWCL算法（信标节点比例为20%）以及OBCL算法在不同通信半径下整个网络的平均定位误差。从图6可以看出，4种算法定位精度都会受到通信半径的影响。当节点通信半径增大时，网络的平均定位误差会减小，而当通信半径增大到一定值时，平均定位误差趋于稳定。对于OBCL，如果减小节点通信半径，候选信标节点集合中的候选信标节点个数就会减少，从而导致求得的最优信标节点的几何质心与节点实际位置并不是很接近。而当节点通信半径增大到一定值时，候选信标集合中的候选信标节点个数会到达一定的上限，所以平均定位误差会逐渐趋于稳定。
4.3参数D对定位精度的影响
在本组实验中，主要改变D的取值来观察OBCL算法定位精度的变化，结果如图7所示。
图7表明当D取值在小于15m时，定位效果比较理想，当D取值比较大时，定位误差会较大。如图8所示，如果4个信标节点初始所在位置构成的正方形区域较大，假如是B1B2B3B4，那么可能节点i定位的时候，候选信标节点集合中只有4个信标节点。而如果4个信标节点初始位置构成的正方形为图8中的小正方形，则节点i定位时，小正方形内的节点都已进行了定位，那么节点i的候选信标节点集合除了4个信标节点以外，还会有其他的准信标节点，这样的话，会减小定位误差。
4.4移动步长λ对定位精度的影响
本组实验主要研究移动步长λ对定位精度的影响。通过改变移动步长，观察不同移动步长时OBCL算法的平均定位误差。实验结果如图9所示。从图9可以看出，随着移动步长的增加，定位误差会逐渐变大。原因同参数D对定位精度的影响类似。
4.5节点密度对定位精度的影响
本组实验主要研究网络节点密度对定位精度的影响，通过改变网络区域内的节点个数来观察OBCL算法平均定位误差的变化，实验结果如图10所示。
从图10可以明显看出，当网络中节点个数逐渐增多时，平均定位误差不断减小，而当节点个数到达一定值时，平均定位误差趋于稳定。因为网络中节点个数较少时，会造成定位时每个节点的候选信标节点个数较少，从而导致定位误差的增加。
5结语
本文在考虑现有质心定位算法不足的基础之上，通过主动地选择最优信标节点来提高定位精度，同时利用移动信标节点和引入节点角色转变机制，使得本文算法在只需要4个信标节点的情况下就可以达到比较理想的定位效果，且大大节约了网络成本。另外，本文引入重定位机制，保证了网络中所有节点能够进行定位。仿真实验表明，与现有的质心定位算法相比，OBCL算法具有较高的定位精度。
参考文献：
. Ad Hoc Networks， 2012， 10（6）： 946-961.
[2]ZHAO C， XU Y， HUANG H. Localization algorithm of sparse targets based on LUdecomposition [J]. Journal of Electronics & Information Technology， 2013， 35（9）： 2234-2239.（赵春晖，许云龙，黄辉.基于LU分解的稀疏目标定位算法[J].电子与信息学报，2013，35（9）：2234-2239.）
. Computer Communications， 2012， 35（13）： 1590-1600.
. Computer Communications， 2012， 35（13）： 1549-1560.
[5]BAHL P， PADMANABHAN V N. RADAR： an inbuilding RFbased user location and tracking system [C]// INFOCOM 2000： Proceedings of the Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies. Piscataway： IEEE， 2000： 775-784.
// Proceedings of the 7th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2001： 166-179.
. IEEE Sensors Journal， 2013， 13（2）： 466-475.
. Journal of Telecommunication Systems， 2003， 22（1/2/3/4）： 267-280.
[9]WU G， WANG S， WANG B， et al. A no
vel rangefree localization based on regulated neighborhood distance for wireless Ad Hoc and sensor networks [J]. Computer Networks， 2012， 56（16）： 3581-3593.
// Proceedings of the 9th Annual International Conference on Mobile Computing and Networking. New York： ACM， 2003： 81-95.
. IEEE Personal Communications， 2000， 7（5）： 28-34.
// WISP 2007： Proceedings of the 2007 IEEE International Symposium on Intelligent Signal Processing. Piscataway： IEEE， 2007： 1-6.
.电子科技大学学报，2010，39（3）：416-419.）
.传感技术学报，2009，22（4）：563-566.）
.西安交通大学学报，2010，44（8）：1-4.）
// ICCSIT 2010： Proceedings of the 3rd IEEE International Conference on Computer Science and Information Technology. Piscataway： IEEE， 2010： 331-336.
