趙海兵， 蔣俊正

(桂林電子科技大學(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)用價(jià)值的。例如環(huán)境污染監(jiān)測、森林火災(zāi)監(jiān)測和天然氣管道監(jiān)測等應(yīng)用場景中，WSN中的傳感器節(jié)點(diǎn)不僅需要提供監(jiān)測對(duì)象的信息，還要包含節(jié)點(diǎn)自身的位置信息。因此，WSN中傳感器節(jié)點(diǎn)定位技術(shù)的研究就顯得尤為重要。

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

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

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

1 定位問題的圖模型

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

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

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

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個(gè)LU節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)，即N1(i)包含了可以與第i個(gè)LU節(jié)點(diǎn)直接相互通信的所有LU節(jié)點(diǎn)，N2(i)包含了可以與第i個(gè)LU節(jié)點(diǎn)直接相互通信的所有LA節(jié)點(diǎn)。

由于WSN以無線的方式進(jìn)行通信，且節(jié)點(diǎn)發(fā)射信號(hào)的功率和接收到信號(hào)的功率都可以測得，節(jié)點(diǎn)間距離可以通過RSS測距技術(shù)[6]獲取。但是在現(xiàn)實(shí)環(huán)境下，發(fā)射信號(hào)在傳輸過程中易受多徑衰落和陰影衰落等影響，所以根據(jù)信號(hào)的衰減特性測得的距離并非兩節(jié)點(diǎn)間的真實(shí)距離。于是，考慮到節(jié)點(diǎn)間距離越遠(yuǎn)，測距時(shí)受到干擾的不確定性越大，測距數(shù)據(jù)越不可靠，則節(jié)點(diǎn)間的測得距離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é)點(diǎn)的坐標(biāo)位置和RSS技術(shù)測得的節(jié)點(diǎn)間距離，求解LU節(jié)點(diǎn)的坐標(biāo)位置。

2 定位問題的求解

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

(16)

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

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

(17)

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

2.1 初始值x0的選取

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

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

(18)

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

(19)

圖1 三點(diǎn)定位法示意圖

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

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

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

2.2 迭代優(yōu)化

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

(20)

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

(21)

4(xTBiix-xTCika-aTDkix+

(22)

(23)

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

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

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

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

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

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

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

(24)

(25)

表1 仿真實(shí)驗(yàn)主要參數(shù)

例1為選取比較合理的LA節(jié)點(diǎn)分布，在噪聲強(qiáng)度為τ=0.20下，對(duì)不同的最大測距范圍dmax做仿真實(shí)驗(yàn)。圖2為4種LA節(jié)點(diǎn)分布圖，(a)、(b)、(c)、(d)中LA節(jié)點(diǎn)的分布依次為：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é)點(diǎn)，圓圈表示LU節(jié)點(diǎn)。圖3的散點(diǎn)圖是100次仿真實(shí)驗(yàn)所得的平均RMSD，其中方形、菱形、圓形、上三角形分別表示LA節(jié)點(diǎn)分布(a)、(b)、(c)、(d)的仿真結(jié)果，可以看出節(jié)點(diǎn)分布(b)的平均RMSD最?。粓D4箱形圖是100次仿真實(shí)驗(yàn)所得MRE的分布情況，其中每組箱形圖分別表示LA節(jié)點(diǎn)分布(a)、(b)、(c)、(d)仿真結(jié)果。顯然LA節(jié)點(diǎn)分布(b)、(c)的MRE是最穩(wěn)定的，異常值比較少、比較小，且LA節(jié)點(diǎn)分布(b)盒形圖的中位線最低。綜合考慮，LA節(jié)點(diǎn)分布(b)定位更為合理，確保了更多的LU節(jié)點(diǎn)周圍至少有3個(gè)LA節(jié)點(diǎn)，且更有利于對(duì)邊緣位置的LU節(jié)點(diǎn)進(jìn)行初步的定位。

圖2 LA節(jié)點(diǎn)分布圖

圖3 100次仿真實(shí)驗(yàn)的平均RMSD

圖4 100次仿真實(shí)驗(yàn)的MRE分布情況

圖5 100次仿真實(shí)驗(yàn)的平均RMSD

圖6 100次仿真實(shí)驗(yàn)的MRE分布情況

圖7 100次仿真實(shí)驗(yàn)的平均RMSD

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

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

圖8 100次仿真實(shí)驗(yàn)的MRE分布情況

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

表3 例3中100次仿真實(shí)驗(yàn)的運(yùn)行時(shí)間 s

4 結(jié)束語

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