水下机器人协同控制的TO模型区域划分定位

陈嘉兴,董怡靖,赵晓旭,刘志华 ,刘 扬

(1.河北师范大学中燃工学院,河北石家庄 050024;2.河北正定师范高等专科学校,河北石家庄 050800;3.河北师范大学计算机与网络空间安全学院,河北石家庄 050024)

1 引言

水声传感器网络(underwater acoustic sensor networks,UASNs)的广泛应用为物联网在海洋领域的发展提供了契机,其中定位系统是UASNs最典型的应用之一,是辅助国防海域建设以及海洋资源开发利用的重要技术手段.自主水下机器人(autonomous underwater vehicles,AUVs)是一种可充电和自主操作的移动水下设备,其应用可涵盖海洋勘探、水下遗迹考古[1-2]等,非常适合协助UASNs执行数据收集和水下定位等任务[3].

由于洋流等原因,UASNs较易形成局部稀疏型网络环境,AUV定位机制采用静态或动态路径规划技术,在稀疏型网络结构中也可以有效定位目标节点.单个AUV需要对目标区域进行多次扫描从而存在耗费大量时间和精力的问题,因此,多AUV协同控制受到了更多学者的关注[4-6].如朱大奇等人[7]针对AUV动态任务分配,引入栅格信度函数概念,控制一组AUV有效到达所有指定位置.LI Y等人[8]提出基于间歇信念传播的航迹推算作为协同定位框架,旨在通过水下机器人协作减缓定位误差的增长.此外,为解决稀疏网络环境下定位覆盖率低并且能量浪费的问题,一些学者基于AUV引入了区域划分策略,该策略主要包括集中式算法和分布式算法,例如K-means聚类算法和格子化分区方法[9].对此,LIN Y等人[10]通过对水下立方体模块进行划分,利用AUV与目标节点之间的信息完成定位,但未考虑信号重叠现象所造成的能源浪费问题.蒋俊正等人[11]提出了一种基于改进牛顿法定位算法,该算法包括区域划分和分布式算法,提高了稀疏型网络的定位精度,具有良好的延展性,但是增加了算法复杂度.OJHA T等人[12]提出一种基于AUV自适应定位方案,针对稀疏型UASNs提供全网定位服务,使AUV能够在稀疏网络中智能调整传输范围,提高了定位覆盖率.LIU P等人[13]针对稀疏型UASNs提出一种基于spark的并行遗传算法来计算舒伯特多峰函数的极值,得到UASNs的最优部署.SU Y等人[14]提出一种三维环境下分区迭代定位机制,即先对邻居节点进行定位,再依次定位外围节点,实现了大规模目标节点的分层定位,有效降低了定位误差,但对稀疏型网络,无法保证良好的定位覆盖率.SONG L等人[15]提出一种基于六边形单AUV区域划分定位算法,布放虚拟锚节点对部分目标节点定位,然后将已定位节点升级为虚拟锚节点,完成剩余节点的定位工作.该算法在位置覆盖、定位速度和功耗方面具有一定优势,但是同样未说明信号重叠区域的目标节点如何定位,同时升级节点的思想会产生一定的误差累积,以及单AUV机制需要承担大量能耗,缩短了AUV工作时间,不利于大规模网络作业.XU T等人[16]所提算法同样基于六边形进行区域划分,该算法通过分析距离因素解决了信号重叠区域节点定位问题.由于六边形是二维图形,因此基于六边形分区仅适用于二维场景,且与六边形同源的六棱柱是否适合三维网络的区域划分问题,LIU L等人[17]对其进行了研究:将目标海域分成多个六面体,利用轨迹的垂直特性完成所有目标节点定位.该算法与二维六边形分区思想同源,能够很好地保证三维网络定位覆盖率,但遗憾的是算法并未考虑由于信号重叠产生的能耗问题.

