无线传感器网络中基于正六边形的移动锚节点路径规划方法

摘要

本发明涉及一种无线传感器网络中基于正六边形的移动锚节点路径规划方法，所述网络包括多个静止的未知节点和一个移动的锚节点，其步骤包括：移动锚节点以恒定速度v移动，每隔时间间隔t，以此刻所在位置为圆心，R为通信半径，广播信标信息，信标信息包括该时刻移动锚节点的位置和信标ID，移动锚节点的移动路径为正六边形，且R＝vt；未知节点不断监听、接收信标信息，若收到的三个信标位置可组成正三角形，且未知节点位于正三角形内，则未知节点通过三边测量法计算自身位置；当移动锚节点移动至网络区域边界处时，采用边界区域补偿方法保证边界未知节点可以收到至少三个不共线的信标位置。本发明定位精度高，网络成本低，且不易受环境影响。

说明书

技术领域

本发明属于无线传感器网络领域，尤其涉及一种无线传感器网络中基于正六边形的移动 锚节点路径规划方法。

背景技术

近年来，随着无线通信和数字电子技术的发展，无线传感器网络(Wireless Sensor  Networks,WSNs)在环境监测、目标跟踪、智能交通等诸多领域得到了广泛的应用，并且已 得到政府部门、工业界、学术界和科研机构的极大关注。位置信息对WSNs的应用具有至 关重要的意义，有效而可靠的定位技术及其优化方法是WSNs技术走向实际应用必须攻克 的关键支撑技术。WSNs的定位算法主要分为两大类：基于锚节点和非基于锚节点的定位算 法，锚节点就是可以预先获取自身位置的节点，基于锚节点的定位算法用锚节点定位未知节 点，而非基于锚节点的定位算法主要计算节点间的相对位置。为了提高定位精度、节约网络 成本，比较实用的定位方法是利用一些移动锚节点，按照有效的规划路径移动，通过发送包 含自身坐标的信息来定位其他节点。移动锚节点路径规划问题可分为两类：静态路径规划和 动态路径规划。静态路径规划是指移动锚节点按照预先规划好的路径移动。动态路径规划是 指移动锚节点根据节点的分布情况动态规划移动锚节点路径。

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

1.Rui Huang等在2007年的《In Proceeding of 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，其目的在于减少锚节点辅助定位过程中广播共线的位置信息。移 动锚节点在移动过程中每隔一个周期广播其位置信息，当未知节点收到三个非共线的信标信 息时，就可以计算自身位置。这两种路径规划方法虽然路径长度相对于其他路径规划算法较 短，并且相应的节省网络能耗，但移动锚节点无法到达监测区域边界，导致边缘节点接收不 到足够的信标信息从而无法定位。

2.Dimitrios Koutsonikolas等在2007年的《Computer Communication》上发表的文章 “Path planning of mobile landmarks for localization in wireless sensor networks”中提出三种 锚节点移动方法：Scan，Double Scan和Hilbert，其目的在于减少网络成本，用一个移动锚 节点替代多个静止的锚节点辅助未知节点定位。作者通过理论和实验对比分析提出的三种路 规划方法的优缺点，三种方法中Scan的移动路径最短，但其沿y轴直线型的移动路径会造 成未知节点接收到若干个共线的移动锚节点信标信号，尤其当锚节点的通信半径过小，导致 许多未知节点无法定位；Double Scan是在Scan的基础上增加移动锚节点在x轴方向上移动 路径，这种路径规划方法解决了信标信息共线问题，但增加了移动锚节点的移动路径长度， 导致了网络能耗增加；与Scan和Double Scan相比，Hilbert是一种能填充满一个平面正方 形的分形曲线，这种移动路径在定位过程中，能够有效减少共线的信标信号，提高定位率， 同时移动路径长度小于Double Scan。

3.Hongjun Li等在2009年的《Journal of Computer Research and Development》上发表 的文章“Path Planning for Mobile Anchor Node in Localization for Wireless Sensor Networks” 把图论引入到无线传感器网络节点定位系统中。把无线传感器网络看成一个连通的节点无向 图，把路径规划问题转化为图的生成树及遍历问题，提出两种动态路径规划算法：宽度优先 算法和回溯式贪婪算法。相比静态路径规划，动态路径规划由未知节点的分布和位置情况来 实时决定移动锚节点的路径，使得移动锚节点的移动更具灵活性，且节约网络能量，但是路 径的长度和定位率两方面的问题还需要解决。

