WSNs中基于能量高效的单移动信标节点辅助定位方法

摘要

本发明涉及一种WSNs中基于能量高效的单移动信标节点辅助定位方法，WSNs模型包括多个随机部署的静态未知节点和一个单移动信标节点，其主要步骤包括：单移动信标节点通信半径的确定；网络分辨率的确定；单移动信标节点广播位置信息包的位置的部署；单移动信标节点的路径规划；单移动信标节点在移动的过程中周期性地广播位置信息包，位置信息包的内容包括此时移动信标节点的坐标信息和信标；静态未知节点不断监听并接收位置信息包，并采用三边测量法计算自身的位置坐标来完成定位。本发明在定位精度高的基础上减少单移动信标节点的能量消耗。此外，本发明还涉及到一种障碍存在时的单移动信标节点路径规划方法及此时广播信息包位置的部署方法。

说明书

技术领域

本发明属于无线传感器网络领域，尤其涉及一种WSNs中基于能量高效的单移动信标节点辅助定位方法。

背景技术

在WSNs中，确定未知节点的位置信息是一个非常重要的工作，因为未知节点给许多位置感知协议和应用程序提供了基本的支持。获得的信息需要和节点的位置相结合才能为观察者提供更准确的数据信息。另外，WSNs也可在监控应用中用于跟踪特定目标，所使用的跟踪算法也需要传感器节点提供相应的位置信息。这些需求都促进了WSNs中高效定位协议的发展。

定位就是在一个给定系统中寻找节点位置信息的过程。为了在一个完整的坐标系统中确定一个无线传感器网络的位置信息，一些节点需要采取一些方式提前知道自身的位置信息，如借助移动信标节点。所谓移动信标节点是指节点在感知区域中移动的同时能够广播自身的位置信息。未知节点定位通常包括两步：(1)两个邻居节点之间的距离测量；(2)在测量距离基础上的几何计算。定位协议可以分为两大类：基于测距的定位协议和基于预留的定位协议。在测距基础上的协议需要知道信标点的位置信息。根据待定点和信标点间的距离，就可以估算出待定点的位置。而无须测距的协议虽然不需要估算距离，但是仍然需要信标节点辅助，通过相关技术估计自身位置。

现阶段使用测距进行定位的都利用了固定节点的距离测量技术。因此其定位精度内在地受限于网络结构以及部署策略。因为实际中统一的网络部署不可能实现，所以部分网络可能会有较低的密度，并且邻节点可能不充足。另外，信标节点在网络中的位置对每个节点来说可能不都是最佳的。因为限制移动使得传感器网络拓扑结构改变很少，所以通过这些技术，某些节点的定位精度无法得到改善。此外，给所有节点都安装GPS设备是难以实现的，特别是对于大规模WSNs来说，而且移动信标节点在拐弯的过程中也会产生大量的能耗。因此使用一个配备有GPS系统的移动信标节点在未知节点之间移动并减少行进过程中拐角的数量，定期广播虚拟信标来帮助附近的位置节点进行定位是一种非常可行的定位方法。一些大型研究机构通过验证表明，移动信标节点区别于普通节点，并且可以通过改变行走路径提高定位精度。所以通过单个移动信标节点来辅助定位是一种有效的定位方法，移动信标节点的路径规划也成为了研究的重点。

目前针对无线传感器网络路径规划的相关研究文献如下：

1.Ou C等在2008年的《IEEE Transactions on Mobile Computing》上发表的文章“Sensor position determination with flying anchors in three-dimensional wireless sensor networks”，提出了一种定位算法。在此算法中，信标节点在区域中飞行，每个信标节点都配备有GPS装置，在飞行穿过感知区域的时候广播虚拟信标。感知区域中，每一个未知节点测量与能够收到的虚拟信标的距离，在基于几何原理的基础上估算其坐标位置。如果未知节点收到超过四个虚拟信标的信息，这四个虚拟信标将形成两个相互交叉的圆，并且有两条垂直于各自圆心的垂线。两条中垂线的相交处就被估算为未知节点的大致位置。这种算法虽然能够帮助未知节点定位，但是却没有涉及到路径规划。

