可容忍信標(biāo)誤差的三維傳感網(wǎng)節(jié)點(diǎn)定位方法

郭曉雷 于 寧 吳銀鋒 萬江文

(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院，北京 100191)

可容忍信標(biāo)誤差的三維傳感網(wǎng)節(jié)點(diǎn)定位方法

郭曉雷 于 寧 吳銀鋒 萬江文

(北京航空航天大學(xué) 儀器科學(xué)與光電工程學(xué)院，北京 100191)

針對信標(biāo)位置存在誤差情況下的三維無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位問題，提出一種基于正交回歸的多跳定位方法.同時(shí)考慮到自變量誤差和因變量偏差對節(jié)點(diǎn)坐標(biāo)估計(jì)的影響，基于約束加權(quán)正交回歸參數(shù)估計(jì)準(zhǔn)則，建立可容忍信標(biāo)位置誤差的三維多跳定位模型，解決了信標(biāo)位置和距離估計(jì)兩方面的誤差并存時(shí)的節(jié)點(diǎn)自定位問題，并給出求解節(jié)點(diǎn)坐標(biāo)最優(yōu)值的數(shù)值方法;推導(dǎo)出相應(yīng)的坐標(biāo)估計(jì)精度評估標(biāo)準(zhǔn)3D-MCRB(3D Multi-hop Cramér-Rao Bound).仿真結(jié)果表明:此方法對信標(biāo)位置誤差和距離估計(jì)誤差都具有較好的抑制能力，在大多數(shù)實(shí)驗(yàn)條件下，能將定位精度提高10%以上.

無線傳感器網(wǎng)絡(luò);三維定位;信標(biāo)位置誤差;正交回歸;Cramér-Rao界

無線傳感器網(wǎng)絡(luò)(WSNs，Wireless Sensor Networks)是由大量的傳感器節(jié)點(diǎn)以無線通訊的方式組成的多跳自組織網(wǎng)絡(luò)系統(tǒng)，網(wǎng)絡(luò)化智慧感知、低成本和布置靈活的優(yōu)勢使其成為目前IT領(lǐng)域的研究熱點(diǎn)之一［1］.在實(shí)際應(yīng)用中，傳感器節(jié)點(diǎn)通常隨機(jī)部署(如飛機(jī)布撒等)在不同的環(huán)境中執(zhí)行各種監(jiān)測任務(wù)，自身的位置無法事先確定，因此節(jié)點(diǎn)在部署后首先需要實(shí)時(shí)地進(jìn)行自定位.

近些年，許多學(xué)者都致力于傳感網(wǎng)定位技術(shù)方面的研究，文獻(xiàn)［2－3］對現(xiàn)有的研究成果進(jìn)行了系統(tǒng)的綜述.信標(biāo)節(jié)點(diǎn)作為傳感網(wǎng)定位的基礎(chǔ)，位置坐標(biāo)的準(zhǔn)確性直接影響到整個(gè)傳感網(wǎng)的定位性能，目前大多數(shù)經(jīng)典定位算法都是在信標(biāo)位置完全準(zhǔn)確的理想條件下實(shí)現(xiàn)定位.然而，在實(shí)際中，由于信標(biāo)節(jié)點(diǎn)通常依靠GPS(Global Positioning System)或人工部署的方式來獲取自身的位置信息，坐標(biāo)往往存在一定的不確定性，如何提高傳感網(wǎng)定位對信標(biāo)位置誤差的容忍能力是一個(gè)亟需解決的重要問題.

