基于移动锚点的三维无线传感网节点定位算法研究∗

王 群陈友荣∗陈 浩苏子漪刘半藤万锦昊

(1.浙江树人大学信息科技学院,浙江 杭州310015；2.常州大学计算机与人工智能学院,江苏 常州213164)

无线传感网(wireless sensor network,WSN)由在一个区域内均匀或随机部署的能量、容量和功能有限的大量微型低成本传感节点组成。其中,定位作为WSN不可或缺的一部分,可广泛应用于目标移动监测、核能监测、生物攻击监测等军事应用,森林火灾监测、洪水监测、精准农业等环境应用,家庭和办公室自动化,人体健康监测,医院内医生和患者跟踪等应用领域[1]。虽然均匀部署的传感节点能够较好的实现定位,但是随机部署的传感节点可能会造成网络的分裂,部分区域密集分布,部分区域稀疏分布甚至不存在,因此需要进行定位,从而获得每一个传感节点的准确位置坐标[2]。

目前,二维无线传感网(2D WSN)的定位算法研究成果较多,其在平坦的地形上定位精度较高[3]。但是在地上和水下的无线传感网较多应用中,需要考虑传感节点的三维坐标。2D WSN通信范围是圆形,而三维无线传感网(3D WSN)的通信范围为球形,且定位时需要4个以上的锚点位置坐标,这使3D WSN的传感节点定位问题面临新的挑战。

目前,3D WSN的定位算法可分成无距离定位算法和基于距离的定位算法。无距离定位算法可包括DV-hop(distance vector-hop)[4],质心等算法,但是该类算法只能粗略获知传感节点分布的位置,定位精度较低。而基于距离的定位算法,利用锚点提供的参考位置,计算传感节点的位置信息,其定位精度较高。其中,部分学者侧重于研究基于静态锚点的3D WSN节点定位算法,如文献[5]提出一种用于无线传感网三维定位的迭代估计算法。该算法计算三维空间的质心坐标和节点间的接收信号强度,利用已定位节点替代距离最远的锚点。文献[6]提出一种基于多通信半径和跳距加权的WSN三维迭代定位算法。该算法参考锚点数量设置跳数阈值,计算平均跳距的权值,采用最小最大法计算节点位置。文献[7]提出一种3D WSN的分布式无范围节点定位算法。该算法更新锚点的平均跳数,减少由共面的锚节点引起的位置误差,并采用辅助锚点,提高定位范围。文献[8]考虑3D通道模型,通过气压传感器和锚点,提出基于Gauss-Newton和两步最小二乘估计的室内定位估计算法,从而提高定位精度。文献[9]评估校正几何稀释度,提出三维无线传感网的到达角目标定位算法。但是在文献[5－9]的3D WSN中,锚点位置固定不变,且每一个传感节点的定位需要不共面的4个以上锚点,因此其定位算法需要较多的锚点,这较难应用到传感节点分布不均匀的随机部署3D WSN中。

因此,部分学者侧重于研究基于移动锚点的3D WSN节点定位算法,如文献[10]将定位过程分为位置估计,坐标转换,位置优化和位置校正四个主要步骤,提出用于3D移动定位的动态多维缩放算法。文献[11]提出基于移动信标的定位算法,即选择信标点集和合适锚点的最佳集合,并通过决策规则提高定位算法。但是文献[10－11]没有考虑移动锚点的移动路径。部分学者侧重于研究移动锚点的路径规划算法,如文献[12]比较随机选择网格中心的随机移动算法,让移动节点随机选择距离最近的未经过网格中心作为下一时刻的停留位置,提出贪婪移动路径选择算法(greedy moving path selection algorithm,GREED)。文献[13]利用节点的三维位置信息,提出一种移动节点的线性移动路径选择算法(Linear moving path selection algorithm for mobile nodes,LMPS),但是文献[12－13]只是考虑移动节点的移动路径选择,没有考虑传感节点的定位问题。

