水下傳感器網絡時間同步和定位的聯合實現方法

嚴長虹,馬 靜

(1.鹽城工學院信息學院,江蘇 鹽城 224000;2.南京航天航空大學經濟管理學院,南京 210016)

?

水下傳感器網絡時間同步和定位的聯合實現方法

嚴長虹1,2*,馬 靜2

(1.鹽城工學院信息學院,江蘇 鹽城 224000;2.南京航天航空大學經濟管理學院,南京 210016)

水下傳感器網絡的信號傳播速度受環境參數的影響而難以確定,增加了時間同步和定位的難度。當信號傳播速度未知時,提出了一種水下傳感器網絡的時間同步和定位聯合實現方案。通過建立該問題的優化函數和模型,設計了線性最小二乘(LLS)估計、最小二乘半定規劃(LS-SDP)、平方最小二乘半定規劃(SLS-SDP)及平方最小二乘二階錐規劃(SLS-SOCSDP)算法,分析了各算法的計算復雜度。仿真分析表明,線性代數LLS算法計算速度快,在低噪聲條件下具有較高的估計精度。凸優化的LS-SDP、SLS-SDP及SLS-SOCSDP算法對未知參數估計的穩定性較好,但計算復雜度較高。

水下傳感器網絡;定位;時間同步;到達時間

水下傳感器網絡主要采用傳感器節點監測水域內的各種環境參數,以實現資源監控、災難預警與導航幫助等。水下傳感器節點所采集的環境參數需要與地理位置坐標相捆綁才有意義,因此定位技術也是水下傳感器網絡的關鍵技術[1-3]。傳統的GPS定位方法由于體積大、能耗高、需要固定的基礎硬件設施并不適應于所有傳感器節點定位。為此,傳感器網絡通常采用已知位置坐標的信標節點去推算未知節點的位置坐標,通過各種測距方法建立節點間距離約束優化方程以估算未知節點位置坐標。常用測距方法包括到達時間(TOA)[4]、到達時間差(TDOA)[5]及接收信號強度(RSS)及能量強度等。其中TOA測量方法實現原理簡單,成本低,是一種較為常見的傳感器網絡定位實現方法。

建立于節點間距離約束優化方程基礎上,已有各種算法估算位置坐標,常用的包括線性方程的代數估計[6-7]及凸優化的半正定(SDP)[8]和二階錐規劃(SOCP)[9]算法。線性代數估計法將未知結果直接表示為代數解,無須迭代計算過程,計算復雜度低,但在噪聲較大時,估計結果不穩定。為此,也有算法將約束優化方程松弛為凸優化過程,SDP和SOCP也是當前傳感器網絡定位常采用的算法,但其計算復雜度較高。為減少凸優化變量及計算復雜度,凸優化模型的建立也是研究的重要內容,也有算法將模型松弛為混合的二階錐規劃(SOCSDP)過程。

時間測量以各節點的時鐘為準,然而各節點的時鐘存在漂移和偏離,導致直接的時間觀測不準確,為此提出了時間同步和定位的聯合實現方法[10-11]。文獻[12]提出了采用多路信號來回傳遞推導了觀測時間與實際時間的關系,從而實現時間同步和定位的聯合。假設所有信標節點的時鐘是同步的,而未知節點存在時鐘漂移和偏離,文獻[13]提出了非確定信標節點位置下多個未知節點的目標位置以及時間同步的聯合代數計算方法。同樣地,以節點時鐘漂移和偏離模型為基礎,文獻[7]提出了一種時間同步和節點定位的多源目標聯合線性估計方法,實現節點時鐘漂移率、偏離量和位置坐標的同時估計。

節點間距離不但與時間有關,而且與信號傳播速度相關,但水下信號傳播速度與水深、鹽度與溫度等因素有關,因此水下傳感器網絡的時間同步和定位更加難以實現。文獻[14]考慮信號傳播速度的不確定性,提出了時間同步和定位的兩步代數計算方法,即預先估計時間同步參數,再以估計出的時間同步參數確定節點位置坐標的兩步估計方法。文獻[15]將水下傳播介質進行分層,采用對聲波傳播速度補償的方法實現時間同步和定位的聯合估計,并亦設計了代數計算方法,但代數計算方法在高噪聲條件下估計誤差較大。