目前針對信標(biāo)位置存在誤差情況下傳感網(wǎng)定位的解決方案不多，主要有:文獻(xiàn)［4］提出一種基于二階錐規(guī)劃的分布式定位算法，信標(biāo)節(jié)點(diǎn)通過與鄰居節(jié)點(diǎn)交互信息的方式，減小自身的位置誤差，然而頻繁的信息交換使得這種算法能耗較高;文獻(xiàn)［5］針對傳感網(wǎng)迭代定位中初始信標(biāo)及二次信標(biāo)位置存在不確定性的問題，分別利用貝葉斯和最小二乘線性估計(jì)法，以及Monte Carlo重要性采樣和成本函數(shù)法，求出未知節(jié)點(diǎn)坐標(biāo)的后驗(yàn)分布;文獻(xiàn)［6］針對水下/地下傳感網(wǎng)集中式定位問題，建立全局極大似然估計(jì)函數(shù)，采用半定規(guī)劃技術(shù)實(shí)現(xiàn)信標(biāo)位置誤差獨(dú)立分布條件下的所有節(jié)點(diǎn)定位;文獻(xiàn)［7］通過坐標(biāo)求精的方法來解決信標(biāo)位置非理想條件下的傳感網(wǎng)定位問題，在一定程度上提高了系統(tǒng)的定位性能.

以上方法主要集中在二維平面分析問題，大多對網(wǎng)絡(luò)的連通性要求較高，通訊消耗較大，算法的擴(kuò)展性也較差，不太適用于大規(guī)模無線傳感器網(wǎng)絡(luò)的應(yīng)用.

本文從傳感網(wǎng)分布式多跳定位的角度出發(fā)，將信標(biāo)位置誤差和距離估計(jì)偏差同時(shí)引入到節(jié)點(diǎn)坐標(biāo)估計(jì)過程中，在不增加通訊消耗的基礎(chǔ)上，利用正交回歸方法增強(qiáng)系統(tǒng)對信標(biāo)位置誤差的容忍能力，提高傳感網(wǎng)的定位性能.同時(shí)，給出了信標(biāo)位置非理想條件下三維多跳定位的Cramér-Rao界，作為評估算法定位精度的標(biāo)準(zhǔn).

1 問題分析

如圖1所示，未知節(jié)點(diǎn)Nu的坐標(biāo)為Xu=［xu，yu，zu］T，信標(biāo)節(jié)點(diǎn) Na(a=1，2，…，K)的實(shí)際坐標(biāo)為 Xa=［xa，ya，za］T，聲明的坐標(biāo)為 X'a=［x'a，y'a，z'a］T.通過節(jié)點(diǎn)間直接測距和多跳信息交互，Nu可以估計(jì)出自身到信標(biāo)節(jié)點(diǎn)Na的多跳距離d'a，距離估計(jì)誤差為ea.這樣，Nu的定位可以看作是如下非線性回歸模型的參數(shù)估計(jì)問題:

式中，Xa為自變量，其觀測值為信標(biāo)節(jié)點(diǎn)聲明的坐標(biāo){X'1，X'2，…，X'K};da為因變量，其觀測值為距離估計(jì)值{d'1，d'2，…，d'K}，相應(yīng)的觀測誤差為{e1，e2，…，eK};Xu為模型的回歸參數(shù).

對于Xu的求解，通常采用非線性最小二乘法(NLSE，Nonlinear Least Squares Estimator)即

圖1 節(jié)點(diǎn)三維定位示意圖

當(dāng)信標(biāo)節(jié)點(diǎn)的坐標(biāo)不存在誤差，且ea服從均值為0的正態(tài)分布時(shí)，NLSE可以最大限度降低距離估計(jì)誤差對節(jié)點(diǎn)定位的影響，是Xu的極大似然最優(yōu)估計(jì).但在實(shí)際應(yīng)用中，NLSE為最優(yōu)估計(jì)的前提條件并不滿足，主要體現(xiàn)在兩個(gè)方面:

1)從幾何意義上講，NLSE的目標(biāo)是尋找一條(個(gè))觀測點(diǎn)到其垂直距離(觀測方向上)平方和為最小的曲線(面)，它僅僅考慮了因變量存在的誤差，未將自變量誤差考慮在內(nèi).當(dāng)所有變量都存在誤差時(shí)，NLSE的擬合效果和穩(wěn)定性都較差.在傳感網(wǎng)節(jié)點(diǎn)定位中，受到GPS精度或環(huán)境干擾等影響，信標(biāo)節(jié)點(diǎn)聲明的坐標(biāo)并不完全準(zhǔn)確，如果不對其位置誤差(自變量誤差)進(jìn)行有效處理，得到的定位結(jié)果可信度不高.

