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

(1. 上海海事大學 商船學院， 上海 201306； 2. 中國(上海)自貿(mào)區(qū)供應(yīng)鏈研究院， 上海 201306)

基于自適應(yīng)與軌跡預(yù)測的移動節(jié)點定位

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

(1. 上海海事大學 商船學院， 上海 201306； 2. 中國(上海)自貿(mào)區(qū)供應(yīng)鏈研究院， 上海 201306)

針對海上節(jié)點隨海浪運動的情形，提出一種基于自適應(yīng)與軌跡預(yù)測的移動節(jié)點定位算法(Adaptive and Trajectory Prediction Localization Algorithm, ATPLA)。首先，基于海域信標節(jié)點運動情況求得海域節(jié)點運動相關(guān)性系數(shù)，并以此建立參數(shù)自適應(yīng)移動節(jié)點運動模型，預(yù)測未知節(jié)點運動軌跡；隨后，提出改進型蒙特卡羅定位方法，優(yōu)化采樣區(qū)域和樣本點權(quán)重；最后，基于未知節(jié)點與其一跳、兩跳信標節(jié)點相對位置進行過濾。仿真結(jié)果表明：ATPLA在信標節(jié)點密度低、節(jié)點運動速度大等情況下具有良好的定位效能，能提高海上動態(tài)節(jié)點的定位能力，進而提高海上搜救的效率和成功率。

交通信息工程； 無線傳感網(wǎng)； 高斯馬爾科夫定理； 蒙特卡洛方法； 動態(tài)定位； 海上搜救

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

經(jīng)濟的快速發(fā)展和對外貿(mào)易的不斷拓展推動著海上交通運輸?shù)群Ｑ笫聵I(yè)的發(fā)展。我國海上經(jīng)濟貿(mào)易發(fā)展迅速，海洋從業(yè)人員數(shù)量急劇增多，海難事故和遇難人數(shù)隨之不斷攀升，導致海上搜救和物標跟蹤定位任務(wù)日益繁重。研究表明，落水人員在20 ℃海水中浸泡最長存活16 h 20 min,而在0 ℃海水中最長僅存活12 min。因此，搜救時間極為緊迫，快速獲取被搜救人員的位置顯得尤為重要。

現(xiàn)行的搜救方法主要是出動大量搜救船舶和直升機，利用人眼或機械設(shè)備進行搜索。一些技術(shù)和設(shè)備的應(yīng)用可在一定程度上提高海上搜救時定位的成功率，但這些搜救設(shè)備僅能提供事故發(fā)生的位置，而當展開搜救工作時落水人員或其他物體已在風、流、浪和涌等因素的作用下發(fā)生漂移，遠離了初始位置。此時，搜救人員需花費大量時間確定搜救范圍，這會大大增加搜救難度、降低搜救成功率。若能獲取海上待搜救人員或貨物等隨海浪的運動軌跡，則搜救機構(gòu)即可有目的地進行搜尋，從而減少搜尋時間、提高搜救效率。

無線傳感器網(wǎng)絡(luò)是由具有感知、計算和無線通信能力的傳感器節(jié)點自組織形成的網(wǎng)絡(luò)。該技術(shù)的迅速發(fā)展為海洋信息的實時獲取和高效傳輸提供了重要的技術(shù)支撐，為海洋環(huán)境監(jiān)測、生物跟蹤及海洋物標搜救[1]等相關(guān)應(yīng)用和研究帶來了強大的推動力，不僅可以用來監(jiān)測風向、波高、潮汐、水溫、光照和水質(zhì)污染等與海洋相關(guān)的信息[2]，而且負責水下水聲傳感器網(wǎng)絡(luò)的信息傳輸[3]。然而，海上多惡劣天氣，易出現(xiàn)大風大浪情況，使得海上人員或貨物的運動高度動態(tài)，這對海上無線傳感器網(wǎng)絡(luò)的應(yīng)用，尤其是海上人員或貨物的定位是一個嚴峻的考驗。

因此，必須對高度動態(tài)的海上移動節(jié)點軌跡預(yù)測進行研究?？紤]到動態(tài)海況環(huán)境因素的影響，針對海上移動物標對定位算法的要求，將信標節(jié)點的運動情況引入到節(jié)點運動軌跡的預(yù)測中，提出一種移動節(jié)點參數(shù)自適應(yīng)軌跡預(yù)測算法。在進行軌跡預(yù)測時，充分考慮對多變環(huán)境的自適應(yīng)，并對基于蒙特卡羅方法定位的采樣區(qū)域和樣本點權(quán)重進行優(yōu)化。最后，將未知節(jié)點運動過程中與一跳和兩跳信標節(jié)點的相對位置信息作為過濾條件，提高海上定位的精度。該研究的成果主要有以下幾點。

