基于移动信标的响应式传感网定位方法

徐 骏,吴 敏,沙 超,倪凯悦,王汝传

(南京邮电大学 计算机学院、软件学院,江苏 南京 210003)

基于移动信标的响应式传感网定位方法

徐 骏,吴 敏,沙 超,倪凯悦,王汝传

(南京邮电大学 计算机学院、软件学院,江苏 南京 210003)

相对于静态锚节点定位算法而言，基于移动锚节点的定位机制能较好地提升定位的准确性。由于受到移动性的限制，某些静态锚节点定位时会出现误差过大的情况。为此，提出了基于蜂窝模型的移动定位算法。该算法应用中心锚节点和边缘锚节点协作遍历模型的中心和边缘位置，可快速定位覆盖区域的未知节点，且能去除移动规划设计中的冗余路径，避免了同一路径的冗余重复访问，有助于保证锚节点移动的高效性和准确性。该算法通常从捕获的三个锚节点信息筛选出RSSI信号强度较大的两个，以避免引入误差过大的距离值，根据信号强度的衰减模型求解可以得到两个位置信息，并由第三个距离信息作为判断条件，唯一确定未知节点的坐标信息。仿真结果表明，所提出的定位算法定位精度较好且定位的时间效率较高。

蜂窝模型；协作遍历；移动信标；RSSI

0 引 言

无线传感网技术在现实生活中应用广泛。通过在指定区域部署低功耗的传感器节点，可实现目标追踪、资源勘探、环境监测等应用。这些应用都要基于位置信息的捕获，其中定位技术起到了关键作用[1-3]。

节点定位的过程就是通过相关的技术手段获取网络结构中未知节点的绝对或相对位置信息。根据定位过程中是否需要测距，无线传感器节点定位可以采用基于测距的定位技术和无需测距的定位技术。其中基于测距的定位方法需要额外的硬件支持，定位精度较高但容易受到环境因素的影响；而无需测距技术虽然定位精度较低，但是成本低且不易受外界环境的影响。

根据锚节点是否具有移动性，定位算法还可以分为静态定位算法和动态定位算法。通常采用静态定位时需要锚节点密度达到一定的程度来满足节点之间的连通性[4]。而动态定位算法可以使用较少的锚节点，而且部署更加灵活多变，近年来在定位领域应用广泛[5-8]。

移动的信标节点沿着事先设计好的移动路径遍历整个网络区域，并在移动到相应的位置广播消息包。未知节点捕获来自锚节点的消息包后保存并进行分析，可以计算出未知节点的估计位置坐标[9-11]。

目前的移动定位算法移动的随机性太大，移动的路径规划存在不合理的情况，效率较低。且在定位移动的过程中节点的配合协作性不高，从而导致节点的定位误差较大。

为此，提出了改进的RSSI定位算法以提升定位精度。在此基础上，设计了基于蜂窝模型的移动规划路径，定义了中心锚节点和边缘锚节点分别遍历蜂窝区域的中心位置和六个边缘位置，并在相应的区域广播消息包，以保证定位区域的位置节点至少捕获到来自三个锚节点的消息包。仿真验证结果表明，所提出的移动定位算法在定位精度和定位的时间效率上均有明显改善。

1 相关工作

使用移动定位算法来求解未知节点坐标时，移动锚节点会沿着设计好的移动轨迹移动，并在相应的位置停留一小段时间来广播自身的消息包，而且需要保证待定位的未知节点至少需要捕获到来自三个锚节点的消息才能确定唯一的位置信息。

移动锚节点定位算法相对于固定锚节点定位算法而言，不会因为锚节点的位置分布不均匀而导致某些节点无法定位，在很大程度上减少了锚节点的使用数量，而且能够设计好的移动路径算法来保证每个未知节点都能至少捕获到来自三个锚节点的消息包。从以上分析可知，相对于固定的锚节点定位算法，移动锚节点定位算法在成本和效率上都有明显提升。

在文献[12]中，基于高斯马尔可夫模型设计移动的规划路径，分别设定了移动锚节点的速度和方向，并对速度和方向分别引入了高斯随机变量。节点的定位采用加权质心算法，对距离值求解倒数作为其在总体样本中的权值来求解具体的距离值。定位过程的权值求解过于简单，并不能很好地规避求解的距离误差值。此外，高斯马尔可夫移动模型随机性太大，导致锚节点遍历路径存在很多的重复路径，移动的效率较低。

