胡 鋼 ，張 瑞，劉宴佳

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

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

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

1 相關(guān)算法分析

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

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

2 Chan算法原理

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

圖1 移動節(jié)點定位示意圖

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

其中

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

將Za的元素表示為:

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

其中

可得Z'a的ML估計為:

最終移動目標(biāo)的定位估計位置為:

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

3 改進的M-Chan算法

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

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

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

(1)初始化階段

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

(2)定位階段

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

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

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

其中

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

同理可求得y軸方向上的速度vy，可知目標(biāo)節(jié)點在t3時刻的運動速度為

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

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

(3)擬合階段

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

4 仿真分析

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

圖3 移動節(jié)點定位仿真示意圖

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

(1)節(jié)點移動速度:

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

圖4 節(jié)點平均移動速度與定位誤差

(2)通信半徑

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

圖5 節(jié)點通信半徑與定位誤差

(3)錨節(jié)點密度

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

圖6 錨節(jié)點密度與定位誤差

5 總結(jié)

本文針對水下傳感網(wǎng)中研究較少的移動節(jié)點定位，提出了一種改進M-Chan算法。該算法通過曲線擬合進行運動軌跡預(yù)測，利用節(jié)點移動特性修正估計位置，從而提高了移動節(jié)點的定位精度。最后對照傳統(tǒng)Chan定位算法，從節(jié)點移動速度、通信半徑、錨節(jié)點密度等不同方面進行了仿真比較，對比了兩種算法的平均定位誤差。仿真結(jié)果表明，M-Chan算法的定位性能提高約5% ～10%，尤其當(dāng)節(jié)點高速移動時，M-Chan算法明顯優(yōu)于傳統(tǒng)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］江冰，吳元忠，謝冬梅.無線傳感器網(wǎng)絡(luò)節(jié)點自定位算法的研究［J］.傳感技術(shù)學(xué)報，2007，6(20):1381－1385.

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

［4］孫利民，李建中，陳渝，等.無線傳感器網(wǎng)絡(luò)［M］.北京:清華大學(xué)出版社，2005.

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

［6］羅海勇，李錦濤，趙方.基于均值漂移和聯(lián)合粒子濾波的移動節(jié)點定位算法［J］.傳感技術(shù)學(xué)報，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］黃梅根，常新峰.一種基于蒙特卡羅法的無線傳感器網(wǎng)絡(luò)移動節(jié)點定位算法研究［J］.傳感技術(shù)學(xué)報，2010，4(23):562－566.

［14］焦竹青，熊偉麗，張林，等.基于曲線擬合的無線傳感器網(wǎng)絡(luò)目標(biāo)定位算法［J］.東南大學(xué)學(xué)報(自然科學(xué)版)，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.