基于网络密度分簇的无线传感器网络多移动信标组移动路径规划方法

技术领域

本发明属于无线传感器网络领域，尤其涉及一种基于网络密度分簇的无线传感器网络多 移动信标组移动路径规划方法。

背景技术

近年来，随着无线通信和数字电子技术的发展，无线传感器网络(Wireless Sensor  Networks,WSNs)由于其高度的学科交叉性和广泛的应用前景而受到世界各国政府部门、工 业界、学术界和科研机构的极大关注，对它的研究已成为当前IT领域最具挑战性的课题之 一，其应用场景包括环境监测、生物医疗、工业自动化控制、智能家居等诸多领域。位置信 息对WSNs的应用具有至关重要的意义，有效而可靠的定位技术及其优化方法是WSNs技 术走向实际应用必须攻克的关键支撑技术。WSNs的定位算法主要分为两大类：基于信标和 非基于信标的定位算法，信标就是可以预先获取自身位置的节点，基于信标的定位算法用信 标定位未知节点，而非基于信标的定位算法主要计算节点间的相对位置。为了提高定位精度、 节约网络成本，比较实用的定位方法是利用一些移动信标，按照有效的规划路径移动，通过 发送包含自身坐标的信息来定位其他节点。移动信标路径规划问题可分为两类：静态路径规 划和动态路径规划。静态移动信标路径规划是指：移动信标按照预先规划好的路径在网络中 移动，不需要根据未知节点的分布密度来随时调整移动路径。动态路径规划是指移动信标根 据网络中节点的分布情况和移动信标当前位置来确定移动信标下一个移动位置。

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

1.Dimitrios Koutsonikolas等在2007年的《Computer Communication》上发表的文章“Path  planning of mobile landmarks for localization in wireless sensor networks”中提出三种信标移动 方法：Scan，Double Scan和Hilbert，并比较了这三种规划路径的性能。三种方法中Scan的 移动路径最短，移动信标沿着y轴方向移动，但其直线型的移动路径会造成未知节点接收到 若干个共线的移动信标信标信号，尤其当信标的通信半径过小，导致许多未知节点无法定位。 考虑到SCAN方法中存在共线问题，DOUBIE SCAN中增加一条x轴方向的路径，这种路径 规划方法解决了信标信息共线问题，但增加了移动信标的移动路径长度，导致了网络能耗增 加。HILBERT由若干个不完全封闭的小正方形组成，路径增加多个转弯以接收更多非共性 信标的信息，提高定位率，同时移动路径长度小于Double Scan。

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

3.Hongjun Li等在2009年的《Journal of Computer Research and Development》上发表 的文章“Path Planning for Mobile Anchor Node in Localization for Wireless Sensor Networks”中 提出了宽度优先算法和回溯式贪婪算法，将图论引入到无线传感器网络节点定位中，把无线 传感器网络看成一个联通的节点无向图，路径规划问题转化为图的生成树及遍历问题。使用 这种路径规划方法，移动信标可以根据接收到的网络信息自适应调节移动路径。动态路径规 划产生的路径不是规则的图形，它利用未知节点分布信息动态调整移动信标移动路径，并且 移动路径较短，从而克服了静态路径规划的不足之处。

4.Huangqing Cui等在2011年的“The 2nd International Conference on Software  Engineering and Service Science”上发表的“Three-mobile-beacon assisted weighted centroid  localization method in wireless sensor networks”令三个移动信标以组移动的方式遍历整个网 络，解决了单个移动信标在定位过程会出现信标位置共线的问题。三个移动信标构成三角形 (最理想情况为等边三角形)，在移动过程中，三个信标之间保持最初的距离同时移动。定 位过程分成三个阶段：首先三个信标共同穿越整个区域并周期性的广播信标数据包；然后未 知节点记录接收到的信标数据包来估算自己的位置；最后剩余未被定位的节点向邻居节点发 出请求，利用邻居节点反馈的位置信息估算自身的位置。

