基于非對稱往返測距的海洋無線傳感網(wǎng)絡(luò)節(jié)點定位算法

覃玉華，劉浩然，鄧玉靜，王星淇，劉 彬，尹榮榮

(1.燕山大學(xué) 信息科學(xué)與工程學(xué)院，河北 秦皇島 066004；2.燕山大學(xué) 河北省特種光纖與光纖傳感重點實驗室，河北 秦皇島 066004)

1 引 言

獲取節(jié)點精確的位置是水下無線傳感網(wǎng)絡(luò)在環(huán)境監(jiān)測、災(zāi)難預(yù)報等方面應(yīng)用的前提，同時節(jié)點位置信息也是網(wǎng)絡(luò)拓?fù)淇刂?、覆蓋控制以及路由決策的重要依據(jù)。

水下節(jié)點定位算法可分為非測距的定位算法與基于測距的定位算法[1,2]。非測距的定位算法是根據(jù)網(wǎng)絡(luò)的連通性，節(jié)點間的路由跳數(shù)等信息估計節(jié)點位置，估計結(jié)果較為粗略，應(yīng)用范圍有限；基于測距的定位算法是根據(jù)測距技術(shù)測出節(jié)點間距離或是角度信息，運用定位策略完成定位工作。主要的測距技術(shù)分為4類：基于信號傳輸時間(TOA)[3]、基于信號到達(dá)時間差(TDOA)[4]、基于信號到達(dá)角度(AOA)[5]、基于接收信號強度(RSSI)[6]。實際應(yīng)用中基于測距定位算法的定位精度更高，應(yīng)用更為廣泛。

節(jié)點時間同步是影響定位的一大問題，雖然研究者們提出了許多節(jié)點間時間同步機制[7,8]，但對于大型水下無線傳感網(wǎng)絡(luò)節(jié)點時間同步，會增加計算復(fù)雜度與節(jié)點硬件要求，因此在定位中盡可能避免時間同步。研究還發(fā)現(xiàn)節(jié)點信號發(fā)射耗能是信號接收耗能的數(shù)10倍[9]，減少信息的發(fā)送有利于降低能耗。文獻(xiàn)[10]提出一種水下定位策略(under-water position scheme, UPS)，UPS算法利用3個水面浮標(biāo)節(jié)點與1個水下信標(biāo)節(jié)點并采用TDOA方式進(jìn)行測距，實現(xiàn)未知節(jié)點的定位。雖然UPS算法避免了時間同步，但是僅依靠4個參考節(jié)點進(jìn)行定位，覆蓋度不高且測距信息發(fā)送頻繁。在UPS算法的基礎(chǔ)上Cheng H等[11]提出一種大規(guī)模水下傳感器網(wǎng)絡(luò)定位方法(localization scheme for large scale, LSLS)，此方法運用UPS算法定位，將一些已定位的節(jié)點作為新的參考節(jié)點進(jìn)行迭代定位計算。LSLS算法改善了UPS算法中節(jié)點定位覆蓋度不高的缺陷，使其適用于大規(guī)模的水下網(wǎng)絡(luò)，但使用特定的海水聲速模型計算聲速，適用性不強，且需節(jié)點測量溫度、鹽度、壓力等數(shù)據(jù)。在未知節(jié)點已知其深度信息的前提下，文獻(xiàn)[12]提出一種基于投影理論的水下傳感器節(jié)點定位方法，該方法利用節(jié)點的深度信息將參考節(jié)點投影至未知節(jié)點所在平面，將水聲傳感器網(wǎng)絡(luò)三維定位問題轉(zhuǎn)化為二維定位問題。文獻(xiàn)[13]提出基于對稱往返測距的定位算法(sea web navigation, SWN)，該算法通過計算未知節(jié)點與鄰居參考節(jié)點間距離，并以距離圓的交點作為未知節(jié)點的位置，但定位過程中多次交換定位信息，能耗高。文獻(xiàn)[14]提出一種基于非對稱往返異步定位(asymmetrical round trip based synchronization-free localization, ARTL)算法，該算法通過信標(biāo)節(jié)點接收自己的數(shù)據(jù)包計算水下聲波速度，完成測距、定位任務(wù)；該算法僅用1個參考節(jié)點的聲波速度作為節(jié)點通信區(qū)域內(nèi)所有節(jié)點間的通信速度，無法實現(xiàn)高精度的定位。文獻(xiàn)[15]提出將加權(quán)最小二乘法以及抗差最小二乘法應(yīng)用于節(jié)點定位，但均只限于陸地環(huán)境。