1) 通過對海上無線傳感器網(wǎng)絡(luò)移動目標跟蹤進行研究，提高動態(tài)環(huán)境下無線傳感網(wǎng)定位的精度和速率。

2) 基于自適應(yīng)與軌跡預(yù)測的移動節(jié)點定位算法(Adaptive and Trajectory Prediction Localization Algorithm, ATPLA),根據(jù)海域信標節(jié)點運動情況構(gòu)建參數(shù)自適應(yīng)運動模型，對海域節(jié)點運動情況預(yù)測提供算法支撐。

3) 自適應(yīng)運動模型的應(yīng)用為海上漂移物漂移模型的研究提供理論依據(jù)。

1 WSN定位現(xiàn)有主要技術(shù)

已有的對無線傳感器網(wǎng)絡(luò)定位算法的研究主要集中在靜態(tài)網(wǎng)絡(luò)環(huán)境方面,而現(xiàn)有的靜態(tài)網(wǎng)絡(luò)環(huán)境下信標節(jié)點和未知節(jié)點均固定的情形難以適用于海上信標節(jié)點和未知節(jié)點都運動的環(huán)境。

海上無線傳感器網(wǎng)絡(luò)節(jié)點動態(tài)定位一直備受相關(guān)學者關(guān)注。GUO等[4]和YU等[5]對海洋傳感器網(wǎng)絡(luò)(Ocean Sensor Networks，OSN)水下三維網(wǎng)絡(luò)的拓撲、路由和定位進行綜述，從宏觀上提出幾種可行的定位算法設(shè)計方案，對定位算法的設(shè)計具有一定指導作用。 USMAN等[6]對三維無線傳感器網(wǎng)絡(luò)的覆蓋范圍和連通性進行研究，但未能給出具體的定位算法。YV等[7]使信標節(jié)點在未知節(jié)點固定的部署區(qū)域內(nèi)按隨機路徑移動并周期性地廣播自己的位置信息，未知節(jié)點對接收到的信標信號進行處理并計算自己的位置。 FU等[8]利用蟻群算法優(yōu)化移動節(jié)點的運動路徑，按等邊三角形最優(yōu)覆蓋原則對上述信標節(jié)點的運動軌跡進行濾波優(yōu)化，降低能耗、提高定位精度。這類算法適用于搜救過程中落水人員位置不變、搜救直升機上裝載有信標節(jié)點的定位情形。但是，海上事故發(fā)生時往往伴隨有惡劣天氣，搜救過程中落水人員位置不變的情形是很少的，算法普適性較差。HYOCHANG等[9]對移動未知節(jié)點與信標節(jié)點之間接收的信號強度(Received Signal Strength, RSS)測值進行優(yōu)化，并依據(jù)RSS值設(shè)置一定的加權(quán)方式，提高定位精度。MUZAMMIL等[10]提出基于DV-Distance的APDV定位算法，利用未知節(jié)點運動時相對于固定信標節(jié)點向量的變化進行輔助定位，降低基于RSSI測距時因非視距信號傳播導致的誤差，提高復(fù)雜環(huán)境下的定位精度。 WU等[11]對基于RSSI的數(shù)據(jù)傳輸模型進行研究，考慮海浪對信號傳播的遮蔽影響，建立符合海上信號傳播的遮蔽模型，并確立符合海上搜救環(huán)境的路徑損耗優(yōu)化模型；同時,對三角形質(zhì)心算法進行優(yōu)化，提出一種基于RSSI加權(quán)的三角質(zhì)心優(yōu)化定位算法，提高海上搜救的定位精度和搜救成功率。這類算法雖然考慮了落水人員在海上運動的情形，但未對節(jié)點運動軌跡進行研究，無法確定從事故發(fā)生至開始搜救時間段內(nèi)節(jié)點的運動情況。

目前國內(nèi)外對海上動態(tài)網(wǎng)絡(luò)定位算法的設(shè)計研究還處于起步階段，研究成果相對較少。 ZHOU[12]假設(shè)水下物標在固定的垂直高度作二維水平運動，根據(jù)標準的二階常速度運動模型構(gòu)建運動狀態(tài)方程，對節(jié)點進行跟蹤和定位。然而，該定位算法僅適用于水下環(huán)境，適用性較差。針對海上環(huán)境， REN等[13]以牛頓插值多項式構(gòu)建節(jié)點的運動模型，提出基于蒙特卡羅算法的多維節(jié)點定位算法(Monte Carlo Multidimensional Localization Algorithm, MCMLA)，可在一定程度上解決水下三維定位問題。但是，該算法在進行運動軌跡預(yù)測時未考慮對海上環(huán)境變化作自適應(yīng)調(diào)整，運動模型自適應(yīng)性較差。此外，在利用蒙特卡洛定位(Monte Carlo Localization，MCL)[14]時，對采樣區(qū)域僅在速度方向上基于海浪譜作優(yōu)化，未考慮在遮蔽效應(yīng)影響下確定采樣區(qū)域時還應(yīng)對速度大小進行優(yōu)化。