5.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移动模型及加权质心定位算法的网络性能最优。但是这样 密集的网络遍历并不适用于稀疏部署的网络。

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

(1)现有的大部分研究主要停留在静态移动信标路径规划上，这种路径规划方式存在 信标位置共线，信标移动路径和网络定位时间较长等问题。

(2)大多数路径规划方法均假设网络均匀部署，当网络非均匀部署时，若令移动信标 按静态移动信标路径规划方法遍历整个网络，不但会导致信标移动路径和网络定位时间过 长，而且在很大程度上降低了信标的利用率。

(3)大多数路径规划方法仅使用单个移动信标，虽然节约了网络成本，但是增加了整 个网络的定位时间，在实际应用中受到限制。

发明内容

本发明的目的是提供一种适用于非均匀部署的无线传感器网络多移动信标辅助定位方 法，避免移动信标移动至部分没有部署节点的区域广播信标数据包而导致的移动路径长和通 信开销大的问题，该定位方法定位精度高，信标移动路径短，通信开销小，信标利用率高。

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

一种基于网络密度分簇的无线传感器网络多移动信标组移动路径规划方法，其步骤包 括：

(1)基于DBSCAN的网络分簇，选取核心密度最大的点作为簇头，保证簇头位于簇 内密度最大处；

(2)簇头位置估计；

(3)移动信标全局路径规划；

(4)移动信标局部路径规划；

(5)移动信标按规划路径以恒定速度v移动，在遍历每个簇时，每隔时间间隔t，以 此刻所在位置为圆心，R为通信半径，广播信标数据包，信标数据包包括该时刻移动信标 的位置和信标ID；

(6)未知节点不断监听、接收信标数据包，若收到的三个信标位置可构成正三角形， 且未知节点位于该正三角形内，则未知节点通过三边测量法计算自身位置；

(7)已定位节点升级为静态信标辅助剩余未知节点定位，若剩余未知节点可以获得至 少三个不共线的信标位置信息，则未知节点通过三边测量法计算自身位置，该过程一直持续 到所有节点完成定位或达到规定迭代次数为止。

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

上述步骤(1)中基于DBSCAN的网络分簇采用基于核心密度的簇头选取机制，从簇 头出发，将簇头n-跳(n≥1)范围内的节点组成一个簇；节点i的n-跳范围内核心密度计算方 法：

${\mathrm{CoreDensity}}_{i,n}=\frac{{\mathrm{NeighborNum}}_{i,n}}{{\mathrm{Dis}\tan \mathrm{ceAve}}_{i,n}},$

其中，${\mathrm{NeighborNum}}_{i,n}=\underset{k=1}{\overset{n}{\Sigma }}{\mathrm{NeighborNum}}_{i\_k},$NeighborNum_{i_k}表示节点i的k-跳节点个数， 因此NeighborNum_i,n表示节点i的n-跳范围内的节点总数；

${\mathrm{Dis}\tan \mathrm{ceAve}}_{i,n}=\left(\begin{array}{cc}\frac{\underset{j=1}{\overset{{\mathrm{NeighborNum}}_{i,n}}{\Sigma }}\mathrm{Dist}(i,{\mathrm{Neighbor}}_{i,n}\left(j\right))}{\underset{k=1}{\overset{n}{\Sigma }}k·{\mathrm{NeighborNum}}_{i\_k}}& {\mathrm{NeighborNum}}_{i,n}\ge \mathrm{NeighborThr}\\ R& {\mathrm{NeighborNum}}_{i,n}<\mathrm{NeighborThr}\end{array}\right)$

其中，Neighbor_i,n(j)表示节点in-跳范围内节点的有序集合，由近到远排列。 Dist(i,Neighbor_i,n(j))表示节点i到其n-跳范围内第j个节点的欧式距离；NeighborThr 代表网络连通度阈值；NeighborNum_{i_k}表示节点i的k-跳节点个数；因此DistanceAve_i,n表 示节点i到其n-跳范围节点的平均1-跳距离。

上述步骤(2)中簇头位置估计采用MDS-MAP(p)算法计算出簇头所在位置。