文献[13]采用MB-DV-Hop定位算法来实现对节点的定位操作，移动锚节点通过螺旋式移动轨迹来遍历网络区域。未知节点实时捕获来自锚节点的数据包，当数据包个数达到三个时，就可以确定自身的坐标，进而转化为静态锚节点。再通过DV-Hop定位算法计算出移动锚节点和静态锚节点之间的平均跳距值，实现对尚未能定位节点的定位操作。但是DV-Hop定位算法节点的定位精度不高，且移动锚节点的移动路径长度过大，效率不高。

文献[14]使用三重定位覆盖模型，并在锚节点移动过程中会一直广播包含自身位置信息的消息包。同时处在该模型区域的未知节点会实时地捕获消息包，并通过比较来保存来自锚节点信号强度最大的消息包，将两个最大的RSSI值所处的点坐标值作为未知节点在边上的投影点，取通过这两个投影点的垂线的交点作为未知节点的坐标值。单个锚节点的移动路径也是基于三重覆盖模型，从而保证每个未知节点都能至少捕获到来自三个锚节点的消息包。锚节点移动过程中一直广播消息包会造成能量的浪费，同时移动路径算法的效率不是很高。

文献[15]也是基于三重覆盖模型，提出移动路径规划算法LTC和STC，并通过比较得出STC的移动效率较高。STC移动的思想是通过三个锚节点的相互配合来实现交替移动，组成一个单位的三重覆盖模型来保证未知节点捕获到来自锚节点的消息包。定位算法使用TDOA，定位精度较高，但是要求使用额外的硬件设备，成本较高。使用三个锚节点来实现移动路径规划，锚节点的利用效率不是很高。

这里基于蜂窝模型，并设定两个锚节点分别遍历蜂窝模型的中心位置和边缘顶点位置，保证在定位区域的未知节点至少能够捕获到来自三个锚节点的消息包，并记录到达未知节点的信号强度值并根据信号衰减模型计算出对应的距离信息，从而保证未知节点能实现定位操作。此外，还对RSSI定位算法进行了改进，在三边定位过程中只捕获最大的两个信号强度，并利用最小的信号强度求解估计距离来最终判断未知节点的坐标。

2 RSSI定位算法优化

对于移动定位算法而言，是由多个定位算法沿着一个移动路径组成，需要确定相应的定位模型和定位算法。

2.1 定位模型

三个锚节点到未知节点的通信距离均小于锚节点广播消息的最大通信半径。假设三个锚节点的坐标分别为(xA,yA)、(xB,yB)、(xC,yC)，未知节点的坐标为(xN,yN)以及到三个锚节点的距离分别为dA、dB和dC。根据距离公式求解可得：

(1)

(2)

(3)

将上面的公式整理可得：

(4)

上式简写成：

(5)

(6)

根据式(5)分析，方程有且只有唯一解。

由此可得，对于某个未知节点进行定位操作，则至少需要捕获到三个锚节点的信息。

如图1(左)所示，锚节点A的通信半径所覆盖的圆形区域，至少需六个额外的锚节点才能保证对该圆形覆盖区域的所有未知节点实现定位操作。

图1 通信覆盖模型(左)与蜂窝模型(右)

将图1的通信覆盖模型简化为蜂窝模型，每个小的三角形构成的区域都至少能捕获到来自三个锚节点的信息。

分别定义两个移动的锚节点为中心锚节点和边缘锚节点。中心锚节点遍历蜂窝模型的中心位置，而边缘锚节点分别遍历蜂窝模型的六个顶点位置，且两个锚节点分别在对应的位置上广播包含自身坐标信息的消息包。依靠两个锚节点的分工协作能够保证该区域的未知节点至少能捕获到三个锚节点的信息包，从而实现定位操作。

2.2 消除最大误差的改进定位方案

基于RSSI的测距技术无需特殊硬件，在成本和功耗上都较低，因此在无线传感器定位算法中得到了广泛应用。其中主要使用的无线电传播模型有三类，其中最常用的是Shadowing[16]模型：

(7)

其中,PLd0表示初始信号强度;α表示射频信号的衰减指数;xσ表示方差为σ的对数误差。

对图1中蜂窝模型的三角形定位区域进行分析，假设三个锚节点的坐标值为(xA,yA)、(xB,yB)和(xC,yC)，以及未知节点D的坐标为(xD,yD)。三个锚节点A、B和C分别向未知节点D发送数据包。筛选出RSSI信号强度最大的两个锚节点信息表项,并根据信号强度的衰减模型分别计算出这两个距离信息。去除掉信号强度最弱的信息值，是为了避免引入误差过大的距离值，从而能够提高定位精度。