鉴于此,本文针对UASNs中稀疏网络定位问题,提出一种AUV协同控制的TO模型区域划分定位算法(aregion determination localization of TO-model,TORD),该算法使用结构和功能相同的2个AUV协同控制完成定位.第1个AUV依据所提出的TO模型完成区域划分,并利用最小值判定法整合信号重叠区域内的公共节点,即在子区域中心以广播的形式与目标节点进行通信,接收到信息的目标节点反馈包含自身编号的数据包,该AUV通过接收到目标节点的反馈信息,确定该子区域(以TO模型中心为信号源所形成的球型信号覆盖范围)存在的目标节点数量和身份信息,然后向第2个AUV发送子区域编号、目标节点编号和数量等信息.第2个AUV接收信息后移动到对应子区域完成定位工作,并将定位的目标节点数量反馈给第1个AUV,如果与第1个AUV识别的目标节点数量不一致,则重新执行定位工作,如果一致,表示该子区域定位工作完成,第2个AUV暂时进入睡眠状态,等待下一次信号到达后被唤醒.TORD优势主要在于:1)目标区域的完全划分,提高了定位覆盖率;2)最小值判定法完成了公共节点的整合,避免了节点的重复定位,减少了能量损耗;3)利用AUV协同机制减少了空闲状态下AUV的能耗,并且为算法提供了执行结束的标志、避免了定位时遗漏目标节点,进一步确保了定位覆盖率;4)该协同机制分散了AUV的能耗,而非让1个设备承受全部能耗,有效延长了设备使用时间,增加了AUV的生命周期,这在面对大规模网络时能够体现出显著的优势,提高了算法的鲁棒性;5)双AUV合作机制实现了区域划分和定位工作同时进行,而非交替进行,极大提高了工作效率.

2 模型设计

2.1 稀疏网络模型

假设在1000 m×1000 m×500 m的定位区域中随机部署N个目标节点Pi(i=1,2,···,N),所有节点通信半径为R,节点间通过声波信号进行通信.如图1所示,负责区域划分的AUV命名为AUV-V,负责定位的AUV命名为AUV-F,图1体现了目标区域经AUV-V一次遍历后的一层子区域及非空子区域的网络模型,每个球体都是一个子区域,其中虚线球体表示空区域(没有目标节点的子区域),实线球体表示非空区域.AUV-V遍历TO模型中心,并向AUV-F发送数据包,包括子区域以及目标节点编号和数量等信息,AUV-F接收信息后被唤醒并前往相应子区域对目标节点进行定位,1个子区域内目标节点定位完成后,向AUV-V反馈定位信息,如信息一致,则该子区域定位工作结束,并进入睡眠状态,等待下一次信号到达后再次被唤醒,否则,重新进行定位工作.

图1 网络区域划分模型Fig.1 Network area division model

2.2 TO模型

为减少AUV-V移动过程中发射信号次数,降低网络能源消耗,该领域很多研究者采用XU T等人[16]提出的原则进行区域划分,本文将其扩展至三维环境:1)模型堆砌后可将目标区域完全覆盖;2)模型体积最大限度接近球型体积.而在空间堆砌中,存在单一多面体堆砌和多种多面体混合堆砌两种方式,其中能够实现空间堆砌的单一多面体包含正方体、正六棱柱、正三棱柱和截角八面体,其他多面体完成堆砌则需要多种多面体进行组合,但不仅多面体的范围难以确定,其组合方式也十分复杂[19],由此本文研究单一多面体堆砌问题.根据上述原则,区域划分模型基于能够单独完成堆砌的多面体选择,其中最接近球型体积的是截角八面体模型(truncated octahedron,TO),下文对此展开论证.

定义1体积系数λ指模型体积V与自身外接球体积之比,公式为

由定义(1)可见,体积系数λ越接近1,多面体体积越接近其外接球体积,子区域间重叠区域越小.在此给出引理1论证不同模型的体积系数.

其中:l为截角八面体边长,la为截角八面体中心至正方形面的垂直距离.