上述算法均有各自的優(yōu)勢，但沒有考慮海上風、浪、流的影響，構(gòu)建的運動模型參數(shù)不能根據(jù)所處海域的變化作出自適應(yīng)調(diào)整，難以達到所需要的定位精度。根據(jù)對波浪的理論假設(shè)及處理方法的不同，將海浪運動分為線性波和非線性波2種[15]。這里基于線性的海浪波進行研究。因此，在構(gòu)建移動節(jié)點運動軌跡時，構(gòu)建一種能自適應(yīng)惡劣海況的模型實現(xiàn)節(jié)點高精度定位。在研究現(xiàn)有物體運動模型的基礎(chǔ)上，以提高運動模型自適應(yīng)為重點，對高斯-馬爾科夫運動模型(Gaussian Markov Mobility Model，GMMM)[16]進行參數(shù)自適應(yīng)優(yōu)化。

2 移動節(jié)點參數(shù)自適應(yīng)軌跡預(yù)測算法

海難事故發(fā)生后，落水人員和貨物會在海浪的作用下發(fā)生漂移。這里提出移動節(jié)點參數(shù)自適應(yīng)軌跡預(yù)測算法，根據(jù)海域內(nèi)信標節(jié)點的運動情況求得節(jié)點的運動相關(guān)性系數(shù)，構(gòu)建節(jié)點運動模型。此外，提出改進的蒙特卡洛方法，對采樣區(qū)域和樣本點權(quán)值進行優(yōu)化。算法流程見圖1。

圖1 算法流程

2.1節(jié)點運動模型

基于線性海浪波構(gòu)建海浪運動模型，提出參數(shù)自適應(yīng)模型預(yù)測海浪的運動趨勢。發(fā)生海上事故時，通過船載全球定位系統(tǒng)(Global Positioning System，GPS)、緊急無線電示位標(Emergency Position Indication Radio Beacon，EPIRB)及搜救人造衛(wèi)星系統(tǒng)(Search And Rescue Satellite Aided Tracking，SARSAT)等設(shè)備確定節(jié)點落水時的初始位置及其運動情況，作為GMMM下節(jié)點運動的初始速度和方向，節(jié)點后一時刻的運動速度和方向根據(jù)節(jié)點之前時間段內(nèi)的運動數(shù)據(jù)進行更新，公式為

(1)

(2)

1) 當α=0時，有

(3)

(4)

2) 當α=1時，有

dt=dt-1

(5)

st=st-1

(6)

則運動延續(xù)之前動作，為線性運動。

在一段時間內(nèi)，同一海域節(jié)點的運動相關(guān)性系數(shù)α相同。在構(gòu)建海域節(jié)點運動模型時，參數(shù)α的自適應(yīng)就是運動模型的自適應(yīng)，從而使運動模型的準確性更高。

2.2節(jié)點運動參數(shù)

(7)

(8)

同理可得

(9)

受海浪遮蔽效應(yīng)的影響，高斯隨機標量作為環(huán)境噪聲不可避免，導致α值存在誤差βαt-1,此時

(10)

(11)

(12)

對運動參數(shù)進行自適應(yīng)更新之后，依據(jù)式(13)和式(14)求得此時節(jié)點的位置坐標為

(13)

(14)

式(13)～式(14)中:φ為dt在所建X-Y坐標系內(nèi)X軸方向的夾角;T為取樣的時間周期。

2.3改進型蒙特卡羅采樣區(qū)域

1) 考慮節(jié)點運動方向的誤差Δθ，以節(jié)點運動方向dt為中心線、st為半徑，將該中心線順時針和逆時針各展開Δθ弧度，提出基于Δθ的扇形加權(quán)區(qū)域。

2) 考慮節(jié)點速度的誤差Δs，在節(jié)點運動方向dt上對st以Δs為增量作同心扇形，提出基于Δs的環(huán)形換加權(quán)區(qū)域。

3) 將基于Δθ和基于Δs構(gòu)建的加權(quán)區(qū)域疊加，提出改進型蒙特卡羅采樣盒子(見圖2)。

圖2 改進型蒙特卡羅采樣盒子采樣圖