综上所述,目前基于静态锚点的3D WSN节点定位算法需要较多的锚点,基于移动锚点的3D WSN节点定位算法较少考虑移动锚点的3D移动路径。因此在上述文献的基础上,考虑3D环境下移动锚点的移动路径,提出一种基于移动锚点的三维无线传感网节点定位算法(node localization algorithm of 3D wireless sensor networks based on mobile anchor,NLA_3D)。在NLA_3D算法中,随机分布的传感节点通过无线通信,获知所有邻居传感节点的距离等连接信息,自组织成多个传感节点全连接的连接树。移动锚点在随机移动探测监测区域的过程中,如果发现未定位传感节点,则获知该传感节点所在连接树的所有传感节点连接信息,采用混合海洋掠食者算法,计算自身的最优移动路径,并在该移动路径的每一个停留位置上,提供四个不共面的锚点位置信息,帮助周围传感节点定位。传感节点接收锚点和已定位传感节点的参考位置信息,采用极大似然估计算法计算自身位置,并发送给移动锚点。NLA_3D算法可定位监测区域内所有传感节点,增加传感节点的平均锚点位置个数和降低平均节点定位误差。

1 算法原理

NLA_3D算法假设:在3D WSN中,存在随机部署且未知自身位置的静止传感节点和一个可移动的锚点。移动锚点能够通过GPS(global positioning system)和北斗等卫星定位模块获知自身的位置坐标。

如图1所示,传感节点随机分布在三维立体监测区域内且需要获知自身的位置,同时为降低系统成本和能耗,采用一个移动锚点辅助定位传感节点。但是NLA_3D算法仍需要解决以下二个问题:一是移动锚点如何为其通信范围内的传感节点提供锚点位置信息,传感节点如何利用移动锚点的位置信息和已定位传感节点位置信息,计算自身的位置坐标；二是移动锚点如何在三维立体监测区域内移动,从而为其通信范围内的传感节点提供不共面的4个以上锚点位置。这二个问题的具体解决如下。

图1 NLA_3D算法原理

1.1 传感节点的定位

假设网络中存在锚点定位传感节点,邻居定位传感节点和未定位传感节点三类传感节点。其中,锚点定位传感节点是根据锚点提供的4个以上参考位置信息,获知自身位置的传感节点。该传感节点的定位位置较准确。邻居定位传感节点是根据锚点和已定位传感节点的4个以上参考位置信息,获知自身位置的传感节点。由于邻居传感节点的位置信息存在一定的误差,因此邻居定位传感节点的定位位置误差较大。未定位传感节点是未知自身位置坐标的传感节点。如图2所示,当移动锚点移动到一个停留位置(xr,yr,zr)后,在每一个停留位置周围位置1(xr＋dmax/2,yr＋dmax/2,zr＋3dmax/4),位置2(xr＋3dmax/4,yr＋dmax/2,zr＋dmax/2),位置3(xr＋dmax/2,yr＋3dmax/4,zr＋dmax/2),位置4(xr＋dmax/2,yr＋dmax/2,zr＋dmax/4)四个位置上停留,发送自身的ID、位置坐标等信息,其中dmax表示节点最大通信半径。未定位传感节点接收到参考位置信息包后,首先读取其位置信息和链路通信的RSSI(received signal strength indication)值。接着采用Kalman滤波器降低信号噪声,并根据RSSI值计算当前传感节点到参考位置的距离。最后传感节点获知4个以上不共面参考位置坐标和到各个位置的距离,采用极大似然估计算法(maximum likelihood estimate,MLE)计算自身的位置坐标[14]。

图2 传感节点的定位示意图

1.2 移动锚点的移动路径规划

移动锚点将整个监测区域分成多个边长相同的小正方体网格。首先,移动锚点在未探测的小正方体网格间随机移动,当在其通信范围内发现存在传感节点时,则加入传感节点所在的连接树,获得该连接树中所有传感节点连接关系。移动锚点为了提供自身的参考位置给所有的传感节点,需要所有的传感节点出现在移动锚点停留的任一位置的单跳通信范围内。

图3 移动锚点的移动位置选择

令xj表示传感节点j,则两个传感节点的连接关系为