图2 模型局部示意图Fig.2 Local schematic diagram of model

因为ΔDEb3和ΔDa3b3均为直角三角形,所以由勾股定理可得截角八面体中心与各正方形面垂直距离la、边长l和外R的关系式

过四边形和六边形中心线,截取截角八面体横截面A-B-C-D-E-F,如图3所示,α,β为横截面对角线的两个夹角.

图3 横截面示意图Fig.3 Schematic diagram of cross section

由此可得

将式(5)进行3阶泰勒展开可得f(σ)存在1个实根σ1和2个复数根σ2,σ3,由盛金公式得

由式(6)可得到TR8棱长l与其中心至各顶点距离R的关系

3 TORD算法

3.1 划分目标区域

为保证以最少子区域数量提供最大信号覆盖范围,基于引理1,本文提出一种TO模型区域划分方式,进而确定AUV-V的移动步长.

设半径为R的模型中心到其正六边形面垂直距离为lb,由勾股定理可得

如图4所示,设相同颜色区域为同层次子区域,以正方形面为接触面进行排列,模型间中心距离为2la;不同颜色区域表示不同层子区域,以正六边形面为接触面进行排列,模型间中心距离为2lb.

图4 TO模型堆砌方式Fig.4 Stacking mode of TO-model

其中:u指部署在y轴方向上第u个子区域,w指部署在z轴方向上第w个子区域.

层间子区域中心坐标为

其中:λ=(ϑ-1)la,且AUV-V取2la和2lb作为层内与层间步长.

所提出的区域划分方式在保证重叠区域最少的同时,完成了目标区域的全覆盖.因此,实现了在AUV-V遍历过程中既降低了通信次数,也保证目标区域的信号全覆盖,从而既控制了区域划分过程中的能量消耗,也保证了良好的定位覆盖率.

3.2 整合公共节点

由于TO模型外接球半径取值为通信半径R,且VTR8小于其外接球体积,所以TO模型范围小于子区域范围,因此,在以TO模型中心为信号源的球型区域中可能发生信号重叠现象.又因节点分布具有随机性,所以易导致在目标节点分区时产生歧义,现将信号发生重叠的区域称为重叠区域,重叠区域内的目标节点称为公共节点.为方便分析现给出以下定义:

定义2设D(SID)为公共节点P距离子区域SID中心的距离,N(SID)为子区域SID内非公共节点的数量,定义P的校正值为其中:ID∈{1,2,···,snum},snum为产生单个重叠区域的相关子区域数量,由此给出下面的校正规则:

规则1若Si的校正值小于Sj的校正值,则将P划分至子区域Si,若大于划分至Sj;

规则2若校正值均相等,则将公共节点划分至其中任意1个子区域.

由于存在2个及以上的子区域重叠导致出现重叠区域,因此整合公共节点的方法更为复杂.为解决上述问题,本文基于构建校正值公式,提出一种整合多个子区域重叠所产生的公共节点的最小值判定法.该算法首先测得公共节点与相关子区域中心点的距离,再结合非公共节点数量,利用校正公式判定公共节点所属子区域.在此给出定理1:

定理1根据校正公式可将位于多个子区域重叠的重叠区域的公共节点划分至单个子区域.

证 如图5所示,设阴影部分为2个子区域重叠的重叠区域,P为公共节点.首先计算P到子区域Si(i=1,2)中心的距离D(Si),然后AUV-V通过与节点通信判断Si中非公共节点的数量N(Si);代入式(12)得到fP(Si)的值,如果满足,则将P划分至Sj,如果fP(S1)=fP(S2)或者D(S1)=D(S2)=0,则将P划分至S1和S2任意1个子区域.

图5 重叠区域示意图Fig.5 Diagram of overlapping region