當水下信號傳播速度為未知參數時,本文提出了一種水下傳感器網絡的時間同步和定位聯合實現方案,并設計了線性最小二乘(LLS)估計方法。為減少高噪聲條件下的估計誤差,本文又提出了凸優化的最小二乘半定規劃(LS-SDP)、平方最小二乘半定規劃(SLS-SDP)及平方最小二乘二階錐規劃(SLS-SOCSDP)算法。仿真實現了各算法,并驗證了各算法的有效性,分析了各算法的計算復雜度和估計精度性能。本文第1部分首先介紹了問題描述;第2部分介紹了算法設計;第3部分詳細推導了各算法的計算復雜度;第4部分為仿真與分析;最后部分為結論。

1 問題描述

考慮水下三維空間部署的傳感器網絡,存在著待確定位置坐標的未知節點,其位置坐標假設為x=[xyz]T。同時在該區域內分布著M個已知位置坐標的信標節點,假設信標節點位置坐標分別為xi=[xiyizi]T,i=1,2,…,M。為估計未知節點坐標,各信標節點與未知節點間進行到達時間(TOA)測量,如圖1所示。信標節點i在Ti,1時刻(Ti,1為信標節點i上時鐘的觀測時間)向未知節點發送信號,未知節點在Ri,1時刻(Ri,1為未知節點上時鐘的觀測時間)收到信標節點i發出的信號。

圖1 觀測時間與實際真實時間關系

由于傳感器節點所處環境參數、初始化及能量消耗等原因使得節點計時時鐘失步,即引起節點上時鐘的觀測時間與實際真實時間不一致。由于Ti,1為信標節點i時鐘的觀測時間,根據文獻[14-15]的節點計時時鐘的漂移和偏離模型,有如下關系式

(1)

(2)

知節點上時鐘的漂移率和偏移量。節點間收到信號的實際真實時間之差為節點間信號到達時間,記作ti,1,因此有關系式

(3)

(4)

當未知節點接收到信標節點i的信號后,未知節點又在Ti,2時刻(Ti,2為未知節點上時鐘的觀測時間)發送信號給信標節點i,信標節點i在Ri,2時刻(Ri,2為信標節點i上時鐘的觀測時間),同式(4)的類似推導過程,有方程式

(5)

當信號在水下區域進行傳播時,信號傳播速度隨水下環境的壓力、鹽度和溫度等參數變化而改變,為此在本模型中將信號傳播速度假設為未知參數。式(4)及式(5)建立了節點的時鐘同步參數ωx、ωi、θx、θi與節點間距離的約束關系,為節點時間同步和位置坐標的聯合估計提供了可能。模型假設信標節點的時鐘漂移率ωi、偏移量θi及位置坐標xi為已知參數,以估計未知節點的時鐘漂移率ωx、偏移量θx、位置坐標x及水下信號的傳播速度c。

2 算法設計

為估計時鐘同步參數ωx、θx、位置坐標x及水下信號的傳播速度c,下面分別介紹線性最小二乘(LLS)估計法及3種不同的凸優化實現方法。

2.1 線性最小二乘(LLS)估計法

對式(4)及式(5)相加,有關系式

(6)

(ai+bi)c+biδxc=di+0.5c(εi,1+εi,2)

(7)

式中:由于ai>0,ai+bi>bi,δx非常接近于零,故式(7)可以近似為

τic=di+εi

(8)

(9)

Aη=b+n

(10)

(11)

式中:權重矩陣Σn=E(nTn),其值表示為

(12)

式中:di為未知參數,可預先設置Σ為單位矩陣,以式(11)近似估計未知節點位置坐標。然后再以此近似估計值計算di,再以式(12)重新計算Σ及η,將此計算方法稱之為線性最小二乘(LLS)估計法。根據向量η的定義,可從向量估計值η提取出未知節點位置坐標及信號傳播速度平方值c2。

2.2 最小二乘半定規劃(LS-SDP)算法

根據表示為式(8)的測量方程及極大似然估計法,聯合估計問題可以表示為以下優化問題

(13)

式(13)所描述的優化問題為非線性非凸優化問題,為轉化為凸優化問題,令d=[d1d2…dM]T,h=[dTc]T,可將式(13)中的目標優化函數重寫為

