基于圖模型的傳感器節(jié)點定位方法

趙海兵， 蔣俊正

(桂林電子科技大學(xué) 信息與通信學(xué)院, 廣西 桂林 541004)

無線傳感器網(wǎng)絡(luò)(wireless sensor network,簡稱WSN)備受關(guān)注，已廣泛應(yīng)用于軍事、環(huán)境、醫(yī)療、家居和工業(yè)等領(lǐng)域[1-2]。在很多需要WSN提供監(jiān)測服務(wù)的場景下，不含位置信息的監(jiān)測數(shù)據(jù)是缺乏應(yīng)用價值的。例如環(huán)境污染監(jiān)測、森林火災(zāi)監(jiān)測和天然氣管道監(jiān)測等應(yīng)用場景中，WSN中的傳感器節(jié)點不僅需要提供監(jiān)測對象的信息，還要包含節(jié)點自身的位置信息。因此，WSN中傳感器節(jié)點定位技術(shù)的研究就顯得尤為重要。

WSN中傳感器節(jié)點位置的獲取可以借助于中國北斗導(dǎo)航系統(tǒng)(Beidou navigation satellite system,簡稱BDS)[3]或美國全球定位系統(tǒng)(global positioning system,簡稱GPS)[4]，但需要在傳感器中添加BDS或GPS接收模塊，不僅增加了傳感器的制作成本，還增加了本身的功耗，縮短整個WSN的壽命。而且部署傳感器的具體環(huán)境可能是復(fù)雜多變的，如室內(nèi)環(huán)境或山林地區(qū)，BDS和GPS信號難以有效穿透墻體、高山、密林等障礙，這導(dǎo)致很多場景下無法使用BDS和GPS進(jìn)行定位[5]。針對這一系列問題，常用的做法是只在少數(shù)傳感器中添加定位模塊，并將其部署在可以接收BDS或GPS信號的位置，利用這一部分傳感器節(jié)點的位置和節(jié)點間距離對其他節(jié)點進(jìn)行定位。其中，事先獲知位置的傳感器節(jié)點稱之為已知位置(location-aware,簡稱LA)節(jié)點，其他節(jié)點稱為未知位置(location-unaware,簡稱LU)節(jié)點。節(jié)點間測距的方法有到達(dá)時間(time-of-arrival,簡稱TOA)、到達(dá)時間差(time-difference-of-arrival,簡稱TDOA)、到達(dá)角(angle-of-arrival,簡稱AOA)和接收信號強度(received-signal-strength,簡稱RSS)[6-7]等。

現(xiàn)有的眾多定位方法中，許多文獻(xiàn)把定位問題歸結(jié)為了優(yōu)化問題，采用凸優(yōu)化的方法進(jìn)行求解。例如，BISWAS等[8]采用了半正定規(guī)劃(semi-definite programming,簡稱SDP)松弛的方法，且引入了一個正則項，有助于降低SDP解決方案的秩，最后采用梯度下降法細(xì)化節(jié)點位置，提高了定位的準(zhǔn)確性。但該正則項系數(shù)的選取比較繁瑣，增加了計算的復(fù)雜度。NONGPIUR[9]同樣采用了SDP松弛的方法，不同的是從節(jié)點連通性出發(fā)引入了一個全新的正則項，用于懲罰一些孤立的節(jié)點，提高了定位的準(zhǔn)確性，該正則項系數(shù)的選取沒有經(jīng)過復(fù)雜的運算，但只是依據(jù)經(jīng)驗獲取，更合理的選取方式有待進(jìn)一步研究。TSENG[10]采用了二階錐規(guī)劃(second-order cone programming,簡稱SOCP)松弛的方法，比SDP松弛有更少的變量和約束條件，但若有大量LU節(jié)點分布在LA節(jié)點形成的凸包之外，則不會有良好的定位效果[11]。

區(qū)別于上述定位方法都有約束條件的限制，同樣采用節(jié)點間的距離誤差作為目標(biāo)函數(shù)，而將定位問題歸結(jié)為一個無約束的優(yōu)化問題。該方法在圖模型基礎(chǔ)上充分考慮了節(jié)點間的連通性，利用節(jié)點間距離對目標(biāo)函數(shù)中各求和項設(shè)置了歸一化的權(quán)重值。對該優(yōu)化問題目標(biāo)函數(shù)的求解分為兩步：1)利用三點定位法對LU節(jié)點進(jìn)行簡單粗略的初步定位；2)把基于三點定位得出的初步定位結(jié)果作為初始值，結(jié)合二階泰勒近似給出的修正海森矩陣，采用修正牛頓法對定位問題進(jìn)行求解。仿真結(jié)果表明，與文獻(xiàn)[8]相比，本方法在不同程度的測距誤差下定位更準(zhǔn)確，且算法迭代次數(shù)更少，耗時更短。