式中:L(xj)表示传感节点xj所在位置的父节点,link(xj,xk)表示传感节点xj和xk的连接关系。令Path表示移动锚点的移动路径,即为传感节点的位置集合{p1,p2,…,pi}。pi表示Path中第i个位置,即传感节点j的位置。令link(pi,pi＋1)表示位置pi和pi＋1的邻居关系指示符,当其为1,则表示位置pi＋1是位置pi上传感节点同一个父节点单跳通信范围内的其他传感节点位置或者其子节点位置。因此移动路径中的每一个位置元素需要满足邻居位置选择约束,即为

令C(xj)表示传感节点xj是否被覆盖的指示符。如果为1,则其至少在一个移动锚点的停留位置的单跳通信范围内。为保证移动锚点可提供有效的参考位置信息,提高传感节点的定位精度,要求所有传感节点必须在移动路径任一停留位置的单跳通信范围内,则单跳覆盖范围约束为

移动锚点的移动路径优化目标是最小化移动路径长度和定位误差,即

式中:Len(path)表示移动路径Path的长度,N1表示移动路径Path中元素的数量。D表示传感节点到移动锚点提供的参考位置的平均距离。当平均距离较近时,RSSI的误差较小,其定位精度较高。

由于采用最优化理论直接求解优化模型(4)的时间复杂度较高,无法适用于计算资源有限的移动锚点,因此采用启发式算法求解。而海洋捕食者算法(marine predators algorithm,MPA)作为最新的启发式算法,通过模拟布朗运动和莱维运动的方式来寻找最优解,比PSO(particle swarm optimization)等传统算法具有更好的寻优精度。但在上述模型中需要针对移动锚点的移动路径进行优化,若直接采用海洋捕食者算法,则难以执行布朗运动和莱维运动,计算运动步长。因此引入遗传算法的交叉和变异操作,提出一种混合海洋捕食者算法(hybrid marine predators algorithm,HMPA),将遗传算法的变异操作认为是布朗运动,增加移动路径的多样性,将遗传算法的交叉操作认为是莱维运动,逐渐靠近最优移动路径。

为了寻找到最优移动路径,HMPA算法首先从移动锚点发现的未定位传感节点开始,根据式(4)从未停留且已定位的传感节点中随机选择下一个停留位置,重复寻找停留位置直到初始化ξ条移动路径,并判断每条路径是否满足式(3)。如果不满足式(3),则执行移动路径的修正。将符合式(2)和式(3)的移动路径均作为猎物,并通过式(5)计算每个猎物的适应度,从中选择适应度最小的猎物作为掠食者。

式中:fi表示猎物i的适应度。由于猎物需要在迭代过程中进行不同阶段的切换,因此令和分别表示最大迭代次数的两个阈值,且,则每个猎物的具体更新如下:

①当迭代次数k≤ρyu1时,由于猎物与最优移动路径存在较大差距,因此需要考虑单跳通信范围内的节点数量与节点距离和,执行变异操作来更新猎物,从而增加移动路径的多样性。首先计算每个猎物中移动锚点停留位置数量,并对其每一个位置,执行如下变异操作:产生一个[0,1]范围内的随机数。若该随机数小于变异概率κ,则根据式(6)计算当前位置下一步中可选择移动位置的评价值。

式中:scorel表示下一步中第l个可选择移动位置的评价值,nl表示下一步中第l个可选择移动位置在单跳通信范围内的节点数量,el表示下一步中l个可选择移动位置到其单跳通信范围内的节点距离和,η1表示节点数量的权重参数,η2表示节点距离和的权重参数。根据式(7)计算选择概率,同时结合轮盘赌思想选择需要插入的移动位置。针对经过上述操作的猎物,保留与原来猎物相同位置数量的移动路径,最终获得新的猎物。

式中:Pl表示下一步中第l个可选择移动位置的选择概率,N2表示下一步中可选择移动位置数量。

