一种基于增量定位的移动信标辅助节点定位算法＊

左 丹 莫建军 肖 胜

（1.海军装备部 北京 100083）（2.海军92980部队 湛江 524000）（3.海军工程大学 武汉 430033）

1 引言

无线传感器网络（wireless sensor network，WSN）是一种分布式、自组织网络，具有覆盖面广、自适应性强、布局方便灵活等许多优点，在民用、航空和军事领域均具有非常广阔的应用前景。

节点定位是无线传感器网络中一项关键支撑技术和研究热点。受资源、成本和应用环境的限制，每个节点均配置GPS接收器或者人工部署显得不现实，因此研究适合无线传感器网络特点的定位机制十分重要［1］。目前的方法大多是基于多个固定信标节点实现的，如三边定位法、三角测量法、DV－HOP法、质心法等［2～4］，要想取得较高的定位精度，往往对信标节点的排布方式和数量存在较高的要求，还带来了许多问题，主要表现在：在定位完成以后，信标节点往往变为普通节点使用，信标节点过多会造成资源浪费，提高网络成本；另外，信标节点过多可能导致计算负荷以及通讯负荷过大，影响实时性和可靠性。

因此，有人提出利用一个或几个移动信标来辅助定位。在这种方式下，装备了GPS或其它定位装置的移动信标节点在部署区域内移动，间隔一定距离或时间后发送当前位置信息，未知节点根据接收到的信息完成自身位置估计，从而能减少信标节点数目，有效降低网络成本［5～9］。这种方式能够有效节约网络成本，同时具有较高的定位精度。但是，移动信标运动过程结束后，少量节点由于离移动信标的路径较远，从而难以接收足够的定位信息。针对这种情况，为提高定位覆盖率，本文选取部分符合条件的节点对接收信息进行转发，提出一种基于增量定位的移动信标辅助节点定位算法。

2 相关模型

2.1 信号传输模型

这里采用距离边界模型。假设发送节点可以将信号传输给其通信半径范围内的未知节点。假设d表示发送节点与未知节点之间的距离，R表示发送节点的通信半径（发送节点可能是移动信标，也可能是普通节点）。未知节点接收到移动信标广播信息的概率为P（d）。模型的数学描述如下：

同样的，如果未知节点与信标之间的距离小于R，则能够接收到发送节点的广播信息；否则，未知节点接收不到其广播信息。

2.2 增量定位模型

如果移动信标的路径间距较大，在定位过程结束后，可能有少量节点可能由于离移动信标的路径较远，从而难以接收足够的定位信息。为克服该问题，本文选取部分普通节点对接收到的信息进行转发，未知节点不但可以利用移动信标的连续广播信息，而且可以结合其它普通节点的转发信息完成增量定位，从而提高算法的定位覆盖率。

2.2.1 利用移动信标的连续广播信息

基于如下判断：如果移动信标连续两次广播信息中有且仅有一次被某个未知节点接收，则该未知节点必将刚刚进入或离开移动信标的信号传输范围。为简化计算，假设移动信标以速度v作匀速直线运动，其通信半径为Rd，广播周期为T。图1显示了节点利用移动信标的连续广播信息进行定位的示意图。

图1 利用移动信标的连续广播信息定位

如图所示，当移动信标处于A点时，未知节点未接收到广播信息，而经过一个广播周期后，未知节点接收到移动信标在B点的广播信息。可以推断，未知节点必定处于以A点为圆心、Rd为半径的通信圆外，同时处于以B点为圆心、Rd为半径的通信圆内。假设经过经过k个广播周期后，信标节点运动至C点，此时未知节点能够接收到最后一个广播信息（未能接收到信标在后一广播位置D点发送的信息），同样可以推断，未知节点必定在以C点为圆心、Rd为半径的通信圆内，同时处于以D点为圆心、Rd为半径的通信圆外。利用所得到的约束条件，可以获取未知节点初步的可能区域［12］。

2.2.2 利用普通节点的转发信息

为提高定位覆盖率，选取部分普通节点对接收的移动信标数据包进行转发，以实现对未知节点的增量定位。数据包内容包括ID和信标的位置信息。为减少能量消耗，节点转发信息的频率并不是周期性的，而是每当接收到移动信标的广播信息后，才向外转发一次。这样可以保证其每次转发的信息都包含不同的信标位置信息，从而提高转发效率。图2为该过程的示意图。

图2 普通节点转发广播信息示意图

为减少累积误差的影响，要求满足以下条件的节点才能被选作转发节点：

1）该节点本身已完成定位，即至少接收到三个（或以上）来自移动信标或其它节点的非共线位置信息。

2）该节点之前接收到的广播信息中有一半以上来自移动信标。

另外，由于未知节点可以通过接收其它节点的数据包来进行定位，数据包生存期越大，定位覆盖率也越大。但是，数据包的生存期越大，数据包的收发次数就越大，通信开销也越大，这里设置数据包的生存期为两跳。当一跳内的普通节点收到信标后，包的生存期减1，并将添加该节点的位置信息字段，向邻居节点转发，邻居节点接收后根据ID判断此数据包是否已经存在，若不存在则添加此包，否则丢弃。可以看出，该规则本质上是一个简单的分布式最短路由协议。表1为数据包的主要字段。

表1 数据包主要字段（a）移动信标数据包

其中，TI（Transmit Indicator）为转发标识，TI＝0表示该数据包来自移动信标，TI＝1表示该广播信息来自普通节点。

通过数据包的转发，部分处于移动信标通信范围之外的节点也可以得到定位信息，从而可以提高定位覆盖率；同时，由于只有满足一定约束条件的普通节点会被选中进行转发，因此节点的定位误差不会产生较大的累积。