2.Dimitrios Koutsonikolas等在2007年的《Computer Communication》上发表的文章“Path planning of mobile landmarks for localization in wireless sensor networks”，作者提出了一些改进后的算法。这三个算法分别叫做SCAN算法,DOUBLESCAN算法和HILBERT算法。在SCAN算法中，移动信标节点沿一个方向移动，比如在二维坐标系统中，沿y轴移动,但由于是沿一个方向移动，也没有增加其他处理方法，导致未知节点会受到若干个移动信标在共线位置发送的信息包从而影响定位效果。Double SCAN算法考虑了共线问题的存在，因此增加了一个在x轴方向上的移动，虽然一定程度上减轻了共线问题，但增加了路径长度从而增加了能耗。Hilbert算法由多个不封闭的小正方形组成，增加了很多拐点使得接收更多的非共线信息包。相比较而言，Hilbert算法提高了定位精度，但是它并没有考虑转弯能量的消耗问题。

3.Rui Huang等在2007年的“The Fifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops”上发表的文章“Static path planning for mobile beacons to localize sensor networks”，提出了优化的路径算法，在提高定位精度的同时也能够使得路径长度有限。这两种算法分别叫做CIRCLES算法和S-CURVES算法。这两种算法都是预先给出路径轨迹，不参考实际传感器节点的分布。两种算法可以避免虚拟信标共线问题。但是CIRCLES算法中的移动锚节点没有遍历整个监测区域，监测区域四个角附近的未知节点因收不到足够多的虚拟信标而无法定位。此外，两种算法都是在信标节点轨迹附近的节点能较为精确地获得位置信息。离轨迹较远的节点定位误差较大，甚至部分未知节点不在信标节点通信范围内，因而不能定位。

4.Baoli Zhang等在2009年的“In Proc.of the 2009 Second Asia-Pacific Conference on Computational Intelligence and Industrial Applications”上发表的文章“Collaborative localization algorithm for wireless sensor networks using mobile anchors”，提出了GMAN算法。该算法中移动信标节点的个数为三个。三个可移动的节点形成正三角形。在行进过程中，相对位置保持不变。移动信标节点组按照从左至右，从下至上的顺序在传感器网络中进行遍历。该算法虽然利用了正三角形定位精度最高的原理，但并没有说明移动信标节点如何进行广播，也没有说明所形成正三角形边长与网络分辨率的关系。

5.Javad Rezazadeh等在2014年的《IEEE SENSORS JOURNAL》上发表的文章“Superior Path Planning Mechanism for Mobile Beacon-Assisted Localization in Wireless Sensor Networks”，并在这篇文章中提出了Z-curve算法。根据该路径规划算法，移动信标节点在定位过程中呈“Z”行进，可以解决三点共线问题，从而在精确地定位静态未知节点的同时减少进行距离。此外，Z-curve算法也对障碍进行了处理，可以在监测区域中存在障碍的情况下进行定位。该算法虽然能够提高未知节点的定位精度，但是根据路径规划，移动信标节点在行进的过程中需要多次改变行进方向，虽然减少了路径长度，但是大大增加了拐角数量，从而增加了能量消耗。

综上所述，虽然移动信标路径规划取得了很大进展，但仍有一些问题需要进一步研究：

(1)现有的大部分研究没有考虑移动信标节点启动、转弯、匀速行进过程中的能量消耗都是将移动信标节点基于理想的情况下，或者是仅仅考虑收发信息包的能量消耗；

(2)大多数路径规划算法可以对监测区域内部的未知节点进行较为精确的定位，而对于网络边沿处节点不能精确地进行定位；

(3)大多数定位较为精确的路径规划算法的转弯过程很多，从而能量消耗大，但转弯过程不多的算法定位却不够精确。

发明内容

本发明的目的是提供一种WSNs中基于能量高效的单移动信标节点辅助定位方法，该方法在提高未知节点定位精度的基础上，使单移动信标节点尽可能沿直线行进，减少拐角数量，从而减少能量消耗，使在WSNs中的静止的未知节点完成自己的定位。

为解决上述技术问题，本发明采用的技术方案是：

一种WSNs中基于能量高效的单移动信标节点辅助定位方法，WSNs模型包括多个随机部署的静态未知节点和一个单移动信标节点，其步骤包括：

(1)单移动信标配备有GPS定位装置，确定单移动信标节点通信半径R，移动速度v；