針對上述存在的問題，本文提出了一種新的基于非對稱往返測距的海洋無線傳感網(wǎng)絡(luò)節(jié)點定位(localization method for marine wireless sensors networks based on asymmetric round-trip ranging, LMARR)算法，通過節(jié)點間非對稱的發(fā)送與接收測距信息，利用節(jié)點接發(fā)信息的時間差計算平均海水聲速，避免時間同步，完成節(jié)點間距離測定；利用得到的距離將各鄰居參考節(jié)點均投影到未知節(jié)點所在平面，用最小二乘法進(jìn)行定位計算，實現(xiàn)在低信息發(fā)送頻率的情況下，提升節(jié)點定位的精度。

2 基于非對稱往返測距的海洋無線傳感網(wǎng)絡(luò)節(jié)點定位算法

2.1 網(wǎng)絡(luò)結(jié)構(gòu)

通常海洋無線傳感網(wǎng)絡(luò)中包含兩類節(jié)點：參考節(jié)點與普通節(jié)點，其中參考節(jié)點包括浮標(biāo)節(jié)點與信標(biāo)節(jié)點，在定位過程中參考節(jié)點位置已知[16]。假定有N個普通節(jié)點，M個參考節(jié)點部署在100 m×100 m×100 m的海域，網(wǎng)絡(luò)結(jié)構(gòu)如圖1所示。浮標(biāo)節(jié)點漂浮在水面，在水面通過GPS獲取精確的節(jié)點位置。信標(biāo)節(jié)點與浮標(biāo)節(jié)點直接通信，使得信標(biāo)節(jié)點獲得位置估計。普通節(jié)點結(jié)構(gòu)簡單，分布廣泛，只能與其通信范圍內(nèi)的信標(biāo)節(jié)點以及普通節(jié)點通信，但難與浮標(biāo)節(jié)點直接通信獲取位置估計，所以將普通節(jié)點作為未知節(jié)點。本文主要是針對未知節(jié)點的定位進(jìn)行研究，定位中參考節(jié)點與未知節(jié)點都含各自的ID信息，并可通過壓力傳感器獲取深度信息。

圖1 網(wǎng)絡(luò)結(jié)構(gòu)Fig.1 Network structure

海下節(jié)點通信以聲波通信為主，海水聲波速度受到溫度、鹽度、壓力或深度等因素影響，聲速變化范圍在1 400～1 600 m/s之間，是一個隨時間空間變化的曲線[17]。Liu J等[18]描述的海水聲速曲線如圖2所示，前20 m聲速穩(wěn)定，海水繼續(xù)加深，聲速持續(xù)變化。海水聲速并不是一個穩(wěn)定值，因此在定位過程中不可忽略海水聲速變化的影響。

圖2 海水聲速變化曲線Fig.2 Curve of seawater sound velocity

2.2 非對稱往返測距算法

依據(jù)圖1的網(wǎng)絡(luò)結(jié)構(gòu)，對某一未知節(jié)點及其鄰居參考節(jié)點進(jìn)行分析，LMARR算法測距過程如圖3所示。假設(shè)圓形的未知節(jié)點A在通信范圍r內(nèi)有s(s≥3)個正方形的參考節(jié)點x1,x2,…,xm,…,xs。

圖3 LMARR算法測距過程Fig.3 LMARR algorithm distance measuring process

在未知節(jié)點A與s個參考節(jié)點的測距過程中，首先由xm在自身時鐘Txm1時刻發(fā)起測距工作。測距信號傳輸?shù)轿粗?jié)點A的時刻為TA1，由此可得：

TA1=Txm1+dxmA/v

(1)

式中：dxmA為參考節(jié)點xm與未知節(jié)點A間距離；v為未知節(jié)點與鄰居參考節(jié)點間的海水聲速。

未知節(jié)點A于TA2時刻向其通信范圍內(nèi)的s個參考節(jié)點發(fā)送相應(yīng)的測距信息，到達(dá)xm參考節(jié)點的時間為Txm3，到達(dá)其它參考節(jié)點的時間為Txi2，據(jù)此可得下列公式：

Txm3=TA2+dAxm/v(i≠m,i=[1,s])

(2)

Txi2=TA2+dxiA/v(i≠m,i=[1,s])

(3)

參考節(jié)點xm發(fā)送的測距信號被參考節(jié)點xi接收到的時刻為Txi1，參考節(jié)點xi在Txi3時刻向xm節(jié)點發(fā)送相應(yīng)信息，被參考節(jié)點xm接收到的時刻為Txim2，由此可得出下列公式：