2)在多跳定位中，距離估計(jì)誤差由測距誤差(隨機(jī)誤差)和多跳折線累積誤差(系統(tǒng)誤差)共同組成，即使節(jié)點(diǎn)間的測距誤差ε服從理想的零均值高斯分布ε～N(0，λ2)，多跳距離估計(jì)誤差分布的均值也不一定為0.在ε～N(0，λ2)的條件下，統(tǒng)計(jì)λ分別為(2，4，6)時(shí)多跳距離估計(jì)誤差的概率密度分布(PDF，Probability Distribution Function)結(jié)果如圖2所示.圖2驗(yàn)證了多跳距離估計(jì)誤差近似有偏正態(tài)分布的特性.因此，在求解節(jié)點(diǎn)坐標(biāo)時(shí)，還需要將距離估計(jì)偏差(因變量偏差)考慮在內(nèi).

圖2 多跳距離估計(jì)誤差概率密度分布統(tǒng)計(jì)圖

2 正交回歸方法

針對NLSE方法存在的問題，本文將信標(biāo)位置誤差和距離估計(jì)偏差同時(shí)引入到節(jié)點(diǎn)坐標(biāo)估計(jì)過程中，提出一種基于正交回歸的傳感網(wǎng)多跳定位方法.

設(shè)Na聲明的坐標(biāo)在(x，y，z)方向上的誤差(vax，vay，vaz)相互獨(dú)立，均服從均值為 μa、方差為的正態(tài)分布，則Na的位置誤差向量為Va=，其分布，均值向量 Ma=［μa，μa，μa］T.在多跳定位中，ea的分布規(guī)律隨網(wǎng)絡(luò)部署環(huán)境的不同而變化，設(shè)ea～，均值(距離估計(jì)偏差)b和方差都為未知數(shù).考慮到約束加權(quán)正交回歸(CWOR，Constrained Weighted Orthogonal Regression)方法可以同時(shí)降低因變量和自變量兩方面的擾動(dòng)對回歸參數(shù)估計(jì)的影響，且有效避免局部最優(yōu)值的出現(xiàn)，這里將其應(yīng)用于信標(biāo)位置誤差和ea并存時(shí)的節(jié)點(diǎn)坐標(biāo)估計(jì)中，由此建立三維無線傳感器網(wǎng)絡(luò)多跳定位模型為

當(dāng)pa=qa時(shí)，式(2)的目標(biāo)是尋找一個(gè)觀測點(diǎn)到其正交距離平方和為最小的曲面，它能最小化自變量和因變量兩方面誤差對模型參數(shù)估計(jì)的影響，因此是一種較為理想的回歸方法.

在式(2)中，目標(biāo)函數(shù)包含的平方項(xiàng)個(gè)數(shù)為4K，回歸參數(shù)個(gè)數(shù)為3K+4，而NLSE目標(biāo)函數(shù)中平方項(xiàng)和回歸參數(shù)的個(gè)數(shù)僅為K和3.相對于NLSE，CWOR模型的求解規(guī)模明顯增大.如果仍采用傳統(tǒng)的適用于NLSE的數(shù)值方法求解式(2)的最優(yōu)值Z^，所需的計(jì)算量和存儲(chǔ)量都較大.為了簡化Z^的求解過程，本文參考文獻(xiàn)［8］中數(shù)值計(jì)算的思想，對其中算法進(jìn)行局部修改或簡化，同時(shí)引入約束條件，得到求解信標(biāo)位置非理想條件下CWOR定位模型最優(yōu)值的數(shù)值方法.

這樣式(2)可以轉(zhuǎn)化為

目標(biāo)函數(shù)S(Z)的梯度G(Z)=2J(Z)T·f(Z)，其中J(Z)為f(Z)的Jacobian矩陣，表達(dá)式為

步驟2求 解 S(Z)的 梯 度 G(i)=2(J(i))Tf(i)，其中 J(i)=J(Z(i))，f(i)=f(Z(i)).如果‖G(i)‖2≤τ1成立(τ1為一極小門限值)，轉(zhuǎn)到步驟9;否則，執(zhí)行下一步.

