胡 鋼 ,張 瑞,劉宴佳
(1.河海大學(xué)計(jì)算機(jī)與信息學(xué)院(常州),江蘇 常州 213022;2.常州市傳感網(wǎng)與環(huán)境感知重點(diǎn)實(shí)驗(yàn)室,江蘇常州 213022)
無線傳感器網(wǎng)絡(luò)(WSN)是信息科學(xué)領(lǐng)域中一個(gè)全新發(fā)展方向,它融合了微處理器、智能傳感器與通信技術(shù),使得傳感器節(jié)點(diǎn)成為集感知信息、交換信息、協(xié)調(diào)控制等功能于一體的有機(jī)結(jié)合體,被認(rèn)為是下一代互聯(lián)網(wǎng)的重要組成部分。根據(jù)應(yīng)用環(huán)境的不同,無線傳感器網(wǎng)絡(luò)又可分為地面?zhèn)鞲芯W(wǎng)、地下傳感網(wǎng)以及水下傳感網(wǎng)。近年來,隨著各國政府對(duì)海洋開發(fā)的重視,水下傳感網(wǎng)進(jìn)步飛速,現(xiàn)在它已經(jīng)廣泛應(yīng)用于海洋數(shù)據(jù)采集、污染檢測(cè)、海上探測(cè)、災(zāi)難預(yù)警、救援打撈和軍事監(jiān)測(cè)等方面[1]。
在大多數(shù)應(yīng)用中,如何快速有效地對(duì)目標(biāo)節(jié)點(diǎn)的物理位置進(jìn)行定位,是國內(nèi)外許多研究機(jī)構(gòu)和學(xué)者所共同探討的問題[2]。在水下救援打撈等領(lǐng)域,則需要對(duì)移動(dòng)的目標(biāo)節(jié)點(diǎn)進(jìn)行定位,對(duì)定位精度也提出了更高的要求,這就給水下傳感網(wǎng)的定位算法設(shè)計(jì)帶來了挑戰(zhàn)。目前,針對(duì)水下傳感網(wǎng)移動(dòng)節(jié)點(diǎn)定位的研究并不多,本文首先分析了現(xiàn)有的定位算法及在水下定位中的優(yōu)劣,然后針對(duì)水下傳感網(wǎng)的特性,提出了一種基于Chan算法改進(jìn)的M-Chan算法,它通過曲線擬合進(jìn)行運(yùn)動(dòng)軌跡預(yù)測(cè),利用節(jié)點(diǎn)移動(dòng)特性修正估計(jì)位置,從而使節(jié)點(diǎn)定位達(dá)到較高的精度,并進(jìn)行了仿真與誤差分析。
常見的節(jié)點(diǎn)定位算法,根據(jù)定位過程中是否需要測(cè)量節(jié)點(diǎn)間的距離,分為基于測(cè)距的算法和無需測(cè)距的算法兩類。無需測(cè)距的算法主要通過節(jié)點(diǎn)之間的連通性實(shí)現(xiàn)節(jié)點(diǎn)定位;基于測(cè)距的算法依賴額外硬件測(cè)量節(jié)點(diǎn)間的距離信息,如接收信號(hào)強(qiáng)度(RSSI)、信號(hào)的到達(dá)時(shí)間(TOA)、不同信號(hào)的到達(dá)時(shí)間差(TDOA)以及信號(hào)的到達(dá)角度(AOA)。該類算法需要額外器件,增加了節(jié)點(diǎn)成本和功耗,但與無需測(cè)距的算法相比,定位精度更高[3]。而在水下環(huán)境中,溫度、障礙物、傳播模式等條件都是不斷變化的,現(xiàn)有的傳播衰減模型又不精確,故測(cè)量接收信號(hào)強(qiáng)度(RSSI)存在困難,精度受限[4]?;诘竭_(dá)時(shí)間差(TDOA)的算法不需要復(fù)雜的測(cè)距設(shè)備,定位精度較高,在水下傳感網(wǎng)定位中最為適用。
水下傳感器網(wǎng)絡(luò)主要依賴聲波進(jìn)行通信,聲波的傳播速率比電磁波小幾個(gè)數(shù)量級(jí),通信過程中的傳播延遲較大。如果目標(biāo)節(jié)點(diǎn)移動(dòng)速度很快,那么在定位信號(hào)從目標(biāo)節(jié)點(diǎn)到錨節(jié)點(diǎn)的傳播時(shí)間內(nèi),目標(biāo)節(jié)點(diǎn)的位移較大,從而使定位精度下降。目前學(xué)術(shù)界提出的一些動(dòng)態(tài)定位算法,如 DLS算法[5]、MSPF 算法[6]、MCL 算法[7]以及基于 MCL 的幾種改進(jìn)算法:如MCB算法[8],解決了MCL方法采樣效率低的問題;Dual-MCL、Mixture-MCL 算法[9]對(duì)預(yù)測(cè)和濾波階段進(jìn)行了改進(jìn)等,這些算法并沒有一項(xiàng)是特別針對(duì)水下傳感網(wǎng)中錨節(jié)點(diǎn)多為靜止?fàn)顟B(tài)的情形設(shè)計(jì)的,也沒有考慮到水下傳感網(wǎng)的傳輸特性,而且它們多不基于測(cè)距,定位精度普遍不高。
常見的 TDOA定位算法包括 Chan算法[10]、Fang算法[11]、Taylor級(jí)數(shù)展開算法[12]等。Chan 算法是一種求解雙曲線方程組的非遞歸算法,算法首先用加權(quán)最小二乘法(WLS)得到一初始解,再用得到的估計(jì)位置坐標(biāo)及附加變量等約束條件進(jìn)行二次WLS估計(jì),最后得到改進(jìn)的位置估計(jì)。該算法計(jì)算量小,并且經(jīng)仿真表明,Chan算法具有更精確的代數(shù)解。
圖1 移動(dòng)節(jié)點(diǎn)定位示意圖
令未知矢量Za=[1]T,其中 Zp=[x y]T,有TDOA噪聲的誤差矢量:
其中
式中(xy)為移動(dòng)目標(biāo)的待估計(jì)位置,(Xi Yi)為第i個(gè)錨節(jié)點(diǎn)的已知位置,Ri,1為第i個(gè)錨節(jié)點(diǎn)相對(duì)于第一個(gè)錨節(jié)點(diǎn)的距離差,則將測(cè)得的Ri,1代入,經(jīng)過一次WLS求解該方程得:
將Za的元素表示為:
其中e1,e2,e3為Z的估計(jì)誤差,Z的前兩個(gè)元素減去X1,Y1,再對(duì)各元素求平方可得Za的誤差矢量:
其中
可得Z'a的ML估計(jì)為:
最終移動(dòng)目標(biāo)的定位估計(jì)位置為:
Chan算法的性能主要受非視距傳播NLOS的影響,水下信道可認(rèn)為是視距信道,因此Chan算法較適用于水下傳感網(wǎng)的定位應(yīng)用。但由于它是針對(duì)靜態(tài)網(wǎng)絡(luò)提出的算法,沒有考慮到節(jié)點(diǎn)的移動(dòng)性;當(dāng)節(jié)點(diǎn)運(yùn)動(dòng)速度較快時(shí),水下較高的信號(hào)傳播延遲將會(huì)帶來不小的定位誤差。
曲線擬合是用連續(xù)曲線逼近平面上離散坐標(biāo)之間函數(shù)關(guān)系的一種數(shù)據(jù)處理方法。實(shí)際計(jì)算中通過觀測(cè)得到一系列坐標(biāo)Si(xi,yi)(i=1,2,3,…,n),用相應(yīng)的解析表達(dá)式y(tǒng)=f(xi)來反映坐標(biāo)變量之間的依賴關(guān)系,就可以在一定意義下最佳逼近已知數(shù)據(jù),反映其變化趨勢(shì)。其中f(xi)常稱作擬合函數(shù),當(dāng)f(xi)為多項(xiàng)式時(shí)又稱多項(xiàng)式擬合,求解f(xi)時(shí)應(yīng)滿足:
式(7)稱為曲線擬合的最小二乘條件,由多元函數(shù)求極值的必要條件,得
水下傳感網(wǎng)進(jìn)行TDOA定位時(shí),錨節(jié)點(diǎn)可隨機(jī)布置在水面某區(qū)域,配有GPS設(shè)備以確定自己的位置坐標(biāo),目標(biāo)節(jié)點(diǎn)在水下運(yùn)動(dòng)并周期性地向錨節(jié)點(diǎn)發(fā)送定位信號(hào)。錨節(jié)點(diǎn)通過全向換能器接收水下節(jié)點(diǎn)的信號(hào)并計(jì)算到達(dá)時(shí)間差,錨節(jié)點(diǎn)之間需要時(shí)間同步,而目標(biāo)節(jié)點(diǎn)只需保證自己的時(shí)鐘穩(wěn)定。在定位過程中,目標(biāo)節(jié)點(diǎn)是移動(dòng)的,假設(shè)其運(yùn)動(dòng)方向不確定,但是知道在當(dāng)前時(shí)刻的運(yùn)動(dòng)速度Vi,如果mi是待定位節(jié)點(diǎn)在當(dāng)前時(shí)刻的估計(jì)位置,那么該節(jié)點(diǎn)在經(jīng)過Δt時(shí)刻后的可能位置就近似在以mi為圓心、VΔt為半徑的圓上。本文提出的M-Chan算法正是利用節(jié)點(diǎn)的這種移動(dòng)特性和曲線擬合方法對(duì)傳統(tǒng)的Chan算法進(jìn)行了改進(jìn),算法的基本流程如下:
(1)初始化階段
本算法假設(shè)目標(biāo)節(jié)點(diǎn)在水下某二維平面上隨機(jī)運(yùn)動(dòng)(三維情況可由二維拓展坐標(biāo)系得到,由于原理相同,故本文不再推導(dǎo)),錨節(jié)點(diǎn)隨機(jī)布置在水面上的某區(qū)域內(nèi),目標(biāo)節(jié)點(diǎn)周期性地發(fā)送定位信號(hào),假定周期為T,稱每次發(fā)送信號(hào)的時(shí)刻為采樣時(shí)刻。當(dāng)目標(biāo)節(jié)點(diǎn)進(jìn)入錨節(jié)點(diǎn)定位區(qū)域時(shí),首先節(jié)點(diǎn)根據(jù)傳統(tǒng)Chan算法估計(jì)自己前3個(gè)采樣時(shí)刻的位置坐標(biāo)mi=(xi,yi)(i=1,2,3),并存放在一個(gè)擬合數(shù)據(jù)隊(duì)列S=(m1,m2,m3)中,然后對(duì)擬合隊(duì)列中的坐標(biāo)數(shù)據(jù)進(jìn)行多項(xiàng)式擬合,計(jì)算出該節(jié)點(diǎn)運(yùn)動(dòng)軌跡的曲線參數(shù),從而預(yù)測(cè)出移動(dòng)節(jié)點(diǎn)的初始運(yùn)動(dòng)曲線fn(xi)。雖然前3個(gè)時(shí)刻的定位沒有考慮聲波的傳播時(shí)延,但它們擬合出的節(jié)點(diǎn)運(yùn)動(dòng)曲線是可信的。
(2)定位階段
從第3個(gè)采樣時(shí)刻起,利用節(jié)點(diǎn)的移動(dòng)性對(duì)估計(jì)位置進(jìn)行修正。Chan算法得到的估計(jì)位置沒有考慮聲波從目標(biāo)節(jié)點(diǎn)到錨節(jié)點(diǎn)的傳播延遲Δt,那么節(jié)點(diǎn)的實(shí)際坐標(biāo)應(yīng)是在此基礎(chǔ)上位移Δt時(shí)間后的新位置。系統(tǒng)發(fā)起定位計(jì)算的時(shí)刻為收集到足夠的TDOA測(cè)量值時(shí),此時(shí)的Δt等于聲波從目標(biāo)節(jié)點(diǎn)傳播到其通信半徑內(nèi)最遠(yuǎn)的錨節(jié)點(diǎn)所用時(shí)間,為簡化計(jì)算,用通信半徑代替這個(gè)距離,從圖2中可以看出,當(dāng)錨節(jié)點(diǎn)密度較大時(shí),目標(biāo)節(jié)點(diǎn)到最遠(yuǎn)可定位錨節(jié)點(diǎn)的距離無限接近于通信半徑。那么此時(shí)傳播延遲Δt=R/c,其中R為通信半徑,c為聲波在水下的傳播速度。
圖2 不同密度下最遠(yuǎn)可定位錨節(jié)點(diǎn)距離示意圖
假設(shè)前三次采樣時(shí)刻分別為t1,t2,t3,函數(shù)h(ti)為ti上的函數(shù)值,那么根據(jù)牛頓插值多項(xiàng)式,可以利用前3個(gè)時(shí)刻的xi=h(ti)來預(yù)測(cè)t時(shí)刻的,公式如下:
其中
由式(9)可以求得目標(biāo)節(jié)點(diǎn)在t3時(shí)刻x軸方向上的速度為
同理可求得y軸方向上的速度vy,可知目標(biāo)節(jié)點(diǎn)在t3時(shí)刻的運(yùn)動(dòng)速度為
此時(shí)由于運(yùn)動(dòng)的連續(xù)性,以t3時(shí)刻的Chan算法估計(jì)坐標(biāo)為圓心,v*Δt為半徑作圓,將此圓方程與擬合曲線函數(shù)f(xi)聯(lián)立,得方程組
求解方程組(15),取其根中與上一時(shí)刻估計(jì)位置歐氏距離較遠(yuǎn)的一個(gè)作為t3時(shí)刻的估計(jì)位置,并將其寫入擬合隊(duì)列,替換掉原有的t3時(shí)刻估計(jì)坐標(biāo)。如果所求方程組無解,則定位失敗,直接采用Chan算法估計(jì)坐標(biāo)作為節(jié)點(diǎn)的最終估計(jì)位置。
(3)擬合階段
當(dāng)移動(dòng)節(jié)點(diǎn)在新的采樣時(shí)刻產(chǎn)生定位信號(hào)時(shí),通過Chan算法首先計(jì)算出該時(shí)刻的一個(gè)初始位置,將其添加到擬合隊(duì)列的末尾,如果隊(duì)列長度超過3,則丟棄隊(duì)列第1項(xiàng),以保證隊(duì)列中保存的節(jié)點(diǎn)位置坐標(biāo)是不斷更新的。此時(shí)對(duì)擬合隊(duì)列進(jìn)行多項(xiàng)式擬合,即可得到節(jié)點(diǎn)當(dāng)前預(yù)測(cè)運(yùn)動(dòng)曲線f(x)。然后重復(fù)定位階段,計(jì)算出當(dāng)前時(shí)刻的估計(jì)坐標(biāo),并將其寫入擬合隊(duì)列替換掉原當(dāng)前時(shí)刻的估計(jì)位置。對(duì)于多項(xiàng)式曲線的擬合,要提高擬合精度和效果,就需要提高曲線階數(shù),而階次太高又帶來計(jì)算上的復(fù)雜性及其他方面的不利,故在實(shí)際應(yīng)用中一般取不超過6的整數(shù)值[14]。
本文為了檢驗(yàn)M-Chan算法的性能,用Matlab對(duì)M-Chan算法與傳統(tǒng)Chan算法進(jìn)行了仿真對(duì)比分析。仿真中,為了使結(jié)果更加接近真實(shí),在邊長L=1000 m的正方形區(qū)域內(nèi)隨機(jī)布置M=200個(gè)錨節(jié)點(diǎn),錨節(jié)點(diǎn)的部署服從均勻分布。另布設(shè)一單目標(biāo)節(jié)點(diǎn),所有節(jié)點(diǎn)的通信半徑R=200 m,聲速取c=1 200 m/s,目標(biāo)節(jié)點(diǎn)采用隨機(jī)Waypoint移動(dòng)模型,平均移動(dòng)速度va=15 m/s,且認(rèn)為節(jié)點(diǎn)在二維平面上運(yùn)動(dòng)。假定算法中錨節(jié)點(diǎn)之間是時(shí)間同步的,TDOA的測(cè)量誤差的分布服從均值為0,方差為σ2=1的高斯分布[15],圖3即為一次仿真的定位結(jié)果示意圖。
圖3 移動(dòng)節(jié)點(diǎn)定位仿真示意圖
文中的平均定位誤差為節(jié)點(diǎn)所有定位時(shí)刻的定位誤差取均值,采用節(jié)點(diǎn)的估計(jì)位置和實(shí)際位置之間的歐氏距離來表示,擬合數(shù)據(jù)隊(duì)列的長度為3,擬合多項(xiàng)式的階數(shù)k=2。所有的仿真結(jié)果均為通過對(duì)20次獨(dú)立仿真結(jié)果取均值獲得。下面從幾個(gè)方面分析該定位算法的定位性能:
(1)節(jié)點(diǎn)移動(dòng)速度:
圖4是節(jié)點(diǎn)移動(dòng)速度對(duì)平均定位誤差的影響。仿真結(jié)果顯示,隨著移動(dòng)速度的增加,Chan算法的定位精度逐漸降低,因?yàn)楣?jié)點(diǎn)速度增大使目標(biāo)節(jié)點(diǎn)在定位信號(hào)的傳播過程中移動(dòng)更遠(yuǎn)的位置,從而使誤差相應(yīng)增大;而M-Chan算法則基本不受節(jié)點(diǎn)移動(dòng)速度的影響,定位誤差較為穩(wěn)定,節(jié)點(diǎn)速度快時(shí),性能較原算法有較大提高,當(dāng)節(jié)點(diǎn)平均移動(dòng)速度為27 m/s時(shí),精度可提高8.87%。
圖4 節(jié)點(diǎn)平均移動(dòng)速度與定位誤差
(2)通信半徑
圖5是隨通信半徑的變化,平均定位誤差的變化曲線圖。通常意義上,節(jié)點(diǎn)通信半徑的增大可以使采樣時(shí)刻接收到定位信號(hào)的錨節(jié)點(diǎn)數(shù)量增多,從而增加雙曲線方程組的方程個(gè)數(shù),使定位精度提高。但在實(shí)際仿真中,平均定位誤差在通信半徑增大時(shí)逐漸增高,表明定位性能不升反降。經(jīng)分析仿真過程認(rèn)為,造成這種現(xiàn)象的原因是當(dāng)目標(biāo)節(jié)點(diǎn)在錨節(jié)點(diǎn)區(qū)域外運(yùn)動(dòng)時(shí),由于通信半徑的增加,能夠接收到定位信息的錨節(jié)點(diǎn)數(shù)量也隨之增加,這就使得之前不能被定位的點(diǎn)變?yōu)榭啥ㄎ稽c(diǎn),如圖3中虛線框所示的定位點(diǎn)。這些點(diǎn)能夠利用的錨節(jié)點(diǎn)有限,定位誤差較大,所以總體定位誤差隨之增高。但誤差大總要優(yōu)于不能定位的結(jié)果,因此綜合來看,總體定位性能還是隨通信半徑增大而提高的。對(duì)M-Chan算法來說,通信半徑的增大意味著其不再近似等于目標(biāo)節(jié)點(diǎn)距最遠(yuǎn)可定位錨節(jié)點(diǎn)的距離,這增加了計(jì)算信號(hào)傳播時(shí)延的誤差,使總體誤差增大。節(jié)點(diǎn)通信半徑為550m時(shí),較原算法約提高精度8.59%。
圖5 節(jié)點(diǎn)通信半徑與定位誤差
(3)錨節(jié)點(diǎn)密度
仿真中的錨節(jié)點(diǎn)密度通過1 000 m×1 000 m區(qū)域內(nèi)的錨節(jié)點(diǎn)個(gè)數(shù)來表示,從圖6可以看出,增加錨節(jié)點(diǎn)密度可以有效提高定位精度,當(dāng)錨節(jié)點(diǎn)密度達(dá)到某一閾值后,兩種算法的平均定位誤差均趨于穩(wěn)定。這是因?yàn)榉抡嬷?,考慮到計(jì)算復(fù)雜度,Chan算法只取最多7個(gè)錨節(jié)點(diǎn)進(jìn)行定位計(jì)算,錨節(jié)點(diǎn)密度達(dá)到一定程度時(shí),每定位時(shí)刻可定位錨節(jié)點(diǎn)數(shù)量飽和,故定位誤差趨于一穩(wěn)定值。M-Chan算法在錨節(jié)點(diǎn)密度較大時(shí)性能較原算法有所提升,在每106m2布置450個(gè)錨節(jié)點(diǎn)的情況下,精度可提高8.01%。
圖6 錨節(jié)點(diǎn)密度與定位誤差
本文針對(duì)水下傳感網(wǎng)中研究較少的移動(dòng)節(jié)點(diǎn)定位,提出了一種改進(jìn)M-Chan算法。該算法通過曲線擬合進(jìn)行運(yùn)動(dòng)軌跡預(yù)測(cè),利用節(jié)點(diǎn)移動(dòng)特性修正估計(jì)位置,從而提高了移動(dòng)節(jié)點(diǎn)的定位精度。最后對(duì)照傳統(tǒng)Chan定位算法,從節(jié)點(diǎn)移動(dòng)速度、通信半徑、錨節(jié)點(diǎn)密度等不同方面進(jìn)行了仿真比較,對(duì)比了兩種算法的平均定位誤差。仿真結(jié)果表明,M-Chan算法的定位性能提高約5% ~10%,尤其當(dāng)節(jié)點(diǎn)高速移動(dòng)時(shí),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é)點(diǎn)自定位算法的研究[J].傳感技術(shù)學(xué)報(bào),2007,6(20):1381-1385.
[3]張正勇,梅順良.無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)自定位技術(shù)[J].計(jì)算機(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)合粒子濾波的移動(dòng)節(jié)點(diǎn)定位算法[J].傳感技術(shù)學(xué)報(bào),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ò)移動(dòng)節(jié)點(diǎn)定位算法研究[J].傳感技術(shù)學(xué)報(bào),2010,4(23):562-566.
[14]焦竹青,熊偉麗,張林,等.基于曲線擬合的無線傳感器網(wǎng)絡(luò)目標(biāo)定位算法[J].東南大學(xué)學(xué)報(bào)(自然科學(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.