基于自适应与轨迹预测的移动节点定位

郭世俊, 吴华锋, 刘 侠, 马奕葳

(1. 上海海事大学 商船学院， 上海 201306； 2. 中国(上海)自贸区供应链研究院， 上海 201306)

基于自适应与轨迹预测的移动节点定位

郭世俊1, 吴华锋1, 刘 侠1, 马奕葳2

(1. 上海海事大学 商船学院， 上海 201306； 2. 中国(上海)自贸区供应链研究院， 上海 201306)

针对海上节点随海浪运动的情形，提出一种基于自适应与轨迹预测的移动节点定位算法(Adaptive and Trajectory Prediction Localization Algorithm, ATPLA)。首先，基于海域信标节点运动情况求得海域节点运动相关性系数，并以此建立参数自适应移动节点运动模型，预测未知节点运动轨迹；随后，提出改进型蒙特卡罗定位方法，优化采样区域和样本点权重；最后，基于未知节点与其一跳、两跳信标节点相对位置进行过滤。仿真结果表明：ATPLA在信标节点密度低、节点运动速度大等情况下具有良好的定位效能，能提高海上动态节点的定位能力，进而提高海上搜救的效率和成功率。

交通信息工程； 无线传感网； 高斯马尔科夫定理； 蒙特卡洛方法； 动态定位； 海上搜救

Abstract: The Adaptive and Trajectory Prediction Localization Algorithm (ATPLA) for nodes on sea surface is introduced. As the first step, the motion correlation coefficient related to the notes in an area is obtained according to the motion of beacon nodes in the area, and the parameter adaptive motion model of the nodes is established for predicting the trajectory of interested unknown nodes. The sampling area and the weights of the sampls are refined with Monte Carlo positioning algorithm afterwards. The position of an unknown note can be determined by means of filtering its one hop and two hop distances relative to beacon nodes. Simulation proves that the ATPLA performs well even if in the situation of low beacon density or high node velocity. The use of ATPLA can improve the mobile note positioning efficiency for maritime search and rescue activity.

Keywords: traffic information engineering; wireless sensor network; Gauss Markov theorem; Monte Carlo method; mobile localization; maritime search and rescue

经济的快速发展和对外贸易的不断拓展推动着海上交通运输等海洋事业的发展。我国海上经济贸易发展迅速，海洋从业人员数量急剧增多，海难事故和遇难人数随之不断攀升，导致海上搜救和物标跟踪定位任务日益繁重。研究表明，落水人员在20 ℃海水中浸泡最长存活16 h 20 min,而在0 ℃海水中最长仅存活12 min。因此，搜救时间极为紧迫，快速获取被搜救人员的位置显得尤为重要。

现行的搜救方法主要是出动大量搜救船舶和直升机，利用人眼或机械设备进行搜索。一些技术和设备的应用可在一定程度上提高海上搜救时定位的成功率，但这些搜救设备仅能提供事故发生的位置，而当展开搜救工作时落水人员或其他物体已在风、流、浪和涌等因素的作用下发生漂移，远离了初始位置。此时，搜救人员需花费大量时间确定搜救范围，这会大大增加搜救难度、降低搜救成功率。若能获取海上待搜救人员或货物等随海浪的运动轨迹，则搜救机构即可有目的地进行搜寻，从而减少搜寻时间、提高搜救效率。

无线传感器网络是由具有感知、计算和无线通信能力的传感器节点自组织形成的网络。该技术的迅速发展为海洋信息的实时获取和高效传输提供了重要的技术支撑，为海洋环境监测、生物跟踪及海洋物标搜救[1]等相关应用和研究带来了强大的推动力，不仅可以用来监测风向、波高、潮汐、水温、光照和水质污染等与海洋相关的信息[2]，而且负责水下水声传感器网络的信息传输[3]。然而，海上多恶劣天气，易出现大风大浪情况，使得海上人员或货物的运动高度动态，这对海上无线传感器网络的应用，尤其是海上人员或货物的定位是一个严峻的考验。

因此，必须对高度动态的海上移动节点轨迹预测进行研究。考虑到动态海况环境因素的影响，针对海上移动物标对定位算法的要求，将信标节点的运动情况引入到节点运动轨迹的预测中，提出一种移动节点参数自适应轨迹预测算法。在进行轨迹预测时，充分考虑对多变环境的自适应，并对基于蒙特卡罗方法定位的采样区域和样本点权重进行优化。最后，将未知节点运动过程中与一跳和两跳信标节点的相对位置信息作为过滤条件，提高海上定位的精度。该研究的成果主要有以下几点。

1) 通过对海上无线传感器网络移动目标跟踪进行研究，提高动态环境下无线传感网定位的精度和速率。