(4)

(5)

公式(4)與公式(5)相加，化簡后得出以下公式：

(6)

由公式(6)，可求解出測距發(fā)起參考節(jié)點與其它參考節(jié)點間的聲波傳輸速度vi：

(7)

為了使節(jié)點不額外增加測量海水聲速的裝置，將未知節(jié)點A及其通信范圍內(nèi)的各參考節(jié)點間的聲波傳播速度的均值作為未知節(jié)點A發(fā)送與接收測距信息的聲波速度v：

(8-1)

(8-2)

將公式(1)與公式(2)相加，化簡后得到dAxm，將公式(8-2)代入公式(9)可計算得到未知節(jié)點A到定位發(fā)起參考節(jié)點xm間距離dAxm：

(9)

(10)

由公式(3)計算得未知節(jié)點A與其它鄰居參考節(jié)點的距離：

dAxi=(Txi2-TA2)v

=(Txi2-Txi1+Txi1-TA2)v

(11)

將公式(2)代入公式(11)中得到：

(12)

將公式(4)代入公式(12)中得到：

(13)

將公式(7)代入公式(13)中得到：

(14)

把公式(8)計算得到的海水聲速與由公式(10)的未知節(jié)點A與參考節(jié)點xm距離公式代入公式(14)，得到未知節(jié)點與其它參考節(jié)點間距離公式：

(15)

由公式(9)與公式(14)可以看出：未知節(jié)點與鄰居參考節(jié)點間距離不僅與節(jié)點測距信息接發(fā)的時間差有關(guān)，還與海水聲速有直接的關(guān)系，海水聲速的準(zhǔn)確性影響著最終距離測定的效果。由公式(10)與公式(15)可以看出：通過LMARR算法進(jìn)行節(jié)點間測距時，只需獲取(Txi2-Txi1),(Txm3-Txm1),(Txim2-Txm1),(Txi3-Txi1),(TA2-TA1)等各節(jié)點測距信息發(fā)送與接收的時間差，并不需要節(jié)點間時間同步以及對海水聲速的額外測定，而且計算公式復(fù)雜度低。從圖3的LMARR算法的測距過程示意圖中，很明顯地看出LMARR算法相對于常規(guī)的對稱往返測距算法，減少了s-1次測距信息的發(fā)送與接收。

2.3 LMARR定位算法

利用最小二乘法[19]對未知節(jié)點進(jìn)行定位計算。為減少計算量及降低計算難度，在運用非對稱往返測距算法測出各個未知節(jié)點與其通信范圍內(nèi)各參考節(jié)點的距離后,根據(jù)節(jié)點深度信息，將由上述方法得到的節(jié)點間的三維空間距離投影至未知節(jié)點所在平面，使其轉(zhuǎn)變?yōu)槎S的距離，再根據(jù)轉(zhuǎn)換得到的平面距離信息完成定位計算。此處最小二乘法定位算法的原理可表述為：當(dāng)已知n個參考節(jié)點位置信息(x1,y1),(x2,y2),…,(xn,yn)以及它們到待求的未知節(jié)點(x,y)的距離d1,d2,…,dn時，可列出非線性方程組：

(16)

為了簡便運算以快速獲取其解析解，需將公式(16)轉(zhuǎn)化為線性方程，使用公式(16)中前n-1個方程分別減去第n個方程，則可得到線性方程組：

(17)

公式(17)可表示為

AX=B

(18)

式中：

XTATAX-BTAX-XTATB+BTB

(19)

于是,可令公式(19)求導(dǎo)等于零:

(20)

2ATAX-2ATB=0

(21)

由公式(21)可得未知節(jié)點的估計位置坐標(biāo)：

X=(ATA)-1ATB

(22)

從公式(22)看出當(dāng)測量得到未知節(jié)點與鄰居參考節(jié)點的距離d1,d2,…,dn越準(zhǔn)確時，求解出未知節(jié)點的坐標(biāo)也越更精準(zhǔn)，但是從公式(17)也不難看出未知節(jié)點的估計位置坐標(biāo)的求解精度受限于公式(16)中的第n個方程的精度。

LMARR算法的步驟簡要地描述如下：

Step 1：節(jié)點部署完成后，各節(jié)點向周圍節(jié)點廣播包含節(jié)點ID，跳數(shù)的數(shù)據(jù)包明確節(jié)點間的鄰居關(guān)系。