(14)

(15)

(16)

所以將式(13)表示的優化函數可進一步表示為

(17)

為將式(17)表示的優化問題轉化為凸優化問題,將H及Z作凸優化松弛,得到以下凸優化問題

(18)

式(18)表示的優化問題為最小二乘(LS)目標函數的半定規劃(SDP)問題,故將上述算法稱為LS-SDP算法。

2.3 平方最小二乘(SLS)凸優化方法

不同于式(13)表示的目標函數,亦可建立平方最小二乘的目標函數,以便于轉化為凸優化問題。為此將式(8)兩邊平方,忽略高階項,有關系式

(19)

對式(19)建立極大似然估計方程,表示為如下平方最小二乘(SLS)目標函數的優化問題

(20)

式中:μ=c2,μ為待確定的未知參數。對式(20)作進一步等效變換和凸優化松弛,可以轉化為以下凸優化問題

(21)

式(21)表示的凸優化問題為目標函數為平方最小二乘(SLS)的半正定規劃(SDP)問題,所以將此計算過程稱之為SLS-SDP算法。SDP凸優化問題的變量較多,計算復雜度也較高,為此將式(21)進一步等效轉化為如下形式

(22)

式中:u=[u1u2…uM]。式(22)表示的凸優化形式既包含了二次錐規劃(SOCP),又包含了半定規劃(SDP)優化,故將此計算過程稱為SLS-SOCSDP算法。

2.4 時間同步參數的計算

考慮信號傳播速度的變化量為Δc,未知節點坐標位置變化量為Δx=[ΔxΔyΔz]T,則式(7)可改寫為

(23)

JΔθ=γ+ε

(24)

二乘法估計原理,未知向量Δθ的估計值為

(25)

(26)

并且將估計出的Δθ(1:3)及Δθ(4)作為Δx及Δc增加到LSS、LS-SDP、SLS-SDP及SLS-SOCSDP各算法的估計值中,對估計結果進行優化求精,將優化求精后的未知節點位置坐標及信號傳播速度稱為優化求精解。為估計時間偏移量θx。將式(5)減去式(4),有以下表達式

(27)

式中:i=1,2,…,M。考慮所有未知節點與信標節點的信號測量,有估計表達式

(28)

3 計算復雜度分析

凸優化算法的計算復雜度主要與凸優化方程中的變量和等式約束數量有關。為比較3種不同凸優化算法LS-SDP、SLS-SDP及SLS-SOCSDP算法的計算復雜度,將算法復雜度計算過程中的參數數量列出在表1中。表1中NSOCP表示了二次錐規劃約束數量,NSDP表示了半定規劃約束數量。LS-SDP算法包括了2個半定規劃約束,其尺寸大小分別為M+1及4,故變量數量為(M+1)2+42,其等式約束數量為M+6。而SLS-SDP算法包括了M個尺寸大小為2及1個尺寸大小為4的半定規劃約束,凸優化變量數量為4M+17,其等式約束數量為2M+6。SLS-SOCSDP算法包括了1個尺寸大小為M+1的二次錐規劃約束及1個尺寸大小為4的半定規劃約束,變量數量為M+18,其等式約束數量為M+6,故SLS-SOCSDP算法的變量與等式約束數量都比SLS-SDP算法有所減少。

[12]的凸優化算法的計算復雜度計算方法,考慮信標節點數量M?4的情況下,3種凸優化算法的復雜度表示如下,

(29)

式中:log(1/ξ)表示了最小需要的迭代次數,ξ為凸優化算法的求解精度。由式(29)可知,3種算法中,LS-SDP算法的計算復雜度較高,而SLS-SOCSDP算法的計算復雜度較低。當然相比于3種凸優化算法,LLS算法不需要迭代計算,其計算過程較凸優化算法快了很多,具體復雜度計算在此不做介紹。

表1 凸優化算法復雜度計算中的參數數量

4 仿真分析

本文假設信號傳播速度為未知參數,利用信標節點的時間同步參數和位置坐標,通過信標節點與未知節點間的TOA測量,實現了未知節點的時間同步參數和位置坐標的聯合估計。在MATLAB軟件上進行了LLS、LS-SDP、SLS-SDP及SLS-SOCSDP算法的仿真分析,3種凸優化算法采用CVX工具箱下的SeDuMi求解器計算。