2) 基于自适应与轨迹预测的移动节点定位算法(Adaptive and Trajectory Prediction Localization Algorithm, ATPLA),根据海域信标节点运动情况构建参数自适应运动模型，对海域节点运动情况预测提供算法支撑。

3) 自适应运动模型的应用为海上漂移物漂移模型的研究提供理论依据。

1 WSN定位现有主要技术

已有的对无线传感器网络定位算法的研究主要集中在静态网络环境方面,而现有的静态网络环境下信标节点和未知节点均固定的情形难以适用于海上信标节点和未知节点都运动的环境。

海上无线传感器网络节点动态定位一直备受相关学者关注。GUO等[4]和YU等[5]对海洋传感器网络(Ocean Sensor Networks，OSN)水下三维网络的拓扑、路由和定位进行综述，从宏观上提出几种可行的定位算法设计方案，对定位算法的设计具有一定指导作用。 USMAN等[6]对三维无线传感器网络的覆盖范围和连通性进行研究，但未能给出具体的定位算法。YV等[7]使信标节点在未知节点固定的部署区域内按随机路径移动并周期性地广播自己的位置信息，未知节点对接收到的信标信号进行处理并计算自己的位置。 FU等[8]利用蚁群算法优化移动节点的运动路径，按等边三角形最优覆盖原则对上述信标节点的运动轨迹进行滤波优化，降低能耗、提高定位精度。这类算法适用于搜救过程中落水人员位置不变、搜救直升机上装载有信标节点的定位情形。但是，海上事故发生时往往伴随有恶劣天气，搜救过程中落水人员位置不变的情形是很少的，算法普适性较差。HYOCHANG等[9]对移动未知节点与信标节点之间接收的信号强度(Received Signal Strength, RSS)测值进行优化，并依据RSS值设置一定的加权方式，提高定位精度。MUZAMMIL等[10]提出基于DV-Distance的APDV定位算法，利用未知节点运动时相对于固定信标节点向量的变化进行辅助定位，降低基于RSSI测距时因非视距信号传播导致的误差，提高复杂环境下的定位精度。 WU等[11]对基于RSSI的数据传输模型进行研究，考虑海浪对信号传播的遮蔽影响，建立符合海上信号传播的遮蔽模型，并确立符合海上搜救环境的路径损耗优化模型；同时,对三角形质心算法进行优化，提出一种基于RSSI加权的三角质心优化定位算法，提高海上搜救的定位精度和搜救成功率。这类算法虽然考虑了落水人员在海上运动的情形，但未对节点运动轨迹进行研究，无法确定从事故发生至开始搜救时间段内节点的运动情况。

目前国内外对海上动态网络定位算法的设计研究还处于起步阶段，研究成果相对较少。 ZHOU[12]假设水下物标在固定的垂直高度作二维水平运动，根据标准的二阶常速度运动模型构建运动状态方程，对节点进行跟踪和定位。然而，该定位算法仅适用于水下环境，适用性较差。针对海上环境， REN等[13]以牛顿插值多项式构建节点的运动模型，提出基于蒙特卡罗算法的多维节点定位算法(Monte Carlo Multidimensional Localization Algorithm, MCMLA)，可在一定程度上解决水下三维定位问题。但是，该算法在进行运动轨迹预测时未考虑对海上环境变化作自适应调整，运动模型自适应性较差。此外，在利用蒙特卡洛定位(Monte Carlo Localization，MCL)[14]时，对采样区域仅在速度方向上基于海浪谱作优化，未考虑在遮蔽效应影响下确定采样区域时还应对速度大小进行优化。

上述算法均有各自的优势，但没有考虑海上风、浪、流的影响，构建的运动模型参数不能根据所处海域的变化作出自适应调整，难以达到所需要的定位精度。根据对波浪的理论假设及处理方法的不同，将海浪运动分为线性波和非线性波2种[15]。这里基于线性的海浪波进行研究。因此，在构建移动节点运动轨迹时，构建一种能自适应恶劣海况的模型实现节点高精度定位。在研究现有物体运动模型的基础上，以提高运动模型自适应为重点，对高斯-马尔科夫运动模型(Gaussian Markov Mobility Model，GMMM)[16]进行参数自适应优化。

2 移动节点参数自适应轨迹预测算法

海难事故发生后，落水人员和货物会在海浪的作用下发生漂移。这里提出移动节点参数自适应轨迹预测算法，根据海域内信标节点的运动情况求得节点的运动相关性系数，构建节点运动模型。此外，提出改进的蒙特卡洛方法，对采样区域和样本点权值进行优化。算法流程见图1。

图1 算法流程

2.1节点运动模型