(2)根据通信半径R确定网络分辨率r，网络分辨率即通信间隔距离；

(3)根据网络分辨率r，部署单移动信标节点广播位置信息包的位置；

(4)根据广播位置信息包的位置对单移动信标节点进行路径规划；

(5)单移动信标节点根据所规划的路径行进，在移动的过程中周期性地广播位置信息包，位置信息包包括此时移动单信标节点的坐标信息和信标ID；

(6)随机分布在WSNs中的静止的未知节点不断监听并接收位置信息包，当能够收到的三个不共线的信标的位置信息能够形成正三角形，且未知节点位于正三角形内，则采用三边测量法计算自身的位置坐标来完成定位；

(7)当单移动信标节点所在的WSNs中存在障碍，单移动信标节点配备有摄像头以及超声波检测装置，能够识别并计算与障碍之间的距离，采取避障措施在避开障碍的同时，也能够给周围未知节点广播位置信息包；当存在障碍时，若广播信息包的位置能够形成正三角形，且未知节点位于正三角形内，则采用正三角形三边测量法计算自身的位置坐标来完成定位，否则采用普通三角形三边测量法完成定位。

上述步骤(2)中网络分辨率r指的是单移动信标节点周期性广播的两个位置信息包之间的距离。

上述步骤(3)中单移动信标节点广播位置信息包的位置部署方法如下：

在长为l宽为h的区域中，n_l代表在长为l的长度区域中的直线需排列正三角形的个数，n_h代表在宽为h的长度的直线需排列正三角形的个数，其中n_l和n_h需要满足以下条件：

$n_l\ge \frac{l+r}{d},n_h\ge \frac{2h}{\sqrt{3}d}$

即：和其中d＝r，d表示正三角形的边长，网络分辨率r＝R，并在此基础上在监测区域中虚拟排列正三角形，使整个区域都能够被正三角形所覆盖的最理想情况，正三角形的顶点则为单移动信标节点广播信息包的位置，为了保证整个区域都能够被正三角形所覆盖，正三角形在边界处都有适当的延伸。

上述步骤(4)中路径规划指的是单移动信标节点从长为l的一边出发，沿长的方向以恒定速度v进行遍历，两条相邻路径之间的距离为直到遍历完所有广播信息包的位置，并在这些预先设计的位置处周期性地广播单移动信标节点实时位置信息。

上述步骤(6)中未知节点不断监听接收来自单移动信标节点发送的信息包，当能够收到三个信息包，且信息包的位置能够构成未知节点在其内部的正三角形时采取三边测量法计算未知节点自身的位置坐标；若不能收到三个信标，则继续监听、等待。

上述步骤(7)中的避障措施是指：当单移动信标节点一旦识别到障碍存在并且能够监测到障碍边界时，采取判别算法计算出较为靠近的边界，向边界点移动后绕障碍行进，当到达下一边界点时，计算离该点最近的原路径上的广播位置点，并向其移动；在避障过程中，单移动信标节点除了在每个拐点处广播位置信息包的同时，也每隔时间向周围节点广播位置信息包；若障碍过大，单移动信标节点不能识别出障碍的任一边界，移动信标节点则继续前进，靠近障碍后在每个拐角处始终右拐行进，直到回到正常的行驶路径，在避障过程中，单移动信标节点除了在每个拐点处广播位置信息包的同时，也每隔时间向周围节点广播位置信息包。

上述的判别算法指的是：

单移动信标节点配备有摄像头采集回的图像，假设前方有障碍时，摄像头采集回的是深色图像，没有障碍的部分显示浅色图像；深色图像和浅色图像构成整个图像；

记i_left、i_right分别为单移动信标节点采集到左、右两端浅色图像所占图像比例的大小：

当i_left＞i_right，监测到距离左边界较近，则向左边界行进；

当i_left＜i_right，监测到距离右边界较近，则向右边界行进；

当i_left＝i_right，两端边界都不能监测，则继续行进。

与现有技术相比，本发明所具有的有益效果是：

(1)定位过程中不需要额外的通信开销，仅通过接收信号强度测量即可完成定位，并且移动信标广播的信标包的位置可以构成正三角形，使定位率及定位精确度大幅提升；

