水下傳感器網絡移動節點定位問題研究*

胡 鋼 ，張 瑞，劉宴佳

(1.河海大學計算機與信息學院(常州)，江蘇 常州 213022；2.常州市傳感網與環境感知重點實驗室，江蘇常州 213022)

無線傳感器網絡(WSN)是信息科學領域中一個全新發展方向，它融合了微處理器、智能傳感器與通信技術，使得傳感器節點成為集感知信息、交換信息、協調控制等功能于一體的有機結合體，被認為是下一代互聯網的重要組成部分。根據應用環境的不同，無線傳感器網絡又可分為地面傳感網、地下傳感網以及水下傳感網。近年來，隨著各國政府對海洋開發的重視，水下傳感網進步飛速，現在它已經廣泛應用于海洋數據采集、污染檢測、海上探測、災難預警、救援打撈和軍事監測等方面［1］。

在大多數應用中，如何快速有效地對目標節點的物理位置進行定位，是國內外許多研究機構和學者所共同探討的問題［2］。在水下救援打撈等領域，則需要對移動的目標節點進行定位，對定位精度也提出了更高的要求，這就給水下傳感網的定位算法設計帶來了挑戰。目前，針對水下傳感網移動節點定位的研究并不多，本文首先分析了現有的定位算法及在水下定位中的優劣，然后針對水下傳感網的特性，提出了一種基于Chan算法改進的M-Chan算法，它通過曲線擬合進行運動軌跡預測，利用節點移動特性修正估計位置，從而使節點定位達到較高的精度，并進行了仿真與誤差分析。

1 相關算法分析

常見的節點定位算法，根據定位過程中是否需要測量節點間的距離，分為基于測距的算法和無需測距的算法兩類。無需測距的算法主要通過節點之間的連通性實現節點定位；基于測距的算法依賴額外硬件測量節點間的距離信息，如接收信號強度(RSSI)、信號的到達時間(TOA)、不同信號的到達時間差(TDOA)以及信號的到達角度(AOA)。該類算法需要額外器件，增加了節點成本和功耗，但與無需測距的算法相比，定位精度更高［3］。而在水下環境中，溫度、障礙物、傳播模式等條件都是不斷變化的，現有的傳播衰減模型又不精確，故測量接收信號強度(RSSI)存在困難，精度受限［4］。基于到達時間差(TDOA)的算法不需要復雜的測距設備，定位精度較高，在水下傳感網定位中最為適用。

水下傳感器網絡主要依賴聲波進行通信，聲波的傳播速率比電磁波小幾個數量級，通信過程中的傳播延遲較大。如果目標節點移動速度很快，那么在定位信號從目標節點到錨節點的傳播時間內，目標節點的位移較大，從而使定位精度下降。目前學術界提出的一些動態定位算法，如 DLS算法［5］、MSPF 算法［6］、MCL 算法［7］以及基于 MCL 的幾種改進算法:如MCB算法［8］，解決了MCL方法采樣效率低的問題；Dual-MCL、Mixture-MCL 算法［9］對預測和濾波階段進行了改進等，這些算法并沒有一項是特別針對水下傳感網中錨節點多為靜止狀態的情形設計的，也沒有考慮到水下傳感網的傳輸特性，而且它們多不基于測距，定位精度普遍不高。

2 Chan算法原理

常見的 TDOA定位算法包括 Chan算法［10］、Fang算法［11］、Taylor級數展開算法［12］等。Chan 算法是一種求解雙曲線方程組的非遞歸算法，算法首先用加權最小二乘法(WLS)得到一初始解，再用得到的估計位置坐標及附加變量等約束條件進行二次WLS估計，最后得到改進的位置估計。該算法計算量小，并且經仿真表明，Chan算法具有更精確的代數解。

圖1 移動節點定位示意圖

令未知矢量Za=［1］T，其中 Zp=［x y］T，有TDOA噪聲的誤差矢量:

其中

式中(xy)為移動目標的待估計位置，(Xi Yi)為第i個錨節點的已知位置，Ri，1為第i個錨節點相對于第一個錨節點的距離差，則將測得的Ri，1代入，經過一次WLS求解該方程得:

將Za的元素表示為:

其中e1，e2，e3為Z的估計誤差，Z的前兩個元素減去X1，Y1，再對各元素求平方可得Za的誤差矢量:

其中

可得Z'a的ML估計為:

最終移動目標的定位估計位置為:

Chan算法的性能主要受非視距傳播NLOS的影響，水下信道可認為是視距信道，因此Chan算法較適用于水下傳感網的定位應用。但由于它是針對靜態網絡提出的算法，沒有考慮到節點的移動性；當節點運動速度較快時，水下較高的信號傳播延遲將會帶來不小的定位誤差。

3 改進的M-Chan算法

曲線擬合是用連續曲線逼近平面上離散坐標之間函數關系的一種數據處理方法。實際計算中通過觀測得到一系列坐標Si(xi，yi)(i=1，2，3，…，n)，用相應的解析表達式y=f(xi)來反映坐標變量之間的依賴關系，就可以在一定意義下最佳逼近已知數據，反映其變化趨勢。其中f(xi)常稱作擬合函數，當f(xi)為多項式時又稱多項式擬合，求解f(xi)時應滿足:

式(7)稱為曲線擬合的最小二乘條件，由多元函數求極值的必要條件，得

水下傳感網進行TDOA定位時，錨節點可隨機布置在水面某區域，配有GPS設備以確定自己的位置坐標，目標節點在水下運動并周期性地向錨節點發送定位信號。錨節點通過全向換能器接收水下節點的信號并計算到達時間差，錨節點之間需要時間同步，而目標節點只需保證自己的時鐘穩定。在定位過程中，目標節點是移動的，假設其運動方向不確定，但是知道在當前時刻的運動速度Vi，如果mi是待定位節點在當前時刻的估計位置，那么該節點在經過Δt時刻后的可能位置就近似在以mi為圓心、VΔt為半徑的圓上。本文提出的M-Chan算法正是利用節點的這種移動特性和曲線擬合方法對傳統的Chan算法進行了改進，算法的基本流程如下:

(1)初始化階段

本算法假設目標節點在水下某二維平面上隨機運動(三維情況可由二維拓展坐標系得到，由于原理相同，故本文不再推導)，錨節點隨機布置在水面上的某區域內，目標節點周期性地發送定位信號，假定周期為T，稱每次發送信號的時刻為采樣時刻。當目標節點進入錨節點定位區域時，首先節點根據傳統Chan算法估計自己前3個采樣時刻的位置坐標mi=(xi，yi)(i=1，2，3)，并存放在一個擬合數據隊列S=(m1，m2，m3)中，然后對擬合隊列中的坐標數據進行多項式擬合，計算出該節點運動軌跡的曲線參數，從而預測出移動節點的初始運動曲線fn(xi)。雖然前3個時刻的定位沒有考慮聲波的傳播時延，但它們擬合出的節點運動曲線是可信的。

(2)定位階段

從第3個采樣時刻起，利用節點的移動性對估計位置進行修正。Chan算法得到的估計位置沒有考慮聲波從目標節點到錨節點的傳播延遲Δt，那么節點的實際坐標應是在此基礎上位移Δt時間后的新位置。系統發起定位計算的時刻為收集到足夠的TDOA測量值時，此時的Δt等于聲波從目標節點傳播到其通信半徑內最遠的錨節點所用時間，為簡化計算，用通信半徑代替這個距離，從圖2中可以看出，當錨節點密度較大時，目標節點到最遠可定位錨節點的距離無限接近于通信半徑。那么此時傳播延遲Δt=R/c，其中R為通信半徑，c為聲波在水下的傳播速度。

圖2 不同密度下最遠可定位錨節點距離示意圖

假設前三次采樣時刻分別為t1，t2，t3，函數h(ti)為ti上的函數值，那么根據牛頓插值多項式，可以利用前3個時刻的xi=h(ti)來預測t時刻的，公式如下:

其中

由式(9)可以求得目標節點在t3時刻x軸方向上的速度為

