移動WSNs中基于半定規(guī)劃的節(jié)點(diǎn)定位算法*

馬佩勛,洪貴華

(1.長沙民政職業(yè)技術(shù)學(xué)院軟件學(xué)院,長沙 410004;2.滇西科技師范學(xué)院信息工程學(xué)院,云南 臨滄 677000)

現(xiàn)多數(shù)定位算法只聚集于靜態(tài)的無線傳感網(wǎng)絡(luò)(Wireless Sensor Networks,WSNs),假定錨節(jié)點(diǎn)和傳感節(jié)點(diǎn)是靜態(tài)的[1]。當(dāng)然,通過頻繁地更新位置估計(jì),可以將這些定位算法應(yīng)用于移動WSNs。但是,在設(shè)計(jì)這些算法時(shí),并沒有考慮如何通過移動信息,提高定位精度[2]。

文獻(xiàn)[3]研究了節(jié)點(diǎn)的移動及移動速度對定位精度的影響。而文獻(xiàn)[4]研究了如何利用移動速度估計(jì)節(jié)點(diǎn)位置。依據(jù)通信節(jié)點(diǎn)間的測距和相對測速信息,通過擴(kuò)展卡爾曼濾波(Extended Kalman Filter,EKF)可估計(jì)節(jié)點(diǎn)位置。

此外,通常利用錨節(jié)點(diǎn)與傳感節(jié)點(diǎn)間的無線信號的一個(gè)物理參數(shù)或多個(gè)物理參數(shù)測距。這些參數(shù)包括到達(dá)時(shí)間(Time of Arrival,ToA)[5]、到達(dá)時(shí)間差(Time Difference of Arrival,TDoA)[6]、接收信號強(qiáng)度(Received Signal Strength,RSS)[7-8]和到達(dá)角度(Angle of Arrival,AoA)[9]。其中,基于ToA測距估計(jì)精度較高,而基于 RSS測距成本低,易實(shí)施。

眾所周知,測距信息總是伴隨著一些噪聲或者不確定信息,這影響了定位性能。而最大似然估計(jì)(Maximum Likelihood,ML)是用于克服定位階段中不確定信息的常用技術(shù)。然而,ML估計(jì)的計(jì)算量大[10]。

利用內(nèi)點(diǎn)法可將ML問題轉(zhuǎn)化為凸優(yōu)化問題。而半定規(guī)劃(Semi-Definite Programming,SDP)[11]和二階錐規(guī)劃(Second Order Cone Programming,SOCP)是兩個(gè)主要的凸優(yōu)函數(shù)。基于SOCP定位系統(tǒng)簡單,計(jì)算復(fù)雜度低。相比于基于SDP定位算法,基于SOCP定位算法的收斂速度更快。但是,基于SDP定位算法的定位精度更高。

為此,針對移動WSNs,提出基于ToA的SDP定位算法SDPL。SDPL算法先利用ToA測距和速度信息,再利用SDP估計(jì)節(jié)點(diǎn)位置。

1 系統(tǒng)模型

在二維空間內(nèi)部署na個(gè)錨節(jié)點(diǎn)和ns個(gè)傳感節(jié)點(diǎn)。所有錨節(jié)點(diǎn)和傳感節(jié)點(diǎn)能夠獨(dú)立移動,從時(shí)刻n的位置移動至?xí)r刻n+1的新位置,其中n=1,…,N。其中N表示總的觀察時(shí)刻數(shù)。

假定每個(gè)傳感節(jié)點(diǎn)能夠測量自己的速度矢量,其包含速率和方向。在兩個(gè)連續(xù)觀察時(shí)刻內(nèi),節(jié)點(diǎn)速度保持常量。將節(jié)點(diǎn)的速度矢量用于節(jié)點(diǎn)的位置估計(jì)。

(1)

(2)

式中:R表示節(jié)點(diǎn)通信半徑。

(3)

2 基于速度輔助的ToA測距定位

假定ToA測距誤差服從高斯分布。利用速度信息提高定位精度。考慮兩種情況:準(zhǔn)確速度信息和噪聲速度信息[12]。

2.1 基于準(zhǔn)確速度信息的定位

若速度信息準(zhǔn)確,則式(1)的模型可修改成:

(4)

將式(4)代入式(3),基于ToA模型可更新為:

(5)

再利用式(6)求解:

(6)

將式(6)分解成多個(gè)子問題,并利用傳感節(jié)點(diǎn)的局部觀察求解。這些子問題依賴于鄰居錨節(jié)點(diǎn)在不同時(shí)刻的位置、節(jié)點(diǎn)與鄰居錨節(jié)點(diǎn)間距離以及節(jié)點(diǎn)在不同時(shí)刻的速度矢量。

令Bi={(j,n)|(i,j,n)∈A}。(j,n)∈Bi意味著在時(shí)刻n,錨節(jié)點(diǎn)j離傳感節(jié)點(diǎn)i的距離小于R。具體而言,對于i∈{1,…,ns},傳感節(jié)點(diǎn)i需解決的子問題:

(7)

(8)

目標(biāo)函數(shù)式(8)是一個(gè)非凸優(yōu)化問題,難以獲取其精確解。為此,利用SDP解決此非凸優(yōu)化問題[13]。

2.2 基于SDP的解

(9)

式中:dk表示矢量d的第k個(gè)元素。而rk表示矩陣R的第k個(gè)行。