初始采樣盒子面積為

s(1)=4nΔθΔs2

(15)

若濾波后符合要求的點不夠N個，則將Δθ和Δs擴大一倍，如圖2中外圍環(huán)形扇形區(qū)域所示，此時采樣盒子的面積為

s(2)=16nΔθΔs2

(16)

進行第i次擴張時，得到的采樣盒子面積為

s(i)=4ni2ΔθΔs2

(17)

而后進行重采樣和濾波，直到得到滿足的點。

對采樣盒子的權(quán)值進行設(shè)置時，靠近運動模型所確定的位置權(quán)值大，具體設(shè)置為

(18)

將第i個樣本點的權(quán)重歸一化得

(19)

則所求坐標為

(20)

3 仿真結(jié)果分析

利用MATLAB 7.10平臺進行計算機仿真。仿真參數(shù)設(shè)置為：仿真區(qū)域為1 000 m×1 000 m的正方形區(qū)域；測距模型中n=2.4，Xσ=7.98 dB;節(jié)點運動以1～10 m/s的速率隨機運動；節(jié)點通信半徑為100 m。仿真試驗主要是將所提出的算法(ATPLA)與基于蒙特卡羅算法的多維節(jié)點定位算法[9](MCMLA) 和蒙特卡羅定位算法[14](MCL)進行比較,主要研究信標節(jié)點密度和節(jié)點移動速度變化對平均定位誤差的影響。

圖3為定位誤差隨信標節(jié)點密度變化曲線。當每平方海里有4個信標節(jié)點時，MCL，MCMLA和ATPLA的定位誤差率分別為0.44，0.3和0.11；ATPLA的定位誤差率相比前兩者分別降低0.75和0.63。該算法在構(gòu)建節(jié)點運動模型時，通過信標節(jié)點的運動求得整個海域的運動參數(shù)，因此隨著信標節(jié)點數(shù)目增加，該研究能更加準確地確定運動模型，使定位精度得到較好的提高。

圖3 定位誤差隨信標節(jié)點密度變化曲線

圖4為定位誤差隨速度變化曲線。當節(jié)點的運動速度為2 m/s時，MCL，MCMLA和ATPLA的定位誤差率分別為0.76，0.62和0.5；ATPLA的定位誤差率相比前兩者分別降低0.34和0.19。隨著節(jié)點運動速度增大，拓撲結(jié)構(gòu)變化頻繁，定位的準確度受到影響。此外，MCL是以一跳通信半徑R和二跳通信半徑2R為過濾條件的，當節(jié)點的運動速度增大至2R時，采樣粒子數(shù)量不夠，容易造成死循環(huán)；而該算法是基于自身位置實時可知的信標節(jié)點構(gòu)建的運動模型，具有自適應(yīng)性，所得的運動模型更加準確，能在速度較大的情況下獲得較好的定位精度。

圖4 定位誤差隨速度變化曲線

4 結(jié)束語

針對海上環(huán)境中節(jié)點隨著海浪運動的應(yīng)用場景，根據(jù)信標節(jié)點的運動情況構(gòu)建符合該海域所有節(jié)點的運動模型，結(jié)合節(jié)點的歷史運動軌跡預(yù)測未知節(jié)點可能的位置；考慮海浪遮蔽效應(yīng)的影響，設(shè)定蒙特卡羅方法定位時的采樣區(qū)域和權(quán)值；以一跳和二跳信標節(jié)點為過濾條件，提高樣本的有效性和動態(tài)網(wǎng)絡(luò)的定位精度。該模型能克服采用MCL定位時采樣容易陷入死循環(huán)的缺點，更符合海上環(huán)境的應(yīng)用。仿真結(jié)果表明：當信標節(jié)點密度低、節(jié)點運動速度高時，所提定位算法的定位效果好于以往的定位算法，能很好地適應(yīng)海上節(jié)點的高度動態(tài)性，實時獲取精確的位置信息，提高救援成功率，減少生命財產(chǎn)損失。

[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)；上海市科學技術(shù)委員會基金(12ZR1412500)；上海市教委科研創(chuàng)新基金(13ZZ124)；上海市教育委員會和上海市教育發(fā)展基金會“曙光計劃”基金(12SG40)；交通運輸部應(yīng)用基礎(chǔ)研究項目(2013329810300)

郭世俊(1990—),男,湖北潛江人,碩士生,從事無線傳感網(wǎng)研究。E-mail:guoshijun1990@126.com 吳華鋒(1976—)，男，福建浦城人，教授，從事交通信息、無線傳感網(wǎng)研究。E-mail:hfwu@shmtu.edu.cn

1000-4653(2016)02-0001-05