Step 2：對未知節(jié)點及通信范圍內(nèi)的參考節(jié)點運用LMARR測距算法進(jìn)行相應(yīng)的測距工作時，首先由發(fā)起測距次數(shù)最少且ID序號小的參考節(jié)點發(fā)起測距工作，此參考節(jié)點在獲取其它各節(jié)點的接受與發(fā)送數(shù)據(jù)包的時間差以及深度信息后，通過公式(10)與公式(15)計算得出未知節(jié)點與其鄰居參考節(jié)點間的距離。

Step 3：由step 2中計算得到的距離，依據(jù)節(jié)點間的深度差，運用勾股定理，將三維距離信息投影到未知節(jié)點所在平面轉(zhuǎn)化成為二維的距離信息。

Step 4：參考節(jié)點依據(jù)上述步驟得到節(jié)點間距離信息，參考節(jié)點的位置信息運用最小二乘法，通過公式(21)完成對未知節(jié)點的定位計算，最后依據(jù)節(jié)點的深度信息輸出未知節(jié)點的三維坐標(biāo)。

Step 5：對剩余的未知節(jié)點逐個重復(fù)上述step 2至step 4，直至完成所有未知節(jié)點的定位。

該算法的測距方式比傳統(tǒng)的對稱往返測距方式減少了數(shù)據(jù)的發(fā)送次數(shù)，降低了能量消耗。運用鄰居參考節(jié)點間的平均聲波速度作為未知節(jié)點的聲波速度，減小海水聲速變化導(dǎo)致的誤差。由剩余能量較多且計算能力較強的參考節(jié)點發(fā)起測距工作，完成定位計算，能夠更好地均衡節(jié)點的能量使用，減少未知節(jié)點的能量消耗。

3 實驗仿真

本文在Windows7系統(tǒng)下使用MATLAB R2016a軟件進(jìn)行仿真實驗，實驗參數(shù)如表1所示。

根據(jù)圖2所述海下聲波傳輸速度與深度數(shù)據(jù)，在不同的深度區(qū)域、參考節(jié)點數(shù)量、節(jié)點通信半徑的情況下對ARTL算法、SWN算法與本文提出的LMARR算法進(jìn)行相應(yīng)的對比實驗，驗證算法的可行性與有效性。

表1 仿真實驗參數(shù)Tab.1 Simulation experiment parameters

3.1 不同海水聲速區(qū)域?qū)MARR算法的影響

根據(jù)圖2中海水聲速變化曲線分別在0～100 m和20～120 m的深度區(qū)域驗證本文提出的算法性能。未知節(jié)點的測距誤差作為算法性能評價指標(biāo)之一，未知節(jié)點i的測距誤差為

(23)

圖4為聲速對測距的影響仿真結(jié)果。

圖4 聲速對測距的影響Fig.4 The effect of sound velocity on ranging

測距誤差的仿真結(jié)果見圖4(a)。

未知節(jié)點的定位誤差也作為算法性能評價指標(biāo)之一，根據(jù)文獻(xiàn)[20]中對定位誤差的定義，未知節(jié)點i的定位誤差為

(24)

算法定位誤差的仿真結(jié)果見圖4(b)。

由圖4可以看出:100個未知節(jié)點隨機部署在不同深度的區(qū)域，本文提出的LMARR算法節(jié)點分布在20～120 m深度區(qū)域的測距效果和定位效果均優(yōu)于分布于0～100 m深度區(qū)域。圖4(a)與圖4(b)兩圖相對比，節(jié)點定位誤差的波動性相對于節(jié)點測距誤差的波動性要大以及個別未知節(jié)點的定位誤差相對較大，這是由于最小二乘定位算法本身存在的局限性所導(dǎo)致。若公式(16)中的第n個方程存在較大測距誤差時，誤差積累，最終的定位結(jié)果會受到影響，就可能會出現(xiàn)個別未知節(jié)點定位誤差相對較大的情況。而該算法在20～120 m深度區(qū)域的測距與定位誤差的波動性更小，這表明在聲速持續(xù)變化的區(qū)域的測距與定位效果更好，穩(wěn)定性更強。

節(jié)點在20～120 m深度區(qū)域的分布情況以及運用算法定位后的效果如圖5所示。

由圖5可以看出：未知節(jié)點的估算位置與實際位置偏差很小，算法的定位效果良好。

圖5 定位效果圖Fig.5 Localization result

3.2 算法的測距和定位性能比較

為了更好地檢驗本文提出的算法性能，對3種定位算法在不同水下區(qū)域的測距性能進(jìn)行了比較，見圖6。