3 算法流程

每个普通节点都建立一个数据链表，用来存储接收到的广播信息，未知节点通过接收移动信标和其它转发节点的数据包进行定位。这里对算法流程进行简要描述：

1）移动信标在运动过程中不断周期性的广播信息。移动信标按照实现规划的路径运动，广播包括自身位置的数据包。

2）普通节点接收到数据包后，将数据包存储在自身数据链表中，并判断是否满足前面介绍的转发节点条件。（1）条件满足，则对TI进行判别：如TI＝0，将该数据包进行转发，并在该数据包中添加自身位置信息字段；如TI＝1，不进行转发。（2）条件不满足，则仅将该信息用作节点自身定位，不进行转发。

3）随着移动信标的不断运动，网络中的定位节点将不断增多，而未定位节点将越来越少，直至整个定位过程结束。

4 仿真结果

为验证所述算法的有效性，进行了仿真分析。初始条件设置如下：200个浮标节点随机分布在2400m×2400m的某矩形区域，设左下角为坐标原点。移动信标的运动路径如图3所示，起点为（－200，0），终点为（2600，2400），路径平行线之间的间隔L＝400m，移动信标的速度为20m／s，通信半径为200m，普通节点的通信半径为100m，信号传输的不规则度DOI＝0.05。

4.1 与质心定位方法的比较

分别在L＝400m和L＝600m的条件下，将传统方法（普通节点不转发信息）和基于增量定位的定位方法进行了比较，结果分别如表2和表3所示。

图3 移动信标的运动路径

表2 间距为400m的算法性能比较

表3 间距为600m的算法性能比较

可以看出，当L＝400m时，两种方法的定位覆盖率几乎都达到100%。但当L＝600m时，由于路径间距大于两倍通信半径，移动信标的广播信息难以覆盖整个网络，此时，传统方法的定位覆盖率较之前下降很快，而所提出的方法通过选取部分节点对移动信标的广播信息进行转发，能够维持较高的定位覆盖率。同时，未知节点还能获取更多的定位信息，因此获得了较好的定位精度。此时，基于增量定位的移动信标辅助节点定位算法在定位覆盖率和定位精度两项指标上均优于传统方法，更适用于移动信标路径间距较大的场合。

4.2 与质心定位方法的比较

图4 不同广播周期下的定位精度

在前面仿真场景的基础上，保持其它参数不变，调整移动信标的广播周期，得到的平均定位误差如图4所示。可见，随着广播周期的增长，该算法的平均定位误差也显著增加。这主要是由于广播周期变大后，节点获取的定位信息将减少。同时，在信标通信半径较大的情况下，未知节点将获得更多来自移动信标的广播信息，因此平均定位误差也将减小。

另外，在前面仿真场景的基础上，调整普通节点的通信半径，算法性能的仿真结果如表4所示。

表4 节点通信半径对算法性能的影响

5 结语

本文针对无线传感器网络的节点定位问题，初步考虑节点之间的协作，提出一种基于增量定位的移动信标辅助节点定位算法。该算法针对网络中可能有少量节点难以接收足够定位信息的情况，选取部分节点对接收信息进行转发，以提高定位覆盖率。通过仿真可以看出，在移动信标的路径长度和通信半径不变的情况下，该方法可获取较高的定位覆盖率，适用于信标路径间距较大的场合。

［1］Akyildiz I F，Su W.Wireless Sensor Network：A Survey［J］.Computer Networks，2002，38（4）：393－422.

［2］Patwari N，Hero III AO，Perkins M，et al.Relative location estimation in wireless sensor networks［J］.IEEE Trans on Signal Processing，2003，51（8）：2137－2148.

［3］Bulusu N，Heidemann J，Estrin D.GPS－less low cost outdoor localization for very small devices［C］／／IEEE Personal Communication，2000，7（5）：28－34.

［4］Bahl P，Padmanabhan VN.RADAR：An In－building RF－based User Location and Tracking System［C］／／Proc.of the 19th Annual Joint Conference on IEEE Computer and Communications Societies.Aviv，Israel：IEEE Press，2000：775－784.

［5］Sichitiu ML，Ramadurai V.Localization of Wireless Sensor Networks with a Mobile Beacon［C］／／Proceedings of the 1st IEEE Conference on Mobile Ad－Hoc and Sensor Systems.IEEE Computer Society，2004：174－183.

［6］Pathirana P N，Bulusu N.Node localization using mobile robots in delay－tolerant sensor networks［J］.IEEE Transactions on Mobile Computing，2005，4（3）：285－296.

［7］Priyantha N，Balakrishnan.Mobile assiated localization in wireless sensor network［C］／／Proceedings of 24th IEEE Conference on Computer Communication.Miami，USA，2005：172－183.

［8］Dimitrios K，Saumitra M，Charlie Y.Path Planning of Mobile Landmarks for Localization in Wireless Sensor Networks［J］.Computer Communications，2007（30）：2577－2592.

［9］白凤娥，孔新店，牟汇慧.无线传感器网络LEACH路由协议改进算法［J］.计算机与数字工程，2011，39（2）.

［10］孙昕，王鑫.一种改进的无线传感器网络动态密钥管理方案［J］.计算机与数字工程，2011，39（10）.

［11］Aram G，Bhaskar K，Kristina L，et al.Distributed online localization in sensor networks using a moving target［C］／／Proceedings of the 3rd International Conference on Information Processing in Sensor Networks.Los Angeles，USA，2004：61－70.

［12］Bin Xiao，Hekang Chen，Shuigeng Zhou.Distributed Localization Using a Moving Beacon in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed System，2008，19（5）：587－600.