據(jù)此,將式(9)可表述以下的約束優(yōu)化問題:

(10)

式中:w=[w1…wK]T。利用表述式(10)的約束項(xiàng):

(11)

利用恒等式xTAx=Tr(xxTA),可將式(11)轉(zhuǎn)換成:[W]kk=Tr(DkS),其中k=1,…,K。而W、Dk和S的定義如式(12)、式(13)和式(14)所示:

(12)

(13)

(14)

再利用式(11)～式(14),式(11)的優(yōu)化問題可表示為:

(15)

2.3 基于噪聲速度信息的定位

在實(shí)際環(huán)境中很難準(zhǔn)確地獲取節(jié)點(diǎn)的速度信息[14]。因此,基于測速誤差和測距誤差條件下,估計(jì)節(jié)點(diǎn)位置。式(16)表示了包含測速誤差的測速模型:

(16)

(17)

對式(17)進(jìn)行對數(shù)變換,基于ML的定位問題可表述為:

(18)

求解式(18),等價(jià)于求解式(19):

(19)

對于任意一個(gè)傳感節(jié)點(diǎn)i,式(19)的第一項(xiàng)為非凸優(yōu),而第二項(xiàng)是凸優(yōu)的,其處理了在不同時(shí)刻節(jié)點(diǎn)i的測速誤差。對式(19)第二項(xiàng)進(jìn)行擴(kuò)展,并丟棄常數(shù)項(xiàng)。同時(shí),為了簡化表述,將下標(biāo)i刪除。最終,可建立式(20)所示的目標(biāo)函數(shù):

(20)

式中:〈a,b〉=aTb。此外,引入以下標(biāo)量:

(21)

(22)

式中:Z=STS。

與上節(jié)類似,將式(20)轉(zhuǎn)化為SDP松馳的優(yōu)化問題:

[L]n+1,n+1-2[L]n+2,n+1-2Ts[[L]n+2,1[L]n+2,2]v(n)+

2Ts[[L]n+1,1[L]n+1,2]v(n)}

(23)

3 性能仿真

3.1 仿真環(huán)境

利用MATLAB建立仿真平臺,并利用MATLAB軟件內(nèi)的CVX工具包[15]。CVX工具包能夠計(jì)算SDP問題。在方形區(qū)域100m×100m內(nèi)部署錨節(jié)點(diǎn)和傳感節(jié)點(diǎn)。這些節(jié)點(diǎn)依據(jù)Random-way點(diǎn)移動模型移動。令?min表示節(jié)點(diǎn)的最大移動速度。

考慮T=30時(shí)刻。節(jié)點(diǎn)在每個(gè)時(shí)刻隨機(jī)地選擇一個(gè)目的節(jié)點(diǎn),再移動至此目的節(jié)點(diǎn)。并隨機(jī)選擇移動速度進(jìn)行移動。此外,引用均方根誤差(Root Mean Square Error,RMSE)作為性能指標(biāo)。

本文在第3節(jié)分別論述了準(zhǔn)確速度信息和噪聲速度信息兩種環(huán)境下的定位問題。為此,接下來分析這兩種環(huán)境下的SDPL算法的RMSE性能。

3.2 數(shù)據(jù)分析

3.2.1 基于準(zhǔn)確速度信息環(huán)境

本小節(jié)考慮三類場景。這三類場景參數(shù)如表1所示。在這三類場景中,節(jié)點(diǎn)的移動的最大速度?min在{1.4,2.8,4.2,5.6,7.0}內(nèi)變化,且單位為m/s。

表1 場景參數(shù)

眾所周知,傳統(tǒng)的定位算法對測距誤差、錨節(jié)點(diǎn)數(shù)以及通信半徑非常敏感。為此,選定三個(gè)場景,分析測距誤差、錨節(jié)點(diǎn)數(shù)以及通信半徑對定位性能的影響。

圖1 RMSE隨和?min的變化情況

圖2、圖3分別顯示了錨節(jié)點(diǎn)數(shù)和通信半徑參數(shù)對定位算法的影響。觀察這兩個(gè)圖不難發(fā)現(xiàn),錨節(jié)點(diǎn)數(shù)從3增加至6或者通信半徑從2 m增加至4 m提高了定位精度。但相比于錨節(jié)點(diǎn)數(shù)從3增加至6或者通信半徑從2 m增加至4 m,移動速度?min從1.4 m/s增加至2.8 m/s時(shí)的定位性能更好。

圖2 RMSE隨錨節(jié)點(diǎn)數(shù)和?min的變化情況

圖3 RMSE隨R和?min的變化情況

3.2.2 基于噪聲速度信息環(huán)境

圖4 參數(shù)?min對RMSE的影響

圖5 RMSE隨變化情況

4 總結(jié)

針對移動無線傳感網(wǎng)絡(luò)的節(jié)點(diǎn)定位問題,基于半定規(guī)劃的節(jié)點(diǎn)定位SDPL算法。SDPL算法利用ToA測距,并結(jié)合移動節(jié)點(diǎn)的速度信息聯(lián)合估計(jì)移動節(jié)點(diǎn)位置。同時(shí),考慮準(zhǔn)確測速信息和噪聲測速信息兩種情況。并通過SDP求解基于ML的定位方程。仿真結(jié)果表明,相比于錨節(jié)點(diǎn)數(shù)和通信半徑,移動信息對定位精度的影響更大。