假设阴影部分为k(k≤snum)个子区域重叠的重叠区域,计算P到子区域Si(i=1,2,···,k)中心的距离D(Si),然后判断Si中非公共节点的数量N(Si);代入式(12)得到fP(Si),如果,则将P划分至Sj,如果(D(Si)=D(Sj)=0),则将P划分至Si任意1个子区域即可.证毕.

综上,依据校正公式可解决多个子区域重叠产生的公共节点的区域划分问题.

针对无法直接判定公共节点所属子区域的问题,提出最小值判定法,通过计算公共节点与子区域中心的距离预计非公共节点数量完成公共节点的整合.即首先计算D(SID)和N(SID)的值,代入式(12)计算校正值fP(SID),若子区域非公共节点数不为0,将P划分至fP(SID)为最小值时所对应的子区域;若为0或者各fP(SID)值相等,将P划分至任意相关子区域.

相比同类文献,最小值判定法不仅解决了多个子区域重叠产生的公共节点区域划分问题[18-21],而且能够保证包含目标节点的子区域数量达到最低,进一步控制了AUV-F定位时的能量消耗.

3.3 定位目标节点

AUV-F接收信号后移动到相应子区域,并随机布放n个非共面的虚拟锚节点qj(j=1,2,···,n)与目标节点Pi进行通信,然后计算qj与Pi的距离dij,假设Pi坐标为(xi,yi,zi),qj坐标为,利用最小二乘法解得dij为

将式(13)整理成矩阵形式

其中:A,η,b表示

通过式(17)计算出目标节点的位置为

由于定位环境为三维网络,则n取值下限为4,为获得更合适的上限值,结合仿真试验进行说明.在表1的参数设置下,本文利用MATLAB对子区域虚拟锚节点数量进行了实验.为避免虚拟锚节点批量随机生成导致实验结果失去参考价值,现采取逐步随机方式生成虚拟锚节点进行仿真.

表1 子区域参数设置Table 1 Parameter setting of sub-regions

如图6所示,对500次结果取均值,随着子区域虚拟锚节点数量n的增大,平均定位误差总体呈缓慢降低趋势,当n∈[8,20]时误差维持在0.125左右,因此本文n取值范围在[8,20]可保证定位精度较高.为确定n的最优值,本文对路径长度进行了仿真,由图6可知,n递增时路径长度随之增加,当n＞12时,路径长度增加程度明显.因此取n∈[8,12],既能保证路径长度较短,也能维持较低的定位误差.

图6 随n值增大路径长度、定位误差变化图Fig.6 Change of path length and localization error

3.4 TORD算法步骤

步骤1基于所提出的TO模型根据式(10)和式(11)完成区域划分.

步骤2利用最小值判定法整合公共节点.

步骤3AUV-V遍历目标区域并记录每个子区域编号以及目标节点编号和数量,AUV-F保持睡眠.

步骤4AUV-V逐步确定目标节点所属子区域,同时与AUV-F通信并将其唤醒.

步骤5AUV-F访问AUV-V筛选出的非空区域,并产生虚拟锚节点与该子区域内目标节点进行通信.

步骤6利用最小二乘法计算该子区域内目标节点的位置.如果AUV-F定位的目标节点数量与AUV-V记录的数量一致,则进入睡眠状态并等待再次被唤醒,不一致则重新执行步骤6.

4 仿真结果与分析

在表2所示的参数设置下,本文利用MATLAB对所提算法进行了仿真验证,并与稀疏环境下的SEAL[12],TSFL[14],MPL[18],BMAP[20]和3D-MNRBSADV-HO-P[21]的定位性能进行了比较.

表2 目标区域参数设置Table 2 Parameter setting of target region

本文依据HAN G等人[22]提出的埃克曼分层模型,将N个目标节点随机部署在1000 m×1000 m×500 m的目标区域,将平均误差函数作为衡量标准

其中:M为仿真次数为第i次仿真完成定位的节点数,(xt,yt,zt)为目标节点估计位置,(xr,yr,zr)为目标节点实际位置.

依据ZHANG Qiang等人[23]提出的定义作为定位覆盖率衡量标准,表示为