4.Huanqing Cui等在2012年的《Computers and Electrical Engineering》上发表的 “Four-mobile-beacon assisted localization in three-dimensional wireless sensor networks”中提 出多锚节点组移动路径规划方法来定位三维空间中的未知节点，即四个移动锚节点构成正四 面体按照RWP(random waypoint)移动模型和LAYERED-SCAN移动模型组移动来辅助定位 空间中的未知节点。当未知节点接收到至少一组同时到达的三个或者四个信标信号时，可用 加权质心算法计算出自身位置。当未知节点接收到的同时到达的信标信号小于三个时，未知 节点无法定位。文章对比了四个移动锚节点和单个移动锚节点在RWP移动模型和 LAYERED-SCAN移动模型下使用多边定位算法和加权质心定位算法的网络性能：即一跳范 围内可定位的未知节点个数、定位精确度、计算和通信开销、路径长度。仿真结果表明四个 移动锚节点采用LAYERED-SCAN移动模型及加权质心定位算法的网络性能最优。但是这 样密集的网络遍历并不适用于稀疏部署的网络。

5.Chia-Ho Ou等在2013年的《IEEE Sensors Journal》上发表的文章“Path planning  algorithm for mobile anchor-based localization in wireless sensor networks”中提出了一种移动 锚节点路径规划方案，用于减少定位误差并且保证所有节点可以确定自身位置，同时提出了 有障碍物情况下的移动锚节点路径规划算法。文章对Ssu等人提出的基于初等几何中“弦的 垂直平分线通过圆心”这一性质来定位未知节点的方案进行改进，即若移动锚节点经过未知 节点感知范围内两次，则可以以未知节点所在位置为圆心，与感知范围边界的四个交点的连 线为弦，形成两条交线，用于计算圆心即未知节点的位置。提出的移动锚节点路径规划算法 可以有效解决过四个交点的直线形成的两条弦较短带来的较大定位误差的问题，保证两条弦 的长度总是大于R为节点的传输半径。该移动锚节点路径规划算法相对于改进的算 法减小了定位误差，提高了定位率。

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

（1）传统的移动锚节点路径规划方法存在信标信息共线问题和边界未知节点难以定位 问题，导致网络定位精度低、定位覆盖率低和能量消耗高。

（2）大多数的路径规划方法使用一个移动锚节点，虽然能节约网络成本，但是降低了整 个网络的定位效率，在实际应用中受到限制。

发明内容

本发明的目的是提供一种适用于单个移动锚节点辅助定位的无线传感器网络定位方法， 该定位方法定位精度高、不易受环境因素的影响、网络成本低且能够有效定位网络边界未知 节点。

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

一种无线传感器网络中基于正六边形的移动锚节点路径规划方法，其步骤包括：

（1）根据监测区域大小，确定合适的移动锚节点通信半径R；

（2）移动锚节点计算移动路径，并以恒定速度v移动，每隔时间间隔t以此刻所在位置 为圆心，R为通信半径，广播信标信息，信标信息包括该时刻移动锚节点的位置和信标ID， 移动锚节点的移动路径为正六边形，且R＝vt；

（3）未知节点不断监听、接收信标信息，用接收信号强度法（received signal strength  indicator,RSSI）测量到移动锚节点间的距离，若监测区域内的未知节点接收到的三个信标 位置可组成正三角形，且未知节点位于正三角形内，则未知节点通过三边测量法（trilateration） 计算自身位置；

（4）当移动锚节点移动至监测区域边界处时，采用边界区域补偿方法保证边界未知节点 可接收到至少三个不共线的信标信息，即使移动锚节点以同样的速度沿圆形监测区域边界环 绕一周，并以同样的时间间隔广播信标信息；若未知节点位于接收到的三个信标位置组成的 三角形内，则以接收到的三个信标坐标的平均值作为未知节点的位置。

上述移动锚节点的通信半径R的具体设定方法为：假设监测区域半径为R_network，取合 适的移动锚节点通信半径R，使得R_network＝nR，n为正六边形的个数且为正整数。

上述移动锚节点具有GPS定位装置，作为定位未知节点的信标节点，移动锚节点以R为 通信半径，向其周围的未知节点广播包含其位置信息和自身ID的信标信息数据包。

上述锚节移动点路径为正六边形，正六边形的边长以锚节点通信半径R递增，即各正 六边形分别内切于半径以R递增的同心圆，直至第n个正六边形路径内切于圆形监测区域。

上述每个正六边形都可以划分为若干个边长相等的正三角形，满足正三角形边长a等于 锚节点通信半径R，即a＝R＝vt。

上述移动锚节点的路径计算方法为：移动锚节点初始时位于监测区域中心（x₀,y₀），以 （x₀,y₀）为原点，建立直角坐标系，移动锚节点从（x₀,y₀）出发，以速度v移动至之后沿着边长为R的正六边形路径移动，每隔时间t发送一次信标信息，当移动锚节点再次 到达点时，向点处移动，之后沿着边长为2R的正六边形路径移动， 每隔时间t发送一次信标信息，如此循环，使得每次正六边形路径的边长增加R，直至第n 个正六边形路径内切于圆形监测区域。

上述移动锚节点边界区域补偿方法具体为：当移动锚节点第二次到达点时，移动锚节点以同样的速度沿圆形监测区域边界环绕一周，并以同样的时间间隔广播信标 信息。

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

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