圖6 3種算法測距性能比較Fig.6 Three algorithms ranging performance comparison

從圖6中可看出在0～100 m的深度區(qū)域中，LMARR算法的平均測距誤差為0.180 9 m，ARTL算法的平均測距誤差為0.189 9 m，SWN算法的平均測距誤差為0.185 7 m，三者相差不大，LMARR算法測距優(yōu)勢不明顯。

在20～120 m深度區(qū)域中, 大多數(shù)未知節(jié)點的測距誤差上，SWN算法測距誤差略微低于ARTL算法， 而LMARR算法的測距誤差最小，僅為0.099 8 m，相對于ARTL算法測距精度提升16%，相對于SWN算法提升10%。在沒有持續(xù)穩(wěn)定的海水聲速的20～120 m深度區(qū)域，LMARR算法與ARTL算法比在一定深度具有持續(xù)穩(wěn)定的海水聲速的0～100 m區(qū)域的測距精度要高。

為進(jìn)一步分析不同算法在不同聲速區(qū)域的定位效果，根據(jù)圖6(a)與圖6(c)的距離信息，完成對未知節(jié)點的定位計算。在0～100 m與20～120 m深度的海水聲速區(qū)域進(jìn)行仿真實驗的定位誤差變化情況見圖7。

圖7 3種算法定位性能比較Fig.7 Three algotithms localization performance comparison

由圖7可知: 在0～100 m深度區(qū)域中LMARR算法的平均定位誤差相對于SWN算法降低11%，相對于ARTL算法降低了20%;在20～120 m區(qū)域中，LMARR和SWN算法的定位誤差相對平穩(wěn)，且LMARR算法的平均定位誤差最小，為0.16 m，平均定位誤差相對于SWN算法降低了20%，比ARTL算法降低了33%。

仿真實驗結(jié)果表明:本文提出的LMARR算法在定位精度上有很大的提升且具有良好的穩(wěn)定性。從圖7中可看出3種算法在沒有持續(xù)穩(wěn)定的海水聲速的20～120 m的區(qū)域的定位誤差比在一定深度具有持續(xù)穩(wěn)定的海水聲速的0～100 m區(qū)域的要小，但是在這兩個不同區(qū)域，LMARR算法的定位誤差均比其它兩種算法小。

3.3 參考節(jié)點數(shù)量對平均定位誤差的影響

未知節(jié)點數(shù)量不變時，參考節(jié)點數(shù)量的變化對平均定位誤差有很大影響。

在20～120 m的海深區(qū)域仿真實驗算法平均定位誤差與參考節(jié)點的數(shù)量數(shù)量關(guān)系曲線，如圖8所示。

圖8 參考節(jié)點與平均定位誤差的關(guān)系Fig.8 The relation between reference node and mean localization error

從圖8看出:隨著參考節(jié)點數(shù)量的增加，3種算法的平均定位誤差均有下降;參考節(jié)點數(shù)量由40個增加至65個時，ARTL算法平均定位誤差由23.3%降至18.7%，SWM算法由20.1%降至16.6%，LMARR算法由17.3%降至14.2%，雖然ARTL算法與SWM算法下降幅度都大于LMARR算法，但是在具有相同的參考節(jié)點數(shù)量時，LMARR算法的定位誤差始終是最小的?？梢姳疚乃惴ǜ苡行У乩脜⒖脊?jié)點的信息，且易于擴展。圖中LMARR算法的平均定位誤差下降曲線最為平滑，顯示此算法具有更好的穩(wěn)定性。

4 結(jié) 論

本文針對海洋傳感器節(jié)點定位的精確度低的問題，考慮海水聲速多變以及節(jié)點信息接發(fā)次數(shù)，提出了LMARR定位算法。該算法不需要節(jié)點額外測定聲速，并且利用聲速均值有效減小了海水聲速多變的影響，通過節(jié)點發(fā)送與接收信息的時間差即可完成測距工作，相對于對稱型往返測距定位算法減少了定位信息接發(fā)的頻率。

仿真實驗表明：LMARR算法在距離估計和節(jié)點定位精度均優(yōu)于SWM算法和ARTL算法，特別是在20～120 m海水聲速持續(xù)變化的區(qū)域，定位精度比SWN算法提高了20%，比ARTL算法提高了33%。在已有網(wǎng)絡(luò)中添加新的參考節(jié)點，不需改動算法仍可完成較高精度的定位工作，展現(xiàn)了該算法良好的穩(wěn)定性以及可拓展性。