1 定位問題的圖模型

為模擬某一實際區(qū)域內(nèi)的WSN，在[-0.5,0.5]×[-0.5,0.5]的平面內(nèi)構(gòu)建了WSN的圖模型G=(V,E,W)，將實際環(huán)境中傳感器近似為平面區(qū)域內(nèi)的節(jié)點，模擬實際場景中傳感器的部署方式，將傳感器的位置近似為平面區(qū)域內(nèi)的坐標(biāo)位置。

V={x1,x2,,xN,a1,a2,,aM}是WSN中所有傳感器節(jié)點的集合。其中：N個LU節(jié)點是隨機(jī)分布的，記xi=[xi1;xi2]，xi1和xi2分別為第i個LU節(jié)點的橫坐標(biāo)和縱坐標(biāo)；M個LA節(jié)點的位置假設(shè)是準(zhǔn)確的(或其位置誤差可以忽略不計)，記ak=[ak1;ak2]，ak1和ak2分別為第k個LA節(jié)點的橫坐標(biāo)和縱坐標(biāo)。則N個LU節(jié)點和M個LA節(jié)點的坐標(biāo)位置分別表示為x和a，即

x=[x11,x12,x21,x22,,xN1,xN2]T，

(1)

a=[a11,a12,a21,a22,,aM1,aM2]T。

(2)

(3)

xTCika-aTDkix+aTFkka，

(4)

其中，

Aij=(ei1-ej1)(ei1-ej1)T+

(ei2-ej2)(ei2-ej2)T，

(5)

(6)

(7)

在實際場景中，如果2個傳感器節(jié)點間的距離太大，發(fā)射信號功率可能會衰減至不能被識別到，因此并不是所有的節(jié)點都可以互相通信。假設(shè)只有距離在dmax范圍內(nèi)的兩節(jié)點才可以正常通信，并用一條邊相連接，記為E={ρij,ρik}，其中ρij表示第i個LU節(jié)點和第j個LU節(jié)點有一條邊相連，ρik表示第i個LU節(jié)點和第k個LA節(jié)點有一條邊相連，從而把WSN建模成一個彼此相連的通信網(wǎng)絡(luò)圖。基于節(jié)點網(wǎng)絡(luò)圖的連通性，把直接相連的節(jié)點作為鄰居節(jié)點，也就是可以直接相互通信的節(jié)點，如下所示：

N1(i)={j:ρij∈E}，

(8)

N2(i)={k:ρik∈E}，

(9)

N(i)=N1(i)∪N2(i)。

(10)

其中，i=1,2,,N,N(i)中包含了第i個LU節(jié)點的所有鄰居節(jié)點，即N1(i)包含了可以與第i個LU節(jié)點直接相互通信的所有LU節(jié)點，N2(i)包含了可以與第i個LU節(jié)點直接相互通信的所有LA節(jié)點。

由于WSN以無線的方式進(jìn)行通信，且節(jié)點發(fā)射信號的功率和接收到信號的功率都可以測得，節(jié)點間距離可以通過RSS測距技術(shù)[6]獲取。但是在現(xiàn)實環(huán)境下，發(fā)射信號在傳輸過程中易受多徑衰落和陰影衰落等影響，所以根據(jù)信號的衰減特性測得的距離并非兩節(jié)點間的真實距離。于是，考慮到節(jié)點間距離越遠(yuǎn)，測距時受到干擾的不確定性越大，測距數(shù)據(jù)越不可靠，則節(jié)點間的測得距離dij和dik可表示為[8]：

(11)

(12)

εijorεik=2rand(1,1)-1。

(13)

(14)

(15)

綜上，本方法構(gòu)建了WSN圖模型G=(V,E,W)。從而定位問題可以概述為：基于圖的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，利用LA節(jié)點的坐標(biāo)位置和RSS技術(shù)測得的節(jié)點間距離，求解LU節(jié)點的坐標(biāo)位置。

2 定位問題的求解

基于圖模型G=(V,E,W)，最小化鄰居節(jié)點間距離誤差的加權(quán)和[8]，將定位問題歸結(jié)為無約束優(yōu)化問題：

(16)

顯然，該目標(biāo)函數(shù)(16)是關(guān)于LU節(jié)點坐標(biāo)x的高度非線性四次函數(shù)，可以通過二階泰勒展開將其近似為如式(17)，再通過迭代的方法求最優(yōu)解[12]。

f(x)≈f(x0)+Tf(x0)(x-x0)+

(17)