步驟3求解一個(gè)正交矩陣Q(i)，使得

具體方法如下:

2)對J(i)a做QR分解，得到這樣

4)分別取a=(1，2，…，K)，進(jìn)行K次上述運(yùn)算，得到所有的和

步驟4求解如下帶約束條件的線性最小二乘問題，得到和Δb(i):

其中

上式的求解，可以通過變量代換將其轉(zhuǎn)化為最小距離規(guī)劃(LDP，Least Distance Programming)問題［9］來實(shí)現(xiàn).

步驟5分別取a=(1，2，…，K)，求解如下線性方程，得到所有的ΔV(i)a:

步驟6令，其中ΔZ(i)=

步驟7如果|ΔS(i)|≤τ2和‖ΔZ(i)‖2≤τ3中任意一個(gè)成立(τ2和τ3都為極小的門限值)，轉(zhuǎn)到步驟9;否則，令i=i+1，轉(zhuǎn)到下一步.

步驟8如果i≥Imax，轉(zhuǎn)到步驟9，Imax為迭代運(yùn)算的最大允許次數(shù);否則，轉(zhuǎn)到步驟2.

步驟9運(yùn)算停止，輸出

通過上述運(yùn)算，可以得到信標(biāo)位置誤差和距離估計(jì)誤差并存時(shí)的節(jié)點(diǎn)坐標(biāo)估計(jì)值.

3 定位精度評估標(biāo)準(zhǔn)(3D-MCRB)

基于估計(jì)理論中的克拉美-羅界(CRB，Cramér-Rao Bound)原理給出一種評價(jià)標(biāo)準(zhǔn)，對定位精度進(jìn)行評價(jià).設(shè)，其中 Z1=是隨機(jī)參數(shù)向量是非隨機(jī)參數(shù)向量.這樣，對于式(2)所示的多參數(shù)聯(lián)合估計(jì)問題，可以采用隨機(jī)和非隨機(jī)參數(shù)聯(lián)合無偏估計(jì)的CRB作為其估計(jì)性能的評估標(biāo)準(zhǔn)［10］.文獻(xiàn)［5］給出了信標(biāo)位置不確定條件下二維傳感網(wǎng)迭代定位的CRB，在此基礎(chǔ)上，本文將其推廣到三維傳感網(wǎng)多跳定位的場合，給出節(jié)點(diǎn)定位所能達(dá)到的誤差下界3D-MCRB(3D Multihop CRB).

F1和F2的取值分別為

F1中的聯(lián)合條件分布對數(shù)似然函數(shù)為

其相應(yīng)的偏導(dǎo)數(shù)為