同理可求得y軸方向上的速度vy，可知目標節點在t3時刻的運動速度為

此時由于運動的連續性，以t3時刻的Chan算法估計坐標為圓心，v*Δt為半徑作圓，將此圓方程與擬合曲線函數f(xi)聯立，得方程組

求解方程組(15)，取其根中與上一時刻估計位置歐氏距離較遠的一個作為t3時刻的估計位置，并將其寫入擬合隊列，替換掉原有的t3時刻估計坐標。如果所求方程組無解，則定位失敗，直接采用Chan算法估計坐標作為節點的最終估計位置。

(3)擬合階段

當移動節點在新的采樣時刻產生定位信號時，通過Chan算法首先計算出該時刻的一個初始位置，將其添加到擬合隊列的末尾，如果隊列長度超過3，則丟棄隊列第1項，以保證隊列中保存的節點位置坐標是不斷更新的。此時對擬合隊列進行多項式擬合，即可得到節點當前預測運動曲線f(x)。然后重復定位階段，計算出當前時刻的估計坐標，并將其寫入擬合隊列替換掉原當前時刻的估計位置。對于多項式曲線的擬合，要提高擬合精度和效果，就需要提高曲線階數，而階次太高又帶來計算上的復雜性及其他方面的不利，故在實際應用中一般取不超過6的整數值［14］。

4 仿真分析

本文為了檢驗M-Chan算法的性能，用Matlab對M-Chan算法與傳統Chan算法進行了仿真對比分析。仿真中，為了使結果更加接近真實，在邊長L=1000 m的正方形區域內隨機布置M=200個錨節點，錨節點的部署服從均勻分布。另布設一單目標節點，所有節點的通信半徑R=200 m，聲速取c=1 200 m/s，目標節點采用隨機Waypoint移動模型，平均移動速度va=15 m/s，且認為節點在二維平面上運動。假定算法中錨節點之間是時間同步的，TDOA的測量誤差的分布服從均值為0，方差為σ2=1的高斯分布［15］，圖3即為一次仿真的定位結果示意圖。

圖3 移動節點定位仿真示意圖

文中的平均定位誤差為節點所有定位時刻的定位誤差取均值，采用節點的估計位置和實際位置之間的歐氏距離來表示，擬合數據隊列的長度為3，擬合多項式的階數k=2。所有的仿真結果均為通過對20次獨立仿真結果取均值獲得。下面從幾個方面分析該定位算法的定位性能:

(1)節點移動速度:

圖4是節點移動速度對平均定位誤差的影響。仿真結果顯示，隨著移動速度的增加，Chan算法的定位精度逐漸降低，因為節點速度增大使目標節點在定位信號的傳播過程中移動更遠的位置，從而使誤差相應增大；而M-Chan算法則基本不受節點移動速度的影響，定位誤差較為穩定，節點速度快時，性能較原算法有較大提高，當節點平均移動速度為27 m/s時，精度可提高8.87%。

圖4 節點平均移動速度與定位誤差

(2)通信半徑

圖5是隨通信半徑的變化，平均定位誤差的變化曲線圖。通常意義上，節點通信半徑的增大可以使采樣時刻接收到定位信號的錨節點數量增多，從而增加雙曲線方程組的方程個數，使定位精度提高。但在實際仿真中，平均定位誤差在通信半徑增大時逐漸增高，表明定位性能不升反降。經分析仿真過程認為，造成這種現象的原因是當目標節點在錨節點區域外運動時，由于通信半徑的增加，能夠接收到定位信息的錨節點數量也隨之增加，這就使得之前不能被定位的點變為可定位點，如圖3中虛線框所示的定位點。這些點能夠利用的錨節點有限，定位誤差較大，所以總體定位誤差隨之增高。但誤差大總要優于不能定位的結果，因此綜合來看，總體定位性能還是隨通信半徑增大而提高的。對M-Chan算法來說，通信半徑的增大意味著其不再近似等于目標節點距最遠可定位錨節點的距離，這增加了計算信號傳播時延的誤差，使總體誤差增大。節點通信半徑為550m時，較原算法約提高精度8.59%。