基于线性海浪波构建海浪运动模型，提出参数自适应模型预测海浪的运动趋势。发生海上事故时，通过船载全球定位系统(Global Positioning System，GPS)、紧急无线电示位标(Emergency Position Indication Radio Beacon，EPIRB)及搜救人造卫星系统(Search And Rescue Satellite Aided Tracking，SARSAT)等设备确定节点落水时的初始位置及其运动情况，作为GMMM下节点运动的初始速度和方向，节点后一时刻的运动速度和方向根据节点之前时间段内的运动数据进行更新，公式为

(1)

(2)

1) 当α=0时，有

(3)

(4)

2) 当α=1时，有

dt=dt-1

(5)

st=st-1

(6)

则运动延续之前动作，为线性运动。

在一段时间内，同一海域节点的运动相关性系数α相同。在构建海域节点运动模型时，参数α的自适应就是运动模型的自适应，从而使运动模型的准确性更高。

2.2节点运动参数

(7)

(8)

同理可得

(9)

受海浪遮蔽效应的影响，高斯随机标量作为环境噪声不可避免，导致α值存在误差βαt-1,此时

(10)

(11)

(12)

对运动参数进行自适应更新之后，依据式(13)和式(14)求得此时节点的位置坐标为

(13)

(14)

式(13)～式(14)中:φ为dt在所建X-Y坐标系内X轴方向的夹角;T为取样的时间周期。

2.3改进型蒙特卡罗采样区域

1) 考虑节点运动方向的误差Δθ，以节点运动方向dt为中心线、st为半径，将该中心线顺时针和逆时针各展开Δθ弧度，提出基于Δθ的扇形加权区域。

2) 考虑节点速度的误差Δs，在节点运动方向dt上对st以Δs为增量作同心扇形，提出基于Δs的环形换加权区域。

3) 将基于Δθ和基于Δs构建的加权区域叠加，提出改进型蒙特卡罗采样盒子(见图2)。

图2 改进型蒙特卡罗采样盒子采样图

初始采样盒子面积为

s(1)=4nΔθΔs2

(15)

若滤波后符合要求的点不够N个，则将Δθ和Δs扩大一倍，如图2中外围环形扇形区域所示，此时采样盒子的面积为

s(2)=16nΔθΔs2

(16)

进行第i次扩张时，得到的采样盒子面积为

s(i)=4ni2ΔθΔs2

(17)

而后进行重采样和滤波，直到得到满足的点。

对采样盒子的权值进行设置时，靠近运动模型所确定的位置权值大，具体设置为

(18)

将第i个样本点的权重归一化得

(19)

则所求坐标为

(20)

3 仿真结果分析

利用MATLAB 7.10平台进行计算机仿真。仿真参数设置为：仿真区域为1 000 m×1 000 m的正方形区域；测距模型中n=2.4，Xσ=7.98 dB;节点运动以1～10 m/s的速率随机运动；节点通信半径为100 m。仿真试验主要是将所提出的算法(ATPLA)与基于蒙特卡罗算法的多维节点定位算法[9](MCMLA) 和蒙特卡罗定位算法[14](MCL)进行比较,主要研究信标节点密度和节点移动速度变化对平均定位误差的影响。

图3为定位误差随信标节点密度变化曲线。当每平方海里有4个信标节点时，MCL，MCMLA和ATPLA的定位误差率分别为0.44，0.3和0.11；ATPLA的定位误差率相比前两者分别降低0.75和0.63。该算法在构建节点运动模型时，通过信标节点的运动求得整个海域的运动参数，因此随着信标节点数目增加，该研究能更加准确地确定运动模型，使定位精度得到较好的提高。

图3 定位误差随信标节点密度变化曲线

图4为定位误差随速度变化曲线。当节点的运动速度为2 m/s时，MCL，MCMLA和ATPLA的定位误差率分别为0.76，0.62和0.5；ATPLA的定位误差率相比前两者分别降低0.34和0.19。随着节点运动速度增大，拓扑结构变化频繁，定位的准确度受到影响。此外，MCL是以一跳通信半径R和二跳通信半径2R为过滤条件的，当节点的运动速度增大至2R时，采样粒子数量不够，容易造成死循环；而该算法是基于自身位置实时可知的信标节点构建的运动模型，具有自适应性，所得的运动模型更加准确，能在速度较大的情况下获得较好的定位精度。

图4 定位误差随速度变化曲线

4 结束语

针对海上环境中节点随着海浪运动的应用场景，根据信标节点的运动情况构建符合该海域所有节点的运动模型，结合节点的历史运动轨迹预测未知节点可能的位置；考虑海浪遮蔽效应的影响，设定蒙特卡罗方法定位时的采样区域和权值；以一跳和二跳信标节点为过滤条件，提高样本的有效性和动态网络的定位精度。该模型能克服采用MCL定位时采样容易陷入死循环的缺点，更符合海上环境的应用。仿真结果表明：当信标节点密度低、节点运动速度高时，所提定位算法的定位效果好于以往的定位算法，能很好地适应海上节点的高度动态性，实时获取精确的位置信息，提高救援成功率，减少生命财产损失。