图2 节点定位模型(左)及其所捕获的信号强度近似相等的情形(右)

当捕获到来自两个锚节点的信号强度近似相等且小于来自另外一个锚节点的信号强度时，将采用如下判定方法：

如图2(右)所示，未知节点D捕获到的来自锚节点B和C的信号强度近似相等，则可以确定未知节点D处在线段BC的中垂线附近。又有来自锚节点A的信号强度最大，则可以得到较为可信的未知节点D和A之间的距离信息为dD，从而可以求解出未知节点D的坐标。求解过程如下：

由D近似处在线段BC的中垂线上，可以得到线段AD近似垂直于线段BC。为了便于计算，引入横坐标和纵坐标的误差值为xα和yα，则有：

(8)

且锚节点A和未知节点的距离为d，则有：

(9)

根据式(8)和式(9)，可以唯一确定未知节点D的坐标值。

当来自三个锚节点的信号强度都近似相等，则可以确定未知节点D处在三个锚节点组成的三角形区域的中心附近。

该定位算法与传统的RSSI三边定位算法相比，去除误差值最大的信号强度值。根据RSSI信号衰减模型可知，根据信号强度求得的距离值越大，该距离值与实际值的误差也越大。因此排除掉信号强度最弱的信息值，可以相应地减小定位的误差值。

3 信标节点移动路径设计

在完成了具体的定位算法后，需要对整体的信标移动路径进行设计。信标移动路径设计的好坏在很大程度上决定了能够访问的未知节点的总数、定位过程的总时间和精度等因素。

假设带定位节点部署在一个W×L的矩形网络区域内，且移动锚节点通信半径为R。

文献[15]提出了基于三重覆盖优化的STC移动路径规划算法，主要使用三个锚节点A、B和C交替移动来实现移动定位。STC具体移动路径如图3所示。从最左端的三角形A1B1C1开始，锚节点A从开始的A1位置移动到相对于线段B1C1的对称位置A2；接着锚节点B从位置B1移动到相对于线段C1A2的对称位置B2；然后锚节点C从位置C1移动到相对于线段A2B2的对称位置C2，后续的节点移动以此类推。

图3 STC的信标移动路径

(10)

这里设计的移动路径是基于蜂窝模型的移动轨迹，主要由一个中心锚节点和一个边缘锚节点配合来完成轨迹移动。中心锚节点移动到蜂窝模型的中心时，会通知边缘锚节点访问蜂窝模型相应的边缘节点位置。如图4所示，粗实线表示中心锚节点移动的轨迹，粗虚线表示边缘锚节点移动的轨迹。

图4 设计的锚节点移动模型

(11)

由此分析得，该算法的移动路径长度小于STC的移动路径长度，且只使用了两个锚节点，而STC中使用了三个锚节点。就路径长度和锚节点使用个数上分析可知，该路径算法优于STC路径算法。

下面分析访问一个未知节点所需的平均时间。当三个锚节点组成三重覆盖模型时，该区域内的节点就能实现定位。假设单位时间内移动的步长为R，网络模型的长和宽分别设为L和W，为了便于分析，假设节点均匀分布，每个三角形区域分布的节点数均为n。

对文献[1]中的锚节点移动轨迹分析得：

(12)

对锚节点移动轨迹进行分析得：

(13)

由式(12)-式(13)得：

(14)

当L≫R时可以得到上面的结果大于零。由此分析，对同一个网络拓扑结构，该路径移动算法定位一个未知节点平均所需的时间较少。

4 仿真实验

将所提出的定位算法命名为MLD，并与单个锚节点的路径规划TRI[14]，以及文献[15]提出的STC路径规划作对比实验。好的移动规划应该能够尽可能短地设计移动路径，并且能较好地提高节点的定位精度，此外还要在尽可能短的时间内定位更多的节点。

实验从三个方面来分析定位算法的性能：

(1)相等时间内能够定位的节点比例；

(2)定位相同节点数锚节点移动路径总长；

(3)节点定位误差率。

采用Java对上述移动定位算法进行仿真实验。设定网络未知节点的部署区域为(800 m×516 m)的矩形区域，内有200个未知节点随机分布其中。设定通信半径为5 m、10 m、15 m和20 m。使用上述三种定位算法，并设定移动步长为R，且节点移动到三重覆盖模型的相应位置时广播数据包。