上述步骤(3)中移动信标全局路径规划采用蚁群算法计算出遍历簇头的先后顺序，三 个移动信标位于边长为R的正三角形的顶点处，并保持相对位置不变，以恒定速度v移动， 按先后顺序依次遍历所有簇头。

上述的三个移动信标之间的关系形式的确定方法为：

三个移动信标在全局路径规划时，在物理关系和逻辑关系上都是一个整体，在物理关系 上，三个移动信标始终呈边长为R正三角形并保持相对位置不变，在逻辑关系上，三个移 动信标是可以对称轮换的，即三个移动信标之间是平等关系。

上述的平等关系是指三个移动信标在构成的正三角形中地位是相同的，且都具有GPS 定位装置，它们的位置信息都通过GPS获取，任一移动信标在正三角形的任一顶点都是等 效的。

上述三个移动信标构成的正三角形以簇头所在位置为中心，三个移动信标分别按边长 a＝R的正六边形路径，且a＝vt。

上述三个移动信标按正六边形路径移动后，移动信标的位置相较于移动前发生了改变， 但三个移动信标的相对位置及所构成的正三角形的边长并未发生改变，即移动后三个移动信 标的位置发生了对称轮换。

上述步骤(7)中已定位节点升级为静态信标辅助剩余未知节点定位可分为以下两个阶 段：

未被定位的未知节点向邻居节点发出定位请求信息，并利用静态信标反馈的位置信息计 算自身位置；

该过程一直持续到所有节点完成定位或未知节点发送的定位请求信息达到规定的次数 为止。

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

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

(2)对网络中节点分布情况没有限制，无论网络是均匀部署还是非均匀部署，都能够通 过网络分簇、全局路径规划及局部路径规划算法动态确定信标移动路径，提高信标利用率；

(3)本发明使用三个移动信标进行组移动，在移动信标从一个簇头移动至下一个簇头的 过程中仍可以定位移动路径上的未知节点，提高了网络定位率，减少了网络定位时间。

附图说明

图1为本发明基于网络密度分簇的无线传感器网络移动信标路径规划方法的流程图；

图2为基于DBSCAN的网络分簇图(n＝2)；

图3为信标移动路径和广播信标数据包位置的示意图；

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

图5为未知节点接收到的三个不共线信标位置示意图。

具体实施方式

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

如图1所示，一种基于网络密度分簇的无线传感器网络多移动信标组移动路径规划方法，其步骤包括：

(1)基于DBSCAN的网络分簇，选取核心密度最大的点作为簇头，保证簇头位于簇 内密度最大处；

(2)簇头位置估计；

(3)移动信标全局路径规划；

(4)移动信标局部路径规划；

(5)移动信标按规划路径以恒定速度v移动，在遍历每个簇时，每隔时间间隔t，以 此刻所在位置为圆心，R为通信半径，广播信标数据包，信标数据包包括该时刻移动信标 的位置和信标ID；

(6)未知节点不断监听、接收信标数据包，若收到的三个信标位置可构成正三角形， 且未知节点位于该正三角形内，则未知节点通过三边测量法计算自身位置；

(7)已定位节点升级为静态信标辅助剩余未知节点定位，若剩余未知节点可以获得至 少三个不共线的信标位置信息，则未知节点通过三边测量法计算自身位置，该过程一直持续 到所有节点完成定位或达到规定迭代次数为止。

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

上述步骤(1)中基于DBSCAN的网络分簇采用基于核心密度的簇头选取机制，从簇 头出发，将簇头n-跳(n≥1)范围内的节点组成一个簇；节点i的n-跳范围内核心密度计算方 法：

${\mathrm{CoreDensity}}_{i,n}=\frac{{\mathrm{NeighborNum}}_{i,n}}{{\mathrm{Dis}\tan \mathrm{ceAve}}_{i,n}},$

其中，${\mathrm{NeighborNum}}_{i,n}=\underset{k=1}{\overset{n}{\Sigma }}{\mathrm{NeighborNum}}_{i\_k},$NeighborNum_{i_k}表示节点i的k-跳节点个数， 因此NeighborNum_i,n表示节点i的n-跳范围内的节点总数；