4.1 算法的平均運行時間

在邊長為100 m的三維區域平面上,預先將未知節點設置在(50,50,50)點,隨機生成M個信標節點。分別假設信標節點數量M=6,7,8,9,10,表2列出了1 000次蒙特卡羅(MC)下LLS、LS-SDP、SLS-SDP和SLS-SOCSDP算法的單次平均運行時間。隨著信標節點數量M的增加,未知節點與信標節點間的TOA測量連接數量增加,4種算法的平均運行時間都略有增加。比較3種凸優化LS-SDP、SLS-SDP和SLS-SOCSDP算法,SLS-SOCSDP的運行時間最短。如當M=6時,SLS-SOCSDP算法的平均運行時間為18.2 ms,而LS-SDP、SLS-SDP算法的平均運行時間為35.6 ms、27.7 ms。相比于3種凸優化算法,LLS算法的運行相當快,當M=6時,LLS算法的平均運行時間僅為0.22 ms。

表2 不同算法的單次平均運行時間比較 單位:ms

4.2 定位誤差比較

所設計的算法在一定程度上進行了近似和松弛,所以定位結果非最優,仿真同時也驗證了4種不同算法的估計誤差精度。6個信標節點分別設置在(95,20,75),(16,95,5),(10,85,50),(70,75,90),(80,25,20),(65,30,60),并在該三維空間上隨機產生20個未知節點。所有信標節點的時鐘同步參數ωi=1,θi=0,且為已知值。假設未知節點與各信標節點間的傳播時間噪聲εi,1、εi,2以納秒為單位,都服從均值為零,方差為δ2的高斯分布。仿真數據生成時,信號傳播速度c預先設置為 3×108m/s。采用均方根誤差(RMSE)評價4種不同算法的定位精度,取20個隨機生成的未知節點位置的平均誤差作為性能評價指標。選擇RMSE定位誤差的蒙特卡羅(MC)次數為1 000次,并采用1 000次平均值進行對比分析。

圖2 誤差隨噪聲大小變化關系

當傳播時間噪聲大小δ從0.5 ns增加到5 ns時,圖2(a)繪出了4種算法的RMSE定位誤差比較,該圖中CRLB表示了該問題模型的克拉美羅下界值[14]。由圖2(a)可見,4種算法的RMSE定位誤差都隨傳播時間噪聲的增加而增大。在低噪聲條件δ<3.5 ns時,LLS算法的定位精度較高,但當δ>3.5 ns時,LLS算法的定位誤差在4種算法中最大。3種凸優化的LS-SDP、SLS-SDP及SLS-SOCSDP算法的估計誤差比較接近。相比較而言,LS-SDP算法的定位誤差較小,但其復雜度較高。SLS-SOCSDP的RMSE定位誤差較大,但SLS-SOCSDP算法的計算復雜度較低。

同樣地,當傳播時間噪聲大小δ從0.5 ns增加到5 ns時,圖2(b)繪出了4種算法的信號傳播速度RMSE估計誤差比較。有同樣的結果發現,在噪聲較小(δ<3.5 ns)時,LLS算法的估計誤差更加接近于CRLB下界值,但當傳播時間噪聲δ>3.5 ns,LLS算法的信號傳播速度估計誤差較其他3種凸優化算法大。3種凸優化算法LS-SDP、SLS-SDP及SLS-SOCSDP的估計誤差比較接近,相比于代數LLS方法,3種凸優化算法隨噪聲的變化關系更加平穩。

圖3 時間同步參數的估計誤差

4.3 時間同步參數估計誤差