為此，采用兩步法來求解。

2.1 初始值x0的選取

結(jié)合泰勒級數(shù)和泰勒展開式的性質(zhì)[13]，式(17)中選取的x0需在x附近，即作為迭代初始值的x0需在LU節(jié)點位置附近，因此對LU節(jié)點進(jìn)行粗略的初步定位。

當(dāng)待求LU節(jié)點最大測距范圍內(nèi)至少有3個LA節(jié)點時，選取距其最近的3個LA節(jié)點，采用三點定位法對該LU節(jié)點進(jìn)行定位。三點定位的幾何思想是：在平面內(nèi)分別以3個LA節(jié)點為圓心，以LA節(jié)點和LU節(jié)點的距離為半徑，畫圓，3個圓的交點就是待求的LU節(jié)點。三點定位方法如圖1所示，A、B和C表示3個LA節(jié)點，坐標(biāo)位置依次是(x1,y1),(x2,y2),(x3,y3)；P為LU節(jié)點，A、B和C三點到待求節(jié)點P的距離分別為d1,d2,d3。假設(shè)待求節(jié)點P的坐標(biāo)位置為(x,y)，則可得到3個關(guān)于圓的方程組：

(18)

對式(18)求解，可得LU節(jié)點P的具體坐標(biāo)：

(19)

圖1 三點定位法示意圖

由于節(jié)點間距離存在誤差，3個圓并不會恰好相交于一點，即求得的LU節(jié)點的坐標(biāo)并不太準(zhǔn)確，因此利用三點定位法只能對部分LU節(jié)點進(jìn)行粗略的定位。

當(dāng)待求LU節(jié)點最大測距范圍內(nèi)只有1～2個LA節(jié)點時，將距其最近的LA節(jié)點的位置作為該LU節(jié)點的位置；當(dāng)待求LU節(jié)點最大測距范圍內(nèi)無LA節(jié)點時，將區(qū)域中心的位置作為該LU節(jié)點的位置。

為了滿足對于定位準(zhǔn)確性的要求，在完成對所有LU節(jié)點粗略的初步定位后，需將本次定位結(jié)果作為初始值進(jìn)行下一步的迭代運算。

2.2 迭代優(yōu)化

求解無約束的優(yōu)化問題，修正牛頓法是最有效的算法之一。首先，把原目標(biāo)函數(shù)(16)改寫為：

(20)

于是，可得到其梯度向量和Hessian矩陣為：

(21)

4(xTBiix-xTCika-aTDkix+

(22)

(23)

采用的修正牛頓法算法流程為：

1) 以三點定位得到的粗略定位結(jié)果作為初始值x0，k=0。

2) 計算步徑Δxk=-2f(xk)-1f(xk)和減量fT(xk)2f(xk)-1f(xk)。

5) 更新xk+1=xk+μΔxk，令k=k+1，返回步驟2)。

考慮到修正牛頓法對初始值的依賴性較大[13]，當(dāng)選取的初始值x0不合適時，將會影響迭代收斂的速度，甚至不收斂，因此采用三點定位法對LU節(jié)點的初步定位結(jié)果作為迭代的初始值。同時，若第k個迭代點xk處的Hessian矩陣非正定時，目標(biāo)函數(shù)在xk處的搜索方向Δxk就未必是下降的。所以，對Hessian矩陣進(jìn)行了修正，以保證其充分的正定性，確保隨著迭代的進(jìn)行，目標(biāo)函數(shù)的值單調(diào)下降，從而使得修正牛頓法能夠快速收斂[15]。

3 仿真結(jié)果及分析

為了評價定位的準(zhǔn)確性，采用與文獻(xiàn)[8]相同的評價指標(biāo)：根均方距離(RMSD)。仿真實驗主要參數(shù)如表1所示。同時，為了更加詳細(xì)地描述實驗過程中定位誤差的分布情況，根據(jù)重構(gòu)誤差(MRE)繪制了箱形圖[11]。

(24)

(25)

表1 仿真實驗主要參數(shù)

