可容忍信標誤差的三維傳感網節點定位方法

郭曉雷 于 寧 吳銀鋒 萬江文

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

可容忍信標誤差的三維傳感網節點定位方法

郭曉雷 于 寧 吳銀鋒 萬江文

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

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

無線傳感器網絡;三維定位;信標位置誤差;正交回歸;Cramér-Rao界

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

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

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

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

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

1 問題分析

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

式中，Xa為自變量，其觀測值為信標節點聲明的坐標{X'1，X'2，…，X'K};da為因變量，其觀測值為距離估計值{d'1，d'2，…，d'K}，相應的觀測誤差為{e1，e2，…，eK};Xu為模型的回歸參數.

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

圖1 節點三維定位示意圖

當信標節點的坐標不存在誤差，且ea服從均值為0的正態分布時，NLSE可以最大限度降低距離估計誤差對節點定位的影響，是Xu的極大似然最優估計.但在實際應用中，NLSE為最優估計的前提條件并不滿足，主要體現在兩個方面:

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

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

圖2 多跳距離估計誤差概率密度分布統計圖

2 正交回歸方法

針對NLSE方法存在的問題，本文將信標位置誤差和距離估計偏差同時引入到節點坐標估計過程中，提出一種基于正交回歸的傳感網多跳定位方法.

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

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

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

這樣式(2)可以轉化為

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

步驟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為一極小門限值)，轉到步驟9;否則，執行下一步.

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

具體方法如下:

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

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

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

其中

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

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

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

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

步驟8如果i≥Imax，轉到步驟9，Imax為迭代運算的最大允許次數;否則，轉到步驟2.

步驟9運算停止，輸出

通過上述運算，可以得到信標位置誤差和距離估計誤差并存時的節點坐標估計值.

3 定位精度評估標準(3D-MCRB)

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

F1和F2的取值分別為

F1中的聯合條件分布對數似然函數為

其相應的偏導數為

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

F2表達式中的聯合分布對數似然函數為

其偏導數為

于是，F2表達式中的左上角塊矩陣為

通過上述推導，b無偏估計的CRB不等式為

式中

Xu無偏估計的CRB不等式為

式中

這樣，通過計算I(Xu)可以推出節點坐標估計誤差的下限，即信標位置和距離估計兩方面的誤差并存時三維傳感網多跳定位所能達到的最高精度.

4 仿真實驗

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

4.1 信標位置誤差對定位性能的影響

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

圖3 信標位置誤差均值對定位性能的影響

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

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

圖4 信標位置誤差標準差對定位性能的影響

圖5 測距誤差標準差對定位性能的影響

4.3 不同網絡連通度下定位性能分析

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

圖6 網絡連通度對定位性能的影響

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

5 結論

由于信標位置的不確定性和多跳距離估計的有偏性，節點自定位時需要將自變量誤差和因變量偏差同時考慮在內.本文給出一種適用于大規模三維無線傳感器網絡的節點多跳定位方法，采用正交回歸技術，最小化信標位置和距離估計兩方面的擾動對節點坐標估計的影響，增強傳感網定位系統的容錯性能.在大多數實驗條件下，相對于非線性最小二乘法，CWOR能將定位精度提高10%以上，定位誤差更接近3D-MCRB;在網絡連通度較小時，CWOR具有更加明顯的優勢.

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，Fidan 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，Feng 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;網絡出版時間:2012-06-15 15:44

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

國家自然科學基金資助項目(60974121，61001138)

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