圖5 節點通信半徑與定位誤差

(3)錨節點密度

仿真中的錨節點密度通過1 000 m×1 000 m區域內的錨節點個數來表示，從圖6可以看出，增加錨節點密度可以有效提高定位精度，當錨節點密度達到某一閾值后，兩種算法的平均定位誤差均趨于穩定。這是因為仿真中，考慮到計算復雜度，Chan算法只取最多7個錨節點進行定位計算，錨節點密度達到一定程度時，每定位時刻可定位錨節點數量飽和，故定位誤差趨于一穩定值。M-Chan算法在錨節點密度較大時性能較原算法有所提升，在每106m2布置450個錨節點的情況下，精度可提高8.01%。

圖6 錨節點密度與定位誤差

5 總結

本文針對水下傳感網中研究較少的移動節點定位，提出了一種改進M-Chan算法。該算法通過曲線擬合進行運動軌跡預測，利用節點移動特性修正估計位置，從而提高了移動節點的定位精度。最后對照傳統Chan定位算法，從節點移動速度、通信半徑、錨節點密度等不同方面進行了仿真比較，對比了兩種算法的平均定位誤差。仿真結果表明，M-Chan算法的定位性能提高約5% ～10%，尤其當節點高速移動時，M-Chan算法明顯優于傳統Chan算法。

［1］Akyitdiz I F，Pompiti D，Melodia T.Underwater Acoustic Sensor Networks:Research Challenges［J］.Ad Hoc Networks(Elsevier)，2005，3(3):257－279.

［2］江冰，吳元忠，謝冬梅.無線傳感器網絡節點自定位算法的研究［J］.傳感技術學報，2007，6(20):1381－1385.

［3］張正勇，梅順良.無線傳感器網絡節點自定位技術［J］.計算機工程，2007，33(17):4－6.

［4］孫利民，李建中，陳渝，等.無線傳感器網絡［M］.北京:清華大學出版社，2005.

［5］Chen Xun，Han Peng.A Viable Localization Scheme for Dynamic Wireless Sensor Networks［C］//Computer and Computational Sciences，First Interactional Multi-Symposiums.Volume 2，Apri 2006:587－593.

［6］羅海勇，李錦濤，趙方.基于均值漂移和聯合粒子濾波的移動節點定位算法［J］.傳感技術學報，2009，3(22):378－386.

［7］Hu L，Evans D.Localization for Mobile Sensor Networks［C］//Proceedings of the 10th Annual International Conference on Mobile Computing and Networking，2004:45－47.

［8］Aline Baggio，Koen Langendoen.Monte Carlo Localization for Mobile Wireless Sensor Networks［J］.Lecture Notes in Computer Science，2006，4325(11):317－328.

［9］Baggio A，Langendoen K.Monte Carlo Localization for Wireless Sensor Networks［C］//Proc of the 2nd Int’l Confon Mobile Ad-Hoc and Sensor Networks(MSN 2006).Hong Kong:Springer Verlag Press，2006:317－328.

［10］ChanY T，Ho K C.A Simple and Efficient Estimator for Hyperbolic Location［J］.IEEE Transactions on Signal Processing，1994，42(8):1905－1915.

［11］Fang B T.Simple Solutions for Hyperbolic and Related Position Fixes［J］.IEEE Trans.on Aerosp.Electron.Syst，1990，26:748－753.

［12］Foy W.Position-Location Solutions by Taylor Series Estimation［J］.IEEE Trans.Aerosp.Electron.Syst，1976，AES－12(2):187－193.

［13］黃梅根，常新峰.一種基于蒙特卡羅法的無線傳感器網絡移動節點定位算法研究［J］.傳感技術學報，2010，4(23):562－566.

［14］焦竹青，熊偉麗，張林，等.基于曲線擬合的無線傳感器網絡目標定位算法［J］.東南大學學報(自然科學版)，2008，91(38):249－252.

［15］Li Cong，Zhuang Wei-hua.Non-Line-of-Sight Error Mitigation in TDOA mobile location［C］//IEEE Global Telecommunications Conference，San Antonio TX USA，Nov 2001:680－684.