在相同的定位时间内，移动定位算法定位未知节点的比例能够较好地反映定位算法的时间效率。定位节点的比例越高，说明移动定位算法移动的时间效率越高。三种移动定位算法的定位节点比例见图5。

图5 不同时间下的节点定位比例

随着运行时间和通信半径R的增加，三种移动定位算法的可定位节点数随之增加。通信半径的增加保证了在相同的移动步长下，锚节点广播的消息包能够被更多的未知节点捕获到，从而能够使更多的未知节点实现定位操作。

TRI可定位节点数最少，主要原因是单个锚节点没有其他的辅助锚节点，在短时间内移动路径长度也较短，相对而言覆盖未知节点的面积较小，这就导致定位的节点比例较少。MLD移动定位算法相对STC而言，相同时间内定位节点比例较高。主要原因是MLD和STC都是基于三重定位模型，且MLD的两个锚节点的移动路径基本平行，不存在移动路径交叉的情况，在纵向上的移动距离较少，从而避免了移动路径的过多冗余，保证了时间效率。此外，MLD只使用了两个移动锚节点，一定程度上节约了成本。

节点在定位的过程由于处在锚节点移动覆盖区域的盲区而导致节点的位置信息捕获不到或误差较大而导致节点无法定位。

遍历完整个网络后，可定位节点分析如表1所示。

表1 不同算法下的可定位节点分布情况

由表1可知，随着通信半径的增加，所能覆盖的通信区域的面积也随之增大，从而能减小定位盲区的面积。TRI由于是单个节点移动来定位,且定位过程中根据信号强度的最大值的几何运算求解坐标值，定位的误差较大，从而导致节点定位的失效。STC和MLD的定位实现过程都是基于三重覆盖定位模型，定位的原理基本相同，在相同通信半径的情况下遍历整个网络区域后的整体定位的效率基本相同。

移动相同的路径所能定位的未知节点的比例也能够反映移动定位算法的效率，其实验结果如图6所示。如果锚节点移动的路径长度相同，而定位的节点数越多，则表明定位效率越好；反之说明定位效率较差。

图6 不同移动路径长度节点定位比例图

TRI算法实现的是单个锚节点的遍历而不是多个节点协作式遍历，从而导致在移动相同路径长度的情况下节点的定位效率较差。STC算法在移动过程需要三个移动的锚节点来实现辅助定位，锚节点相对移动的路径长度较大，而MLD移动过程中只需要两个锚节点，且基本上沿着直线移动前进，因此遍历相同面积区域移动的路径长度也就相对较短，从而可以定位更多的节点。

下面讨论在不同的通信半径下，访问整个网络区域锚节点所移动的路径长度，如图7所示。访问的未知节点覆盖的网络区域的面积是恒定的，最终移动路径的长短能够较好地反映节点遍历网络区域的效率。

图7 不同通信半径下移动路径总长度对比图

随着通信半径的增大，能够保证在相同的移动路径下遍历更多的节点区域面积，因此节点的移动路径长度也会随之减少。TRI使用单个锚节点来遍历该区域，不能实现分工协作，需要自身来完成更多的遍历工作，也就导致移动的路径长度偏大。STC移动过程中是使用三个锚节点来实现遍历，移动路径存在较多的交叉情况而不是平行进行的，导致效率降低。而MLD在移动过程中，中心锚节点和边缘锚节点是平行移动的，不存在交叉，显著提高了遍历的效率。

5 结束语

移动信标辅助定位中锚节点的移动性保证了未知节点至少能够捕获到三个锚节点的信息，从而保证了定位的精度要求，减少了锚节点的使用数量，降低了定位成本。为此，提出的移动定位算法使用两个锚节点来分别遍历蜂窝模型的中心和边缘位置。采用改进的RSSI定位算法，能较好地提高定位的精度和时间效率。移动锚节点的移动轨迹不存在交叉移动的情况，避免了移动路径的冗余，因此能够较好地提升定位的时间效率。相关的仿真实验也验证了上述内容，同时表明，改进的定位算法利用两个边长和最长边的长度判断并计算出位置信息，规避了三边定位的最大误差值，在一定程度上提高了定位精度。

[1] 崔逊学,左从菊.无线传感器网络简明教程[M].北京:清华大学出版社,2009.

[2] Li Fangmin,Han Ping,Luo Ting.Adaptive region localization algorithm based on packet loss rate and RSSI in wireless sensor networks[J].Journal of Communication,2009,30(9):15-23.