同时,在每一次猎物初始化、交叉操作、变异操作等操作后,猎物有可能不满足约束条件(2)和(3)或存在重复的移动位置,因此需要执行以下修正策略:(a)如果猎物存在重复的移动位置,则在路径中寻找不是首次出现的移动位置,并删除该移动位置。(b)如果猎物无法满足式(3),则从中选择一个邻居节点数量最多的节点,通过最近邻插入算法将该节点加入到已获知该节点位置的路径后[14],直到满足式(3)。(c)如果猎物中下一跳传感节点不在当前移动锚点的未停留且已定位的传感节点中,则根据式(2)重新初始化1条移动路径进行替换,并判断每条路径是否满足式(3)。如果满足式(3),则完成该连接树中所有节点的覆盖和移动路径的修正,否则重新执行移动路径的修正,直到满足移动路径的约束。

在完成移动路径修正策略后,考虑到新产生的猎物可能会比原来的猎物要差,因此需要执行海洋记忆操作,即重新结合式(5)计算每个猎物的适应度,从而选择适应度最小的移动路径作为掠食者,并根据适应度从小到大的原则选择前ξ条猎物作为下一次迭代所需的猎物。为了避免陷入局部最优解,需要结合每个猎物的适应度,根据式(8)计算其确认值。对每个猎物,执行以下操作:产生一个[0,ξ]范围内的随机数,其中ξ表示范围阈值。若该随机数小于确认值,则根据式(2)重新初始化1条移动路径进行替换,否则保留该路径。

式中:τi表示猎物i的值,λ表示适应度的权重参数。

2 算法实现

NLA_3D算法是分布式算法,移动锚点和传感节点各自执行不同的步骤。其中,如图4所示,传感节点的具体实现步骤如下:

步骤1 网络启动后,初始化延时时间范围等参数。

步骤2 传感节点随机延时一段时间。在延迟时间内,如果接收到其他传感节点的连接树组建信息包,则加入到连接树,将自身ID加入到连接树组建信息包中,并广播发送更新的连接树组建信息包,同时将自身信息通过多跳路由发送给根节点,并接收根节点的所有传感节点的连接信息,跳到步骤4,否则跳到步骤3。

步骤3 没有接收到其他传感节点的连接树组建信息包,则以自身为根节点,发送包括自身ID等信息的连接树组建信息包,收集所有传感节点的ID、节点间距离等连接信息,并广播通知所有的传感节点。

步骤4 监听周围节点,接收这些节点提供的位置坐标,如果接收到的不共面参考位置坐标数量大于3个,则跳到步骤5,否则重新跳到步骤4,继续监听。

步骤5 采用极大似然估计算法计算自身的位置坐标,并广播通知移动锚点。

如图5所示,移动锚点的具体实现步骤如下:

图4 传感节点的工作流程图

步骤1 网络启动后,初始化最大迭代次数K和当前迭代次数k＝1等参数。将整个监测区域分成多个大小相同的小正方体网格。

步骤2 移动锚点从当前位置,随机探测未访问的周围小正方体网格,广播发送自身的信息,并将该网格标记为已探测。如果发现未定位的传感节点,则与该节点通信,获知该传感节点所在连接树中所有传感节点的连接信息,跳到步骤3,否则重新跳到步骤2,继续探测下一个未访问的周围小正方体网格。

步骤3 随机初始化移动路径。若移动路径不满足式(3),则执行修正策略。同时通过式(5)计算每个猎物的适应度,从中选择适应度最小的猎物作为掠食者；

步骤4 根据当前迭代次数,执行全部变异操作、一半变异一半交叉操作和全部交叉操作,更新每一个猎物。

步骤5 移动锚点执行移动路径的修正,并通过式(5)计算每个猎物的适应度,选择适应度最小的猎物作为掠食者。根据适应度从小到大的原则选择前ξ条猎物作为后续操作所需的猎物。

步骤6 移动锚点根据猎物的适应度计算其确认值,并根据其值随机选择猎物,重新初始化该猎物,从而避免陷入局部最优解。若当前迭代次数k小于最大迭代次数K,k＝k＋1,直接跳到步骤4,否则跳到步骤7。