${\mathrm{Dis}\tan \mathrm{ceAve}}_{i,n}=\left(\begin{array}{cc}\frac{\underset{j=1}{\overset{{\mathrm{NeighborNum}}_{i,n}}{\Sigma }}\mathrm{Dist}(i,{\mathrm{Neighbor}}_{i,n}\left(j\right))}{\underset{k=1}{\overset{n}{\Sigma }}k·{\mathrm{NeighborNum}}_{i\_k}}& {\mathrm{NeighborNum}}_{i,n}\ge \mathrm{NeighborThr}\\ R& {\mathrm{NeighborNum}}_{i,n}<\mathrm{NeighborThr}\end{array}\right)$

其中，Neighbor_i,n(j)表示节点in-跳范围内节点的有序集合，由近到远排列。 Dist(i,Neighbor_i,n(j))表示节点i到其n-跳范围内第j个节点的欧式距离；NeighborThr 代表网络连通度阈值；NeighborNum_{i_k}表示节点i的k-跳节点个数；因此DistanceAve_i,n表 示节点i到其n-跳范围节点的平均1-跳距离。

上述步骤(2)中簇头位置估计采用MDS-MAP(p)算法计算出簇头所在位置。

上述步骤(3)中移动信标全局路径规划采用蚁群算法计算出遍历簇头的先后顺序，三 个移动信标位于边长为R的正三角形的顶点处，并保持相对位置不变，以恒定速度v移动， 按先后顺序依次遍历所有簇头。

上述的三个移动信标之间的关系形式的确定方法为：

三个移动信标在全局路径规划时，在物理关系和逻辑关系上都是一个整体，在物理关系 上，三个移动信标始终呈边长为R正三角形并保持相对位置不变，在逻辑关系上，三个移 动信标是可以对称轮换的，即三个移动信标之间是平等关系。

上述的平等关系是指三个移动信标在构成的正三角形中地位是相同的，且都具有GPS 定位装置，它们的位置信息都通过GPS获取，任一移动信标在正三角形的任一顶点都是等 效的。

上述三个移动信标构成的正三角形以簇头所在位置为中心，三个移动信标分别按边长 a＝R的正六边形路径，且a＝vt。

上述三个移动信标按正六边形路径移动后，移动信标的位置相较于移动前发生了改变， 但三个移动信标的相对位置及所构成的正三角形的边长并未发生改变，即移动后三个移动信 标的位置发生了对称轮换。

上述步骤(7)中已定位节点升级为静态信标辅助剩余未知节点定位可分为以下两个阶 段：

未被定位的未知节点向邻居节点发出定位请求信息，并利用静态信标反馈的位置信息计 算自身位置；

该过程一直持续到所有节点完成定位或未知节点发送的定位请求信息达到规定的次数 为止。

实施例：

n＝2，即簇内跳数为2时，网络成簇结果如图2所示。确定簇头所在位置后，移动信 标进行全局路径规划确定遍历簇头的先后顺序，三个移动信标位于长为R的正三角形的顶 点处，并保持相对位置不变，以恒定速度v移动，按先后顺序依次遍历所有簇头，如图3 所示。

在局部路径规划过程中，三个移动信标以簇头所在位置为正三角形中心，分别沿着边长 a＝R的正六边形路径，且a＝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)计算自身位置。如图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所示，若未知节点(x′,y′)接收到的信标数据包中任意三个信标位置不能构成正 三角形，则未知节点从接收到的信标数据包中随机选择三个信标位置(x₁,y₁)，(x₂,y₂)和 (x₃,y₃)用三边测量法计算自身位置。

本发明具有简单可靠、定位精度高的优点，且适用于非均匀部署的无线传感器网络，使 用三个移动信标组移动实现对网络中的未知节点定位，减少了网络定位时间，提高了信标利 用率，可扩展性强，具有广泛的应用价值。

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