其中Ntotal为总节点数目.

4.1 通信半径对定位覆盖率的影响

图7给出了TORD算法定位覆盖率随通信半径的变化,由图7可知,虚拟锚节点数量n随通信半径R的增大而降低,但二者均对定位覆盖率影响较小.因为R的改变减少了子区域的数量,从而n的值随之减小,但依据所提出的区域划分方式,依然能够保证目标区域的信号覆盖,进而保证了较高的定位覆盖率.同时,由图7可以看出,随着通信半径的增长,MPL算法和TORD算法定位覆盖率均较为稳定,但前者覆盖率相对偏低,而TSFL算法在通信半径增大到约400m时覆盖率较高并趋于稳定,因此,TORD算法在定位覆盖率方面的优势更加突出.

图7 不同通信半径下虚拟锚节点数目和定位覆盖率Fig.7 Number of virtual anchor nodes and localization coverage under different communication radius

4.2 通信半径对模糊节点数量和处理率的影响

由于公共节点的整合结果对定位影响较大,因此现对本文提出的最小值判定法的有效性进行验证,并提出以下定义:

定义3设产生的公共节点数量为Nfu,被处理公共节点数量为Ncfu,则处理率Cop为

图8为网络区域范围为1000m,计算公共节点数量和处理率Cop随通信半径变化而改变的结果图.从图8可以看出,在目标区域环境一定的情况下,当通信半径R≤300 m时,公共节点数量相对较少.根据最小值判定法对其进行二次划分,随着公共节点数量不断增加,Cop依然保持稳定且处理效果显著.

图8 不同通信半径下模糊节点数目、Cop变化图Fig.8 Changes in the number of fuzzy nodes and processing rate

4.3 不同网络区域范围下虚拟锚节点数量的比较

图9为当通信半径R的取值定为300m时,3D-MNRBSA-DV-HOP、BMAP和TORD关于虚拟锚节点个数与网络区域范围关系对比图.如图9所示,随着网络区域范围的增加,子区域数量会随之增加,进而虚拟锚节点数量呈上升趋势.相比BMAP算法,TORD算法的虚拟锚节点数量平均降低了54%,最高可达68.8%,与3D-MNRBSA-DV-HOP算法相比,网络区域范围大于720m时,TORD算法虚拟锚节点数量平均降低10.4%,最高可达20%,且与上述两种算法相比,在网络区域范围为1000m时,TORD算法虚拟锚节点数量较低,因此算法能耗较低.

图9 不同区域范围下虚拟锚节点数量对比图Fig.9 Comparison of the number of virtual anchor nodes in different regions

4.4 不同网络区域范围下定位误差的比较

如图10所示,当通信半径R取300m、网络区域范围从400m至1000m变化时,TORD算法的定位误差始终低于其他3种算法,并且TORD算法误差变化趋势呈稳定状态,因此算法鲁棒性强.

图10 不同区域范围下定位误差对比图Fig.10 Comparison of localization errors in different regions

5 结论

本文针对UASNs动态变化易形成稀疏型低覆盖定位问题,提出AUV协同控制的TO模型区域划分定位算法.该算法首先从理论上证明了TO模型满足三维区域划分原则并且其体积比相对最优,设计了最优区域划分方式,并提出最小值判定法解决公共节点区域划分问题;然后提出AUV协同策略完成定位.理论分析和仿真表明,与同类算法相比,在不同网络范围和通信半径标准下,所提算法能更好地适用于稀疏网络环境,保证了定位精度的同时有效提高了网络定位覆盖率和鲁棒性.同时,算法使用AUV协同机制可实现区域划分与定位工作同步执行,并且AUV-F只需关注非空区域即可,从而缩短了算法执行时间,减少了能量消耗,延长了设备使用寿命.此外,AUV移动轨迹是决定定位精度和能耗的重要因素,未来将对轨迹优化作进一步研究.