當所設計的4種算法估計出未知節點位置坐標及信號傳播速度后,根據2.4所述的方法計算未知節點的時間同步參數,仿真同時也分析了時間同步參數的估計誤差。未知節點及信標節點參數設置同4.2,當傳播時間噪聲大小δ從0.5 ns增加到5 ns時,圖3繪出了4種算法的時間同步參數包括時鐘漂移率和偏移量的RMSE估計誤差比較。圖3(a)所反映的時鐘漂移率隨噪聲δ的變化曲線與圖3(b)的時鐘偏離量隨噪聲δ的變化曲線,有非常相似的變化關系。當δ<3.5 ns時,代數LLS算法的時鐘漂移率及偏移量估計誤差RMSE都較其他3種凸優化算法小;而當噪聲δ>3.5 ns時,LLS算法的估計誤差較大。相比于代數LLS方法,3種凸優化算法隨信號傳播噪聲的變化較為平緩。如當噪聲δ為0.5 ns時,LS-SDP算法的時鐘漂移率RMSE為0.065,而代數LLS算法的時鐘漂移率RMSE僅為0.03,代數LLS算法比LS-SDP算法的估計誤差小;而當噪聲δ等于5 ns時,LS-SDP算法的時鐘漂移率RMSE增加到了0.12,而LLS算法的時鐘漂移率RMSE增加到了0.175,代數LLS算法比LS-SDP算法的估計誤差更大了。

4.4 優化求精估計誤差比較

本文內容2.4所介紹的計算過程同時也對未知節點位置坐標進行了優化求精,仿真同時也對求精前的初始解與優化求精解進行了對比。同樣地,未知節點及信標節點參數設置同4.2,當傳播時間噪聲大小δ從0.5 ns增加到5 ns時,圖4對比了優化求精前后定位誤差與信號傳播速度的大小關系。由圖4(a)可見,SLS-SOCSDP算法經過優化求精后,未知節點定位誤差有較大的改善,更加接近于估計結果的CRLB下界值。如當δ=5 ns時,SLS-SOCSDP算法的初始解定位誤差RMSE為4.7 m,而經過優化求精后,其定位誤差RMSE減少到了3.9 m。從圖4(b)可以發現,優化求精后的信號傳播速度估計誤差也有較好的改善。如當δ=5 ns時,LLS算法的信號傳播速度初始解估計誤差RMSE為1.22×107m/s,而經過優化求精后,其估計誤差RMSE減少到了0.95×107m/s,估計誤差較初始解有較大的改進。

圖4 優化求精前后估計誤差比較

5 結論

當無線信號在水下傳播時,信號傳播速度難以測量。本文針對水下傳感器網絡的時間同步和定位聯合實現問題,提出了通過信標節點與未知節點間的雙路來回時間測量方法。假設水下信號傳播速度為未知參數,設計了時間同步和定位聯合實現問題模型的LLS、LS-SDP、SLS-SDP及SLS-SOCSDP算法,驗證了算法的有效性。與所設計的3種凸優化算法比較,代數LLS算法運算速度快,但在強噪聲時估計誤差較大。相比與LLS算法,LS-SDP、SLS-SDP及SLS-SOCSDP的凸優化算法隨噪聲的變化更為平緩。當然本文所提出了模型算法也有一定的局限性,只適用于單源節點的時間同步和定位聯合實現問題,未將模型擴展到多源節點合作實現,有待于進一步探索與研究。

參考文獻:

[1] Amin Y Teymorian,Wei Cheng,Liran Ma,et al. 3D Underwater Sensor Network Localization[J]. IEEE Transactions on Mobile Computing.2009,8(12):1610-1621.

[2] Xing Tan,Jian Li. Cooperative Positioning in Underwater Sensor Networks[J]. IEEE Transactions on Signal Processing,2010,58(11):5860-5891.

[3] 蔡紹濱,高振國,潘海為,等. 帶有罰函數的無線傳感器網絡粒子群定位算法[J]. 計算機研究與發展,2012,49(6):1228-1234.

[4] Hong Shen,Zhi Ding,Soura Dasgupta,et al. Multiple Source Localization in Wireless Sensor Networks Based on Time of Arrival Measurement[J]. IEEE Transactions on Signal Processing,2014,62(8):1938-1949.

[5] Le Yang,C Ho. An Approximately Efficient TDOA Localization Algorithm in Closed-Form for Locating Multiple Disjoint Sources with Erroneous Sensor Positions[J]. IEEE Transactions on Signal Processing,2009,57(12):4598-4615.

[6] Huajie Shao,Xiaoping Zhang,Zhi Wang. Efficient Closed-Form Algorithms for AOA Based Self-Localization of Sensor Nodes Using Auxiliary Variables[J]. IEEE Transactions on Signal Processing,2014,62,(10):2580-2594.

