基于锚节点移动路径动态规划的定位算法

王 鑫，田 艺，蒋 华，覃 琴

(1. 桂林电子科技大学 计算机与信息安全学院，广西 桂林 541004；2. 桂林电子科技大学 海洋信息工程学院，广西 北海 536000)

0 引 言

水下无线传感器网络的定位技术在水下无线传感器网络(UWSN)中扮演着至关重要的角色[1,2]，只有当传感器节点位置已知时，传感器节点采集的数据才具有意义[3]。网络中的节点被随机部署在水下，部署的传感器节点在水中形成三维体系结构，节点在水下的随机部署给水下无线传感器网络定位带来了很多挑战[4]。

水下无线传感器网络中节点随机部署导致传感器节点稀疏和锚节点分布不均匀[5]。水的流动性会造成UASN结构的非均匀，常鲁杰等[6]提出了基于迭代粒子群优化的RQ-PSO定位算法，利用MDS-MAP算法[7]进行定位，提出的PQ-PSO算法减少了定位误差，使得算法更具有鲁棒性。针对锚节点随机分布导致传感器网络定位率低、定位误差大的问题，黄炎等[8]提出基于锚节点连通度的无线传感器网络定位算法，引入平均锚节点连通度的概念，根据节点实时分布来划分网络，实时控制移动锚节点分布，提高了定位算法的精度。陈友荣等[9]将网络划分成多个六边形，提出一种辅助信标节点的路径规划算法，分析对比了SCAN算法、CIRCLES算法等移动路径静态规划算法，降低了定位时间和平均定位误差。汪晗等[10]提出基于几何精度因子的静态锚节点优化布设方法，但定位精度受到锚节点几何面积的大小的约束。黄冰倩等[11]提出宽度优先搜索(BFS)算法选取虚拟锚节点，减少了虚拟锚节点数量和锚节点移动路径长度。程向红等[12]提出运用栅格法对已知地图进行建模，在算法中引入向量指导路径方向，通过多次奖励与惩罚措施来进行路径规划。这些算法均在某一方面减少了锚节点数量和移动路径长度，但缺乏对网络整体定位率和定位精度的考虑。

针对已有的基于移动锚节点的定位算法，提出基于锚节点移动路径动态规划的水下无线传感器网络定位算法(underwater wireless sensor network localization algorithm based on dynamic planning of anchor node moving path，BMAP)。采用节点信息列表，通过锚节点与普通节点之间的双向互动，保存采集到的网络中节点的信息。利用路径动态规划，解决锚节点的移动路径规划问题。通过RSSI测距算法和三边定位算法，实现了网络中普通节点的定位，仿真结果表明，BMAP算法有较好的节点定位率和较低的平均定位误差，并降低了定位能耗。

1 水下无线传感器网络模型

由于水下的特殊环境，水下无线传感器网络具有三维结构，以水平面为XOY平面向下建立一个三维坐标系，如图1所示。传感器节点随机分布在水中，水下的传感器节点受到环境的限制，它们无法远程充电，普通传感器节点的能源主要因为通信和计算而耗尽。在监控区域中布置适量数目的锚节点和普通的传感器节点，锚节点用于辅助定位和网络数据采集，传感器节点用于采集水下相关数据。

图1 水下无线传感器网络三维模型

如图2所示将水下无线传感器网络三维空间定位转换成二维平面定位。假设每个传感器节点都可以通过自身携带的压力传感器获得自身的深度信息，当未定位的传感器节点接收到水下锚节点广播的信息后，通过RSSI测距算法计算出自身与锚节点的距离L，结合自身的深度数据h，将未定位节点与锚节点投影在同一二维平面，可计算出该节点与锚节点的平面投影距离d。

图2 三维空间转换二维平面

第i个节点投影后与锚节点的距离为

(1)

式中：Li为第i个节点与锚节点的实际距离，hi为第i个节点的深度值。在图2中，传感器节点A和传感器节点B通过已知的数据L1、L2和h1、h2利用式(1)计算出节点A的投影与锚节点投影的距离d1、节点B与锚节点投影的距离d2。

2 锚节点移动路径动态规划算法

路径规划方法应用在众多领域，可以拓扑化为点、线的问题基本都可以采用路径规划的方法解决。基于对信息的动态或静态获取可以把路径规划分为静态规划和动态规划。该文采用动态规划方法，实时获取普通节点的动态信息，生成必经虚拟锚节点集合，通过蚁群算法求出最短路径。

2.1 必经虚拟锚节点的选取

2.1.1 基于广度优先搜索算法选取