步骤7 移动锚点沿着最优路径移动,获知当前位置周围的传感节点,提供4个不共面的参考位置,接收邻居传感节点的位置坐标。

步骤8 完成最优移动路径的移动,获知传感节点的位置坐标后,将传感节点所在的正方体网格标记为已探测,跳到步骤2。

图5 移动锚点的工作流程图

3 算法仿真

3.1 仿真参数和算法性能参数

在算法仿真中,选择以下参数进行仿真:三维监测区域为1000 m×1000 m×1000 m,正方体网格边长为200 m,节点最大通信距离半径为250 m,最大迭代次数为40,不同优化阶段切换阈值和为13和26,节点数量的权重参数η1为1,节点距离和的权重参数η2为0.5,变异概率κ为0.3,初始化移动路径数量ξ为25,适应度的权重参数λ为2。其中,平均节点定位误差定义为所有传感节点计算的自身位置坐标和真实坐标的误差平均值,可表示为:

式中:(xl,c,yl,c,zl,c)表示传感节点l通过算法计算所得的自身位置坐标,(xl,r,yl,r,zl,r)表示传感节点l的真实坐标,ο表示传感节点的总数。已定位传感节点个数比定义为能计算自身位置的传感节点个数与其总个数的比值,可表示为:

式中:ζ表示能计算自身位置的传感节点数量。传感节点的平均锚点位置个数定义为移动锚点沿着其移动路径提供参考位置时,所有传感节点可获知的锚点位置总个数和传感节点总个数的比值,可表示为:

式中:σ表示所有传感节点可获知的锚点位置总个数。

3.2 仿真结果分析

首先,选择3.1节中的参数,选择传感节点总数100,分析NLA_3D算法的收敛性。如图6所示,NLA_3D算法引入遗传算法的变异操作和交叉操作,改进海洋捕食者算法,在迭代过程中增加移动路径的多样性,并可快速趋向于最优移动路径,从而提高收敛效率,因此当迭代次数大于20时,NLA_3D能寻找到最优移动路径,其算法是收敛的。

其次,选择3.1节中的参数,选择传感节点个数100,分别计算NLA_3D、RAND[12]、GREED[12]、LMPS[13]算法中移动锚点的移动路径,获得如图7～图10所示的各个算法移动锚点的移动路径。其中,RAND算法的移动锚点选择正方体网格中心作为下一个停留位置,GREED算法的移动锚点从周围未经过的网格中心中随机选择距离最近的网格中心作为下一个停留位置,LMPS算法的移动锚点采用文献中的算法获得移动路径。

图6 NLA_3D算法的收敛图

图7 RAND算法锚点的移动路径

图8 GREED算法锚点的移动路径

图9 LMPS算法锚点的移动路径

图10 NLA_3D算法锚点的移动路径

如图7所示,RAND算法的移动锚点在网格中心间随机移动,其移动路径局限于右下区域,没有遍历整个监测区域。如图8所示,GREED算法的移动锚点只选择未经过的网格中心,整个移动路径经过监测区域,停留位置分布较分散,但是没有考虑传感节点的分布。如图9所示,LMPS算法的移动锚点按照线性移动的方式,从初始位置开始,沿着算法规定的路径移动,遍历经过移动路径上的所有网格中心。如图10所示,NLA_3D算法根据传感节点的连接信息,建立最小化移动路径长度和定位误差的优化模型,并采用混合海洋捕食者算法求解模型,获得最优移动路径。该移动路径经过整个监测区域,能出现在每一个传感节点周围,为其提供参考位置信息,让所有传感节点都能定位自身位置。

接着,选择3.1节中的参数,选择传感节点个数100,分析移动锚点的移动次数对未定位传感节点个数的影响。如图11所示,随着移动次数的增加,NLA_3D、RAND、GREED和LMPS算法的未定位传感节点个数都下降。但是NLA_3D算法在获知周围传感节点所在的连接树信息后,以移动路径长度和定位误差作为适应度值,并增加移动路径的多样性,逐渐靠近最优移动路径,从而获得最优移动路径。该移动路径有效覆盖所有的传感节点,导致其未定位传感节点个数下降最快,而RAND算法具有随机性,LMPS算法按照固定轨迹移动,GREED算法没有考虑传感节点分布,因此当移动次数大于10次时,NLA_3D的未定位传感节点个数都小于RAND、GREED和LMPS算法,且其最终趋向于0。