例1為選取比較合理的LA節(jié)點分布，在噪聲強度為τ=0.20下，對不同的最大測距范圍dmax做仿真實驗。圖2為4種LA節(jié)點分布圖，(a)、(b)、(c)、(d)中LA節(jié)點的分布依次為：LA=r×[1,-1,0,1,-1;1,1,0,-1,-1],r=0.2,0.3,0.4和LA=rand(2,M)-0.5，三角形表示LA節(jié)點，圓圈表示LU節(jié)點。圖3的散點圖是100次仿真實驗所得的平均RMSD，其中方形、菱形、圓形、上三角形分別表示LA節(jié)點分布(a)、(b)、(c)、(d)的仿真結(jié)果，可以看出節(jié)點分布(b)的平均RMSD最小；圖4箱形圖是100次仿真實驗所得MRE的分布情況，其中每組箱形圖分別表示LA節(jié)點分布(a)、(b)、(c)、(d)仿真結(jié)果。顯然LA節(jié)點分布(b)、(c)的MRE是最穩(wěn)定的，異常值比較少、比較小，且LA節(jié)點分布(b)盒形圖的中位線最低。綜合考慮，LA節(jié)點分布(b)定位更為合理，確保了更多的LU節(jié)點周圍至少有3個LA節(jié)點，且更有利于對邊緣位置的LU節(jié)點進(jìn)行初步的定位。

圖2 LA節(jié)點分布圖

圖3 100次仿真實驗的平均RMSD

圖4 100次仿真實驗的MRE分布情況

圖5 100次仿真實驗的平均RMSD

圖6 100次仿真實驗的MRE分布情況

圖7 100次仿真實驗的平均RMSD

例2為驗證本方法初始值x0的選取是否可行，本次仿真對LA節(jié)點分布(b)在相同噪聲強度τ=0.20和不同的最大測距范圍dmax下進(jìn)行了對比實驗。圖5的散點圖是100次仿真實驗所得的平均RMSD，其中方形、菱形和圓形分別表示以隨機(jī)點、本方法和LU節(jié)點真實位置為初始值x0的仿真結(jié)果。從圖5可看出，本方法選取的初始值x0比以隨機(jī)點為初始值x0時所得的平均RMSD小，且與以LU節(jié)點真實位置為初始值x0時的平均RMSD相近。圖6箱形圖是100次仿真實驗所得MRE的分布情況，其中每組箱形圖分別表示以隨機(jī)點、本方法和LU節(jié)點真實位置為初始值x0的仿真結(jié)果。從圖6可看出，本方法選取的初始值x0和以LU節(jié)點真實位置為初始位置x0的MRE最穩(wěn)定，異常值較少、較小，且箱形圖的中位線也最低。因此，本方法選取的初始位置x0是可行的。同時，最大測距半徑dmax越小，傳感器節(jié)點功耗越小，測距數(shù)據(jù)也越可靠，因此取dmax=0.6較為合理。

例3為了客觀地評價本方法的定位性能，本次仿真在相同的LA節(jié)點分布(b)，dmax=0.6和不同的噪聲強度τ下進(jìn)行了對比實驗。其中，噪聲強度τ越大表示測距誤差越大。圖7的散點圖是100次仿真實驗所得的平均RMSD，其中菱形和方形分別表示本方法和文獻(xiàn)[8]的仿真結(jié)果。從圖7可看出，噪聲強度τ較小時，兩者得到的平均RMSD很接近，但當(dāng)噪聲強度τ較大時，本方法所得RMSD明顯更小。圖8箱形圖是100次仿真實驗所得MRE的分布情況，其中每組箱形圖分別表示本方法和文獻(xiàn)[8]方法的仿真結(jié)果。從圖8可看出，噪聲強度τ較小時，兩者盒箱形圖很相似，但當(dāng)噪聲強度τ較大時，本方法的盒形圖中位線更低，異常值更少、更小。表2和表3分別是100次仿真實驗的算法平均迭代次數(shù)和運行時間，表中數(shù)據(jù)顯示該算法平均迭代次數(shù)遠(yuǎn)小于文獻(xiàn)[8]，且運行時間更短。綜上，與文獻(xiàn)[8]相比，在不同程度的測距誤差下，本節(jié)點定位方法定位更快、更準(zhǔn)確。

圖8 100次仿真實驗的MRE分布情況

表2 例3中100次仿真實驗的算法平均迭代次數(shù)

表3 例3中100次仿真實驗的運行時間 s

4 結(jié)束語

針對WSN中節(jié)點間測距誤差導(dǎo)致節(jié)點定位不準(zhǔn)確的問題，提出了一種基于圖模型的節(jié)點定位方法，并將定位問題歸結(jié)為一個無約束的凸優(yōu)化問題。對于該定位問題的求解，首先采用了三點定位方法進(jìn)行粗略定位，然后采用修正牛頓法進(jìn)行迭代優(yōu)化。仿真實驗表明，與現(xiàn)有方法相比，本算法在不同程度的測距誤差下定位更快、更準(zhǔn)確。后續(xù)工作將把更多圖模型的理論和方法應(yīng)用到節(jié)點定位中，克服對節(jié)點位置初始值的依賴和對最大測距范圍的局限性，并對大規(guī)模WSN中的節(jié)點進(jìn)行定位。