[3] Liu Y,Yang Z,Wang X,et al.Location,localization,and localizability[J].Journal of Computer Science and Technology,2010,25(2):274-297.

[4] Yang Zheng, Wu Chensu,Liu Yunhao.Localization calculation:wireless network positioning[M].Beijing:Tinghua University Press,2014.

[5] Chui W Y,Chen B S,Yang C Y.Robust relative localization estimation in wireless sensor networks with inexact position problems[J].IEEE Transactions on Mobile Computing,2012,11(6):935-946.

[6] Kim E,Kim K.Distance estimation with weighted least squares for mobile beacon-based localization in wireless sensor networks[J].IEEE Signal Processing Letters,2010,17(6):559-562.

[7] Zhang B,Yu F.Low-complex energy-efficient localization algorithm for wireless sensor networks using directional antenna[J].IET Communication,2010,4(13):1617-1623.

[8] Ou C H.A localization scheme for wireless sensor networks using mobile anchors with directional antennas[J].IEEE Sensor Journal,2011,11(7):1607-1616.

[9] Huang R, Zaruba G V.Monte Carlo localization of wireless sensor networks with a single mobile beacon[J].Wireless Networks,2009,15(8):978-990.

[10] Ding Y,Wang C,Xiao L.Using mobile beacons to locate sensors in obstructed environments[J].Journal of Parallel and Distributed Computing,2010,70(6):644-656.

[11] Zhang B,Yu F,Zhang Z.Collaborative localization algorithm for wireless sensor networks using mobile anchors[C]//Proceedings of 2nd Asia-Pacific conference on computational intelligence and industrial applications.Wuhan,China:[s.n.],2009:309-312.

[12] Shi Q J,He C.Multi-power level mobile beacon assisted distributed node localization algorithm[J].Journal on Communications,2009,30(10):8-13.

[13] 姚忠孝,俞 立,董齐芬.基于移动信标的DV-Hop无线传感网络定位算法[J].传感技术学报,2009,22(10):1504-1509.

[14] Guo Zhongwen,Guo Ying,Hong Feng,et al.Perpendicular intersection:locating wireless sensors with mobile beacon[J].IEEE Transactions on Vehicular Technology,2010,59(7):3501-3509.

[15] 崔焕庆,王英龙,郭 强,等.多移动信标辅助的分布式节点定位方法[J].通信学报,2012,33(3):103-111.

[16] Zhong Z,Luo D,Liu S,et al.An adaptive localization approach for wireless sensor networks based on Gauss-Markov mobility model[J].Acta Automatical Sinica,2010,36(11):1557-1568.

A Mobile-beacon Based Localization Algorithm in Responsive Sensor Networks

XU Jun，WU Min，SHA Chao，NI Kai-yue，WANG Ru-chuan

(Computer and Software College of Nanjing University of Posts and Telecommunications,Nanjing 210003,China)

Compared with static anchor localization scheme,the localization algorithm based on multi-mobile anchor can improve the accuracy of the localization greatly.Due to restriction of the mobility,it can lead to the large error of location for the unknown nodes.The mobile-anchor localization proposed is on the basis of Hexagon-based model,where the central and the border anchors are applied to visit the relevant positions with corporation,and it can get the position information of the unknown nodes in shorter time.Besides，the design of the mobile planning can get rid of the redundant path and improve the accuracy and efficiency.Picking out of two with larger strength from the three messages and it can remove the result with larger error.Then from two messages,the two results of the position of the unknown node can be obtained.And according to the three messages,the only final result can be gotten.The algorithm of RSSI is improved and can get better accuracy of localization.Simulation results show that the proposed measure has the better accuracy of the localization and higher rate of efficiency.

Hexagon-based model;visiting with corporation;mobile beacon;RSSI

2016-02-18

2016-06-15 网络出版时间：2017-04-28

国家自然科学基金资助项目(61572260)；江苏省优秀青年基金(BK20160089)；江苏省研究生创新工程项目(SJZZ16_0147,SJZZ16_0149,SJZZ16_0150,KYLX15_0842)

徐 骏(1990-)，男，硕士研究生，研究方向为无线传感网定位技术；吴 敏，博士，副教授，研究方向为无线自组织网络协同信息处理技术；沙 超，博士，副教授，研究方向为无线传感网能耗均衡技术；王汝传，教授，研究方向为物联网信息处理技术。

http://kns.cnki.net/kcms/detail/61.1450.TP.20170428.1702.006.html

TP31

A

1673-629X(2017)06-0199-06

10.3969/j.issn.1673-629X.2017.06.042