[7] 顧治華,朱雪芬,吳曉平,等. 一種傳感網時間同步和定位的聯合線性估計方法[J]. 傳感技術學報,2016,29(3):397-402.

[8] Pratik Biswas,Tzu-Chen Liang,Kim-Chuan Toh,et al. Semidefinite Programming Approaches for Sensor Network Localization with Noisy Distance Measurements[J]. IEEE Transactions on Automation Science and Engineering,2006,3(4):1-11.

[9] Ghasem Naddafzadeh-Shirazi,Michael Botros Shenouda,Lutz Lampe. Second Order Cone Programming for Sensor Network Localization with Anchor Position Uncertainty[J]. IEEE Transactions on Wireless Communication,2014,13(2):949-963.

[10] Aitzaz Ahmad,Erchin Serpedin,Hazem Nounou,et al. Joint Node Localization and Time-Varying Clock Synchronization in Wireless Sensor Networks[J]. IEEE Transactions on Wireless Communication,2013,12(10):5322-5333.

[11] Weijie Yuan,Nan Wu,Bernhard Etzlinger,et al. Cooperative Joint Localization and Clock Synchronization Based on Gaussian Message Passing in Asynchronous Wireless Networks[J]. IEEE Transactions on Vehicular Technology,2016,65(9):7257-7273.

[12] Reza Monir Vaghefi,R Michael Buehrer. Cooperative Joint Synchronization and Localization in Wireless Sensor Networks[J]. IEEE Transactions on Signal Processing,2015,63(14):4035-4040.

[13] Liyang Rui,K C Ho. Algebraic Solution for Joint Localization and Synchronization of Multiple Sensor Nodes in the Presence of Beacon Uncertainties[J]. IEEE Transactions on Wireless Communications,2014,13(9):5196-5210.

[14] Roee Diamant,Lutz Lampe. Underwater Localization with Time-Synchronization and Propagation Speed Uncertainties[J]. IEEE Transactions on Mobile Computing,2013,12(7):1257-1269.

[15] Jun Liu,Zhaohui Wang,Jun-Hong Cui,et al. A Joint Time Synchronization and Localization Design for Mobile Underwater Sensor Networks[J]. IEEE Transactions on Mobile Computing.2016,15(3):530-543.

Joint Implement Approach for Time Synchronization and Localization in Underwater Sensor Networks

YAN Changhong1,2*,MA Jing2

(1.School of Information Engineering,Yancheng Institute of Technology,Yancheng Jiangsu 224000,China; 2.College of Economics and Management,Nanjing University of Aeronautics and Astronautics,Nanjing 210016,China)

In underwater sensor networks,signal propagation speed is difficult to be determined due to the influence of environmental parameters,which increases the difficulty of time synchronization and localization. When the signal propagation speed is unknown,a joint implementation scheme for time synchronization and localization is put forward in underwater sensor networks. By building the optimization function and model of the problem,the linear least squares(LLS)estimation,least squares semidefinite programming(LS-SDP),squared least square semidefinite programming(SLS-SDP)and squared least square second order cone and semidefinite programming(SLS-SOCSDP)algorithms are designed,then the computational complexity of the proposed algorithms is analyzed. The simulation analysis shows that the linear algebra LLS algorithm runs fast and obtains high positioning accuracy in low noise conditions. The stability of LS-SDP,SLS-SDP and SLS-SOCSDP algorithm with convex optimization is better,but the computation complexity is higher.

underwater sensor networks;localization;time synchronization;time of arrival

嚴長虹(1980-),女,講師,在讀博士,主要研究方向為無線傳感器網絡、信號分析與處理、網絡安全等。在國內外重要會議及期刊上發表論文十多篇;

馬 靜(1966-),女,教授,博士生導師,主要研究領域包括信息企業化、知識管理與知識管理系統、電子商務、國防科技情報、復雜網絡與網絡輿情、大數據分析等。

項目來源:國家自然科學基金項目(71373123);江蘇高校哲學社會科學研究重點項目(2015ZDIXM007);南京航空航天大學基本科研業務費重大項目(NP201630X)

2016-11-02 修改日期:2017-02-12

TP393.0

A

1004-1699(2017)06-0922-07

C:6150;7110;5210

10.3969/j.issn.1004-1699.2017.06.020