根據(jù)ED'{(D'－D －B)(D'－D －B)T}=Σ2，可得

F2表達(dá)式中的聯(lián)合分布對數(shù)似然函數(shù)為

其偏導(dǎo)數(shù)為

于是，F(xiàn)2表達(dá)式中的左上角塊矩陣為

通過上述推導(dǎo)，b無偏估計(jì)的CRB不等式為

式中

Xu無偏估計(jì)的CRB不等式為

式中

這樣，通過計(jì)算I(Xu)可以推出節(jié)點(diǎn)坐標(biāo)估計(jì)誤差的下限，即信標(biāo)位置和距離估計(jì)兩方面的誤差并存時(shí)三維傳感網(wǎng)多跳定位所能達(dá)到的最高精度.

4 仿真實(shí)驗(yàn)

在200×200×200的三維空間區(qū)域內(nèi)隨機(jī)部署200個(gè)傳感器節(jié)點(diǎn)，其中信標(biāo)節(jié)點(diǎn)個(gè)數(shù)S1=20，未知節(jié)點(diǎn)個(gè)數(shù)S2=180.在默認(rèn)條件下，網(wǎng)絡(luò)連通度為12，節(jié)點(diǎn)間測距誤差ε～N(0，12)，信標(biāo)位置誤差向量V～N(M，σ2I)，M=［μ，μ，μ］T，μ=1，σ=1.為了避免參考野值的出現(xiàn)，將信標(biāo)節(jié)點(diǎn)坐標(biāo)在任一方向上的誤差都限制在±15之內(nèi).仿真中，相同條件下的實(shí)驗(yàn)都運(yùn)行100次，取NLSE和CWOR兩種方法的平均定位誤差(ALE，Average Localization Error)與相應(yīng)的3D-MCRB進(jìn)行比較.ALE和3D-MCRB的計(jì)算公式如下:

4.1 信標(biāo)位置誤差對定位性能的影響

分別改變信標(biāo)位置誤差的均值μ和標(biāo)準(zhǔn)差σ，得到兩種方法的ALE和相應(yīng)的3D-MCRB對比結(jié)果如圖3和圖4所示.隨著μ增大，NLSE的ALE大致呈逐漸增長的趨勢，在μ=5時(shí)，其ALE超過50%;CWOR受μ的影響較小，其ALE始終不超過30%;由于節(jié)點(diǎn)坐標(biāo)無偏估計(jì)的CRB與μ無關(guān)，因此圖3中的3D-MCRB幾乎為一條直線.圖4中，3條曲線都隨σ的增大逐漸上升，其中NLSE的曲線變化最為明顯，CWOR和3D-MCRB的變化趨勢大致相同;CWOR的定位精度始終比NLSE的高14%以上，在 σ=8時(shí)甚至能達(dá)到26%.3D-MCRB顯示了節(jié)點(diǎn)坐標(biāo)無偏估計(jì)可能達(dá)到的誤差下界，在兩種情況下，CWOR僅比3DMCRB高10%左右.綜上分析，CWOR對信標(biāo)位置誤差具有較強(qiáng)的容忍能力.

圖3 信標(biāo)位置誤差均值對定位性能的影響

4.2 測距誤差對定位性能的影響

圖5為平均定位誤差隨測距誤差標(biāo)準(zhǔn)差λ變化的關(guān)系圖.在不同λ下，NLSE的ALE始終高于節(jié)點(diǎn)通訊半徑的40%，最大為58.7%.在 λ≤6時(shí)，CWOR的ALE變化不明顯，始終處于25% ～27%之間;在λ=7時(shí)，也僅為30%;繼續(xù)增大λ，CWOR的ALE在λ=9時(shí)才略超過40%(仍比NLSE低13%，相應(yīng)的3D-MCRB此時(shí)已經(jīng)達(dá)到26%).因此，CWOR對測距誤差具有一定的抑制能力，在λ不大時(shí)效果較明顯.

圖4 信標(biāo)位置誤差標(biāo)準(zhǔn)差對定位性能的影響

圖5 測距誤差標(biāo)準(zhǔn)差對定位性能的影響

4.3 不同網(wǎng)絡(luò)連通度下定位性能分析

改變R，得到不同連通度下傳感網(wǎng)定位精度對比曲線如圖6所示.

圖6 網(wǎng)絡(luò)連通度對定位性能的影響

隨著網(wǎng)絡(luò)連通度的增大，不相鄰節(jié)點(diǎn)間的最短路徑接近直線的概率增大(多跳折線累積誤差減小)，同時(shí)未知節(jié)點(diǎn)在信息幀生命周期(TTL，Time To Live)范圍內(nèi)可以獲得的參考信息數(shù)量增加，因此兩種方法的ALE都呈逐漸下降的趨勢.在網(wǎng)絡(luò)連通度較小時(shí)(不大于9)，相對于NLSE，CWOR能夠顯著提高傳感網(wǎng)的定位精度(超過30%)，其ALE接近3D-MCRB;在網(wǎng)絡(luò)連通度為15時(shí)，CWOR仍能將定位精度提高約14%.

5 結(jié)論

由于信標(biāo)位置的不確定性和多跳距離估計(jì)的有偏性，節(jié)點(diǎn)自定位時(shí)需要將自變量誤差和因變量偏差同時(shí)考慮在內(nèi).本文給出一種適用于大規(guī)模三維無線傳感器網(wǎng)絡(luò)的節(jié)點(diǎn)多跳定位方法，采用正交回歸技術(shù)，最小化信標(biāo)位置和距離估計(jì)兩方面的擾動(dòng)對節(jié)點(diǎn)坐標(biāo)估計(jì)的影響，增強(qiáng)傳感網(wǎng)定位系統(tǒng)的容錯(cuò)性能.在大多數(shù)實(shí)驗(yàn)條件下，相對于非線性最小二乘法，CWOR能將定位精度提高10%以上，定位誤差更接近3D-MCRB;在網(wǎng)絡(luò)連通度較小時(shí)，CWOR具有更加明顯的優(yōu)勢.

References)