(2)单移动信标节点在行进的过程中适当地延伸出监测区域，使得预先部署的广播信息包的位置所构成的多个互不重叠的正三角形可以覆盖整个监测区域；

(3)本发明中单移动信标节点根据预先部署的广播信息包的位置沿直线行进，并周期性地在部署的位置处广播包含自身实时位置信息的信息包，因此虽然沿直线行进，但由于对广播位置的部署，从而在一定程度上解决了共线问题。

(4)本发明的避障措施，可以减少避障过程中的移动距离，增加广播信息包的个数，从而提高障碍存在时的定位精度。

附图说明

图1为本发明的流程图；

图2为单移动信标节点广播信息包的位置部署图；

图3为单移动信标节点的路径规划图；

图4为未知节点接收到的三个信标呈正三角形示意图；

图5为移动信标节点监测到右边界情况下的行进路径；

图6为移动信标节点监测到左边界情况下的行进路径；

图7为移动信标节点不能监测到任一边界的三种情况下的行进路径；

具体实施方式

下面结合附图对本发明作进一步的详细说明。

如图1所示，一种WSNs中基于能量高效的单移动信标节点辅助定位方法，WSNs模型包括多个随机部署的静态未知节点和一个单移动信标节点，其步骤包括：

(1)单移动信标配备有GPS定位装置，确定单移动信标节点通信半径R，移动速度v；

(2)根据通信半径R确定网络分辨率r，网络分辨率即通信间隔距离；

(3)根据网络分辨率r，部署单移动信标节点广播位置信息包的位置；

(4)根据广播位置信息包的位置对单移动信标节点进行路径规划；

(5)单移动信标节点根据所规划的路径行进，在移动的过程中周期性地广播位置信息包，位置信息包包括此时移动单信标节点的坐标信息和信标ID；

(6)随机分布在WSNs中的静止的未知节点不断监听并接收位置信息包，当能够收到的三个不共线的信标的位置信息能够形成正三角形，且未知节点位于正三角形内，则采用三边测量法计算自身的位置坐标来完成定位；

(7)当单移动信标节点所在的WSNs中存在障碍，单移动信标节点配备有摄像头以及超声波检测装置，能够识别并计算与障碍之间的距离，采取避障措施在避开障碍的同时，也能够给周围未知节点广播位置信息包；当存在障碍时，若广播信息包的位置能够形成正三角形，且未知节点位于正三角形内，则采用正三角形三边测量法计算自身的位置坐标来完成定位，否则采用普通三角形三边测量法完成定位。

上述步骤(2)中网络分辨率r指的是单移动信标节点周期性广播的两个位置信息包之间的距离。

上述步骤(3)中单移动信标节点广播位置信息包的位置部署方法如下：

在长为l宽为h的区域中，n_l代表在长为l的长度区域中的直线需排列正三角形的个数，n_h代表在宽为h的长度的直线需排列正三角形的个数，其中n_l和n_h需要满足以下条件：

$n_l\ge \frac{l+r}{d},n_h\ge \frac{2h}{\sqrt{3}d}$

即：和其中d＝r，d表示正三角形的边长，网络分辨率r＝R，并在此基础上在监测区域中虚拟排列正三角形，使整个区域都能够被正三角形所覆盖的最理想情况，正三角形的顶点则为单移动信标节点广播信息包的位置，为了保证整个区域都能够被正三角形所覆盖，正三角形在边界处都有适当的延伸。

上述步骤(4)中路径规划指的是单移动信标节点从长为l的一边出发，沿长的方向以恒定速度v进行遍历，两条相邻路径之间的距离为直到遍历完所有广播信息包的位置，并在这些预先设计的位置处周期性地广播单移动信标节点实时位置信息。

上述步骤(6)中未知节点不断监听接收来自单移动信标节点发送的信息包，当能够收到三个信息包，且信息包的位置能够构成未知节点在其内部的正三角形时采取三边测量法计算未知节点自身的位置坐标；若不能收到三个信标，则继续监听、等待。