根据虚拟锚节点到未定位节点之间的距离L判断未定位节点的类型。先行锚节点随机选取一个未定位的节点进行访问，在移动的过程中广播信息，并判断未定位节点的类型。算法核心流程如下：

步骤1 当L

步骤4 在锚节点遍历网络的过程中，当未定位节点接收到3个或者3个以上的广播信息，若该节点在集合Vinter中，则通过三边定位算法定位，并将该节点加入已定位节点集合Vd。

步骤5 先行锚节点遍历完整个网络之后，从集合Vneig中删除集合Vd中出现的节点ID。

步骤6 输出最终的集合Vneig，即为必经虚拟锚节点集合。

2.1.2 BMAP算法选取

通过两个阶段来规划移动锚节点在网络中的移动路线。第一阶段为锚节点移动遍历网络发布信息、采集信息阶段。如图3所示，圆形代表虚拟锚节点，三角形代表未定位的节点，未定位节点随机分布，将水下无线传感器网络以步长Lr为单位划分成栅格形状。

图3 先行锚节点移动轨迹

水下无线传感器网络中的每一个节点都拥有一个信息列表Ginfor，先行锚节点信息列表包含发布信息时所在的虚拟锚节点ID号，标识符S(发送信息为0，接收信息为1)，深度值，接收到的未定位节点返回的信息。未定位节点信息列表包括节点自身的ID，深度值，接收到的信号强度以及发送信息的虚拟锚节点ID，标识符。

水下无线传感器网络中有两个移动锚节点，第一个锚节点负责发布信息，第二个锚节点负责采集信息与辅助定位。

步骤1 第一个锚节点沿着图3中虚线从下至上，从左至右移动遍历网络，当锚节点运动到虚拟锚节点的位置时广播一次信息。第二个锚节点在t时刻之后开始沿着同一路线移动。

步骤2 未定位节点接收到信息后，将接收到的虚拟锚节点ID号和与其对应的信号强度Sinten保存到Ginfor，ID与Sinten属于一对一关系。

步骤3 当未定位节点不能再接收到第一个锚节点广播的消息时，Ginfor只保留Sinten最大的3个信号对应的ID，将自身的信息列表Ginfor发送给到达其通信范围内的第二个锚节点。

步骤4 第二个锚节点将接收到的信息保存到自身的信息列表Ginfor，将其中的虚拟锚节点ID保存到必经虚拟锚节点集合Vindis。

如图4所示，网络中每一个虚线栅格的顶点即为虚拟锚节点的位置，栅格的长度为Lr，锚节点的通信半径为R，Q1和Q2为位置未知的节点。

图4 必经虚拟锚节点

执行步骤1，先行锚节点M移动到虚拟锚节点的位置时，信号范围如图中的圆圈所示，执行步骤2。未知节点Qi执行步骤3，未知节点Q1接收到先行锚节点从A、B、C、D这4个虚拟锚节点广播的信息，保存信号强度最强的A、B、D这3点的ID，未知节点Q2接收到从C、E、F、G广播的信息，保存C、E、F这3点的ID。执行步骤4，完成第一阶段的必经虚拟锚节点选择，产生必经虚拟锚节点集合Vindis。

2.2 基于锚节点移动路径动态规划的定位算法

锚节点移动路径规划问题是一个旅行商问题[13](trave-lling salesman problem，TSP)，必经虚拟锚节点集合Vindis等价于旅行家必须经过的旅游景点集合，移动锚节点等价于旅行家，移动锚节点经过每一个必经虚拟锚节点等价于旅行家经过每一个旅游景点。设计移动路线使得移动锚节点经过所有的必经虚拟锚节点，并且移动路径最短。

目前，学者们提出遗传算法、蚁群算法、禁忌搜索算法、模拟退火算法等众多启发式优化搜索算法解决TSP问题。蚁群算法是模拟蚂蚁觅食的方式，通过蚂蚁觅食时在路径上释放的信息素来选择下一条路径。

已得必经虚拟锚节点集合Vindis，将必经虚拟锚节点存放在数组A和B中，其中aij=bij

A=aij(i=1,2,3,…,j=1,2)

(2)

B=bij(i=1,2,3,…,j=1,2)

(3)

必经虚拟锚节点a到必经虚拟锚节点b的距离

(4)

通过式(4)得到必经虚拟锚节点的加权矩阵Di,j

(5)

设定整个蚁群中有m只蚂蚁，有n个城市，各个城市之间的距离为Di,j(i,j=1,2,3…n)。

(6)

式(6)中的ηij(t)是启发函数，β是启发函数重要程度因子，α是信息素重要程度因子，allowk是蚂蚁K可以选择的城市集合，τij(t)是城市i和城市j之间的路径上t时刻的信息素浓度