图11 各算法的未定位传感节点个数

最后,选择3.1节中的参数,传感节点80,100,120,140,160,180,200,随机分布在三维监测区域内,随机产生同一传感节点数量下的10个拓扑结构,分别计算NLA_3D、RAND、GREED、LMPS算法的已定位传感节点个数比、传感节点的平均锚点位置个数和平均节点定位误差,并取其平均值作为仿真结果值。RAND算法、GREED算法和LMPS算法选择与NLA_3D算法相同的传感节点定位方法。

如图12所示,不管传感节点个数如何变化,NLA_3D算法的已定位传感节点个数比为100%,远高于RAND算法、GREED算法和LMPS算法的已定位传感节点个数比。这是因为:NLA_3D算法的移动锚点获知周围存在未定位传感节点时,可直接获知该传感节点所在的连接树中各个传感节点的连接关系,并采用混合海洋捕食者算法计算移动锚点的最优路径。该路径可以让移动锚点移动到每一个传感节点的周围,提供参考位置坐标,从而辅助所有的传感节点计算自身的位置。RAND算法的移动锚点路径具有随机性,定位效果较差。GREED算法虽然让移动锚点探测未经过的区域,但是没有考虑传感节点的分布,具有一定的盲目性。LMPS算法按照固定的轨迹移动,在有限的移动距离情况下,其定位到的传感节点较少。

图12 各算法的已定位传感节点个数比

如图13所示,NLA_3D算法的平均锚点位置个数最多,高于RAND算法、GREED算法和LMPS算法的平均锚点位置个数。这是因为:NLA_3D算法根据未定位传感节点的连接关系,尽量让其移动锚点停留位置在每一个传感节点的周围,在有限移动距离下可覆盖更多的传感节点,而其他算法移动路径往往只经过一部分监测区域或者虽然路径经过整个区域,但是其停留位置分布不合理。

图13 各算法的传感节点的平均锚点位置个数

如图14所示,NLA_3D算法的平均节点定位误差最低,小于RAND算法、GREED算法和LMPS算法的平均节点定位误差。这是因为:在NLA_3D算法中,移动锚点在探测监测区域中,获知未定位传感节点的连接信息后,将传感节点到移动锚点停留位置的平均距离作为混合海洋捕食者算法的优化目标之一,在其最优移动路径寻找中尽量能出现在每一个未定位传感节点的附近,提供自身较精确的参考位置信息,帮助未定位传感节点计算自身的位置。RAND算法、GREED算法和LMPS算法都没有考虑未定位传感节点的分布情况,且其传感节点的平均锚点位置个数较少。

图14 各算法的平均节点定位误差

4 总结

本文提出一种基于移动锚点的三维无线传感网节点定位算法。首先,提出传感节点的定位算法,即根据移动锚点或已定位传感节点位置,采用极大似然估计算法计算自身位置坐标。其次,根据传感节点间的无线通信,提出自组织的连接树划分算法,并考虑移动锚点的移动路径选择,建立最小化移动路径长度和定位误差的优化模型,并引入遗传算法思想,提出一种混合海洋捕食者算法(HMPA)求解优化模型,获得移动锚点的最优移动路径。最后给出算法的仿真参数和性能参数,比较NLA_3D、RAND、GREED和LMPS算法的性能。

总之,NLA_3D算法是一种分布式算法,可获得适合当前传感节点连接关系的移动路径,从而增加传感节点的平均锚点位置个数,增加已定位传感节点个数比,降低平均节点定位误差。但是NLA_3D算法没有考虑移动锚点的停留位置选择对传感节点定位的影响,因此下一阶段目标是考虑RSSI距离计算误差,寻找一种移动锚点自身位置坐标提供方法,降低传感节点的定位误差。