[1] KRISHNA C R, YADAV P S. A Hybrid Localization Scheme for Underwater Wireless Sensor Networks [C]. IEEE International Conference on Issues and Challenges in Intelligent Computing Techniques, 2014.

[2] LUO H J, ZHONG Y, LIN F H. Localization for a Hybrid Ocean Wireless Sensor Networks [J]. Springer Berlin Heidelberg Advanced Technologies in Ad Hoc and Sensor Networks, 2014,295： 353-362.

[3] PETRIOLI C, PETROCCIA R, POTTER J R. The SUNSET Framework for Simulation, Emulation and At Sea Testing of Underwater Wireless Sensor Networks [J]. Ad Hoc Networks, 2014,34:224-238.

[4] GUO Z W, LUO H J, HONG F. Current Progress and Research Issues in Underwater Sensor Networks[J]. Journal of Computer Research and Development, 2010, 47(3): 377-389.

[5] YU W, LIU Y J, GUO Z W. Three-Dimensional Ocean Sensor Networks: A Survey[J]. Journal of Ocean University of China, 2012, 11(4): 436-450.

[6] USMAN M, AMMARI H M. Coverage and Connectivity in 3D Wireless Sensor Networks [C]. The Art of Wireless Sensor Networks in Springer Berlin Heidelberg, 2014.

[7] LV J, WANG Y, WEI N, et al. Dynamic Path Planning Method for Anchor Node in Three-Dimensional Wireless Sensor Networks [C]. IEEE International Symposium on Instrumentation and Measurement Sensor Network and Automation, 2013.

[8] FU Q, CHEN W, LIU K Z. Node Localization with a Mobile Beacon Based on Ant Colony Algorithm in Wireless Sensor Networks [C]. IEEE International Conference on Communications and Mobile Computing, 2010.

[9] HYOCHANG A, RHEE S B. Simulation of a RSSI-Based Indoor Localization System Using Wireless Sensor Network [C]. IEEE Proceedings of the 5th International Conference on Ubiquitous Information Technologies and Applications, 2010.

[10] MUZAMMIL H, TRIGONI N. Adaptive Node Placement for Improving Localization Accuracy in Clutter-Prone Environments [C]. IEEE Wireless Communications and Networking Conference, 2013.

[11] WU H F, YANG L, LIU L, et al. Real-Time Localization Algorithm for Maritime Search and Rescue Wireless Sensor Network [J]. International Journal of Distributed Sensor Networks, 2013(3)：188-192.

[12] ZHOU H F. Underwater Sensor Networks Target Tracking Algorithm Research [D]. Hangzhou: Zhejiang University, 2013.

[13] REN K L, HAN J J. Node Localization Algorithm of Wireless Sensor Network in Marine Monitoring [J]. Journal of Computer Applications, 2012, 32(10): 2692-2695.

[14] ALINE B, LANGENDOEN X. Monte Carlo Localization for Mobile Wireless Sensor Networks [J]. Ad Hoc Networks, 2008, 6(5): 718-733.

[15] BANNER M L, BARTHELEMY X, FEDELE F, et al. Linking Reduced Breaking Crest Speeds to Unsteady Nonlinear Water Wave Group Behavior [R]. Physical Review Letters, 2014.

[16] WU W, QIN S, WANG X. A New Integrated Gaussian-Markov Process Model for Precision Shipboard Transfer Alignment [C]. IEEE in Position, Location and Navigation Symposium, 2014.

MobileNodeLocalizationBasedonAdaptiveTrajectoryPrediction

GUOShijun1，WUHuafeng1，LIUXia1,MAYiwei2

(1. Merchant Marine College, Shanghai Maritime University, Shanghai 201306, China; 2. China Institute of FTZ Supply Chain, Shanghai 201306, China)

U644.1

A

2016-03-18

国家自然科学基金(51279099)；上海市科学技术委员会基金(12ZR1412500)；上海市教委科研创新基金(13ZZ124)；上海市教育委员会和上海市教育发展基金会“曙光计划”基金(12SG40)；交通运输部应用基础研究项目(2013329810300)

郭世俊(1990—),男,湖北潜江人,硕士生,从事无线传感网研究。E-mail:guoshijun1990@126.com 吴华锋(1976—)，男，福建浦城人，教授，从事交通信息、无线传感网研究。E-mail:hfwu@shmtu.edu.cn

1000-4653(2016)02-0001-05