allowk={0,1,…,n-1-tabk

(7)

当所有蚂蚁完成一次循环后按式(8)更新信息素

(8)

本文定位算法步骤如图5所示。

图5 BMAP算法流程

3 实验仿真

3.1 实验设置

实验仿真选择在Windows 10 PC机上通过MATLAB工具模拟海洋环境下的无线传感器网络，实现基于锚节点移动路径动态规划的水下无线传感器网络定位方法，对本文的BMAP算法与基于BFS算法的定位算法、SCAN算法和锚节点随机的RSSI定位算法从虚拟锚节点数量、锚节点移动路径长度、定位覆盖率和平均定位误差4个方面进行比较。

表1 实验参数设置

水下无线传感器网络中节点定位率的计算方式如式(9)所示

(9)

其中，Plocation是节点定位率，Nlocnode是水下无线传感器网络中能够被定位的节点总数，N是水下无线传感器网络中节点的总数。

3.2 实验结果和分析

在仿真区域为90 m×90 m的正方形区域，随机布置传感器节点50个，传感器节点随机分布在监控区域之中，传感器节点的分布及锚节点移动路径如图6所示。SCAN算法中锚节点按照从下至上、从左至右沿着箭头所示路径移动。BFS算法根据广度优先搜索算法选取虚拟锚节点，锚节点沿着规划的路径移动。锚节点随机算法随机部署锚节点。BMAP算法中锚节点沿着动态规划的路径移动。

图6 传感器节点分布

图7为SCAN算法、BFS算法和BMAP算法3个基于锚节点移动路径规划的定位算法的虚拟锚节点个数与网络区域边长关系对比图。通过改变网络区域边长来改变水下传感器节点的稀疏程度，区域边长越大，网络中节点越稀疏。在传感器节点稀疏的水下无线传感器网络中，BMAP算法选取的虚拟锚节点数量少于SCAN算法,略大于BFS算法，BMAP算法减少了虚拟锚节点数量，从而降低了节点之间的通信能耗。

图7 虚拟锚节点个数

图8为SCAN算法、BFS算法和BMAP算法3个基于锚节点移动路径规划的定位算法的锚节点移动路径长度与网络区域边长关系对比。在传感器节点稀疏的水下无线传感器网络中，BMAP算法的虚拟锚节点移动路径长度远小于SCAN算法，略大于BFS算法的虚拟锚节点移动路径长度。BMAP算法降低了锚节点移动能耗、减少了网络定位时间。

图8 锚节点移动路径长度

图9为SCAN算法、BFS算法和BMAP算法3个基于锚节点移动路径规划的定位算法和锚节点随机的RSSI定位算法的节点定位率与网络区域边长关系对比图。在传感器节点稀疏的水下无线传感器网络中，BMAP算法的节点定位率最高，且节点定位率稳定，优于其它3种定位算法。BFS算法在网络区域边长为90 m和120 m时定位率优于其它3种算法，但当网络区域边长增加时，定位率急剧下降到最低。

图9 节点定位率

图10为SCAN算法、BFS算法和BMAP算法3种基于锚节点移动路径规划的定位算法和锚节点随机的RSSI定位算法的平均定位误差与网络区域边长关系对比图。BMAP算法平均定位误差略高于SCAN算法，但远低于BFS算法和锚节点随机的RSSI算法。BMAP算法的平均定位误差随着网络区域边长的增加能够稳定在1 m以内。BFS算法和锚节点随机的RSSI算法的平均定位误差随着网络区域边长的增加在不断地增大。在网络区域边长为210 m时，BFS算法和锚节点随机的RSSI算法的平均定位误差是BMAP算法的7倍，BMAP算法具有较高的定位精度。

图10 定位误差

在传感器节点稀疏的水下无线传感器网络中，BMAP算法选取的虚拟锚节点个数和锚节点移动路径长度小于SCAN算法，节点定位率高于BFS算法和锚节点随机的RSSI算法，平均定位误差远低于BFS算法和锚节点随机的RSSI算法。因此，BMAP算法整体具有较好的定位性能。

4 结束语

针对水下无线传感器网络节点稀疏、随机部署锚节点导致定位误差大、网络定位率低的问题。提出一种基于锚节点移动路径动态规划的水下无线传感器网络定位算法。采用动态路径规划，通过双移动锚节点选择必经虚拟锚节点，利用蚁群算法规划锚节点移动的最短路径，结合RSSI测距算法和三边定位算法完成节点定位。对BMAP算法、BFS算法、SCAN算法和锚节点随机的RSSI算法进行定位性能对比，结果表明BMAP算法整体具有较低的能耗、较高的定位率和定位精度。