上述步骤(7)中的避障措施是指：当单移动信标节点一旦识别到障碍存在并且能够监测到障碍边界时，采取判别算法计算出较为靠近的边界，向边界点移动后绕障碍行进，当到达下一边界点时，计算离该点最近的原路径上的广播位置点，并向其移动；在避障过程中，单移动信标节点除了在每个拐点处广播位置信息包的同时，也每隔时间向周围节点广播位置信息包；若障碍过大，单移动信标节点不能识别出障碍的任一边界，移动信标节点则继续前进，靠近障碍后在每个拐角处始终右拐行进，直到回到正常的行驶路径，在避障过程中，单移动信标节点除了在每个拐点处广播位置信息包的同时，也每隔时间向周围节点广播位置信息包。

上述的判别算法指的是：

单移动信标节点配备有摄像头采集回的图像，假设前方有障碍时，摄像头采集回的是深色图像，没有障碍的部分显示浅色图像；深色图像和浅色图像构成整个图像；

记i_left、i_right分别为单移动信标节点采集到左、右两端浅色图像所占图像比例的大小：

当i_left＞i_right，监测到距离左边界较近，则向左边界行进；

当i_left＜i_right，监测到距离右边界较近，则向右边界行进；

当i_left＝i_right，两端边界都不能监测，则继续行进。

实施例：

当n_l＝6和n_h＝5时，单移动信标节点广播信息包的位置部署图如图2所示。单移动信标节点的通信半径为R，网络分辨率r＝R。各个广播信息包的位置点可以形成若干个互不重叠的正三角形，正三角形的边长d＝r＝R。单移动信标节点从监测区域长l的一端出发，沿直线以恒定速度v移动，从下往上依次遍历所有的广播信息包的位置，为了保证可操控性，单移动信标节点在左右两端改变移动方向的位置分别在两条直线上，如图3所示。当到达预先部署的广播信息包的位置时，单移动信标节点广播包含自身实时位置信息的信息包给周围的静态未知节点。

未知节点不断监听、接收信息包，用用接收信号强度法(received signal strength indicator,RSSI)测量到移动信标发送此信息包位置的距离，即其中P_R(d)表示接收信号功率，P_T表示发射功率，PL(d₀)表示传播距离为d₀时的路径损耗，η为路径损耗指数，d为发送节点和接收节点间的距离。当静态未知节点能够收到三个非共线的信标，且三个信标可以组成正三角形，未知节点位于正三角形内，则未知节点利用三边测量法(trilateration)计算自身的位置。如图4所示，假设未知节点的坐标为(x,y)，未知节点能够收到的三个虚拟信标的坐标为(x_a,y_a)，(x_b,y_b)，(x_c,y_c)，能够形成正三角形，未知节点的计算公式为：

$\left(\begin{array}{c}{(x-x_a)}^2+{(y-y_a)}^2=d_a^2\\ {(x-x_b)}^2+{(y-y_b)}^2=d_b^2\\ {(x-x_c)}^2+{(y-y_c)}^2=d_c^2\end{array}\right)$

其中d_a，d_b，d_c分别为未知节点到三个虚拟信标(x_a,y_a)，(x_b,y_b)和(x_c,y_c)的距离。

当区域中存在障碍物时(本发明假设障碍物为长方形)，图5，图6，图7分别表示移动信标节点监测到右边界，左边界和不能监测到任一边界的三种情况下的行进路径。当能够监测到距离右边界近时，如图5所示，移动信标向边界移动，然后沿边界行进到达下一边界后计算找到原始路径上离此位置最近的未被障碍覆盖的广播信息包的位置，并向其移动，完成避障。整个避障过程除了在拐角处会广播位置信息包，每隔时刻，移动信标也会广播位置信息给周围的未知节点。图6表示了与图5相反的情况，移动信标向障碍的左边界行进的过程。当不能监测到障碍边界时，则移动信标继续前进，遇到障碍或到达边界时都右拐，广播信息包过程与前两种相似，直到回到正常行驶路径，图7给出了示意图。

本发明可以在定位精度高的基础上，减少能量消耗；适用于传感器节点随机部署的无线传感器网络；使用单个移动信标节点部署较为简单；也给出了相应的避障措施。

以上广播信息包位置的部署方法以及移动信标节点的路径规划方法是本发明中的实施方式，但并不能因此而理解为对本发明专利范围的限制。应当指出的是，在不脱离本发明提出的方法前提下，无线传感器网络移动信标路径规划方法有若干新的实施方案以及对本方案的变形和改进，这些都属于本发明的保护范围。因此，本发明专利的保护范围应以所附权利要求为准。