基于自適應與軌跡預測的移動節點定位

郭世俊, 吳華鋒, 劉 俠, 馬奕葳

(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