（2）对节点密度没有限制，无论是在密集网络还是在稀疏网络中，对辅助定位的效果没 有影响；

（3）本发明只需要一个移动锚节点，即可获知无线传感器网络区域内所有未知节点的位 置信息，降低了网络的成本。

（4）本发明针对在移动锚节点路径规划中存在边界未知节点无法定位的情况，提出边界 区域补偿方法，保证移动锚节点路径覆盖整个监测区域。

附图说明

图1为本发明无线传感器网络中基于正六边形的移动锚节点路径规划方法的流程图；

图2为未知节点接收到的三个信标位置坐标计算示意图；

图3为边界未知节点接收到的三个信标位置坐标计算示意图；

图4为未知节点随机分布图；

图5为移动移动锚节点路径和发射信标信息位置的示意图；

图6为移动锚节点边界区域补偿方法示意图。

具体实施方式

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

如图1所示，一种无线传感器网络中基于正六边形的移动锚节点路径规划方法，其步骤 包括：

（1）根据监测区域大小，确定合适的移动锚节点通信半径R。

（2）移动锚节点计算移动路径，并以恒定速度v移动，每隔时间间隔t以此刻所在位置 为圆心，R为通信半径，广播信标信息，信标信息包括该时刻移动锚节点的位置和信标ID， 移动锚节点的移动路径为正六边形，且R＝vt。

（3）未知节点不断监听、接收信标信息，用接收信号强度法（received signal strength  indicator,RSSI）测量到移动锚节点间的距离，即$P_R\left(d\right)=P_T-\mathrm{PL}\left(d_0\right)-10\eta {\log }_{10}\left(\frac{d}{d_0}\right),$其 中P_R(d)表示接收信号功率，P_T表示发射功率，PL(d₀)表示传播距离为d₀时的路径损耗， η为路径损耗指数，d为发送节点和接收节点间的距离。若监测区域内的未知节点接收到的 三个信标位置可组成正三角形，且未知节点位于正三角形内，则未知节点通过三边测量法 （trilateration）计算自身位置，如图2所示，若监测区域内未知节点(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)的距 离。

（4）当移动锚节点移动至监测区域边界处时，采用边界区域补偿方法保证边界未知节点 可接收到至少三个不共线的信标信息，即使移动锚节点以同样的速度沿圆形监测区域边界环 绕一周，并以同样的时间间隔广播信标信息。若未知节点位于接收到的三个信标位置组成 的三角形内，则以接收到的三个信标坐标的平均值作为未知节点的位置。如图3所示，若未 知节点(x′,y′)为边界未知节点，其接收到的三个信标信息的坐标分别为(x₁,y₁)，(x₂,y₂)和 (x₃,y₃)，且(x′,y′)位于三个信标位置构成的三角形内，则以接收到的三个信标坐标的平均 值作为未知节点的位置，即$x^{\prime }=\frac{x_1+x_2+x_3}{3},$$y^{\prime }=\frac{y_1+y_2+y_3}{2}.$

如图4所示，上述移动锚节点的通信半径R的具体设定方法为：假设监测区域半径为 R_network，取合适的移动锚节点通信半径R，使得R_network＝nR，n为正六边形的个数且为 正整数。

上述移动锚节点具有GPS定位装置，作为定位未知节点的信标节点，移动锚节点以R为 通信半径，向其周围的未知节点广播包含其位置信息和自身ID的信标信息数据包。

上述锚节移动点路径为正六边形，正六边形的边长以锚节点通信半径R递增，即各正 六边形分别内切于半径以R递增的同心圆，直至第n个正六边形路径内切于圆形监测区域。

上述每个正六边形都可以划分为若干个边长相等的正三角形，满足正三角形边长a等于 锚节点通信半径R，即a＝R＝vt。

如图5所示，移动锚节点的路径计算方法为：移动锚节点初始时位于监测区域中心 （x₀,y₀），以（x₀,y₀）为原点，建立直角坐标系，移动锚节点从（x₀,y₀）出发，以速度v移动 至之后沿着边长为R的正六边形路径移动，每隔时间t发送一次信标信息， 当移动锚节点再次到达点时，向点处移动，之后沿着边长为2R的 正六边形路径移动，每隔时间t发送一次信标信息，如此循环，使得每次正六边形路径的边 长增加R，直至第n个正六边形路径内切于圆形监测区域。

如图6所示，移动锚节点边界区域补偿方法具体为：当移动锚节点第二次到达点 时，移动锚节点以同样的速度沿圆形监测区域边界环绕一周，并以同样的时 间间隔广播信标信息。

本发明具有简单可靠、且定位精度高的优点，只用了一个移动锚节点就实现了对网络中 未知节点的定位，节约了网络成本，可扩展性强，具有广泛的应用价值。

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