［1］ BurattiC，Conti A，DardariD，et al.An overview on wireless sensor networks technology and evolution［J］.Sensors，2009，9(9):6869－6896

［2］ Boukerche A，Oliveira H A B F，Nakamura E F，el al.Localization systems for wireless sensor networks［J］.IEEE Wireless Communications，2007，14(6):6 －12

［3］ Mao G Q，F(xiàn)idan B，Anaderson B D O.Wireless sensor network localization techniques［J］.Computer Networks，2007，51(10):2529－2553

［4］ Srirangarajan S，Tewfik A H，Luo ZQ.Distributed sensor network localization using SOCP relaxation［J］.IEEE Transactions on Wireless Communications，2008，7(12):4886 －4895

［5］ Vemula M，Bugallo M E，Djuric PM.Sensor self-localization with beacon position uncertainty［J］.Signal Processing，2009，89(6):1144－1154

［6］ Lui KW K，Ma W K，So H C，et al.Semi-definite programming algorithms for sensor network node localization with uncertainties in anchor positions and/or propagation speed［J］.IEEE Transactions on Signal Processing，2009，57(2):752 －763

［7］ Wan Jiangwen，Yu Ning，F(xiàn)eng Renjian，et al.Localization refinement for wireless sensor networks［J］.Computer Communications，2009，32(13 －14):1515 －1524

［8］ Schwetlick H，Tiller V.Numerical methods for estimating parameters in nonlinear models with errors in the variables［J］.Te chnometrics，1985，27(1):17 － 24

［9］ Lawson C L，Hanson R J.Solving least squares problem［M］.Philadelphia:Society for Industrial and Applied Mathematics，1995

［10］ Messer H.The hybrid Cramer-Rao lower bound-from practice to theory［C］//In Proceedings of Fourth IEEE Workshop on Sensor Array and Multichannel Processing.Waltham:Signal Processing Society，2006:304 －307

(編 輯:劉登敏)

Beacon error-tolerable method for node localization in 3D w ireless sensor networks

Guo Xiaolei Yu Ning Wu Yinfeng Wan Jiangwen
(School of Instrument Science and Opto-electronics Engineering，Beijing University of Aeronautics and Astronautics，Beijing 100191，China)

For 3D wireless sensor networks(WSNs)with inaccurately positioned beacon nodes，a novel multi-hop node localizationmethod that can tolerate beacon position errorswas proposed.The influences of independent variable errors and dependent variable biases on node coordinate estimation were taken into account simultaneously.Based on the principle of constrained weighted orthogonal regression，a reliable 3Dmulti-hop localization model was constructed，and the numerical method for calculating the optimum value of node coordinates was given.The 3D multi-hop Cramér-Rao bound(3D-MCRB)for node localization under combined uncertainties in beacon positions and estimative distances was also derived.Simulation results show that the novel method is robust against beacon position errors and distance estimation errors.Inmostexperiment conditions，the multi-hop localization accuracy can be improved by at least10%.

wireless sensor networks;3D localization;beacon position error;orthogonal regression;Cramér-Rao bound

TP 393

A

1001-5965(2012)06-0810-06

2011-03-24;網(wǎng)絡(luò)出版時(shí)間:2012-06-15 15:44

www.cnki.net/kcms/detail/11.2625.V.20120615.1544.034.htm l

國家自然科學(xué)基金資助項(xiàng)目(60974121，61001138)

郭曉雷(1983 －)，男，河北石家莊人，博士生，sensory@buaa.edu.cn.